This is part of a series on procedural generation in games.
Generating maps pragmatically is trickier than it seems. First off, the ability to write a good map generation algorithm is highly dependent on the desired output. As an example, I'm not aware of any first person shooter that uses generated maps, and I would be amazed to see one. The nuances required for a good map in that genre are quite complex. On the other hand, generated maps are not uncommon in the dungeon crawling genre, as it seems it's easier to make a useable map with code there. Since Idamu Caverns is a dungeon crawler with generated maps, that will be the focus of this post.
I did a lot of research before starting on Idamu Caverns. Probably the single most influential thing I read is this nine part series on developing Roguelike games. It's quite a lot to read, but if you're planning on developing anything vaguely Roguelike, I recommend that you set aside time for it.
It's difficult to write this without the article becoming overly long, as there's a lot to be said on the topic, but one of the most important things to clarify before you start writing map generating code is to understand why you're doing so. Not so much, why am I having code create maps instead of just creating the maps myself; but why do I need maps in the first place?
Unless you're writing a text adventure (remember those?) you'll need a way to represent game play graphically, but even with text adventures there were maps. To get to the real answer, we have to dig deeper, to the core concept that exploring maps is fun. Take away the monsters and loot and everything else, and there's a joy alone in exploring a map. And map exploration is something video games do better than any other medium I can think of.
So, if you're going to have a map at all, you need to make sure that exploring that map is an adventure in itself. This leads to another concept that I'll touch on over and over again: random generation is usually bad and should be used sparingly.
Taken to an extreme, a purely random map isn't even playable. It would have a completely random tile on each square, and probably wouldn't even be traversal. While such an extreme case may seem pointless to bring up, the rule of thumb that less random is better probably holds true in most cases.
The map generator currently used by Idamu Caverns is actually many layers of map generation, as well as many iterations of the code.
From the start, I recognized that many techniques of map generation existed, that I probably wouldn't get it right on the first try, and that the the different methods could produce maps with different feels and it may be useful to have more than one method. As a result, the first thing Idamu Caverns' map generator does is to select a specific map generator. This approach allows me to work on new map generators over periods of time, and leave them disable in the production code until they're finally ready, which works well with the frequent release model of the game.
The first map generator code was non-random procedural generation. A long hallway was generated with the up and down stairs at opposite ends, and equally sized rooms placed equal distance along the hall. The only random element to the map would be what monsters and items spawned in each room. The advantage is that the code was simple, reliable, and fast; but the disadvantage was that the resultant maps were boring. They had no entertainment value in themselves. As a result, this original code didn't even survive to the first release version.
What replaced it was a random generator that worked by drawing random sized rooms, then connecting them with hallways. This was considerably more interesting, but also more challenging to make work. The complexity of connecting the rooms without having hallways that overlapped and created an ugly mess was challenging. Early versions would frequently create maps with sections inaccessible from the stair.
Furthermore, even this was too boring. Hallways were never interesting, it was difficult to allow them to intersect while preventing them from intersecting too much and in ugly ways. With each room simple a rectangle, there was never anything interesting about the rooms.
In essence, there was too much random, and not enough human controlled interest. I didn't need to be a genius to solve the problem, though, I just took some hints from the article mentioned above and programmed a method for extracting data on human-generated rooms and placing them instead of random sized rectangles. This allowed me to draw any sort of room (or possibly a configuration of multiple rooms) and have the code randomly place it on the map then connect everything with halls. The unintended benefit is that it allows the hall code to become simpler. No longer were hall intersections allowed, instead, a small number of "rooms" are drawn that are essentially hall intersections. The random placement algorithm puts these on the map occasionally and connects them to everything else as if they were a room.
The algorithm continues to evolve, and as it does it keeps appearing that less randomness is better than more. One such optimization was that instead of placing rooms completely at random, the algorithm now breaks the room sizes into large and small, and places a few large rooms first, then attempts to fill in the rest of the map with small rooms. This ensures that maps will always have a large room, and not simply be crammed full of tiny rooms. It also avoids the uncommon, but annoying map with only a few large rooms.
A lot of the design emerged as I experimented. Originally, I intended for every level to have a single stair down to the next level. However, I couldn't quite get the code to guarantee that there would always be a path between the two stairs. To shorten a long story, instead of ensuring that you could always get to the down stair, I embraced the concept of the occasional dead end level by creating workarounds that prevent it from stopping further gameplay.
There's a lot more I can say on this topic, so it's likely I'll do additional posts.
The next post in this series concerns keeping the game fun and challenging.
No comments:
Post a Comment