Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (497)
Games in Android Showcase (114)
games submitted by our members
Games in WIP (563)
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 1088 times)
0 Members and 1 Guest are viewing this topic.
Offline Middy

Junior Member




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?
Offline princec

JGO Kernel


Medals: 378
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 Smiley

Offline Middy

Junior Member




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!
Legends of Yore - The Casual Retro Roguelike
Offline Orangy Tang

JGO Kernel


Medals: 56
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 ]
Offline princec

JGO Kernel


Medals: 378
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 Smiley

Offline 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  Smiley
It all depends on your needs I guess, as Cas pointed out.

Offline Orangy Tang

JGO Kernel


Medals: 56
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..
4 memory reads
7(?) register stores
3 mults
2 subtract
1 add
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 Tongue ). 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 ]
Offline abies

Senior Member





« 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...

Artur Biesiadowski
Offline Middy

Junior Member




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 Smiley

When do I get my makeMyGameAsILike() extension?
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

BurntPizza (8 views)
2014-09-21 00:34:41

moogie (7 views)
2014-09-21 00:26:15

UprightPath (22 views)
2014-09-20 20:14:06

BurntPizza (27 views)
2014-09-19 03:14:18

Dwinin (40 views)
2014-09-12 09:08:26

Norakomi (70 views)
2014-09-10 13:57:51

TehJavaDev (96 views)
2014-09-10 06:39:09

Tekkerue (49 views)
2014-09-09 02:24:56

mitcheeb (70 views)
2014-09-08 06:06:29

BurntPizza (52 views)
2014-09-07 01:13:42
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!