Java-Gaming.org Hi !
 Featured games (84) games approved by the League of Dukes Games in Showcase (601) Games in Android Showcase (171) games submitted by our members Games in WIP (649) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 datastrukture for intersection  (Read 1302 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: 555
Projects: 3
Exp: 16 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?
Orangy Tang

JGO Kernel

Medals: 57
Projects: 11

 « 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: 555
Projects: 3
Exp: 16 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

 « 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

You cannot reply to this message, because it is very, very old.

 Jesse (12 views) 2015-07-29 04:35:27 Riven (33 views) 2015-07-27 16:38:00 Riven (18 views) 2015-07-27 15:35:20 Riven (20 views) 2015-07-27 12:26:13 Riven (11 views) 2015-07-27 12:23:39 BurntPizza (30 views) 2015-07-25 00:14:37 BurntPizza (40 views) 2015-07-24 22:06:39 BurntPizza (24 views) 2015-07-24 06:06:53 NoxInc (27 views) 2015-07-22 22:16:53 NoxInc (18 views) 2015-07-22 22:13:39
 wessles 48x theagentd 45x basil_ 35x orangepascal 28x KaiHH 27x ags1 19x Riven 19x mooman219 17x princec 14x KudoDEV 13x bornander 12x klaus 11x Jesse 10x philfrei 9x Zaneris 9x deepthought 8x
 List of Learning Resourcesby gouessej2015-07-09 11:29:36How Do I Expand My Game?by bashfrog2015-06-14 11:34:43List of Learning Resources2015-05-31 05:37:30Intersection Methodsby Roquen2015-05-29 08:19:33List of Learning Resources2015-05-05 10:20:32How to: JGO Wikiby Mac702015-02-17 20:56:162D Dynamic Lighting2015-01-01 20:25:42How do I start Java Game Development?by gouessej2014-12-27 19:41:21
 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