Introduction to Pathfinding Algorithms

“Pathfinding or pathing refers to the plotting, by a computer application, of the shortest route between two points. It is a more practical variant on solving mazes. This field of research is based heavily on Dijkstra’s algorithm for finding the shortest path on a weighted graph.” — From WIKIPEDIA

“… Pathfinding addresses the problem of finding a good path from the starting point to the goal―avoiding obstacles, avoiding enemies, and minimizing costs (fuel, time, distance, equipment, money, etc.). Movement addresses the problem of taking a path and moving along it. It’s possible to spend your efforts on only one of these. At one extreme, a sophisticated pathfinder coupled with a trivial movement algorithm …” — From Amit’s Blog

 

List of Pathfinding algorithms

  •  A*
  • Dijkstra’s Algorithm
  • Depth-First Search
  • Breadth-First Search
  • Q-Learning

 

Helpful Resources