Building an AI for Navigating Obstacles

While creating Brimstone as a sequel to Entombed, our development team decided to make some modifications to the AI that makes the game work. Specifically, we wanted to improve the target-tracking capabilities of the game – essentially the ability of the character to navigate the maze in search of a target that the user has clicked on. This allows our users on touchscreen devices to easily tell the character where they want him to go, rather than being forced to micromanage his every move (which can be quite cumbersome on a small screen). This target-tracking system is showcased in the following video:

We first designed this system for Entombed, but encountered some basic flaws with its implementation: first, the character could not plan very far ahead and was easily confused by obstacles in his path; second, the character tended to get stuck in “oscillations” in which he would pace back and forth between two squares. Needless to say, we hoped to jettison both of these traits when creating the AI for the new game.

For the purpose of these algorithms, we assume that your game is divided (as ours were) into squares on a grid, some of which had obstacles and some of which did not. Squares off the grid are here considered to be obstacles for the sake of brevity.

How the Entombed AI Worked

To make the Entombed AI follow targets, it would simply look at the four squares immediately adjacent to the player (above, below, to the left, and to the right) and for each would find a “proxy distance” from that square to the target. Whichever square had the minimum proxy distance would be the next square the character would move to. Of course, once the character actually reaches the target its AI needs to be turned off so it will stop pacing around the target. There are other ways to prevent this behavior, but this is the easiest way to accomplish it.

To make the character avoid obstacles, we chose the following as our proxy distance between square A and a target:

  1. If square A is not an obstacle, the proxy distance is simply the distance from A to the target.
  2. If square A is an obstacle, the proxy distance is some arbitrarily large number (larger, though, than any actual distance in the maze – for our case we chose 100 tile widths, which is much larger than the 59 tile width diagonal of our 42×42 tile maze).

As a first approximation, this doesn’t perform that badly: the character will make a beeline for the target until it reaches an obstacle, at which point it will do its best to get around the obstacle. It has no real problem with one or two obstacles in its path, and can get around them with ease.

However, there are significant drawbacks to this method as well: too many obstacles clustered together will become an impenetrable barrier to the character’s path; in addition, there are many scenarios where the character will get stuck oscillating between two squares that each have the same proxy distance.

Some Modifications to Improve the Algorithm

The central problem with our previous algorithm is that the AI only plans out one step at a time. A much better AI would plan several steps ahead and take note of which paths terminate in obstacles. Luckily, the scheme we developed above needs only some slight modifications to do this.

Rather than using a single proxy, let’s recursively define the n-proxy of a square as follows (here n is an integer):

  1. If the square contains an obstacle, the n-proxy is defined as some number much larger than any distance in the maze.
  2. If the square doesn’t contain an obstacle and n = 0, the n-proxy is defined as the distance from the square to the target.
  3. If the square doesn’t contain an obstacle and n > 0, the n-proxy is defined by finding the (n-1)-proxy of each of the adjacent squares (top, bottom, left, right) and finding the minimum of their values. The n-proxy is then the lesser of this value and the square’s own 0-proxy.

Although this is a complicated definition, it follows a very simple heuristic idea: the n-proxy of a square is the closest distance you can get to the target, given that you can walk n steps from that square. Note also that the proxy we were using before is the same as our new 0-proxy.

Armed with this recursive definition, we can create a much more sophisticated algorithm: at each step, the AI looks at each of the four adjacent squares (top, bottom, left, right) and moves to the one which has a minimum P-proxy (where P is a value of your choosing – note though that it must be the same for all four squares). For our game, we found that P-values around 3 were not good enough at navigating large clusters of obstacles, while P-values close to 10 slowed even desktop computers down with large amounts of recursion. We chose a P-value of 7 as this enabled sophisticated navigation while still running quickly even on an iPhone. If you are designing a game with high graphics overhead, or if quite a few characters in your game are using this algorithm simultaneously, we would suggest using a lower P-value.

There’s still a huge problem with this algorithm, which is not obvious until you code it up and try it out: the character will stop precisely P steps before the target and begin oscillating! Remember that the n-proxy of a square is the closest distance you can get to the target, given that you can walk n steps from that square. But if my current square is P steps away from the target, and all the surrounding squares are P steps away from the target, then all of these squares will return a P-proxy of zero! This is when our algorithm breaks down, as it is incapable of distinguishing between these squares. This gets represented physically by the character oscillating back and forth between two squares of equal P-proxy.

Rather than freak out, we should recognize that this is a signal that we are within P steps of the target square and we can easily pick out a path that minimizes the number of steps to the target rather than minimizing some proxy. This can be accomplished rather similar to before, by defining the n-step of a square as follows:

  1. If the square has an obstacle or n < 0, the n-step is defined as some prohibitively huge number.
  2. If the square is the target square, the n-step is defined as (P – n).
  3. If none of these conditions hold true, find the minimum (n-1)-step of the adjacent squares (top, bottom, left, right) and return the lesser of this value and the current square’s n-step.

Notice the P-step of a square gives the minimum number of steps taken to get to the target, provided that you are within P steps of the target. Now our algorithm looks as follows:

  1. For each square, rank the P-proxy of each adjacent square.
  2. If the minimum two P-proxies are equal, rank the P-step of each adjacent square instead.
  3. Move to the square with the minimum P-proxy, or P-step, depending on which is appropriate.
  4. Repeat from step 1. End the algorithm when the target is reached.

Finally, all that remains to do is to remove the oscillations that occur when the character gets stuck between two squares of equal P-proxy. (With the modified program intact, these oscillations should only occur if the obstacle requires more than P steps to get around.) The fix couldn’t be simpler: if the character’s next square is the same as its previous square, end the algorithm.

Closing Remarks

We hope you find this algorithm useful. Extensions of it can be used to create AI beyond the context of games – for example, a little roomba robot that whizzes about a room and avoids obstacles – provided that the AI has some means of mapping out its environment. Enjoy!

Games Mentioned in This Post:


 

Brimstone


 

Entombed

1 thought on “Building an AI for Navigating Obstacles”

Leave a Reply

Your email address will not be published. Required fields are marked *