Evolving sparse direction maps for maze pathfinding
Vahl Scott Gordon, Z. Matley · 2004
A genetic algorithm is used to solve a class of maze pathfinding problems. In particular, we find a complete set of paths directing an agent from any position in the maze towards a single goal. To this end, we define a sparse direction map, wherein the maze is divided into sectors, each of which contains a direction indicator. Maps are evolved using a simple genetic algorithm. The fitness function samples the efficacy of the map from random starting points, this estimating the likelihood that agents find the goal. The framework was effective in evolving successful maps for three different mazes of varying size and complexity, resulting in interesting and lifelike agent behavior suitable for games, but not always the shortest paths.