While brainstorming and looking how the numbers built up for the Wavefront/Grassfire technique and building the windows program time and time again, I started to observe an interesting pattern. It took me a little while to figure out the pattern of the numbers but eventually started to remind me of an older image processing routine that I had built a few years ago – The Min Filter or minimum filer.
The Min filter was an image processing routine I built while playing around with how to manipulate image arrays. Basically, a kernel runs through an image and finds the lowest number pixel in a group of pixels and assigns all pixels to that same lowest number.
Now, the two would not be exactly alike, but it did start to run a new idea through my head. The AI would need to be constantly updated, but that is OK since the player is always moving. So, the concept of endless iterations seemed like a good concept.
The idea is basically this, we look at the 4 neighbors to a central pixel, find the lowest number and then assign the central pixel to the lowest number and add 1 to that. The shape of the kernel of known as a hollow cross kernel. We will apply this same idea to tiles rather than pixels and you will get the general operation of the function.
So, it can be easier to show in actual operation, so without further ado, here are some images of the function.
With our array, we need to mark it with some numbers first. The walls (in red) get populated with a 255. The player (blue) gets marked with a 1 and the open pathways are marked with a 128.
Our kernel starts off like this. The yellow is the central tile, while the green is the neighbors to the central tile.
We take the minimum of these which is 128 and add 1 to the number and place it in the center. This gets us to this.
Well, this seems to get us in a bad place (at least for now), but not to worry, it will work itself out. Our next tile will end up like this.
Here we see that we are now looking to modify the yellow tile and the green neighbors are 129, 128 and 128, the minimum number of the group is 128, so we add 1 and write it to the central tile.
Our next kernel position has neighbors of 128, 129 and 255(wall). The minimum of the group is 128, so we write it as 128 + 1 = 129. Same as the prior tiles.
Which gets us this.
So, let’s fast forward a little bit.
Up until now, all of our tiles will end up with the exact same number, which is 129. Now our kernel has encountered a different number.
Our central tile is 128, but our neighbors are not 255, 129, 128 and 1. Our minimum number is 1, so we assign our central tile to 1 + minimum neighbor, which is 2.
And write that to the array.
It’s where the tiles start to turn in our direction. Now let’s scan the next tile
Our neighbors are 128, 128, 129 and 2. Our minimum number is 2, so we assign our central tile to 1 + minimum neighbor, which is 3.
So, I am sure you see the pattern we are working with now, so let’s fast forward, just a little.
Here we are going to have to make a little allocation to this tile, the tile marked 1 is a special position, so we cannot mark it with the smallest of the 4 neighbors + 1, so we are going to have to account for the 1 in our calculations. So we will code in to skip that number if we encounter it.
Let’s fast forward again to the end of the tileset.
By the end of our first pass, our array now looks like this, a partial Wavefront / Grassfire. This is for 1 iteration. During the game, we have endless iterations, but as you can see we have most of the closest tiles already figured out, which means the enemies that are already in those positions know exactly how to reach you, while the further enemies do know yet know how to reach you.
Let’s perform another iteration.
Here’s our second pass. The minimum numbers of the undecided tiles get increased to 130 because the neighbors in those tiles would be 129 (from prior scan) which increase to 130, however, the top tiles are now populated and the bottom tile are working on the edge of the barrier. We have over half of the tiles populated with a number that will guide the enemy toward you.
Let’s perform another iteration.
Here’s the result of our third pass, the barrier does slow the population of the array, as we only recorded 3 tiles.
Let’s start another iteration and point out another area of interest about halfway.
Somewhere around halfway, we encounter this scenario, don’t worry, just pointing out a good example of the minimum operation. Our central tile is 131 (yellow), the neighbors are 7,5,132 and 255. Our minimum number is 5, so our central tile is assigned the minimum number + 1, which is 6. Again, just demonstrating our kernel. Let’s finish our iteration.
Here’s the result of our 4th pass. All but a few tiles are undecided. That will clear up on our next pass.
That our basic idea, find the minimum number of our kernel, add 1 and place that new number in the central area.
Now for our larger tileset, this will take longer to populate, so we are going to have to break it in parts.
Let’s show our larger tileset, the one we use for our game example
We are going to scan 1 row at a time (in orange) during each enemy call and compare the central tile of each tile with its 4 neighbors. Our first pass will look like this
Notice, this pass, tiles 12-14(x) and row 2 are changed.
Now at this time, all 4 enemies have been called. So the rest of the game loop is played out. When the game loop encounters the enemy calls again, we will then scan the next 4 rows. I’m going to fast forward to the end of the enemy loop.
Here’s the end of our second enemy loop, the most the player can travel at this rate is 2 pixels. If the enemy is in the range of the yellow, you have already been targeted.
Let’s finish out our next enemy call, which will be the last 2 rows and the first two rows (as the start of the next iteration).
At this point, we have gone through three calls of the enemy loop, each call of the enemy, the player can move 1 pixel at a time. If the enemy is in the yellow zone, at this time, you are already targeted. It will take 16 pixels for you to get from 1 tile to the next. Let’s see what we can scan in the time for you to reach the next tile.
Fourth enemy call.
Fifth enemy call.
Sixth enemy call.
Seventh enemy call.
Eighth enemy enemy call.
We are now about halfway to another tile for the player. If the enemy is in the yellow zone, you are already targeted. Otherwise, the enemy does not know where you are. Since we are now trying to scan around obstacles, the grassfire will slow down a bit.
Ninth enemy call.
Tenth enemy call.
Eleventh enemy call.
Twelfth enemy call.
Thirteenth enemy call.
Fourteenth enemy call.
Fifteenth enemy call.
Sixteenth enemy call.
At this point, you would think the player has now moved to a different tile. It will take 38 enemy calls (at 10 tiles at a time) for the entire screen to be mapped out. There will also be errors along the way (they do self-correct though). However, there 4 enemy calls and 1 player call in the game loop, so the enemy is called more often. 4 enemies move 1 pixel before the player can move 1 pixel, which means there are fewer iterations than are realized. This means the 38 calls, is really 38 divided 4 which is 9 ½ pixels pixels in reality.
You may think, ah-ha, the wavefront is not fast enough, my player might be able to get away. However, there are a number of factors that will disallow that. The first factor is that the screen is constantly scanning for the next tile and it really does build up faster than one thinks. The second factor, you will find that the scan closer to the player updates much quicker than the remainder of the tiles meaning that the scan near the player updates every 2 ½ scans, so if the enemy is 2 tiles away, it has you marked already. Next, player reflexes, sure if you move continuously in one direction, you can get away on an empty screen, but there are obstacles in the way, so the player has to be able to navigate them without stopping a bit, what will actually happen over time is that the enemy will start to catch up 1 pixel at a time to the player. Finally, is that the numbers do not really change all that much. Here’s an observation.
Here’s a complete wavefront with your player highlighted in blue.
Now, let’s move the player up 1 tile.
The numbers do change, but again, not by all that much, meaning that the enemy has an estimate on how to get to the player. Now, let’s move the player the 2 additional tiles that it can make way for the entire scan to take place.
Again, you will notice that the numbers don’t change all that much, in fact, the numbers that change the most are the only closer to the target (the player), and those numbers are the ones that update the most often. Meaning that on further tiles, the enemy has an estimate on how to get to you and the enemies that are closer, have your player targeted. Best of luck trying to escape when you are now in the bullseye.