Introduction

This tutorial will hopefully explain everything you need to know to make a successful AI system for a 2d top down racing game.

Basic Theory

Most 2d (top down) race games are based on a series of "waypoints" that mark out a route for the ai cars to follow. When a car gets within a certain distance of a waypoint it heads for the next one, and so on until a complete lap has been travelled.

A simple algorithm to implement this would be something like:

Public Sub DoAI
    For n = 0 to Ubound(Cars)
        If Cars(n).NextNode.Location = Cars(n).Location then
            Cars(n).NextNode = (cars(n).NextNode + 1) mod NumNodes
            Cars(n).Direction = GetAngle(Cars(n).Location, Cars(n).NextNode.Location)
        Endif
    Next n
End Sub

This would result in a working way to follow a route, although it wouldn't be very realistic. It basically just checks if each car is sitting directly on the node it was heading for. If it is the car is set to head for the next node and it is spun round to face it. Using this method you can have any number of cars chasing around the "track" defined by the waypoints (nodes) very quickly.

However as you probably noticed there's several huge bugs in this. Firstly, a car must be exactly on top of a node for anything to happen, and secondly when a car does reach a node, is instantly "snaps" into its new direction, which is totally unrealistic and very silly.

Improvements

A better approach would be to first make the nodes have some volume, so you can detect when a car gets very close but may miss the actual node itself. This is a fairly simple check, you measure the distance between the centre of the waypoint and the centre of the car, if it is less than the radius of the waypoint combined with the radius of the car, then they're in contact and we can start driving towards the next node.

The other bug we should address is the turning problem. Rather than simply setting the direction of the car to be the angle to the next waypoint we instead check every tick if the waypoint is on the cars left or right side and turn a small amount in the appropriate direction. Obviously we have to work out a way to decide if the car is on our left or our right.

Remember that VB thinks about angles in terms of radians. A radian in a measure of angle similar to degree's, but while there are 360 degrees in a complete turn, there are only 6.28318… or Pi * 2 radians in a complete circle. For this example I am numbering them in the range of -Pi to +Pi, this is because it makes a lot of the calculations easier. By the way, in the example program you will see a small sub incidentally that checks values passed to it and forces them to be within this range. This is good practice anyway since sometimes functions and code will return values far outside the usual ranges, this just puts them back in.

Private Sub CheckAngle(ByRef Dir As Single)
    'simply ensures that a direction is within a range of -1*Pi to +1*Pi
    While Dir > PI Or Dir < -PI
        If Dir > PI Then Dir = Dir - 2 * PI
        If Dir < -PI Then Dir = Dir + 2 * PI
    Wend
End Sub

I'll quickly show you two utility functions used throughout this program (and any game really), FindAngle and GetDistance. FindAngle simply enough takes two pairs of co-ordinates and returns the angle between them (in radians). If you couldn't have guessed, GetDistance returns the distance between two pairs of co-ordinates.

Private Function FindAngle(X1 As Single, Y1 As Single, X2 As Single, Y2 As Single) As Single
    Dim sngXComp As Single
    Dim sngYComp As Single
    'Find the angle between the 2 coords
    sngXComp = X2 - X1
    sngYComp = Y1 - Y2
    If Sgn(sngYComp) > 0 Then FindAngle = Atn(sngXComp / sngYComp)
    If Sgn(sngYComp) < 0 Then FindAngle = Atn(sngXComp / sngYComp) + PI
End Function
Private Function GetDistance(X1 As Single, Y1 As Single, X2 As Single, Y2 As Single) As Single
    GetDistance = Sqr((X1 - X2) ^ 2 + (Y1 - Y2) ^ 2)
End Function

Now, in order to work out if the node is on our car's left or right side we need to first find the angle using FindAngle, however this returns the angle relative to the screen, i.e. 0 is north. To work out the relative angle we must subtract our direction from that angle, thus giving the direction relative to us. Then we obviously run our CheckAngle just to force the angle back into the proper range. Now 0 radians is directly ahead of our car, no matter what direction it is facing. Thus if the angle is positive we know the node is on our left, and if its negative then the node is clearly on our right.

Now we know which way to turn, it's simply a case of adding or subtracting our "turn angle" from our direction, like so.

If RelativeAngle > 0 Then
    Car.Direction = Car.Direction + Car.TurnRatio
Else
    Car.Direction = Car.Direction - Car.TurnRatio
End If

Problems

We now have a car that can smoothly track a series of waypoints very nicely. There is however one big bug left to iron out (well ok there are several, but one main one). As you may have noticed, no attention has been paid to the speed of the car. At the moment it travels with a totally constant speed, which does of course cause a serious problem when we remember that it only turns quite gradually as well. If two waypoints are too close together the car can quite easily get caught in a loop, where it cannot turn fast enough to reach the waypoint and circles around and around it forever.

There are lots of ways to calculate this, some much better than others obviously. A fairly simple, yet very effective method that I plan to use in my next game is to calculate the turning circle of the car each tick (i.e. the circle it would drive around if it kept its current speed). If the next node is within this circle we know we can't reach it at our current speed, and we have to slow down. Since we are supposed to be racing it makes sense to increase our speed if the node is outside the circle as well.

However, the problem is, given that we know the forward speed of the car, and the amount it turns every tick, how do we calculate the radius of the circle it makes? I have to admit that I didn't have a clue, or rather I did think of several fairly inefficient ways to do it, but in the end I had to ask for help (you should never be afraid to ask people to help, most people are more than willing to share their experience). Anyway, a guy going by the name of Brykovian came up with this way, which works perfectly, thanx a lot.

r = (v^2)/a

Where r is the radius of the circle, v is the velocity of the car, and a is its acceleration towards the centre of the circle. How, you are wondering, do we find the acceleration towards the centre point? He answered that too :-).

If you know the X & Y velocity components your car has at one point (call 'em VX1, VY1), and then you know the X & Y velocity components your car has at another point (VX1, VY2), and you know the amount of time between them (T) ... then your average acceleration over that time is the change in velocity over that time, or:

AX = (VX2-VX1)/T 
AY = (VY2-VY1)/T

So your total velocity amount is:

 A = Sqr(AX*AX + AY*AY)

So, first we project our circle round a few steps so we can get a small arc and the second pair of co-ordinates (VX2/VY2 in his example). Then we calculate the relative x and y velocities, like this.

Dim DummyCar    As CarType
Const NumTicks = 10
DummyCar = Car
For T = 1 To NumTicks
    If TurnLeft Then
        DummyCar.Direction = DummyCar.Direction + DummyCar.TurnRatio
    Else 'Turn Right
        DummyCar.Direction = DummyCar.Direction - DummyCar.TurnRatio
    End If
    DummyCar.Location_X = DummyCar.Location_X + DummyCar.Speed * Sin(DummyCar.Direction)
    DummyCar.Location_Y = DummyCar.Location_Y - DummyCar.Speed * Cos(DummyCar.Direction)
Next T
VelocityX1 = Sin(Car.Direction) * Car.Speed
VelocityY1 = Cos(Car.Direction) * Car.Speed
VelocityX2 = Sin(DummyCar.Direction) * DummyCar.Speed
VelocityY2 = Cos(DummyCar.Direction) * DummyCar.Speed

We now know the x and y components of the speed both before and after we projected out a segment of our movement, we can calculate the acceleration.

AccelX = (VelocityX2 - VelocityX1) / NumTicks
AccelY = (VelocityY2 - VelocityY1) / NumTicks
AccelTot = Sqr(AccelX * AccelX + AccelY * AccelY)

And finally work out the radius of the circle.

Radius = (Car.Speed * Car.Speed) / AccelTot

Note that this can cause an overflow error if the car's speed is 0, so in the example there's a small error handler in place.

Now all that remains to do is calculate the centre point of the circle…

If TurnLeft Then
    OriginX = Car.Location_X + Radius * Sin(Car.Direction + PI / 2)
    OriginY = Car.Location_Y - Radius * Cos(Car.Direction + PI / 2)
Else 'Turn Right
    OriginX = Car.Location_X + Radius * Sin(Car.Direction - PI / 2)
    OriginY = Car.Location_Y - Radius * Cos(Car.Direction - PI / 2)
End If

… and calculate if the node is within it.

Distance = GetDistance(CircleX, CircleY, Nodes(NextNode).Location_X, Nodes(NextNode).Location_Y)
If Distance < CircleRadius Then
    Car.Speed = Car.Speed - Car.BrakeSpeed
    If Car.Speed < Car.MinSpeed Then Car.Speed = Car.MinSpeed
Else
    Car.Speed = Car.Speed + Car.Accleration
    If Car.Speed > Car.MaxSpeed Then Car.Speed = Car.MaxSpeed
End If

Now we have a really nice little model for tracking nodes perfectly. Well almost perfectly, there are a couple of tweaks that could be made, one of which I implemented in the example program and one or two others that go beyond the scope of this article.

Advanced AI's

The first little tweak I implemented was to give the car a blind spot behind it, if the node is within this angle, the car will brake, or reverse, thus preventing it from taking a huge circle round to reach a node that's behind the car. Thus making the code above become:

If Distance < CircleRadius Then
    Car.Speed = Car.Speed - Car.BrakeSpeed
    If Car.Speed < Car.MinSpeed Then Car.Speed = Car.MinSpeed
ElseIf Abs(RelativeAngle) > Car.BackAngle Then
'Check if node is behind us and slow down if it is
    Car.Speed = Car.Speed - Car.BrakeSpeed
    If Car.Speed < Car.MinSpeed Then Car.Speed = Car.MinSpeed
Else
    Car.Speed = Car.Speed + Car.Accleration
    If Car.Speed > Car.MaxSpeed Then Car.Speed = Car.MaxSpeed
End If

This makes the car behave a little bit more sensibly, as you can see from the sample program, however there is still lots of room for you to expand on the system.

I wont go into too much detail here, since I haven't actually implemented any of these ideas for myself yet, however after I finish writing my game I may well write another tutorial on advanced car AI systems.

The main problem with the system in the sample app is that it wont always take the shortest route, it accelerates to either its maximum speed or the maximum speed at which it can reach the next node, however it can go quite a long way off course in order to do so. This is partly because the way the car is set up in the example it has a fairly low turning ability. I have noticed that when the BackAngle (the "blind spot" behind it) is decreased a lot (i.e. the car has tunnel vision) it does work much better, try experimenting with it to find the optimal angle.

Another problem is the cars ability to only track a single node at once. As you will see from playing with the example, it quite often can take a fairly logical set of nodes, and because it turns the wrong way, and because of the problem in the last paragraph, it can sometimes head into a node in such a way as the next node is then behind it, causing it to do a three-point turn and swing round to try and get the next node. (Incidentally the ability for the AI to do a three-point turn happened entirely on its own, I never intended for it to happen. Its things like that that make AI programming so much fun.)

There are lots of ways to resolve this issue, and I haven't thought about it enough to give any advice, but you basically need a way to work out the optimal angle to enter each node at (this could be part of the node data) and then angle the car not only to hit the node but if possible to hit it at that angle. This reminds me a lot of a simple Bézier curve, so perhaps that would be a good way to start researching ways to do this. Then again if your levels are designed well you shouldn't have any real problems with this.

Depending on how the waypoints are set up you can create some advanced features like shortcuts, perhaps with doors that open and close so the waypoint has some basic logic built into its definition, or you can use random weightings to create more interesting and believable AI's. You could even implement an entire scripting engine into the nodes, allowing a car to make very intelligent decisions about where to go next.

One other thing that deserves a mention is what to do when a car, due to a collision with another car, misses a waypoint entirely, yet is in a position beyond it, and should logically carry on to the next node. One fairly simple way I am considering implementing in my game is to check if the node after the current one is closer than the current one and switch to it if it is. However this could cause problems. Consider for example a long straight with a hairpin bend and another long straight coming back the same way. On the way towards the hairpin bend, the node for returning back the other way could be closer, even though there is a solid wall in between them.

These issues I leave to you to resolve as you see fit, I hope I have however given you a fairly good understanding of the basic principles of how to create a playable and enjoyable AI system for a top down race game.

Good Luck.

Nick Turner
The Tyrant

Download the sample application here.