Procedural Generation, Part 1

by on Jan.20, 2011, under Programming

One of the biggest parts of Drillboid’s gameplay will be the level generation. This was my first time programming a level generator, though, so I did a little research and found that ChevyRay’s article on procedural generation and the source code for Spelunky were incredibly helpful. So, in the spirit of sharing that those lovely folks set, I figured I’d share what I came up with in the end!

The system you see in the current test build has three steps: first, it carves out a bunch of “rooms”, second, it fills those rooms in with premade rooms, and third, it randomizes those rooms slightly. Today I’ll be looking at the first step, but I’ll probably talk about the other two steps later on.

So, on to carving rooms. I liked the generator that ChevyRay described near the end of his article, but I found it a little too blobby for a platformer – that’s a lot of space to fill. Either way, it makes for a nice cave, so I figured I’d use its basic rules:

  • A root cell is placed in the centre of the room, and it chooses a random direction to dig in.
  • Every step of the simulation, all cells have a chance to change direction or stop digging altogether, then they place a cell in the direction that they are digging in.
  • Newly-placed cells inherit the direction of the cell that placed them.
  • A cell can’t stop digging if it is the last cell left digging.

I figured I could tweak these rules to make some nice caves for platforming, so I added the following:

  • The cave needs to be entered from the surface, so there should be a shaft leading down to it. To guarantee this, the root cell is placed in the room’s top-centre and and always starts by digging down.
  • Cells that try to dig up past the top of the room are turned around.
  • Every frame, a cell has a chance of digging down instead of whatever its current direction is. This doesn’t overwrite the current direction, but is only temporary to the current frame.
  • To deal with the levels being blobby, the cells remember which directions they dug into other cells through, and which cells they were dug into through. The result is that rooms can be right next to each other, but still have a dividing wall.

I prototyped this in Game Maker, so you can give the generator a try here. If you’re on a non-Windows machine, bear with me – here’s some screenshots of the results it gave:

Hmm. Well, it’s certainly less blobby, but there’s a lot of shafts. On all three of them, you can nearly fall straight from the top to the bottom. I tried tweaking the variables a bit, but it still didn’t look like it would be much fun to play. Between the affinity to digging downward and the fact that it always starts from the top, the levels were just too vertical. Heck, sometimes, I even got this:

As well, the exit is placed at the lowest point of the level, which also isn’t all that interesting. To make matters worse, if the generator has less than 20 cells after 30 simulation steps, it restarts and generates something bigger. It takes a good 5 tries to get a good level, and sometimes more. That could get a bit slow when generating the level. Later, I realized that wouldn’t be a big issue, but it’s still a consideration.

Anyway, back to the drawing board!

My next implementation changed some more rules:

  • The root cell is placed in the centre again, with a random direction.
  • The affinity to move downward has been removed.
  • There’s a maximum number of cells (40, to be exact).
  • The exit is placed at the furthest cell from the entrance. The cells are coloured depending on how far from the entrance they are, and this can be used to determine how much treasure and how many enemies to spawn.
  • Once the cells are all placed, a two-cell shaft is added above the topmost cell, and it is centred and aligned with the top of the room.

This is a bit closer to ChevyRay’s generator. Give a shot. Here’s a few examples of generated levels:

These are looking way nicer. There’s a lot more horizontal movement, and the ends of the levels are a bit more out of the way. As well, it takes far less tries to generate a decently-sized level. The one problem is, it’s still creating a lot of shafts. So, I made two last adjustments: I increased the chance of the dig direction changing, and I added a chance that, when changing directions, it’ll restrict the possible directions to only horizontal ones. The final implementation is the one in the test build right now, but you can see a Game Maker version of it here, along with a few images:

As you can see in the first image, it can generate smaller levels, but it also ranges to bigger ones like the third one and more spread-out ones like the second. Once this is filled in with obstacles, it’ll make for some interesting levels!

If you’d like to see the source code for the last version, here it is, fully commented. Feel free to learn from it, or even copy from it! I’d be that much happier if you linked back to this page, but it’s your choice – as long as if gives you some ideas, I’m happy.

Part 2 of this article can be found here!

3 Comments for this entry

  • Link

    Thanks for this article. I’d like to talk about the fact that it could possibly be hard when you’re in school and merely starting to create a long credit history. There are many scholars who will be merely trying to make it through and have long or favourable credit rating can be a difficult matter to own.

  • Slanje Cveca

    Reading, watching movies or plays, or similar activities that may bring inspiration.

  • Sarkari Naukri

    I am trying to find out some really good blogs for reading. I used to be looking over yahoo and google and found your blog. Effectively i enjoy your high quality blog design and style as well as your authoring skills. Carry on doing it.

Leave a Reply