I’m currently in the process of trying to create my first procedurally generated dungeon and am following this blog post in order to figure it out.
So far things have gone well and I’ve managed to get a dungeon created that is almost perfect for my needs - except that I wanted to be sure that I could always get from any point to any other point within the dungeon and sometimes it generates rooms that are not connected to the rest of the dungeon.
I couldn’t figure out how to fix things based on my existing code and, so I went back to the blog post mentioned above and noticed that he’s taking a (slightly) different approach from me when connecting his dungeon up. I simply looped through all my rooms and made sure they had at least one door connecting them to either another room or a corridor. The guy writing the post uses a concept of regions that, to be honest, I’m simply not getting. He says that he’s using the connectors to separate the regions, but, as far as I can tell, that simply gives you each room as a region and then all of the corridors as one large region - but that doesn’t seem to be how he’s actually implementing it - which is why I’m confused.
Part of the problem is that his code is written in Dart which I’m not at all familiar with. Much of it I can figure out, but not this section:
void _connectRegions() {
// Find all of the tiles that can connect two (or more) regions.
var connectorRegions = <Vec, Set<int>>{};
for (var pos in bounds.inflate(-1)) {
// Can't already be part of a region.
if (getTile(pos) != Tiles.wall) continue;
var regions = new Set<int>();
for (var dir in Direction.CARDINAL) {
var region = _regions[pos + dir];
if (region != null) regions.add(region);
}
if (regions.length < 2) continue;
connectorRegions[pos] = regions;
}
var connectors = connectorRegions.keys.toList();
// Keep track of which regions have been merged. This maps an original
// region index to the one it has been merged to.
var merged = {};
var openRegions = new Set<int>();
for (var i = 0; i <= _currentRegion; i++) {
merged[i] = i;
openRegions.add(i);
}
// Keep connecting regions until we're down to one.
while (openRegions.length > 1) {
var connector = rng.item(connectors);
// Carve the connection.
_addJunction(connector);
// Merge the connected regions. We'll pick one region (arbitrarily) and
// map all of the other regions to its index.
var regions = connectorRegions[connector]
.map((region) => merged[region]);
var dest = regions.first;
var sources = regions.skip(1).toList();
// Merge all of the affected regions. We have to look at *all* of the
// regions because other regions may have previously been merged with
// some of the ones we're merging now.
for (var i = 0; i <= _currentRegion; i++) {
if (sources.contains(merged[i])) {
merged[i] = dest;
}
}
// The sources are no longer in use.
openRegions.removeAll(sources);
// Remove any connectors that aren't needed anymore.
connectors.removeWhere((pos) {
// Don't allow connectors right next to each other.
if (connector - pos < 2) return true;
// If the connector no long spans different regions, we don't need it.
var regions = connectorRegions[pos].map((region) => merged[region])
.toSet();
if (regions.length > 1) return false;
// This connecter isn't needed, but connect it occasionally so that the
// dungeon isn't singly-connected.
if (rng.oneIn(extraConnectorChance)) _addJunction(pos);
return true;
});
}
}
I don’t get this code and I think it’s partly because I’m simply not understanding the concept of a region as he uses it. I did try and ask in the comments, but it’s an old post, so I’m not expecting a reply there.
So, can anyone help me understand what he means by a region and, if so, help me understand his code?
If it’s any help - here is my current attempt at this:
private void connectRegions() {
while (rooms.size > 0) {
Rectangle room = rooms.peek();
Array<Vector2> connectors = getConnectorsByRoom(room);
carveDoors(connectors);
rooms.removeValue(room, false);
}
}
private void carveDoors(Array<Vector2> connectors) {
int connector = MathUtils.random(connectors.size - 1);
for (Vector2 connection : connectors) {
if (MathUtils.random(50) != 0) {
grid[(int) connection.x][(int) connection.y] = 0;
} else {
if (!isNextToDoor(connection)) {
grid[(int) connection.x][(int) connection.y] = DOOR;
}
}
}
Vector2 goodConnector = connectors.get(connector);
if (!isNextToDoor(goodConnector)) {
grid[(int) goodConnector.x][(int) goodConnector.y] = DOOR;
}
}
private boolean isNextToDoor(Vector2 cell) {
int x = (int) cell.x;
int y = (int) cell.y;
return grid[x - 1][y] == DOOR
|| grid[x + 1][y] == DOOR
|| grid[x][y + 1] == DOOR
|| grid[x][y - 1] == DOOR;
}
As I say, it actually works well, but can produce unreachable sections of the dungeon.