Evolving Better Pathfinders

Algorithms like A* are well known solutions to the pathfinding problem, but there is a distinction between efficient and accurate pathfinding algorithms, and realistic pathfinding algorithms. The traditional definition of a “good” algorithm requires it be complete and quick. My definition of “realistic”, in contrast, is that an algorithm be reasonably good, reasonably fast, and reasonably fallable. That is, it should not be perfect, and when it does fail, it should fail in much the same way a human fails.

The following article is a supplement to an article I wrote for GamaSutra, and is intended as a more in depth explanation of how the Hampton pathfinding application used Genetic Programming to evolve a more realistic pathfinder. You may want to read the original article before continuing on. Read more