roddy: (Default)
[personal profile] roddy
I received an email from a friend several days ago mentioning that he had seen my Dungeon generating code and wanted to extend the Dungeon class and add additional features. This had me looking back at my original code and realizing that, as it stands, Dungeon is not very extendible.

In this article, I will be modifying the Dungeon.java class so as to allow for better extendability, and explaining the design decisions that I make in regards to why certain aspects of the Dungeon are private rather than protected.

I would expect that people reading this article will have at least a basic understanding of inheritance in Java, and would understand what I meant about the effect of certain variables being private or protected.

Variables


The first thing I considered were my variables. I have two sets of variables in my class: a bunch of constants that restricted the size of dungeons and minimum lengths for rooms and corridors, and a bunch of class variables that saved actual dimensions, tiles, and so forth.

Constants


First let us consider our constants. In the original Dungeon, they read as follows:
private static final int MAX_X = 50;
private static final int MAX_Y = 50;
private static final int MIN_X = 10;
private static final int MIN_Y = 10;
private static final int MIN_CORRIDOR_LENGTH = 3;
private static final int MIN_ROOM_LENGTH = 3;

MAX_X and MAX_Y define the maximum dimensions of our dungeon. This was an arbitrary choice on my part, not a design restriction. MIN_X and MIN_Y were somewhat the same way, except that they had to (obviously) limit the minimum size to something greater than zero, and to something greater than the minimum corridor length. MIN_CORRIDOR_LENGTH and MIN_ROOM_LENGTH are both design decisions and programmatic ones. A corridor or room of length 1 is a single dot, which is kind of stupid because we'd end up with patchwork dungeons.

With this in mind, I removed the MAX_X and MAX_Y constants, and modified the rest of the code to reflect that.

This leaves me in a bit of a quandary for my default constructor. Previously it would have just created a dungeon of maximum dimensions, but now it needs to pick two arbitrary dimensions for x and y. Unfortunately for me, my random number generator doesn't get instantiated until later, within the init() method. So I tweaked the init() method a bit to generate random x and y values if the provided ones were undefined (-1):
private void init(int x, int y) {
    this.x = x;
    this.y = y;
    //...
    r = new Random();
    if (this.x == -1) {
        this.x = r.nextInt(500)+ MIN_X;
    }
    if (this.y == -1) {
        this.y = r.nextInt(500)+ MIN_Y;
    }
    //...
}

Here the random number generator is given an unofficial ceiling of 500 tiles in each direction. This is because the nextInt() method, with no limits, will pick a number between 0 and 232, which is a wee bit big for our dungeon.

This is still a flawed design, because 500 is hard-coded as a limit. The best way to determine the ultimate ceiling would be to run an analysis on the algorithm and determine at what point does the size-for-efficiency trade-off become sub-optimal. But until I have the time to run the analysis, we have a 500-tile ceiling.

MIN_X and MIN_Y are added to the random number to raise the floor to whatever the minimum is in that given direction.

Instance Variables


Now that we've cleaned up our constants, let's consider our instance variables. These private variables are only accessible by this class's objects, so we need to determine which ones we want to change the security to protected to make visible to child classes.

Currently we have the following instance variables defined:
private double busyness;
private int x;
private int y;

private Terrain[][] dungeonMap;

private Random r;

Determining what exactly we should make visible to children is not easy. Let us consider each variable separately.

First, r, the random number generator. Do we want child dungeons using their own random number generators, or should they use ours? If you read the documentation about java.util.Random, specifically about how it gets seeded, you'll probably decide that you really only want one random number generator to ever get used, to cut down on the chances of similarly-seeded generators picking identical numbers.

Next, dungeonMap, a mapping of tiles indicating what kind of terrain is at any given pair of coordinates. This is an integral part of our dungeon generation algorithm, and we really don't want to give children access to it. What could they possibly need access for? Setting a given tile to a particular terrain could be easily made into a protected method. This one needs to stay private.

We will consider x and y, the dimensions, together. Is there any reason to give a child class access to the dimensions themselves? Not really. They're just ints – what can child classes do with x and y that they can't do via getX() and setY()? The same is true for busyness.

Methods


Most of the methods we have are OK. We do need to make sure to add a few methods as we discussed in the previous section so that child classes can modify the tile map.

Which brings us to an interesting point. Currently, when we draw a floor, we have hard-coded a choice of Terrain.DIRT as the floor. Likewise, walls are hard-coded as Terrain.WALL. What if we wanted a stone dungeon with stone walls? Or a rich palace with bronze floors and gold walls? What if one of the child classes wants to allow for this?

This change is not as difficult as it seems. It only requires two new constants, two new instance variables, and a few tweaks to the constructors and the init method:
private static final Terrain DEFAULT_TERRAIN = Terrain.DIRT;
private static final Terrain DEFAULT_WALL = Terrain.DIRT_WALL;
    
private Terrain floor;
private Terrain wall;
    
public Dungeon() {
    init(-1, -1, DEFAULT_TERRAIN, DEFAULT_WALL);
}
    
public Dungeon(int x, int y) {
    x = x >= MIN_X ? x : MIN_X;
    y = y >= MIN_Y ? y : MIN_Y;
    init(x, y, DEFAULT_TERRAIN, DEFAULT_WALL);
}
    
public Dungeon(int x, int y, Terrain floor, Terrain wall) {
    floor = floor.isWall() ? DEFAULT_TERRAIN : floor;
    wall = wall.isWall() ? wall : DEFAULT_WALL;
    init(x,y,floor, wall);
}
    
private void init(int x, int y, Terrain floor, Terrain wall) {
    this.x = x;
    this.y = y;
    this.floor = floor;
    this.wall = wall;
    dungeonMap = new Terrain[this.x][this.y];
    //...
}

We also need to modify any references to dungeon[x][y] = Terrain.DIRT (or whatever) to instead assign this.floor. Or, even better, to use our brand-spanking-new setFloor(x,y) or setWall(x,y) methods:
protected void setFloor(int x, int y) {
    if (x < 0 || y < 0 || x > dungeonMap.length
    || y > dungeonMap[x].length) {
        return;
    }
    dungeonMap[x][y] = floor;
}
protected void setWall(int x, int y) {
    if (x < 0 || y < 0 || x > dungeonMap.length
    || y > dungeonMap[x].length) {
        return;
    }
    dungeonMap[x][y] = wall;
}

The only remaining method we'll need is one that will allow child dungeons to check if a given tile is a wall. (Previously this would be done by calling dungeonMap[x][y].isWall(), since the Terrain enum has a defined isWall method. Now, however, we have a specific tile that represents a wall in our dungeon.)
protected boolean isWall(int x, int y) {
    if (x < 0 || y < 0 || x > dungeonMap.length || y > dungeonMap[x].length) {
        return false;
    }
    return dungeonMap[x][y].equals(wall);
}


Java Code


Here is the complete Java code of an extendable Dungeon class. Feel free to use it, please understand the terms of the license before you do.
/* This work is licensed under the Creative Commons
* Attribution 3.0 Unported License. To view a copy of this
* license, visit http://creativecommons.org/licenses/by/3.0/
* or send a letter to Creative Commons, 171 Second Street,
* Suite 300, San Francisco, California, 94105, USA.
*/
package castle.dungeon;
import java.util.Random;

/**
* A simple dungeon generation class. (10 July 2010)
* @author Roddy of the Frozen Peas
* (roddyofthefrozenpeas@gmail.com)
**/
public class Dungeon {
    private static final int MIN_X = 10;
    private static final int MIN_Y = 10;
    private static final int MIN_CORRIDOR_LENGTH = 3;
    private static final int MIN_ROOM_LENGTH = 3;
    private static final Terrain DEFAULT_TERRAIN = Terrain.DIRT;
    private static final Terrain DEFAULT_WALL = Terrain.DIRT_WALL;
    
    private Terrain floor;
    private Terrain wall;
    private double busyness;
    private int x;
    private int y;
    private Terrain[][] dungeonMap;
    protected Random r;
    public Dungeon() {
        init(-1, -1, DEFAULT_TERRAIN, DEFAULT_WALL);
    }
    public Dungeon(int x, int y) {
        x = x >= MIN_X ? x : MIN_X;
        y = y >= MIN_Y ? y : MIN_Y;
        init(x, y, DEFAULT_TERRAIN, DEFAULT_WALL);
    }
    public Dungeon(int x, int y, Terrain floor, Terrain wall) {
        floor = floor.isWall() ? DEFAULT_TERRAIN : floor;
        wall = wall.isWall() ? wall : DEFAULT_WALL;
        init(x,y,floor, wall);
    }
    private void init(int x, int y, Terrain floor, Terrain wall) {
        this.x = x;
        this.y = y;
        this.floor = floor;
        this.wall = wall;
        dungeonMap = new Terrain[this.x][this.y];
        for (int i = 0; i < this.x; i++) {
            for (int j = 0; j < this.y; j++) {
                dungeonMap[i][j] = wall;
            }
        }
        r = new Random();
        if (this.x == -1) {
            this.x = r.nextInt(500)+ MIN_X;
        }
        if (this.y == -1) {
            this.y = r.nextInt(500)+ MIN_Y;
        }
        double targetBusyness = r.nextDouble();
        while (targetBusyness <= 0.55 || targetBusyness >= 0.8) {
            targetBusyness = r.nextDouble();
        }
        busyness = 0.0;
        while (busyness < targetBusyness) {
            build();
        }
    }
    private void build() {
        int x = r.nextInt(this.x);
        int y = r.nextInt(this.y);
        switch(r.nextInt(3)) {
            case 0:
                int directionX, directionY;
                do {
                    directionX = r.nextInt(3) - 1; // -1 -> 1
                    directionY = r.nextInt(3) - 1; // -1 -> 1
                } while (directionX == 0 && directionY == 0);
                int length = r.nextInt(this.x > this.y ? this.x : this.y);
                buildCorridor(x, y, directionX, directionY, length);                
                break;
            default:
                int width = r.nextInt(this.x/2);
                int height = r.nextInt(this.y/2);
                buildRoom(x,y,width,height);
                break;
        }
        evaluateBusyness();
    }
    private void evaluateBusyness() {
        int walkable = 0;
        int unwalkable = 0;
        for (int row = 0; row < dungeonMap.length; row++) {
            for (int col = 0; col < dungeonMap[row].length; col++) {
                if (dungeonMap[row][col].isWall()) {
                    unwalkable++;
                } else {
                    walkable++;
                }
            }
        }
        busyness = (1.0*walkable) / unwalkable;
    }
    private void buildCorridor (final int x, final int y, final int directionX, final int directionY, int length) {
        if (x <= 0 || y <= 0 || x >= this.x || y >= this.y) {
            return;
        }
        if (length < MIN_CORRIDOR_LENGTH) {
            return;
        }
        if (dungeonMap[x][y].isWall()) {
            return;
        }        
        int positionX = x;
        int positionY = y;
        for (int i = 0; i < MIN_CORRIDOR_LENGTH; i++) {
            positionX += directionX;
            positionY += directionY;
            if (positionX <= 0 || positionX >= this.x || positionY <= 0 || positionY >= this.y) {
                return;
            } else if (!dungeonMap[positionX][positionY].isWall() && i < MIN_CORRIDOR_LENGTH-1) {
                return;
            }
        }
        int actualLength = length;
        for (int i = MIN_CORRIDOR_LENGTH; i < length; i++) {
            positionX += directionX;
            positionY += directionY;
            if (positionX <= 0 || positionX >= this.x || positionY <= 0 || positionY >= this.y) {
                actualLength = i-1;
                i = length;
            }
        }
        positionX = x;
        positionY = y;
        for (int i = 0; i < actualLength-1; i++) {
            positionX += directionX;
            positionY += directionY;
            if (!dungeonMap[positionX][positionY].isWall()) {
                actualLength = i;
            }
        }
        positionX = x;
        positionY = y;
        for (int i = 0; i <= actualLength; i++) {
            dungeonMap[positionX][positionY] = floor;
            positionX += directionX;
            positionY += directionY;
        }
    }
    private void buildRoom(int x, int y, int width, int height) {
        if (x <= 0 || y <= 0 || width < MIN_ROOM_LENGTH || height < MIN_ROOM_LENGTH || (x + width >= this.x) || (y + height >= this.y)) {
            return;
        }
        for (int row = x+1; row < x+width; row++) {
            for (int col = y+1; col < y + height; col++) {
                if (!dungeonMap[row][col].isWall()) {
                    return;
                }
            }
        }
        int entranceCount = 0;
        for (int row = x; row <= x+width; row++) {
            for (int col = y; col <= y+height; col++) {
                if (!dungeonMap[row][col].isWall()) {
                    entranceCount++;
                }
            }
        }
        if (entranceCount > 4) {
            return;
        }
        for (int row = x; row <= x+width; row++) {
            for (int col = y; col <= y+height; col++) {
                if (dungeonMap[row][col].isWall()) {
                    dungeonMap[row][col] = floor;
                }
            }
        }
    }
    protected void setFloor(int x, int y) {
        if (x < 0 || y < 0 || x > dungeonMap.length || y > dungeonMap[x].length) {
            return;
        }
        dungeonMap[x][y] = floor;
    }
    protected void setWall(int x, int y) {
        if (x < 0 || y < 0 || x > dungeonMap.length || y > dungeonMap[x].length) {
            return;
        }
        dungeonMap[x][y] = wall;
    }
    protected boolean isWall(int x, int y) {
        if (x < 0 || y < 0 || x > dungeonMap.length || y > dungeonMap[x].length) {
            return false;
        }
        return dungeonMap[x][y].equals(wall);
    }
    
    // GETTERS AND SETTERS //
    @Override public String toString() {
        StringBuffer sb = new StringBuffer();
        for (int row = 0; row < x; row++) {
            for (Terrain t : dungeonMap[row]) {
                sb.append(t.toString());
            }
            sb.append("\n");
        }
        return sb.toString();
    }
    @Override public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null || !(obj instanceof Dungeon)) {
            return false;
        }
        Dungeon d = (Dungeon) obj;
        if (d.x != this.x || d.y != this.y) {
            return false;
        }
        if (dungeonMap.length != d.dungeonMap.length) {
            return false;
        } else {
            for (int i = 0; i < dungeonMap.length; i++) {
                if (dungeonMap[i].length != d.dungeonMap[i].length) {
                    return false;
                } else {
                    for (int j = 0; j < dungeonMap[i].length; j++) {
                        if (!(dungeonMap[i][j].equals(d.dungeonMap[i][j]))) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
    public int getX() {
        return x;
    }
    protected void setX(int x) {
        this.x = x;
    }
    public int getY() {
        return y;
    }
    protected void setY(int y) {
        this.y = y;
    }
    public Terrain[][] getDungeonMap() {
        return dungeonMap;
    }
    protected void setDungeonMap(Terrain[][] dungeonMap) {
        this.dungeonMap = dungeonMap;
    }
}


Notes


Important: This work is licensed under the Creative Commons Attribution 3.0 Unported License. To view a copy of this license, visit http://creativecommons.org/licenses/by/3.0/ or send a letter to Creative Commons, 171 Second Street, Suite 300, San Francisco, California, 94105, USA.

You are allowed to use this code, and derive your own from it, in commercial products (or otherwise), IF AND ONLY IF you leave the attribution to Roddy of the Frozen Peas (roddyofthefrozenpeas@gmail.com). Please see the specifics.

Other articles in this series:


  1. Dungeon generation

  2. Extending the dungeon (this article)

  3. Connected dungeons

Profile

roddy: (Default)
Roddy of the Frozen Peas

Expand Cut Tags

No cut tags

November 2010

S M T W T F S
 123456
78910111213
14151617181920
21222324252627
282930    

Style Credit

Tags