Read on Twitter
Most #gamedev are familiar with A*, the most used pathfinding algorithm in games.
But did you know that there's a very common scenario in which A* DOES NOT find the shortest path? 
Let's see why A* won't work in "Portal", and how we can fix it!
But did you know that there's a very common scenario in which A* DOES NOT find the shortest path? Let's see why A* won't work in "Portal", and how we can fix it!
All pathfinding algorithms work by iteratively exploring nearby cells in the grid.
Breadth First Search explores them in the order in which they are discovered.
Dijkstra's Algorithm, instead, keeps exploring the SHORTEST PATH FIRST.
(gif by @redblobgames)
Breadth First Search explores them in the order in which they are discovered. Dijkstra's Algorithm, instead, keeps exploring the SHORTEST PATH FIRST.(gif by @redblobgames)
That is also why Dijkstra's algorithm is sometimes referred to as the SHORTEST PATH FIRST algorithm.
Ultimately, it is that property that ensures its OPTIMALITY (= it will always find the shortest path between any two points).
Ultimately, it is that property that ensures its OPTIMALITY (= it will always find the shortest path between any two points).
A* is a variant of Dijkstra's.
Instead of just taking into account the cost to reach an already explored node, it also tries to estimate how far that node is from the target destination.
โข ๐(๐): known cost to go from ๐ด to ๐
โข โ(๐): estimated cost to go from ๐ to ๐ต
Instead of just taking into account the cost to reach an already explored node, it also tries to estimate how far that node is from the target destination.
โข ๐(๐): known cost to go from ๐ด to ๐
โข โ(๐): estimated cost to go from ๐ to ๐ต
The function โ(๐) is known as a HEURISTIC: an "educated guess", basically.
There are countless functions you can use, each one leading to a potentially slightly different solution.
A* will ALWAYS find a solution.
But whether that solution is OPTIMAL or not, depends on โ(๐).
There are countless functions you can use, each one leading to a potentially slightly different solution.
A* will ALWAYS find a solution.
But whether that solution is OPTIMAL or not, depends on โ(๐).
For A* to be OPTIMAL (= guaranteed to find the SHORTEST PATH), โ(๐) must be ADMISSIBLE.
An admissible heuristic NEVER OVERESTIMATES the true, shortest distance from ๐ to ๐ต.
Below, you can see the actual shortest distance โ*(๐), compared to a possible heuristic โ(๐).
An admissible heuristic NEVER OVERESTIMATES the true, shortest distance from ๐ to ๐ต.
Below, you can see the actual shortest distance โ*(๐), compared to a possible heuristic โ(๐).
Finding an admissible heuristic is not an easy task.
But there is a scenario in which it becomes trivial.
If you are doing pathfinding in a 2D or 3D game, there is no shortest path than a straight line between two points!
The true shortest path must be longer or equal.
But there is a scenario in which it becomes trivial.
If you are doing pathfinding in a 2D or 3D game, there is no shortest path than a straight line between two points!
The true shortest path must be longer or equal.
And because of this, virtually all games which are using A* are also using the Euclidean distance as their โ(๐) of choice! 
But, as hinted, there is a very common scenario in which many games which violates the admissibility constraint... TELEPORTING!
But, as hinted, there is a very common scenario in which many games which violates the admissibility constraint... TELEPORTING!
Teleporting between ๐ด and ๐ต means the existence of a path SHORTER than a straight line between ๐ด and ๐ต.
A* won't find the shortest path in Portal!
But there is no need to panic!
As long as the heuristic is MOSTLY respected, A* is NEARLY OPTIMAL.
A* won't find the shortest path in Portal! But there is no need to panic!
As long as the heuristic is MOSTLY respected, A* is NEARLY OPTIMAL.
If optimality this is critical for you, you can solve this problem by running A* three times:
โข ๐โ = A* from ๐ด to ๐ต
โข ๐โ = A* from ๐ด to ๐ (closest teleport to ๐ด)
โข ๐โ = A* from ๐ (closest teleport to ๐ต) to ๐ต
If ๐โ+๐โ<๐โ: RUN TO THE TELEPORT!!!
โข ๐โ = A* from ๐ด to ๐ต
โข ๐โ = A* from ๐ด to ๐ (closest teleport to ๐ด)
โข ๐โ = A* from ๐ (closest teleport to ๐ต) to ๐ต
If ๐โ+๐โ<๐โ: RUN TO THE TELEPORT!!!
And for the @BostonDynamics fans reading this, here's a video of Professor Nosferatu bullying Shakey: the first robot for which A* was originally designed for!
Because AI researchers have been stopping robots from pushing boxes since 1972!
Because AI researchers have been stopping robots from pushing boxes since 1972!
๐๐ต๐ฎ๐ป๐ธ ๐๐ผ๐ ๐ณ๐ผ๐ฟ ๐ฐ๐ผ๐บ๐ถ๐ป๐ด ๐๐ผ ๐บ๐ ๐๐ฒ๐ฑ ๐๐ฎ๐น๐ธ If you enjoy content about gamedev, shader coding and artificial intelligence, feel free to retweet & follow me for more!
