GRIP, spline dependency

In another in the series of AI articles related to the game GRIP, we will today examine the use of pathways, or splines within the game. Not anything you can see, I'm referring to the invisible splines that bring it all together in realising some pretty core functions without which the game would be nothing.

Example splines on the Canyon track

Jumping right in, the obvious example is how the bots traverse each of the tracks in GRIP and this is largely governed by a series of splines that are laid out by level designers during their production. This is pretty standard fare for racing games, ever since the original Rollcage every racing game that I've worked on has featured these kinds of spline in one form or another and as far as I know, no superior alternative has been developed during all of that time. In GRIP however, we do much more with them than just that.

Splines are not just used for navigation by the bots, but they also provide them with a variety of driving cues as well as a sense of environmental space. They are also similarly used by the Assassin missile for navigation around the tracks in pursuit of vehicles. They are critical in the determination of race position for each vehicle and are also used by the cinematic cameras to deliver those nice, sweeping shots at the end of a race. All of this, from a single set of splines hand-crafted for each track iteratively, over and over again, until the bots are driving like arch-demons, those god-damn Assassin missiles aren't ploughing into the scenery and the cinematic cameras look as slick as can be. It's not sexy work for sure and entails of a lot of raw observation and manual tweaking, but it is satisfying having the control to elevate the quality of the game experience in this way, moreso getting that data tuned so tight that it practically squeaks. The quality of this data means the difference between a shoddy, dumb game, and one that challenges the player to their limit.

In general, the construction of these splines is pretty straightforward. They are laid out around each track describing the routes available to the bots. We try to keep them as simple as possible in order to aid ongoing maintenance - trust me these splines are edited over and over again so the fewer the better. We limit ourselves to having just a single, looped spline that describes the main route around a track - this is the one we use to determine race position for vehicles. Branching from that we then have a number of alternative routes described by non-looped splines which then merge back onto the main spline at some point. They are laid out close to the ground, or driving surface that the route intends the vehicle to be driving upon. It's critical however that they don't intersect any of the scenery if the environmental space data is to be calculated correctly.

Example junction where several branches can be taken

To get to the meat of their use in-game, we'll first take a detailed look at how the bots use these splines to determine where and how to drive. At the start of a race, each bot determines the nearest spline and attaches itself to it. As they drive around they are continually looking at how to navigate ahead. Each spline contains a list of junctions where other splines head off in different directions and these junctions are evaluated by the bots to determine which route to take. This is a semi-random affair with routes having a custom probability of being taken compared to one another, as well as an indication of whether each route is good for collecting pickups or good for high speed. So for example, if a bot has no pickups and is ahead of the player, then they are much more likely to take a route laden with pickups than one that is faster. Similarly, if a bot is lagging behind the player then they are more likely to take the faster routes.

What happens when a vehicle crashes off the track or otherwise deviates away from the spline they are currently following? Trying to follow a spline that is no longer accessible results is pretty poor driving behaviour and it's critical to determine if the current spline is still valid for each bot at very regular intervals without compromising too much CPU time. The sooner we establish the lack of validity for their current spline, the quicker we can have the bot switch to a better spline and correspondingly more intelligent behaviour - there's nothing worse than seeing a bot driving blindly up against a wall like a horny dog trying to follow a spline that is no longer accessible. How we avoid this is down to using the specialist environment space data encoded along the length of each spline so we don't have to resort to doing any expensive ray casts.

Diagnostic rendering showing a spiral of environmental space probes

The environment space data is pre-compiled ahead of time and packaged with the game. It is sampled every ten metres along a spline and is gathered by sending a spiral of 32 ray casts out from those sample points along the spline to cover a full 360 degree arc perpendicular to the spline's direction. For tunnels, caverns or any kind of convex space this gives a really good sense of the space surrounding the spline. For complex, especially concave environments, the sense of space is considerably less accurate but still nonetheless useful and fit for purpose. All we really need to gather from this data at run-time is the amount of space available around spline at a given point along it, and whether a given object is within that space or otherwise occluded from it. This isn't always as accurate as we would like it to be in a perfect world, but it has proved accurate enough for the job in hand.

Splines consist of a number of control points, usually created purely in the pursuit of forming the shape of a spline. At these points we also record extra information that helps the bots to understand the driving environment in that vicinity. For example; how wide the driving area is so they can maneuver effectively, the optimum speed for taking corners without crashing, the minimum speed required for jumps or uphill sections - that kind of thing. The driving hints stored at these points are really what give the bots a solid start in becoming competitive against players and avoiding the worst of driving mistakes.

Moving on now, Assassin missiles similarly use this spline data. They can determine when to slow down a little for sharp corners for example. But more than that, the Assassins also need some additional help. In that, we also store the nearest ground point every 10 metres along the spline specifically for use by Assassin missiles and the cinematic cameras. Both the missiles and the cameras try to keep to a set height above the nearest terrain while following a spline. The splines themselves can have variable height above the terrain you see, often very close to it, far closer than you would like a missile or camera to be travelling. With this nearest terrain data, which incidentally is smoothed to avoid temporary jumps in surface direction, we can easily aim for a set height above the surface.

Example missile spline (in white) next to a vehicle spline that was impossibly tight

Assassin missiles also use the same route data that vehicles do too, trying to take the shortest path between the missile and the intended target. Sometimes though, on fairly rare occasions the splines we setup for vehicle navigation are just too tight or in some other way unsuitable for missile following. On these occasions we graft a special missile spline into the route, which missiles always take when they encounter it in order to avoid the problematic vehicle spline sections. As part of helping the missiles along in difficult situations, at the spline control points we store an indication of whether the missile should attempt terrain height following as normal, or simply stick directly to the spline centre line while maneuvering. Of course we interpolate between these two modes of maneuvering to smooth out the transitions.

Similarly, a little extra data is provided to the cinematic camera system. We examine the splines during the pre-compilation process to identify sections that are suitable for camera tracking. Harsh movements to the camera are generally not desirable as it can be very jarring to the viewer. So we want to avoid sharp surface direction changes, and of course sharp corners so we examine the splines looking for sections that don't exhibit either of these features. From this examination we end up with a list of sections for each spline that are smooth and can be used for cinematic camera tracking which we'll employ at run-time, normally when a game event completes before returning to the main UI.

Race position determination for vehicles can be quite problematic. Even with using a single, looped spline against which we measure race progress it is still sometimes difficult to ascertain. For example, how do you determine the closest point on a spline for a given point in space? Like, where is the closest part of a spline to a specific vehicle? Mathematically, this is a nightmare and as far as I know there is no solid, non-multi-sample solution - certainly not for the kind of complex-shaped splines we're using in GRIP. For our game we had to invent a solution whereby we iterate along the length of a spline, comparing distances between each point we test and the point in space we're interested in. Ideally you would want to do this with a small iteration distance to get an accurate result, but obviously this would be an enormous waste of CPU resources making hundreds or even thousands of comparisons so we take a different approach. We start by initially taking a large iteration step and identify the closest point on the spline at that scale. Then we narrow down the comparison to just the space surrounding that closest point and the two points either side of it on the spline and halve the iteration distance. We then run the comparisons again over that shorter distance to refine the closest point further. We do that repeatedly, maybe five times I think to get the required accuracy, making something on the order of 20 comparisons to find a solution.

This is not without error though it has to be said, and where splines loop back on themselves or have otherwise complex shapes, closest point determination can be inaccurate where we initially hook onto the wrong part of the spline during the initial pass with a large iteration step, and then refine the closest point in the wrong area completely missing the correct solution lying elsewhere on the spline. To solve this, when a vehicle first enters a track we use a very small iteration distance during the initial pass to hook the correct area. This takes a lot longer of course but at the start of a game event this doesn't matter, it's just during the event that we can't continue to take that approach. Instead, during the game we know the closest point on the spline that the vehicle was on during the previous time frame and we can use that knowledge in the calculation for the current time frame. We take that closest point, factor in how much the vehicle has moved in space since the last point, and then just examine a small section of spline in the vicinity of the area traversed. Because it's just a small area we can use a small iteration distance too in order to maximise the accuracy of race position determination. It's the distance along the spline you see that determines lap position, and combined with the number of laps completed the ultimate race position.

Which part of this spline is the vehicle (centre image) closest to? Possibly not the one you would hope.

But there are other times where we have to be equally careful in selecting spline areas for examination, like when you've lost sight of the current spline from your vehicle that has maybe crashed into a different part of the track or is occluded from it for some less dramatic reason - an inconvenient rock for example. When selecting a new spline to follow, we have to ensure that the closest point we select on that new spline is related to the last known lap position around the track for the vehicle. For instance, it would be easy to hook onto the new spline in the wrong place, maybe if it had two straights running parallel to each other in close proximity but in opposite directions. You might actually be closer to the wrong section of track here and identify the wrong closest point on the spline. Instead we have to always have in mind the closest relevant point on the spline, which sometimes may not be the absolute closest point. And yes, Chris does create these kinds of scenarios with U turns and crossovers for me to handle on many occasions, thanks buddy.

So we've taken a fairly broad overview of our use of splines here but already this article has grown to quite a size and we'll wrap it up around here. I think though we've nevertheless illustrated quite well just how pivotal these splines are to the game and how getting the data tuned well, along with being careful how we use splines algorithmically is incredibly important. Splines in their essence don't really solve any significant problems - they're just a basic construct on which you can build. You have to work hard to enhance and optimise splines, and carefully tailor your algorithms to your particular game's requirements in order to get the most from them. And in GRIP, I think we've just about achieved that.

[Posted 03/19/2020]