Difference between revisions of "Complete Roguelike Tutorial, using python+libtcod, part 2"
|Line 231:||Line 231:|
== Dungeon generator ==
== Dungeon generator ==
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
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 featThere 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
The basic idea is thisa , the a tunnel. .
Revision as of 05:25, 27 December 2009
This is part of a series of tutorials; the main page can be found here.
This part will introduce the map, FOV, and finally a neat dungeon generator! No roguelike is complete without those. We'll start with the map, a two-dimensional array of tiles where all your dungeon adventuring will happen. We'll start by defining its size at the top of the file. It's not quite the same size as the screen, to leave some space for a panel to show up later (where you can show stats and all). We'll try to make this as configurable as possible, this should suffice for now!
MAP_WIDTH = 80 MAP_HEIGHT = 45
Next, the tile colors. For now there are two tile types -- wall and ground. These will be their "dark" colors, which you'll see when they're not in FOV; their "lit" counterparts are not needed right now. Notice that their values are between 0 and 255, if you found colors on the web in hexadecimal format you'll have to convert them with a calculator. Finding RGB values by educated trial-and-error works at first but with time you'll have a set of colors that don't mix together very well (contrast and tone as perceived by the human eye, and all that stuff), so it's usually better to look at a chart of colors; just search for "html colors" and use one you like.
color_dark_wall = libtcod.Color(0, 0, 100) color_dark_ground = libtcod.Color(50, 50, 150)
What sort of info will each tile hold? We'll start simple, with two values that say whether a tile is passable or not, and whether it blocks sight. In this case, it's better to seperate them early, so later you can have see-through but unpassable tiles such as chasms, or passable tiles that block sight for secret passages. They'll be defined in a Tile class, that we'll add to as we go. Believe me, this class will quickly grow to have about a dozen different values for each tile!
class Tile: #a tile of the map and its properties def __init__(self, blocked, block_sight = None): self.blocked = blocked #by default, if a tile is blocked, it also blocks sight if block_sight is None: block_sight = blocked self.block_sight = block_sight
As promised, the map is a two-dimensional array of tiles. The easiest way to do that is to have a list of rows, each row itself being a list of tiles, since there are no native multi-dimensional arrays in Python. We'll build it using a neat trick, list comprehensions. See, the usual way to build lists (from C++ land) is to create an empty list, then iterate with a for and add elements gradually. But in Python, the syntax [element for index in range], where index and range are the same as what you'd use in a for, will return a list of elements. Just take a second to understand that sentence if you never worked with that before. With two of those, one for rows and another for tiles in each row, we create the map in one fell swoop! The linked page has a ton of examples on that, and also an example of nested list comprehensions like we're using for the map. Well, that's an awful lot of words for such a tiny piece of code!
def make_map(): global map #fill map with "unblocked" tiles map = [[ Tile(False) for y in range(MAP_HEIGHT) ] for x in range(MAP_WIDTH) ]
Accessing the tiles is as easy as map[x][y]. Here we add two pillars (blocked tiles) to demonstrate that, and provide a simple test.
map.blocked = True map.block_sight = True map.blocked = True map.block_sight = True
Don't worry, we're already close to a playable version! Since we need to draw both the objects and the map, it now makes sense to put them all under a new function instead of directly in the main loop. Take the object rendering code to a new render_all function, and in its place (in the main loop) call render_all().
def render_all(): #draw all objects in the list for object in objects: object.draw()
Still in the same function, we can now go through all the tiles and draw them to the screen, with the background color of a console character representing the corresponding tile. This will render the map.
for y in range(MAP_HEIGHT): for x in range(MAP_WIDTH): wall = map[x][y].block_sight if wall: libtcod.console_set_back(0, x, y, color_dark_wall, libtcod.BKGND_SET ) else: libtcod.console_set_back(0, x, y, color_dark_ground, libtcod.BKGND_SET )
Ok! Don't forget to call make_map() before the main loop, to set it up before the game begins. You should be able to see the two pillars and walk around the map now!
But wait, there's something wrong. The pillars show up, but the player can walk over them. That's easy to fix though, add this check to the beginning of the Object 's move method:
if not map[self.x + dx][self.y + dy].blocked:
Here's the code so far.
Field of View (FOV)
The next step towards a complete roguelike is FOV. This adds a tactical element, and lets the player wonder what's on the other side of every door and every corner! The FOV works like a light source where the player stands, casting light in every direction but not getting past any walls. Regions in shadow are invisible. You could code it yourself by casting rays outward from the player, but it's much easier than that; libtcod has a whole module dedicated to it! It includes different methods with varying levels of precision, speed and other interesting properties. There's an excellent study here if you want to know more about them, including tables and images comparing the different algorithms.
We'll define the chosen algorithm along with some other constants so they can be changed later. For now it's 0, the default algorithm. There's also an option to light walls or not, this is a matter of preference. Another important constant is the maximum radius for FOV calculations, how far the player can see in the dungeon. (Whether this is due to the player's sight range or the light from the player's torch depends on how you choose to explain this to the player.)
FOV_ALGO = 0 #default FOV algorithm FOV_LIGHT_WALLS = True TORCH_RADIUS = 10
Also, we'll need more colors for lit tiles! The color definitions will now be:
color_dark_wall = libtcod.Color(0, 0, 100) color_light_wall = libtcod.Color(130, 110, 50) color_dark_ground = libtcod.Color(50, 50, 150) color_light_ground = libtcod.Color(200, 180, 50)
These are taken straight away from the libtcod sample that comes with the library, and you may want to change them to give your game a more unique feel (see the earlier notes about colors).
The libtcod FOV module needs to know which tiles block sight. So, we create a map that libtcod can understand (fov_map), and fill it with the appropriate values from the tiles' own block_sight and blocked properties. Well, actually, only block_sight will be used; the blocked value is completely irrelevant for FOV! It will be useful only for the pathfinding module, but it doesn't hurt to provide that value anyway. Also, libtcod asks for values that are the opposite of what we defined, so we toggle them with the not operator.
fov_map = libtcod.map_new(MAP_WIDTH, MAP_HEIGHT) for y in range(MAP_HEIGHT): for x in range(MAP_WIDTH): libtcod.map_set_properties(fov_map, x, y, not map[x][y].blocked, not map[x][y].block_sight)
FOV will only need to be recomputed if the player moves, or a tile changes. To model that we'll define a global variable fov_recompute = True before the main loop. Then, in the handle_keys function, whenever the player moves we set it to True again, like in the following code.
#movement keys elif libtcod.console_is_key_pressed(libtcod.KEY_UP): player.move(0, -1) fov_recompute = True elif libtcod.console_is_key_pressed(libtcod.KEY_DOWN): player.move(0, 1) fov_recompute = True elif libtcod.console_is_key_pressed(libtcod.KEY_LEFT): player.move(-1, 0) fov_recompute = True elif libtcod.console_is_key_pressed(libtcod.KEY_RIGHT): player.move(1, 0) fov_recompute = True
Now we need to change the rendering code to actually recompute FOV, and display the result! It's a major overhaul of the render_all function. We only need to recompute FOV and render the map if recompute_fov is True (and then we reset it to False), done by the following code.
if fov_recompute: #recompute FOV if needed (the player moved or something) fov_recompute = False libtcod.map_compute_fov(fov_map, player.x, player.y, TORCH_RADIUS, FOV_LIGHT_WALLS, FOV_ALGO)
As you can see we're using all the constants we defined earlier. After that comes the code that iterates over all tiles and displays them in the console. We'll add an extra condition for each tile:
visible = libtcod.map_is_in_fov(fov_map, x, y)
Depending on the value of visible, the tile may be drawn in different colors (lit or dark). We'll show all of the modified map display code to make this a bit more clear.
#go through all tiles, and set their background color according to the FOV for y in range(MAP_HEIGHT): for x in range(MAP_WIDTH): visible = libtcod.map_is_in_fov(fov_map, x, y) wall = map[x][y].block_sight if not visible: #it's out of the player's FOV if wall: libtcod.console_set_back(0, x, y, color_dark_wall, libtcod.BKGND_SET) else: libtcod.console_set_back(0, x, y, color_dark_ground, libtcod.BKGND_SET) else: #it's visible if wall: libtcod.console_set_back(0, x, y, color_light_wall, libtcod.BKGND_SET ) else: libtcod.console_set_back(0, x, y, color_light_ground, libtcod.BKGND_SET )
There! It's done, you can move around the pillars and see their shadows being cast as you walk.
The last detail is to make sure objects only show if they're in the player's FOV. In the Object 's draw method, add a FOV check before drawing:
if libtcod.map_is_in_fov(fov_map, self.x, self.y):
Apart from defining the newly used global values in render_all and handle_keys, that's all there is to it. This is actually one aspect that can take a long time to get right in a roguelike, fortunately we were able to do it with a modest amount of work!
The whole code for this section is 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. First of all, a little helper class that will be very handy when dealing with rectangular rooms:
class Rect: #a rectangle on the map. used to characterize a room. def __init__(self, x, y, w, h): self.x1 = x self.y1 = y self.x2 = x + w self.y2 = y + h
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:
def create_room(room): global map #go through the tiles in the rectangle and make them passable for x in range(room.x1, room.x2 + 1): for y in range(room.y1, room.y2 + 1): map[x][y].blocked = False map[x][y].block_sight = False
But we want to leave some walls at the border of the room, so we'll leave out one tile in all directions.
def create_room(room): global map #go through the tiles in the rectangle and make them passable for x in range(room.x1 + 1, room.x2): for y in range(room.y1 + 1, room.y2): map[x][y].blocked = False map[x][y].block_sight = False
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.
def make_map(): global map #fill map with "blocked" tiles map = [[ Tile(True) for y in range(MAP_HEIGHT) ] for x in range(MAP_WIDTH) ] #create two rooms room1 = Rect(20, 15, 10, 15) room2 = Rect(50, 15, 10, 15) create_room(room1) create_room(room2)
Before testing out, make the player appear in the center of the first room:
player.x = 25 player.y = 23
You can walk around the first room, but not reach the second. We'll define a function to carve a horizontal tunnel: <def>create_h_tunnel(x1, x2, y):
global map for x in range(min(x1, x2), max(x1, x2) + 1): map[x][y].blocked = False
map[x][y].block_sight = False
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:
for x in range(x1, x2 + 1):
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:
for x in range(x2, x1 + 1):
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.
def create_v_tunnel(y1, y2, x): global map #vertical tunnel for y in range(min(y1, y2), max(y1, y2) + 1): map[x][y].blocked = False map[x][y].block_sight = False
Now, in make_map, we can connect both rooms with a horizontal tunnel.
create_h_tunnel(25, 55, 23)
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.
def center(self): center_x = (self.x1 + self.x2) / 2 center_y = (self.y1 + self.y2) / 2 return (center_x, center_y) def intersect(self, other): #returns true if this rectangle intersects with another one return (self.x1 <= other.x2 and self.x2 >= other.x1 and self.y1 <= other.y2 and self.y2 >= other.y1)
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.
ROOM_MAX_SIZE = 10 ROOM_MIN_SIZE = 6 MAX_ROOMS = 30
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.
rooms =  num_rooms = 0 for r in range(MAX_ROOMS): #random width and height w = libtcod.random_get_int(0, ROOM_MIN_SIZE, ROOM_MAX_SIZE) h = libtcod.random_get_int(0, ROOM_MIN_SIZE, ROOM_MAX_SIZE) #random position without going out of the boundaries of the map x = libtcod.random_get_int(0, 0, MAP_WIDTH - w - 1) y = libtcod.random_get_int(0, 0, MAP_HEIGHT - h - 1)
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.
#"Rect" class makes rectangles easier to work with new_room = Rect(x, y, w, h) #run through the other rooms and see if they intersect with this one failed = False for other_room in rooms: if new_room.intersect(other_room): failed = True break
If the room is valid, we can carve it with create_room! We'll also handle a special case -- the first room, where the player starts out, in the center.
if not failed: #this means there are no intersections, so this room is valid #"paint" it to the map's tiles create_room(new_room) #center coordinates of new room, will be useful later (new_x, new_y) = new_room.center() if num_rooms == 0: #this is the first room, where the player starts at player.x = new_x player.y = new_y
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 (ie, top-left), and the other in the opposing corner (ie, 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 room 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 tunnels (horizontal or vertical) will be very small, depending on the case. It's a bit hard to visualize though, you'll have to see it in action.
else: #all rooms after the first: #connect it to the previous room with a tunnel #center coordinates of previous room (prev_x, prev_y) = rooms[num_rooms-1].center() #draw a coin (random number that is either 0 or 1) if libtcod.random_get_int(0, 0, 1) == 1: #first move horizontally, then vertically create_h_tunnel(prev_x, new_x, prev_y) create_v_tunnel(prev_y, new_y, new_x) else: #first move vertically, then horizontally create_v_tunnel(prev_y, new_y, prev_x) create_h_tunnel(prev_x, new_x, new_y) #finally, append the new room to the list rooms.append(new_room) num_rooms += 1
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.
The last detail after dungeon generation is exploration, a.k.a Fog of War.