One of the most important mechanics of Roche Fusion is the procedurally generated gameplay. All the enemies you see are generated by a complex algorithm that is designed to construct games that are fair and varied. While generating a random number is trivial, the combination of the amount of degrees of freedom on one side and the constraints on the other makes this process a lot more complicated.
Let's try to get an idea of the scale of the problem first. Right now we have about a dozen of different enemies. In the final game, there will probably be a few dozen. Each enemy has different slots for equipment, let us estimate three on average. Assuming around ten different enemy weapons and other equipment, this already results in a thousand variations for each enemy, though bosses with the double amount of equipment slots already have a million. Now also consider the large amount of ways to spawn and move these enemies, throw in an additional time factor and it becomes pretty obvious that we have near endless possibilities with a relatively small set of enemies and equipment to begin with.
To solve this, we take a hierarchical approach to the problem. Instead of having one big mastermind, we make the mastermind even smarter by making him hire some minions. We split every spawning option into its parameters and choose these parameters one by one. Every parameter is chosen in such a way that its parameter space is small enough to make a choice from. Of course we have to deal with the fact that not every combination of parameters works. Hence we will look for a senseful order in which we choose the parameters, which will allow us to limit the parameter spaces of unfixed parameters to those which work with the already fixed ones.
The National Bank of Space
Apart from handling the large amount of parameters, we also have to make sure that the game's difficulty is also predictable to some extent and that we can control this difficulty over time. We solve this by introducing the National Bank of Space - or the more technical term: a credit provider. A common method to regulate difficulty is to keep track of a number of credits that increases over time. The actual generator - our mastermind - can then spend these credits on events, which all have a certain cost. By making sure the cost and difficulty of an event are proportional to each other, a system is created of which the difficulty can be easily regulated by the credit income.
This generation method works particularly well in applications where the events happen on fixed time intervals. The first iteration of the current gameplay generator made use of this system by working with random time intervals. While the generated events indeed became more difficult over time, there was one essential problem to this algorithm. In a typical game we want easier and harder events to mix up. One time you maybe get a lot of small enemies thrown at you and sometimes the generator just wants to spend a large amount of credits to throw a big guy at you. In the current system, the generator would have to save up enough credits to afford this, which would result in a long pause before harder events. Long story short: we fired him.
Intuitively, this big pause should happen after such a big event has taken place. So ignoring the lessons that can be learned from the economic crisis, the new mastermind we hired - well, programmed - decided to start working with a debt-based credit system. Every time the generator reaches a positive credit balance, it buys something new, which will result in a negative credit balance. It will take some time to repay the debt that has been caused by the last purchase, which is proportional with the cost and thus the difficulty of the event. After fiddling with the numbers for a few hours, the rate at which enemies spawn should be roughly the rate a player can handle at a certain point in the game.
Event Consultancy Group
The first parameter for our event generation is now easily deduced: we choose a random difficulty for the next event that fits with the current gamestate (i.e. events earlier in the game generally have a lower cost than those that occur later).
We also have a large set of predefined event generators: a group of minions that we will call the Event Consulting Group. Event generators can be as abstract as we wish, but what is important to know is that every event generator has a certain difficulty window and it can guarentee that it can perform an event for you for every difficulty from that window you give to it. (Well, it is actually a bit more important than that, but let's just ignore that for now.) So after he chose a difficulty for the next event, the mastermind selects a minion that fits the difficulty and let it do the rest.
Drone Manufacturing Inc.
The way an event generator handles the generation step can be different per generator. Eventually it wants to select some enemies to spawn and that is where we pick up the process again. Every enemy type has certain base stats, including a base cost. Every enemy type can also specify the minimum and maximum cost the applied equipment should have. Together this creates a window of costs for each enemy in which we can vary by applying different equipment to the enemy. Just as with the events, the event generator can look for an enemy type that fits the cost the generator wants to spend on it. For each enemy type we introduce an associated generator (yay, more minions!) that takes the cost and spits out an enemy blueprint.
Every enemy type has a few slots in which it can fit equipment (right now these slots are limited to weapons only). As there are still a lot of variations possible, we cheat a bit and divide all the credits we can spend on equipment over these slots randomly. Using a simple optimisation algorithm we try to find some fitting equipment for every slot. We also add a little bit of random perturbation here, to increase the amount of variation in the enemy loadouts.
Because each equipment slot introduces a deviation from the goal cost, we might end up with something that is quite far off the desired cost. While the effects might seem small at first, they could have a big impact on the gameplay. We introduced a local search algorithm (for those interested: a variant of simulated annealing is used here) to optimise the difference between total equipment value and the desired equipment value. Basically we select a random other piece of equipment and try replacing the equipment in one slot with it and check whether that brings us closer to the desired value. We only try this a few times (currently about ten times), but this already greatly improves the predictability of the enemy value.
After this process, we have enemies that can be plugged into the event which in turn can be plugged into the game. This whole chain of events happens every time the generator decides to perform a new event. Together this algorithm produces very varied gameplay, while keeping very close to the difficulty we want the game to have.
But wait, there's more!
While a fairly detailed overview of the generation algorithm is given above, this article is far from complete. There are many small tweaks in the process that improve it and the game also contains several special cases for some events or enemy types. It also incorporates code to prevent "boring bits" as much as possible and it corrects for update stages and boss battles as well.
The sum of the parts...
We started out with a huge set of things we can choose from and as you all know: taking decisions is never easy. By adding a structure to all these options and splitting it in a nice hierarchy however, we are able to turn it into a system that contains of relatively simple parts. Instead of building a random event from scratch, we first decide its difficulty, its nature, its enemy type and finally the final form of the enemy. This enemy blueprint is handed back to the event generator, which combines with its own blueprint to create a new event. What can I say, it's almost like magic.