16 votes
Accepted

Fully dynamic KD-Tree vs. Quadtree?

KD-trees are definitively not dynamic enough to be considered, honestly. Moving a few units can easily require you to rebuild the whole KD-Tree. Plus, a KD-tree is very efficient for queries, but ...
  • 1,035
6 votes

Fully dynamic KD-Tree vs. Quadtree?

Lærne's suggestions are great, but I would also suggest a dynamic bounding volume tree of AABBs. Conceptually the dynamic bounding volume tree keeps a balanced tree of nodes which can be queried at ...
  • 3,022
6 votes
Accepted

Should I use octree or quadtree for my spacial data structures?

I'm not really good at fabricating N- statements, but the minimum search times for an object at child[0] of every child[0] should be close to the same +- a dimension. If the object falls at child[4] ...
  • 3,634
4 votes
Accepted

Entity Component System: where do I put containers?

Update I have wrote Theraot.ECS inspired by Fastest way to look up an entity with a set of components?. However this answer motivated me to allow to specify custom containers for particular types. ...
  • 19k
4 votes

Entity Component System: where do I put containers?

Just like with any software architecture question, the short answer is "It depends..." Where do I put that quadtree? Any auxiliary data structures needed by one system only should be part of that ...
  • 113k
3 votes
Accepted

QuadTree-based pathfinding for a volume body

I'm doing research in autonomous navigation for robotics, and this is a familiar problem. The real world analogy is you have two vehicles (a robotic motorcycle and a robotic tank) that have to decide ...
3 votes
Accepted

Quadtree splitting

It's a quad tree so when you split it into 4 parts any entities belonging to the parent get divided between the children based on position.
  • 246
3 votes
Accepted

Using QuadTree for Procedural Generation

As already stated in others comments I think you might be using the quadtree concept to solve the wrong problem. I spend most of my time managing massive amounts of data working with voxels and even ...
  • 1,683
2 votes

QuadTree: store only points, or regions?

I would add this as a comment in response to @Nathan Reed's answer, except it's too big to be a comment, and is perhaps in any case worthy of being a separate answer. We were doing precisely what was ...
  • 121
2 votes
Accepted

Quadtree vs multiple resolution grids for terrain rendering

For performance reasons I never frustum cull on the CPU -- I just distance cull as part of the LOD determination so I'm rendering everything in front of and behind the camera (let the GPU do the ...
  • 444
2 votes

Pair collision detection on quadtree

It depends how you implement double dispatching how elegant it is. You are effectively trying to dispatch to a function that's able to handle collision between types X and Y and execute function for ...
  • 870
2 votes

How to handle (0,0) in 2D game quad tree?

In this case you have to decide what to do. In most cases, this is done automatically for you because your sorting is based upon <=, ...
  • 1,840
2 votes

Where should I store an object? - QuadTree

There are multiple solutions to this problem. You can place the object in the smallest node which fully contains it. You can split its edges among multiple nodes and tag them with which object they ...
2 votes
Accepted

Is there an existing Quadtree implementation in libGDX?

GDX doesn't support it directly. A version for LibGDX https://github.com/alwex/QuadTree
  • 2,502
2 votes

Optimizing a quadtree for circles and circular queries

As explained in the answer by Romen, there aren't many applicable data structures which are not based on rectangles. But there are a couple other optimizations you can do for circle-circle collisions ...
  • 113k
2 votes

Optimizing a quadtree for circles and circular queries

I can't recommend a structure that actually implements what you're asking for, but it definitely won't work like a quad tree. It may not be a tree at all and it might not even exist... A quad tree has ...
  • 331
2 votes
Accepted

Quadtree for AABB collision boxes

There are 2 ways to deal with boxes straddling a boundary. One is to keep the box in the vector of the node where it straddles the boundary and don't push it down. The other is to add the box to all ...
2 votes

How to handle objects at the edges of spatial partition cells?

The simple answer would be to add the object's pointer to both cells. As it exists in both cells, to not include it in both cells would be to circumvent the purpose of having the tree to begin with. ...
  • 514
2 votes

Quad sphere subdivision algorithm

Implementing LOD subdivision on terrain is quite complicated, I rather recommend to use a library or something. But if you prefer to learn the hard way here are the principal steps you need to do: ...
  • 210
1 vote
Accepted

What algorithm is best for finding non-static nearest neighbors on a 2d grid?

An alternative I found was Spatial Hashing. The basics work as such: If I was given a 100x100 world, it would be split into 10x10 chunks. Each chunk holds all the entities in its 10x10 world area. ...
1 vote
Accepted

How can I split my terrain into quads so that each quad would have a renderable vertex/index buffer? (DirectX11, C++)

As I have done what you are trying to do, ala quad tree and splitting into chunks. A couple of things. For optimal performance, I have found that keep the vertex list as one buffer. Do your ...
  • 1,120
1 vote
Accepted

Using Lazer with a Quadtree

you could something like the following, that would at least limit the enemy-ray tests to quads that only intersect the line: ...
1 vote

Drawbacks to an Octree and Quadtree hybrid?

A k-d tree like Philipp suggested would likely be a good solution, but certainly more complicated to implement. Your proposed solution should work fine, but you may need to be clever with how you ...
  • 109
1 vote

Where should I store an object? - QuadTree

One chief concern of putting the object in every leaf node it occupies instead of the inner node that actually contains it is that, when traversing the tree, you have to track whether you have visited ...
  • 3,022
1 vote

QuadTree Checking Collision With Different Levels of Nodes

The answer is yes, of course. You test object b against all L1 nodes in the root because that's where it is. If a node is hit, add it's objects to the short phase (object to object tests) list. ...
  • 454
1 vote

Efficient container(s) for units in an 2D RTS game

Use an influence map for target searching. Have a grid and on each node, reserve a spot in a collection of units for each team. For each unit, generate a collection of coordinates within range and ...
  • 2,051
1 vote

How do I construct the planes for my camera's frustum?

Field of View and Aspect Ratio define how much the frustum planes diverge, so a little math should let you define the 4 planes of the viewport... but then you are stuck with plane/plane intersection ...
  • 444
1 vote

Calculating adjacent quads on a quad sphere

In their paper "Navigating through Triangle Meshes Implemented as Linear Quadtrees", Michael Lee and Hanan Samet propose a method of addressing the nodes (triangles) of a spherical quad-tree such that ...
  • 111

Only top scored, non community-wiki answers of a minimum length are eligible