DungeonMazeGeneration Can Create Unrecorded Doors

[Chris3606]

In GoRogue 3, the following code can lead to rooms where there are openings that are not recorded in doors:

// Generate a map
var generator = new Generator(100, 100);
generator
    .AddSteps(DefaultAlgorithms.DungeonMazeMapSteps(
        minRooms: 10, maxRooms: 20, roomMinSize:5, roomMaxSize: 11, saveDeadEndChance: 0))
    .Generate();

This should not be possible given how the map generation algorithm functions, and indicates either maze generation has an error, or we are failing to record all rooms.

[Chris3606]

The unit test (and thus the seed/RNG/generation parameter configuration) used to produce the following images/case are documented here.

I've found the cause of this issue. Let us examine a problematic map after room generation and maze generation, but before doors are generated:

Non-walkable (wall) tiles are denoted by # The floor of the only room that was generated is represented by .. The numbered squares represent 3 unique, disconnected mazes that were generated during maze creation. The areas are identified area 0 through area 2, and each square is numbered based on which area it is a part of.

The following is the output of continuing the algorithm through the maze connection step, but stopping BEFORE door carving:

The numbers that denote the mazes have been changed to . for simplicity (since they are passable). The issue is that the connection of the mazes has clearly resulted in cutting through the room (creating the unwanted door).

What has happened is that, during the area connection algorithm, first the closest area to area 0 was found. The closest area is 1. Connecting the points in area 1 and area 2 that are closest to each other is no problem. The issue is that the connection algorithm then tries to connect area 1 to area 2, because when you process area 1, the closest area that is not already joined with 1 is 2. Only the original area 1 and area 2 are passed to the connection point selector, and considering only those points, the easiest connection cuts through the room.

The critical issue here is that only the original areas are passed to the connection point selector, so it cannot take into account points in the newly joined area(s).

The fact that the center point of the area's bounds is used to select the connection point is also problematic, however unlikely to occur if the connection point selector was working properly.

[Chris3606]

This really just highlights that GoRogue connection algorithms need an overhaul (and this is known, as it's tracked by #144 . However, since DungeonMazeMapSteps supposedly makes strong guarantees about the maximum number of doors per side, a fix that at least restores these guarantees is necessary to make this algorithm usable.

Hotfix Proposal 1

Short of fixing the connection algorithms themselves, one option is to simply check for this map state and reject any maps that result in it. It's a rather blind faith and ugly approach, but it would work to mitigate the issue.

Hotfix Proposal 2

Another possibility (though really just extension of the first) would be to simply refill the inadvertently created doors to walls, then re-determine the areas of the map and re-run the connection algorithm (which shouldn't make the same mistake again since it now knows about the connected areas). This would probably make a mess of the context state and/or require some cleanup, but would work as well.

Hotfix Proposal 3

Another possible approach is to refactor Area and/or create a better disjoint set implementation that actually joins the areas. Such an implementation is currently possible (set supports union operations), but it would likely be asymptotically inefficient. One way around this would be to implement the "unions" as a wrapper that implements area as a list of areas that forwards operations to each item in the list. Testing would be required to see what the efficiency results of this would be.

It is also of note that only option 2 would stand a chance of mitigating issues resulting from the center point of the area bounds being used for calculations pertaining to how to determine the area closest to another. Even with that, it would be difficult to offer guarantees that such an algorithm could not infinitely recurse trying to correct such flaws, so some hard-fail cutoff would probably be necessary.

[Chris3606]

There are a few other ways to cause this issue as well. Most have been solved, but at its core, the issue boils down to there is no way to guarantee mazes can be connected to each other without also creating doors, and in this case the connection algorithm cuts through the rooms.

The original algorithm solved this by treating rooms and tunnels as generic "regions", but didn't offer the element of control over number of connections. So, The most recent referenced commit adds RegenerateMapException which the RoomDoorConnection step will throw if it is given rooms that already have doors. It happens infrequently enough to where this is sufficient, and I believe this solves the issue as well as it can be solved without massive API changes (which are already planned as a potential GoRogue 4 feature). As such, closing for now.