# Map accessibility for procedurally-generated platforming maps

This topic is 3267 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I'm working on a platforming game (that is, horizontal run&jump, like Mario, Metroid, Castlevania, and the like) that relies on procedurally-generated maps to increase replayability. Here's a sample map I've created after a few days working on the algorithm: Black is open, white is walls, grey is out of bounds, and the green and red are the tree I used to create the initial structure. My problem now is that I want to be able to guarantee access to all parts of the map. Right now in that map, there's plenty of areas that are either inaccessible (for example, the upwards shaft on the left side) or impossible to get out of (most of the downward shafts that end in rooms). The plan is to create an order of exploration by controlling which areas the player has access to -- finishing one area gets him a powerup that gives access to the next, Metroid-style. But I can't do that until I can figure out which areas can be accessed. I'm having trouble thinking of an algorithm that will work reasonably well. The best I've come up with is something along the following lines (note that the player starts in the middle of the map, the floor of which is therefore always accessible):
Pop accessible block A off of queue
Look at space B just to the left of A
Is that space occupied by a block:
B is accessible by walking. Enqueue it
Else:
Look above B for the closest floor C with enough headroom above it for the player to fit
Is it lower than the player's max jump height:
C is accessible by jumping. Enqueue it
Look below B for the closest floor D:
Is D far enough below C for the player to fit:
D is accessible by dropping down. Enqueue it
Repeat

The problem here is that it gets into trouble with things like jumping arcs, air control, and so on. Plus there's a ton of niggling little things involved in checking for headroom on jumps, making certain I don't accidentally teleport through walls during the scan, and so on. I'm hoping that one of you has a better idea. It doesn't have to be massively efficient, though I'd hope for sub-minute processing time on a map of the size in the example (270x195 tiles). My primary goals are accuracy and simplicity, as I anticipate having to make slight tweaks to deal with the player gaining new powerups. For what it's worth, at the moment I'm assuming that the player is 3 blocks tall, 1 block wide, can jump up 3 blocks, and can jump over 6 blocks. These statistics are subject to change once I actually add the player to the game. [Edited by - Derakon on March 13, 2009 6:37:54 PM]