Radu Angelescu

Dec 21, 2015

Procedural race track generation

Hey guys! This article is about implementing procedural generated, closed race tracks for my 2d top down racing game AI framework.

So I got back to my Carvatar project, after having a little break. It currently has a simple AI controller (really simple) that actually uses only 2 raycast sensors to take input decisions or a neural network controller that is currently trained just for testing purposes after the simple AI. The neural network manages to reproduce the simple AI really well (but that’s to be expected, because the simple AI is really simple :) ). The car model is not that hard to control so simple ruled AI does not perform that bad :). This will change.

Back to our tracks

I used procedural generated race tracks to make my life easy, this way I could have a ton of tracks without having to paint them/edit them manually. I kept the algorithm as simple as possible (my goal was just to get something ok for the AI), but it was kind of fun so I think I will later come back to this and experiment other ways of doing it.
I knew I did not want to do a lego like method (where you have a certain number of pieces for the track) and then do an assembly process :), because I want something more interesting and flexible that isn’t based on manually created content. The LEGO (L-System :D ) approach is actually a good one, used a lot in games, it makes life easier, and if you have a deadline and good graphic artists/editors I think it is the sane solution, but it’s always fun to try new things.

My first instinct was use a composite Bezzier curve, but I said I should first try something easy and see if that gets me close to what I want.

So my algorithm is simple, the trick is actually to make a radial representation of the points on the track. I first generate the center line (line that marks the center of the track), this is actually the basis of the algorithm, and then generate all the other in game information for it. If I ever want to test other generation methods I can easily change the centerline function.

We have a circle and we want to pinch it or squish it, do some random transformations so we get a random closed curve. Of course that we could actually use any kind of closed curve as a starter point (the circle is just one of the possibilities).

  • Pick circle center: \(C\)
  • For each control point
    • Pick a random radius \(R\) (for a low probability pick \(R\) to be really big), this will be our curvature
    • Map circle \(\alpha\) angle to current control point
    • Set the control points coordinates \(P = C + R (\sin(\alpha), \cos(\alpha))\)
    • Do a linear interpolation between control points to get the other points values
  • Make the end point be the start point
  • Lerp the remaining interval
  • Smooth the points

So here it is:

 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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
void CTrack::genCenterline(b2Vec2 *points)
{

    b2Vec2 centerOfTrack = b2Vec2(SCREEN_SIZE_WIDTH / 2.0f, SCREEN_SIZE_HEIGHT / 2.0f);
    // generate first important points
    // with a low sample rate (given by the downstep)
    int i;
    for (i = 0; i < m_settings.track_size; i += m_settings.down_step)
    {
        float randomRadius = randomInterval(m_settings.radius_curvature[0], m_settings.radius_curvature[1]);
        float randomValue =  randomInterval(m_settings.hard_curvature_probability[0], m_settings.hard_curvature_probability[1]);
        float offsetconst = (randomValue >= m_settings.hard_curvature_probability[2]) ? (float)m_settings.hard_curvature_value : (float)m_settings.radius_offset_curvature;
        float radius      = offsetconst + randomRadius;

        float alpha = ((360.0f / (m_settings.track_size - 1)) * i) * DEGTORAD;
        // control point
        points[i] = centerOfTrack + radius * b2Vec2(sin(alpha), cos(alpha));

        // fill in the rest of the interval
        const int startIntervalIdx = i - m_settings.down_step;
        if (startIntervalIdx >= 0)
        {
            const int endIntervalIdx = i;
            lerpInterval(startIntervalIdx, endIntervalIdx, points, m_settings.track_size);
        }
    }
  //Make the end point be the start point
  points[m_settings.track_size - 1] = points[0];
    //lerp last part if track_size is not a multiple of downstep
    if (i >= m_settings.track_size)
    {
        lerpInterval(i - m_settings.down_step, m_settings.track_size-1, points, m_settings.track_size);
    }

    //apply a simple smooth filter (moving average 3, centered)
    for (int i = 0; i < m_settings.smooth_iterations; i++)
    {
        for (int k = 0; k <  m_settings.track_size; k++)
        {
            // wrap around index
            int prev_idx = ((k - 1) < 0) ? (m_settings.track_size - 1) : (k - 1);
            int next_idx = ((k + 1) >= m_settings.track_size) ? 0: (k + 1);

            // moving average
            points[k] = 1/3.f *(points[prev_idx] + points[k] + points[next_idx]);
        }
    }

}

void CTrack::lerpInterval(int startIdx, int endIdx, b2Vec2* points, int size)
{
    const int lenInterval = endIdx - startIdx;
    for (int j = startIdx; j < endIdx && j < size; j++)
    {
        const float ammount = 1.0f - (endIdx - j) / (float)m_settings.down_step;
        points[j] = Lerp(points[startIdx], points[endIdx], ammount);
    }
}

After generating the center line, I map it to my logic representation of the track and then generate the static physic objects. The main function that generates the track looks like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
void CTrack::genTrack()
{
    loadSettingsFromTOML("TrackGeneration.TOML");
.............
    b2Vec2 *centerlinePoints = new b2Vec2[m_allPointsSize];

    genCenterline(centerlinePoints);
    genLogicalTrackRepresentation(centerlinePoints);
    genPhysicsTrackRepresentation();

    delete[] centerlinePoints;
}

As you may have noticed, I recently started using TOML files for storing config stuff (and actually even some physic shapes like the car body). The reason for this is that I kind of got tired of XML and JSON and found this format to be really nice and human readable. Of course it’s not as fast as binary files but it beats writing an editor :) . Carvatar actually has a modified version of the TOML parser that compiles on windows (small modifications made by me)

I’ll put the TOML file parse code here so you can see why I like it (did not do any data validation :D ):

 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
void CTrack::loadSettingsFromTOML(const char *filename)
{
    std::ifstream ifs(filename);
    toml::Parser parser(ifs);
    toml::Value documentRoot   = parser.parse();
    toml::Value* trackSettings = documentRoot.find("tracksettings");

    m_settings.track_size               = trackSettings->find("track_size")->as<int>();
    m_settings.down_step                = trackSettings->find("down_step")->as<int>();
    m_settings.sector_step              = trackSettings->find("sector_step")->as<int>();
    m_settings.track_width              = trackSettings->find("track_width")->as<int>();
    m_settings.radius_offset_curvature  = trackSettings->find("radius_offset_curvature")->as<int>();
    m_settings.hard_curvature_value     = trackSettings->find("hard_curvature_value")->as<int>();
    m_settings.smooth_iterations        = trackSettings->find("smooth_iterations")->as<int>();

    const toml::Array& radius_curvature             = trackSettings->find("radius_curvature")->as<toml::Array>();
    const toml::Array& hard_curvature_probability   = trackSettings->find("hard_curvature_probability")->as<toml::Array>();
    const toml::Array& physics_wall_size_inner      = trackSettings->find("physics_wall_size_inner")->as<toml::Array>();
    const toml::Array& physics_wall_size_outer      = trackSettings->find("physics_wall_size_outer")->as<toml::Array>();

    m_settings.radius_curvature[0] = radius_curvature.at(0).as<int>();
    m_settings.radius_curvature[1] = radius_curvature.at(1).as<int>();

    m_settings.hard_curvature_probability[0] = hard_curvature_probability.at(0).as<int>();
    m_settings.hard_curvature_probability[1] = hard_curvature_probability.at(1).as<int>();
    m_settings.hard_curvature_probability[2] = hard_curvature_probability.at(2).as<int>();

    m_settings.physics_wall_size_inner[0] = physics_wall_size_inner.at(0).as<int>();
    m_settings.physics_wall_size_inner[1] = physics_wall_size_inner.at(1).as<int>();        

    m_settings.physics_wall_size_outer[0] = physics_wall_size_outer.at(0).as<int>();
    m_settings.physics_wall_size_outer[1] = physics_wall_size_outer.at(1).as<int>();

}
posted at 10:11  ·   ·  AI  procedural generated  racing game  race ai  Carvatar  C++  TOML joy

· This is not your average Footer