I recently participated in the CIG 2010 Mario level generation competition. My submission utilizes a multi-pass approach to level generation in which the system iterates through the level several times, placing different types of objects during each pass. During each pass through the level, a subset of each object type has a specific probability of being added to the level. The result is a computationally efficient approach to generating a large space of randomized levels.
A level created by the probabilistic multi-pass generator
The generation process consists of several phases, which place additional object types in the level. The following passes occur during generation:
- Ground placement
- Secondary hills
- Pipes
- Enemies
- Blocks
- Coins
Phases in the level generation process
During each phase, the generator traverses the level from left to right placing objects in response to probabilistic events. For example, during the first phase the system places the ground. The following events can occur during this phase:
- Begin gap (if not currently placing a gap)
- End gap (if currently placing a gap)
- Change ground height (if not currently placing a gap)
Each of these events has a probability of occurring during the first pass through the level. The activation condition for an event is specified as follows:
Math.random() < pEvent
where pEvent is the probability that a specific event will occur. The system also applies a set of constraints in order to ensure that generated levels are playable. During ground placement, the following rules are enforced:
- If the current gap exceeds the maximum gap size, immediately add ground
- If the ground height is increased, constrain the maximum increase in height
Playability constraints are only applied during the first phase of the generation process. The additional constraints specified by the competition rules are satisfied by over-generating and then constraining during the generation process.
A level generated with the EXTREME parameter set
The system takes two types of parameters as input: probabilities that specify the frequency of events occurring, and parameters that constrain the range of generated values. While the entry submitted to the CIG 2010 competition used a fixed parameter set, it is possible to adapt to players by selecting different probabilities in response to the supplied player model. For example, the system could generate levels for highly skilled players by utilizing an EXTREME parameter set.
Check out the generator by running this JAR. Or, play around with the generator source. For information on setting up your own generator, see the competition rules.
