Procedural generation of floor plans

What makes a major game developer when he needs to do a lot of rooms for games? Hires a bunch of artists. What makes a lone game developer? Writes procedural generator that performs all the work for him.

In this article I will discuss how I implemented on Unity3d a simple method for the generation, which leads to good results and can be easily modified.

  •      The whole space is divided into cells like grid in architectural plans.
  •      External walls already exist and are input to the program.
  •      There is a list of rooms that need to be placed on the layout.
  •      Rooms have a parameter "desired size" and factors of attraction to each other
  •      Point of production rooms are scattered randomly on the plan, possibly with the help of some exemplary card.
  •      Then each point starts rectangular grow until it reaches a certain size for her.
  •      When all the boxes up, the room begins to grow in the shape of the letter L as long as possible.
  •      The remaining space is tacked to the neighbors.

Rooms grow on one wall at a time, to avoid creeping wall of the room at each other. The wall is selected from the largest walls of the room, if there is the same - takes random. The highest wall is taken in order to increase the maximum size of rooms was, and they were "plump".

Now, about my implementation. I did not bother with a realistic plan, coefficients and size of the room - it's decorations, I worked on the basic algorithm, everything else can be quickly added. The article also refers to the special inspections to prevent the emergence of U-shaped rooms, I did not do them, do not see anything wrong with these rooms. I was setting as corridors, doors and windows, it is a separate issue, and their arrangement may depend on the generation of the rest of the building.

The most difficult thing was to choose the principle of growth rooms and storage of data about them and the building. The same result can be obtained by using cellular automata or even just run through the array. I tried several options, I would always have an idea of the dimensions of the room and the exact position of its walls, so I created a class that stores only the corners of the room, and the walls are created automatically by linking two adjacent corners.

Binding of the walls is essentially a shell polygon search of a set of points. Trivial task with a lot of tricks, if you're interested, I advise you to look    here. I decided to limit right angles between adjacent walls and fashioned a simple algorithm:

  •      Find the minimum and maximum X and Y coordinates in the set points.
  •      From point (minX, minY) go upstairs to the Y and alternately looking for a point with coordinates so if it's not there, you're looking right, bottom and left. When we find it we take out of the old list is transferred to the new list.
  •      The coordinates of this point in the old list looking for the next point higher on the Y, if found - transfer to the new list are removed from the old one, remember that they found a wall that is parallel to Y, then the next wall should be parallel to X.
  •      We are looking for a point on the ICSU right and left, transferred to a new list, remember the orientation just found the wall, looking down the analogy.
  •      The last point in the old list is simply transferred to the new one.

Sort corner of the room

public GridVector SortCorners()
    {
        // Looking for room ambit
        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;
        }

        // Sort corners of the room
        var oldC = new List<GridVector>(corners);
        var newC = new List<GridVector>();
        bool parallelX = false;
        while (oldC.Count > 1)
        {
            // Looking for a first angle
            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;
                }
            }
            // Looking for the other corners
            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;
            }
        }
        // Add the last remaining corner
        newC.Add(oldC[0]);
        corners = newC;
        return null;
    }

    bool ScanLeft(ref List<GridVector> oldC, ref List<GridVector> 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<GridVector> oldC, ref List<GridVector> 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<GridVector> oldC, ref List<GridVector> 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<GridVector> oldC, ref List<GridVector> 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 one can easily deduce the wall. Thanks sorting becomes more easy to learn one important thing - the direction of the outside of the walls of the room. To turn off the end of the wall to the outside, you need to change the X and Y locations and invert the first coordinate to obtain the following: (-y, x).

Rooms are stored in the form of points, the points are sorted, the walls are constructed automatically, outwardly we know - All this is enough to check the free space on the floor plan and room to grow. Sometimes the truth is necessary to add new wall when the old ones into something rested and can not grow.

To check the availability of the cells and the search for potential new walls, I use a function that collects a list of available sites for growth supplied to the input of the wall. Then I sort of found segments from across the room categories: solid walls,  pieces at the edge of the wall, central segments.

Choose the largest wall of the available and are sent to the growth room. And the function checks whether there is such a wall, or need to create a new one. When the wall is, the coordinates of its ends are shifted outwardly, which leads to the automatic lengthening of adjacent walls.

Search for wall segments

List<RoomWall> 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<RoomWall>();
        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 rooms I use texture, in pixels which I bring the provisions of the walls. If you do not erase the old wall, you get filled areas, as gif-ke in the beginning of this article. Paint the walls with lines Brezenhema. In case of problems with pasting the walls, all at once becomes clear. Texture can be used instead of a two-dimensional array or right to operate a three-dimensional model.

Exterior walls can be generated very simply. Draw some black rectangles of arbitrary size and draw them over the same and only one white pixel is less on each side. It turns out a lot of different houses.

 

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


Unity Web Player | Windows | Linux | Mac | GitHub
 

Shift - Creates a random external walls with random rooms
Ctrl - Download a test with random texture bathrooms
Enter - Remove all the rooms and load test texture
Spacebar - Stop the growth of rooms
1  alphabetic keyboard - including visualization Search free cells
The left mouse button on a free area - Add the room

For users of Linux: Make the file executable with ProceduralExperiments.x86 «chmod + x ProceduralExperiments.x86» and run.

All data posted on the site represents accessible information that can be browsed and downloaded for free from the web.

 

http://habrahabr.ru/post/184818/

 

User replies

No replies yet