Hello!
Recently I've been busy working on procedural generation for levels, which is something I didn't originally plan for but started to look more attainable as time went on. Much like the previous work I did on path finding, there are some difficulties that come with doing this kind of thing for a free-form environment and not one that's nice and grid based, which I'll talk about more below. Even though I'm still planning to hand design a lot of the levels, this will really help to add some extra choice for players, and even open up the possibility for an endless mode once the main game is finished.

Quick note on the videos in this post: to be able to show the generation slowed down like that I hacked some stuff together (which I explain at the bottom of this post). In the actual game this generation happens in milliseconds.

If you like what you see here, please take a look at Deep Space Exploitation on Steam and perhaps wishlist it! :)

Deciding on Proc-Gen
Originally I only planned on using procedural generation for the textures of the asteroids and not the levels themselves. My idea was that since the game isn't going to be infinitely long, and procedural generation is hard to actually make good and interesting, I could hand design each level instead and reap the benefits of a human touch (like placing resources specifically to trick players or give them a huge payoff). I had a huge love of procedural generation when I first started programming, and made lots of little experiments but also wasted a lot of time trying to get the results just right when I could have been putting more effort into other things. So this was partly influenced by me not wanting to get stuck with a task I wasn't sure I could actually pull off.

Now though, decent procedural generation started to seem more attainable. After working on the game all this time I felt I had a much better understanding of what worked and what didn't for levels, and how I could have that pieced together randomly. This is partly confidence from having hand-built a lot of levels, and partly from having more tools available to use for this (I say tools, but I mean clever code for interacting with the physical shapes of things).

I decided to give myself one week (which turned into one and a half after other commitments) to have a serious go at it, so what you're seeing here is the result of that. I'm quite pleased with the result, and I think it can only get better with tweaks and added features.

Step 0 - Parameterisation
The generation is actually quite heavily parameterised, with me specifying exactly how many asteroids of each size and type, how many resources of each type, what destruction to apply, and finally what other entities to place. Because of this, I'm a little reluctant to call this "procedural generation" since it's more just clever placement of things. When I think of procedural generation I think of the huge worlds of games like Dwarf Fortress. But this approach works well for me because I do want to really specify what goes into a level for the purpose of balance and some form of predictability.

Step 1 - Asteroids
The first step is the placement of asteroids, since they're the largest objects on each level and everything revolves around them. There are four different sizes of asteroids (Large, Medium, Small, and Tiny) and currently three different types (Purple, Red, and White), with parameterisation allowing to specify exactly how many of each we want. There are also asteroid presets, which are hand designed placements of asteroids, with each asteroid shape having roughly four presets to choose from.

Very roughly, this is the process for placing the asteroids:
1. Select the largest asteroid size available
2. Select an available asteroid type for this size
3. Find a random place for this asteroid with some additional padding around it
4. Decide whether we will use a preset
    4.1. Find all presets which we have available asteroids for
    4.2. Place a preset which doesn't intersect with other asteroids
5. Decide the total number of asteroids in this cluster
6. Place asteroids in this cluster until we reach the total number
    6.1 Choose a random asteroid in this cluster
    6.2 Choose a random size smaller than this asteroid that we still have availability for
    6.3 Place a new asteroid of this size next to the current asteroid
    6.4 Repeat until we've placed all asteroids in this cluster
7. Repeat until we've placed all asteroids

I find this strikes a decent balance between being random, interesting, fun to fly around, and also semi-natural looking. I'm thinking to experiment with broader rules, such as making everything more scattered or condensed.

Step 2 - Destruction
Next there's the chance for some destruction to be added, so that the level looks like someone else might have been here before and done some mining. This is done before placing any resources or entities so that we don't place anything exactly where we make the destruction and make it look like someone excavated some resources but then decided not to take them. The destruction is also physically simulated so that asteroids look like they've actually been moved by what's been damaging them, and having resources/entities placed while that is happening can make things look a little too random.

At the moment there are two types of destruction for randomisation; explosive charges, and bullet impacts. The destruction for explosive charges is positioned on the circumference of Large or Medium asteroids, since placing them on smaller ones can completely obliterate them, making it pointless to even place them. And the destruction for bullet impacts are positioned starting from an empty point in space and then casting rays out in a fan to see where bullets could impact, and then creating small destructions for those positions. After each destruction there's a random chance to place some debris associated with it, such as shrapnel from explosive charges, or un-detonated bullets from bullet impacts.

Step 3 - Entities
These are the different entities that we might want in a level, like the scrap processor or random pieces of scrap lying around. I plan to add individual rules for each of these so that I can have specific results, instead of trying to come up with one master rule for everything. So if I want one level to have a container that's always empty, I might specify rule CONTAINER_EMPTY in the parameters, or if I want a later level to have a container with some good loot in I might specify rule CONTAINER_LOOT_3. 

Step 4 - Resources
And finally there are the resources, which are parameterised by type (Blue, Green, or Red), quantity, and the range of depths they can be placed at. Currently, there are rules stating which asteroid types a resource can be placed on (Blue crystals only on purple asteroids, for example), and for each asteroid shape I pre-compute the resource placement positions and their depths, so when it comes to placing resources we do the following:

1. Choose a resource to place
2. Get all asteroids this resource can be placed on
3. Get all placement positions for the given depth range for these asteroids
4. Choose a placement position out of these positions that doesn't overlap with an existing resource
5. Place the resource there
6. Repeat until all resources are placed

This is fairly simple but allows for good distribution of resources in the level. I do want to improve this by forcing some clusters of resources, or giving a larger weighted range of depths, so you can specify that a resource could be placed at depth 1, but it's much more likely to be placed at depths 4 to 6.

Hacking these Video together
I wanted to show videos of the generation happening in somewhat slow motion, so you can see what's going on. In the actual game this generation happens very quickly (Under 100ms in debug, which makes me think I have a lot more room if I want to use more complicated logic) so I needed to slow it down and also show it happening in real time while the level is running. 

First I tried throwing it on a separate thread and locking between updates so that the main thread and the generation thread weren't fighting for the same resources, but even that didn't work because of some restrictions to using graphics components off of the main thread (I generate each asteroid's texture as it's created).

So what I ended up doing is turning each method in the level generation into a C# Generator Method, which basically means that execution can pause and return at specific points. With this I can do everything on a single thread and wait for a timer to elapse between each level generation step or placement. Fun!

What's Next?
Now that I have this working I'm able to very easily add more "filler" levels between the more interested hand designed levels. It also means I can hand design more levels as whatever the procedural generation outputs is completely editable using my makeshift level editor, so if I see it generating something that I know could be better, I can do a few manual tweaks and voila.

This also sets the game up well for a potential endless mode after release. Though I won't go as far as to promise this, because I have no idea what the state of things will be once I actually get there.

If you've got to this point, thank you so much for reading, and I hope you found this all even slightly interesting. If you did, be sure to check out Deep Space Exploitation on Steam!