Complete Roguelike Tutorial, using python+libtcod, part 3
This is part of a series of tutorials; the main page can be found here.
Dungeon building blocks
Alright then, it's about time our dungeon takes a recognizable shape! I never cared much for pillars anyway. What we're gonna do now is create functions to carve rooms and tunnels in the underground rock. These functions will be the building blocks used to generate the whole dungeon which you'll get to later.
First of all, a little helper class that will be very handy when dealing with rectangular rooms:
This will take top-left coordinates for a rectangle (in tiles, of course), and its size, to define it in terms of two points: top-left (x1, y1) and bottom-right (x2, y2). Why not store directly its top-left coordinates and size? Well, it's much easier to loop through the room's tiles this way, since Python's range function takes arguments in this form. It will also be apparent later that the code for intersecting rectangles (for example, to be sure rooms don't overlap) is easier to define this way.
Python's range function, however, excludes the last element in the loop. For example, for x in range(x1, x2) will only loop until x2 - 1. So the code to fill a room with unblocked tiles could be:
The + 1 at the end takes care of the issue we mentioned. But we actually want to leave some walls at the border of the room, so we'll leave out one tile in all directions.
Subtle, but important! This way, even if two rooms are right next to each other (but not overlapping), there's always one wall separating them. Now we're going to modify the make_map function to start out with all tiles blocked, and carve two rooms in the map with our new function.
Before testing out, make the player appear in the center of the first room:
You can walk around the first room, but not reach the second. We'll define a function to carve a horizontal tunnel:
There's some creative use of the min and max functions there, so we'll explain that a bit. Feel free to skip this if you got it. They'll return the minimum or maximum of both arguments, but why are they needed? Well, if x1 < x2, x1 will be the minimum of both, and x2 the maximum. So that line will be the same as:
If they're reversed, the same line wouldn't work -- as it is, for only loops from a small number to a bigger number. But returning to the original line, then x2 will be the minimum, and x1 maximum. You guessed it -- it will be the same as:
It could be solved with other logic: swapping their values, changing the for 's step to negative, having an if to choose between the two lines... The functions min and max tend to give the shortest code, though it may be harder to understand if you're not used to them much.
The function to carve vertical functions is pretty similar.
Now, in make_map, we can connect both rooms with a horizontal tunnel.
That concludes the test for the carving functions! It's really starting to look better by the minute. You can create different dungeon configurations with them, but it's tricky defining the coordinates by hand and we're going to rush right away to the most interesting bit: random dungeon generation!
You can find the whole code for this part here.
Finally, the dungeon generator. After this point you'll have accomplished something that is truly a turning point in the development of a roguelike, and that is no small feat! There are many different approaches to coding a dungeon generator, and there is no consensus; everyone has their own interpretation of the right way to do this. Perhaps after being content with this one for a while you'll think of different ways to improve it.
The basic idea is this. Pick a random location for the first room, and carve it. Then pick another location for the second; it cannot overlap with the first. Connect the two with a tunnel, and repeat. This will yield a sequence of connected rooms.
One important property is that the player is guaranteed to be able to reach every room. The downside is that there will be lots of overlaps between the tunnels, and even tunnels overlapping rooms, but that's not too bad since the player can't distinguish between tunnel floor and room floor. The overlaps actually give it a more complicated look than if it were just a simple string of rooms!
Alright, we can see that the Rect class needs a method to check for intersections, so that no two rooms can overlap. We'll also create a method to return the center coordinates of the room since that's where all tunnels will be connected.
Don't worry if the intersection logic seems alien, it's a direct formula that doesn't require interpretation! It's one of those copy-and-paste things. The constants for the dungeon generation are simply the room's minimum and maximum size, and the maximum number of rooms.
Ok, we've described the gist of the algorithm, took care of all helper functions and classes... Now to implement it in make_map. Remove the previous code that creates the example rooms and tunnel, and make a loop to iterate until the maximum number of rooms, assigning random coordinates and size to each one as we go.
The random_get_int function returns a random integer between two numbers; the first parameter, zero, identifies the "stream" to get that number from. Random number streams are useful if you want to recreate sequences of random numbers; for our purposes it's not needed, so we use the default stream.
The Rect class will really start to come in handy at this point! The rooms list stores all previous rooms as Rect 's. That way we can compare the new room with previous ones for intersection, and reject it if it overlaps.
If the room is valid, we can carve it with create_room! We'll also handle a special case: the player will start in the center of the first room.
The tunnels deserve some attention. (This is a long example, but please be patient!) Sometimes a strictly horizontal or vertical tunnel can't connect two rooms. Imagine one is on one corner of the map (e.g., top-left), and the other in the opposing corner (e.g., bottom-right.) You'd need two tunnels going from the first room: one horizontal tunnel to reach the right side of the map, and one vertical tunnel to go from there to the bottom of the map (reaching the second room). Or the other way around: one vertical tunnel to reach the bottom of the map, and another horizontal one to reach the right side (reaching the second room.) Both options are valid, so we choose between them randomly.
So we're going to code that, and you'll see that this not only covers extreme cases like the one in the example, but also works perfectly when two rooms are side-by-side! Since in that case one of the tunnel segments (horizontal or vertical) will be very small, and only the other segment will be visible. It's a bit hard to visualize though, you'll have to see it in action.
You made it through all that in one piece, eh? Let's test it out! With some luck, some of the dungeons you get can be pretty amazing. Not too shabby for our own little algorithm!
The final code for the dungeon generator is here.