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 entireQuadTree
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 tinyQuadTrees
. These will be hard to search through, create, etc..