How to place rooms proceduraly (rule based) on in a game word

Question

I am trying to design the algorithm for my level generation which is a rule driven system. I have created all the rules for the system. I have taken care to insure that all rooms make sense in a grid type setup. for example: these rooms could make this configuration

The logic flow code that I have so far

Door{
    Vector3 position;
    POD orient;     // 5 possible values (up is not an option)
    bool Open;
}

Room{
    String roomRule;
    Vector3 roomPos;
    Vector3 dimensions;
    POD roomOrient;     // 4 possible values
    List doors<Door>;
}

LevelManager{
    float scale = 18f;
    List usedRooms<Room>;
    List openDoors<Door>
    bool Grid[][][];

    Room CreateRoom(String rule, Vector3 position, POD Orient){
        place recieved values
        based on rule fill in other data
    }

    Vector3 getDimenstions(String rule){
        return dimensions of the room
    }

    RotateRoom(POD rotateAmount){
        rotate all items in the room
    }

    MoveRoom(Room toBeMoved, POD orientataion, float distance){
        move the position of the room based on inputs
    }

    GenerateMap(Vector3 size, Vector3 start, Vector3 end){
        Grid = array[size.y][size.x][size.z];
        Room floatingRoom;
        floatingRoom = Room.CreateRoom(S01, start, rand(4));
        usedRooms.Add(floatingRoom);
        for each Door in floatingRoom.doors{
            openDoors.Add(door);
        }

//      fill used grid spaces

        floatingRoom = Room.CreateRoom(S02, end, rand(4);
        usedRooms.Add(floatingRoom);
        for each Door in floatingRoom.doors{
            openDoors.Add(door);
        }

        Vector3 nRoomLocation;
        Door workingDoor;
        string workingRoom;
//      fill used grid spaces

//      pick random door on the openDoors list
        workingDoor = /*randomDoor*/
//      get a random rule
        nRoomLocation = workingDoor.position;
//      then I'm lost
    }
}

I know that I have to make sure for convergence (namely the end is reachable), and to do this until there are no more doors on the openDoors list. right now I am simply trying to get this to work in 2D (there are rules that introduce 3D), but I am working on a presumption that a rigorous algorithm can be trivially extended to 3D.

EDIT: my thought pattern so far is to

1. take an existing open door
2. and then pick a random room (restrictions can be put in later)
3. place that room's center at the doors location
4. move the room in the direction of the doors orientation half the rooms dimension w/respect to that axis
5. then test against the 3D array to see if all the grid points are open, or have been used, or if there is even space to put the room (caseEdge)
6. if caseEdge (which can also occur in between rooms) then put the door on a toBeClosed list, and remove it from the open list (placing a wall or something there).
7. then to do some kind of test that both the start, and the goal are connected, and reachable from each other (each room has nodes for AI, but I don't want to "have" to pull those out to accomplish this).

but this logic has the problem for say the U, or L shaped rooms in my example, and then I also have a problem conceptually if the room needs to be rotated.

Answer 1

As I explained before, since there are already good algorithms to perform pathfinding, space filling etc, you could simplify the work by setting up the initial rooms.

Since it's a game world, the goal is not just to fill up a grid with rooms, but to create a space where a player can move around following a game logic.

So, if you set some rules to avoid breaking your world such as:

• Each door have its own properties (one-way, two-ways, locked, etc).
• A player can enter/exit a room only by a door.
• Each room must be 'solved': it must be possible, starting from any door, to reach each of the other doors in the room.
  • For each room, some particular rotations could be avoided to ensure the previous rule.
• Rooms are connected by doors, and connected doors must be of the same size.

By 'door' I mean any kind of passage. Even empty space can be a door.

Since these prerequisites are met per-room, you can create rooms as complex as you need because it won't affect your algorithm (the number of doors per room WILL affect the computing time).

I.E.: to avoid a corridor with a door on the end to become vertical and so requiring a huge jump/fall you can set those 2 rotation as off-limit. That way, when the filling algorithm tries to set that room, it will discard it if it would require that illegal rotation.

Also, if the player suddenly gains the ability to fly, it still won't affect your algorithm directly: it will affect the 'solving' ability for each room and the possible rotations.

After this setup, the case is similar to inventory-filling/pathfinding/maze solving, depending on what you actually need. Every time the algorithm choose a candidate solution, with a simple check to enforce previous rules you'll have it discard it or keep it, without modifying the algorithm itself.

I think that the possibility to rely on a solid external algorithm is a huge advantage over a custom-tailored one.

Answer 2

Rather than using your method, I would use a maze algorithm, like one of these:

Then just knock out sections of walls to make larger rooms. Make sense? You could probably create more diverse and interesting results this way, with faster compute speed.