Pathfinding Algorithms in Games

Abstract

This article describes the A*, Dijkstra's, and genetic pathfinding algorithms used in games, providing a comparison and information about them. While these are not the only algorithms used in game pathfinding, they are currently the most commonly used ones. As games increasingly demand the presentation of more data (higher-quality graphics, complex environmental communication systems, better sound effects, advanced character movement sets, smarter AI, etc.) in shorter time frames, algorithms must be developed to become more optimal. In the near future, they will be replaced by improved versions or entirely new algorithms

Keywords

ant colony optimization, AI, A* algorithm, breadth-first search, Dijkstra's algorithm, game character, graph, genetic algorithm, level, pathfinding