The problem behind pathfinding is as old as the Labyrinth at Knossos: how do I get from point A to point B using the shortest route and avoiding all obstacles in-between?
Many algorithms have been developed to solve pathfinding problems, including those related to the A* algorithm, which was first introduced in computer science during the 1960s (section 2).
Pathfinding routines are typical components of many video games, with Non-Player Characters (NPCs) having the task of finding optimal paths on the game maps, which can constantly change. For example, passageways, gates, or doors can change their statuses during gameplay.
There are quite a lot of problems when it comes to pathfinding, and unluckily for us, there isn't a one-solution-fits-all approach. This is because each problem will have its own solution, depending on the type of problem it is. Not only this...