Space Racers Breakdown Part 2: Node Navigation
Part 1: Map Format
So as promised I shall attempt to explain some of the techniques used in Space Racer. This post will be about the node system I used, which performs three main tasks.
The first is to stop cheating by short cutting. This is pretty easy to do using the collision detection of the Tiled map. Nodes themselves are objects created in Tiled, and parsed via the tmx map loader class. Using the MapObject::Contains() function it is trivial to detect which node a vehicle has passed through, and update the vehicle's currentNode property with the ID of the last node the vehicle touched. If a vehicle then comes in contact with a new node whose ID is not one more or one less than the currentNode property the vehicle must have taken a shortcut, and therefore gets reset.
The second task of the node system is a bit more complex. When I was researching the game I found little to no information on how to measure just how far around the track a vehicle was - and therefore no way to sort player positions. The solution I came up with is as follows: Each node has a position in world coordinates, which is derived from the centre of the map object representing the node. This allows a one dimensional chain to be created around the track from the list of positions. The complex part is calculating just how far along this one dimensional path a vehicle is, when the vehicle obviously has free range of movement in two dimensions. Just measuring the distance between a node and a vehicle is not enough. For example:
Vehicle B is further from the current node, but because it's not taking an as direct route Vehicle A is actually in the lead. To fix this I use a bit of vector maths, along with some pre-processing of the node data. When the map is loaded the nodes are parsed into a series of objects which look like this:
struct Node
{
int ID;
vec2 position;
vec2 nextUnit;
float nextMagnitude;
};
Besides the ID and position of the node in world coordinates I also store a unit vector which points to the next node, and its magnitude - which is the distance between the node and the next one. Storing the vector in its component form let me use the dot product of the unit vector and the relative vehicle vector to find the vehicle's magnitude were it to be traveling along the vector between the two nodes. This sounds a bit wordy, so here's another diagram:
D is the distance we are ultimately trying to find: if we calculate this for each vehicle then it is simple to find which is furthest along the vector between the nodes, and therefore which race position the vehicle is in. To calculate D we first find rv, the relative vector of the vehicle position to the node position
vec2 rv = vehiclePosition - nodePosition;
D is then the result of the dot product of the *unit* vector and rv. This is why it is important to store the unit vector in the node properties. Normalising a vector is also relatively computationally heavy because of the square root, so as it is a constant for each node it makes sense to just calculate it once and store it. We now end up with
float D = dot(node.nextUnit, rv);
This solves part of the problem, but of course not all vehicles are going to be between the same two nodes. It also doesn't provide the total distance traveled around the track. This is solved by using the nextMagnitude property of the node. Each vehicle has a cumulative distance property, so each time a vehicle reaches a new node not only is the vehicle's currentNode property (the ID of the node) updated, nextMagnitude value is added to vehicle.currentDistance. Again, calculating the length of a vector is computationally expensive, so it makes sense to calculate it once and then store it. The total distance is then solved as
float total = vehicle.currentDistance + D;
Now we know the total distance traveled by each vehicle, and a simple std::sort() provides the vehicle's race position. Here's a shot of the debug view of this technique in action (the orange numbers are the total distance):
The final task of the node system is to provide navigation data to the AI used for computer controlled vehicles. The vehicle class itself provides an interface which allows control input from various sources, such as keyboard, controller or via the network. The AI class creates its own control output which is then fed to the vehicle class through this interface. Each AI has a destination position calculated as
vec2 destination = currentNode.position + currentNode.nextUnit * currentNode.nextMagnitude;
The AI then steers the vehicle until it points (approximately) at the destination and accelerates towards it. I say approximately because the accuracy is deliberately varied between AI objects to stop them being too perfect, and too hard to race against. Each AI also measures its distance between its current location and the destination, and will start to brake as it gets closer. Again the distance before the AI starts to brake is varied, although not only between AI objects, but also over the course of the race. This is done to help try and reduce predictability of AI players, and also allows for varying grades of AI 'competence' - how difficult to beat the AI player is.
That pretty much sums up the node system of Space Racers. In the next post I'll try to describe how the vehicle physics work. As always questions / comments are welcome.
Part 3: Vehicle Handling
So as promised I shall attempt to explain some of the techniques used in Space Racer. This post will be about the node system I used, which performs three main tasks.
The first is to stop cheating by short cutting. This is pretty easy to do using the collision detection of the Tiled map. Nodes themselves are objects created in Tiled, and parsed via the tmx map loader class. Using the MapObject::Contains() function it is trivial to detect which node a vehicle has passed through, and update the vehicle's currentNode property with the ID of the last node the vehicle touched. If a vehicle then comes in contact with a new node whose ID is not one more or one less than the currentNode property the vehicle must have taken a shortcut, and therefore gets reset.
The second task of the node system is a bit more complex. When I was researching the game I found little to no information on how to measure just how far around the track a vehicle was - and therefore no way to sort player positions. The solution I came up with is as follows: Each node has a position in world coordinates, which is derived from the centre of the map object representing the node. This allows a one dimensional chain to be created around the track from the list of positions. The complex part is calculating just how far along this one dimensional path a vehicle is, when the vehicle obviously has free range of movement in two dimensions. Just measuring the distance between a node and a vehicle is not enough. For example:
struct Node
{
int ID;
vec2 position;
vec2 nextUnit;
float nextMagnitude;
};
Besides the ID and position of the node in world coordinates I also store a unit vector which points to the next node, and its magnitude - which is the distance between the node and the next one. Storing the vector in its component form let me use the dot product of the unit vector and the relative vehicle vector to find the vehicle's magnitude were it to be traveling along the vector between the two nodes. This sounds a bit wordy, so here's another diagram:
vec2 rv = vehiclePosition - nodePosition;
D is then the result of the dot product of the *unit* vector and rv. This is why it is important to store the unit vector in the node properties. Normalising a vector is also relatively computationally heavy because of the square root, so as it is a constant for each node it makes sense to just calculate it once and store it. We now end up with
float D = dot(node.nextUnit, rv);
This solves part of the problem, but of course not all vehicles are going to be between the same two nodes. It also doesn't provide the total distance traveled around the track. This is solved by using the nextMagnitude property of the node. Each vehicle has a cumulative distance property, so each time a vehicle reaches a new node not only is the vehicle's currentNode property (the ID of the node) updated, nextMagnitude value is added to vehicle.currentDistance. Again, calculating the length of a vector is computationally expensive, so it makes sense to calculate it once and then store it. The total distance is then solved as
float total = vehicle.currentDistance + D;
Now we know the total distance traveled by each vehicle, and a simple std::sort() provides the vehicle's race position. Here's a shot of the debug view of this technique in action (the orange numbers are the total distance):
The final task of the node system is to provide navigation data to the AI used for computer controlled vehicles. The vehicle class itself provides an interface which allows control input from various sources, such as keyboard, controller or via the network. The AI class creates its own control output which is then fed to the vehicle class through this interface. Each AI has a destination position calculated as
vec2 destination = currentNode.position + currentNode.nextUnit * currentNode.nextMagnitude;
The AI then steers the vehicle until it points (approximately) at the destination and accelerates towards it. I say approximately because the accuracy is deliberately varied between AI objects to stop them being too perfect, and too hard to race against. Each AI also measures its distance between its current location and the destination, and will start to brake as it gets closer. Again the distance before the AI starts to brake is varied, although not only between AI objects, but also over the course of the race. This is done to help try and reduce predictability of AI players, and also allows for varying grades of AI 'competence' - how difficult to beat the AI player is.
That pretty much sums up the node system of Space Racers. In the next post I'll try to describe how the vehicle physics work. As always questions / comments are welcome.
Part 3: Vehicle Handling
Comments
Post a Comment