Generating Random Dungeons (part 1)

Technorati Tags: Dungeon Generation, Test-driven Development

Introduction

I have been toying around with the idea of coding a random dungeon generator for some time now. A Google search for “Dungeon Generation Algorithms” yields quite a few interesting articles on the topic. Reading about it is one thing and doing it yourself is a completely different story.

The goal of this series of articles is to describe the development process of a random dungeon generator. I also hope to touch on some agile development principles, patterns and practices.

The algorithm I will attempt to implement was developed by Jamis Buck and can be found at http://www.myth-weavers.com/generate_dungeon.php. The dungeons generated by this algorithm reminded me of my old D&D days drawing out maps using pen and paper. Please check out http://www.myth-weavers.com/generate_dungeon.php to generate some sample dungeons to get a feel for what I’m trying to achieve.

I will be limiting the scope of my first release to generating rooms, corridors and doors. I want to try and get something resembling a dungeon out quickly so that I can actually walk around in it and hopefully evolve it into a RogueLike in the future (a completely different set of articles).

I will be using Microsoft Visual Studio 2005 Professional, C#, and NUnit as my development environment, programming language and unit testing framework. I will follow the algorithm step by step describing my understanding, assumptions and design decisions. I will then dive into the actual coding and try to use a Test-driven development approach.

Algorithm Step 1

Start with a rectangular grid, x units wide and y units tall. Mark each cell in the grid unvisited.

The first step in the algorithm requires a “grid” data structure containing “cells” with an “unvisited” state. Agile development methodology states “Consider the simplest thing that could possibly work”.

Immediately I’m thinking a 2-dimensional array storing some kind of value indicating an “unvisited” state. Let’s assume that we can store the visited state using a Boolean. (I know this is really naive but that’s kind of the point). I like the idea of using a “Map” class to contain my 2-D array providing a starting point for the dungeon generator.

I start of by creating a unit test to create a map and mark each cell as unvisited. The code that satisfies this requirement would look something like this.

        [Test]

        public void TestMarkCellsUnvisited()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

 

            for(int x = 0; x < map.Width; x++)

                for(int y = 0; y < map.Height; y++)

                    Assert.IsFalse(map[x, y]);

        }

 

I compile the test and it fails as expected. We need to implement some new functionality.

First we need to implement the Map class by providing a constructor that takes as input a width and height property used to initialize an array of type boolean.

The “MarkCellsUnvisited()” method is quite straight forward to implement. All I need to do is loop through all the cells in the map (our array) and mark each location as unvisited by setting the boolean flag to “False”.

The actual test assertion yielded a requirement I did not anticipate before. I need some way of accessing the various cells in my map and I need to be able to retrieve the width and height. Using an indexer I easily hook up the required functionality to access the map cells. Get properties for Width and Height provide the last functionality required to make the test pass.

The source code for the new Map class is as follows.

    public class Map

    {

        private readonly bool[, ] cells;

 

        public Map(int width, int height)

        {

            cells = new bool[width, height];

        }

 

        public void MarkCellsUnvisited()

        {

            for (int x = 0; x < Width; x++)

                for (int y = 0; y < Height; y++)

                    cells[x, y] = false;

        }

 

        public bool this[int x, int y]

        {

            get { return cells[x, y]; }

        }

 

        public int Width

        {

            get { return cells.GetUpperBound(0) + 1; }

        }

 

        public int Height

        {

            get { return cells.GetUpperBound(1) + 1; }

        }

    }

Conclusion

The section above describes the process of evolving the design of the random dungeon generator using Test-driven development techniques. We were able to, through the unit tests; implement the simplest design that satisfies the requirements of the first step in the random dungeon generation algorithm.

In part 2 of this article series we will deal with the next few steps in the algorithm.