Home About EIS →

A Probabilistic Multi-Pass Level Generator

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:

  1. Ground placement
  2. Secondary hills
  3. Pipes
  4. Enemies
  5. Blocks
  6. 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:

  1. If the current gap exceeds the maximum gap size, immediately add ground
  2. 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.


About the author:  Ben Weber is a PhD student at UC Santa Cruz. Read more from this author


This entry was posted in Academics. Bookmark the permalink. Both comments and trackbacks are currently closed.

8 Comments

  1. Anonymous
    Posted September 2, 2010 at 5:16 PM | Permalink

    Neat!

    Ever consider generating random numbers from different distributions?

    For instance hard enemies or interesting little traps could be placed with an exponential distribution. It’d be similar to what you were doing but could result in less uniformly random looking results.

    If you don’t feel like venturing further you could look at perlin noise. Perlin noise is great for landscapes because it has noise at different frequencies. You do the large changes at low frequency and the small changes at high frequency.

  2. mt10
    Posted September 8, 2010 at 5:08 AM | Permalink

    Finally! A game I can play forever without ever getting bored!

    Oh no, now I’m never ever going to go out of my basement…

  3. Gaming4Life
    Posted September 20, 2010 at 11:14 PM | Permalink

    Just played through a few rounds and had to say, I liked how it got harder or easier depending on how well I did, or how often I died. Neat.

  4. Funny News
    Posted October 1, 2010 at 3:04 PM | Permalink

    This is awesome. I love mario as do most generation Y’ers. The formula needs to be copied and recreated with unlimited options by computers. How cool! Now I want to be a computer scientist.

  5. Increase Web Traffic
    Posted December 29, 2010 at 4:39 AM | Permalink

    Wow. Impressive.

  6. clint herman
    Posted January 8, 2011 at 3:01 AM | Permalink

    I found this game cute but very enjoyable. Thanks for posting!

  7. printing china
    Posted January 13, 2011 at 10:51 PM | Permalink

    good

  8. Marc Azada
    Posted August 18, 2011 at 12:28 AM | Permalink

    Nice game! Seems fun to me. It was even explained well.

4 Trackbacks