I recently bumped into this, which is a demo page for a great pathfinding Javascript library. I noticed that none of the offered algorithms works the same way as the one I made for Caste Break, so I’m sharing my implementation here. I don’t know if this algorithm already exists and has a name, or if there’s an easier way to achieve the same thing. If so, please, drop a comment!

I won’t discuss code implementations here, just the abstract idea. Also, I should note that I’m not really well versed on the subject, so bear with me if I say something stupid.

The prerequisites

I started using A*, but, in Caste Break, as the enemies’ paths may be altered by the units, the process was getting heavy, because each enemy had it’s path recalculated every time a new unit was placed. So I set out to search for the best alternative for my use case:

• One target, multiples sources
• Unified path information (instead of storing them individually on each enemy)
• No diagonal movement allowed
• Always select the best path
• Least possible turns

I didn’t find any algorithm/system/whatever that fulfilled all these conditions. The last one was the most important for me.

My solution

To those of you familiar with the subject, here’s the TL;DR:

Perform a Breadth-First Search on the entire grid, starting from the point the enemies will head, which will have score 1 and priority 1. For each node (or tile), set its direction to indicate the neighbor with the highest priority. Set the current node’s score and priority to be the same as the indicated node. Add 1 to the score if the direction of the indicated node is the same as the current’s. Add the current node’s score to its priority.

If this isn’t clear to you (sorry, it’s hard to describe such things succinctly!), follow the step-by-step below.

The process

Let’s use this basic grid, or rather, a tile map. Each square is a tile, and the white tiles are the ones the enemies can walk. The star is where the enemies will try to reach, and the skull is where they’ll come from. I chose to start from the star, as I think it eases the way of thinking.

Each tile will have three important properties:

• Direction: indicates the next tile the enemy should walk
• Score: used to calculate the priority
• Priority: used to determine the directions of nearby tiles

First, we should set the score and the priority for the first tile, and mark it with a direction. In this case, let’s say the direction is ‘none’, as it will be the end of the path.

The following routine will then be applied until all the map is covered:

1. Select the tiles that surrounds the used ones. These are called the frontier.
2. For each tile in the frontier:
   1. Find the adjacent tiles that can be walked and have a direction.
   2. Set the direction to indicate the tile with the highest priority value.
   3. Copy the score and the priority from the indicated tile.
   4. If the direction is the same as of the indicated tile, add 1 to the score.
   5. Add the score value to the priority.
3. Repeat.

Let’s see how it goes. The tiles with a red outline are our frontier, currently with one tile. This tile will be the first we’ll use.

The bluish tiles are the ones we’ll consider, because they’re adjacent to the current one (painted in red). There’s only one that already contains a direction (the enemies’ target), so we’ll indicate it, defining the direction as ‘down’. Then, as the direction is different from the indicated tile (remember that we have set it as ‘none’), the score will be the same, which, in this case, is 1. To finalize, we take the priority from the indicated tile (also 1) and add the current tile’s score, receiving a priority of 2.

After that, we increase our frontier.

As a convention, we’ll always iterate through the frontier in clockwise order, starting from the top tile, as the next image shows.

Now, the direction is the same as the indicated tile (both are ‘down’), so the score is increased by 1. As the indicated tile has a priority of 2, this tile’s priority will be 4.

The second and last tile from the current frontier will indicate ‘left’ and keep the score from the indicated tile, resulting in a priority of 3. Time to advance the frontier.

As before, we start from the top and go clockwise.

Again, only one valid adjacent tile. As the direction is repeated, the score is increased, resulting in 3, and the priority is calculated after that, resulting in 7 (because the indicated tile’s priority is 4).

This time, there’s two adjacent tiles that contains direction information, so we’ll indicate the one with the highest priority: the one to the left. After that, the score and the priority is calculated as usual: copy score and priority and add the score to the priority.

Now that you got the hang of it, we’ll advance some steps.

You can already see (hopefully) how increasing the score only when the direction stays the same will prevent unnecessary turns. Let’s advance a bit more.

This is a case where I originally thought I would encounter some issues, but, fortunately, the routine handles that normally. The frontier is separated by an obstacle, reunites a few steps further and no unnecessary turns are generated.

We’re close to the end, so allow me fill the rest of the grid for you.

If you start a path in any tile of the map and follow the directions until the end, you will always make the minimum possible turns. The next image illustrates the final path that would be used by the enemies.

Final thoughts

With this algorithm, the enemies’ walking behavior got a lot more natural and predictable by the player, especially when blocking the path with units. I also could centralize the path information in one place, instead of each enemy having their own, saving memory and CPU usage. Hope you find it useful, or at least gives you an idea to build on top.

Although Caste Break doesn’t have levels with more than one target, I imagine it would work flawlessly. However, if this method wouldn’t be a good fit for you, or if you simply want to keep reading about pathfinding, I recommend this series of posts by Red Blob Games. It’s still unfinished, but it’s very well written and goes from the simple concepts all the way to the more advanced stuff.

In case you find something confusing, or even bad written, feel free to contact me.