One of the most popular genres of computer game, the racing game, has players controlling cars at break-neck speeds around a racing track…….
Let’s think about how computer games can create realistic racing tracks. The problem of getting an object like a car to follow a path or track is important, and starts with the idea of a waypoint.
Waypoints are just the points (or, more accurately, the position vectors) that we would like our object to move through. For example, we could have a set of waypoints that look like this:
Our object starts at the first waypoint (let’s say the one on the left). It moves towards the second waypoint. When it reaches the second waypoint, it then switches its target to the third waypoint, and so on until it reaches the final waypoint.
The challenge is to make the object move in a smooth curve between the waypoints, so it looks like the natural movement of a car. We don’t usually want jerky motion where the car changes direction instantly from one waypoint to another.
The Maths of a Smooth Curve
So from the point of view of maths, our problem has been reduced to finding a way to create a smooth curve which passes through all of the waypoints. Once we have created the curve, our object can then be programmed to move along the curve.
One of the simplest curves in maths is a quadratic curve…..quadratic just means that there is a squared power of x in the equation.
We will try to use quadratic equations to make a smooth curve between our waypoints.
Actually, the way to do this has already been worked out! A brilliant French engineer, Pierre Bezier, calculated it all while working for Renault, the car manufacturer. Bezier wanted a way to calculate smooth curves for the body of Renault cars, and so devised curves which are now called Bezier curves.
In particular, Bezier used three points (or position vectors) to describe a smooth quadratic curve, called the quadratic Bezier curve. If the three points (position vectors) are A, B, and C, then the equation of a point, P, on the quadratic Bezier curve is:
P = (1 - t) [ (1 - t)A + tB ] + t[ (1 - t)B + t C ], 0 <= t <= 1
The variable t is called a parameter. The value t = 0 corresponds to one end of the curve, at the point A. When t = 1 we will be located at the other end of the curve, point C. If t = 0.5 we will be half way along the curve.
The equation might look difficult, but if you look at it carefully you’ll see that it’s actually quite straightforward. The term in the form (1 – t) x First Point + t x Second Point, in the inner brackets, appears twice, and then we just have the multipliers (1 – t) and t before each term.
Let’s explore the equation applied to three points: A = (1, 0), B = (0, 0), and C = (0, 1). This Excel spreadsheet calculates the x and y coordinates of point P for various values of t, and then plots the graph of the x and y values.
This is the graph that the spreadsheet produces:
When t = 0, our object will be at the point (1, 0). When t = 1, it will be at (0, 1), and for values of t between 0 and 1 the object will move smoothly along the curve between the end-points.
So we now have a way to create a smooth curve between three points.
How do we apply this idea to a racing track through a series of waypoints?
Let’s first divide the waypoints into groups of three, and then create a quadratic Bezier curve between each group of three waypoints. There might be slight differences in curvature from one curve to another, but this shouldn’t be too much of a problem provided the waypoints are reasonably smoothly spaced.
For example:
Waypoint numbers 1, 2, 3: first quadratic Bezier curve between these points
Waypoint numbers 3, 4, 5: second quadratic Bezier curve between these points
Waypoint numbers 5, 6, 7: third quadratic Bezier curve between these points
and so on.
Here is an example with 11 waypoints in total:
(Note that the Bezier curve doesn’t pass through every second waypoint. These waypoints act to set the curvature of a particular quadratic Bezier curve). We’ve created the curve in the two dimensions, on a flat plane, but the maths also works in three dimensions – vectors can be 3D just as easily as 2D.
The Maths of a Race Track
We’ve successfully created a smooth curve, but at the moment it’s just a line with no width. We need to create now a smooth track, which follows the curve and has sufficient width to allow a car to drive along it.
There are a number of ways that we can do this in a computer game. In general, in a complicated situation with waypoints in three dimensions, one of the best ways to create a race track is to use some maths called a vector product. However, in two dimensions, it can be much more straightforward.
Let’s start with two adjacent points on the quadratic Bezier curve. The first, point B, is where our car is currently, and the second, point C, the next point where the car is moving towards. So the line from B to C is the line along the centre of the racing track. We want to create additional points to the left and right of the car which will define the left and right hand sides of the racing track.
If V is the vector between the two points on the quadratic Bezier curve, which has components Vx and Vy in the x and y directions, then the vector to the right hand side of the track, at the position marked R, will be:
(Vy, -Vx)
(we might need to multiply this vector by some value related to the width of the track).
And to the left hand side of the track will be
(-Vy, Vx)
If we do this for each point on the quadratic Bezier curve then we create a track with a set of points that looks like this:
We now follow this process along the whole set of waypoints, and can join the points to create a racing track that looks like this:
Removing the waypoint and Bezier markers gives us just the track:
Although there are some small irregularities in the smoothness of the track, by using slightly more advanced maths we could smooth these out. For example, Bezier also devised cubic Bezier curves, which could be used a create a smoother track. We could also use moving averages of the points along the track to smooth the path.
Let’s Go Racing!
Now that we have create racing tracks, we can use a 3D Game Engine like Unity to race a car model along the track, complete with a terrain as a backdrop, and a stylish car for us to drive:
And here is another track created using quadratic Bezier curves:
If you would like to race a choice of ten different funky cars along five different tracks then check out our app, available on itch.io!
Comments