I was posting some screenshots on Twitter a while back about my work on the random track generation in the untitled car game and a few people asked me how I was doing it. It's nothing super fancy but I thought I'd finally write about what I did!
The car game has completely randomized tracks. Every time you load a race it creates a whole new layout based on some basic inputs.
My basic goals for the track generation were:
- Different maps every time
- Tracks must be a full loop (starting point and end point are the same)
- Intersections where the track crosses itself.
- Size control. I wanted to be able to say 'make a big map' or 'make a small map' etc.
- Adding new track parts to the generation should be easy
With all of this in mind I tried to come up with the simplest thing possible to accomplish this. My first idea (seen right) was to just make a bunch of randomly-shaped squares that connect at the corners... but I didn't like having each 'loop' be a boring box shape.
I went through a few other ideas that I ended up ditching before coming up with something that I was happy with and that fit all my criteria. It ended up being much simpler than some of my more complicated initial ideas.
The tracks right now are all built with a set of these basic shapes on the left. I have 4 corner pieces, 2 straight pieces, 4 starting lines (1 for each direction) and two intersections. I chose to keep each rotation of the same shape of tile separate so I could have more control over the placement of objects onto them that might block the camera if they are positioned oddly. By keeping them separated I can place tall buildings or trees on the far side of the track and not worry about them rotating in front of the camera. The game uses a fixed isometric/orthographic camera so this would have been an issue.
Every tile is a prefab in Unity and I use a tweaked tagging system I initially created for Moon Hunters to tag all of the pieces. The tags tell the generator what they are (tile), what shape they are (straight, curve, intersection), and what directions they connect to other tiles (up, down, left or right).
The way the taging system works, at runtime, when I need a specific piece I can grab a list of matching tiles by simply calling TagTool.GrabObjects("tile straight left right speedway") and it will return to me any tiles where those tags match. Then I just select a random one from the list and place it on the grid. (Note: The 'speedway' tag is there to say that it's for the speedway level. On a swamp level I would use 'swamp' instead to get different prefabs that match them levels theme).
That's great but how do you know where to put them?
So yeah, after ditching a few different generation ideas I ended up using something pretty simple. Using all the stuff above, what my generator basically does is builds a list of spots on a grid and lays down track as it goes.
I build a grid that has the width and height given and just choose a random spot on the map to start the track (Spot 1 on the left here). Then I begin a loop of the following steps:
- Find another random spot.
- Use A* pathfinding to make sure we can make it there.
- Temporarily add the new section of the track but store it in-case we need to remove it later.
- Make sure there is a legal pathfinding path from this new spot back to the starting position. I never add a new point unless it's possible to complete the track from this new point.
- If everything checks out, go back at step #1 until we've created the number of nodes we want. If anything has gone wrong, back up a step and then go directly back to the starting line.
Once we've created X number of nodes (given at the start) we find a route back to the starting position and finish the track.
As it builds the paths it also stores the type of tile it's using. So it tells the path that it's a straight, or a curve and gives which directions each piece has a connecting neighbour (up, down, left or right) so that later on it knows how to choose the correct tile prefab for each position.
The above method works great but the A* I wrote at first would never choose a path that looped back over itself (because it would mark parts of the track as 'unpassable') so I had to find a solution for intersections.
What I ended up doing was changing the A* so that it would cross over straight parts of the track (which I had already tagged as 'straight' for my prefab/tag system) as long as they were perpendicular to the direction of the new path and there was an empty space somewhere on the other side (it can cross several straight paths in a row if it's a legal path).
So then I ended up with nice looping paths with interesting shapes!
If ever the system tries to draw any path to the next node and it fails for any reason, it instead backs up one node and draws a path back to the starting line. So I always end up with a full loop and never a dead-end in a corner of the grid.
Once the whole track is built I have to find a good spot for the starting line. Since it's possible for Spot #1 to be a curve, all I do it move along the path I made until I find a straight, and then add the tag 'startingline' to it and also give it the direction the track is going so it knows which direction to face the cars. When the tiles are generated it grabs a starting line instead of the normal straight piece automatically.
So hopefully this was all clear enough to understand. At the basic level it's just drawing a line within a given area and making sure it always has a path back to the start to form a full loop. It stores a bunch of information in the form of some tags for each tile as it goes along and when it's ready, it uses the tags to grab random parts that match the tags.
This means I can make 'straight' pieces that have jumps, or have obstacles or any other variation I want and all I have to do is tag them properly and they will be added to the track generation automatically.
I had a lot of work left to do adding variations and themes and obstacles now! But the basics are all in and working quite well now.
If anyone actually got this far and has any questions feel free to tweet at me or leave a comment.