I posted a mockup of an action adventure environment a while back. It was all hand-placed, but the plan was to make the game handle maps for me.


With help from my Prim BSP and Prim Grid libraries, I'm just about there. Here's how:

1. I use a prim_Grid to create an overworld maze. Each cell is a screen.
2. I choose to focus on the current screen. That (plus some border tiles for warping between screens) is my map.
   
3. I set everything to a wall by default.
4. I send my map dimensions into a prim_BSP. That splits the map into random rectangles and forms a maze out of their connections.
   
5. I identify the nodes connected to off-screen rooms.
6. Using the prim_BSP's built-in proc, I isolate the dead end nodes of the maze. By definition, I know that dead ends won't block movement between the other nodes. Some nodes with off-screen connections might be in this set because the prim_BSP only tracked what's local. The rest I choose to leave as walls. They will make the room look less like a giant rectangle.
   • Optional: I then send the dimensions of each dead end node's core into a prim_Grid, have it graph a maze and isolate that maze's dead end cells. What's left is a random shape to add detail inside the wall.
7. I turn the cores of each remaining node into floors.
8. I turn the borders between connected nodes into floors.
   • For nodes connected by a corner tile, I add an adjacent floor tile so diagonal movement isn't required. I also think it looks better with tiles graphics that use hard 90 degree angles. ;)
9. I'd like to place props, but I don't want them to block travel. As before, I know that dead ends in a maze are always safe. I therefore make a maze for the floor inside its arbitrary shape. (This is similar to how the "brain curves" in MeanderGall are formed.)
   1. I make a child type of prim_Grid with a second grid2d_Grid. I then make the new prim_Grid type ask the second grid for permission when seeking connection candidates.
   2. I make an instance of the new prim_Grid type using the dimensions of my map. I then set its second grid to ignore the coordinates of every wall tile.
   3. I tell this prim_Grid to graph like usual and then ask it for the dead end nodes.
10. Placing props in every dead end cell could result in a narrow range of movement. I choose just a fraction of the available tiles at random.
    
    • Random pixel offsets can help remove the grid.
    • When plants are placed closely together, making them small gives a hint that they're fighting for nutrients... and just plain adds variety.

Here's one of the resulting maps:


I think this looks better than the top mockup. It doesn't quite match, but I can theoretically choose whatever environment I want for each node. If I want to block an exit off with water, I can just change the tiles of its node and allow the player access to a tool used to cross. If it's not part of the gameplay then I don't really care.

I still have to decide on my biomes and how to choose them, but the map portion of my game is pretty much a solved problem. Deciding on the actual game mechanics has been the more glaring issue.

...Of course, you now have both the tools and the algorithm so my own project doesn't matter, does it? ;)


_{As usual, royalty-free textures were provided by Spiral Graphics.}