Simplicity was never my strong point 
in the image there are 3 room generators in close proximity and only the first one spawns an actual room.
Generates a room only if there is not something in the way, it’s a box trace example. this should get you going quite far!
Extract and merge the content folder into a project. to get bp, hope this helps and sorry it took so long!
Click here - the last upload i forgot a really simple get actor location node and it was all messed up because of it lol!
If you notice anything wrong just let me know i’ll fix it, you should be able to change the size of the room once its in the level by it’s actors details, if you wanna mess with it
I am a bit in a rush so I might have missed something.
I did something simular to this once on a smaller scale. If you are talking about uniform rooms, there is a easy way to fill a surface, while preventing reacreating and processing of rooms where rooms already are.
The area is filled with rooms, in a vector/array.
Each room will have a number of possible doors.
each room will have the flag visited.
There will be one searcharray.
- You will take one room in the area, mark it as visited, add it to the search array.
- Get the last room in the searh array, you take one random door for the room, check if that door leads to a visited room, if so, try again, untill you find a non visited room.
2.1 If there are only visited rooms around this room, remove the last entry in the search array, if the array is empty and there are no room to visit you are done, else, goto 2. - Turn the wall in the direction to a door, add the room on the other side to the visited list, add it to the search array, goto 2.
This will create a ordinary maze. The standard variaty, you can follow it to the end by turning right in every corner.
Of cource you can spice it up as well and combined rooms into bigger rooms later, add doors in new places, or remove them, but upon removal make sure you have some kind of code checking that you can access all areas.
The advantage of this design as well, as soon as you start backing in the search list, you know that that path has reached a logical dead end, here it would be possible to tag a room or hallway.
Rambling rambling.
Oh I saw multiple floors as well, just add rooms in the up down direction as well, and add those up down to be accessible when looking for valid rooms from a room.
The compression on the image is terrible. Maybe something is visible, maybe not, but that is the kind of result the algoritm can generate. You can’ alter the apperance a lot, say you want a lot of narrow hallways instead of random turns, then you can simply cache the last direction you went, and try that direction first when you enter a new room, or other sets of small rules on what direction to choose instead of “random”.
In that image, that happy colors come from the fact that I gave each enclosed area, a unique Id so I could logicaly know what hanged together. It’s simply done by marking the rooms with a increasing unique id as long as you have to step back in the search array, when you stop steping back because you find a new way to expand, you increase the id by one, set that one when you step back in the array and repeat.
All areas with a lower ID then the current one will be block off if you block the entrence.
I haven’t had a chance to look at this yet. Worked late, got home late, didn’t sleep… gonna be a rough day, hopefully I can stay awake long enough tonight to load this up. From the picture and the description, it sounds like you’re just placing a box and checking to see if anything overlaps. Which, while it works, it leaves you guessing as to how big you can make it. Though that may very well not be what you did… I’ll see tonight.
Actually the big part of this (and the main reason behind this thread) was because I have rooms of random size. In the original post, I outlined the steps I took to generate the map, the problem was within step 4. It basically comes down to figuring out how much space is available to use when creating a room. I appreciate the time you took to write this post, but it looks like it’s more in the direction of maze solving than spacial … uhh … logistics.
the box that is placed is actually a shape trace with its debug set to persistent. also it’s size is directly related to the size of the generated room, you could randomly generate its size and it would be no problem as the trace would encompass the future size of the generated room. it’s essentially two loops that place things in x and y.
Heres a video and 2 new blueprints to show what i did - Get these not the one in my last post, while the one in the other post works and is good these two bps are better
The black square are blueprints that build from 0,0,0 into positive x and y local space(the origin point is the lower left corner of room). the white square are blueprints that build from 0,0,0 to positive x and y in a scene component’s local space then scene component is moved half in both axis (x and y) towards negative x and y local space so that it seems like it built from negative x and y local space in to positive x and y local space(center of room origin point).
These blueprints don’t support rotation but it’s not hard at all to enable it on the center point generator, all you need to do is get the actor rotation plug it’s pin into the orientation pin of the box trace for objects node in the Room Trace Function in the ‘Build_FromCenter’ blueprint.
The black square blueprint can be rotated but you’ll have to figure out the rotation and vector logic for that one. i prefer not to rotate things if the origin is not in the center.
If you look at the portions of my map generator related to the vector field, it might give you some ideas on how you could both store all your level data and use that organization to procedurally place all your rooms.
Since you are building wall by wall, aligning everything on a grid should make things pretty simple for figuring out if a certain grid space is already occupied.
So with a grid there might be 2 general ways you go about making all the rooms you need.
Option 1; you start with a box and carve it internally into what you are looking for, similar to what Cobryis suggested as well as my own map generation.
Option Two; you start in the middle and grow out until you reach the boundaries of your level. This is what you seem to be trying to do.
Basically you can alter path finding algorithms to fill out your rooms. You just check tile by tile until you run into obstacles. Then you can either set that as a room, or abort and try a different room size or delete that door and try a different direction from the last room. The key is that as the room grows tile by tile, it hits the level boundary, other room boundaries, or other obstacles, and stops or alters course. So you might have a room randomly try to grow 10X by 5Y, but it hits something at 8X, so the room is then 8X by 5Y. Or maybe you don’t want a room that size, so you call in a different room with a smaller X, or you just drop this path and go back to the other paths(rooms/doors).
How you work any of this depends on your goals and limitations of course. Do you have standardized room sizes/modules, or can they be any dimension? Are furniture and other obstacles procedurally placed? Etc, etc.
Ohhh, I see. Two thoughts:
- If there is a very large room (including multiple levels), a small shape trace inside that first room could pass the collision check. Or even a large room that might encompass a smaller one. This could be avoided by restricting the maximum number of floors to 3 so that the top or bottom of the trace will always hit a floor/ceiling if there’s another room, but it’s kinda meh to have to do that. I don’t even know if I’d want to, but it would be nice to be able to.
- This is essentially the same process as I had done before (Place a solid rectangular actor and scale it to the room size. Run a check to see if there’s any actors overlapping) except with the problem described in 1, although probably more performance friendly. Determining the size of the box is troublesome. Some potential ways to deal with that (none of which I actually like):
-
Try a number of random shapes. If it fails N tries, wall off the door. I like random, but this might be too inconsistent.
-
Try 3 pre-set sized boxes. Small (400x400), Medium (800x800) and Large (1400x1400). If more than 0 pass, randomly pick one of the ones that passed. Then, randomly pick dimensions smaller than the size of the box that passed. This is a better version of the prior one as it at least forces the check of 3 different sizes (the prior one could constantly try boxes that were way too big without ever trying something smaller than 600x600).
-
An expanding collision box. Create a 200x200 box just outside the door. Until it collides on all X Y and Z axis (or reaches a limit), keep expanding it outwards. Once all 3 collide, back it off one step then get random dimensions within the results. This will be incredibly performance heavy I imagine but will yield the most accurate results.
Actually, everything is aligned to a grid. Every wall and door is slightly offset in their facing direction, so walls from two rooms that are back to back actually have the same world location, but they are rotated correctly so they’re facing inward and the relative offset places them next to each other rather than on top of each other. The end result is everything is aligned to a 200x200x300 grid.
That’s precisely the problem I’m dealing with - properly determining the amount of space I have for a room in 3 dimensions.
The only actual physical actors I have are Walls (200x200x300), Doors (200x200x300), Ceilings (100x100, scaled to room size) and Floors (100x100, scaled to room size). Everything in the map is comprised of those. When I am running my traces, I look at it like “How many 200 unit wide walls can I fit in this area?”, no standardized sizes other than that.
I have no room interiors yet, I wanted to get the actual rooms working first.
-
you hopefully won’t be building your rooms in a way that’s unconnected. if we build a map and start from the first room going from each of the doors and placing new rooms at each door location the new rooms being placed will only place if they have the space. they would never get built inside because they would have hit something else first.
-
OH if you need to fill a space for the maximum size ? ms paint time. mind you i have not done this in bp yet but it should work.
&stc=1
start with an accepted traced room then
&stc=1
trace from that rooms center point from 3 directions
&stc=1
try a new room with it’s size increased with relation to the trace length in that direction
&stc=1
But what happens in situations like this where you started with an accepted size but the center traces hit something else but there is a room with a close proximity yet the trace says something way different.
&stc=1
it would result with something like this which would not build, in this case i would decrease it’s size until it fit. or better yet do n,s,e,w and ne, nw, se, sw traces from the center and figure the size constants somehow
Anyone else have an idea for this ? i just keep generating new rooms till it fits grab a few in an array, select the largest
Y… yes. I think I’m mixing up problems a little bit.
Not necessarily, but I need to know what the MAX size is if I’m going to randomly generate a room that will fit there.
Exactly, yes. I am notoriously bad at explaining things, but this is what I was talking about in my original post.
I don’t mean just aligned to a grid, but also stored as a grid in an array. Each tile in the whole map needs a specific place in an array, and you check that array as you generate to see if it is a valid build location. You can just zip through a number of indexes and check to see if any of those indexes have walls already. You can do it row by row(or really any way you can think of) so that it stops when it hits a wall at any given index.
This spreadsheet shows you how I index my array to my map. I use hexagons, but if you are doing a square grid it is even easier since you don’t care about offsets.
Map your grid to an array like this, and then when you want to know what is at a position, say the next tile over, you just use your current tile’s index, use a small bit of math to find his neighbor tile’s index, and see if it is already occupied.
And that is just for placement. Once you have the grid set up like that, you can store whatever information you want about any given tile at it’s index. You could store the index for each wall tile in a room in a separate array, and then randomly choose one of those to be your door, or whatever else you want it to be. So you would have another array that is also indexed as above, and it just holds the information about whether any given tile is a door. And then you have another array that says whether furniture occupies a given tile, and on and on.
Do you have any of how you’re going to deal with AI for a procedural level?
I saw a GDC talk from the Warframe ppl and they said the most terrible part for their procedural levels were the AI implementation.
I have a new theory as to why this isn’t working. I’m an idiot.
So, I had my trace that went straight into the room… I wasn’t subtracting the original door location by the hit actor result, I was simply returning the location of what was hit. So if there was ever an obstacle in front of a door, it would hit it, then return a completely bogus number. I must have missed that step when re-making this for the 10th time…
Anyways, here’s a screenshot of the current problem. Nothing new, just an actual screenshot rather than MSPaint:
Room 2 gets created and collides with Room 1 because the traces missed the corner room. Old hat.
I’m gonna be honest… this makes my head hurt. I’ve always equated myself to a computer with very low RAM. I need to have everything out in front of me for me to look at and work through step by step… trying to do it in my head causes me to bluescreen, and I still haven’t slept yet so my already limited brain capacity is not so good. I think I’m gonna stick to my method for now because it’s something tangible I can work with.
I have absolutely no idea. Not a clue. I’m just making this up as I go, it’s my favorite way to do things :). That does add one more to the “pros” column in the implementation of having each room be a pre-created piece I can just tack on.
Yeah I work pretty much the same way and if someone had shown me that without me ever creating it I would probably completely brain dump it too.
I created the whole spreadsheet just to visualize the vector of each tile in relation to it’s index in the array. The array came first and it was a problem thinking about it and how it related to the map without some kind of visualization.
Ok, so to summarize so far, there are several approaches to random map generation
- Room By Room - This is the method I am currently using. In order to determine where the next room can do, the space must be measured. The idea is to first obtain the maximum dimensions the room could be, then randomize the dimensions to place a room there. After all the rooms are placed, I can go in and decide the contents, locked doors, “end” condition, etc.
- Room-By-Room, Semi-Planned - Same as the first method but with an actual path in mind. Instead of just placing rooms with random walls and random doors, start off by making a single path leading from the start to the end then use all the other unused doors for additional places to go.
-
Pre-Planned / Graph - Whatever Zeustiak posted
If room-by-room is the method used, we will need to dynamically determine the amount of space available.
- Line Traces
-
Up/Down/Left/Right/Straight line traces from the doorway of the previous room. This was my first method and it didn’t work as rooms could be placed in such a way where they would avoid the line trace.
-
Previous traces, include diagonals. I did not do this method as it seemed rather messy and requires (12?) traces per exit… and I’m not convinced it would always find a colliding room
-
Box Trace - (12?) line traces connected to form a rectangle. It is impossible for this trace to miss a room that would collide, but this method does not allow for an easy way to determine the maximum room size for a given space.
- Box Collision - Place a box actor of a scaled size and check to see if it overlaps with anything. This inherently has the same problem as the Box Trace in the previous section (no way to determine maximum size). There are a couple methods that might help.
-
Randomly try boxes of different sizes. Try 10 of them. If they all fail, it is determined there is not enough space.
-
Use several (3-5) pre-set sizes to “measure” the room. Will a small box fit? Medium? Large? Use the largest size that fit to randomize dimensions.
-
Expanding collision box. Place the smallest possible room sized box at the next room location. If there is no collision, expand the dimensions, one at a time. At each expansion, check collision until it collides. Then, stop expanding in that dimension. Once the box has stopped expanding (or has expanded to a pre-set limit), return the dimensions and use them to randomize the room size.
-
Premade Rooms - In the editor, create many rooms of various sizes and configurations. Each room would be fully encompassed by one or more collision boxes which, when attempting to place the room, would collide with other rooms if there were problems. There is still the issue of determining what size room can be placed, but it could be done with some of the previously mentioned methods. There are several advantages to this approach.
Pros: -
Allows me to more easily create rooms that are sized the way I might want
-
Allows me to create rooms of different shapes, not simply rectangles
-
Might make it easier later if I implement AI
-
Since they’re not built wall-by-wall, I wouldn’t need to have a room split into 100 different actors. Easier to manage plus less of a hit on performance with dynamic lighting.
Cons:
- No longer truly random (although getting into “True random” is a completely different discussion).
- Needing to make all the rooms
- Needing to make enough rooms that the configurations aren’t easily recognizable as “another room of type [x]”, guessing I would need at least 20, probably closer to 50
- Makes it much harder to have rooms that end up looping back on themselves. Premade rooms will have doorways (or potential doorways) built in, and the chance that they will happen to line up with a doorway from another room is pretty slim. This is a big one.
Hello again.
This expanding thing sounds slow. Why not choose a random size for the collision box and then where it’s closest collision is, you set that as the end point for that wall.
That’s interesting… but I have a very hard time coming up with the logic needed to do that.
So here we have the start room at world location 0,0 - exact center. The blue rooms are just stuff in the way. Dotted line is the collision box.
I run the collision check, it returns Room 1 and Room 2, the blue rooms. I can get their locations which would be 1200,300 and 500,-600 respectively. I would then need to ask each room what its dimensions are so i can try to find the wall closest to the door I’m looking at … and it all seems very messy.
I could do the collision check by component instead of by actor which would return the actual wall, but the center of the wall still might not be useful.
Anyways, I ran through a little test with premade rooms. I created 7 rooms in MSPaint
Just noticed I have two labeled “Small Room”. 5 was supposed to be “Medium Room”
Then, starting with a “Start room” with 4 exits, I went through everything step by step, randomly picking a shape to add (used random.org). I documented the whole thing, but it’s 200 lines going through every doorway and I don’t think it would help to post it.
My process was as follows:
For each room
For each door in that room
Check just outside the doorway.
If there's a wall there, consider this doorway "Blocked" and wall it off.
If there's a door there, do nothing - the path loops back on itself.
If there's nothing there...
While # of attempts is less than 6
Pick a random number 1 through 7. This number corresponds to a room shape.
Try to place that room shape, with the shape rotated so the "open" doorway lines up with the door I'm looking at***
If it collides with something, increment the number of attempts
If it does not collide
Add the room to the room array
***To make things even more random, I would have it pick a doorway in the new room shape and align it rather than always using the same one. But it was just more straightforward to do it this way with the test.
Here is the result:
It’s actually not bad… but it’s 30 rooms and the furthest you ever get from the start is 4 rooms.
But that’s just the nature of doing it this way. I could change the logic so instead of going through every door for every room, it could randomly pick a room then randomly pick a door from that room. Or I could implement one of the methods I talked about above and process a single path, giving me a distance of 15 rooms from the start to the “end”, then fill in a bunch of others (which might create shorter paths, but that happens. But I do want to reiterate, this is not a “maze”. There will be obstacles of some sort for the players to overcome before they can proceed to the next room and they will likely need to visit most of the rooms before the level is “complete”.
In doing this, only TWO rooms had doors that lined up to create loops… I was hoping for maybe closer to 4 or 5, and not ones that were right next to each other.
Overall, not bad. Not sure how it will function in 3D, but not bad.
Edit: Somehow 30 rooms seemed a lot bigger in MSPaint…
I put Room 23 in the wrong place, but let’s ignore that.
Think I’m gonna need to scale it up a bit.
I’m not at my computer right now so I can’t check, but I figured (and possibly incorrectly) that you could get the points of intersection on collision. You’d choose the closest point of collision to get your wall distance.
EDIT: And as for your premade test, that looks pretty awesome. I’d love to actually do more than theory craft, but I’m pretty busy so I’ll have to wait on actually writing my version of this.
Hmm, I’ll have to see about that.
Edit: I’m pretty sure using the “Get overlapping actors” function simply returns an array of actors. There is an actual function that can be used to create a collision box (rather than create an actor and treat it as a collision box), but I can’t seem to find it on Google. I wonder if that is what you’re referring to?
But honestly, I might just stick with the premade. My in-game reproduction of the test ended up pretty well except that it was much smaller than I had anticipated. The “Long hallway” took about 3 seconds to go through. I haven’t actually plugged them into the room generator yet, I just placed them manually. In addition to the walls, doorways, floors and ceilings, I created a vector point at each doorway that I can place either a door or a wall to finish the room.
Going to see if I can plug them into the generator tonight if I don’t get caught up carving pumpkins or playing video games.
Edit: Tested a new algorithm.
Start:
Add all pre-created rooms to a PreRoom array
Create start room with 4 doors.
Room added to "Rooms" array
Loop:
While NumRooms < MaxRooms...
Pick a random room to process. Random Number between 0 and (Rooms array length - 1)
Pick a random door to that room. Random number between 0 and (Door array length - 1)
Check just outside the room to see if there's a door or wall
If there's a door, remove the door being processed from the Door array, break
If there's a wall, place a wall at this doorway. Remove the door being processed from the Door array, break.
If nothing...
While number of attempts to place a room is less than 5 and room has not been placed
Pick a random room to add. Random Number between 0 and (PreRoom array length - 1)
Pick a random door from that room. Random Number between 0 and (Number of doors on room)
Place the new room with the chosen doorway so it lines up with the processing room at the processing doorway.
If there's a collision, increment room attempts.
If there's no collision,
Remove processed door from processed room
If processed room has no more doors..
Remove processed room from Rooms array
Add new room to Rooms array
Remove the picked door from the new room
If attempts = 5, Remove processed door from processed room
If processed room has no more doors..
Remove processed room from Rooms array
And the result:
Much more spread out than the previous one. Ignore the other numbers in the start room, I was labeling doorways.
Since it’s more spread out, there’s less chance of it looping and there was only 1 loop to be found. However, there is also rooms that are further away from the center than in the previous test. I just noticed I accidentally filled in a doorway between room 13 and 18 - that was supposed to be open.