# Procedual level generation for a platformer game (tilebased) using player physics

I have been searching for information about how to build a 2d world generator (tilebased) for a platformer game I am developing. The levels should look like dungeons with a ceiling and a floor and they will have a high probability of being just made of horizontal rooms but sometimes they can have exits to a top/down room.

Here is an example of what I would like to achieve. I'm referring only to the caves part. I know level design won't be that great when generated but I think it is possible to have something good enough for people to enjoy the procedural maps (Note: Super Metroid Spoiler!):

http://www.snesmaps.com/maps/SuperMetroid/SuperMetroidMapNorfair.html

An idea I had to accomplish this was to let the computer play a level and carve the dungeon as the "computer player" plays. But don't know how to handle branches in the way, etc... Using this way of carving I could be confident that at least an exit exists in the map and that it is reachable.

Another idea I had was using a cellular automata with some heuristics to do the carving. A problem arises here: how could I make sure that all zones carved are reachable by the player (that is limited by gravity, etc...) ?. I guess I could use some kind of graph that could follow the different dungeon floors the automata is carving and then somehow I could measure if some part would be reachable or not by the player and add platforms or new terrain to make it reachable.

• I think part 1 of your questions boils down to "how can I ensure procedurally-generated platformer maps are reachable"? If so please edit the question to make that obvious. The other parts should be split into separate questions. Aug 20, 2014 at 0:45
• I have rewritten the question. I realized there was a lot of not needed text. Now I have tried to concentrate in the terrain reachability problem. Aug 20, 2014 at 8:52

In order to create a randomly procedurally generated level, you need a random moving unit AI that behaves like the player.

The computer controlled unit needs all the moves (actions) the player would have at this point in the game and it will need to refrain from heading back (I'll explain why and how next).

You need to mark each platform and each empty tile or empty space the carving character moves through to ensure they are not modified after they are generated. If they are modified it could break the desired flow and movement in the level.

Lets take a "basic" example where the player unit can only walk, jump and fall. The computer controlling AI begins sending the player a random stream of input and state (similar to keyboard input from a real live player + onGround state Boolean).

Lets say the AI player starts in an entrance. Now the computer begins to pick moves randomly with a specified expectancy. Each time the unit moves left or right onGround, a platform is generated underneath it's new position. The unit is disallowed from moving backwards to platfroms it already visited (we specified how before).

The player can also jump. When the player jumps, she will begin to fall down once she reaches her jump maxHeight. When she begins to fall, the computer will decide when to turn the onGround back on. This needs to be done before the player reaches a point lower than the point from which the character cannot jumped back unless you want the reverse route to be inaccessible (you need to write a method that test for jump-back-ability, there are instructions on the site).

Sometimes you may wish to randomly turn off the onGround and let the character fall through a hole in the ground. Again the character is disallowed from falling longer than her jump maxHeight when the route needs to be bidirectional.

In order to add forks in the route, simply create a new random player moving player at the point where you want the path to fork, this player will have to jump because it is disallowed from moving on existing ground and after jumping it will need to land on a newly created platform because like we said, empty tiles or empty space are not modifiable after a character moved through them.

Last notes:

• Test for jump-back-ability and create empty space tiles as needed.
• give the player a general direction to head towards.
• Allow it multiple goals in one room so the path could twist and turn.
• I like this idea. I had in mind something like this as I said before about the computer playing itself through the level. A new point of view I can extract from your answer is that you seem not to carve but build the level as the player traverses it. Sorry but I wasn't able to find any information about jump-back-ability here. I would really like to have a talk with you through skype or anyting about this subject because my head is full of ideas to implement at this moment. Could it be possible? I will then add all the important points here if people is interested. Aug 20, 2014 at 10:02
• Sounds great. I don't have Skype atm but I can chat when I get back from work. My email address is my nick @ gmail. Take a look at this discussion about jump-ability checking: gamedev.stackexchange.com/questions/69926/… There are more examples. You could search for "can jump check" or something similar. Aug 20, 2014 at 10:49
• @Notbad Here is an answer I've given about platform reachability by means of jumping: gamedev.stackexchange.com/questions/71612/… Aug 20, 2014 at 11:00
• Ah, I see, I was looking into this last week. By the way I sent you an email will my contact. Thanks again. Aug 20, 2014 at 11:58