Problem
I’m creating an RPG type game, and now I am working on procedural town generation. The algorithm for that creates some roads going horizontally and vertically, and then attempts to place buildings in the open spaces.
Once a building is successfully placed, I use this algorithm to iterate through the positions of the walls and determine what type of wall should go in each position. There are a few different patterns needed to account for all potential outcomes, such as the intersection between walls, the corners, etc.
Here is a screenshot of the result:
First I created this enum for the different possible patterns.
WallPattern.java
public enum WallPattern {
//0 is empty
//1 is wall
//2 is optional, can be empty or wall
TOP_LEFT(0, 0, 2,
0, 1, 1,
2, 1, 2),
TOP_RIGHT(2, 0, 0,
1, 1, 0,
2, 1, 2),
BOTTOM_LEFT(2, 1, 2,
0, 1, 1,
0, 0, 2),
BOTTOM_RIGHT(2, 1, 2,
1, 1, 0,
2, 0, 0),
HORIZONTAL(2, 0, 2,
2, 1, 2,
2, 0, 2),
VERTICAL(2, 2, 2,
0, 1, 0,
2, 2, 2),
INTERSECTION(2, 1, 2,
1, 1, 1,
2, 1, 2);
private final List<Integer> pattern;
private WallPattern(int one, int two, int three, int four, int five, int six, int seven, int eight, int nine) {
this.pattern = new ArrayList<Integer>();
this.pattern.add(one);
this.pattern.add(two);
this.pattern.add(three);
this.pattern.add(four);
this.pattern.add(five);
this.pattern.add(six);
this.pattern.add(seven);
this.pattern.add(eight);
this.pattern.add(nine);
}
public boolean patternMatches(List<TownTileType> tilePattern) {
if (tilePattern.size() != this.pattern.size()) {
return false;
}
boolean matches = true;
for (int i = 0; i < tilePattern.size(); i++) {
TownTileType type = tilePattern.get(i);
int patternNum = this.pattern.get(i);
// if type is a wall, the pattern must allow one
if (type == TownTileType.WALL) {
if (patternNum == 0) {
matches = false;
break;
}
//if type is not a wall, the pattern must not require one
} else {
if (patternNum == 1) {
matches = false;
break;
}
}
}
return matches;
}
}
Then I iterate through each of the wall positions, creating a list of the surrounding tiles and checking if it matches any pattern:
//set the types based on their neighbors
Map<MapPoint, TownTileType> typesBasedOnNeighbors = new HashMap<MapPoint, TownTileType>();
for (MapPoint wallPoint : wallPositions) {
if (this.townTiles[wallPoint.x][wallPoint.y] == TownTileType.WALL) {
List<TownTileType> patternForPoint = new ArrayList<TownTileType>();
for (int x = wallPoint.x - 1; x <= wallPoint.x + 1; x++) {
for (int y = wallPoint.y + 1; y >= wallPoint.y - 1; y--) {
patternForPoint.add(this.townTiles[x][y]);
}
}
for (WallPattern pattern : WallPattern.values()) {
if (pattern.patternMatches(patternForPoint)) {
typesBasedOnNeighbors.put(wallPoint, TownTileType.getTypeForWallPattern(pattern));
break;
}
}
}
}
//dont change them until they are all determined
for (Entry<MapPoint, TownTileType> entry : typesBasedOnNeighbors.entrySet()) {
this.townTiles[entry.getKey().x][entry.getKey().y] = entry.getValue();
}
As always I am interested in any and all feedback about this approach. I’m stuck with Java 6 since this is a libGDX game.
As requested, here is getTypeForWallPattern:
public static TownTileType getTypeForWallPattern(WallPattern wallPattern) {
switch (wallPattern) {
case TOP_LEFT:
return WALL_TOP_LEFT;
case TOP_RIGHT:
return WALL_TOP_RIGHT;
case BOTTOM_LEFT:
return WALL_BOTTOM_LEFT;
case BOTTOM_RIGHT:
return WALL_BOTTOM_RIGHT;
case INTERSECTION:
return WALL_INTERSECTION;
case HORIZONTAL:
return WALL_HORIZONTAL;
case VERTICAL:
return WALL_VERTICAL;
}
return EMPTY;
}
Solution
Unrelated: you may be interested in this presentation from the folks at Grinding Gear Games, where they discuss random level generation
public enum WallPattern
This might be better named a WallSpecification – it’s a description of how to choose what kind of wall piece you need, right? WallPattern isn’t wrong, but I think the word “Pattern” can get a bit overloaded.
//0 is empty
//1 is wall
//2 is optional, can be empty or wall
Magic numbers are a bad idea. You can usually identify magic numbers by the fact that you never actually use them as numbers (would you ever add a wall to an optional?), and if you are lucky they are accompanied by a comment explaining that they mean something else.
enum TileSpecification {
EMPTY, WALL, UNSPECIFIED
}
Introducing TileSpecification is going to make the WallPattern code more verbose, but I believe it will help clarify your intent. Onward….
private final List<TileSpecification> pattern;
private WallPattern(TileSpecification one, TileSpecification two, TileSpecification three, TileSpecification four, TileSpecification five, TileSpecification six, TileSpecification seven, TileSpecification eight, TileSpecification nine) {
this.pattern = new ArrayList<Integer>();
this.pattern.add(one);
this.pattern.add(two);
this.pattern.add(three);
this.pattern.add(four);
this.pattern.add(five);
this.pattern.add(six);
this.pattern.add(seven);
this.pattern.add(eight);
this.pattern.add(nine);
}
Magic numbers again — this time appearing as argument names. The names of the arguments kind of match up with the index into the list that they will appear in, but that’s not telling us what’s really going on. Let’s look at how it is being used….
for (int i = 0; i < tilePattern.size(); i++) {
TownTileType type = tilePattern.get(i);
int patternNum = this.pattern.get(i);
If you look at this code for a moment, we aren’t really using the List as a List; we don’t care about the order of the checks at all. It’s just being used as a Collection, with the index being used as the key to match up the two tile patterns.
The canonical collection that supports lookup by key is a Map
private final Map<Integer, TileSpecification> pattern;
private WallPattern(TileSpecification one, TileSpecification two, TileSpecification three, TileSpecification four, TileSpecification five, TileSpecification six, TileSpecification seven, TileSpecification eight, TileSpecification nine) {
this.pattern = new HashMap<Integer, TileSpecification>();
this.pattern.put(1, one);
this.pattern.put(2, two);
this.pattern.put(3, three);
this.pattern.put(4, four);
this.pattern.put(5, five);
this.pattern.put(6, six);
this.pattern.put(7, seven);
this.pattern.put(8, eight);
this.pattern.put(9, nine);
}
Here, we are temporarily taking advantage of the fact that Java can autobox int to Integer via Integer.valueOf.
This refactoring added more magic numbers, which isn’t what we want. But it is maybe getting easier to see that they are there, and should be addressed. Effective Java tells us that we should use EnumMap instead of ordinal indexing — a fancy way of saying we shouldn’t be using numbers as keys to our map.
Let’s look for the meaning behind the numbers
TOP_LEFT(0, 0, 2,
0, 1, 1,
2, 1, 2),
Aha – we get a lucky break. You formatted the original code to make it easier to see what was going on, and from this we can determine that meaning encoded into the position in your list is the relative position of this tile in relation to the home tile. Since we can enumerate the relative positions, that suggests we should again implement an enum
enum RelativePosition {
TOP_LEFT, TOP_CENTER, TOP_RIGHT,
CENTER_LEFT, HOME, CENTER_RIGHT,
BOTTOM_LEFT, BOTTOM_CENTER, BOTTOM_RIGHT
}
private final Map<RelativePosition, TileSpecification> pattern;
private WallPattern(TileSpecification one, TileSpecification two, TileSpecification three, TileSpecification four, TileSpecification five, TileSpecification six, TileSpecification seven, TileSpecification eight, TileSpecification nine) {
this.pattern = new EnumMap<RelativePosition, TileSpecification>(RelativePosition.class);
this.pattern.put(TOP_LEFT, one);
this.pattern.put(TOP_CENTER, two);
this.pattern.put(TOP_RIGHT, three);
this.pattern.put(CENTER_LEFT, four);
this.pattern.put(HOME, five);
this.pattern.put(CENTER_RIGHT, six);
this.pattern.put(BOTTOM_LEFT, seven);
this.pattern.put(BOTTOM_CENTER, eight);
this.pattern.put(BOTTOM_RIGHT, nine);
}
Now that it is clear what the arguments are, we can name them more appropriately.
private WallPattern(TileSpecification topLeftNeighbor, TileSpecification topCenterNeighbor, TileSpecification topRightNeighbor, TileSpecification centerLeftNeighbor, TileSpecification home, TileSpecification centerRightNeighbor, TileSpecification bottomLeftNeighbor, TileSpecification bottomCenterNeighbor, TileSpecification bottomRightNeighbor) {
Well, I suppose that’s clearer, but it’s wordy wordy wordy. Is there anything we can do about that? One answer might be to create a constructor that accepts a pre-populated map
private WallPattern(Map<RelativePosition, TileSpecification> pattern) {
this.pattern = pattern;
}
You still need to map the assignments, but you’ve got options for how to do that (static initializers, fluent builders, whatever you think makes sense).
public boolean patternMatches(List<TownTileType> tilePattern) {
Based on how you are using it here, I suspect that use EnumMap instead of ordinal mapping works here too….
public boolean patternMatches(Map<RelativePosition, TownTileType> tilePattern) {
for(Map.Entry<RelativePosition,TileSpecification> entry : pattern.entrySet()) {
TileSpecification tileSpec = entry.getValue();
TownTileType townTile = tilePattern.get(entry.getKey());
if (! specificationMatches(tileSpec, townTile)) {
return false;
}
}
return true;
}
boolean specificationMatches(TileSpecification tileSpec, TownTileType townTile) {
...
}
Notice the logic – we return true if every one of the TileSpecifications in the pattern is satisfied. This implies that we only need to test the positions where that question is in doubt. In other words, since TileSpecification.UNSPECIFIED always passes, we don’t need to check it… so we don’t need to put those in the pattern map, which in turn means that we don’t necessarily need that specification at all.
I’m guessing that you might have similar logic for things outside of towns. In that case, you probably don’t want to restrict the patternMatches method to TownTileType. There are two things you might do.
You could decide that patternMatches() should take anything that extends a common base tile. In that case, the signature would look like
public boolean patternMatches(Map<RelativePosition, ? extends TileType> tilePattern) {
...
}
That can work if TileType has all the information that you need to perform the match.
Another possibility is to use a matching Policy (or Strategy) that knows how to match lots of different things.
interface MatchingPolicy<SpecificationType, ItemType> {
boolean matches(SpecificationType specification, ItemType item);
}
class TownWallMatchingPolicy implements MatchingPolicy<TileSpecification,TownTileType> {
....
}
In that case, your pattern matching code can be very generic
class MapSpecification<K, V, T> {
Map<K,V> specifications;
MatchingPolicy<V,T> policy;
public boolean patternMatches(Map<K, ? extends T> target) {
for(Map.Entry<K,V> entry : specifications.entrySet()) {
V spec = entry.getValue();]
T item = target.get(entry.getKey());
if (! policy.matches(spec, item)) {
return false;
}
}
return true;
}
Using switch to go from one value to another is a code smell.
public static TownTileType getTypeForWallPattern(WallPattern wallPattern) {
switch (wallPattern) {
case TOP_LEFT:
return WALL_TOP_LEFT;
case TOP_RIGHT:
return WALL_TOP_RIGHT;
case BOTTOM_LEFT:
return WALL_BOTTOM_LEFT;
case BOTTOM_RIGHT:
return WALL_BOTTOM_RIGHT;
case INTERSECTION:
return WALL_INTERSECTION;
case HORIZONTAL:
return WALL_HORIZONTAL;
case VERTICAL:
return WALL_VERTICAL;
}
return EMPTY;
}
Isn’t this just a Map<WallPattern,TownTileType>, which an EMPTY value if the map doesn’t contain the key?
You might also want to look into the BuilderPattern from the Gang of Four Book As I recall, the examples there feature maze building, which includes choosing the right type of wall for the circumstances….
private WallPattern(int one, int two, /* ... */ int nine) {
this.pattern = new ArrayList<Integer>();
this.pattern.add(one);
this.pattern.add(two);
this.pattern.add(three);
this.pattern.add(four);
this.pattern.add(five);
this.pattern.add(six);
this.pattern.add(seven);
this.pattern.add(eight);
this.pattern.add(nine);
}
Even for Java 6, you can use varargs and Arrays.asList(T...) already:
enum WallPattern {
// showing only for TOP_LEFT
TOP_LEFT(0, 0, 2,
0, 1, 1,
2, 1, 2);
final List<Integer> values;
private WallPattern(Integer... values) {
this.values = Arrays.asList(values);
}
}
Yes, this relies on auto-boxing int -> Integer, which is something I don’t usually recommend, but it appears to work fine as long as you know what you are doing :).
if (/* ... */) {
matches = false;
break;
}
Might be better to just return false from here then.
edit: Extra pointers…
for (WallPattern pattern : WallPattern.values()) {
if (pattern.patternMatches(patternForPoint)) {
typesBasedOnNeighbors.put(wallPoint, TownTileType.getTypeForWallPattern(pattern));
break;
}
}
You may want to put this as a public static method in WallPattern:
enum WallPattern {
// ...
public static WallPattern matches(List<TownTileType> patternForPoint) {
for (WallPattern pattern : values()) {
if (pattern.patternMatches(patternForPoint)) {
return pattern;
}
}
return null;
}
}
The usage in the original place is thus simplified, somewhat:
WallPattern pattern = WallPattern.matches(patternForPoint);
if (pattern != null) {
typesBasedOnNeighbors.put(wallPoint, TownTileType.getTypeForWallPattern(pattern));
}
You may want to inverse the if condition below and do an early continue to reduce the nesting:
// instead of this
for (MapPoint wallPoint : wallPositions) {
if (this.townTiles[wallPoint.x][wallPoint.y] == TownTileType.WALL) {
// ...
}
}
// try this
for (MapPoint wallPoint : wallPositions) {
if (this.townTiles[wallPoint.x][wallPoint.y] != TownTileType.WALL) {
continue;
}
// ...
}
Since there is a one-to-one relationship between wall patterns and tile types, model that in your enums:
public enum WallPattern {
//0 is empty
//1 is wall
//2 is optional, can be empty or wall
TOP_LEFT(0, 0, 2,
0, 1, 1,
2, 1, 2, TownTileType.WALL_TOP_LEFT),
TOP_RIGHT(2, 0, 0,
1, 1, 0,
2, 1, 2, TownTileType.WALL_TOP_RIGHT),
BOTTOM_LEFT(2, 1, 2,
0, 1, 1,
0, 0, 2, TownTileType.WALL_BOTTOM_LEFT),
BOTTOM_RIGHT(2, 1, 2,
1, 1, 0,
2, 0, 0, TownTileType.WALL_BOTTOM_RIGHT),
HORIZONTAL(2, 0, 2,
2, 1, 2,
2, 0, 2, TownTileType.WALL_HORIZONTAL),
VERTICAL(2, 2, 2,
0, 1, 0,
2, 2, 2, TownTileType.WALL_VERTICAL),
INTERSECTION(2, 1, 2,
1, 1, 1,
2, 1, 2, TownTileType.WALL_INTERSECTION);
private final List<Integer> pattern;
private final TownTileType tileType;
private WallPattern(int one, int two, int three, int four, int five, int six, int seven, int eight, int nine, TownTileType tileType) {
this.pattern = new ArrayList<Integer>();
this.pattern.add(one);
this.pattern.add(two);
this.pattern.add(three);
this.pattern.add(four);
this.pattern.add(five);
this.pattern.add(six);
this.pattern.add(seven);
this.pattern.add(eight);
this.pattern.add(nine);
this.tileType = tileType;
}
public TownTileType getTileType() {
return tileType;
}
}
To get the tile type:
WallPattern.TOP_LEFT.getTileType();
No loops, switchs, ifs (and’s or but’s) required.