Our latest blog takes a slightly more scientific turn than usual as we take a look at how we created the algorithm used in Mantis Burn Racing to automatically generate the best racing lines on tracks. This may prove to be quite appealing to those of you with a more, shall we say, technical mind, but wherever your interests lie, we hope you find it in some way interesting!
Thanks to Thang Phung Dinh, one of our talented programmers, for putting this together.
Step 1: Slide up the track
The first step is creating cross section lines along the track (shown above as the green lines). Each of these lines cross the entire available width of the track. The distance (along the track) between those lines is up to you but a value of around 10 meters worked for us. The detail of how you generate these lines depends on how represent your track in your program.
The next step is to create the same number of X nodes equally spaced on each line (shown as red circles in the image above, with X = 4). Choosing X depends on the average track width (the average length of green lines). A good starting value for X is the one that the makes the distance between 2 adjacent nodes on a line is about 0.5 meters.
Step 2: Choosing Segment/Value Function
In the image below, given the car goes from node Prev to node Cur and then to node Next (on 3 consecutive lines along the track ), we need to come up with a function to evaluate how good this small racing line is. Lets call this function: Segment/Value (Prev, Cur, Next), the bigger its value is, the better the path is. This function will be used later to calculate the best racing line.
Segment/Value can take any form as long as it has these properties:
– The smaller A and B (the shorter the car will travel), the bigger Segment/Value is.
– The smaller P (straighter path) is, the bigger Segment/Value is.
One example may be:
Alpha / (A + B) + Beta * Cos (P)
Where Alpha and Beta is the weight you give to the importance of path’s distance and path straightness. If you give distance more weight, your racing line will prioritise shorter route, otherwise if you give angle more weight, your racing line prioritise straighter route.
Step 3: Generate the racing line
What we need to do here is generate the best racing line going through nodes from the first line to the last line, shown as the blue line below:
We will use a method very similar to recursive algorithms to find this path.
For every node, we will calculate this information: Given the car is currently positioned at this node (let’s say Line L node A) and came from a particular node on a previous line (node B on line L-1) then what would be the best possible racing line value for the whole route going from Node B to Node A and all the way to the last line (This is the accumulated values of all Segment/Values along the path). Let’s call this information Route Value Map (RVM).
So one way store RVM for each node as:
RouteValue RVM; // Assume we have 4 nodes on each line, each item on this // array represents a node on previous line.
Where RouteValue is
float m_routeValue; // Best route value provided we came from a particular // node on previous line
Int m_routeNextNode; // The node index on the next line // that gives the best route
Assume that we already have the RVM values for all the nodes on the next line: L + 1, we can calculate this RVM values for nodes on line L. So it is possible to calculate RMV for all nodes if we calculate RVM values for nodes from in the order of last line to first line.
As an example, the pseudo-code below shows how we can use RVM of nodes on Line 7 to calculate RVM for Node 1 on Line 6 (let’s call this node Cur)
For each node Prev on Line 5
For each node Next on Line 7
This Route Value = Segment/Value( Prev to Cur to Nex) + Next ’s
If (This Route Value > Best Route Value So Far)
Best Route Value So Far = This Route Value;
Best Next Node So Far = Next ;
Cur ’s RVM [ Prev ].m_routeValue = Best Route Value So Far;
Cur’ s RVM [ Prev ].m_routeNextNode = Best Next Node So Far;
The pseudo code above works for nodes on all lines except ones on the first and the last line. For the last line, we just fill RMV values with 0. And for the first line, we don’t have a node to come from so the This Route Value is just Next’s RVM.m_routeValue.
Once we have the RMV values for all nodes, constructing the racing line is straightforward. Just choose a starting node on line 0 and follow its RVM’s m_routeNextNode value to choose which node on the next line to go to next.