This is a version of Gary William Flake’s Termite Algorithm1 (also see
this earlier version
) which stores all the chips within a
QuadTree is implemented similarly to
Dan Shifman’s version on The Coding Train
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
QuadTreebefore it subdivides and distributes its children into these new subdivisions. As this number goes up, the “deapth” of the entire
QuadTreeis 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
QuadTreefrom 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..
The Computational Beauty of Nature : Computer Explorations of Fractals, Chaos, Complex Systems, and Adaptation (MIT Press, 1998) ↩︎