Questions tagged [spatial-partitioning]
Spatial partitioning refers to dividing up some space (such as the game world) into regions with the intent to efficiently search or traverse those regions or the objects within those regions.
22 questions
1 vote
1 answer
188 views
0 votes
2 answers
120 views
Using spatial hash to determine view distance
I am creating a client/server that is 2D and based on a map. Characters on the server are then separated into a spatial hash. I am using this to determine who to send data to, essentially, people in ...
- 101
0 votes
0 answers
367 views
Can inserting/removing one point in a quadtree or octree cause multiple splits/collapses?
I was reading Robert Nystrom's Game Programming Patterns website and, in the section about spatial partitioning, particularly in the section on quadtrees, he mentions: Objects can be added ...
- 157
1 vote
2 answers
2k views
Optimizing a quadtree for circles and circular queries
I'm developing a 2D ant simulation in JavaScript. I'd like to implement a quadtree to store the positions of ants and other markers. I approximate all of these entities as circles, and I'm only ...
- 19
1 vote
0 answers
189 views
3D Binary Space Partitioning with solid/empty leaves
I've recently started looking into BSPs for real-time collision detection, and I'm now looking into improving the performance of my solution. The system that I've implemented is rather similar to the ...
- 11
0 votes
0 answers
825 views
2D Spatial Hashing in C++ Causing Game to run more Slowly
I'm trying to use spatial hashing to speed up collision detection in my game. I believe spatial hashing is better suited for my game than quadtrees, because I have lots of fast-moving objects in my ...
- 21
1 vote
1 answer
191 views
Does collision detection data structures require a manifold mesh
Is it possible to apply spatial split techniques (oct-trees bsp-trees, etc) when meshes are not necessary manifolds? The mesh in question represents the "map". This means that it is static so spatial ...
- 133
5 votes
2 answers
4k views
Performance problems with quadtree for dynamic objects
I´ve implemented a quadtree spatial partitioning to my game engine as I wanted to try it and see how it affects the performance checks. The results were great (instead of hundreds collision checks ...
- 589