Java-Gaming.org Hi !
 Featured games (91) games approved by the League of Dukes Games in Showcase (757) Games in Android Showcase (229) games submitted by our members Games in WIP (844) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
 Home Help Search Login Register
Pages: [1]
 ignore  |  Print
 datastrukture for intersection  (Read 2170 times) 0 Members and 1 Guest are viewing this topic.
Middy

Junior Devvie

Java games rock!

 « Posted 2004-01-26 08:30:44 »

Well at our scene have a number of objects present. They are all moving around. Obviously we need to check for intersection.  But currently we have to check for each object versus each object. This is not a good solution.

Is there an efficient datastrukture for this?. Can we store the objects in a way so we quickly can determine wich objects to checj for intersection and wich we shouldent. Oct-trees?, for instance?

What are you doing in your project?

When do I get my makeMyGameAsILike() extension?
princec

« JGO Spiffy Duke »

Medals: 1033
Projects: 3
Exp: 20 years

Eh? Who? What? ... Me?

 « Reply #1 - Posted 2004-01-26 09:14:49 »

<big edit when wrong formula realised>

When dealing object collisions you've got a triangular number; for n objects you have to deal with n^2 - ((n-1)^2)/2 collisions. This is an O(n^2) algorithm then, that being the largest term. As n grows, it gets slower and slower for each n.

To divide and conquer this using a binary space partition you will, for every reduction in n by half, reduce the algorithmic time of collision by 4. However - you then have to add the cost of classifying each object into its appropriate space.

Cas

Middy

Junior Devvie

Java games rock!

 « Reply #2 - Posted 2004-01-26 10:03:34 »

The objetcs are moving i (random) directions. So a maintenance of a BSP tree would have to happen each  tick. That takes O(n^2) as well and would probably leave use where we started (probably even more work)

Idea
We want to know if ONE objects collides wth others(the sip the player moves around in). Maybe Range trees combined with a sort of bounding box would do it?

When do I get my makeMyGameAsILike() extension?
 Games published by our own members! Check 'em out!
Orangy Tang

JGO Kernel

Medals: 57
Projects: 11

Monkey for a head

 « Reply #3 - Posted 2004-01-26 12:47:51 »

A quad or oct tree tends to work pretty well for moving objects I've found, perhaps a loose one if things are moving quite rapidly.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
princec

« JGO Spiffy Duke »

Medals: 1033
Projects: 3
Exp: 20 years

Eh? Who? What? ... Me?

 « Reply #4 - Posted 2004-01-26 14:29:22 »

Before you go all wandering off and creating some wacky and clever algorithm just exactly how many objects are there anyway and what's your time budget to do a collision test? If we're talking only 100 objects then that's only 5,000 collision tests per frame - or about 5,000,000 clock cycles at a guess - less than 1% of your typical CPU horsepower. At 1,000 objects it's more like 500m cycles which is likely to end up being 100% CPU bound on slower chips. But then - how often do you need to check for collisions? Can it be done every other frame?

(I wonder how many cycles a simple sphere-radius collision actually costs?)

If you're dealing with over 200 objects per frame I'd at least classify them into an octree first. The octree depth is the important number to consider here. Maybe use a depth equal to the number of 0's (100-999 objects, use depth=2, 1000-9999, use depth=3, etc). Worth a shot.

Cas

erikd

JGO Ninja

Medals: 16
Projects: 4
Exp: 14 years

Maximumisness

 « Reply #5 - Posted 2004-01-26 14:36:50 »

Yes, Cosmic Trip checks collision for every object against every object in every frame and time spent there is minimal.
I usually implement things the unclever way and only try to think of clever things when they turn out to be too slow
It all depends on your needs I guess, as Cas pointed out.

Orangy Tang

JGO Kernel

Medals: 57
Projects: 11

Monkey for a head

 « Reply #6 - Posted 2004-01-26 15:15:07 »

Quote
(I wonder how many cycles a simple sphere-radius collision actually costs?)

 1  2  3  4  5  6  7  8 `            float dx = this.center.x - circle.getX();            float dy = this.center.y - circle.getY();                        float separationSquared = dx*dx + dy*dy;            if (separationSquared < radius*radius)                  return true;            else                  return false;`

Hmm..
7(?) register stores
3 mults
2 subtract
1 compare

Assuming a 1Ghz CPU and 200Mhz memory a memory read turns out to be 5 ticks. Floating point multipy is what, 3 or 4 cycles? Call it 5 to be on the safe side. Add/sub can probably be done in a couple, call it 3. Total of 4*5 + 7 + 3*5 + 2*3 + 1*3 + 1 = 52 cycles total.

Probably quite wrong actually but worth a guess (and I'm not even going to attempt to think about pipelining ). And I think I've probably missed a few register moves and stores to reshuffle things mid flow, but they should be pretty cheap.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
abies

Senior Devvie

 « Reply #7 - Posted 2004-01-26 17:14:38 »

Quote

Assuming a 1Ghz CPU and 200Mhz memory a memory read turns out to be 5 ticks. Floating point multipy is what, 3 or 4 cycles? Call it 5 to be on the safe side. Add/sub can probably be done in a couple, call it 3. Total of 4*5 + 7 + 3*5 + 2*3 + 1*3 + 1 = 52 cycles total.

Memory access cost will vary depending if data is in cache. If it is inside, it can be almost free . If not, you will pay a lot more that just 5 CPU cycles - we are talking about 6-8 MEMORY cycles for reading random place in memory - in your example, it translates to 30-40 cpu cycles, can be a lot more on faster CPU. Hopefully x and y will be near each other, so second read will be already from cache - but we are talking about variance from 0 to 80 cpu cycles for memory access alone. Mispredicted branch at end can easily cost 10-20 cycles depending on CPU type.

Depending on code layout, computations in code can go in parallel, fitting well in pipelines (but I would maybe try to move dx*dx into temp variable before executing second memory access?). Anyway, cost of rest of code can be in 10-30 cycles range - plus 0-80 cycles penalty for possible main memory access and mispredicted branching.

If somebody cares to write such code in C (working on realistic data set), it is easy to see cache missed with AMD Codeanalyst. It should be also possible to see actual pairing/pipeline stalls with it. Too bad it doesn't work with jitted java code...

Middy

Junior Devvie

Java games rock!

 « Reply #8 - Posted 2004-01-26 17:35:44 »

cas is prolly right. We are talking below a 100 objects. This was nice. A problem solved that werent a problem at all

When do I get my makeMyGameAsILike() extension?
Pages: [1]
 ignore  |  Print

 EgonOlsen (76 views) 2018-06-10 19:43:48 EgonOlsen (56 views) 2018-06-10 19:43:44 EgonOlsen (76 views) 2018-06-10 19:43:20 DesertCoockie (256 views) 2018-05-13 18:23:11 nelsongames (156 views) 2018-04-24 18:15:36 nelsongames (155 views) 2018-04-24 18:14:32 ivj94 (896 views) 2018-03-24 14:47:39 ivj94 (157 views) 2018-03-24 14:46:31 ivj94 (809 views) 2018-03-24 14:43:53 Solater (173 views) 2018-03-17 05:04:08
 Java Gaming Resourcesby philfrei2017-12-05 19:38:37Java Gaming Resourcesby philfrei2017-12-05 19:37:39Java Gaming Resourcesby philfrei2017-12-05 19:36:10Java Gaming Resourcesby philfrei2017-12-05 19:33:10List of Learning Resourcesby elect2017-03-13 14:05:44List of Learning Resourcesby elect2017-03-13 14:04:45SF/X Librariesby philfrei2017-03-02 08:45:19SF/X Librariesby philfrei2017-03-02 08:44:05
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org