Dungeon Generation with no corridors and room dependencies

Question

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.

Answer 1

This is a cool problem. I believe it can be solved using action planning in the space of room placements.

Define the State of the world as follows:

//State:
//    A list of room states.
//    Room state:
//      - Does room exist?
//      - Where is room's location?
//      - What is the room's size?

Define a Constraint as:

 // Constraint(<1>, <2>):
 //  - If room <1> and <2> exist, Room <1> is adjacent to Room <2>

Where "adjacent" is as you described (sharing at least 3 neighbors)

A Constraint is said to be invalidated whenever the two rooms are not adjacent, and both rooms exist.

Define a State to be valid when:

// foreach Constraint:
//        The Constraint is "not invalidated".
// foreach Room:
//       The room does not intersect another room.

Define an Action as a placement of a room, given a current State. The Action is valid whenever the resulting state from the action is valid. Therefore, we can generate a list of actions for each state:

// Returns a list of valid actions from the current state
function List<Action> GetValidActions(State current, List<Constraint> constraints):
    List<Action> actions = new List<Action>();
    // For each non-existent room..
    foreach Room room in current.Rooms:
        if(!room.Exists)
            // Try to put it at every possible location
            foreach Position position in Dungeon:
                 State next = current.PlaceRoom(room, position)
                 // If the next state is valid, we add that action to the list.
                 if(next.IsValid(constraints))
                     actions.Add(new Action(room, position));

Now, what you're left with is a graph, where States are nodes, and Actions are links. The goal is to find a State which is both valid, and all of the rooms have been placed. We can find a valid placement by searching through the graph in an arbitrary way, perhaps using a depth-first search. The search will look something like this:

// Given a start state (with all rooms set to *not exist*), and a set of
// constraints, finds a valid end state where all the constraints are met,
// using a depth-first search.
// Notice that this gives you the power to pre-define the starting conditions
// of the search, to for instance define some key areas of your dungeon by hand.
function State GetFinalState(State start, List<Constraint> constraints)
    Stack<State> stateStack = new Stack<State>();
    State current = start;
    stateStack.push(start);
    while not stateStack.IsEmpty():
        current = stateStack.pop();
        // Consider a new state to expand from.
        if not current.checked:
            current.checked = true;
            // If the state meets all the constraints, we found a solution!
            if(current.IsValid(constraints) and current.AllRoomsExist()):
                return current;

            // Otherwise, get all the valid actions
            List<Action> actions = GetValidActions(current, constraints);

            // Add the resulting state to the stack.
            foreach Action action in actions:
                State next = current.PlaceRoom(action.room, action.position);
                stateStack.push(next);

    // If the stack is completely empty, there is no solution!
    return NO_SOLUTION;

Now the quality of the dungeon generated will depend on the order in which rooms and actions are considered. You can get interesting and different results probably by just randomly permuting the actions you take at each stage, thereby doing a random walk through the state-action graph. The search efficiency will greatly depend on how quickly you can reject invalid states. It may help to generate valid states from the constraints whenever you want to find valid actions.

Answer 2

Your generation priorities are in conflict. When generating levels, your first goal should be a web of planar (non-overlapping), connected points, irrespective of scale. Then proceed to create rooms from the points within that web. Creating room shapes first is a mistake, generally speaking. Create connectivity first, and then see what room forms can be accommodated within that.

General Algorithm

1. Create a quantised floor grid of sufficient size to support your level, using a 2D array or image.

2. Scatter points at random across this empty floor space. You can use a plain random check on each tile to see whether it gets a point, or use standard / Gaussian distribution to scatter points. Assign a unique colour / numeric value to each and every point. These are IDs. (P.S. If after this step you feel you need to scale your space up, by all means, do.)

3. For each such generated point, in sequence, incrementally grow a bounds circle or bounds rectangle out by a single step (typically a rate of 0.5-1.0 cells/pixels per step) in x and y. You can either grow all bounds in parallel, all starting from size zero at the same step, or you can start growing them at different times and at different rates, giving bias to the size of those that start earlier (imagine seedlings growing, where some start late). By "grow" I mean fill in the newly-incremented bounds with the colour / ID unique to the starting point for those bounds. A metaphor for this would be holding marker pens against the back of a piece of paper, and watching inkblots of different colours grow, until they meet.

4. At some point the bounds of some point and another point are going to collide, during the grow step. This is the point at which you should stop growing the bounds for those two points -- at least in the uniform sense described in step 3.

5. Once you've grown all points' bounds as far as possible and stopped all growth processes, you will have a map that should be largely, but not entirely filled. You may now want to pack up those empty space, which I will assume to be white, as if colouring in a sheet of paper.

Post-process Space-filling

A variety of techniques can be used to fill in the empty / white spaces that remain, per step 5:

• Have a single neighbouring, already-coloured area claim the space, by flood filling it that colour so it all joins up.
• Flood with new, as-yet-unused colours / numbers / IDs, such that they form entirely new areas.
• Round robin approach such that each already-filled neighbouring area "grows" a little bit into the empty space. Think of animals drinking around a watering hole: they all get some of the water.
• Don't totally fill the empty space, just cross it to link up existing areas using straight passages.

Perturbation

As a final step to make things look more organic, you could do edge-perturbation in varying degrees, on the edges cells of areas. Just be sure not to block crucial movement routes.

Theory, for Interest's Sake

This is similar to the approach taken in Voronoi Diagrams / Delaunay Triangulation, except that in the above you are not explicitly creating edges -- instead, when bounding areas collide, growth ceases. You will notice that Voronoi Diagrams are space-filling; this is because they do not cease growth merely on touching, but rather on some nominal degree of overlap. You could try similar.