I'm making a game with a procedurally generated world created at the beginning of the game, consisting of several areas represented by grids (say, 8x8, 9x6, the sizes would ideally be arbitrary). These areas are supposed to be connected to each other through a dependency list.
A connection exists when at least 3 spaces of that grid are exposed between those two areas. In the middle cell of that 3 space connection area is the doorway between areas:
I've been trying to figure out a way to connect them, but it becomes increasingly complex the more areas you need to consider at the same time.
I've tried some paper prototyping and while it's a very simple process when doing it visually, I haven't found out a good set of mathematical expressions that allows me to place rooms with the same efficiency by code.
Here's a "simple" example I'm struggling with right now:
- Area 'a' needs to be connected to 'b' and 'c'
- Area 'b' needs to be connected to 'a' and 'd'
- Area 'c' needs to be connected to 'a' and 'd'
- Area 'd' needs to be connected to 'b' and 'c'
Consider, for simplicity, we're placing the rooms by their order of appearance on the list (I've tried others). So I'm approaching this as your standard procedural Dungeon Generation algorithm.
We place 'a' anywhere on the board, since it's the first area. Next, we pick a wall at random and, since nothing is connected to that wall, we can place 'b' there:
Now we need to place 'c', but 'a' is already on the board, and has an occupied wall, so we decide to put it on another wall. But not every placement will do, because 'd' is coming up and it needs to be connected to 'b' and 'c' too:
I tried a possible limitation that 2 rooms that have the same set of dependencies cannot be on opposite walls, but even that doesn't guarantee success:
And in other cases, where the areas have different sizes, being on opposite walls can work:
Also, not considering a used wall is a flawed assumption since it rules out valid solutions:
I've tried looking up research on other Procedural Generation algorithms or similar, such as Optimal Rectangle Packing and Graph Layout algorithms, but usually those algorithms don't take into account every constraint of this problem and are hard to mix together.
I thought about a bunch of approaches, including placing an area and backtrack until a suitable placement is found, but they seem very dependent on trial and error and costly in terms of computation. But, given the extensive research on the last two problems I mentioned, it might be the only/best solution?
I just wanted to see if someone has had similar problems in the past or is willing to help me figure this out and give me a few pointers on where I should start with the algorithm. Or, failing that, I'll have to look into loosening the constraints I've set.