Friday, September 9, 2011

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

25 comments:

  1. This is really interesting (though I code mine in Python, I can still make reasonable sense of what you're coding here!). I'm currently re-working quite a lot of the code for my roguelike, and I'm semi-seriously considering adding a z coordinate too. Sure, it would massively increase the (already significant) time Worldgen takes; but as you say, it only happens once, and if the player is willing to wait 30 seconds, I'm sure they'll wait a little longer. Still not sure whether to add a proper z coordinate, or simply simulate many slices on top of each other. Are you going to have flying creatures, how instance, readily able to move between z coords? Or just the player/monsters at staircases, etc?

    ReplyDelete
  2. Made it this far. I think three-dimensional space is basically the best thing ever and that more roguelikes should do things with it. :P

    Anyway, do you think it'd be worthwhile to invert the order of the indices? [z][y][x] instead of [x][y][z]. It feels sort of intuitive to have them ordered width, height, depth; but with depth first, it'd be easier to move whole (x,y)-layers around. Seems that inserting a z-level into the world would come up more often that an x-slice.

    ReplyDelete
  3. @Ultima, Sorry for the long delay but I just now saw your comment. I find that a proper 3 dimensional array is far easier since moving between Z levels is no different than moving along the X or Y axis. It also means you can just update everything in the world and not worry about trying to simulate a bunch of turns when you reenter a level. If you have a very large world then it would make since to break it into chunks of, for example, 100x100x10. Those could be swapped between memory and the hard drive as needed behind the scenes.

    ReplyDelete
  4. @anon, I agree that having a realistic 3D space adds a lot. Having the Z layers be the first index would make it easier to add and remove a layer - if java allowed arrays to be resized, which it doesn't. Although I may be wrong since it's not my primary programming language. For adding and removing layers you'd need to use a List<Tile[x][y]> since you can insert and remove items in a List. It shouldn't matter too much since the only time you really access the tiles directly by index is when creating the world and through the world itself. Exactly how you represent the world should be an implementation detail that only they know about. For this project I just created it all at once but if you want to move entire layers around, then yes, the Z index does need to be handled differently. Now that you mention it, changing the Z levels as part of the game could be an interesting 7DRL....

    ReplyDelete
    Replies
    1. You can use System.arraycopy to resize arrays. Technically you can do it with Arrays.copyOf, but that only works for single dimensional arrays for some odd reason.

      Delete
  5. I've worked hard getting through this tutorial all the way here. I attempted the Z levels. I have compleated throught his tutorial but have run into problems. When i try to go up and down levels the message popes up that eaither "you go to level 2" or "you try to go up but hit the cealing." afterwhich, nothing really happens. Is this supposed to be implemented later? Where can i make more levels in my code? Where should i start to look for trouble shooting this, it is clearly not a build error but some kind of logical error i overlooked. Thanks in advanced

    ReplyDelete
    Replies
    1. I ran into this same issue and then realized I hadn't properly modified the Creature.moveBy to use the z axis and the the CreatureAi.onMove, which propagates to PlayerAi.onMove(). Make sure you have that player.z = z; and that you are passing the z axis change information!

      When I run into issues, I have been downloading Trystan's source and diffing it against what I have, and using that to locate key differences. It is really easy to miss a one line change after going through a couple dozen lines of code :)

      As an additional tip, comment the hell out of everything you put in place and make sure you understand each step of it. It takes more time, but will save you some headache.

      Delete
    2. It doesn't work for me too. No messages popes up too. I've checked my code with Trystan's one and everything looks similar.

      Delete
    3. Go to PlayerAi.java and check if you set the z value

      public void onEnter(int x, int y, int z, Tile tile){
      if (tile.isGround()){
      creature.x = x;
      creature.y = y;
      creature.z = z; <- check if this is here
      } else if (tile.isDiggable()) {
      creature.dig(x, y, z);
      }
      }

      Delete
  6. How do you change the number of stairs per level? I have stairs all over the place when I would much rather have a single up stair and a single down stair per level. I would very much appreciate any help on this, I have fiddled around with various numbers trying to alter the stair count but nothing has worked. I'm brand new to programming, so I would love any help I can get.

    ReplyDelete
  7. I feel like the z-axis is an interesting addition.
    However, it adds quite a significant amount of time to the world rendering (before it took about two seconds, now I've left it going for over 3 minutes and there's still no response >_>). I even have a pretty beefy computer.
    My thought would be to, instead of storing 5 levels in one world, send the player to another world if they go to a stairs. This way, you could limit the number of levels by counting the number of times the player has gone down/up stairs, and it would make transferring between levels easier.

    ReplyDelete
  8. So it is intended that a lot of stairs appear basically everywhere where there is floor in z and z+1? Cuz that are a lot of stairs. Also if x,y,z is a wall and x,y,z+1 is a floor and a monster spawns at x,y,z+1 you can see the monster while being on the z layer, not to mention it becomes pretty buggy with the stairs and monster spawn as well, maybe I just did something wrong in the code and I will go over it again, though I would really like to know if the way the stairs work is at least intended. Oh this behaviour holds only true while I have disabled following under Worldbuilder.createRegions()

    if (size < 25)
    removeRegion(nextRegion - 1, z);

    Because if I keep this in nearly everything becomes a wall, so that must be something on my side... but I wanted to fix stairs and fungi spawn first before I nail that one down.

    ReplyDelete
    Replies
    1. I'm guessing something isn't right with your code. It's supposed to have one stairs down for each overlapping region. So for each region on Z, and each region on Z+1 that has at least one open tile in common, there should be one and only one staircase.

      Or at least that's what this tutorial has. How you connect things is really up to you. Experiment.

      Delete
    2. Well, I found my error in WorldBUilder.createRegions()
      Where it says "regions = new int[width][height][depth]" I actually made a methodvariable called "regions" instead of altering the class one. That fixed nearly everything.

      I actually did not expect to see the blogger himself to be still active here. I gonna use this chance and ask if your blog is dead or if you moved somewhere else, because I really liked the articles I read.

      Delete
    3. Glad you found a fix!

      I haven't really felt the need to blog in a while but I wouldn't say this is dead; just a really long nap. Knowing that someone finds it useful really makes me want to start blogging again though. I've been thinking about how my AI code has changed over the years and I might write something about that.

      Delete
    4. Well, I would look forward to it! It is not just gaming-related articles but also those informative blogposts where you also put links to various informative sites like http://sourcemaking.com/ into it.

      Following your tutorial at work (I am from a country where it is not norm to go to university, instead, we kinda take on a 2-3 years paid apprenticeship at a company mixed in with some school, and my superior is really busy at the moment so he actually lets me do that, even though I have to write it in C# (or Delphi)) motivated me a lot to do my own thing ones I got the basic grisp of it. I already have an idea and it is planned out since a year, I am just a really lazy person. What I wanna say is, your tutorial really helps out not just in terms of learning but I couldn't believe I would have so much fun programming it.

      Delete
  9. Well my computer must be ancient, because I ran out of memory! Wonderful tutorial. Going to recode my project with 2d arrays, and load new dungeon data each stairwell.

    ReplyDelete
  10. Well my computer must be ancient, because I ran out of memory! Wonderful tutorial. Going to recode my project with 2d arrays, and load new dungeon data each stairwell.

    ReplyDelete
  11. If you end up with an infinite loop while executing WorldBuidler.fillRegion, check to make sure that the nextRegion instance variable was initialized to 1. This isn't covered here on this post and took me a while to figure out. Generation of a 5 level dungeon should take less than a second or two on an i5 CPU.

    ReplyDelete
  12. If you end up with an infinite loop while executing WorldBuidler.fillRegion, check to make sure that the nextRegion instance variable was initialized to 1. This isn't covered here on this post and took me a while to figure out. Generation of a 5 level dungeon should take less than a second or two on an i5 CPU.

    ReplyDelete
  13. Those are the possible values and hopefully for the future would help students to proceed further if they really wanted to get success. free on-line classifieds

    ReplyDelete
  14. I'm not sure what happened, but after this lesson I was no longer able to attack the fungi on other levels than the first. Everything is the same as the original code except the displayTiles section that you'd mentioned before for optimization, and I gave the list World.creatures a getter. Any ideas what it might be? I've combed through every file with no luck.

    ReplyDelete
  15. Never mind. I figured it out. I forgot to add depth to the displayTiles method, so I was seeing all the fungi from every level, and the ones I couldn't attack were actually on a different depth than my player. Fixed it now, thanks anyway.

    ReplyDelete
  16. You don't mention that the nextRegion and regions variables have to be declared as WorldBuilder's fields.

    Going with "go figure all the other changes by yourself" approach makes your tutorial not very applicable for beginners. Not that it was written with them in mind in the first place.

    In fillRegion method an out of bounds condition must be checked. You have it in the code to download, but not in the tutorial. Same goes for a tile getter in World class.

    ReplyDelete