Hey everyone,
I am currently looking for the best way to achieve a floor-plan/structure to the image below:
Refer algorithm - Procedural... house with rooms generator - Game Development Stack Exchange
I read through the post, however was a bit confused. I also attempted to use binary space partitioning, but unfortunately it didn’t create “paths” and more or less sectioned off the floorplan.
Anyhoot, what would be the best(algorithm) to achieve the image I first posted?
6 Likes
For hallway generation, the algorithm described in the stack overflow article is nearly identical to a binary space partitioner, it just has some added “width” in the middle for the hallway. The first cut in your image was the lowest horizontal hallway, with the vertical hallways going north and south off of it next. Once the groups of rooms (as defined by the hallways) are sufficiently small you split the rooms into halves, thirds, forths, ext. For each room, it has a random probability to continue splitting, decreasing to zero as it nears a minimum size. Lastly, the each room needs at least one door. Any wall can be chosen for this, but the image above prefers walls with a hallway on the other side.
Okay, so what you are saying is for the first one it split it into two pieces, and then just adding “padding” for the initial hallway?
Yup. You can continue splitting groups of rooms with hallways in the same way to split groups of rooms with walls: a probability to continue splitting that decreases as you go.
I understand the room splitting (keep splitting until room = min_size), however I am just confused with the hallways/corridor production.
So are you saying that the rooms are just constructed as is, and that padding is just added to achieve the hallways?
I’m not sure what your seeing. Let’s work through a little of the implementation and maybe that’ll clear it up.
Let’s start the algorithm with a point and X / Y dimensions. I randomly choose either X or Y to split, then where to split on that dimension. This gives me three results: a point and X / Y dimensions for two groups of rooms, and a hallway centered at my split represented by the dimension I choose, the split location, and the width. The hallway is assumed to extend the length of its parent area. Each of the groups of rooms have a corner point and dimensions that account for the width of the hallway. I continue the algorithm on each of the new groups of rooms if a randomly generated number is greater than the continuation probability given their size.
1 Like
Ok I think I’m grasping this better… (thanks again for bearing with me on this!)
So I have my plane, generate a random point on it and then split the plane X or Y, and then create a “hallway” there with whatever defined width I provided, then to generate more hallways I simply find a random point on the original line I split and then split on the opposite axis, and just keep repeating with that?
Close. The hallway creates two sides. Each side can be represented in the same format as your original plane. This allows you to call the same function again to split each side with another hallway. Yes, the direction of the hallway should be the opposite of the hallway that created a side. Your problem is naturally a recursive one, but instead of one path of recursion, it splits into two at each step. The end result is a tree-like traversal depth first.