Connected Dungeons
Jul. 15th, 2010 11:21 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
roddyIn previous articles, we developed a rudimentary dungeon generating program that would build a simple dungeon of rectangular rooms and straight hallways. Through the use of a random number generator, we were able to build rooms at randomly (or pseudo-randomly) chosen locations throughout the map. This random room placement ensured that no two dungeons would be alike, but it also ensured that we would, at times, generate dungeons where not all rooms and corridors were connected or accessible.
In practical terms, this is not necessarily a bad thing. Some games have traps that include trap doors that drop you into a pit of monsters (and treasure). Alternatively, a dungeon level might have multiple sets of stairs, each leading to a different part of the next level, or perhaps skipping the next level entirely. Throne rooms, prisons, panic rooms, treasure troves – there are numerous possibilities for an unconnected dungeon.
But what if we want a plain old fully-connected dungeon, where we can start at any point A and travel to any other point B?
This article discusses the concept of a connected dungeon, where every part of the dungeon is accessible from every other part. We will discuss the concepts behind connectivity, and develop an algorithm for connecting an unconnected dungeon. We will be extending the original dungeon generating class developed in previous articles.
At the highest level, our algorithm will need to proceed as follows:
The first thing on our agenda is developing a way to determine the connected state of our dungeon. Imagine for a moment that we are actually dealing with a real stone dungeon. If this were the case, we'd arbitrarily pick a room and begin filling it with water. When the room was full, we'd look over the dungeon and see if there was any part not flooded. If all the rooms were flooded, the dungeon would be fully connected. Otherwise, the remaining dry areas are inaccessible from our chosen starting point.
Unfortunately we're not dealing with water and stone dungeons; we're dealing with an abstract programming concept. Up until now, we've been mapping out our dungeon on a two dimensional array of elements of the Terrain enum called dungeonMap. Since connectivity is an abstract concept – more so than terrain, at least – we'll want a new two-dimensional array to track different disjoint areas. We'll call our new two-dimensional int array connectivityMap.
At a high level, the idea is as follows. First, we instantiate a two-dimensional int array with the same dimensions as our dungeonMap tile array. Next, we map every wall in dungeonMap to a 0 in connectivityMap, and every “walkable” tile to a 1. Third, we pick an arbitrary walkable (ex. connectivityMap[x][y] = 1) point and recursively fill it and all adjacent points that are also walkable with the number 2. Then we analyze the connectivityMap: if any 1's remain, then the dungeon is not connected.
Now we need to connect our two disjointed areas. Our connectivityMap has labeled all the coordinates in area A as 1, and all coordinates in area B as 2. We need to calculate the shortest path between these two coordinate clouds, and then draw a connecting corridor between them. The specific algorithms for these concepts will be discussed in a later section. Repeat until the dungeon is no longer unconnected.
Considering the high level explanation we just finished, let us consider the requirements of our new ConnectedDungeon class.
Since we don't know how many disjointed areas there are in our dungeon, we'll probably need to run a while-loop constructed as follows:
Unfortunately for us, the isConnected method isn't quite as simple as it might be. Since we determine connectivity by filling the dungeon with water, we'll need to write the fillMap method first.
Our entire algorithm depends on our ability to fill our metaphorical dungeon with metaphorical water and see which areas remain metaphorically dry. Let's see if we can move away from the English-major-terms and into some hard code.
First let us consider what we're doing at a not-quite-as-high-as-the-water-in-the-dungeon level. At this point, we have a pre-constructed dungeon that has a mapping of terrain tiles called dungeonMap. We also have a mapping of walls-and-floors called connectivityMap, that has a 0 for a wall and a 1 for a floor. We also have an initialized random number generator.
The first thing we will need to do is pick a random piece of floor in our dungeon. This can be simply done with our random number generator, r, from the original Dungeon class. We'll just keep picking random points until we manage to choose a pair that is not a wall:
Now that we have a location, we can start filling the room, and all connecting areas, with water. In this case, we will map the number 2 to every position on connectivityMap. This concept lends itself particularly well to a recursive algorithm, so we'll create a new method, fillFromPoint, to do this:
The fillFromPoint point method is hinging on the fact that connectivityMap will only have mapped 0 and 1. If we run fillFromPoint twice in a row, we might end up with a map of 0's and 2's, which would make it completely useless. So before fillMap calls fillFromPoint, we'll need to ensure that connectivityMap has been reset to its base state.
So for that we'll need three methods: a reset method, an initialization method (to set connectivityMap to its base state), and a method to check that it is still in its base state.
We've now got enough to finalize our fillMap method. It is almost anticlimactically simple:
With the fillMap and hasTwoGroups methods, we now have enough of a framework to build our isConnected method. Really, all it does is call fillMap, and then check if it has two groups (ie: two unconnected areas.) It is arguably even less impressive than the fillMap method.
Yes, that really is all there is to it.
So now that we know for certain if there are disconnected areas, we need a way to join up those areas. We should assume that, at this point, we do in fact have a disconnected dungeon, and we also have a connectivityMap consisting of 0's for walls, and 1's and 2's respectively for disjointed areas. Since connectivityMap is a two-dimensional array, we can now consider each of those locations as coordinates on a Cartesian (x-y) plane.
Before we go much further, we'll need to digress to a semi-related topic: the shortest path between those areas.
One of the most difficult courses on a college Computer Science curriculum is the algorithms course. It's one thing to whip up a program to do something, but are you doing it in the most efficient way possible? If we increase the number of inputs, will it work in a reasonable time? If we build a 10,000 x 10,000 dungeon, will we have to wait six hours for it to finish? Will it even finish?
The concept of dungeon building seems almost pre-made for this kind of course. Just to build the simplest dungeon we had to make decisions. It's one thing for a human to make a decision based on a set of facts, but a whole other thing for a machine to do it. Decision making is one of the core precepts of higher-level programming. What is artificial intelligence, after all, but a machine making decisions?
I have yet to encounter an algorithms book or class which doesn't even make mention of the shortest path problem. It is an integral and elementary aspect of graph theory: given a set of connected points, find the shortest path between point A and point B. The graph might be weighted – that is, each connection has some “value” – or directed – each connection is a single direction – or any of a dozen other permutations on the same problem. Ever wonder how MapQuest or Google Maps worked? This is the basic idea behind it.
What we have is a slightly more difficult problem. We have two abstract “areas” and we need to find the shortest path between them. It is an extension of the classic “Traveling Salesman Problem:” given a bunch of cities, find the most efficient way to visit every single city exactly once. For five cities, no problem; for 10,000, on the other hand...
Unfortunately for us, the Traveling Salesman Problem is what we call NP-complete. Wikipedia has a decent overview of the topic, but at its most basic, an NP-complete problem has no easy “right” solution, and it can be verified in polynomial time (ex, with 1 input, 1 time; with 10 inputs, 100 time; with 100 inputs, 10,000 time, etc; or worse; this is an example of binomial time.) Since there is no ready-made solution, and since this is not an algorithms class, we are going to approach this problem in a brute-force manner and use a greedy algorithm.
Let us first consider our two “areas” that we want to find the shortest-path from. Instead of considering random blobs on a map, we'll need to write out the coordinates of every point within each of those areas. Now, since we're doing a brute-force approach and not something super fancy, we're going to take every single point in group A and compare it to every single point in group B, and then find the shortest distance from all of those and save it.
Our shortest-path method, then, will need to take two int[][] arrays representing the each area's points. (The arrays should be arranged such that if point (1,2) were the first point in the array, it would be stored as a[0][0] = 1, a[0][1] = 2.) Our shortest-path method, then, will look as follows:
If we were dealing with arbitrary points in space, we might use a distance formula such as
We will therefore need to determine tile distance, rather than exact distance. That is, how many tiles apart are points A and B?
Conceptually speaking, travel by tile can be either horizontal, vertical, diagonal, or a combination of two of these. Therefore our getTileDistance method will need to consider all of these possibilities. If all coordinates (x1, y1) and (x2, y2) are equal to their counterparts, that is x1=x2 and so on, then we don't need to do anything because the shortest path from point A to itself is staying right where we are. On the other hand, if x1=x2 but the y-coordinates are different, they we need to draw a vertical path. And if y1=y2 and the x-coordinates are different, we we need a horizontal path. It is when none of these coordinate pairs are equal that we need to worry about diagonals and combinations.
In this case, we will need to know the difference between the x and y values – the Δx and Δy. This is simply subtracting x1 from x2 and taking the absolute value of the result (or y1 from y2 for Δy). If the two delta values are equal, Δx = Δy, then we have a situation where we can draw a true 1:1 diagonal – (x1, y1) → (x1+1, y1+1) → … → (x2-1, y2-1) → (x2, y2). Otherwise the tile distance is the greater of the two delta values.
For example, consider point A at (0, 0) and point B at (1, 2). Δx is 1 – 0 = 1. Δy is 2 – 0 = 2. To get from point A to point B we might first move vertically, then diagonally. Or diagonally, then vertically. Two steps total.
Now we know the length of the shortest path, as well as the location of it. Using this information, we can now determine the actual shortest path. My shortest path algorithm isn't too complicated, nor does it create very interesting corridors. For the sake of simplicity, it only creates straight paths.
Our getShortestPath method will be returning a two-dimensional int array as I previously described above. For example, if the first two points in the array are (0, 1) and (1, 2), they'd be stored as such:
A quick note: we've already defined a getShortestPath method, but this is a different getShortestPath method. This method is a static method in our PathUtil utility class, whereas the other getShortestPath method is a private helper method within the ConnectedDungeon class.
Once again, we have the base case of (x1, y1) being equal to (x2, y2). In this case, we need to return null. We also have to trap for bad inputs, such as negative x or y values.
Next we have to determine the x- and y-directions. Why? Because if x1 = x2, then we need to build a vertical path, but otherwise we need to know if we're building an upward or downward trending path. In order to avoid redundant code, I've defined a getDir method:
Now back to the getShortestPath method. Now that we have the x- and y-directions, we can tell the program to build either a horizontal, vertical, or diagonal path:
First let us consider the buildVerticalPath method. Since there will be no change in horizontal position, all it needs to do this task is the initial (x1, y1) coordinates, and the final y2-coordinate.
The most difficult of the build paths is buildDiagonalPath. As you might have noticed in the original getShortestPath method, we pass buildDiagonalPath the original (x1, y1) coordinates, as well as the Δx and Δy values.
The first thing we do, as usual, is check for the case where the initial coordinate is the same as the end coordinate. In this case, that involves seeing if both Δx and Δy equal 0.
Next we check to see if we're building what I've been calling a “true” diagonal path – equal deltas, with a ±1 change to each coordinate between subsequent points. This is the easiest diagonal to deal with, since we're just adding or subtracting 1 to each component of the previous point.
If we don't have a true diagonal, we're going to have to build a two-part path, as discussed several sections back. First, we determine which is greater, Δx or Δy. This will allow us to determine if we're building a horizontal or vertical segment first.
Now that we know which is greater, we build that horizontal or vertical segment. This code seems a bit convoluted, but what is basically happening is that if diffX happens to be Δx, it is assigned the value of either -1 or 1, depending on whether Δx is greater than or less than 0; otherwise it is assigned a 0. The same happens to diffY. Then we run a for-loop that runs from 0 to greater (which in the previous code segment is initialized to the greater of Δx and Δy). For each iteration of the for-loop we assign a point, and then increment x and y by diffX and diffY respectively.
Next we build the diagonal part of the path and return the overall result.
Now that we've got our path-drawing utility methods defined, we can finish joining up our disconnected areas. Recall that at this point we have a connectivityMap of 0's, 1's and 2's.
We've got a helper class to determine the shortest path, but it requires an array of coordinates for each disconnected area. So the first thing we need to do is generate those coordinate arrays.
Now that we've got those coordinate arrays, it's just a simple matter of calling getShortest path, and then iterating through the resultant coordinate array to draw the path.
PathUtil.java
ConnectedDungeon.java
As I mentioned previously, my shortest path methodologies are no the most sophisticated, nor is my method of linking up disjointed areas. Both of these areas could see some improvement, but they work as they currently stand.
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.
In practical terms, this is not necessarily a bad thing. Some games have traps that include trap doors that drop you into a pit of monsters (and treasure). Alternatively, a dungeon level might have multiple sets of stairs, each leading to a different part of the next level, or perhaps skipping the next level entirely. Throne rooms, prisons, panic rooms, treasure troves – there are numerous possibilities for an unconnected dungeon.
But what if we want a plain old fully-connected dungeon, where we can start at any point A and travel to any other point B?
This article discusses the concept of a connected dungeon, where every part of the dungeon is accessible from every other part. We will discuss the concepts behind connectivity, and develop an algorithm for connecting an unconnected dungeon. We will be extending the original dungeon generating class developed in previous articles.
The algorithm
At the highest level, our algorithm will need to proceed as follows:
- Determine if the dungeon is unconnected. If it is, continue.
- Locate two unconnected areas, A and B.
- Find the closest location between A and B and draw a corridor between those points, in a sort of extended shortest-path scenario.
- Repeat until the dungeon is no longer un-connected.
Determining connectivity
The first thing on our agenda is developing a way to determine the connected state of our dungeon. Imagine for a moment that we are actually dealing with a real stone dungeon. If this were the case, we'd arbitrarily pick a room and begin filling it with water. When the room was full, we'd look over the dungeon and see if there was any part not flooded. If all the rooms were flooded, the dungeon would be fully connected. Otherwise, the remaining dry areas are inaccessible from our chosen starting point.
Unfortunately we're not dealing with water and stone dungeons; we're dealing with an abstract programming concept. Up until now, we've been mapping out our dungeon on a two dimensional array of elements of the Terrain enum called dungeonMap. Since connectivity is an abstract concept – more so than terrain, at least – we'll want a new two-dimensional array to track different disjoint areas. We'll call our new two-dimensional int array connectivityMap.
At a high level, the idea is as follows. First, we instantiate a two-dimensional int array with the same dimensions as our dungeonMap tile array. Next, we map every wall in dungeonMap to a 0 in connectivityMap, and every “walkable” tile to a 1. Third, we pick an arbitrary walkable (ex. connectivityMap[x][y] = 1) point and recursively fill it and all adjacent points that are also walkable with the number 2. Then we analyze the connectivityMap: if any 1's remain, then the dungeon is not connected.
Now we need to connect our two disjointed areas. Our connectivityMap has labeled all the coordinates in area A as 1, and all coordinates in area B as 2. We need to calculate the shortest path between these two coordinate clouds, and then draw a connecting corridor between them. The specific algorithms for these concepts will be discussed in a later section. Repeat until the dungeon is no longer unconnected.
Considering the high level explanation we just finished, let us consider the requirements of our new ConnectedDungeon class.
- A two-dimensional integer array for mapping connected areas
- An isConnected() method to determine if a dungeon is connected
- A fillMap() method to “fill” a dungeon with “water” and identify disjointed areas
- A joinMap() method to physically join up two disjoint areas
- Methods for determining minimum distance between two groups and optimal corridor placement, for use by joinMap().
Since we don't know how many disjointed areas there are in our dungeon, we'll probably need to run a while-loop constructed as follows:
while (!isConnected()) {
joinMap();
}Unfortunately for us, the isConnected method isn't quite as simple as it might be. Since we determine connectivity by filling the dungeon with water, we'll need to write the fillMap method first.
The Floodgates
Our entire algorithm depends on our ability to fill our metaphorical dungeon with metaphorical water and see which areas remain metaphorically dry. Let's see if we can move away from the English-major-terms and into some hard code.
First let us consider what we're doing at a not-quite-as-high-as-the-water-in-the-dungeon level. At this point, we have a pre-constructed dungeon that has a mapping of terrain tiles called dungeonMap. We also have a mapping of walls-and-floors called connectivityMap, that has a 0 for a wall and a 1 for a floor. We also have an initialized random number generator.
The first thing we will need to do is pick a random piece of floor in our dungeon. This can be simply done with our random number generator, r, from the original Dungeon class. We'll just keep picking random points until we manage to choose a pair that is not a wall:
int x, y;
do {
x = r.nextInt(getX());
y = r.nextInt(getY());
} while (isWall(x,y));Now that we have a location, we can start filling the room, and all connecting areas, with water. In this case, we will map the number 2 to every position on connectivityMap. This concept lends itself particularly well to a recursive algorithm, so we'll create a new method, fillFromPoint, to do this:
private void fillFromPoint(final int x, final int y) {
if (x < 0 || y < 0 || x >= getX() || y >= getY() || isWall(x,y) || connectivityMap[x][y] != 1) {
return;
}
connectivityMap[x][y] = 2;
fillFromPoint(x, y-1);
fillFromPoint(x, y+1);
fillFromPoint(x-1, y);
fillFromPoint(x+1, y);
fillFromPoint(x+1, y+1);
fillFromPoint(x+1, y-1);
fillFromPoint(x-1, y-1);
fillFromPoint(x-1, y+1);
}The fillFromPoint point method is hinging on the fact that connectivityMap will only have mapped 0 and 1. If we run fillFromPoint twice in a row, we might end up with a map of 0's and 2's, which would make it completely useless. So before fillMap calls fillFromPoint, we'll need to ensure that connectivityMap has been reset to its base state.
So for that we'll need three methods: a reset method, an initialization method (to set connectivityMap to its base state), and a method to check that it is still in its base state.
private void resetConnectivityMap() {
if (hasTwoGroups()) {
initConnectivityMap();
}
}
private boolean hasTwoGroups() {
boolean hasOne = false, hasTwo = false;
for (int i = 0; i < getX(); i++) {
for (int j = 0; j < getY(); j++) {
if (hasOne && hasTwo) {
return true;
}
if (connectivityMap[i][j] == 2 && !hasTwo) {
hasTwo = true;
} else if (connectivityMap[i][j] == 1 && !hasOne) {
hasOne = true;
}
}
}
return hasOne && hasTwo;
}
private void initConnectivityMap() {
for (int i = 0; i < getX(); i ++) {
for (int j = 0; j < getY(); j++) {
if (isWall(i,j)) {
connectivityMap[i][j] = 0;
} else {
connectivityMap[i][j] = 1;
}
}
}
}We've now got enough to finalize our fillMap method. It is almost anticlimactically simple:
private void fillMap() {
int x, y;
do {
x = r.nextInt(getX());
y = r.nextInt(getY());
} while (isWall(x,y));
resetConnectivityMap();
fillFromPoint(x,y);
}The Dry Spots
With the fillMap and hasTwoGroups methods, we now have enough of a framework to build our isConnected method. Really, all it does is call fillMap, and then check if it has two groups (ie: two unconnected areas.) It is arguably even less impressive than the fillMap method.
private boolean isConnected() {
fillMap();
return hasTwoGroups();
}Yes, that really is all there is to it.
Join It Up
So now that we know for certain if there are disconnected areas, we need a way to join up those areas. We should assume that, at this point, we do in fact have a disconnected dungeon, and we also have a connectivityMap consisting of 0's for walls, and 1's and 2's respectively for disjointed areas. Since connectivityMap is a two-dimensional array, we can now consider each of those locations as coordinates on a Cartesian (x-y) plane.
Before we go much further, we'll need to digress to a semi-related topic: the shortest path between those areas.
The shortest path
One of the most difficult courses on a college Computer Science curriculum is the algorithms course. It's one thing to whip up a program to do something, but are you doing it in the most efficient way possible? If we increase the number of inputs, will it work in a reasonable time? If we build a 10,000 x 10,000 dungeon, will we have to wait six hours for it to finish? Will it even finish?
The concept of dungeon building seems almost pre-made for this kind of course. Just to build the simplest dungeon we had to make decisions. It's one thing for a human to make a decision based on a set of facts, but a whole other thing for a machine to do it. Decision making is one of the core precepts of higher-level programming. What is artificial intelligence, after all, but a machine making decisions?
I have yet to encounter an algorithms book or class which doesn't even make mention of the shortest path problem. It is an integral and elementary aspect of graph theory: given a set of connected points, find the shortest path between point A and point B. The graph might be weighted – that is, each connection has some “value” – or directed – each connection is a single direction – or any of a dozen other permutations on the same problem. Ever wonder how MapQuest or Google Maps worked? This is the basic idea behind it.
What we have is a slightly more difficult problem. We have two abstract “areas” and we need to find the shortest path between them. It is an extension of the classic “Traveling Salesman Problem:” given a bunch of cities, find the most efficient way to visit every single city exactly once. For five cities, no problem; for 10,000, on the other hand...
Unfortunately for us, the Traveling Salesman Problem is what we call NP-complete. Wikipedia has a decent overview of the topic, but at its most basic, an NP-complete problem has no easy “right” solution, and it can be verified in polynomial time (ex, with 1 input, 1 time; with 10 inputs, 100 time; with 100 inputs, 10,000 time, etc; or worse; this is an example of binomial time.) Since there is no ready-made solution, and since this is not an algorithms class, we are going to approach this problem in a brute-force manner and use a greedy algorithm.
Let us first consider our two “areas” that we want to find the shortest-path from. Instead of considering random blobs on a map, we'll need to write out the coordinates of every point within each of those areas. Now, since we're doing a brute-force approach and not something super fancy, we're going to take every single point in group A and compare it to every single point in group B, and then find the shortest distance from all of those and save it.
Our shortest-path method, then, will need to take two int[][] arrays representing the each area's points. (The arrays should be arranged such that if point (1,2) were the first point in the array, it would be stored as a[0][0] = 1, a[0][1] = 2.) Our shortest-path method, then, will look as follows:
private int[][] getShortestPath(int[][] aGroup, int[][] bGroup) {
if (aGroup.length == 0 || bGroup.length == 0 || aGroup[0].length != 2 || bGroup[0].length != 2) {
return null;
}
int minDist = Integer.MAX_VALUE;
int closestA = -1, closestB = -1;
for (int a = 0; a < aGroup.length; a++) {
int x1 = aGroup[a][0];
int y1 = aGroup[a][1];
for (int b = 0; b < bGroup.length; b++) {
int x2 = bGroup[b][0];
int y2 = bGroup[b][1];
int distance = PathUtil.getTileDistance(x1, y1, x2, y2);
if (distance < minDist) {
closestA = a;
closestB = b;
minDist = distance;
}
}
}
if (closestA < 0 || closestB < 0 || closestA > aGroup.length || closestB > bGroup.length) {
return null;
}
int x1 = aGroup[closestA][0];
int y1 = aGroup[closestA][1];
int x2 = bGroup[closestB][0];
int y2 = bGroup[closestB][1];
return PathUtil.getShortestPath(x1, y1, x2, y2);
}Notice that our method depends on two static methods in PathUtil: getTileDistance and getShortestPath. We will discuss those in the next two sections. I've created the PathUtil class to hold useful static methods for calculating paths. In the future it might also hold methods for figuring out the fastest route from point A to point B, so that you can have super efficient monsters that track you down and slay you. But we might be getting ahead or ourselves in this matter.Tile Distance
If we were dealing with arbitrary points in space, we might use a distance formula such as
We will therefore need to determine tile distance, rather than exact distance. That is, how many tiles apart are points A and B?
Conceptually speaking, travel by tile can be either horizontal, vertical, diagonal, or a combination of two of these. Therefore our getTileDistance method will need to consider all of these possibilities. If all coordinates (x1, y1) and (x2, y2) are equal to their counterparts, that is x1=x2 and so on, then we don't need to do anything because the shortest path from point A to itself is staying right where we are. On the other hand, if x1=x2 but the y-coordinates are different, they we need to draw a vertical path. And if y1=y2 and the x-coordinates are different, we we need a horizontal path. It is when none of these coordinate pairs are equal that we need to worry about diagonals and combinations.
In this case, we will need to know the difference between the x and y values – the Δx and Δy. This is simply subtracting x1 from x2 and taking the absolute value of the result (or y1 from y2 for Δy). If the two delta values are equal, Δx = Δy, then we have a situation where we can draw a true 1:1 diagonal – (x1, y1) → (x1+1, y1+1) → … → (x2-1, y2-1) → (x2, y2). Otherwise the tile distance is the greater of the two delta values.
public static int getTileDistance(int x1, int y1, int x2, int y2) {
if (x1 == x2 && y1 == y2) {
return 0;
} else if (x1 == x2) {
return Math.abs(y1-y2);
} else if (y1 == y2) {
return Math.abs(x1-x2);
} else {
int xDelta = getDelta(x1, x2);
int yDelta = getDelta(y1, y2);
if (xDelta == yDelta) { // true diagonal
return xDelta;
}
return Math.max(xDelta, yDelta);
}
}The final diagonal length, the maximum of the two deltas, is not entirely intuitive. Consider, however, that what I've been calling a “true” diagonal is actually the hypotenuse of a bilateral triangle; that is, the vertical gain (or loss) is equal to the horizontal gain (or loss.) In order to draw any other diagonal, we find the difference between those gain/losses, the deltas, and equalize them.For example, consider point A at (0, 0) and point B at (1, 2). Δx is 1 – 0 = 1. Δy is 2 – 0 = 2. To get from point A to point B we might first move vertically, then diagonally. Or diagonally, then vertically. Two steps total.
The shortest path (pt 2)
Now we know the length of the shortest path, as well as the location of it. Using this information, we can now determine the actual shortest path. My shortest path algorithm isn't too complicated, nor does it create very interesting corridors. For the sake of simplicity, it only creates straight paths.
Our getShortestPath method will be returning a two-dimensional int array as I previously described above. For example, if the first two points in the array are (0, 1) and (1, 2), they'd be stored as such:
// (0,1)
path[0][0] = 0;
path[0][1] = 1;
// (1,2)
path[1][0] = 1;
path[1][1] = 2;The idea is that the first index refers to which element (first, second, etc) on the path it is; then the int[] array at that index is the two-dimensional representation of that point.A quick note: we've already defined a getShortestPath method, but this is a different getShortestPath method. This method is a static method in our PathUtil utility class, whereas the other getShortestPath method is a private helper method within the ConnectedDungeon class.
Once again, we have the base case of (x1, y1) being equal to (x2, y2). In this case, we need to return null. We also have to trap for bad inputs, such as negative x or y values.
if (x1 == x2 && y1 == y2) {
return null;
}
if (x1 < 0 || x2 < 0 || y1 < 0 || y2 < 0) {
return null;
}Next we have to determine the x- and y-directions. Why? Because if x1 = x2, then we need to build a vertical path, but otherwise we need to know if we're building an upward or downward trending path. In order to avoid redundant code, I've defined a getDir method:
private static int getDir(int start, int end) {
if (start == end) {
return 0;
} else if (start < end) {
return 1;
}
return -1;
}private static int getDir(int start, int end) {
if (start == end) {
return 0;
} else if (start < end) {
return 1;
}
return -1;
}Now back to the getShortestPath method. Now that we have the x- and y-directions, we can tell the program to build either a horizontal, vertical, or diagonal path:
// determine the x direction
int xDir = getDir(x1, x2);
int yDir = getDir(y1, y2);
if (xDir == 0) {
return buildVerticalPath(x1, y1, y2);
} else if (yDir == 0) {
return buildHorizontalPath(y1, x1, x2);
} else {
int xDelta = getDelta(x1, x2);
int yDelta = getDelta(y1, y2);
return buildDiagonal(x1, y1, xDelta, yDelta);
}Yes! More utility methods. Because I am a big proponent of separation of purposes.First let us consider the buildVerticalPath method. Since there will be no change in horizontal position, all it needs to do this task is the initial (x1, y1) coordinates, and the final y2-coordinate.
private static int[][] buildVerticalPath(final int x, final int y1, final int y2) {
if (y1 == y2) {
return null;
}
int[][] path;
if (y2 > y1) {
path = new int[y2-y1][];
} else {
path = new int[y1-y2][];
}
int currentY = y1;
for (int i = 0; i < path.length; i++) {
path[i] = new int[2];
path[i][0] = x;
path[i][1] = currentY;
currentY++;
}
if (y1 > y2) {
currentY = y1;
for (int i = 0; i < path.length; i++) {
path[i][1] = currentY;
currentY--;
}
}
return path;
}The method initially assumes that the final y2 position will be at some point greater than y1. If that's not the case, the last if-statement is intended to invert the coordinates. The buildHorizontalPath is identical to the buildVerticalPath method, except that it deals with a varying x-coordinate rather than a varying y.The most difficult of the build paths is buildDiagonalPath. As you might have noticed in the original getShortestPath method, we pass buildDiagonalPath the original (x1, y1) coordinates, as well as the Δx and Δy values.
The first thing we do, as usual, is check for the case where the initial coordinate is the same as the end coordinate. In this case, that involves seeing if both Δx and Δy equal 0.
if (xDelta == 0 && yDelta == 0) {
return null;
}Next we check to see if we're building what I've been calling a “true” diagonal path – equal deltas, with a ±1 change to each coordinate between subsequent points. This is the easiest diagonal to deal with, since we're just adding or subtracting 1 to each component of the previous point.
if (xDelta == yDelta) { // true diagonal
int diff = (xDelta < 0) ? -1 : 1;
int[][] path = new int[xDelta][];
for (int i = 0; i < xDelta; i++) {
path[i] = new int[2];
path[i][0] = x;
path[i][1] = y;
x += diff;
y += diff;
}
return path;
}If we don't have a true diagonal, we're going to have to build a two-part path, as discussed several sections back. First, we determine which is greater, Δx or Δy. This will allow us to determine if we're building a horizontal or vertical segment first.
int greater = xDelta > yDelta ? xDelta : yDelta;
int[][] path = new int[greater][2];Now that we know which is greater, we build that horizontal or vertical segment. This code seems a bit convoluted, but what is basically happening is that if diffX happens to be Δx, it is assigned the value of either -1 or 1, depending on whether Δx is greater than or less than 0; otherwise it is assigned a 0. The same happens to diffY. Then we run a for-loop that runs from 0 to greater (which in the previous code segment is initialized to the greater of Δx and Δy). For each iteration of the for-loop we assign a point, and then increment x and y by diffX and diffY respectively.
int i=0;
int diffX = (greater == xDelta ? (xDelta < 0 ? -1 : 1) : 0);
int diffY = (greater == yDelta ? (yDelta < 0 ? -1 : 1) : 0);
for (; i < greater; i++) {
path[i][0] = x;
path[i][1] = y;
x += diffX;
y += diffY;
}Next we build the diagonal part of the path and return the overall result.
diffX = xDelta < 0 ? -1 : 1;
diffY = yDelta < 0 ? -1 : 1;
for (; i < greater; i++) {
path[i][0] = x;
path[i][1] = y;
x += diffX;
y += diffY;
}
return path;
}Joining it up, part 2
Now that we've got our path-drawing utility methods defined, we can finish joining up our disconnected areas. Recall that at this point we have a connectivityMap of 0's, 1's and 2's.
We've got a helper class to determine the shortest path, but it requires an array of coordinates for each disconnected area. So the first thing we need to do is generate those coordinate arrays.
private void joinMap() {
int aCount = 0;
int bCount = 0;
for (int i =0; i < getX(); i++) {
for (int j = 0; j < getY(); j++) {
if (connectivityMap[i][j] == 1) {
aCount++;
} else if (connectivityMap[i][j] == 2) {
bCount++;
}
}
}
int[][] aGroup = new int[aCount][2];
int[][] bGroup = new int[bCount][2];
aCount = bCount = 0;
for (int i = 0; i < getX(); i++) {
for (int j = 0; j < getY(); j++) {
if (connectivityMap[i][j] == 1) {
aGroup[aCount][0] = i;
aGroup[aCount][1] = j;
aCount++;
} else if (connectivityMap[i][j] == 2) {
bGroup[bCount][0] = i;
bGroup[bCount][1] = j;
bCount++;
}
}
}Now that we've got those coordinate arrays, it's just a simple matter of calling getShortest path, and then iterating through the resultant coordinate array to draw the path.
int[][] shortestPath = getShortestPath(aGroup, bGroup);
if (shortestPath == null) {
return;
}
for (int i = 0; i < shortestPath.length; i++) {
int x = shortestPath[i][0];
int y = shortestPath[i][1];
setFloor(x,y);
}
}Code
PathUtil.java
/* 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;
/**
* A utility class of methods related to path generation and measurement.
* @author Roddy of the Frozen Peas (roddyofthefrozenpeas@gmail.com)
* @version 1.0 (15 July 2010)
**/
public class PathUtil {
public static double getDistance(int x1, int y1, int x2, int y2) {
return Math.sqrt(Math.pow((x2-x1), 2) + Math.pow((y2-y1), 2));
}
public static int getTileDistance(int x1, int y1, int x2, int y2) {
if (x1 == x2 && y1 == y2) {
return 0;
} else if (x1 == x2) {
return Math.abs(y1-y2);
} else if (y1 == y2) {
return Math.abs(x1-x2);
} else {
int xDelta = getDelta(x1, x2);
int yDelta = getDelta(y1, y2);
if (xDelta == yDelta) { // true diagonal
return xDelta;
}
return Math.max(xDelta, yDelta);
}
}
public static int[][] getShortestPath(final int x1, final int y1, final int x2, final int y2) {
if (x1 == x2 && y1 == y2) {
return null;
}
if (x1 < 0 || x2 < 0 || y1 < 0 || y2 < 0) {
return null;
}
int xDir = getDir(x1, x2);
int yDir = getDir(y1, y2);
if (xDir == 0) {
return buildVerticalPath(x1, y1, y2);
} else if (yDir == 0) {
return buildHorizontalPath(y1, x1, x2);
} else {
int xDelta = getDelta(x1, x2);
int yDelta = getDelta(y1, y2);
return buildDiagonal(x1, y1, xDelta, yDelta);
}
}
private static int[][] buildDiagonal(int x, int y, int xDelta, int yDelta) {
if (xDelta == 0 && yDelta == 0) {
return null;
}
if (xDelta == yDelta) { // true diagonal
int diff = (xDelta < 0) ? -1 : 1;
int[][] path = new int[xDelta][];
for (int i = 0; i < xDelta; i++) {
path[i] = new int[2];
path[i][0] = x;
path[i][1] = y;
x += diff;
y += diff;
}
return path;
}
int greater = xDelta > yDelta ? xDelta : yDelta;
int[][] path = new int[greater][2];
int i=0;
int diffX = (greater == xDelta ? (xDelta < 0 ? -1 : 1) : 0);
int diffY = (greater == yDelta ? (yDelta < 0 ? -1 : 1) : 0);
for (; i < greater; i++) {
path[i][0] = x;
path[i][1] = y;
x += diffX;
y += diffY;
}
diffX = xDelta < 0 ? -1 : 1;
diffY = yDelta < 0 ? -1 : 1;
for (; i < greater; i++) {
path[i][0] = x;
path[i][1] = y;
x += diffX;
y += diffY;
}
return path;
}
private static int[][] buildHorizontalPath(final int y, final int x1, final int x2) {
if (x1 == x2) {
return null;
}
int[][] path;
if (x2 > x1) {
path = new int[x2-x1][];
} else {
path = new int[x1-x2][];
}
int currentX = x1;
for (int i = 0; i < path.length; i++) {
path[i] = new int[2];
path[i][1] = y;
path[i][0] = currentX;
currentX++;
}
if (x1 > x2) {
currentX = x1;
for (int i = 0; i < path.length; i++) {
path[i][0] = currentX;
currentX--;
}
}
return path;
}
private static int[][] buildVerticalPath(final int x, final int y1, final int y2) {
if (y1 == y2) {
return null;
}
int[][] path;
if (y2 > y1) {
path = new int[y2-y1][];
} else {
path = new int[y1-y2][];
}
int currentY = y1;
for (int i = 0; i < path.length; i++) {
path[i] = new int[2];
path[i][0] = x;
path[i][1] = currentY;
currentY++;
}
if (y1 > y2) {
currentY = y1;
for (int i = 0; i < path.length; i++) {
path[i][1] = currentY;
currentY--;
}
}
return path;
}
private static int getDir(int start, int end) {
if (start == end) {
return 0;
} else if (start < end) {
return 1;
}
return -1;
}
private static int getDelta(int first, int second) {
return Math.abs(first-second);
}
}ConnectedDungeon.java
/* 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;
/**
* An extension to the simple Dungeon class that guarantees that a generated dungeon will be fully connected. That is -- that every area of the dungeon is accessible from every other area.
* @author Roddy of the Frozen Peas (roddyofthefrozenpeas@gmail.com)
* @version 1.0 (15 July 2010)
* @see {@link Dungeon}
**/
public class ConnectedDungeon extends Dungeon {
private int[][] connectivityMap;
public ConnectedDungeon() {
super();
init();
}
public ConnectedDungeon(int x, int y) {
super(x, y);
init();
}
public ConnectedDungeon(int x, int y, Terrain floor, Terrain wall) {
super(x, y, floor, wall);
init();
}
private void init() {
connectivityMap = new int[getX()][getY()];
initConnectivityMap();
while (!isConnected()) {
joinMap();
}
}
private void joinMap() {
int aCount = 0;
int bCount = 0;
for (int i =0; i < getX(); i++) {
for (int j = 0; j < getY(); j++) {
if (connectivityMap[i][j] == 1) {
aCount++;
} else if (connectivityMap[i][j] == 2) {
bCount++;
}
}
}
int[][] aGroup = new int[aCount][2];
int[][] bGroup = new int[bCount][2];
aCount = bCount = 0;
for (int i = 0; i < getX(); i++) {
for (int j = 0; j < getY(); j++) {
if (connectivityMap[i][j] == 1) {
aGroup[aCount][0] = i;
aGroup[aCount][1] = j;
aCount++;
} else if (connectivityMap[i][j] == 2) {
bGroup[bCount][0] = i;
bGroup[bCount][1] = j;
bCount++;
}
}
}
int[][] shortestPath = getShortestPath(aGroup, bGroup);
if (shortestPath == null) {
return;
}
for (int i = 0; i < shortestPath.length; i++) {
int x = shortestPath[i][0];
int y = shortestPath[i][1];
setFloor(x,y);
}
}
private int[][] getShortestPath(int[][] aGroup, int[][] bGroup) {
if (aGroup.length == 0 || bGroup.length == 0 || aGroup[0].length != 2 || bGroup[0].length != 2) {
return null;
}
int minDist = Integer.MAX_VALUE;
int closestA = -1, closestB = -1;
for (int a = 0; a < aGroup.length; a++) {
int x1 = aGroup[a][0];
int y1 = aGroup[a][1];
for (int b = 0; b < bGroup.length; b++) {
int x2 = bGroup[b][0];
int y2 = bGroup[b][1];
int distance = PathUtil.getTileDistance(x1, y1, x2, y2);
if (distance < minDist) {
closestA = a;
closestB = b;
minDist = distance;
}
}
}
if (closestA < 0 || closestB < 0 || closestA > aGroup.length || closestB > bGroup.length) {
return null;
}
int x1 = aGroup[closestA][0];
int y1 = aGroup[closestA][1];
int x2 = bGroup[closestB][0];
int y2 = bGroup[closestB][1];
return PathUtil.getShortestPath(x1, y1, x2, y2);
}
private boolean isConnected() {
fillMap();
return hasTwoGroups();
}
private void fillMap() {
int x, y;
do {
x = r.nextInt(getX());
y = r.nextInt(getY());
} while (isWall(x,y));
resetConnectivityMap();
fillFromPoint(x,y);
}
private void fillFromPoint(final int x, final int y) {
if (x < 0 || y < 0 || x >= getX() || y >= getY() || isWall(x,y) || connectivityMap[x][y] != 1) {
return;
}
connectivityMap[x][y] = 2;
fillFromPoint(x, y-1);
fillFromPoint(x, y+1);
fillFromPoint(x-1, y);
fillFromPoint(x+1, y);
fillFromPoint(x+1, y+1);
fillFromPoint(x+1, y-1);
fillFromPoint(x-1, y-1);
fillFromPoint(x-1, y+1);
}
private void resetConnectivityMap() {
if (hasTwoGroups()) {
initConnectivityMap();
}
}
private boolean hasTwoGroups() {
boolean hasOne = false, hasTwo = false;
for (int i = 0; i < getX(); i++) {
for (int j = 0; j < getY(); j++) {
if (hasOne && hasTwo) {
return true;
}
if (connectivityMap[i][j] == 2 && !hasTwo) {
hasTwo = true;
} else if (connectivityMap[i][j] == 1 && !hasOne) {
hasOne = true;
}
}
}
return hasOne && hasTwo;
}
private void initConnectivityMap() {
for (int i = 0; i < getX(); i ++) {
for (int j = 0; j < getY(); j++) {
if (isWall(i,j)) {
connectivityMap[i][j] = 0;
} else {
connectivityMap[i][j] = 1;
}
}
}
}
}Notes
As I mentioned previously, my shortest path methodologies are no the most sophisticated, nor is my method of linking up disjointed areas. Both of these areas could see some improvement, but they work as they currently stand.
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:
- Dungeon generation
- Extending the dungeon class
- Connected dungeons (this article)
