Using a Genetic Algorithm to Explore A*-like Pathfinding Algorithms
- 1 January 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 23254270,p. 72-79
Abstract
We use a genetic algorithm to explore the space of pathfinding algorithms in Lagoon, a 3D naval real-time strategy game and training simulation. To aid in training, Lagoon tries to provide a rich environment with many agents (boats) that maneuver realistically. A*, the traditional pathfinding algorithm in games is computationally expensive when run for many agents and A* paths quickly lose validity as agents move. Although there is a large literature targeted at making A* implementations faster, we want believability and optimal paths may not be believable. In this paper we use a genetic algorithm to search the space of network search algorithms like A* to find new pathfinding algorithms that are near-optimal, fast, and believable. Our results indicate that the genetic algorithm can explore this space well and that novel pathfinding algorithms (found by our genetic algorithm) quickly find near-optimal, more-believable paths in LagoonKeywords
This publication has 4 references indexed in Scilit:
- Finding Attack Strategies for Predator Swarms Using Genetic Algorithms2005
- New Methods for Competitive CoevolutionEvolutionary Computation, 1997
- Depth-first iterative-deepeningArtificial Intelligence, 1985
- A Formal Basis for the Heuristic Determination of Minimum Cost PathsIEEE Transactions on Systems Science and Cybernetics, 1968