8
\$\begingroup\$

I've started working on a text-based adventure game that has procedurally-generated levels. I am unfamiliar with the more popular methods so I just decided to generate the dungeon using a recursive method. However, my code looks quite amateur-ish with all the if statements and I am unsure of whether or not it could run better. It also uses a lot of memory.

Here is the code for the dungeon generation:

public class Dungeon {
    private int depth;
    private ArrayList<Tile> tiles = new ArrayList<Tile>();
    private Random rand;
    
    public Dungeon(int depth) {
        this.setDepth(depth);
        rand = new Random();
        generateDungeon(depth);
    }
    /**
     * initialize starting tile
     * @param depth 
     */
    public void generateDungeon(int depth) {
        Tile temp = new Tile(0,0,new TileType(0,0),rand.nextBoolean(), rand.nextBoolean(), rand.nextBoolean(), rand.nextBoolean());
        while(!temp.hasDown() && !temp.hasUp() && !temp.hasRight() && !temp.hasLeft()) {
            temp = new Tile(0,0,new TileType(0,0),rand.nextBoolean(), rand.nextBoolean(), rand.nextBoolean(), rand.nextBoolean());
        }
        tiles.add(temp);
        generateDungeon(depth-1, temp);
    }
    /**
     * create next tile originating from last tile
     * @param depth
     * @param s
     */
    public void generateDungeon(int depth, Tile s) {
        if(depth >= 1) {
            if(s.hasDown() && !tileExists(s.getX(), s.getY()-1)) {//check if last tile has a down door and a tile directly below does not exist
                Tile temp = new Tile(s.getX(), s.getY()-1, getRandomTileType(this.depth), true, rand.nextBoolean(), rand.nextBoolean(), rand.nextBoolean());
                tiles.add(temp);
                generateDungeon(depth-1,temp);
            } else if(s.hasDown() && tileExists(s.getX(), s.getY()-1)) {// if it already exists, connect it to starting tile
                getTile(s.getX(), s.getY()-1).setUp(true);
            }
            if(s.hasUp() && !tileExists(s.getX(), s.getY()+1)) {
                Tile temp = new Tile(s.getX(), s.getY()+1, getRandomTileType(this.depth), rand.nextBoolean(), true, rand.nextBoolean(), rand.nextBoolean());
                tiles.add(temp);
                generateDungeon(depth-1,temp);
            }else if(s.hasUp() && tileExists(s.getX(), s.getY()+1)) {
                getTile(s.getX(), s.getY()+1).setDown(true);
            }
            if(s.hasLeft()&& !tileExists(s.getX()-1, s.getY())) {
                Tile temp = new Tile(s.getX()-1, s.getY(), getRandomTileType(this.depth), rand.nextBoolean(), rand.nextBoolean(), rand.nextBoolean(), true);
                tiles.add(temp);
                generateDungeon(depth-1,temp);
            }else if(s.hasLeft()&& tileExists(s.getX()-1, s.getY())) {
                getTile(s.getX()-1, s.getY()).setRight(true);
            }
            if(s.hasRight() && !tileExists(s.getX()+1, s.getY())) {
                Tile temp = new Tile(s.getX()+1, s.getY(), getRandomTileType(this.depth), true, rand.nextBoolean(), rand.nextBoolean(), rand.nextBoolean());
                tiles.add(temp);
                generateDungeon(depth-1,temp);
            }else if(s.hasRight()&& tileExists(s.getX()+1, s.getY())) {
                getTile(s.getX()+1, s.getY()).setLeft(true);
            }
        } else if(depth==0) {// this is to make sure that there are no doors leading nowhere
            if(s.hasDown() && !tileExists(s.getX(), s.getY()-1)) {
                Tile temp = new Tile(s.getX(), s.getY()-1, getRandomTileType(this.depth), true, false, false, false);
                tiles.add(temp);
            }else if(s.hasDown() && tileExists(s.getX(), s.getY()-1)) {
                getTile(s.getX(), s.getY()-1).setUp(true);
            }
            if(s.hasUp() && !tileExists(s.getX(), s.getY()+1)) {
                Tile temp = new Tile(s.getX(), s.getY()+1, getRandomTileType(this.depth), false, true, false, false);
                tiles.add(temp);
            }else if(s.hasUp() && tileExists(s.getX(), s.getY()+1)) {
                getTile(s.getX(), s.getY()+1).setDown(true);
            }
            if(s.hasLeft() && !tileExists(s.getX()-1, s.getY())) {
                Tile temp = new Tile(s.getX()-1, s.getY(), getRandomTileType(this.depth), false, false, false, true);
                tiles.add(temp);
            }else if(s.hasLeft()&& tileExists(s.getX()-1, s.getY())) {
                getTile(s.getX()-1, s.getY()).setRight(true);
            }
            if(s.hasRight()&& !tileExists(s.getX()+1, s.getY())) {
                Tile temp = new Tile(s.getX()+1, s.getY(), getRandomTileType(this.depth), false, false, true, false);
                tiles.add(temp);
            }else if(s.hasRight()&& tileExists(s.getX()+1, s.getY())) {
                getTile(s.getX()+1, s.getY()).setLeft(true);
            }
        }           
    }

    private TileType getRandomTileType(int depth) {
        double emptyFactor = -0.01 * depth*depth + 0.6 >= 0.25 ? -0.01 * depth*depth + 0.6 : 0.25;
        double enemyFactor = 0.01 * depth +0.25 <= 0.7 ? 0.01 * depth +0.25  : 0.7;
        double trapAndChestFactor = 0.1 * Math.log10(depth) <= 0.1 ? 0.1 * Math.log10(depth)  : 0.1;
        TileType empty = new TileType(1, (emptyFactor));
        TileType enemy = new TileType(2, enemyFactor);
        TileType trap = new TileType(3, trapAndChestFactor);
        TileType chest = new TileType(4, trapAndChestFactor);
        TileType[] types = {empty, enemy, trap, chest};
        
        double totalWeight = 0.0d;
        for (TileType i : types)
        {
            totalWeight += i.getW();
        }
        
        int randomIndex = -1;
        double random = Math.random() * totalWeight;
        for (int i = 0; i < types.length; ++i)
        {
            random -= types[i].getW();
            if (random <= 0.0d)
            {
                randomIndex = i;
                break;
            }
        }
        return types[randomIndex];
    }
    public int getDepth() {
        return depth;
    }


    public void setDepth(int depth) {
        this.depth = depth;
    }
    
    public Tile getTile(int x, int y) {
        for(Tile t : tiles) {
            if(t.getX() == x && t.getY() ==y) {
                return t;
            }
        }
        return new Tile(0,0,new TileType(-1,0),false,false,false,false);
    }
    public boolean tileExists(int x, int y) {
        for(Tile t : tiles) {
            if(t.getX() == x && t.getY() ==y) {
                return true;
            }
        }
        return false;
    }
    public void drawDungeon() {
        for(Tile t : tiles) {
            System.out.println("x: "+ t.getX() + " y: " + t.getY() + " type: " + t.getType() + " top door: " + t.hasUp() + " bottom door: " + t.hasDown() + " left door: " + t.hasLeft() + " right door: " + t.hasRight());
        }
    }
}

The Tile class:

public class Tile {
    private boolean up,down,left,right;
    private int x, y;
    private TileType type;
    
    public Tile(int x, int y, TileType type, boolean up, boolean down, boolean left, boolean right) {
        this.type = type;
        this.up = up;
        this.down = down;
        this.left = left;
        this.right = right;
        this.x = x;
        this.y = y;
    }

    public boolean hasUp() {
        return up;
    }

    public void setUp(boolean up) {
        this.up = up;
    }

    public boolean hasDown() {
        return down;
    }

    public void setDown(boolean down) {
        this.down = down;
    }

    public boolean hasLeft() {
        return left;
    }

    public void setLeft(boolean left) {
        this.left = left;
    }

    public boolean hasRight() {
        return right;
    }

    public void setRight(boolean right) {
        this.right = right;
    }

    public TileType getType() {
        return type;
    }

    public void setType(TileType type) {
        this.type = type;
    }

    public int getX() {
        return x;
    }

    public void setX(int x) {
        this.x = x;
    }

    public int getY() {
        return y;
    }

    public void setY(int y) {
        this.y = y;
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ @ggorlen Please do not edit code in any question that is not your own, the point of code review is to review the original posters code, not someone else's edit. \$\endgroup\$ – pacmaninbw Jul 10 at 22:10
  • 1
    \$\begingroup\$ @pacmaninbw I indented the code so that it appears correctly formatted and preserved the OP's intent. I didn't realize fixing formatting issues with displaying it correctly on the interface was forbidden. Do you have a meta reference for this? Thanks. \$\endgroup\$ – ggorlen Jul 10 at 22:13
  • 1
    \$\begingroup\$ I think you may be confused because the diff went haywire, so on quick glance it looks as if I've totally changed all of the code, but if you look closely it's just a giant Ctrl+K 4-space indent. \$\endgroup\$ – ggorlen Jul 10 at 22:26
  • 3
    \$\begingroup\$ @ggorlen You're edit looks fine to me (I use the side-by-side markdown option). Whitespace editing (in the stackoverflow style) is generally frowned upon, however where it's just fixing the whole code indentation it's usually acceptable. codereview.meta.stackexchange.com/a/6124/4203 \$\endgroup\$ – forsvarir Jul 10 at 23:04
  • 2
    \$\begingroup\$ @forsvarir Ah, that's a helpful link. Thanks. Yeah, I thought my edit abided by these rules: Ctrl+K fine but not touching anything beyond that. \$\endgroup\$ – ggorlen Jul 10 at 23:14
4
\$\begingroup\$

Some initial thoughts...

Consider your interface

The public methods of your class are the one's that you're expecting to be called from outside. Your generateDungeon methods are both marked as public. These methods don't really seem like they're designed to be called more than once. The version of generateDungeon that takes in a Tile, in particular seems like it's an internal method, so should probably be private.

Consider either having a method:

public static Dungeon generateDungeon(int depth)

Which returns a new instance of a dungeon, or having the generateDungeon reset the list of Tiles when generate is called.

Members vs Parameters

Depth seems like it is really just an input into your generation algorithm. It doesn't really seem to make sense to get the depth of the dungeon, since it doesn't tell me much. Do you need it as a property? Does it really make sense for a client to be able to call setDepth?

final

If you're not expecting a value to change after it's been constructed, consider making it final. This gives a hint to the reader that they can assume the value is constant and the compiler can help enforce this. So, for example after a tile has been constructed, does it really make sense to set the x/y/tileType? If not, then consider getting rid of the setters and making the fields final.

Tile access

At the moment, your storing your tiles in a list. When you want to find a particular tile, you iterate through the list until you find a tile with the correct x/y coordinates. This is ok with a small number of items, however it doesn't scale particularly well, so when you start getting a lot of Tiles in the list it's going to take a while. Consider using a different strategy for storing the Tiles which would allow more direct access. One approach might be to use a HashMap instead and encode a key from the x/y coordinates. Something as simple as this might work...

private HashMap<String, Tile> tiles = new HashMap<>();

public Tile getTile(int x, int y) {
    String key=x+","+y;
    return tiles.containsKey(key) ? tiles.get(key) :  new Tile(0,0,new TileType(-1,0),false,false,false,false);
}

private void addTile(Tile tile) {
    String key=tile.getX()+","+tile.getY();
    _tiles.put(key, tile);
}

You already centralise the way that you check/get the tiles. However, centralising the way that you add tiles would make it easier to change the storage method.

getRandomTileType

This method seems like it's doing a lot of work that it doesn't need to. It generates four different types of tiles and calculates weights for every single tile generated. This is dependant on the depth, however you're using the depth property, rather than the parameter depth when calling this method, so the seed passed in is always the same. All of these tiles/weights could be generated once at the beginning of the generation and reused.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Nice project, if you'll publish the full game online I'll check it out.

These are my suggestions:

Polymorphism

The class Tile can be of type Enemy, Empty, Trap or Chest. Instead of passing a TileType is better to create a subclass for each type. It's easier to extend it in the future and more readable.

Verbose constructor

The constructor of the Tile contains many parameters.

public Tile(int x, int y, TileType type, boolean up, boolean down, boolean left, boolean right) { 
    this.type = type; 
    this.up = up; 
    this.down = down; 
    this.left = left; 
    this.right = right; 
    this.x = x; 
    this.y = y; 
}

You can create another constructor with a boolean array for the sides (up, down, etc.) and initialize them to false by default.

public Tile(int x, int y) {
    this.x=x;
    this.y=y;
    // all sides are set to false by default
    this.sides=new boolean[4];
}

The type of the Tile is determined by the subclass:

public class EmptyTile extends Tile{
    
    public EmptyTile(int x, int y) {
        super(x, y);
    }
//...
}

Immutability

As @forsvarir noticed, some fields never change after the object construction and they should be set to final. For example the coordinates x and y of the Tile.

Performances

Again as pointed out by @forsvarir, iterating through the tiles every time has its cost, which is dependent on the number of tiles. Using a Map you can access the tiles in constant time.

Comments

There are some comments next to the code, which makes some line of code really long. Keep the comments on top of the code.

Dungeon creation algorithm

Yes, there are a lot of if-and-else, it took me some time to understand it. But it can be reduced with some adjustments:

  • Use an array for the sides. So that you can use a loop instead of 4 conditions like s.hasUp(), s.hasDown(), etc.
  • The top level if(depth >= 1) and else if(depth==0) differ only in not calling the function recursively, so they can be merged into one.

This is the code refactored:

public abstract class Tile {
    private final int x, y;
    private boolean[] sides;
    protected double weight;
    
    public Tile(int x, int y) {
        this.x=x;
        this.y=y;
        // all sides are set to false by default
        this.sides=new boolean[4];
    }
    
    public abstract double calculateWeight(int depth);
    
    public void openSide(Direction direction) {
        this.sides[direction.getValue()]=true;
    }
    
    public boolean hasAtLeastOneDoor() {
        return hasDown() || hasUp() || hasRight() || hasLeft();
    }
    
    public boolean hasDoorOn(Direction direction) {
        return this.sides[direction.getValue()];
    }

    public boolean hasUp() {
        return this.sides[Direction.UP.getValue()];
    }
    
    public void setSides(boolean[] sides) {
        this.sides = sides;
    }
    
    public boolean hasDown() {
        return this.sides[Direction.DOWN.getValue()];
    }

    public boolean hasLeft() {
        return this.sides[Direction.LEFT.getValue()];
    }

    public boolean hasRight() {
        return this.sides[Direction.RIGHT.getValue()];
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    public double getWeight() {
        return this.weight;
    }

    public boolean[] getSides() {
        return this.sides;
    }
    
    abstract String getType();

    @Override
    public String toString() {
        return "x: "+ getX() + " y: " + getY() + " type: "+ getType() + " top door: " + hasUp() + " bottom door: " + hasDown() + " left door: " + hasLeft() + " right door: " + hasRight() + " weight: "+ this.weight;
    }
}

The class EmptyTile:

public class EmptyTile extends Tile{
    
    public EmptyTile(int x, int y) {
        super(x, y);
    }
    
    public EmptyTile(int x, int y, int depth) {
        super(x, y);
        this.weight=calculateWeight(depth);
    }
    
    @Override
    public double calculateWeight(int depth) {
        return -0.01 * depth*depth + 0.6 >= 0.25 ? -0.01 * depth*depth + 0.6 : 0.25;
    }

    @Override
    String getType() {
        return "Empty";
    }
}

The class TrapTile:

public class TrapTile extends Tile{
    
    public TrapTile(int x, int y) {
        super(x, y);
    }

    public TrapTile(int x, int y, int depth) {
        super(x, y);
        this.weight=calculateWeight(depth);
    }
    
    @Override
    public double calculateWeight(int depth) {
        return 0.1 * Math.log10(depth) <= 0.1 ? 0.1 * Math.log10(depth)  : 0.1;
    }

    @Override
    String getType() {
        return "Trap";
    }
}

I am not including the other two EnemyTile and ChestTile because they are similar.

The class Direction:

public enum Direction {
    UP(0),
    RIGHT(1),
    DOWN(2),
    LEFT(3);
    
    private int value;
    
    Direction(int value){
        this.value=value;
    }
    
    public int getValue() {
        return this.value;
    }
    
    public static Direction of(int value) {
        return Stream.of(Direction.values())
                .filter(v -> v.getValue()==value)
                .findFirst().orElse(null);
    }
    
    public static Direction oppositeOf(Direction direction) {
        if(direction.equals(Direction.UP)) {
            return Direction.DOWN;
        }else if(direction.equals(Direction.DOWN)){
            return Direction.UP;
        }else if(direction.equals(Direction.RIGHT)) {
            return Direction.LEFT;
        }else return Direction.RIGHT;
    }
}

And finally the class Dungeon:

public class Dungeon {
    private int depth;
    private Map<String,Tile> tiles = new HashMap<>();
    private Random rand;
    
    public Dungeon(int depth) {
        this.depth=depth;
        rand = new Random();
        generateDungeon(depth);
    }
    /**
     * initialize starting tile
     * @param depth 
     */
    public void generateDungeon(int depth) {
        Tile firstTile = new EmptyTile(0,0);
        setRandomSides(firstTile);

        while(!firstTile.hasAtLeastOneDoor()) {
            setRandomSides(firstTile);
        }
        addTile(firstTile);
        generateDungeon(depth-1, firstTile);
    }
    /**
     * create next tile originating from last tile
     * @param depth
     * @param tile
     */
    private void generateDungeon(int depth, Tile tile) {
        if(depth >= 0) {
            // for every side
            for(int i=0; i<4 ;i++) {
                Direction direction = Direction.of(i);
                if(tile.hasDoorOn(direction)) {
                    // get next tile location
                    int nextX = nextXTo(tile.getX(),direction);
                    int nextY = nextYTo(tile.getY(),direction);
                    // if it already exists, connect it to starting tile
                    if(tileExists(nextX, nextY)) {
                        getTile(nextX, nextY).openSide(Direction.oppositeOf(direction));
                    }
                    else {
                        // create a random tile
                        Tile temp = getRandomTile(nextX, nextY, depth);
                        // if last tile then open side to the previous and add to tiles
                        if(depth==0) {
                            temp.openSide(Direction.oppositeOf(direction));
                            addTile(temp);
                        }
                        else {
                            setRandomSides(temp);
                            temp.openSide(Direction.oppositeOf(direction));
                            addTile(temp);
                            generateDungeon(depth-1,temp);
                        }
                    }
                }
            }
        } 
    }
    
    private int nextYTo(int y, Direction direction) {
        if(direction == Direction.UP) {
            y++;
        }else if(direction == Direction.DOWN) {
            y--;
        }
        return y;
    }
    private int nextXTo(int x, Direction direction) {
        if(direction == Direction.RIGHT) {
            x++;
        }else if(direction == Direction.LEFT) {
            x--;
        }
        return x;
    }
    
    public Tile getRandomTile(int x, int y, int depth) {
        Tile empty = new EmptyTile(x,y,depth);
        Tile enemy = new EnemyTile(x,y,depth);
        Tile trap = new TrapTile(x,y,depth);
        Tile chest = new ChestTile(x,y,depth);
        
        Tile[] tiles = {empty, enemy, trap, chest};
        double totalWeight = 0.0d;
        for (Tile i : tiles)
        {
            totalWeight += i.getWeight();
        }
        
        int randomIndex = -1;
        double random = Math.random() * totalWeight;
        for (int i = 0; i < tiles.length; ++i)
        {
            random -= tiles[i].getWeight();
            if (random <= 0.0d)
            {
                randomIndex = i;
                break;
            }
        }
        return tiles[randomIndex];
    }
    
    private void addTile(Tile tile) {
        String key=tile.getX()+","+tile.getY();
        tiles.put(key, tile);
    }
    
    private void setRandomSides(Tile tile) {
        boolean[] arr = new boolean[] {rand.nextBoolean(),rand.nextBoolean(),rand.nextBoolean(),rand.nextBoolean()};
        tile.setSides(arr);
    }

    public int getDepth() {
        return depth;
    }

    public Tile getTile(int x, int y) {
        String key=x+","+y;
        return tiles.getOrDefault(key, new EmptyTile(0,0));
    }
    
    public boolean tileExists(int x, int y) {
        String key=x+","+y;
        return tiles.containsKey(key);
    }
    public void drawDungeon() {
        tiles.forEach((k, v)-> System.out.println(v));
    }
}

Refactoring algorithms is tricky, better to have at least a test to don't introduce bugs:

@Test
public void myTest() {
    int depth = 5;
    Dungeon d = new Dungeon(depth);
    d.drawDungeon();
    for(int x=-depth; x < depth+1; x++) {
        for(int y=-depth;y < depth+1; y++) {
            if(d.tileExists(x, y)) {
                Tile t = d.getTile(x, y);
                if(t.hasDoorOn(Direction.UP)) {
                    assertTrue(d.getTile(x, y+1).hasDoorOn(Direction.DOWN));
                }else if(t.hasDoorOn(Direction.DOWN)) {
                    assertTrue(d.getTile(x, y-1).hasDoorOn(Direction.UP));
                }else if(t.hasDoorOn(Direction.RIGHT)) {
                    assertTrue(d.getTile(x+1, y).hasDoorOn(Direction.LEFT));
                }else if(t.hasDoorOn(Direction.LEFT)) {
                    assertTrue(d.getTile(x-1, y).hasDoorOn(Direction.RIGHT));
                }
            };
        }
    }
}
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.