Unveiling the Fog with Quadtrees

Before my next post on implementing an improved A* to suit Triangulated areas, I thought I’d take another look at the spacial partitioning structure – Quadtrees! Unlike Triangulation, Quadtrees partition space recursively into smaller space as more data points are added.

An interesting use of this is to model complicated shapes in a discrete fashion. Large generic parts of the shape can be represented by high level nodes on the Quadtree, whereas more detailed parts of the shape can be represented as smaller nodes.

In the example above I’ve used a Quadtree to optimise the simulation of the Fog of War – something you can find in many strategy games. The vision of the orange circles is represented as white squares, and the grey squares represent areas outside the vision of the orange circles. You can have a go moving the circles about to reveal different areas.

In this instance the Quadtree can be thought of as storing some simple data in the form of an area, as well as a revelation status flag. Insertions happen into the Quadtree in the form of data points. In this case they also have a radius so an individual data point may end up influencing a large part of the data-structure.

You can see that areas which are highly revealed, or primarily hidden are represented with larger quadrilaterals (to see this ensure the option “Toggle Lines” is on), whereas areas on the border between being revealed or not are represented with much finer quadrilaterals. This is beneficial for several reasons:

• Firstly we reduce the resolution of the data-structure where resolution is not needed, this saves us from storing a very large array of revelation flags. You can see how a uniform grid looks by turning on the option “Use Uniform Grid” to compare the number of quadrilaterals used to represent the same thing.
• Following on from that, the number of spaces we have to query when determining whether or not we have some range of vision that is going to be reduced resulting in a performance increase.
• Additionally we can reduce redundancy when revealing areas on the screen which have already been revealed before. With a uniform grid there is no easy way to know which areas have already been revealed, so we must enumerate many grid spaces for each orange circle. With a Quadtree we know that if a node higher in the tree is revealed, every node below it is too. Thus we don’t need to attempt to reveal those areas and revealing the same area twice becomes very cheap.

The actual revelation of areas is done by imposing the radius of vision upon a node of the tree. If the radius revealed encompasses the entirety of the range the node represents, we can mark the node as containing a revealed flag and quit. Otherwise we need to determine whether the area we are revealing intersects the range of the node at all. If so, we can repeat this process with its child nodes. If not, we know that the range represented by the node is not revealed at all.

We start this process from the root node which encompasses the entire candidate area, thus we reveal nodes recursively until we reach some detail threshold.

I hope I’ve done an ok job explaining how Quadtrees can be used to store data in a unique fashion, let me know if you have any questions in the comments below.

If you’re a software developer looking for a better way to manage errors in your apps, feel free to sign up for Raygun.

Raygun is an error reporting software system covering all major programming languages and platforms. Check out Raygun’s free trial today and find software errors before your users do.