Why is Path Finding Important in Video Games?
- NPCs - Make up the crux of many video games.
- AI is utilized in practically every game
- Pathfinding requires CPU usage
- Minimaps/World Maps within games (Open world)
- Very common algorithms used in most games is the A* algorithm or Dijkstra's algorithm which we’ve looked at together as a class.
Considerations with Pathfinding in Video Games
- Focus on research is based on the AI Model
- Pathfinding for AI characters
- Several algorithms looked at were A* (the most common technique for pathfinding)
-
Additional others like Dijkstra’s Algorithm, Genetic Algorithm, Ant Colony Optimization
- Static and Dynamic Pathfinding (Metaheuristic vs Heuristic)
- Concluded the pathfinding algorithms in terms of time/performance
- Did not mention specific methods
- Did not list games examined either
Comparison of Pathing Algorithms
Heuristic algorithms
- Aim to find a good solution to a specific problem in a reasonable amount of time with no guarantee of efficiency
- Satisfactory solution where an optimal solution is impractical
Meta-Heuristic algorithms
- High-level strategies that combine lower-level techniques for exploration and exploitation of search space
- Based on natural phenomenon
- A* and Dijkstra's used as a solution to find the shortest path
- Ant colony optimization (ACO) and genetic algorithm used to find minimum cost path in a graph
- A* - RPGs, racing, turn-based strategy
- Dijkstra's - network routing, public transportation, logistics
- Genetic - biomimetic, automotive design, engineering design, robotics
- Ants - robotics, submarine
Sources: iopscience.iop.org
