roguelike tutorial 07: z levels and deeper caves

Our simple little roguelike is so flat and two dimensional. Let's change that. I'll try to write use code thats easy to read and understand, even if it's woefully inefficient. It's a good thing world gen only happens once.

Most roguelikes have a 2d level and just simulate the current one. When you leave the current level either a new one is created or an old one is loaded. If loading an old level then the program usually simulates the passage of time and adds some items or creatures and makes it look like things happened even though you weren't there. I find it easier just to create the entire world at once and simulate everything. This also makes world gen easier since you can make decisions based on the entire world, not just the thin slices that already exist. Our world is small enough for now that the extra time to create it and memory it takes up it shouldn't be a problem.

In order to build better caves we're going to have to work with coordinates a lot. We should make a class to represent a point in space.

package rltut;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Point {
    public int x;
    public int y;
    public int z;

    public Point(int x, int y, int z){
        this.x = x;
        this.y = y;
        this.z = z;
    }
}

Two points that represent the same location should be treated as equal. These are known as value objects as opposed to reference objects. We can tell Java that by overriding the hashCode and equals methods. Here's what Eclipse generated:

@Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + x;
        result = prime * result + y;
        result = prime * result + z;
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
         return true;
        if (obj == null)
         return false;
        if (!(obj instanceof Point))
         return false;
        Point other = (Point) obj;
        if (x != other.x)
         return false;
        if (y != other.y)
         return false;
        if (z != other.z)
         return false;
        return true;
    }

We're also going to spend a lot of time working with points that are adjacent to something. This will be much easier if we can just ask a point for a list of it's eight neighbors.

public List<point> neighbors8(){
    List<point> points = new ArrayList<point>();
  
    for (int ox = -1; ox < 2; ox++){
        for (int oy = -1; oy < 2; oy++){
            if (ox == 0 && oy == 0)
                continue;
    
            points.add(new Point(x+ox, y+oy, z));
        }
    }

    Collections.shuffle(points);
    return points;
}

We shuffle the list before returning it so we don't introduce bias. Otherwise the upper left neighbor would always be checked first and the lower right would be last which may lead to some odd things. Now that we have a Point class, let's use it to make some better caves. First we need to add two new tile types, stairs up and stairs down.

STAIRS_DOWN('>', AsciiPanel.white),
    STAIRS_UP('<', AsciiPanel.white);

Then, in the WorldBuilder class, we create a region map. Each location has a number that identifies what region of contiguous open space it belongs to; i.e. if two locations have the same region number, then you can walk from one to the other without digging through walls.

private WorldBuilder createRegions(){
        regions = new int[width][height][depth];
    
        for (int z = 0; z < depth; z++){
            for (int x = 0; x < width; x++){
                for (int y = 0; y < height; y++){
                   if (tiles[x][y][z] != Tile.WALL && regions[x][y][z] == 0){
                       int size = fillRegion(nextRegion++, x, y, z);
              
                       if (size < 25)
                           removeRegion(nextRegion - 1, z);
                   }
                }
            }
        }
        return this;
    }

This will look at every space in the world. If it is not a wall and it does not have a region assigned then that empty space, and all empty spaces it's connected to, will be given a new region number. If the region is to small it gets removed. When this method is done, all open tiles will have a region assigned to it and we can use the regions array to see if two tiles are part of the same open space.

The removeRegion method does what it sounds like. It just zero's out the region number and fills in the cave so it's solid wall. I prefer caves where the smaller areas have been filled in but this step isn't necessary.

private void removeRegion(int region, int z){
    for (int x = 0; x < width; x++){
        for (int y = 0; y < height; y++){
            if (regions[x][y][z] == region){
                regions[x][y][z] = 0;
                tiles[x][y][z] = Tile.WALL;
            }
        }
    }
}

The fillRegion method does a flood-fill starting with an open tile. It, and any open tile it's connected to, gets assigned the same region number. This is repeated until there are no unassigned empty neighboring tiles.

private int fillRegion(int region, int x, int y, int z) {
        int size = 1;
        ArrayList<Point> open = new ArrayList<Point>();
        open.add(new Point(x,y,z));
        regions[x][y][z] = region;
    
        while (!open.isEmpty()){
            Point p = open.remove(0);

            for (Point neighbor : p.neighbors8()){
                if (regions[neighbor.x][neighbor.y][neighbor.z] > 0
                  || tiles[neighbor.x][neighbor.y][neighbor.z] == Tile.WALL)
                    continue;

                size++;
                regions[neighbor.x][neighbor.y][neighbor.z] = region;
                open.add(neighbor);
            }
        }
        return size;
    }

To connect all the regions with stairs we just start at the top and connect them one layer at a time.

public WorldBuilder connectRegions(){
        for (int z = 0; z < depth-1; z++){
            connectRegionsDown(z);
        }
        return this;
    }

To connect two adjacent layers we look at each region that sits above another region. If they haven't been connected then we connect them.

private void connectRegionsDown(int z){
    List<String> connected = new ArrayList<String>();
  
    for (int x = 0; x < width; x++){
        for (int y = 0; y < height; y++){
            String region = regions[x][y][z] + "," + regions[x][y][z+1];
            if (tiles[x][y][z] == Tile.FLOOR
              && tiles[x][y][z+1] == Tile.FLOOR
              && !connected.contains(region)){
                connected.add(region);
                connectRegionsDown(z, regions[x][y][z], regions[x][y][z+1]);
            }
        }
    }
}

The region variable is just a way to uniquely combine two numbers into one. This way we just need a list of the region strings instead of some list of pairs or something. If java had tuples then we could use that instead of this way.

To connect two regions, we get a list of all the locations where one is directly above the other. Then, based on how much area overlaps, we connect them with stairs going up and stairs going down.

private void connectRegionsDown(int z, int r1, int r2){
        List<Point> candidates = findRegionOverlaps(z, r1, r2);
    
        int stairs = 0;
        do{
            Point p = candidates.remove(0);
            tiles[p.x][p.y][z] = Tile.STAIRS_DOWN;
            tiles[p.x][p.y][z+1] = Tile.STAIRS_UP;
            stairs++;
        }
        while (candidates.size() / stairs > 250);
    }

Finding which locations of two regions overlap is pretty straight forward.

public List<Point> findRegionOverlaps(int z, int r1, int r2) {
        ArrayList<Point> candidates = new ArrayList<Point>();
    
        for (int x = 0; x < width; x++){
         for (int y = 0; y < height; y++){
             if (tiles[x][y][z] == Tile.FLOOR
                  && tiles[x][y][z+1] == Tile.FLOOR
                  && regions[x][y][z] == r1
                  && regions[x][y][z+1] == r2){
              candidates.add(new Point(x,y,z));
             }
         }
        }
    
        Collections.shuffle(candidates);
        return candidates;
    }

After all that, the method for making caves needs to be amended.

public WorldBuilder makeCaves() {
        return randomizeTiles()
             .smooth(8)
             .createRegions()
             .connectRegions();
    }

The world class obviously needs to be changed. Not only does a third layer need to be added to the tiles array, but most methods need to accept a new z parameter. I'm suer you can find all the changes that need to be made. Here's an example of an updated method:

public void addAtEmptyLocation(Creature creature, int z){
        int x;
        int y;
    
        do {
         x = (int)(Math.random() * width);
         y = (int)(Math.random() * height);
        }
        while (!tile(x,y,z).isGround() || creature(x,y,z) != null);
    
        creature.x = x;
        creature.y = y;
        creature.z = z;
        creatures.add(creature);
    }

The Creature class also needs a new z coordinate and many of it's methods need to be updated too. I'll leave that to you as well. Here's my new version of the moveBy method.

public void moveBy(int mx, int my, int mz){
        Tile tile = world.tile(x+mx, y+my, z+mz);
    
        if (mz == -1){
            if (tile == Tile.STAIRS_DOWN) {
                doAction("walk up the stairs to level %d", z+mz+1);
            } else {
                doAction("try to go up but are stopped by the cave ceiling");
                return;
            }
        } else if (mz == 1){
            if (tile == Tile.STAIRS_UP) {
                doAction("walk down the stairs to level %d", z+mz+1);
            } else {
                doAction("try to go down but are stopped by the cave floor");
                return;
            }
        }
    
        Creature other = world.creature(x+mx, y+my, z+mz);
    
        if (other == null)
            ai.onEnter(x+mx, y+my, z+mz, tile);
        else
            attack(other);
    }

The CreatureAi classes, PlayScreen class, and a few others need to be updated. Your IDE should tell you which ones are broken by the new thrid dimension. You should be able to fix all of these on your own. One thing is that the greater than and less than keys used to move up and down stairs don't work with the keyCode() method so that needs to be handled differently. Here's how I did it:

switch (key.getKeyChar()){
        case '<': player.moveBy( 0, 0, -1); break;
        case '>': player.moveBy( 0, 0, 1); break;
        }

This one was a lot of work. The algorithm for creating 3d caves that are connected takes a while to explain even though each step isn't too difficult on it's own. The real bummer was having to update all the places where we were using coordinates. I suppose that if we were using a Point class from the beginning then adding a z coordinate to the Point would have required far fewer changes. Or we could have stuck to a list of 2d arrays and just tracked the current one instead of simulating a 3d world all at once. Oh well. Maybe you wont make the same mistake with the next roguelike you make.

download the code