# Iterating over Dungeon Map

I'm working on an RPG so of course I have to have some dungeons. I've got the dungeon generation working, with the output being a DungeonTileType[][].

Now I wanted to create the code for the player to be able to enter the dungeon. To do so, I created a Dungeon class that will hold all of the information necessary for the game to work.

Here it is:

public class Dungeon {

private final Player player;
private final DungeonTileType[][] dungeonTiles;

private MapPoint startPoint;
private MapPoint endPoint;

public Dungeon(Player player, DungeonTileType[][] dungeonTiles) {
this.player = player;
this.dungeonTiles = dungeonTiles;

for (int x = 0; x < dungeonTiles.length; x++) {
DungeonTileType[] row = dungeonTiles[x];
for (int y = 0; y < row.length; y++) {
DungeonTileType type = row[y];
if (type == DungeonTileType.START) {
this.startPoint = new MapPoint(x, y);
} else if (type == DungeonTileType.END) {
this.endPoint = new MapPoint(x, y);
}
}
}

this.player.setDungeonStartPosition(this.startPoint);
}

public DungeonTileType[][] getTiles() {
return this.dungeonTiles;
}

public Player getPlayer() {
return this.player;
}

public MapPoint getStartPoint() {
return this.startPoint;
}

public MapPoint getEndPoint() {
return this.endPoint;
}
}


I'm using a maze generating algorithm as the first step for the dungeon creation, so I can make use of the start point of the maze to position the player correctly once he enters the dungeon. I could also use the end point to create stairs to another level at some point.

What I really don't like is that I cannot use for : in in this situation, because I need to have the X and Y coordinates of a given tile. One solution would be to have a DungeonTile class that keeps track of both the type and the position, but I like the simplicity of the matrix, especially when I go to serialize things. I also thought about a list of lists, because then I could use indexOf(), but again I lose the simplicity of the matrix in that situation.

I would love to get some ideas for alternative approaches.

I'm working on an RPG so of course I have to have some dungeons. I've got the dungeon generation working, with the output being a DungeonTileType[][].

Well there's your problem. To simplify eliminate the search, you should return something like this:

class Dungeon {
DungeonTileType[][] tiles;
MapPoint start;
MapPoint end;
}


Think about it, you currently have some code that generates a map that you then search through the entire map to find out where you placed that one exit and that one start tile.

When you place the start and end tiles, you should save the position that you placed them at.

As for general two dimensional looping, I wrote a Iterator for looping through 2D arrays a while ago that you can use if you'd like.

You could create a class that encapsulates the raw array.

class Tile {
MapPoint getPosition();
DungeonTileType getType();
}

class DungeonMap implements Iterable {
private DungeonTileType[][] tiles;

DungeonMap(DungeonTileType[][] tiles);
Iterator<Tile> iterator();
}


If you need more operations on the map these can be added as well, e.g. changeTile(MapPoint).

The loop in Dungeon can now be changed to this:

for (Tile tile : dungeonMap) {
if (tile.getType() == DungeonTileType.START) {
this.startPoint = tile.getPosition();
} else if (tile.getType() == DungeonTileType.END) {
this.endPoint = tile.getPosition();
}
}


How is the getTiles method used? It breaks encapsulation pretty bad. You should try to isolate the tile handling code to one class, and not have anyone depend on its current data structure.

If the dungeon is big searching through it for a specific tile will be slow ( $O(n)$ ). You can speed this up by sorting the map by type first and using a more sophisticated search algorithm.

• I don't think it's a good idea to use a Tile class in this case, that costs more than it's worth. – Simon Forsberg Sep 26 '15 at 20:05
• @SimonForsberg What does the Tile class cost? – jacwah Sep 26 '15 at 20:20
• For each tile in the Dungeon you would have to instantiate a Tile, and a MapPoint. This costs O(width * height) memory, but what do you gain from it? Absolutely nothing in this case in my opinion. – Simon Forsberg Sep 26 '15 at 20:40
• @SimonForsberg Nope. Since DungeonMap is an iterator and not a collection, it only uses constant extra memory (the size of one Tile), O(1) if you will. – jacwah Sep 26 '15 at 20:45
• Okay, then I understand how you plan on implementing that iterator, by either changing the value of the tile a whole bunch of times, or by creating a new Tile object for each call to next. Both of those options have a few drawbacks though: Re-using the same tile would lead to it being impossible to send that Tile instance onward. Creating a new Tile each time would make more work for the garbage collector and would affect performance a bit (creating many short-lived objects can be quite costly in Java). – Simon Forsberg Sep 26 '15 at 21:06