Quad Trees

In my current implementation, the road generator performs a two-step process during each L-system iteration:

  • generation of map nodes and edges
  • checking of local conditions for each generated node or edge

The local conditions are nicely described in Parish & Mueller’s paper. At this stage, I’m working on implementing checks for road intersections (so that a crossroad can be generated) and the proximity of nodes to existing edges (so they can be “stitched” to the existing edge). This is described visually in Figure 8 of the paper.

It is of course intuitively clear that a brute force solution for checking for a node’s neighbours in a given radius is a very unoptimal one. In just a dozen or so iterations, the L-system spits out so many nodes that Unity starts crumbling down if I just walk through them in an O(n^2) fashion. So, I needed a lookup table of some sort, which would keep the locality information so that the neighbours can be fetched more easily.

Enter quad trees. They have exactly what I want, a fast drill-down to the exact neighbourhood of a given node. After implementing the class and adding each map node to it after spawning it from the L-system, I get something like this:

quad1The quad tree is drawn in cyan, nodes and edges are red. You see I still haven’t fixed that road creation bug, I really like the spiral.¬†You can see how the quad tree is localizing tightly packed nodes into tightly packed subtrees, and sparse areas are covered with larger trees.

Now, what I really like about my quad tree implementation is that the Add method actually returns an instance of the quad tree: if the node was added to the current tree, that tree is returned. If, however, a node is added outside the bounds of the current tree, that tree automatically creates a parent tree, adds itself as its subtree, and then returns the parent quad tree. This way the client can ignore the growth of the quad tree by simply always assigning the result of the Add operation back to its quad tree reference, and voila.

Here’s how it looks zoomed out after the tree has grown a bit:

quad2I still haven’t implemented the fetching of a node’s neighbours, I’ll be working on that in my next hacking session. I know the most correct way would be to specify the radius around the given node for fetching its neighbours, but I think a more “blocky”, approximate solution will be just fine – once you locate the node inside a particular quad tree, just walk the hierarchy upwards until the current quad tree has an area that encapsulates the search circle (given by a node’s position and search radius). We’ll see if that approach is good enough.

Leave a Reply

Your email address will not be published. Required fields are marked *