Grid-Based DungeonBuilding a dungeon based on a grid model.
IntroductionThe
grid-based dungeon generator is an easy method to generate maps that
contain rooms guaranteed to fit within the dungeon space. By dividing
the dungeon space into a set of cells, rooms can be placed into the
space without the need to check whether each room overlaps another
room, or falls outside of the dungeon space. This article describes how
to use the grid-based generator to create the basic dungeon layout.
Creating the GridThe
first step is to create an array of some data type that will represent
the dungeon. Each cell in the dungeon array will correspond to a
particular location on the map. Normally the dungeon array is filled
with a wall id or some other impassible dungeon feature and rooms are
carved out of the map.
The next step is to divide the array
into logical units called cells. The cells define the maximum size of a
room, as well as its position on the dungeon map. Since each cell
represents a room, the size of the cell will determine the maximum size
of the room. If the maximum room size is 10, and the dungeon is 100 x
100 tiles, then the grid will be an array of 10 x 10 cells.
The
easiest way to represent this is to create an array of a structure. The
structure would contain the upper x and y coordinates of a dungeon
tile. In the example given above, the grid would be a structure array
with 100 elements (10 x 10 cells). The program would then iterate
through the dungeon array using a step value equal to the cell size and
store the dungeon (x, y) tile position in the grid array structure.
Once
the grid is created the program can add rooms to the dungeon map.
Adding a room can be done in a variety of ways, depending on the needs
of the game. Grid cells represent rooms, both the location and maximum
size of a room, so the room building code will select a cell from the
grid, determine the size of the room (min size to grid cell size) and
draw that cell on the dungeon array using a floor, or some other
passable tile id. The grid cell will then be marked as used so the room
building code will know that the room already exists.
To prevent
overlapping rooms in the dungeon, the program should select a maximum
room size 1 tile less than the grid cell size. Using a room size equal
to the grid cell size will create open areas that can be adjusted to
create caverns and other naturalistic features.
It is easy to
see that each room will automatically fit within the dungeon array.
This eliminates quite a bit of code that is normally needed to ensure a
room will fit on the map, that a room will not overlay another room and
fit within the array boundaries.
Connecting the GridOnce
the rooms are created they can be connected in a variety of ways to
produce different styles of dungeons. For example, a flood-fill
corridor connection algorithm would create a dungeon where each room
would fan from a central seed room, requiring a lot of backtracking to
visit all the rooms. A connect this room to last room algorithm would
create a lot of corridors and rooms that have multiple doorways. The
dungeon generator could use a number of corridor building algorithms to
create a wide range of dungeon styles.
Geometric RoomsSince
a room is constrained by the cell it occupies, it is quite easy to
create rooms that are not square without worrying about whether the
room will fit on the map. The room drawing code could draw a circle or
a triangle within a grid cell and the room will automatically fit on
the map.
Generating DoorsCreating
doors for rooms is easier since the room list contains the room
dimensions within the cell. As the corridor building algorithm reaches
a room, it simply checks to see if it has reached the border of the
room. If it has, a door can be placed.
Themed DungeonsSince
the grid has a regular structure, creating themed dungeons is much
easier. Themes usually have some order to them, some sequence inherent
in the theme, and having a grid layout to help guide the theme reduces
the code necessary to build the theme.
Example CodeIn order to create the dungeon, we need to start with some data definitons.
'Size of the map. #Define mapw 100 #Define maph 100 'Grid cell size (width and height) #Define csizew 10 #Define csizeh 10 'Empty cell flag. #Define emptycell 0 'Grid dimensions. Const gw = mapw \ csizew Const gh = maph \ csizeh 'Max and min room dimensions #Define roommax 8 #Define roommin 4 'Max and min number of rooms. #Define nroommax 50 #Define nroommin 20
'Coordinates. Type mcoord x As Integer y As Integer End Type
'Room dimensions. Type rmdim rwidth As Integer rheight As Integer rcoord As mcoord End Type
'Room information Type roomtype roomdim As rmdim 'Room width and height. tl As mcoord 'Room rect. br As mcoord End Type
'Grid cell structure. Type celltype cellcoord As mcoord 'The cell position. Room As Integer 'Room id. End Type
|
Mapw and maph define the width and height of the dungeon in tile units. That is, this prticular dungeon will be 100x100 tiles.
Csizew and csizeh
are the grid cell width and height in tile units. A cell is a logical unit that will
contain a room. The cells must be larger than the room size so that a
room will fit into a cell without overlapping other rooms, unless of
course you want overlapping rooms.
The emptycell flag marks a cell as empty, that is, does not have a room in it. This flag is used when picking cells for a new room.
The Const values gw and gh
are the grid width and grid height in cells. In this dungeon, we have a
map size of 100 divided by a cell size of 10, which gives us a grid of
10 by 10 cells, or 100 cells total.
Roommax and Roommin
define the maximum and minimum number of tiles for each room. The
values represent both the width and height of a room. Since these
values are smaller than the cell size, we know that no matter how the
room is configured, it will fit inside a cell. As we will see, we can
create not just square rooms, but rectangular rooms as well.
Nroommax and nroommin
define the maximum and minimum number of rooms in the dungeon. Since we
have 100 cells to wotk with, we can easily place up to 50 rooms with no
noticable impact on performance. Increasing the grid size, will allow
even more rooms to be placed if desired.
Now that we have the data definitions in place, we can intilaize the grid.
Summary The
grid-based dungeon generator is a fast and simple way to create
dungeons. The amount of error checking code that is normally associated
with dungeon building is not needed since the rooms of the dungeon are
constrained by the cell structure of the grid. This makes the dungeon
building code smaller, faster and easier to maintain.
There is
as much freedom when using the grid as there is with a free-form
layout, without the complication. Any type of dungeon that other
dungeon building algorithms create, can be created using the grid
method, and usually much easier.
This site is © Copyright Richard D. Clark, 2010, All Rights Reserved
Website
templates
|