Look at the following example:
How many iterations of regular A* would it take to find the path between the purple square and where the mouse cursor is? (the end of the corridor). About 20. 20 times the pathfinding code will loop through, adding to arrays and checking all the tiles around to see if they’re walkable. Not very efficient, especially with all those straight lines.
That’s what first got me thinking about this. The game I was working on was going to have lots of corridors and straight paths, so I started thinking: what if, instead of having to go along those straight corridors one by one, you could skip right over them in one iteration?
That was great and all, but surely finding the start and end of the corridor would take more loops, and possibly waste more time than it saved? Seeing as the terrain in this game was dynamic as well (the user could remove and add tiles), I couldn’t store a pre-set list of nodes at the end of the corridors and use them for path finding.
But what if I could dynamically generate them? That, and the previous idea of long corridors being represented as a start and the end node, are the principles behind this pathfinding algorithm.
Have a look again at the example:
How many iterations did I say this would take in regular A*? 20? With this method - 4. Yup. 4. That’s 20% of the original iterations.
How it works in context
The example above has 5 ‘nodes’. These are where the purple square is, all the three corners, and where the mouse is. The nodes are shown in red on this diagram:
The basic idea is just normal A*, but instead of using every tile, just the ‘nodes’ are used. Each node knows where the nodes around it are, and if there’s a node above, below, to the left or to the right of it. That node is then used as the next tile in the algorithm, missing out all the tiles in the long line between the nodes.
Of course, I’m sure this isn’t a new idea. However, if I added to the path:
New nodes are automatically added. This dynamic node creation is the real driving force behind this algorithm.
However, there are some limitations to how much A* can be improved upon in certain situations. Take for example, a map with a large open space. Every tile in that space becomes a node, referencing all the tiles directly around it as the nearest node, and the speed becomes exactly the same as normal A*. However, when there are lots of long corridors involved, the speed is increased greatly.
There are 2 parts to the implementation - the node creation, and the node-based pathfinding. The node-based path finding, as I’ve said, is basically just A*, but using the nodes instead of every tile, so I won’t go into it in great detail.
The node creation, on the other hand, is what I want to talk about. Node updating only takes place every time a tile is changed, not every frame, and when it does, there’s only a small amount of work actually done.
Take this example:
If I was to click on the square where the mouse was to create a walkable tile above that last node, the following would happen:
- The tile would start looking in all 4 directions for a node. As the tiles above, to the left and to the right of it are all not-walkable, it would only look downwards. Because of this, the tile knows it is the end of a vertical corridor.
- It would find the node directly below it. This node thinks it is the end of a vertical corridor, but with the introduction of the tile above it, it now stops being a node.
- The tile then looks at the old node’s connected nodes, and connects itself to the node below it, at the corner.
- The tile then becomes a node, at the end of the corridor.
The end result looks like this:
Of course, this is only one of few cases that could possibly happen. In general, this is what happens:
- New Tile (A) is made walkable.
- A looks upwards for a node.
- If A finds a node (B), it first checks if B is now part of a corridor instead of the end of one.
- If it is, A updates the node at the other end of B’s corridor (C), and tells C that A is now the end of the corridor.
- If B is a corner or a junction, A tells B that it is now there, and a new corridor has been created.
- Repeat steps 3-5 for the other 3 directions.
If that doesn’t make sense, I apologise.
Below is a link to an implementation of the technique. Click to make tiles walkable, left and right to scroll, and space to move the purple square to where the cursor is. You can also press Ctrl to spawn “enemies” that will follow you.
Also, if you mouse over a node, the node it’s connected to will point towards it, so you can see the nodes.