Partition (inter object) Shape Collision

[kevin]

This example is basically an asteroids frame work.   While it doesn't play a full game of asteroids, it's set up to demonstrate a method of partitioning the games world space to help eliminate unnecessary collision checks.  In this case shape intersections.

The partitioning in the example is achieved by cutting up the screen is vertical rectangular regions. Each region is 1 partition.  The partition will hold a list of the objects that share this space.   The partition map is just a 2D array.  Where the X coordinate represents the vertical region and the Y coordinate represents the index of the asteroid in this partition list.  To assign an Asteroid into a partition it's index is simply dropped at the end of the list.   element zero is used as each partitions item counter.

 Each update the partition is cleared.  Then the asteroids are remapped into the partition buffer.  To map them,  all were doing is running through the asteroids, calcing it absolute width, then translating that region to the partition buffer.    When collisions require testing, rather than scan all the objects each time, we poll the partition map for a list of objects that are known to be within our test objects region.  This will give us a short  list of asteroids to check against.  

 There's potentially a logic errors (as objects are moving and checking), but all in all it's good enough... :)

[Big C.]

Great Job...

I am very happy that I find something of mine in your sourcecode...  :)

I get over 280 FPS...

In the case of nearer analysis of the source code I must state that I must learn still a lot  :(  (or translate to understand...  ;) )

Big C.

[medwayman]

You're a fast worker Kevin :)  

I'll have a good look through this

Thanks  :)

[thaaks]

I get around 130 FPS.
I think I will modify the code a bit to add yellow and green flashies to the red flashies and then I can finally stop consuming alcohol and other drugs and just watch the demo  :D

The partitioning code is pretty smart. It even covers asteroids spanning more than two partitions.
I think the only "flaw" if I dare to say so is when you check for collisions. Then you only look at asteroids that are less than 50 pixels away. There you could also calculate the interesting asteroids by using the radius of the checked asteroid (YTop = y - radius, YBottom = y + radius) and use those values to find possible collision asteroids.

I read about this partitioning several times in other forums but never understood how such code could work for moving objects and never found an example (some of those game gurus have a bad habit of only "mentioning" their knowledge and forget about explaining) - but now I know  :D

Thanks for this eye and brain opener!

Cheers,
Tommy

[kevin]

I think the only "flaw" if I dare to say so is when you check for collisions. Then you only look at asteroids that are less than 50 pixels away. There you could also calculate the interesting asteroids by using the radius of the checked asteroid (YTop = y - radius, YBottom = y + radius) and use those values to find possible collision asteroids.

 True, but it does that, as it doesn't pass the collision object in, just the shape index.  As there not all asteroids

 Generally, you'd have a 2D partition rather than columns as seen here.  Given that situation i'd probably still use a trivial reject max radius, before falling to the second level of tests.

 However, one thing that is missing from the demo is a way to stop duplicated tests occurring.  Since objects allocated as they move and prior to moving. it's more than likely you'll end up checking the same object more than once.  

 The remarkable trivial solution is use a unique stamp.   If an object is within range to check, and it's stamp is invalid (<> to current stamp) you check. Once checked, you stamp it with the current stamp.   This way even if it's in the partition 10 times, it only ever gets checked once..

[thaaks]

True, but it does that, as it doesn't pass the collision object in, just the shape index.  As there not all asteroids

Yes, I missed that. You're right.

The remarkable trivial solution is use a unique stamp.   If an object is within range to check, and it's stamp is invalid (<> to current stamp) you check. Once checked, you stamp it with the current stamp.   This way even if it's in the partition 10 times, it only ever gets checked once..

And if you toggle the stamp between 0 and 1 everytime you reset the partitions you don't even need to reset the stamps inside the objects.
We used that once in our Smalltalk system for the "mark and sweep" Garbage collector code. Works fine  :D

Cheers,
Tommy

[stef]

Hi!
Where can I find this code?

stef

[kevin]

attached to the first post

[stef]

thx :D