Building Logic for AI in Games – Part 2: Vision

In my previous article, Building Logic for AI in Games – Part 1: Simple Movement, I discussed how I made enemies follow certain paths in my HTML5 game, Infiltration. I then had to figure out how to make enemies see the player.

In order to check if an enemy sees the player, I first perform a simple distance check. Indeed, if an enemy is too far from the player, I consider that he shouldn’t be able to see him.

Then, I perform the angle check. I have two angles: the direction towards which the enemy looks, and the angle from the enemy directly to the player. Considering that the enemy has a 90° field of view, I have to check if the difference between these two angles is below or above 45°.

Calculating the difference between two angles is more difficult than it sounds. It is more difficult than simply calculating the difference between two numbers because of the sign. This article explains it in further detail. Now that I am sure that the player is within sight of the enemy, and in its field of view, I have to check if there are no walls between them. This is the trickiest part.

The first approach would be to loop over all the obstacles in the level and test for each of them if the trajectory between the enemy and the player goes through it. If we have N obstacles in the level, we would have to calculate 2N line intersections (complexity: O(n)). Then, if we have M enemies in the level, that would bring us to 2 * N * M line intersections to calculate in the worst case. And that is for each frame.

The worst case would never happen of course. It would require all enemies to be within sight range, facing the player, and with no obstacles between the two. I used that method for Haunted Gardens, because I did not need to check the zombies’ vision at every frame. And Infiltration had to work on mobile, therefore I tried to limit the number of checks for each frame.

Instead, I came up with a second approach. The previous one would have been perfect, completely reliable, and it was working, but I wanted performance to be the best possible, and I didn’t need an exact solution. This approach works great as long as the player does not notice the trick.

The idea is based on the fact that the levels are usually small, with a rectangle shape, and could be drawn on a grid. Given this hypothesis, I can create a matrix containing the obstacles, instead of a list that I would have to loop over every time.

Here is what the matrix would look like on a simple level: 0 represents an empty space (no obstacles), and 1 represents an obstacle.

The good thing about having such a matrix is that I now have direct access to one location on the level, and I can know instantly whether there is an obstacle at this exact location.

Now, I can use this matrix to check if the enemy’s vision is stopped by an obstacle.

  

The idea is to browse the line going from the enemy to the player one time on the X axis, and one time on the Y axis.

Since the level is a 20-pixel grid, all I need is to check every 20 pixels if there is an obstacle. For example, if I’m looping over the X axis, I will calculate the corresponding Y coordinate for each iteration, and then check on the grid if the position is available. I then do the same thing on the Y axis.

The reason I do it twice (once for the X axis, once for the Y axis) is because of the nearly horizontal, and nearly vertical cases.

As you can see on the example above, if I looped only over the Y axis, I would check only one position on the grid, while I obviously need to perform three checks to be sure there is no obstacle. Therefore looping over the X axis would make more sense. The same applies for nearly vertical lines. Therefore, to be sure I do not miss an obstacle, I always loop over both axes.

Although it sounds more sketchy than the first approach, this method does have an advantage: the number of checks I will perform do not depend on the complexity of the level, but only on the angle and distance between the enemy and the player. And given the levels’ architectures, this number should stay pretty low.

For instance, if the distance is 200 pixels, and the trajectory is horizontal or vertical (which is the best case), I will only have to perform 10 checks (on the X or Y axis). In the worst case, which is a 45° angle, the distance projected on both axes is only 141 pixels, so I only have to perform 7 checks on both axes, and 14 checks in total.

Now that I know when an enemy sees the player, I can start thinking about how he should behave when that happens…