With this post we reach the last post dedicated to enemy AI – probably. This time I want to focus on one specific character behaviour: the search. When the player alerts the enemies but these lose track of where the player is, they have to search the area and try to find him. This might sound simple but it is not. Where should the enemy search? What’s route will he follow? How do we detect obstacles?
Defining the search area
This is clearly the easiest part. As soon as the search behaviour is triggered in the FSM we look in which tile is the enemy located. With enemy coordinates xy we do a simple calculation and we find the exact tile. E.g. with 64×64 tiles we would do tile_x = floor(enemy_x / 64) * 64. Same for the y component.
Once we have the tile we decide a radius, e.g. 3 tiles around, and we get the position of those tiles. Knowing the tile size it’s pretty easy.
Cleaning the area
The process done in the previous step has given us an area to search. The problem is that we don’t know how to move around and even worse than that, the area is not clean. By that I mean that we don’t know which of those tiles are walkable and which aren’t. There might be walls in between but we don’t know.
To the rescue it comes the most unexpected (to me) but at the same time logical solution. The algorithm that is used in software like Photoshop or Paint to fill an are with a color, the flood fill algorithm. If you think about it it actually makes a lot of sense. You need to know which tiles of the selected area are available to you, meaning that they are connected to the tile the enemy is on and that they are empty of obstacles. That’s exactly what happens when you use the bucket fill tool in paint software. You click on a white pixel with the bucket and the blue color selected. Any pixel connected to that one will be changed to blue as long as they are white. The exact same thing we need.
We run this simple algorithm through the array of tiles we had from the previous step and we will have a clean area that must be search by the enemy.
Finding a path
The last thing left to do is to find a path to move around those selection of tiles. Because of how the flood fill algorithm works, the result array of tiles has a pretty well defined flow. The problem is that if we move from tile to tile it looks kind of silly and weird.
The solution I came for is to start by the first tile and loop over the following tiles checking the distance. If the distance is higher than the one to the previous tile, we keep going. If it’s a smaller distance we’ve found one of our key points. We repeat this process until we reach the end of array.
By doing this process we guarantee that we will reach all the extremes of the selected area. Through testing this has proven to be more than reasonable and in no case there are tiles that are unexplored. Better than that, the movement through the search areas feels reasonable and logical, giving the feel to the player that the enemies area looking around for him.
I’ve tried a bunch of other things before I reached this solution and nothing worked as I wanted. I could have never imagined that an algorithm that is on first sight so disconnected from game development could work, but it does. I guess there’s a lesson to be learned from here.
Anyway, I thought it was an interesting thing to talk about and a good way to end this section of the devlog dedicated to enemy AI. Let’s see how the game evolves in the following weeks and what else can we talk about. I want to talk at some point about the more artistic/visual part of the game. We’ll see.