Article
Procedural Map Generation
Published 5 years ago
631
0
How To Do It Well, Based on the Needs of the Game
One of our first major design decisions on Couch Heroes vs The Dungeon was to generate each level procedurally. This was partly because we wanted the experience to be highly replayable, but also because creating levels by hand can take a lot of time—we didn't know how much time we had before Apple would tell us to submit our game for the tvOS launch. We had done some previous work on procedural map generation in a different project, so we applied what we had learned to this new scenario.
In Couch Heroes we have a grid layout where each point on the grid is a single, small square that can contain one environmental item—for instance, an enemy spawner or loot pickup.
Points as squares.
However, our previous work was kind of a different beast; those efforts involved generating a grid where each "point" was a actually large town square. Each of these large squares contained an inner courtyard area surrounded by buildings and paths, where each courtyard, path, and building was randomly chosen from a pool of handmade objects. On the one hand, the town square method guaranteed that we would have wide-open spaces, which are excellent for handling the chaotic swarms you get in a top-down shooter, and allowed for each space to be at least a bit different from the one adjacent to it. But on the other hand, this approach was very limiting when it came to level variation because each town square had an identical layout and creating each portion of the square required a lot of work from artists. Plus, paths needed to be lined up with those in adjacent squares in order to prevent them from running into the back of a building in the other square, so generating a random border layout proved to be surprisingly obnoxious.
It was pretty clear that things had to be done differently this time, and so we used a more generalized method. This method created a grid system where each grid point was truly a single small point rather than a large area, which allowed for far more variation in each generated layout.

# The Basic Algorithm

## PATH SOBRIETY

We start with a "drunken walk", which begins at a starting position and randomly moves around the environment. The algorithm is constrained by the grid's boundaries and chooses to turn or move forward based on a given "straightness factor", which pretty much equates to whether the algorithm is more sober (straighter line) or drunk (lots of turning). The result is a single path weaving throughout the grid.
A "drunken walk" through a less sober path.

## CREATING ROOMS

At this point, the world is still pretty empty and so the next step fills the voids untouched by the path by placing rooms of semi-random size in several of the untouched areas. The rooms then need to be connected to the path, so we look outward from each room in order to find the nearest adjacent room or path and then create a new path from the current room to that point. The catch here is that one unconnected room can connect itself to another unconnected room and vice versa, meaning that even though both rooms are technically connected to something else, they are only connected to each other and neither is connected to the main path.
Then, we have to make sure that each room is reachable by the player, which we do by using an A* search to walk from each room back to the level's starting position and adding a new connection whenever a valid path can not be found.

## FINAL TOUCHES

Now that the floors are generated, we fill the spaces with other environmental objects. Doors are placed in points that stand between a large area and a small one, like where a hallway meets a room. Destructible objects are placed on points that lie within a room and border a wall. The exit point and resurrection tower are placed in different semi-randomly chosen rooms; in the case of the exit's room, preference is given to a room that is furthest from the entrance. Enemy spawners are semi-randomly placed in various rooms and loot pickups are sprinkled around the environment.
There you have it: a map generator capable of creating levels with enough variety to provide players with a unique experience whenever they play. Happy dungeon crawling!
Apple, Apple TV, Siri Remote and tvOS are trademarks of Apple Inc., registered in the U.S. and other countries. App Store is a service mark of Apple Inc.
The alcoholic figure is by Rflor from the Noun Project.