Generating a procedural planet/asteroid field

Lately I've been working with a game project where the player flies along a swarm of planetoids, placing bombs, collecting coins and dodging bad asteroids. As it would be quite dull to have a single hand-crafted map for the game, procedural content generation was required. The ultimate goal in map generation would be to create a path for the player to loosely follow. The path should have occasional obstacles but mostly it just contains lots of coins for extra score. Who wouldn't want to get a score as high as possible?

White is the main path, yellow is the obstacle option four. Read more later on.

So we need a path. And not just any path, a naturally looking path that shouldn't zigzag around too wildly. Rather, it should have small, smooth hops from one node to another. And to make the player stay on the path there should be obstacles. In theory there can be obstacles everywhere, just as long as they are not on the path. But note that complete coverage is not a necessity, as long as there is enough obstacles. There can be some open areas that function as alternative routes for the player. But how to create the path?


(To make it easier to follow the images and text: the path starts from the left and continues to the right ad infinitum.)

Option A: MSP

Graphs and point clouds can be transformed into paths. Take a point cloud, apply Delaunay triangulation and then apply minimum spanning tree to eliminate most of the pathways to force the player to follow the path more closely.

So, being bit more specific: Start by generating a cloud of random points. For example take a grid as a base structure and then displace the centroids, and eliminate the points that are too close together.

Apply Delaunay triangulation to create a graph that represents the potential paths the player can follow. This ensures that all the path segments are short and no path intersects with another.

Next, apply minimum spanning tree to the graph. As a result we now have a beautiful, uniformly random path from the beginning to the end, with some dead ends for variance. Optionally some dead ends can be connected to the main path to create loops to function as alternate routes.

Two small samples of option A.

Sure, that should certainly work, but just look at all those complex algorithms! Surely there must be a simpler way to produce results that are just as viable.

Option B: Generate and test

Start with the point cloud from option A. Then build the path segment by segment by looping the following:

Take a bunch of planets(the rightmost and the preceding grid column) and do a circle cast to each. If the cast does not collide to other planets, the player is able to fly along it. From those planets, select a random one as the next node for the path. Optionally the jaggedness of the path can be reduced by adjusting the chances for each planet in relation to the distance and the angle in relation of the last node.

A sample of option B. Every other segment is green or blue.

Pay attention to the fact that this option operates segmentally. The map can be generated on-demand instead of requiring the computation of the whole, potentially large map. In addition to feeling lazy, this is the reason option B was chose for the game.

Obstacles

Now that the base structure of the map is formed one way or the another, it needs to have obstacles to actually make it feel good instead of being just a dull collection of lifeless rocks. There is a few options here, and it would probably be wise to mix several them together for variance. Most of them also benefit from scaling their effect as the map progresses, so that it is easy at the start and gets progressively harder from there.

First options is to follow the path and create polygonal areas that tangent it. You'll also probably want to eliminate smaller polygons that fit inside bigger ones. The areas can then be filled using some kind of unspecified algorithm. Now there are no short-cuts and the map was just enriched by objects that are not just point-like dullnesses.

Second option is to cast rays, once again, to other planets that are on the path(except the next one). It there is a clear path, block it by creating an asteroid to somewhere around the midpoint of that path. At least there are no short-cuts.

Third option is to convert planets further away from the main path to asteroids. As the map progresses the conversion threshold is lowered until at the end only the main path is traversable.

Fourth option is actually a variation of first two. Taking the outermost edge of the polygon and creating an asteroid at the midpoint. This way only the longest of short-cuts is blocked, without polluting the space with too many worthless asteroids blocking even the shortest of paths.

It would also be wise to have some checks here and there to make sure that the main path stays obstacle free, but there is no need to be exhaustive about it. Remember those alternate routes? Trust the player to overcome the blockage. If the obstacle can't be avoided then it's just a challenging feature.

Other refinements

Now that the traversable path is generated, all that is needed is incentives for the player to actually follow it instead of trying to find one on his/her own. Add coin strips to longer paths, then orbiting ones to shorter nodes and finally some special coins to planets outside of the path. Then add some rotating asteroids with surface obstacles and it's actually starting to look like a fineish map! In the end this took about 550 lines of C# code.