To start off this deep dive I want to ask you two questions, when was the last time you raced an AI in a game? Now, when was the last time you raced an AI that felt competent at driving in the game world? Even the premiere arcade racing game Need For Speed: Unbound is still plagued with complaints about inept AI that still somehow wins races on the hardest difficulty through painfully strong rubberbanding.

Worse yet, none of these AIs seem to know how to drift! The first competent drifting AI only just came out about 2 weeks ago with an update to Gran Turismo's Sophy, and that is squarely within the realm of sim racing, so this isn't your super high octane drift racing experience either, you can beat a drifting Sophy by just following the ideal racing line!

What are we to do? With studios of tens to hundreds of developers putting out subpar single player racing experiences, and everyone else just giving in and pitting you against ghosts and other online players to substitute the adversarial experience of drifting...

I'm glad you asked!

Introducing the very first iteration of our drift racing AI: Scully

Inspired by the classic Scalextric slot car racers, this AI can be given almost any arbitrary line, and follow it as quickly as possible within the driving physics provided in Drift King. Using nothing but steering, handbrake and boost. With 100% throttle at all times.

In this deep dive, I'll not only be going into detail on how the algorithm works, so that you can implement it within your own games. But also going into the process of how we produced this algorithmic solution, so you can learn from our mistakes too!

Drift on!

Scully's Algorithm

Inputs & Outputs

Scully is a very simple AI in terms of inputs. All we need is a curve that we can sample at a specified distance (think of it like the slot for a slot car, the AI will follow this line), and the physical properties of a given vehicle that we are controlling: position, rotation, velocity, angular velocity, and acceleration. For more complex behaviours like avoiding other vehicles, we'll need more inputs like the positions of other nearby cars, but that's outside the scope of this deep dive. At the other end of the algorithm, our outputs are also very simple, outputting the desired throttle, braking, steering, handbrake, and boost. These can be fed into your vehicle controller to get our desired behaviours to execute.

If your game does not have any way of increasing engine power at will (boost, NOS, magic), the vehicle only be able to maintain the line from the inside of the corner, going towards the outside will be unavoidable. However, you may be able to modulate throttle instead, using only 0.5 throttle in the middle of a corner, and increasing as necessary to keep the vehicle on the line. I leave this as a challenge to the reader!

In short:

• Inputs
  • Our desired line, with a method to:
    • Sample location and tangent at a given distance (not sampled with normalised t, must be distance)
    • Find the closest sample on the curve to a given location, which returns the distance along the curve. Make sure this is commutative - the distance that is output from this must give you the same sample if you input that distance into the other function
    • You may also want the distance function to wrap at the ends of the line if you wish the vehicle to drive continuously around a circuit
  • Vehicle position and rotation
  • Vehicle velocity and angular velocity
  • Vehicle acceleration (can be derived from velocity delta if not provided, like in Unity)
  • Vehicle drift angle (can be derived from the vehicles velocity and rotation)
• Outputs
  • Desired throttle (float, 0 to 1) - always 1 in our algorithm
  • Desired handbrake (boolean)
  • Desired steering (float, -1 to 1)
  • Desired braking (float, 0 to 1) - always 0 in our algorithm
  • Desired boost (boolean)

Now that we have our inputs and outputs, we need our algorithm to transform this. One could use a neural network at this point, but then you have to contend with weeks of training time and frequent overfitting issues. With a simple algorithm we can reason its effectiveness and tweak with intent instead of guessing!

Ideal Algorithm

At a top level, our idealised behaviour is a state machine AI with only two states, line follow and drift mode, we start the vehicle off in the Line state:

1. Collect our inputs, and use the vehicles position to find the closest sample on the curve to the vehicle. We want to also calculate the vehicles current distance to this sample, we'll call this the Distance Off Track
2. Project where our vehicle is going to end up given its current velocity and acceleration - for both 0.5 seconds and 1.2 seconds into the future
   1. The formula to find this is p + vt + 0.5 * a (t*t) - where p is position, v is velocity, a is acceleration, and t is time
3. Find the distance from the vehicle to these two projected points, add this distance to the distance given by the closest sample, and plug this into the curve. This gives us our offset from the ideal line, if we keep these two projected points on top of the sampled points, the car drives the curve perfectly!
   1. In our implementation, we also add an extra bit of distance when sampling the curve, keeping the sampled points a set distance ahead of our projected points, even when exactly on the line. This is because we don't use the position offset but the angle offset, and the offset helps to reduce the impact of sampling inaccuracies (we don't use exact bezier solutions, instead baking points on the bezier curve and lerping between them)
4. We'll call our two sample/projection pairs our Steering Offset, and our Drifting Offset, our next decisions are based on these offsets
5. If our Drifting Offset goes too far off the track and we're in Line mode, switch to Drift mode
6. If our Steering Offset and our Drifting Offset are back on the track, switch back to Line mode
7. In Line mode, we get the angle that points along our Steering Offset, and compare that to the vehicle's current pointing angle, applying steering to reduce the Steering Offset angle to zero.
   1. The angle in this case is just a signed angle that points from the projected position to the sampled position, relative to our cars current angle (so if the car needs to turn right to match the offset angle, it's positive, and for left, negative)
8. In Line mode, the path follow algorithm is complete, return to Step 1 for the next frame.
9. In Drift mode, we instead get the angle that points along our Braking Offset, comparing that to our vehicle's current pointing angle, applying steering to reduce the Drifting Offset angle to zero
10. Also in Drift mode we'll want to apply handbrake until the vehicle drift angle is high enough to sustain the drift without further handbraking
11. Once we're sliding, now we do the real magic of drift control...
12. Continue holding the handbrake until the Steering Offset is near the outside of the corner
13. When the Steering Offset falls to the outside of the corner, apply boost to bring it back to the line.
    1. We use the tangent of the Steering Offset sample to determine "outside". If both projected points fall on the same side, we are travelling towards the outside of the corner. If projected points fall on opposing sides, we are travelling too far on the inside of the corner, AKA cutting the corner
       

Effectively:

• In Line mode, align car to resolve 0.5s projected angle
  • The vehicle uses steering and tyre grip to resolve the position difference between the projection and the sample
• In Drift mode, align car to 1.2s projected angle, and use the handbrake/boost to resolve 0.5s projected angle
  • The vehicle uses the braking projected angle to figure out what direction to apply velocity (like a rocket ship in space), and uses position difference between the steering projection/sample pair to figure out how much acceleration is required to resolve the future 0.5s position of the vehicle

Visual representation of all the data that our algorithm generates and the desired outcomes using this data

Even more basically - in Drift mode: turn to face the inside of the corner, and push the car backwards and forwards to hold the line. That's it!

We understand that this may still be quite confusing, and if so, do not hesitate to leave a comment or send us a message, and we'll explain in more detail, or even send you a snippet of our code!

How We Got Here

Step 1 - Meandering

Making mistakes is a big part of solving problems, and the first and biggest problem was failing to control variables while developing the algorithm. Initially, we started developing our AI solution by chucking a bunch of bots on a track, and attempting to get the bots to follow the entire track at once, bumps and all.

We just chucked this track at the AI with our fingers in our ears screaming "GOOD LUCK!"

We found that as we built solutions that we were overfitting to the bumps and peculiarities of this track, and that we needed to simplify, so we moved to a clean flat map.

Much better! Right?

But no, this wasn't enough, we couldn't quickly iterate, and were once again overfitting. This time however, we were overfitting to the first corner, and not idealising the starting conditions to truly lock down each single variable. It was disaster after disaster, watching the vehicle take the first corner reasonably well and then absolutely suck at the remainder of the track! We needed a better solution.

We needed individual test suites.

To this end, we quickly whipped up a bit of code that would start the car with an exact position and velocity, and once the vehicle hit the end of the spline, we'd warp it back to those exacting values. We then created a bunch of individual corners with all sorts of different properties, like varying corner radii, different angles. All sorts of different scenarios that the vehicles are likely to encounter, which finally came to this:

Perfect, now we have consistency, much easier to solve!

This was the solution we were looking for, turned the problem from intractable, to trivial.

Step 2 - Entering the corner

Once our test suites were developed, we could start tackling the problem proper, but another important step was setting up a baseline, to both prove that even the tightest corner had a reliable solution with only 3 inputs (steering, handbrake, boost), and to break down the human thought process into reproducible algorithmic steps.

To this end, we reused our Clip That functionality to save a replay of a perfectly driven high speed line. This saved both the path that the car followed and the inputs required to recreate the turn. By stepping frame by frame through the replay, we can reverse engineer our subconscious and figure out exactly what problems we're trying to solve and what outcomes we're trying to achieve through our inputs.

Snapshot of a recorded human high speed drift line, with spheres to mark handbrake input start and end

Through this, we found that the fastest line is achieved by considering two styles of driving: Holding a line while the vehicle's grip is sufficient to take the turn - and - slamming the handbrake whenever we needed a tighter turning radius, using the boost to keep from falling off the track at the deepest part of the corner - allowing us to carry more speed into the corner - and boosting as the turn ends to bring the vehicle's speed back up to race pace.

Step 3 - Tightening the turn

After proving that the problem is solvable with an algorithm, and figuring out what that algorithm should be to match the human baseline, we now have to write our algorithm and continuously test it against our baseline. Since our AIs take all the corners simultaneously, we can get immediate feedback on all our testing, proving each step of the way that our algorithm can handle more than just one corner type!

Our first step was ensuring that we follow a non-drift line without significant deviation, since cutting corners could cause the AI to slam into walls or end up in slower terrain such as grass. Once our straight line was proven, we added in the first part of the drift, making sure that the angle that the car ends up at before needing to boost was matching the recorded vehicle's angle. Finally, we add in our handbrake/boost part of the algorithm and verify that the vehicle holds steady on the line through the exit of the corner!

Once we have the vehicle following the line on all our test cases, only then do we move back to the complex track to verify that it can handle a series of corners. Only after all that, can we finally bring the vehicle back to our intended tracks back in the main game.

Our attempts at producing an AI were so effective, that no further tweaks were needed for most of the tracks in the game, proving that the AI is not overfitted to any single track! We do however have some overfitting issues for cases where the vehicle can accelerate and turn considerably faster than stock, which is the target of further improvements to the AI.

Step 4 - Adjusting our exit

Now we have a functioning AI that follows the line perfectly, and now we simply need to integrate it into our existing AI systems such as pathfinding. Unfortunately we don't want to give away too much, so we're not going to be describing how the traffic pathfinding works, as that is a considerable extension to the path following behaviour. If you're stuck with AI pathfinding however, send me a message, and I'd be more than happy to lend a hand!

Conclusion

In basic terms, if you want to create effective state machine based AI systems, you must reduce the problem space. Always remove complexity from your testing, and try to control your variables such that you are only dealing with one single variable at a time. Ensure that your test cases get to the point as quickly as possible, and parallelise your test suites where possible.

As a bonus end note, for creating difficulty levels for your games: Always make your hardest difficulty first. Try and create the ideal perfect AI and then add human mistakes. Never ship broken AI as an "easy mode". Your players will not appreciate a game that they win by AI ineptitude, and appreciate even less a game that they lose in spite of AI ineptitude (like in cases of severe rubberbanding - see: the Need For Speed franchise)

Good luck with your AI systems, and happy drifting!

- George