Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
1  
Can you describe the problem you're facing in more detail? –  Byte56 May 29 '12 at 21:14
    
Yeah, what's your question exactly? –  Laurent Couvidou May 29 '12 at 21:18
1  
While it could surely be extended to 3D, it could be not so trivial depending on your game logic. In a 3D world you face the possibility of unreachable paths due to the movement limitations instead of collisions/dead-ends. I.E: if a corridor goes up or down 7m. you need to know how high a player could 'jump' or 'fall' without suffering death. A possibile way could be to first solve each 2D floor and connect that to the next one (up or down) using failsafe joints (ruled by game logic). –  Darkwings May 29 '12 at 21:21
    
@Darkwings that is a very good point, and that is why that a room that incorporates 3Dy motion will still have doors, and why room start centered at the position of the door (see edit). though I will examine my room rules to see if any 3D constraints need to be given. –  gardian06 May 29 '12 at 21:45
    
Well, I didn't take into account doors (assuming each joint was open by default) but that's a good example of something you should dedcide beforehand: does a door going up/down even make sense in your world? There's quite a bit of special cases that a normal geometric solution won't solve without additional rules. –  Darkwings May 29 '12 at 22:29

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
    
my game has already been defined as dynamically created random procedural levels. which is why I am asking this question in the first place, but your answer is still viable to future users. –  gardian06 May 29 '12 at 22:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.