This is a problem I've been mulling over for a bit; I'm interested in seeing how other people approach it. I have a program I've written that generates cave systems, like this:
I'd like to use it for a Metroid-style game of exploring, finding powerups that let you get past barriers, etc., but to do that I need to be able to programatically figure out what parts of the map are accessible to the player. That map above has some areas that can't be reached (straight up from the middle, for example, or the long vertical cave on the right side) and many that can't be exited once entered (most of the rectangular rooms, for example).
My starting assumptions: the player is 3 blocks tall and 1 block wide. He can jump 3 blocks into the air (i.e. if there is a wall that is as tall as he is, he can jump onto it). He can jump over a gap that is five blocks wide (total jump length 6 blocks). He cannot crawl, turn into a morph ball, slide, or anything like that.
I started working on an algorithm that starts with a known-accessible block and tries to find out what blocks are reachable from it. The algorithm looks roughly like this:
Pop accessible block A off of queue
Foreach distance d < player jump length:
Look at space B d to the side of A
Is that space occupied by a block:
B is accessible by walking/jumping. Enqueue it
# Abstracted away: checking for ceiling room, horizontal barriers
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
# Abstracted away: previously-jumped-to targets; decaying jump height with distance
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
# Abstracted away: horizontal barriers
Repeat
Repeat
All of the "abstracted away" notes are basically things that this "teleport horizontally over and then look up and down" algorithm doesn't handle well. There's also messiness with things like a tunnel that is reachable by jumping, but only if you start out above it (there's an example of that down and a bit left of center in the example map).
Basically I think this approach is flawed, but I'm having difficulty thinking of one that would work better. If you think the problem's interesting, I'd love to hear your thoughts on it.
Edit: I've come up with an alternative approach that I think is less error-prone. I've written a description with images
here. Thoughts on that approach?
