The need for data structures that allow for some sort of neighbor search and/or region query are quite common in almost any kind of simulation including video games. Possible solutions include simple sorted lists, grids, hash maps, all sorts of trees etc.. I found myself in the situation that I had to implement such a structure many times now and almost always do a little search to see if there are particularly well suited structures for the specific problem I'm trying to solve. Especially in forums any question about this sort of thing will invariably result in someone mentioning a quad/octree in the first few answers (often the first). Accordingly I started out writing a quadtree many times and so far I ditched every one of those attempts and went for something that I felt was better suited. So either quadtrees are overhyped or I just don't know how to write one.

The "replacement" solutions I mostly use are either grids, hash maps or binary trees. Grids work nicely in situations where the domain is finite and in average cases give almost optimal complexity (build in O(n), search in O(1), usually about O(n) memory requirement) and iteration over them can be implemented to be very cache friendily. I use hash maps in pretty much the same situation with the difference that I don't need a finite domains for those. With binary trees I mean the ones where you subdivide the space either along the longest axis (which actually is almost equivalent to a quad/octree) or at the "median" element (kd-tree?).

Quadtrees in comparison just always seemed unwieldy to me. They are "finite domain", "fixed subdivision" structures and seem to mostly combine the disadvantages of the other structures. But given the wide usage I have to assume I'm missing something. I especially get frustrated with their implementation. Not that I don't get them to work or something, It's just that the other structures always look "cleaner" to me, especially the grids which look borderline trivial and are super easy to maintain/test. Also apart from the algorithmic complexity, the "raw speed" (as in measured speed) from say a coarse grid is often better for my use cases (running in a fraction of a single frame) because of the more linear memory access patterns.

So what is the deal with Quadtrees? How are they really efficiently implemented? In what cases are they better than the alternatives?

Also apart from the algorithmic complexity, the "raw speed" (as in measured speed) from say a coarse grid is often better for my use cases (running in a fraction of a single frame) because of the more linear memory access patterns.

So what is the deal with Quadtrees? How are they really efficiently implemented? In what cases are they better than the alternatives?

For special cases like terrain, where you already know that the entire tree will be filled, you can use a pointer free tree, consecutively stored in memory and being pretty fast with little overhead (none, actually, since nodes don't store anything but user data). Besides that I wouldn't use any tree unless the number of objects/data really begs for it.

I think I've read somewhere an article about "relaxed quadtrees" or something. I'd currently like to investigate them in more detail. Standard QuadTrees never catched up with me. Hell, I'm not at home even with BSPs...

For special cases like terrain, where you already know that the entire tree will be filled, you can use a pointer free tree, consecutively stored in memory and being pretty fast with little overhead (none, actually, since nodes don't store anything but user data). Besides that I wouldn't use any tree unless the number of objects/data really begs for it.

Hmm, but then the "tree" is nothing but a storage order? I see the advantage that this order has better "spatial coherence", but it's primarily another way to index a grid, or am I missing something?

Hmm, but then the "tree" is nothing but a storage order? I see the advantage that this order has better "spatial coherence", but it's primarily another way to index a grid, or am I missing something?

I don't think that you're missing anything japro. At a basic level it's exactly another way to index a grid. One point though of the tree over, say, a regular grid is would be memory usage. With a regular grid you need resources to maintain every grid element of the entire world. With the tree you're able to condense empty areas of the world into larger elements and potentially spend that memory to provide a more fine grained partition for areas where there actually are a lot of objects. I wouldn't be surprised if the people that keep saying 'use an octree' are just using that as a shortcut for 'use some form of data structure that provides reasonably spatial partitioning'. Grids can work out great for that, as can octrees or BSP trees.

One thing to remember about any data structure is that they're always situational. If I were building a board game like chess a grid seems like the most reasonable data structure but for something more free-form like a GTA game, maybe it's not.

Hmm, but then the "tree" is nothing but a storage order? I see the advantage that this order has better "spatial coherence", but it's primarily another way to index a grid, or am I missing something?

Pretty much that. If the tree doesn't have additional info (like bounding volumes for each node) there is no reason for it to explicitly exist at all and it just boils down to index your grid a certain way (at this point the tree is probably useless). It's just the one special case, where you can implement a tree without all the child/parent pointers that waste space and make collecting all leaves of a higher up node very painful. It is very useless for dynamic game objects unless your world is so full that (almost) every cell of the underlying grid is actually filled.

Besides that, if there really is any particular love for quadtrees it's probably because the concept is simpler than trees using arbitrary or alternating planes and with even 3D games mostly happening in 2 dimensions they are the most commonly applicable kind of tree.

During the creation of my google maps clone (that is displaying vector & raster data using the mercator projection) a quadtree came in very handy and was several magnitudes faster for frustum culling than an ordinary hash map. Even with "huge" amount of items (about 100.000) it performed quite well and provided other means for culling as well. Drawing so many items would result in too much overdraw (for example if each is represented by a smal 16px² image) and thus less benefit for the user: I quickly came up with an algorithm that filtered out a big percentage of unseen items (basically only N items could be drawn PER bucket, where N is calculated from bucket_size / maximum_item_size).
But as always, choose the right tool for the job: If a quadtree didn't perform as well for you, then it may not be the right one (or your implementation was bad, or you used it wrong, but I can't judge that ;) ).