3D Pathfinding: Thoughts

3D Pathfinding: Thoughts

For one of my university assignments I’m working in a group to develop a racing game, taking inspiration from Mario Kart. I’ve come to realise that AI (specifically, staying in the centre of the track and/or getting the width of the track) is pretty important for a lot of stuff in the game:

  • Items (red shells, blue shells, etc. all run along the centre of the track until it homes into the target)
  • Computer-controlled players travel along this centre too, but with a variance controlled by the width of the track

Over the last couple of weeks I’ve thought of a number of different ways this could be achieved, such as allowing developers to draw the centre of the track in a level editor and manually plotting the centre of the track via taking coordinate values from in-game runs around the track. None have been ideal as it adds extra steps to the development process.

However I think I’ve thought of a way to effectively solve this problem and for movement to be extremely accurate too, all without any manual plotting of the track by anyone.

How?

The problem is that the track is one big 3D object with holes, this means that it’s not as simple as “get the closest bit and measure it”. One of my original ideas was to get the nearest edge of the track to the object and then get the width of the track at that point as set by the developer- one I initially dismissed because it required manual intervention.

However, I think this idea does have merit but using a slightly different version of it: get the nearest edge of the track to the player, and then get the next nearest edge in the opposite direction. That’ll get the two edges (using a raycast, it’ll need to do a raycast for every x units away from each side of the player until it does not hit anything) and can be used to get the centre of the track at a given point.

These points can then be stored within a file and then used when required- I pondered the possibility of simply doing it live however this would be inefficient as many objects will require the exact same calculations. It’s better to do it once and then read-back (because the track will not change in the GM version of the game, and even if it changes during development the model can be re-trained).
Alternatively the model could be trained when the track is loading as part of the loading process for that course.

Obviously the above only works for tracks that do not have a bottom (aka, are in the sky). Tracks that are on the ground will have barriers on either side of the track to prevent the player from driving off it, even “Moo Moo Farm” has small hills designed to slow down the player if they venture off course.

I think these barriers can be used to our advantage too: do another raycast but only on the X and Z axis (not Y) from the player’s position, and then do yet another raycast from the returned position- the two returned positions will be the left and right limits of the track.

The above raycast method could also be used as part of the pathfinding system to try and avoid objects.

Potential issues + solutions

What would a split in the path look like to the system?

A path split to the system would result in identical distance values resulting from the split path (assuming the split starts in the dead centre).
This means that we need to deal with identical values- in this case it would probably be best to randomly decide which value to go with (as although both values are identical, their associated positions would be different and so would result in different paths).

But wouldn’t the object just fall off the track in the centre of that split?

Yes, but not if we take the object position to be x distance in front of the object itself. This could be modified automatically for different types of object (i.e. blue shells have a snappier response than red shells, and so x for blue shells will be smaller than the x for red shells).

This should prevent the object from flying off the track in the case of a branch in the track, and in the case of corners would change how quickly the object changes direction (with a larger x value, the object should arc through corners rather than do a straight 90-degree change).

How does this help knowing which position in the race the player is in?

There will only be a certain number of points plotted by the model for a given track, so we can just take the current point and divide it by the total points to get the percentage (rp = p/tp). It would be important to take into account the current lap for the player in these calculations (it wouldn’t be good if the player was winning the race, only to go into the next lap for them to fall into last place because the calculations didn’t take this into account).

Why are points only put into the centre of the track?

As above the centre of the track is the most used for objects, as well as to put the player back onto the track if they fall off it. For AI-controlled opponents, it would be a good idea to program some variance in this so they can move around on either side of this centre line (scalextric-style cars on “tracks” in computer games is something that we can do better on).
Object detection and avoidance would help add to this too (as above, this can be done via raycasts on the X and Z axis), such as avoiding other players.

 

No Comments

Add your comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.