5-6-2018

While doing some research on enemy path-finding, I came across some obvious solutions, such as A-Star among other types of algorithms. Now, I’m not trying to say anything one way or another about A-Star, however, the algorithm does not seem to be a rather easy one to write and furthermore, if I apply it to multiple enemies, I’m almost certain it will require a pass for each enemy, each time the player moves. That seems like a lot of processing power needed to plot a path to the player. Too much work for the Z80 processor when you are also updating sprites and all the other routines needed for the game.

Finally, giving up on A-Star, I came across this video.

https://www.youtube.com/watch?v=jYHcY9YDPBM

What we are watching is the algorithm for the Wavefront path-finding technique. Once the algorithm is run, we have a complete path from point A to point B showing across the entire grid. Therefore with this algorithm, we can calculate it once and have each enemy have a path back to the player, no matter how many enemies are involved.

Pretty Awesome.

Now how do we go about doing this?

It actually took me quite some time to google and find an answer that seemed appropriate for me to understand.

http://www.robotc.net/blog/2011/08/08/robotc-advanced-training/

Is where I found my answer, it’s called the Wavefront Algorithm, also known as the Grassfire Algorithm.

Apparently, this is a popular algorithm for use in Robotics and it’s pretty interesting.

The author of this particular version of the Wavefront is Timothy Friez. He is the Chief Operating Officer at Robomatter Inc. Visit their website at http://www.robomatter.com/.

I contacted Mr. Friez and asked him if I could use his code so I could modify it to use it on my game and try to speed up the code. He agreed and now my challenge is to see what I can do to speed up the code.

Now, just for clarification, Timothy Friez did not invent the Wavefront/Grassfire algorithm, he just wrote a version that is not only fast but easy to understand. It’s his version, that I am going to use as a base and modify it for speed and modify it to adapt to Z88dk. The end result, that I come up with, the functionality works the same but looks quite a bit different. Also, it would seem that the Wavefront/Grassfire Algorithm is closely related to the flood fill algorithm in its implementation, however, the results are pure Dijkstra’s algorithm.

You may ask then, what is Dijkstra’s algorithm?

Dijkstra’s algorithm, invented in the 1950’s is what the A-Star algorithm is based on. I call it the mother of optimal path-finding algorithms. It computes the number of steps required to move from point A to B including barriers. It does this by moving outwards from the target counting each step until it the graph is completed. Just for reference, A-Star came out afterward and is an optimization enhancement to Dijkstra’s algorithm.

There are a number of excellent articles written on the Dijkstra’s Algorithm, including the Wikipedia entry ( https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm ). Almost all of them show you how to use priority queues to solve the algorithm. However, priority queues require a different library and that add additional memory to our program, so I’ve decided to stay away from using that library.

On reading most of these articles, you will see quite a few abstract concepts that are quite difficult to understand unless you are already familiar with graph theory and techniques.

It’s sometimes easier to illustrate the problem and solution, that to try to write it.

Given the following maze (where 255 are barriers and the 1 is the target).

What is the shortest path to the target?

The solution to a person, is rather straightforward, quick a quick look at the simple maze a person can solve this almost instantaneously. A computer has a bit more of a difficult time solving this. For a computer to solve this, we must move from the target back to the destination and count the number of steps taken. We then take the pathway with the fewest steps.

Here’s the formulation of the Wavefront/Grassfire algorithm.

Here is our pathway.

At any point along the maze, pick any spot, and follow the lowest number downwards and you will find the pathway.

However, as I pointed out before, most all path-finding algorithms use priority queues (additional libraries) to solve the problem. What is needed is a technique to resolve this without using additional libraries.

Here is where I introduce the Wavefront/Grassfire algorithm.

In the Wavefront/Grassfire algorithm, we scan across the array, finding the current wave (number) and all the neighbors will get that same number + 1.

To illustrate this, we will show a simple maze.

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

0 | – | – | – | – | – | – | 0 |

1 | – | – | 255 | – | – | – | 1 |

2 | – | – | 255 | 1 | – | – | 2 |

3 | – | – | 255 | – | – | – | 3 |

4 | – | – | – | – | – | – | 4 |

5 | – | – | – | – | – | – | 5 |

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

Here the 255 represent our barriers. 1 represents our target.

Let’s run a Wavefront.

Our current wave is 1.

Step 1, find the neighbors to 1

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

0 | – | – | – | – | – | – | 0 |

1 | – | – | 255 | ? | – | – | 1 |

2 | – | – | 255 | 1 | ? | – | 2 |

3 | – | – | 255 | ? | – | – | 3 |

4 | – | – | – | – | – | – | 4 |

5 | – | – | – | – | – | – | 5 |

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

Take those neighbors, increment our wave and assign them to our neighbors.

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

0 | – | – | – | – | – | – | 0 |

1 | – | – | 255 | 2 | – | – | 1 |

2 | – | – | 255 | 1 | 2 | – | 2 |

3 | – | – | 255 | 2 | – | – | 3 |

4 | – | – | – | – | – | – | 4 |

5 | – | – | – | – | – | – | 5 |

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

Our current wave is now 2.

Step 2, find the neighbors to 2

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

0 | – | – | – | ? | – | – | 0 |

1 | – | – | 255 | 2 | ? | – | 1 |

2 | – | – | 255 | 1 | 2 | ? | 2 |

3 | – | – | 255 | 2 | ? | – | 3 |

4 | – | – | – | ? | – | – | 4 |

5 | – | – | – | – | – | – | 5 |

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

Take those neighbors, increment our wave and assign them to our neighbors.

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

0 | – | – | – | 3 | – | – | 0 |

1 | – | – | 255 | 2 | 3 | – | 1 |

2 | – | – | 255 | 1 | 2 | 3 | 2 |

3 | – | – | 255 | 2 | 3 | – | 3 |

4 | – | – | – | 3 | – | – | 4 |

5 | – | – | – | – | – | – | 5 |

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

Our current wave is 3.

Step 3, find the neighbors to 3

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

0 | – | – | ? | 3 | ? | – | 0 |

1 | – | – | 255 | 2 | 3 | ? | 1 |

2 | – | – | 255 | 1 | 2 | 3 | 2 |

3 | – | – | 255 | 2 | 3 | ? | 3 |

4 | – | – | ? | 3 | ? | – | 4 |

5 | – | – | – | ? | – | – | 5 |

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

Take those neighbors, increment our wave and assign them to our neighbors.

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

0 | – | – | 4 | 3 | 4 | – | 0 |

1 | – | – | 255 | 2 | 3 | 4 | 1 |

2 | – | – | 255 | 1 | 2 | 3 | 2 |

3 | – | – | 255 | 2 | 3 | 4 | 3 |

4 | – | – | 4 | 3 | 4 | – | 4 |

5 | – | – | – | 4 | – | – | 5 |

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

Our current wave is 4.

Step 4, find the neighbors to 4

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

0 | – | ? | 4 | 3 | 4 | ? | 0 |

1 | – | – | 255 | 2 | 3 | 4 | 1 |

2 | – | – | 255 | 1 | 2 | 3 | 2 |

3 | – | – | 255 | 2 | 3 | 4 | 3 |

4 | – | ? | 4 | 3 | 4 | ? | 4 |

5 | – | – | ? | 4 | ? | – | 5 |

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

Take those neighbors, increment our wave and assign them to our neighbors.

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

0 | – | 5 | 4 | 3 | 4 | 5 | 0 |

1 | – | – | 255 | 2 | 3 | 4 | 1 |

2 | – | – | 255 | 1 | 2 | 3 | 2 |

3 | – | – | 255 | 2 | 3 | 4 | 3 |

4 | – | 5 | 4 | 3 | 4 | 5 | 4 |

5 | – | – | 5 | 4 | 5 | – | 5 |

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

Our current wave is 5.

Step 5, find the neighbors to 5

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

0 | ? | 5 | 4 | 3 | 4 | 5 | 0 |

1 | – | ? | 255 | 2 | 3 | 4 | 1 |

2 | – | – | 255 | 1 | 2 | 3 | 2 |

3 | – | ? | 255 | 2 | 3 | 4 | 3 |

4 | ? | 5 | 4 | 3 | 4 | 5 | 4 |

5 | – | ? | 5 | 4 | 5 | ? | 5 |

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

Take those neighbors, increment our wave and assign them to our neighbors.

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

0 | 6 | 5 | 4 | 3 | 4 | 5 | 0 |

1 | – | 6 | 255 | 2 | 3 | 4 | 1 |

2 | – | – | 255 | 1 | 2 | 3 | 2 |

3 | – | 6 | 255 | 2 | 3 | 4 | 3 |

4 | 6 | 5 | 4 | 3 | 4 | 5 | 4 |

5 | – | ? | 5 | 4 | 5 | 6 | 5 |

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

Our current wave is 6.

Step 6, find the neighbors to 6

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

0 | 6 | 5 | 4 | 3 | 4 | 5 | 0 |

1 | ? | 6 | 255 | 2 | 3 | 4 | 1 |

2 | – | ? | 255 | 1 | 2 | 3 | 2 |

3 | ? | 6 | 255 | 2 | 3 | 4 | 3 |

4 | 6 | 5 | 4 | 3 | 4 | 5 | 4 |

5 | ? | 6 | 5 | 4 | 5 | 6 | 5 |

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

Take those neighbors, increment our wave and assign them to our neighbors.

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

0 | 6 | 5 | 4 | 3 | 4 | 5 | 0 |

1 | 7 | 6 | 255 | 2 | 3 | 4 | 1 |

2 | – | 7 | 255 | 1 | 2 | 3 | 2 |

3 | 7 | 6 | 255 | 2 | 3 | 4 | 3 |

4 | 6 | 5 | 4 | 3 | 4 | 5 | 4 |

5 | 7 | 6 | 5 | 4 | 5 | 6 | 5 |

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

Our current wave is 7.

Step 7, find the neighbors to 7

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

0 | 6 | 5 | 4 | 3 | 4 | 5 | 0 |

1 | 7 | 6 | 255 | 2 | 3 | 4 | 1 |

2 | ? | 7 | 255 | 1 | 2 | 3 | 2 |

3 | 7 | 6 | 255 | 2 | 3 | 4 | 3 |

4 | 6 | 5 | 4 | 3 | 4 | 5 | 4 |

5 | 7 | 6 | 5 | 4 | 5 | 6 | 5 |

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

Take those neighbors, increment our wave and assign them to our neighbors.

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

0 | 6 | 5 | 4 | 3 | 4 | 5 | 0 |

1 | 7 | 6 | 255 | 2 | 3 | 4 | 1 |

2 | 8 | 7 | 255 | 1 | 2 | 3 | 2 |

3 | 7 | 6 | 255 | 2 | 3 | 4 | 3 |

4 | 6 | 5 | 4 | 3 | 4 | 5 | 4 |

5 | 7 | 6 | 5 | 4 | 5 | 6 | 5 |

– | 0 | 1 | 2 | 3 | 4 | 5 | – |

And now our wavefront is built. Now from any point on the map, we can move downwards in the numbers and find our target (1)

So, without any further introduction, let’s delve into his code.

```
//FUNCTION wavefront algorithm to find most efficient path to goal
void WavefrontSearch()
{
int goal_x, goal_y;
bool foundWave = true;
int currentWave = 2; //Looking for goal first
while(foundWave == true)
{
foundWave = false;
for(int y=0; y < y_size; y++)
{
for(int x=0; x < x_size; x++) { if(map[x][y] == currentWave) { foundWave = true; goal_x = x; goal_y = y; if(goal_x > 0) //This code checks the array bounds heading WEST
if(map[goal_x-1][goal_y] == 0) //This code checks the WEST direction
map[goal_x-1][goal_y] = currentWave + 1;
if(goal_x < (x_size - 1)) //This code checks the array bounds heading EAST if(map[goal_x+1][goal_y] == 0)//This code checks the EAST direction map[goal_x+1][goal_y] = currentWave + 1; if(goal_y > 0)//This code checks the array bounds heading SOUTH
if(map[goal_x][goal_y-1] == 0) //This code checks the SOUTH direction
map[goal_x][goal_y-1] = currentWave + 1;
if(goal_y < (y_size - 1))//This code checks the array bounds heading NORTH
if(map[goal_x][goal_y+1] == 0) //This code checks the NORTH direction
map[goal_x][goal_y+1] = currentWave + 1;
}
}
}
currentWave++;
PrintWavefrontMap();
wait1Msec(500);
}
}
```

Before we start any programming, let’s examine what we are doing with this code.

First, we are providing a map to the algorithm. It comes in the form of a 2D array. We also need to provide a target point. Finally, we need to supply the size of the array to the algorithm so we can properly address the array.

Our localized variables are goal_x, goal_y, foundWave and curretWave.

We set the foundWave to true to enter the While loop and we set the currentWave to 2 to search the array.

Next, we enter the foundWave loop from the true setting set just prior and we immediately set the foundwave to false, so now we have created a loop until we find out currentWave number.

Next, we will search through all elements of the array in both X and Y and keep searching until we find our currentWave number.

Once we find our currentWave number, we will set the foundWave to true.

If the neighbor is 0 and within the bounds of the array, we will mark the neighbors with the currentWave number + 1.

Now, that our foundWave is set to true, we can increment our currentWave by 1.

Finally, we restart and restart.

Another description of the algorithm is found here.

http://www.robotc.net/forums/viewtopic.php?f=1&t=5043

Here’s a block diagram of how the code functions.

Coming up next, rewriting the grassfire/Wavefront algorithm

The tables generated in this document were generated by: