This is a version of Gary William Flake’s Termite Algorithm1 (also see this earlier version ) which stores all the chips within a QuadTree . The QuadTree is implemented similarly to Dan Shifman’s version on The Coding Train .

While the QuadTree does not provide much impovment’s as the number of chips increases (this is due (I think) to the fact that the QuadTree must be rebuilt each iteration), it does, however allow for the number of Termites to increase dramatically since each termite must perform many fewer distance calculations. Therefore, the rate of termite steps per second is quite high.

Some important Variables and Stats:

Quad Tree max child count
The treshold of how many chips can be in a QuadTree before it subdivides and distributes its children into these new subdivisions. As this number goes up, the “deapth” of the entire QuadTree is limited, however, it means that a termite will have larger populations to search through.
QuadTree Min Side length
This threshold prevents the deapth of the entire QuadTree from going out of control – as the chipas are moved around, they will be moved closer and closer together which result in tiny QuadTrees. These will be hard to search through, create, etc..

  1. The Computational Beauty of Nature : Computer Explorations of Fractals, Chaos, Complex Systems, and Adaptation (MIT Press, 1998) ↩︎