The challenge
We want to be able to create a lot of levels for the game. Indeed, for some game modes, such as “puzzle rush”, or our future multiplayer modes, level diversity is really important.
However, while creating a level is really fun, creating 100 or 300 levels in a row proved to be quite cumbersome. We decided to try to create an random level generator.
1.Tickles Penguin’s rules
The first step was to create an object representing the game and its rules.
Here are the game rules :
- A penguin is located in a 8×16 board. The goal is to reach the finish line, at the edge of the board.
- The player decides to move up, left, right or down so that the penguin slides until it reaches a block that would make it stop. Only then, the player can decide to move to another direction to try to reach the end.
Different types of blocks are available in the game :
 | Finish Line | You win the game if you reach this block. |
 | Picks | If you touch the picks, you lose. |
 | Treadmill | The treadmill will force your penguin to follow the direction indicated by the arrows. |
 | Snow | The snow makes the penguin stop on the block. |
 | Wall | The wall makes the penguin stop in front of it. |
 | Tree | The tree makes the penguin stop in front of it. |
 | Door (yes, it is a door) | The door makes the penguin teleport to another predefined door. |
 | Bridge | The bridge makes your penguin go over the block under it. For example, if you put a bridge above a wall, bridge allows go across the wall.  |
The first challenge was to code this using python. We ended up with an object called Board, which is a class in which you can set the size of the board, the penguin’s starting position, and position all the blocks.
In the Board class, a method called simulate_movement allows you to indicate a starting position, a direction, and get at the end the CharacterState representing the position of the penguin, whether it is still alive and whether you won the game.
def simulate_movement(
self,
position: PositionInput,
direction: DirectionInput,
*,
stop_on_stop: bool = True,
stop_on_win: bool = True,
stop_on_death: bool = True,
) -> CharacterState:
"""Simulate movement of the character in a direction.
Args:
direction: The direction of the movement.
position: The position of the character.
stop_on_stop: Whether to stop when the character stops.
stop_on_win: Whether to stop when the character wins.
stop_on_death: Whether to stop when the character dies.
Returns:
The state of the character after the movement simulation.
"""
character = Character(position)
character.direction = direction
self.move_character_until_end(
character,
stop_on_stop=stop_on_stop,
stop_on_win=stop_on_win,
stop_on_death=stop_on_death,
)
return character.get_state()2. Generating a random path
Once we are able to code game mechanics, we can now start creating our random levels.
To do so, we used the following algorithm:
- Initialize random starting and ending positions
- From the starting position, initialize a random step by choosing:
- A random orientation (horizontal or vertical)
- A random number of steps (which can be negative). For exemple, horizontal movement with -5 steps means you are moving 5 steps to the left. The random number of steps must be chosen so that the penguin does not leave the board.
- For the following iterations (depending on how many moves you want to player to do to reach the end), you simply:
- Change the orientation (if previous orientation was horizontal, the next orientation if vertical and vice versa)
- Choose a random number of steps with the following constraints
- The penguin does not leave the board,
- The penguin does reach a previous location,
- The penguin does not cross other steps too much
- To reach the end, generate steps to go to the end.
NB: With hindsight, it would have been far better to create random levels starting from the end and without predefined starting positions. Indeed, the method we followed made us write extra lines of code to avoid creating easy levels in which the starting position is in the same axis as the ending position, or a move make you go to the same axis as the ending position.
Here is the result of the random creation of a path:
3. Generating random “constraint” paths
To lure the player and not just create one path, we can also create other paths the penguin must be able to follow using the same method:
4. Adding blocks
Next, we generate blocks making the level possible (-6 represents a vertical bridge, -5 a horizontal bridge, -3 a wall, -4 is snow, 1 the starting position, -2 the ending position) :
The blocks must be created so that :
- The winning path is feasible
- The constraint path are feasible, only if it does not make the winning path impossible
We can add new constraint paths to make the level more interesting:
5. Coding a game solver
Then, we need to create an game solver to make sure :
- The level is feasible
- The level is only feasible through the winning path we created, and not some other easier paths.
To this end, the solution is to create a directional graph with all the possible moves the penguin can do. Starting from the penguin initial position, we simulate each and every move (up, down, left, right). The shortest path is then simply the path from the starting position to the finish line with the minimum number of steps.
6. Adding blocks to stop shorter paths
Now that we have a game solver, we can add blocks to stop shorter paths to be possible.
For example, in the following illustration, we added a vertical bridge to prevent the blue path from being be feasible.
We keep iterating, 10 times, to get the following result:
Once the level is created, we can choose to accept/or reject it depending on:
- Whether the shortest path has enough steps (let’s say we want between no less than 8 moves to finish a level),
- Whether the level does not have too much bridges or walls, for example.
And here is the final level in the game:
Don’t hesitate to post comments. 🙂