= videos.length) currentVideoIndex = 0; } window.onload= function() { videoPlayer = document.getElementById("playerClassicAI"); PlayNext(); } HTML5 Video is required for this video. We have the procedural track, we have the ghysics car model, let’s make a simple top down racing AI! Above you can see me play with the basic AI (I am the red one that always ends up hitting the wall :) ) [Continue Reading..]" />

Radu Angelescu

dec. 29, 2015

Implementing a simple top down racing game ai controller

We have the procedural track, we have the ghysics car model, let’s make a simple top down racing AI! Above you can see me play with the basic AI (I am the red one that always ends up hitting the wall :) )

This article will be really easy and short, but it will produce cool results. This is a basic AI but you can actually make a full arcade racing game with it just by layering a FSM on top to handle some special cases. The main ideea is that you need to know the racing line and then you need to follow it as good as possible.

Racing Line

The racing line is the trajectory the car will follow during a race. This is actually an AI problem in itself: generating the best racing line on a given track for a given car physics model. The main problem is you need to minimize the time it takes to complete the race. If you minimize the length of the race line this could result in increasing the time because you need to break a lot to be able to resolve short curves, if you increase the length you may have a good speed but you still need to travel extra. You can also express the problem in curvature terms but you still meet the same problems.

We will not tackle a machine learning algorithm for generating the best race line in this article, we will just settle on an empirical approximation of a good racing line. In other words we will settle for an easy way of tuning the curvature of our race line.

Our algorithm is simple and it resembles a step from the procedural track generation article: we take the center points of the track and apply a 3 order moving average smooth filter

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
void CTrack::genRacingLineApproximation()
{
    //apply a simple smooth filter (moving average 3, centered)
    for (int k = 0; k < m_trackSize; k++)
        m_points[k].racingPoint = m_points[k].center;

    for (int i = 0; i < m_smoothIterations; i++)
    {

        for (int k = 0; k < m_trackSize; k++)
        {
            // wrap around index
            int prev_idx = ((k - 1) < 0) ? (m_trackSize - 1) : (k - 1);
            int next_idx = ((k + 1) >= m_trackSize) ? 0 : (k + 1);
            // moving average
            m_points[k].racingPoint = 1 / 3.f *(m_points[prev_idx].racingPoint + m_points[k].racingPoint + m_points[next_idx].racingPoint);
        }
    }
}

Note that we can choose any smoothIterations variable we want, as this becomes bigger the overall racing line curvature will get smaller. Experiment with this, see what’s the best value. It can also be used for generating variations in racers.

For the “try to race like the player” problem we will generate the race line using the player race data.

Creating the controller that will follow the race line

I called it BasicAIController. The algorithm itself is not a difficult one but this controller is important for future development and for formulating the problem.

So It tries to follow the race line. It just looks ahead and picks the race line point from his lookat and then it tries to go towards it. We try to keep our controllers on the high level side: they can only simulate pressing keys and receive data that a player normally would.

We define our basic parameters

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
enum EBASICAI
{
  EBASICAI_MAXSPEED,
  EBASICAI_ANGLETOTURN,
  EBASICAI_DISTANCETOFRONTWALL_STOP,
  EBASICAI_LOOKAHEAD_DISTANCE,
  EBASICAI_ANGLETOTURNSPEEDINFLUENCE,

  EBASICAI_NUM
};
float m_params[EBASICAI_NUM];

Note that the usage of a an array is not arbitrary or a crazy decision :) . We do this so we can later generalize and use the basic ai for our machine learning/optimization algorithms.

So this is the whole AI update function (it’s really a line follower)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// Reset our current action
m_currentAction[OA_DOWN] = m_currentAction[OA_LEFT] = m_currentAction[OA_RIGHT] = m_currentAction[OA_UP] = -1.0f;
// Get our sensor data
float *sensorData = m_car->getSensorData()->data;

//Get the lookat race line point
SGenTrackNode &toSector = TRACK->getSectorPoint(m_car->getCurrentRaceSectorIdx() + floor(m_params[EBASICAI_LOOKAHEAD_DISTANCE]));
//Create the target vector
b2Vec2 diff = toSector.racingPoint - m_car->getPosition();
//Create the direction to target vector
b2Vec2 dir = diff;
dir.Normalize();

// Get the forward car vector
b2Vec2 forwardCar = m_car->getCarModel()->getDirection();

// Get the angle between the car front and the direction to target
// map it to degree space
float dot   = -forwardCar.x * dir.y + forwardCar.y * dir.x;
float angleInDegrees        = glm::degrees(acos(dot));
float targetAngleInDegrees  = 90;// front of car
float diffAngleToTarget     = targetAngleInDegrees - angleInDegrees;

// Turn the car in the direction that minimizes the angle between the car forward vector
// and the to target vector
 if (diffAngleToTarget > m_params[EBASICAI_ANGLETOTURN])
   m_currentAction[OA_RIGHT] = 1.0f;
 else
 if (diffAngleToTarget < m_params[EBASICAI_ANGLETOTURN])
   m_currentAction[OA_LEFT] = 1.0f;

 // Tune the speed procent we are safe to accelerate within
 // note that it is invers proportional to the to target angle (or you can perceive this as curvature)
 float maxSpeedPercent = m_params[EBASICAI_MAXSPEED] * (1.f - diffAngleToTarget * m_params[EBASICAI_ANGLETOTURNSPEEDINFLUENCE]);

 // Accelerate if we are within safe velocity limits and if we did not hit a wall
 if(sensorData[IS_VELOCITY] < maxSpeedPercent && sensorData[IS_RAYCAST0] > m_params[EBASICAI_DISTANCETOFRONTWALL_STOP])
   m_currentAction[OA_UP] = 1.0f;

 //Send the action
 m_car->setAction(m_currentAction);

The comments in the code should be self explanatory.

You may notice that our line follower AI uses parameters. These parameters actually dictate how well our line follower, follows the line and actually how good it’s overall performance is.

The parameters can only be determined based on our car physics model, so we may see this as an opportunity to test a differential evolution algorithm for the problem: “pick the best parameters so the racer gets the best time in a race”. But until then let’s just enjoy our simple AI and watch it perform on various tracks, using some “ok” hand picked, TOML stored :) , parameters.

Don’t forget the full source code can be found here and the latest commit id when writing this article is 724ccc1.