- Forum
- General C++ Programming
- Complicated Project, procedural generati
Complicated Project, procedural generation
I am trying to make a random generator for building interiors, but, not the standard rogue-like stuff. I am wanting something sensical, and that fills in the designated space without leaving a bunch of "blank" areas that don't make sense. I am also trying to avoid reliance on large tiles.
The output I'm going for right now is have a 3d vector as a map of the building (I'm not married to this idea, if something better can be found.) Each cell refers to a one yard space or wall section.
What I would like help with, is trying to figure out the algorithms to split the space in a sensible manner with hallways, appropriate rooms, including closets or other sub-rooms. Also, I am rather new to developing programs, so any advice on efficiency or good practices with procedural generation, or even how to layer the various classes to avoid cyclical dependency, would all be welcome.
I figure on sectioning of areas as having a particular type, so a hospital might have a labs areas, surgery area, inpatient rooms, clinic, offices, etc
The output I'm going for right now is have a 3d vector as a map of the building (I'm not married to this idea, if something better can be found.) Each cell refers to a one yard space or wall section.
What I would like help with, is trying to figure out the algorithms to split the space in a sensible manner with hallways, appropriate rooms, including closets or other sub-rooms. Also, I am rather new to developing programs, so any advice on efficiency or good practices with procedural generation, or even how to layer the various classes to avoid cyclical dependency, would all be welcome.
I figure on sectioning of areas as having a particular type, so a hospital might have a labs areas, surgery area, inpatient rooms, clinic, offices, etc
All of this is written from the perspective of a 2d plan. I strong suggest you get that working before trying to fill multiple floors/3d spaces.
If you want to generate a building, many buildings are basically a bunch of rooms connected by doors. I would start out by coding that. i.e. Filling a space with rooms, leaving no gaps and ensuring there is at least 1 single walk that visits all of them. If you look to roguelikes, there are tons of tutorials and readings on exactly this kind of thing. You can use fairly free (but reasonable) constrains on room sizes to make the generation quick and easy.
Next up, you can look at customizing your algorithm. I would do this by defining room types. e.g.
"stdroom" -> A room with size n x m where n & m satisfy: 4 <= x>= 10 with any amount of doors.
"surgeryroom" -> n x 6 where n satisfies 8 <= n <= 10, with 1 door.
"Patientroom" -> 4 x 8 with 1 door. Must link to a corridor.
"corridor" -> 4 x n where n satisfies 6 <= n <= 20 with any amount of doors.
You could speed up generation by having some large standard templates already made up.
The algorithm would ask for how many rooms of each type and the total area for fitting them all into. Then check the total area asked for is <= building space. You can also check for other rule breaches such as having 0 corridors and 4 patient rooms.
Then, start filling in rooms from the top corner* and working across, ensuring each room is obeying its own rules, ensuring to fill in space at 100% rate until...
We fit the stuff all in.
OR
We failed to fit the stuff in.
I would suggest giving the algorithm x tries to try and fit all the rooms in and if it fails on all those attempts, say that the room configuration doesn't look like it can be done.
Btw, I am currently making a roguelike and spent tons of time reading about dungeon generation. There are LOTS of useful things for you to read up on in those articles/tutorials etc if you haven't done this kind of thing before. Do not be so fast to disregard them!
*If you use any templates, before this stage, see if any of the room combos fit any templates and try laying those first. Templates should consist of room combinations fitting into a space very efficiently, probably in several different shapes (so instead of trying to fit 9 rooms randomly, the algorithm throws all 9 into pre-set template configurations and only spends time with that).
If you want to generate a building, many buildings are basically a bunch of rooms connected by doors. I would start out by coding that. i.e. Filling a space with rooms, leaving no gaps and ensuring there is at least 1 single walk that visits all of them. If you look to roguelikes, there are tons of tutorials and readings on exactly this kind of thing. You can use fairly free (but reasonable) constrains on room sizes to make the generation quick and easy.
Next up, you can look at customizing your algorithm. I would do this by defining room types. e.g.
"stdroom" -> A room with size n x m where n & m satisfy: 4 <= x>= 10 with any amount of doors.
"surgeryroom" -> n x 6 where n satisfies 8 <= n <= 10, with 1 door.
"Patientroom" -> 4 x 8 with 1 door. Must link to a corridor.
"corridor" -> 4 x n where n satisfies 6 <= n <= 20 with any amount of doors.
You could speed up generation by having some large standard templates already made up.
The algorithm would ask for how many rooms of each type and the total area for fitting them all into. Then check the total area asked for is <= building space. You can also check for other rule breaches such as having 0 corridors and 4 patient rooms.
Then, start filling in rooms from the top corner* and working across, ensuring each room is obeying its own rules, ensuring to fill in space at 100% rate until...
We fit the stuff all in.
OR
We failed to fit the stuff in.
I would suggest giving the algorithm x tries to try and fit all the rooms in and if it fails on all those attempts, say that the room configuration doesn't look like it can be done.
Btw, I am currently making a roguelike and spent tons of time reading about dungeon generation. There are LOTS of useful things for you to read up on in those articles/tutorials etc if you haven't done this kind of thing before. Do not be so fast to disregard them!
*If you use any templates, before this stage, see if any of the room combos fit any templates and try laying those first. Templates should consist of room combinations fitting into a space very efficiently, probably in several different shapes (so instead of trying to fit 9 rooms randomly, the algorithm throws all 9 into pre-set template configurations and only spends time with that).
Most of those resources, that I have thus far found, do one if two things, either everything is same size squares put together which gets repetitive and doesn't make for "realistic" layouts, or they leave gaping holes everywhere. Those are both things I want to avoid.
If you know of one that doesn't, I'd like to hear it.
As for buildings, generally only houses and factories are a bunch of rooms connected by doors. Most other building types, like apts, hospitals, offices, etc, are corridors that act as the highways to access everywhere, which then connect the rooms, and a few rooms connect only through another room rather than a corridor, usually closets and premium offices for those that have a private secretary.
If you know of one that doesn't, I'd like to hear it.
As for buildings, generally only houses and factories are a bunch of rooms connected by doors. Most other building types, like apts, hospitals, offices, etc, are corridors that act as the highways to access everywhere, which then connect the rooms, and a few rooms connect only through another room rather than a corridor, usually closets and premium offices for those that have a private secretary.
Well I'm not exactly sure what your end goal is with your project? And that really does affect what algorithms you want to be using. If you goal is to end up with buildings that are 'realistic' looking in design, I personally would do what I suggested above and tweak the algorithm and templates until results were good.
There are other methods though. For instance, you could generate a perfect maze and then knock out walls to create rooms in it, or lay down corridors first and fill in the spaces with rooms.
Some reading that might be of interest:
http://pcg.wikidot.com/
And of particular interest to you should be this page: http://pcg.wikidot.com/pcg-algorithm:city-generation
There are other methods though. For instance, you could generate a perfect maze and then knock out walls to create rooms in it, or lay down corridors first and fill in the spaces with rooms.
Some reading that might be of interest:
http://pcg.wikidot.com/
And of particular interest to you should be this page: http://pcg.wikidot.com/pcg-algorithm:city-generation
Basically, the only stuff I've found so far either says to make a bunch of lego blocks, generally all of the same size, and randomly join together, or to randomly expand in some direction, which tends to leave holes. Neither option makes for very sensible layouts, and the lego version can get repetitive quite quickly.
Besides, I don't particularly want all rooms of the same type to always be the same size and shape.
Besides real structures rarely have the "bunch of rooms connected by doors" style, (generally only houses, factories, and games) in real buildings, the corridors are like a highway system connecting all the areas together, and most rooms connect to a corridor.
I'm not particularly looking for the easy way out on this, I just need it to work.
A couple core ideas I'm trying to work from so far,
A, define areas using a tree structure, primary entrance -> a few major corridors-> major rooms and minor corridors-> minor rooms. Some rooms might have subrooms, such as closets or an office and secretary desk combo. Also, larger office buildings can have areas of this structure within larger areas.
B, possibly make the corridors, the divide the remaining space into rooms.
C, do the skeleton of the entire structure, then do individually themed areas.
These are some of the things I was thinking of. I don't really want another tile builder, nor another ultra random dungeon. I want a sensible structure where I can set some ground rules, then generate a hundred buildings each unique and different, yet still seem to be structures that might actually be used in real life.
Besides, I don't particularly want all rooms of the same type to always be the same size and shape.
Besides real structures rarely have the "bunch of rooms connected by doors" style, (generally only houses, factories, and games) in real buildings, the corridors are like a highway system connecting all the areas together, and most rooms connect to a corridor.
I'm not particularly looking for the easy way out on this, I just need it to work.
A couple core ideas I'm trying to work from so far,
A, define areas using a tree structure, primary entrance -> a few major corridors-> major rooms and minor corridors-> minor rooms. Some rooms might have subrooms, such as closets or an office and secretary desk combo. Also, larger office buildings can have areas of this structure within larger areas.
B, possibly make the corridors, the divide the remaining space into rooms.
C, do the skeleton of the entire structure, then do individually themed areas.
These are some of the things I was thinking of. I don't really want another tile builder, nor another ultra random dungeon. I want a sensible structure where I can set some ground rules, then generate a hundred buildings each unique and different, yet still seem to be structures that might actually be used in real life.
| Basically, the only stuff I've found so far either says to make a bunch of lego blocks, generally all of the same size, and randomly join together, or to randomly expand in some direction |
Maybe try reading those links I suggested?
| nor another ultra random dungeon. I want a sensible structure where I can set some ground rules, then generate a hundred buildings each unique and different |
...And you really should should read about dungeon generation. Dungeon generation is not random! It sounds like you don't know much about this topic and just reading about procedural generation in general will help you a great deal in getting ideas for how things work and how to make algorithms at least somewhat efficient.*
Also, the way you speak of you core ideas makes it sound like you haven't written any code yet. Write some basic procedural generation examples first, THEN brainstorm how you're going to make your implementation.
*Just as an example:
| B, possibly make the corridors, the divide the remaining space into rooms. |
If you had been reading about dungeon generating algorithms, you might have seen a recursive division method (with an early cutoff) could be a good algorithm for this.
Hmm, somehow when I reloaded the page it was missing my second to last post and your following post with the links. I thought I needed to retype everything, thus I did.
As for the link, I had found that a while ago, but perhaps I just hadn't hit the right subpages yet. Trying to navigate that site is a nightmare, and all the deadends are just irritating, so I've been tackling it slowly.
As for random dungeons, I understand they aren't truly random and there are slight variations.
However, all the algorithms I've found so far boil down to selecting a new piece and trying to place it somewhere, checking whether it would fit there, and then either placing it, or trying a new spot, generally picking a connection to existing pieces.
Alternatively, making tiles and placing those like an automated game of tetris.
Perhaps it is just my underwhelming google fu (my google fu is horrible), but I haven't found much in the way of satisfactory level creation.
As for a subdividing algorithms, I have not actually seen anything of that sort. Of course, I hadn't thought of trying to search that term.
I do have some code, not perfect yet, but it does give me a map of the right size, and I have tried a few things, but nothing really yet has accomplished what I wanted.
As for the link, I had found that a while ago, but perhaps I just hadn't hit the right subpages yet. Trying to navigate that site is a nightmare, and all the deadends are just irritating, so I've been tackling it slowly.
As for random dungeons, I understand they aren't truly random and there are slight variations.
However, all the algorithms I've found so far boil down to selecting a new piece and trying to place it somewhere, checking whether it would fit there, and then either placing it, or trying a new spot, generally picking a connection to existing pieces.
Alternatively, making tiles and placing those like an automated game of tetris.
Perhaps it is just my underwhelming google fu (my google fu is horrible), but I haven't found much in the way of satisfactory level creation.
As for a subdividing algorithms, I have not actually seen anything of that sort. Of course, I hadn't thought of trying to search that term.
I do have some code, not perfect yet, but it does give me a map of the right size, and I have tried a few things, but nothing really yet has accomplished what I wanted.
If you could provide a picture of you start-state and end-state, then I could probably direct you to the appropriate articles and make some better targeted suggestions. Exactly what your start and end state will be will affect things a lot.
Okay, assuming I understand start and end states correctly,
The pure concept,
I want to input the shape and size of the building along with the external features that affect the internal features (windows, doors, gaping holes in walls, etc), I also want to have optional inputs for things like building type (office building, apts, hotel, etc), layout theme, and a few other things to be added later for placing items, occupants, etc.
I want it to output a generic map of the layout in a form that doesn't specify the visual graphics (the idea being that each section of wall, floor, etc, can then be be chosen based on visual theme after the layout is generated.) I want the layout to be more realistic in terms of how things are laid out and connected (so that you might have an entrance of some sort, corridors leading to all the important areas, and rooms or nested areas connecting to the corridors, also considering stairways/elevators, maintenance areas, closets, rooms with plumbing being grouped together, etc. And of course to avoid strange spaces like 1'x15' wide rooms.
Currently my solution is to make a building of connected rectangular wings (each wing can have it's own size and be linked). I realize this limits my options in regards to circular or angled structures, but I haven't figured out a better method yet. Each wing is a grid map with odd numbered rows/columns being walls, and even numbers being the actual spaces. Thus each cell of the map describes what types of floor, door, window, wall, etc belongs in each spot.
The pure concept,
I want to input the shape and size of the building along with the external features that affect the internal features (windows, doors, gaping holes in walls, etc), I also want to have optional inputs for things like building type (office building, apts, hotel, etc), layout theme, and a few other things to be added later for placing items, occupants, etc.
I want it to output a generic map of the layout in a form that doesn't specify the visual graphics (the idea being that each section of wall, floor, etc, can then be be chosen based on visual theme after the layout is generated.) I want the layout to be more realistic in terms of how things are laid out and connected (so that you might have an entrance of some sort, corridors leading to all the important areas, and rooms or nested areas connecting to the corridors, also considering stairways/elevators, maintenance areas, closets, rooms with plumbing being grouped together, etc. And of course to avoid strange spaces like 1'x15' wide rooms.
Currently my solution is to make a building of connected rectangular wings (each wing can have it's own size and be linked). I realize this limits my options in regards to circular or angled structures, but I haven't figured out a better method yet. Each wing is a grid map with odd numbered rows/columns being walls, and even numbers being the actual spaces. Thus each cell of the map describes what types of floor, door, window, wall, etc belongs in each spot.
Last edited on
Topic archived. No new replies allowed.