Mark Sachs (ksleet) wrote,
Mark Sachs

  • Mood:
  • Music:

Map generation.

So I got random map generation working in my vector engine! Which was really rather thrilling.

Right now it's just drawing the map to the screen -- I have some half-implemented physics code for handling rooms made up of an arbitrary collection of lines, but I'm not bothering to get that working yet since map generation is honestly more fun. But as you can see, I can have a selection of rooms of random sizes, connected by corridors. To get this working, I studied typical map generation algorithms for Roguelike games. The one I decided to use is really quite elegant:

1. Start with a single room.
2. Pick any random room that already exists on the map. If we're just starting, of course that will be the single room we created in step 1.
3. Pick a random side of the room. Place an exit.
4. Add a corridor extending out from that exit.
5. Create another room at the other end of the corridor.
6. If at any point in steps 2-5 the corridor or room you created overlaps any of the other corridors or rooms already placed on the map, throw out both of them, return to step 2 and try again.
7. Otherwise, save the newly created corridor and room, and go back to step 2. Continue until you have the desired number of rooms and corridors.

What makes this algorithm great is that it completely avoids the complex problem of deliberately trying to link together two already-placed rooms, as the naive algorithm ("create some rooms then make corridors linking them") does. You're guaranteed to get a topologically correct tree of corridors and rooms every time. Plus, there are lots of ways to customize the algorithm to create a different-looking map: for example, if in step 2 you allow corridors to be chosen as well as rooms, then you'll get a map with lots of branching corridors. (In fact, I do allow that currently -- you can see a few "T" corridors in the screenshot above.) If in step 3 you only select exits on the left or right sides of the room, you'll get a long, skinny map with many choke points. And so forth. I've got a half-implemented parameters class that will let me gimmick the generation results, and am looking forward to exercising it.

I should mention that this algorithm also suits the desired gameplay very nicely. The goal of each map is to go from your starting position to the reactor, blow it up, then go from there to the exit. If I assume that the first room created is where the reactor will be, it's easy to put the entrance at the end of one "branch" of the map and the exit at a different "branch." Because of how the level was constructed, you are guaranteed to be able to get from the start of the map to the end.

The only flaw is that this algorithm is incapable of making a series of rooms that connect in a loop, since no newly created corridors or rooms are allowed to overlap existing ones. But I can imagine a simple change in Step 6 where if we detect that a corridor overlaps a room, we just create a new exit on the already-existing room that meets the new corridor, and call it done. A little tricky but it should resolve the issue.
Tags: nagawrimo, nerd
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 1 comment