3

I've been trying to implement a spatial partitioning algorithm in my game, but both spatial hashes and quadtrees aren't what I'm looking for.

My level size is not supposed to have a limit (only Int32 limits). I need a spatial partitioning algorithm that doesn't need a "Level Width" and a "Level Height".

I have many moving physical objects. I need the algorithm to be fast enough to support 500+ objects.

Any alternative?

Vittorio Romeo
  • 90,666
  • 33
  • 258
  • 416
  • Why doesn't Quad Trees work for you? Just set the first quad size to int.MaxValue x int.MaxValue and make N separations depending on required search resolution. That should be fast enough. Also, what about BSP? – Andrey Agibalov Jul 22 '11 at 23:43
  • 500 moving object get way too slow with QuadTrees. I need to remove the object from the QuadTree and insert it again every frame (if it moved). – Vittorio Romeo Jul 22 '11 at 23:47
  • You can use object's position delta to quickly decide what is the next node to place object to, that should be very fast. Were you using your own implementation of quad trees? – Andrey Agibalov Jul 22 '11 at 23:52
  • I was using this http://bytes.com/topic/c-sharp/insights/880968-generic-quadtree-implementation ... the "delta position" stuff sounds interesting... can you elaborate? – Vittorio Romeo Jul 23 '11 at 00:22
  • See also http://gamedev.stackexchange.com/questions/15126. – cic May 03 '16 at 22:12

1 Answers1

2

I've decided to go with fixed 2D grids.

I've made two videos which explain in-depth how I implemented them, and the current implementation is available on my GitHub page: https://github.com/SuperV1234/SSVSCollision

http://www.youtube.com/watch?v=7HY_SqqaoL4

http://www.youtube.com/watch?v=vYB37BDtHuQ

Vittorio Romeo
  • 90,666
  • 33
  • 258
  • 416