Procedural generation of floor plans

What does a major game developer do when he needs to concoct a lot of space for the game world? Hires a bunch of artists. What makes a lazy / poor / lonely game developer in the same situation? Writes a procedural generator that does all the dirty work for it.

There are many , many articles on procedural generation of floor plans. Here are five links to articles . Only the source to none of them.

In this article I will talk about how I implemented one simple generation method on Unity3d, which leads to good results and is easily modified. With pictures and sources.

If you want, you can read the original article , but the essence is approximately as follows:

• The whole space is divided into cells like grid in architectural plans.
• Exterior walls already exist and are fed to the entrance of the program.
• There is a list of rooms that need to be placed on the plan.
• The rooms have the parameter “desired size” and coefficients of attraction to each other.
• The points of birth of rooms are scattered according to a plan in a random way, possibly with the help of some kind of approximate map.
• Then each point begins to grow rectangularly until it reaches the dimensions defined for it.
• When all the rectangles have grown, the rooms start to grow in the shape of an L until it is possible.
• The remaining free space is attached to the neighbors.

Rooms grow one wall at a time to avoid walls and rooms crawling on top of each other. The wall is selected from the largest walls of the room, if there is the same - a random one is taken. The largest wall is taken in order to increase the area of ​​the rooms was maximum, and they were "plump".
')
Now about my implementation. I didn’t bother with the realistic layout, the coefficients and the size of the rooms - these are all decorations, I worked on the basic algorithm, everything else can be added quickly. The article also speaks of special checks that prevent the appearance of U-shaped rooms, I did not do them, I do not see anything wrong with such rooms. Also, I did not arrange corridors, doors and windows, this is a separate topic, and their placement may depend on the generation of the rest of the building.

The most difficult was to choose the principle of growth of rooms and the method of storing data about them and the building. One and the same result can be obtained with the help of cellular automata or even a simple run through the array. I tried several options, I always wanted to know about the dimensions of the room and the exact position of its walls, so I created a class in which only the corners of the room are stored, and the walls are automatically created by linking two adjacent corners.

Linking walls is essentially a search for a polygon shell from a set of points. The task is non-trivial and with a bunch of dirty tricks, if you're interested, then I advise you to look here . Fortunately, I decided to confine myself to right angles between adjacent walls and made a simple algorithm:

• Find the minimum and maximum values ​​of the coordinates X and Y in the set of points.
• From the point (minX, minY) we go upstairs through the game and alternately look for a point with such coordinates, if it is not there, then we search for the right, bottom and left. When we find, we take it out of the old list, transfer it to the new list.
• From the coordinates of this point in the old list we are looking for the next point higher in the game, if we find it, we transfer it to the new list, delete it from the old one, remember that we found a wall that is parallel to Y, then the next wall should be parallel to X.
• We are looking for a point along Ix to the right and left, transferring it to a new list, remembering the orientation of the wall just found, looking further by analogy.
• The last point in the old list is simply transferred to the new one.

In the end, we get a list of angles, sorted in a clockwise direction, from which you can easily draw walls. Thanks to the sorting, it becomes easy to recognize another important thing - the direction outward from the wall of the room. In order to rotate the end of the wall outward, you need to swap X and Y in places and invert the first coordinate to get the following: (-y, x).

Rooms are stored as points, points are sorted, walls are built automatically, outward direction is known - all this is enough to check the free space on the floor plan and grow rooms. Sometimes the truth has to add new walls when the old ones have already rested against something and cannot grow.

To check the availability of cells and search for possible new walls, I use a single function that collects a list of available for growth sections of the wall supplied to the entrance. Then I sort the found segments from the whole room into categories: solid walls, pieces at the edge of the wall, central segments. I choose the largest wall available and send it to the growth function of the room, but she understands, she already has such a wall, or we need to create a new one. When there is a wall, the coordinates of its ends are shifted outwards, which leads to the automatic lengthening of the adjacent walls.


To display all the manipulations with the rooms, I use a texture, in pixels of which I bring up the positions of the walls. If you do not erase the old walls, you get filled areas, as in the gif-ke at the beginning of the article. I draw walls with the help of the Brezenham lines, which I wrote about here . In case of problems with the gluing of the walls, everything at once becomes clear. Instead of texture, you can use a two-dimensional array, or immediately operate a three-dimensional model.

Exterior walls can be generated very simply. We draw several black rectangles of arbitrary sizes, and on top of them we draw the same white ones and one pixel less on each side. It turns out a lot of different houses. You can also make them three-dimensional and cover the roof. Kanevsky's voice: However, this is a completely different story.

On the links below you can see the binary and source code of the finished project.

Unity Web Player | Windows | Linux | Mac | Sources on GitHub

Shift - Creates random exterior walls with random rooms.
Ctrl - Load a test texture with random rooms.
Enter - Remove all rooms and load a test texture.
Spacebar - Stop rooms growing
Alphabet Keyboard Unit - Enable Free Cell Search Visualization
Left mouse button on the free area - Add room
Esc - Exit

For Linux users: Make ProceduralExperiments.x86 executable using “chmod + x ProceduralExperiments.x86” and run.