Random Map Generation - Looking for suggestions on a different implementation

[Chumble]

The project is creating rooms with doors. Any door that does’t have something the way can be used to generate another room. There are 4 main blueprints in play here.

“Rooms” - The main actor that spawns everything else. My level has one “Rooms” actor in it at 0,0,0 and everything is generated from that. Contains an array of “Room” actors.
“Room” - A single rectangular room with an array of “Door” actors. Also has “Wall” actors, but they’re not stored.
“Door” - A 200x300 wall with an opening for a player to walk through
“Wall” - A 200x300 solid wall.

A room is built wall-by-wall using either a Door or a Wall (Currently, every segment has a 10% chance to be a door).

Here’s the basic logic:

1. Create Start room. Small room with 4 doorways. Add the Start room to the array
   
   I apologize for the images. Posting at work and all I have available is MSPaint
2. For each room in the room array…
3. For each door in the door array of the current room…
4. Use the door’s location to determine the amount of space available outside the doorway for another room
5. If there is space, randomize the dimensions within the space available and spawn a new Room actor
6. Add the room actor to the room array
7. Build the room based on the dimensions passed in. If a door segment is placed, add the door to the “Doors” array.
   From here, the logic passes back to step 3. There are 3 more doors in the array still, each creating their own room. Then the logic passes back to step 2 where the 4 new rooms are processed. I have a “Max Rooms” variable which I use to break the loop

The problem I have is with step 4, determining the amount of space I have available.

At first, I grabbed the location just outside the door and ran 5 single line traces (Up, Down, Left, Right, Forward) to see what was out there.
Side Note: I say “Left”, “Right” and “Straight” because I am doing everything 100% relative to the door being processed. In doing everything relative to the door, I can build a room in any direction without needing a separate routine for each direction I would build in.

I thought this was working for a while until I finally realized these traces wouldn’t find rooms that were built on a diagonal from the doorway

So my next thought was … if 5 traces isn’t enough… I need more. (including both top-down and perspective views for this to improve clarity).

1. See how much room I have Up and Down
   
   I took the results of this trace and divided it by 300 (the height of a door/wall) to see how many doors/walls I could fit in the space available.

2. For every vertical I had available, I ran traces left and right as well. In this picture I show that the prior step determined I could go both up a floor and down a floor. Save the values of each left/right trace into their own array.
   

3. For every horizontal “segment” found in step 2, run a forward (away from the door) trace. Save the values into an array.
   

4. Compile the results. For every left/right/forward trace, go through the array and get the lowest value in the array. The room can only be as big in that direction as the lowest trace will allow.

5. Use the up/down/values from step 4 to build the room.

This worked … OK. Overall it seems much more intensive than I had planned, but it kind of worked. As I was roaming about my game though, I found instances where rooms were being created inside other rooms. The reason this happens is because two or more doorways were leading into the same area. Both doorways get “processed” and build a room on top of each other. I thought I had taken steps to prevent this. I have a system in place that, when placing a door or wall, it checks to see if it is up against another door. If it is, remove that door from the array of doors to be processed so that it doesn’t try to make another room. But it seems that’s not working.

In this example, both room 1 and room 3 have doorways leading into the same area. Example isn’t truly accurate, the rooms would never be the same exact size, but you get the idea.

So room 1 processed the eastern door and created room 4. Room 3 will later process the southern door and run the traces INSIDE room 4 and build another room inside it.

After all this, I decided to add another layer of checks to the process. I created a 100x100 collision box actor. When my traces are done, I spawn the collision box scaled to the room’s proposed dimensions and check to see if it’s overlapping any actors. If it is, I bail out of the whole thing. But then I started thinking… if I’m doing that, why bother with the trace at all? Toyed with the idea of just generating collision boxes of random sizes and seeing if they overlap. Maybe try 5-10 times with random boxes. If it still overlaps after all that, just remove the doorway and decide there’s not enough room. Seems messy though.

So I’m looking for new/creative ways to solve this problem. Maybe one without so many steps. Debugging random generation is insanely difficult and I spend most of my time reading log files to determine what got spawned where and why.

Anyways, thanks for reading.

[Cobryis]

Trace out in all outward directions from the corners of the door. Let’s build this wall by wall instead of room by room? So the first wall is the wall parallel to the wall of the door. Actually, let’s just find the length the wall needs to be on one side of the door. We’re going to choose the shortest between 3 lengths. A random length, or if shorter, one of the lines tracing from the relevant corners of the door. Now we have the end position of that side of the wall. Next lets do the wall adjacent to that wall. From that end position, we have to choose the shortest between 3 lengths. A random length, or lines tracing from the corners of that wall. If we hit a door, then we’re now going to have to calculate the next half of the wall after the door we hit. If we didn’t, the now we have to decide to turn the wall left or right. For the sake of simplicity, we turn left in order to make our room a simple box.

Now, that’s the basic idea, but there are a few caveats. What if when our wall turns left for the last time, it’s not aligned with the wall of the initial door? Well, if we step back we should have also done the other half of the wall around that first door. Then we would have known at least its end position. Then the wall we later generated parallel to that should have to choose between either that length or the shortest traced length. If the shortest traced length is shorter than the wall we’re running parallel to, the first one I described at the start of this paragraph, then we need to make that first wall shorter to meet with the shortest length.

This is just a rough approach I would take. What I’ve described is sort of like a Dynamic Programming approach, which would be the best way I think to solve this. The other solution is to go for a less complex design and just have preset sized rooms that fit together like puzzle pieces. You then randomly select an appropriate puzzle piece (room) to build your level.

Your MS Paint drawings are awesome by the way.

If you don’t understand my approach, or if my approach lacks an understanding of yours, then its probably my fault for improvising this answer or not using MS Paint.

EDIT: Also, for your room inside a room problem, once you’ve traced your way to a door AND actually generated the room next to that door, you just mark that door as visited, and then it won’t be allowed to make any rooms.

EDIT 2: Some sort of ‘plane’ tracing would be better. I’d have to do more research into that.

[Chumble]

Well, I read through your post twice but I don’t quite follow you.

@Cobryis;170428

Trace out in all outward directions from the corners of the door.

So, like that? Orr… no … that’s probably not it…

For now let’s just pretend there’s no elevation changes. Every room will be 300 units tall. I can add taller rooms and rooms offset on the Z axis later once the core functionality works.

Are you suggesting that a trace is run for every wall/door placed to see if there’s space for the next wall? Doesn’t seem like it but I’m having a tough time understanding :-/.

Just for some added detail, this is how my rooms are currently built.

So it is kinda wall-by-wall, but the only check done when the wall is placed is to see if it’s up against another door/wall. At the point that the walls are being built, the system already assumes there’s enough room for the whole thing.

@Cobryis;170428

What I’ve described is sort of like a Dynamic Programming approach

The way I have it currently is supposed to be dynamic, detecting walls and doors in other rooms and adapting to make it work with the current room. I feel like looking at this too heavily from the perspective of a single wall might add to the complexities.

@Cobryis;170428

The other solution is to go for a less complex design and just have preset sized rooms that fit together like puzzle pieces. You then randomly select an appropriate puzzle piece (room) to build your level.

That’s actually pretty interesting. I plan on completely randomizing the room’s interiors (furniture, lights, objects, etc) so I guess if I had enough precreated shapes the user might not notice that the shape of the room is identical to what they’ve seen before. I could build the room and have a collision box encompassing the whole thing… then simply try to place it. If it didn’t work, try again with a different room. I could keep some parts of it random by having a number of “potential” doors within the room and randomly decide if they’re going to be doors or walls. At the end of the basic room generation when I start to generate room contents, I would need to loop through every room, then every door for that room. If the door is up against a wall, have a chance for the wall to be a door (if it fails, make the door a wall). If it’s up against a door… nothing needs to happen. If it’s up against nothing (empty space), turn the door into a wall to make sure the map is contained.

It could work and might be easier… I can optimize the rooms so that I don’t need 80 different actors for a single room… plus it allows me to more easily place rooms of different shapes (like Tetris blocks). Definitely something to think about.

[Cobryis]

@Chumble;170511

Well, I read through your post twice but I don’t quite follow you.

So, like that? Orr… no … that’s probably not it…

For now let’s just pretend there’s no elevation changes. Every room will be 300 units tall. I can add taller rooms and rooms offset on the Z axis later once the core functionality works.

Are you suggesting that a trace is run for every wall/door placed to see if there’s space for the next wall? Doesn’t seem like it but I’m having a tough time understanding :-/.

Sorry, that’s what I started with but then I sort of changed strategy. Let’s only do wall lengths for now as I think you suggested. When I was saying you have to choose the shortest of 3 lengths, I meant: We want the wall to be some random length; however, if that random length is too long, then we have to choose the next shortest length. Tracing out 2 lines from the door allows the room to be of any height at any point, and allows adjacent room to be even half the height of the room you’re in.

However, I don’t really like all this line tracing. Ideally we should come up with some sort of ‘plane’ tracing.

Just for some added detail, this is how my rooms are currently built.

So it is kinda wall-by-wall, but the only check done when the wall is placed is to see if it’s up against another door/wall. At the point that the walls are being built, the system already assumes there’s enough room for the whole thing.

The way I have it currently is supposed to be dynamic, detecting walls and doors in other rooms and adapting to make it work with the current room. I feel like looking at this too heavily from the perspective of a single wall might add to the complexities.

My point about dynamic programming is that you can’t place the walls until you’ve mapped out the room. The problem is that your first wall could go X length, but the wall that will be parallel to it may not be able to go X length, and so the first wall would need to be shorter (if we’re making rectangles).

[Cobryis]

If you didn’t understand my original post, I don’t think you missed much because your new image of the algorithm seems pretty similar to what I was trying to say. The difference is that I try to measure the necessary lengths of the walls (instead of placing wall segments) for the whole room first. Also, do you understand the EDIT about marking a door as visited?

EDIT: I just edited this whole post. This is the dynamic programming strategy I was talking about: http://en.wikipedia.org/wiki/Dynamic_programming

[Chumble]

@Cobryis;170537

My point about dynamic programming is that you can’t place the walls until you’ve mapped out the room. The problem is that your first wall could go X length, but the wall that will be parallel to it may not be able to go X length, and so the first wall would need to be shorter (if we’re making rectangles).

Yeah… all those traces map the room out fully, but I will admit I really don’t like running them all. An average sized room is probably about 7x7x2 which results in 20 traces per room. Simply placing a massive collision box the size of a potential room and seeing if it overlaps with anything would be much more straightforward, but the problem is I would just be guessing at how big it could be, potentially quite a few times.

Also, one advantage to my current implementation is I find rooms end up being right against eachother fairly often, allowing me to have paths that loop back on themselves

Left = No looping, a bunch of individual paths that can split, but never backtrack
Right = Lots of looping. Too many, really, but it’s just an example.

I think I’m just looking for excuses to draw examples in MSPaint now. I really don’t feel like working

Edit: Random attached image I don’t remember making. Can’t seem to get rid of it either. Weird.

Edit 2: Replying to your edit

@Cobryis;170544

If you didn’t understand my original post, I don’t think you missed much because your new image of the algorithm seems pretty similar to what I was trying to say. The difference is that I try to measure the necessary lengths of the walls (instead of placing wall segments) for the whole room first.

Ok, so rather than place five 200-unit wide walls, just scale the wall to be a single 1000-unit wide wall? Would help with optimization, that’s for sure. It does muck with my “Every wall placed has a chance to be a door” thing though and I’m not sure how I’d handle creating new doors or modifying existing doors should the need arise.

@Cobryis;170544

Also, do you understand the EDIT about marking a door as visited?

Yes, but I don’t think it’s relevant. Each doorway can only be processed once.

Ex:
Room Array = {Room1,Room2}

Room1’s Door Array {Door1,Door2,Door3}
Room2’s Door Array {Door1,Door2,Door3,Door4}

The logic is:
For each item in Room
For each item in Door

So it will do Room1, Door1,Door2,Door3…Room2, Door1,Door2,Door3,Door4

And for each door, it might tack another room onto the end of the Room array but it will never go back and try to process rooms or doors that have already been executed as the arrays are append only and I do not remove items from them.

That being said, I think you answered this way because I did a poor job explaining (Although your answer might just work anyways). Going to refer back to this image:

So here in my Room array is Room1,Room2,Room3

Room1 (for some reason) still has yet to process the right doorway and Room3 has yet to process the bottom doorway.

When Room1’s right doorway processes and it creates Room4, when the walls are placed it WILL find the bottom doorway of Room3. When it does, right now it says

1. Is this door the door that created this room? If so, skip the rest of this, it’s not needed.
2. What room does this door belong to?
3. Get the Door array from the owning room
4. Remove this door from the Door array from the owning room

So this will never remove a door from a room that has yet to be processed. Since the Door array or the owning room has not yet been processed, it’s no big deal to remove it from the array.

The problem with the above is it is SO VERY INCREDIBLY HARD to determine if it worked… and if it doesn’t look like it worked, it’s SO VERY INCREDIBLY HARD to determine where it went wrong. I’m guessing right now it’s removing the wrong door from the array, causing one doorway to not generate a room and another to generate a room inside a room.

In using your solution, I could simplify this. Have a boolean variable on each door called “Blocked”, default to false. If I find a doorway when creating a room, simply set the value of “Blocked” to be true. Then, when I’m looping through each doorway, checked the “Blocked” variable. If it’s set… skip that door.

[SaxonRah]

When making something of this scale you should break down everything in to smaller problems. I personally do my generation different but this approach should work.

If you’re trying to figure out how much room you have in for example a 2 axis area x and y, you need to do a 4 directional trace (nsew) from the rooms center point to the half the total size of that axis.

lets say you have a room with a door. you go from the door, to half the new room’s size for that axis it’s being built from and do traces like the picture if it’s clear on all sides, then build room, if not you could shrink the new room in the axis that failed it’s size check trace

&stc=1

(green arrows are traces, red arrow is half of new rooms size in x, blue dot is center point, black room is starting room, gray is new room)

(also yes when you are making generators it’s far easier to make a single level generator and then repeat on your tile size in z)

[Cobryis]

@Chumble;170559

Yeah… all those traces map the room out fully, but I will admit I really don’t like running them all. An average sized room is probably about 7x7x2 which results in 20 traces per room. Simply placing a massive collision box the size of a potential room and seeing if it overlaps with anything would be much more straightforward, but the problem is I would just be guessing at how big it could be, potentially quite a few times.

Line tracing is pretty cheap and procedural generation is not going to be much cheaper unless you start taking major shortcuts.

What kind of experience are you going for? That’s typically what would determine your algorithm.

One other idea I have is to just procedural place a bunch of boxes and procedurally place a bunch of boxes and then procedurally tear down walls between some of them, and place doors between others. It’s obviously more complex than that though. You know how minecraft generates biomes and what not? Well if the sort of building you’re going for follows a natural pattern, then maybe that’s how your algorithm should construct it. Like, step 1 of the algorithm ‘paints’ a hallway. Step 2 attaches rooms to it. Step 3 Adds a stair case and places another hallway at the top. Step 4 places more rooms. Maybe Step 5 checks if rooms are on top of each other and then makes a secret passageway between them.

[Chumble]

@SaxonRah;170562

When making something of this scale you should break down everything in to smaller problems. I personally do my generation different but this approach should work.

If you’re trying to figure out how much room you have in for example a 2 axis area x and y, you need to do a 4 directional trace (nsew) from the rooms center point to the half the total size of that axis.

lets say you have a room with a door. you go from the door, to half the new room’s size for that axis it’s being built from and do traces like the picture if it’s clear on all sides, then build room, if not you could shrink the new room in the axis that failed it’s size check trace

&stc=1

(green arrows are traces, red arrow is half of new rooms size in x, blue dot is center point, black room is starting room, gray is new room)

(also yes when you are making generators it’s far easier to make a single level generator and then repeat on your tile size in z)

But what if you have another room at the diagonal?

The traces will miss it completely and the rooms will overlap. This is the exact problem I had to begin with

I ran the traces from the doorway itself rather than the center (because I didn’t know where the center would be until I actually ran the trace).

[Chumble]

@Cobryis;170569

Like, step 1 of the algorithm ‘paints’ a hallway. Step 2 attaches rooms to it. Step 3 Adds a stair case and places another hallway at the top. Step 4 places more rooms. Maybe Step 5 checks if rooms are on top of each other and then makes a secret passageway between them.

I kinda feel like that’s what I already have in place … make a room, give it doorways. For each doorway, make a room. Repeat… unless I’m misunderstanding you.

[Cobryis]

@Chumble;170570

But what if you have another room at the diagonal?

The traces will miss it completely and the rooms will overlap. This is the exact problem I had to begin with

I ran the traces from the doorway itself rather than the center (because I didn’t know where the center would be until I actually ran the trace).

When you then trace into the wall after it turns, you’ll find that other room. You can get the size of the segment of wall you went to far into, and then move that original wall’s end point back.

[SaxonRah]

I’ll make something for you to check out, give me a moment while i use some black magic to create a blueprint.

[Cobryis]

@Chumble;170572

I kinda feel like that’s what I already have in place … make a room, give it doorways. For each doorway, make a room. Repeat… unless I’m misunderstanding you.

I’m going to MS paint now.

[Chumble]

@Cobryis;170576

I’m going to MS paint now.

MSPAINT PARTY WOOO! Sorry for any dial-up users who load this thread. But seriously… get better internets.

[Cobryis]

Note that this isn’t exactly what you were going for. I’m just trying to give you ideas.

Step 1 - easy
Step 2 - you choose some outside box to be the start and some box at some other point (in this example, the opposite end) to be the other end of the hallway. you then find the shortest path there and open the walls between the boxes of that path
Step 3 - you build rooms off the hallway using adjacent blocks. in this example, my algorithm would make sure every room connects to the hallway. maybe in a more complex one, some rooms would be storage closets for other rooms and would not connect to the hallway or any other room.
Step 4 - you go along the hallway and make sure that every room along it has at least one entry door. You then go into the rooms and allow, at random, for doors to be connected between rooms.

Notes: See that tiny room between the two big ones on the bottom? It would look a bit odd for either room of the big room to have a door to that small room. Anyway, your algorithm could also make sure that rooms have a min and max number of doors given their size. So if that room is 1 node, then maybe the algorithm dictates it can only have 1 door (which was chosen by the hallway). For bigger rooms, maybe if they have more than 2 nodes they can have more than 1 door, and then if they have more than 1 adjacent room, they can have more than 2 doors?

[ItsBenji90]

Are you doing this map generation during runtime? Like as the player ventures through, the map generates new rooms?
I’ll be making something similar for my top-down shooter but having the whole map generated before the player jumps in.

[Chumble]

@Cobryis;170584

Note that this isn’t exactly what you were going for. I’m just trying to give you ideas.

Step 1 - easy
Step 2 - you choose some outside box to be the start and some box at some other point (in this example, the opposite end) to be the other end of the hallway. you then find the shortest path there and open the walls between the boxes of that path
Step 3 - you build rooms off the hallway using adjacent blocks. in this example, my algorithm would make sure every room connects to the hallway. maybe in a more complex one, some rooms would be storage closets for other rooms and would not connect to the hallway or any other room.
Step 4 - you go along the hallway and make sure that every room along it has at least one entry door. You then go into the rooms and allow, at random, for doors to be connected between rooms.

Notes: See that tiny room between the two big ones on the bottom? It would look a bit odd for either room of the big room to have a door to that small room. Anyway, your algorithm could also make sure that rooms have a min and max number of doors given their size. So if that room is 1 node, then maybe the algorithm dictates it can only have 1 door (which was chosen by the hallway). For bigger rooms, maybe if they have more than 2 nodes they can have more than 1 door, and then if they have more than 1 adjacent room, they can have more than 2 doors?

That’s an interesting way to go about it and I have mixed feelings. So basically, you create a giant grid, determine a path from start to finish, then populate rooms along that path (not necessarily filling in every single room). Right off the bat you establish there’s a valid way to get from “start” to “end” and using the grid, you’ll never have rooms overlapping. It’s interesting. I don’t know if I’ll use it, but it’s a creative solution and that’s what I asked for Thank you

@Lazy Games;170586

Are you doing this map generation during runtime? Like as the player ventures through, the map generates new rooms?
I’ll be making something similar for my top-down shooter but having the whole map generated before the player jumps in.

Right now all map generation is done before the player spawns. I have my setup done dynamically enough that if I find that the generated map causes too much lag, I can have the new room get generated when the player activates the connecting doorway. I would honestly like to avoid this approach because when I’m creating the room contents, I want to be able to better pair up objectives.

Ex: Find a box in one room with a strange object, spawn a strange device halfway across the map that the object can be used in. Or even just mapping locked doors/keys … I could have it be random but then you never know if the player will have enough keys to make it from start to end… and if you create a system where the player can always get more keys somehow, it takes away from the game.

So far, the only performance issue I’ve seen when running the game is when dynamic lighting is on and it’s trying to light every room… to be expected. I’ve already taken steps to avoid that (disabling lights where there’s no player nearby).

[SaxonRah]

I realized i do use 8 traces for a square room, n s e w ne nw se sw.

I’m still conjuring this bp up.

[Chumble]

@SaxonRah;170594

I realized i do use 8 traces for a square room, n s e w ne nw se sw.

Hm… yeah. If I’m doing stuff on the Z axis as well I would need … uhh… 17? Might have put that together wrong in my head.

Edit: If I decide the Z axis rooms ahead of time, then it’s 8 traces per elevation (at least one, at most like 5…). I don’t know if that’s an improvement on the traces outlined in the first post.

[SaxonRah]

@Chumble;170599

Hm… yeah. If I’m doing stuff on the Z axis as well I would need … uhh… 17? Might have put that together wrong in my head.

Depends on what kind of generation you are doing. but generally If you want multi-leveled things you should generate 1 floor at a time, that way you dont need z traces