Read on Twitter
As a #gamedev, you might be familiar with pathfinding algorithms such as A* or Dijkstra.
But not many know how they actually work...
Pathfinding algorithms might be complex, but they're not complicated.
So let's find out how they actually work!
But not many know how they actually work...
Pathfinding algorithms might be complex, but they're not complicated.
So let's find out how they actually work!
When a problem is too complex to be tackled, it is not uncommon to start with a simpler one.
Is point B REACHABLE from point A?
That's easy to test! Starting from A, let's "expand"/"explore" to its surrounding nodes.
And repeat, until B is found or no new cell is found.
Is point B REACHABLE from point A?That's easy to test! Starting from A, let's "expand"/"explore" to its surrounding nodes.
And repeat, until B is found or no new cell is found.
That is known as the FLOOD FILL algorithm.
And once implemented, it can be easily extended to answer a more difficult question.
What is the DISTANCE between A and B?
All you need is to count how many iterations you have done before reaching B!
And once implemented, it can be easily extended to answer a more difficult question.
What is the DISTANCE between A and B?All you need is to count how many iterations you have done before reaching B!
We're almost there!
What is the PATH between A and B?
Instead of just counting how many steps we do, we can label each cell to remember where we came from!
This creates a MINIMUM SPANNING TREE!
Once B is reached, we follow the arrows in reverse and that is our path!
What is the PATH between A and B?Instead of just counting how many steps we do, we can label each cell to remember where we came from!
This creates a MINIMUM SPANNING TREE!
Once B is reached, we follow the arrows in reverse and that is our path!
And that's it, really! 
Virtually all pathfinding algorithms found in games work exactly like this!
In fact:
- Depth-First Search
- Breadth-First Search
- Dijkstra Algorithm
- A*
...are all "variants" of the same pathfinding algorithm: FRONTIER SEARCH!
Virtually all pathfinding algorithms found in games work exactly like this!
In fact:
- Depth-First Search
- Breadth-First Search
- Dijkstra Algorithm
- A*
...are all "variants" of the same pathfinding algorithm: FRONTIER SEARCH!
Now, there's one small problem that we might need to address...
The order in which we explore the nodes is VERY important, as it can create a different SPANNING TREE!
The order in which we explore the nodes is VERY important, as it can create a different SPANNING TREE!
Ultimately, this could lead to very different paths...
Regardless of the order in which you explore/expands your cells, you will EVENTUALLY find a path. But this does not guarantee it is the shortest one!
Regardless of the order in which you explore/expands your cells, you will EVENTUALLY find a path. But this does not guarantee it is the shortest one!
If you want to make sure you can ALWAYS get the SHORTEST path between two points, you need the following condition:
Before exploring a cell at distance N, make sure you have explored all other cells at distance N-1!
And this makes the pathfinding algorithm OPTIMAL!
Before exploring a cell at distance N, make sure you have explored all other cells at distance N-1!
And this makes the pathfinding algorithm OPTIMAL!
๐๐ต๐ฎ๐ป๐ธ ๐๐ผ๐ ๐ณ๐ผ๐ฟ ๐ฐ๐ผ๐บ๐ถ๐ป๐ด ๐๐ผ ๐บ๐ ๐๐ฒ๐ฑ ๐๐ฎ๐น๐ธ If you enjoy content about gamedev, shader coding and artificial intelligence, feel free to retweet & follow me for more!
