The game Backroads Lightning is a game I wrote for the Procedural Death Jam, a game jam which prominently features procedural content. A key goal of procedural content is to generate a new environment each time you play, so that you can't memorize map layouts or enemy placement. The random dungeons of many roguelikes are a good example of procedural content. Another good example are the random maps of Spelunky.
I've written several random dungeon generators in the past so I wanted to use this jam as an opportunity to try and generate something that was specifically NOT a dungeon. Generating a random network of roads seemed like an interesting idea. After trying several methods I hit upon the process detailed here. A lot of details will be glossed over, and you will probably have to learn Graph Theory as you go if you don't already. But even if you don't just looking at a picture for each step will probably give you a good idea of what's going on.
Step 1-Lots of connections
To start with, I generate lot of "way-stations" which are sort of the equivalent of dungeon rooms in a roguelike. These are just specific locations where enemies can spawn or where you might have to pickup moonshine. Each way-station is marked as a dot on the map below.
I need to connect all the way-stations together. So for now I just connect them up using a Delaunay triangulation which makes sure I can get from one way-station to every other way-station and also that no road crosses another road. Writing your own Delaunay triangulation is pretty hard; luckily the guys at S-Hull have already written one that I can use.
Step 2: Spanning Tree
The road network already looks OK, but there are too many connections and loops, making it look more like a maze than a road network. So next I cut down the number of connections between points. I remove as many connections as I can while still making sure you can drive from one way-station to any other way-station. This produces a (not necessarily minimum) Spanning Tree.
Step 3: Oops, need some loops
Now the road network is basically all dead ends, which is also not ideal. What we want is some combination of loops and dead ends. So at this point I add back a few connections (not all of them!) to produce a network that contains both loops and dead ends. By varying the number of connections you add back in, you can roughly control the ratio of dead ends to loops.
Step 4: Curves
Ok, connection-wise that looks pretty good, but all the roads are straight lines leading into awkward intersections. We really want the roads to follow a smooth curve from one location to another. So at this point I grab several connections at once and convert them into an interpolating spline curve. I use an interpolating curve which is smooth but goes through the original points, so that the roads still allow access to the original way-station locations.
One drawback to this step is that sometimes road will now intersect or overlap, which causes nasty hills if the two roads are at different elevations. I wanted to add some code which smoothly merge intersecting roads but ran out of time.
To sum up the process:
- pick N random locations
- make a Delaunay triangulation
- remove connections to produce a spanning tree
- add some connections back to make loops
- convert straight roads into interpolating splines