Requirement
It’s time to start developing our Roguelike game. We’ll begin by generating a dungeon. Some details are specified below, but generating a good-looking dungeon is largely a matter of taste. The figure shows an example generated by (an old version of) my game.
Because it’s so much a matter of taste, you may decide how you want your dungeon to look and come up with your own heuristics to generate that look. Things to keep in mind are playability and realism. Yeah, it’s a fantasy game where we fight monsters in underground dungeons, but that doesn’t mean there’s no realism! Corridors that are too straight are probably unrealistic; after all, veins of harder minerals occur in the rock, and miners will probably tunnel around them. On a more practical note, large open areas, wide corridors, and overly straight corridors give advantages to monsters in play because the player does not have architectural features to use to tactical advantage. A poor dungeon leads to an unplayable game. Players need places to rest and hide out of sight of fire-breathing dragons and balrogs, spell-casting necromancers, and arrow-loosing orc hordes. On the other hand, often line of sight is useful for your own attacks, so you don’t want your passages too twisty.
Your dungeon generator should be written with an eye toward extensibility. Remember that you will be.
-----------------------------------------------------------------------------
| ............. ..... |
| ............. ###..... |
| ......... ............. #### ..... |
| .... ......... ............. ## ..... |
| .... ......... ............. # ..... |
| .... ......... ............. ### ..... |
| ....################# ......... ............. # ..... |
| # #######......... ............. ## ..... |
| # # #......... # ### # |
| # ## ######## ##### # |
| # ## ######## ## #........ |
| ## # # # # ##############........ |
| # .... ## # # # |
| ## .... # .... #..... |
| ....####.... ### .... #..... |
| ....# ....# ### .... #..... |
| ....# ## |
| ....######## |
| |
-----------------------------------------------------------------------------
An example randomly-generated dungeon from my code. Rock is represented by spaces, room floor by periods, and corridor floor by hashes. The border was added artificially to demarcate the map from the page. While you’re welcome to draw a border around your dungeon (and many students do), this one is only here so that you can see the bounds of my dungeon in this document.
Adding functionality on top of this next week, and for the rest of the semester (see the roguelike roadmap on the assignments page). For this step, you generate a dungeon, draw it on the standard output, and exit. Here are the requirements:
- All code is in C.
- Dungeon measures 80 units in the x (horizontal) direction and 21 units in the y (vertical) direction. A standard terminal is 80 24, and limiting the dungeon to 21 rows leaves three rows for text, things like gameplay messages and player status, which come later.
- Require at least 5 rooms per dungeon
- Each room measures at least 3 units in the x direction and at least 2 units in the y direction.
- Rooms need not be rectangular, but neither may they contact one another. There must be at least 1 cell of non-room between any two different rooms.
- The outermost cells of the dungeon are immutable, thus they must remain rock and cannot be part of any room or corridor.
- Room cells should be drawn with periods, corridor cells with hashes, and rock with spaces.
- The dungeon should be fully connected, meaning that from any position on the floor, your adventurer should be able to walk to any other position on the floor without passing through rock.
- Corridors should not extend into rooms, e.g., no hashes should be rendered inside rooms.
Here is an informal description of a dungeon generator that I wrote to produce the figure; I’ve played with dungeon generation enough to know that much simpler methods can do the job, but this method does a nice job of balancing aesthetically-pleasing (to me) dungeons and having a small, straightforward imple- mentation. There are certain tunable parameters, for example, determining the size of a new room, that I leave out of the description. You may use this algorithm, something you find online, or something of your own devising.
To implement my algorithm, you will need an array of rooms and an 80 21 matrix of cells representing the dungeon. I initialize the dungeon by setting an immutable flag on the outermost cells and assigning a hardness to the material in every cell. I then attempt to randomly place random rooms in the available space, checking that the room can be placed legally each time, until some termination criterion is reached. Example criteria: the dungeon is at least 7% open (not rock); there were 2000 failed placement attempts in a row; a create new room() predicate failed; etc.
After placing rooms, move through the room array of n rooms, connecting room 1 with room 2, then room 3 with rooms 1-2, . . . until you’ve connected room n with rooms 1-(n 1). Okay, so how do we make that connection? Find the closest room in the already connected set using Euclidean distance to its centroid then carve a path to it by changing rock to open space; this can always be done with zero or one change of direction. If you get that working, then add some random changes of direction in there to make it look a little more exciting.
So why do I have that rock hardness? Well, our adventurer and monsters will eventually be able to tunnel through the dungeon, so hardness will be a useful notion to influence tunneling, but for now I use it to drive a corridor heuristic. I use Dijkstra’s algorithm where my edge weights are rock hardnesses and modified with penalties for direction changes to find shortest paths between 1-2, 2-3, . . ., (n 1)-n. If you implement this, you’ll find that your code will draw corridors directly to nearby rooms too oftenthe dungeon ends up connected, but there are never any loops, and I think that’s kind of boringso you need to weight empty space close to the hardness of the softest rock to get more satisfying results. You may be thinking that this is an interesting method, but it requires a priority queue, so it’s too much work. That may be trueup to you to decidehowever: 1) A priority queue is easy to implement; and 2) You’ll need one eventually, anyway, in order for monsters to move around the dungeon without getting stuck in corners.