» Home

  » FreeBasic Tutorials

  » FreeBasic Programs

  » Contact

Grid-Based Dungeon

Building a dungeon based on a grid model.

Introduction

The 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 Grid

The 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 Grid

Once 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 Rooms

Since 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 Doors

Creating 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 Dungeons

Since 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 Code

In 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