September 9, 2013 at 10:49Procedural generation of floor plans
What does a major game developer do when he needs to cook up a lot of space for the game world? Hires a bunch of artists. What does a lazy / poor / lonely game developer do in the same situation? He writes a procedural generator that does all the dirty work for him.
For procedural generation of floor plans have many , very many articles . Here are five more links to articles . Only source codes to none of them.
In this article, I will talk about how I implemented on Unity3d one simple generation method, which leads to good results and is easily modified. With pictures and source codes.
If you want, you can readoriginal article , but the gist is about the following:
- The whole space is divided into cells like a grid in architectural plans.
- External walls already exist and are fed into the program entrance.
- There is a list of rooms that need to be placed on the plan.
- The rooms have the parameter "desired size" and the coefficients of attraction to each other
- The points of birth of the rooms are scattered according to the plan randomly, possibly with the help of some approximate map.
- Then each point begins to grow rectangular until it reaches the dimensions defined for it.
- When all the rectangles have grown, the rooms begin to grow in the shape of the letter L as long as possible.
- The remaining free space is fastened 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 are identical ones, a random one is taken. The largest wall is taken in order to maximize the room area, and they were "puffy".
Now about my implementation. So far I have not bothered with the realistic layout, the coefficients and sizes of the rooms - these are all embellishments, I worked on the basic algorithm, everything else can be quickly added. Also, the article talks about special checks that prevent the appearance of U-shaped rooms, I did not do them, I do not see anything bad in such rooms. Also, I did not arrange corridors, doors and windows, this is a separate topic, and their arrangement may depend on the generation of the rest of the building.
The most difficult thing was to choose the principle of room growth and the way to store data about them and the building. The same result can be obtained using cellular automata or even a simple run through the array. I tried several options, I always wanted to have an idea of 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 tricks, if interested, I advise you to look here . Fortunately, I decided to limit myself to right angles between adjacent walls and made a simple algorithm:
- Find the minimum and maximum values of the X and Y coordinates in the set of points.
- From the point (minX, minY) we go up the little game and alternately look for a point with such coordinates, if it is not there, then look for the right, bottom and left. When we find, we pull it out of the old list, transfer it to the new list.
- From the coordinates of this point in the old list, we look 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, so the next wall should be parallel to X.
- We search for a point by X on the right and on the left, transfer to a new list, remember the orientation of the wall we just found, look further by analogy.
- The last point in the old list is simply transferred to the new one.
Sort room corners
public GridVector SortCorners()
{
// Ищем границы комнаты
var minX = corners[0].x;
var maxX = corners[0].x;
var minY = corners[0].y;
var maxY = corners[0].y;
foreach (var corner in corners)
{
if (corner.x < minX) minX = corner.x;
if (corner.x > maxX) maxX = corner.x;
if (corner.y < minY) minY = corner.y;
if (corner.y > maxY) maxY = corner.y;
}
// Сортируем углы комнаты
var oldC = new List(corners);
var newC = new List();
bool parallelX = false;
while (oldC.Count > 1)
{
// Ищем первый угол
if (newC.Count == 0)
{
if (ScanUp(ref oldC, ref newC, minX, minY, maxY)) continue;
if (ScanRight(ref oldC, ref newC, minX, minY, maxX)) continue;
if (ScanDown(ref oldC, ref newC, minX, minY, minY)) continue;
if (!ScanLeft(ref oldC, ref newC, minX, minY, minX))
{
Debug.Log("Error on start");
return null;
}
}
// Ищем остальные углы
else
{
var last = newC[newC.Count - 1];
if (parallelX)
{
if (ScanRight(ref oldC, ref newC, last.x, last.y, maxX))
{
parallelX = false;
continue;
}
if (ScanLeft(ref oldC, ref newC, last.x, last.y, minX))
{
parallelX = false;
continue;
}
}
else
{
if (ScanUp(ref oldC, ref newC, last.x, last.y, maxY))
{
parallelX = true;
continue;
}
if (ScanDown(ref oldC, ref newC, last.x, last.y, minY))
{
parallelX = true;
continue;
}
}
Debug.Log("Error -------------------------------------------------");
Debug.Log("Corners: " + corners.Count);
Debug.Log("OldC: " + oldC.Count);
Debug.Log("NewC: " + newC.Count);
Debug.Log(last);
color = Color.red;
return last;
}
}
// Добавляем последний оставшийся угол
newC.Add(oldC[0]);
corners = newC;
return null;
}
bool ScanLeft(ref List oldC, ref List newC, int startX, int startY, int minX)
{
for (var x = startX; x >= minX; x--)
{
var index = oldC.FindIndex(gv => gv.x == x && gv.y == startY);
if (index > -1)
{
newC.Add(oldC[index]);
oldC.RemoveAt(index);
return true;
}
}
return false;
}
bool ScanUp(ref List oldC, ref List newC, int startX, int startY, int maxY)
{
for (var y = startY; y <= maxY; y++)
{
var index = oldC.FindIndex(gv => gv.x == startX && gv.y == y);
if (index > -1)
{
newC.Add(oldC[index]);
oldC.RemoveAt(index);
return true;
}
}
return false;
}
bool ScanRight(ref List oldC, ref List newC, int startX, int startY, int maxX)
{
for (var x = startX; x <= maxX; x++)
{
var index = oldC.FindIndex(gv => gv.x == x && gv.y == startY);
if (index > -1)
{
newC.Add(oldC[index]);
oldC.RemoveAt(index);
return true;
}
}
return false;
}
bool ScanDown(ref List oldC, ref List newC, int startX, int startY, int minY)
{
for (var y = startY; y >= minY; y--)
{
var index = oldC.FindIndex(gv => gv.x == startX && gv.y == y);
if (index > -1)
{
newC.Add(oldC[index]);
oldC.RemoveAt(index);
return true;
}
}
return false;
}
In the end, we get a list of angles sorted clockwise, from which you can easily display the walls. Thanks to sorting, it becomes easy to learn another important thing - the direction outward from the wall of the room. In order to turn the end of the wall outward, you need to swap X and Y and invert the first coordinate to get the following: (-y, x).
The rooms are stored in the form of points, the points are sorted, the walls are built automatically, the outward direction is known - all this is enough to check the free space on the floor plan and grow the rooms. Sometimes it’s true that you have to add new walls when the old ones have rested in something and cannot grow.
To check the availability of cells and search for possible new walls, I use one function, which collects a list of available for growth areas supplied to the entrance wall. Then I sort the found segments from the whole room into categories: solid walls, pieces at the edge of the wall, central segments. I select the largest wall from the available ones and send it to the growth function of the room, and she understands herself whether she already has such a wall, or needs to create a new one. When there is a wall, the coordinates of its ends are shifted outward, which leads to the automatic extension of adjacent walls.
Search for wall segments
List FindSegments(RoomWall wall, Color freeColor, Color roomColor)
{
var moved = wall + wall.outwards.minimized;
BresenhamLine(moved, new Color(Random.value * 0.7f + 0.1f, Random.value * 0.7f + 0.1f, Random.value * 0.7f + 0.1f), segmentsTexture);
var x0 = moved.start.x;
var y0 = moved.start.y;
var x1 = moved.end.x;
var y1 = moved.end.y;
var segments = new List();
GridVector start = null;
GridVector end = null;
bool steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0);
if (steep)
{
Swap(ref x0, ref y0);
Swap(ref x1, ref y1);
}
if (x0 > x1)
{
Swap(ref x0, ref x1);
Swap(ref y0, ref y1);
}
for (int x = x0; x <= x1; x++)
{
for (int y = y0; y <= y1; y++)
{
int coordX = steep ? y : x;
int coordY = steep ? x : y;
Color color = texture.GetPixel(coordX, coordY);
if (color != freeColor && color != roomColor)
{
if (end != null && start != null)
{
var segment = new RoomWall(start, end);
segment -= wall.outwards.minimized;
segments.Add(segment);
start = null;
end = null;
}
scanTexture.SetPixel(coordX, coordY, Color.red);
}
else
{
if (start == null)
{
start = new GridVector(coordX, coordY);
}
end = new GridVector(coordX, coordY);
scanTexture.SetPixel(coordX, coordY, Color.green);
}
}
}
if (end != null && start != null)
{
var segment = new RoomWall(start, end);
segment -= wall.outwards.minimized;
segments.Add(segment);
}
return segments;
}
To display all the manipulations with the rooms, I use a texture in which pixels I enter the position of the walls. If you don’t erase the old walls, you get filled areas, as on the gif at the beginning of the article. I draw the walls using the Bresenham lines that I wrote about here . In case of problems with gluing walls, everything immediately becomes visible. Instead of texture, you can use a two-dimensional array or immediately operate with 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 only white ones and one pixel less on each side. It turns out a lot of different houses. They can also be made three-dimensional and covered with a roof. Voice of Kanevsky: However, this is a completely different story.
On the links below you can see the binaries and source codes of the finished project.
Unity Web Player | Windows | Linux | Mac | Sources on GitHub
Shift - Creates random external walls with random rooms
Ctrl - Download a test texture with random rooms
Enter - Remove all rooms and load a test texture
Space - Stop the growth of rooms
Unit on the alphabetic keyboard - Turn on visualization of the search for free cells
Left mouse button on a free area - Add
Esc Room - Exit
For Linux users: Make the ProceduralExperiments.x86 file executable with “chmod + x ProceduralExperiments.x86” and run it.