Driver code

Sun, 7 Nov 2010 by Thomas ten Cate · Comments
 Cart Frenzy, Artificial Intelligence, Algorithms

There are a handful of racing games that let you race purely against your own best time, but the majority of them let you race against others. It adds an element of competition that you don’t get when racing alone. The solitary racer is someone who spends hours trying to figure out the optimal way to tackle that sharp corner, just to shave a tenth of a second off his best time. Not the kind of audience I’m targeting with a somewhat (albeit not completely) casual mobile racing game. Long story short, I need opponents.

At some point, I will probably introduce a multiplayer mode, but for now, the opponents’ carts will be driven by a piece of artificial intelligence (AI) code. The fun factor of the game heavily depends on the quality of the competition, so this needed to be done as soon as possible.

After a few days of experimenting and tweaking, I now have an AI driver that performs reasonably well. It takes its clue from waypoints defined in the level. I can place these in the editor to define the approximate path that the AI should follow:

The waypoints are shown as numbered crosses, and are connected by a quadratic spline (which is not used in-game at all). Each waypoint has a radius, which indicates how far we can deviate from the central line. These circles are no longer used in the current version, but I might start using them again in the future.

Everything in the game is controlled by the physics engine, and the AI carts are no exception. We cannot simply make them move exactly along the prescribed path: we need to provide steering and thruster input to the cart, just like a human player would. This was the tricky bit, but I eventually developed a system that works fairly well. I wrote some debugging code to visualize what is going on:

We keep track of two route segments at each moment: the segment that we’re currently on, and the one after that. You can see these being drawn as the bright red lines, just like in the editor. The AI projects its current position onto its current segment; this gives a number between 0 and 1 indicating how far we are along this segment. Then we take that same position along the next segment, and steer towards that (the thick orange line). This gives a smooth movement of our target point, and thus smooth steering behaviour, instead of jerky steering each time we proceed to the next waypoint. (The dark red line probes the distance to the wall ahead of us, and is not used for waypoint following.)

For speed control, we measure the angle and length of the next two segments, and derive an approximate corner radius from that. The acceleration or deceleration is then controlled to match the preferred speed for a turn of that radius. With some tweaking, this scheme works quite effectively.

This would all be fine if we were driving alone. But we’re not: others can bump into us and drive us off course, and we can find ourselves in a random position, at a random velocity, under a random angle, at any moment. To deal with unexpected situations, the AI is built as a state machine, which makes decisions according to a certain ‘strategy’. It currently has three different strategies:

• The ‘forward’ strategy is the default, which simply tries to follow the track according to the waypoints.
• The ‘backward’ strategy is used when we’ve run into a wall and need to back up. This gets activated when a wall is in front of us, too close to avoid by a forward turn. It drives backwards, making a turn so that the nose turns towards the next waypoint. When we’re far enough from the wall, we resume the forward strategy. This makes for quite realistic navigation behaviour.
• The ‘panic’ strategy is used when we’re stuck, that is, the cart hasn’t moved very far for a few seconds. It just sets a random speed and direction for a second or two, then resumes the forward strategy.

This approach seems to work pretty well. So well, in fact, that I’ll have to tune it down significantly to make the opponents beatable at all. I can think of several ways to do this: give them a nonzero reaction time, allow them to make decisions only a few times per second instead of every frame, smear out the decision making process over several frames, adjust the waypoints to leave some more room, add some randomness… plenty of possibilities to play with. But that will have to wait until serious playtesting – for now, I’m quite happy with a brainchild that outperforms its creator.