1. Generate a grid:
- GfVIqIF.png (6.78 KiB) Viewed 605 times
2. Color the grid with x red rooms (hard), y blue rooms (medium) and z green rooms (easy) such that x+y+z = n rooms in the grid (x, y, z can be changed to control difficulty):
2.a) First color it with x red rooms such that no red room has another same colored neighbor (this can be changed if dungeon difficulty should be higher);
2.b) Then for each red room color one neighbor blue and one neighbor green;
2.c) Color the rest of the rooms with the remaining number of rooms for each color.
- 9E6YRxc.png (21.62 KiB) Viewed 605 times
3. Choose two nodes that are far apart enough and then find a path between them while mostly avoiding red rooms. If you choose a proper x, since red rooms can't be neighbors to themselves and the pathfinding algorithm doesn't go for diagonals, it should create a not so direct path from one node to the other.
- joqNLyL.png (22.99 KiB) Viewed 605 times
4. For all nodes in the path, add their red[, green, blue] neighbors. This should create the possibility of side paths and overall complexity/difficulty in the dungeon.
- PJ4gDPX.png (23.81 KiB) Viewed 605 times
5. Join smaller grids into bigger ones according to predefined room sizes. Higher chance of smaller width/height and lower chance of bigger width/height.
- oSsWtGP.png (19.26 KiB) Viewed 605 times
6. Generate all possible connections between rooms.
- 5PVneQf.png (10.91 KiB) Viewed 605 times
7. Randomly remove connections until a certain number of connections per room is met. If n = total rooms, then set n*x rooms with >=4 connections, n*y with 3, n*z with 2 and n*w with 1, such that x+y+z+w=1. Controlling x, y, z and w lets you control how mazy the dungeon gets. If z or w are considerably higher than x or y then there won't be many "hub" rooms that connect different paths, so it's gonna have lots of different thin paths with dead ends. If x or y are higher then the dungeon will be super connected and therefore easier.
- dtfoT3g.png (10.89 KiB) Viewed 605 times
8. Reconnect isolated "islands". Since step 7 is completely random, there's a big chance that rooms or groups of rooms will become unreachable.
8. To fix that:
8.a) Flood fill to figure out how many isolated groups exist;
8.b) Pick a group at random and go through its rooms. For each room check if it neighbors a room belonging to another group, if it does then connect them and end the search;
8.c) Repeat 8.a -> 8.b until there's only one group left (everyone's connected).
- UtGPsyP.png (10.9 KiB) Viewed 605 times
And that's it, I guess. There's more stuff like adding special rooms, but that's specific to each game, so whatever. But basically I have a few parameters I can control when creating a new dungeon: dungeon width/height; percentage of hard, medium and easy rooms; what color neighbors get added to the original path and the percentage of rooms with >=4, 3, 2 or 1 connections. I think that's enough to have control of how easy/hard the dungeon will be...
Maybe, if the versions of LÖVE add more that I can add, development could last longer!! I am sort of looking for people to design characters, but I'm holding back on it for now because of a few reasons:
)
A ton of people use that.
