Programmer’s Weekly: Steering AI in the right direction

Written by: Mark Bouwman

AI? Artificial Intelligence?

Indeed. Artificial Intelligence. You might be wondering, what exactly IS Artificial Intelligence? (Of course you’re not, you’re reading a programmer’s blog on the website of a game company. I’m guessing you got here for game related stuff, and that AI isn’t all that new to you.)

Artificial Intelligence has a wide range of topics, spreading from simulating flocks of birds to computers beating us at a game of chess. However, when we talk about it in the gaming industry, we usually mean just one thing: the illusion of intelligence in a non-player character (NPC). The illusion that the NPC is smart enough to act on his own, the illusion that an actual human being controls him. It’s getting the player to believe the opponents are aiming the same way he does, it’s getting the player to believe the opponents don’t drive the best laps possible, it’s getting the player to believe his opponents are as bad at playing the game as him.

But Mark, when do you need a NPC to be intelligent?!

Well, I’ll give an example. In one of Little Chicken’s current projects, the player can drive around and has to chase enemies, shooting them down in order to continue to the next level. But to create a challenge for the player we don’t want the enemies to feel like they’re just driving randomly (and through buildings). We want the enemies to be smart. We want them to dodge buildings, chase the player and group up with other enemies. This brings us to the topic of this week’s post: Getting the AI to steer.

The challenge: Getting the enemies to NOT crash into a wall
Let’s start by actually getting the AI to drive. I mean, how can we chase the AI if they’re just standing still? Getting them to drive isn’t hard: all you need to do is to move the AI forward and rotate them so that they steer. It’s nothing fancy, nothing special. The tough part though, is getting them to NOT crash into walls (read: not making them look like idiots).

There are tons of ways to implement collision detection and collision prevention. During the development of this game we thought of, and implemented, several different ways to get the AI to detect walls around them, until we finally got to something we agreed to use in the game.

The first method we came up with was traversing the AI over a grid, using A* to find the shortest path to their goal. Buildings were represented by non-traversable tiles in the A* grid. This ‘perfect route’ was then used to create a curved route that the AI followed. We switched to a different method due to numerous things; balancing quality and performance being the main reason. A* can be performance heavy, calculating a lot per frame. If you have three enemies calculating the path to a point about 200 squares away, it can take a LOT of time to actually get the best possible path if there are lots of obstacles in the way. Also, the quality was not as high as we wanted it to be; AI cut corners due to the curved lines they followed. Having no other form of collision detection on the AI, they carelessly drove through walls. Because of this, the grid had to get smaller and more precise. A goal that used to be 200 tiles away, suddenly got 400 tiles away! This more than doubled the amount of possible calculations!

The most efficient way we found to handle collision detection was through using something I like to call the three-point-raycast method. The method is fairly simple, but shows that the simplest solutions sometimes have the best outcome. It’s light on performance and memory, works fast and creates human-like movement.


A visual representation of the three-point-raycast method

How it works: Every NPC has a point at the front of his bike from which a ray is casted. This initial ray detects a possible collision directly in front of the AI. When this possible collision has been detected, two new rays get casted. These new rays are slightly angled (about five degrees) to the left and the right side of the initial ray. These rays give information on which side has an object closest to the AI. The side with the closest collision should be avoided; there is more space at the other side. The AI steers towards that open space, based on how close the collision in front of him is. The closer the object he can collide with, the tighter he steers. Because of this, the AI moves in nice curves, avoiding all collisions.

Voilà, done. The AI now steers like a human being.

All we had to do next was getting the AI to actually steer towards a goal. This is used for chasing the player. With collision detection out of the way, this was actually quite an easy thing to do. All we had to do is create a simple rule: When there’s no collision detection for a second or so, steer towards the goal. With this one rule in action, we were able to have the AI circle around the player, scatter and race away from the player and much, much more. Such a simple rule made the AI a lot more fun to play against.

So, what did you learn?

Getting the AI to steer ended up not being all that hard once we found a good way to implement the collision prevention. It did however, get me to realize something important: Keep it simple. Keeping things simple help a lot. The three-point-raycast method was so much quicker to implement and required less thinking (math) than the method using pathfinding, but gave much better results. Sometimes, the easiest solution is the best solution.

Keep It Simple, Stupid.

2,595 total views, 1 views today