Thread by @AlanZucconi

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!

🧵

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)

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).

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 𝐵

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 ℎ(𝑁).

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 ℎ(𝑁).

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.

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! ✨

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.

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!!! ✨

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! 🧛‍♂️

✨ 𝘁𝗵𝗮𝗻𝗸 𝘆𝗼𝘂 𝗳𝗼𝗿 𝗰𝗼𝗺𝗶𝗻𝗴 𝘁𝗼 𝗺𝘆 𝘁𝗲𝗱 𝘁𝗮𝗹𝗸 ✨

If you enjoy content about gamedev, shader coding and artificial intelligence, feel free to retweet & follow me for more! 😎