Procedural Building Generation
Oscar Oosterling 500775970
Table of contents
Step 3: Placing blocks & creating data
Introduction
The idea of this project was to recreate an existing game/art piece named Townscaper. This game uses procedural block placements on an irregular grid to create a really cool looking town with lots of variation. I knew that this was a bit too much for my own project so I decided to recreate an earlier version of townscaper named Brick Block. This version is based on a square grid where each ‘block’ has 6 sides(Stålberg, O. S., 2015).
My goal for this project was to create a similar working project that i can show to other people in the browser without the fancy and good looking assets. The main focus of this project was the code and having the code be cleanly written and organized without using existing tutorials or other peoples code.
I had bigger things in mind at the start of the project but I noticed that what i wanted to do was harder than i thought. I wanted to make the code be useable outside of my own project as a library or a unity asset but before I can do that I need to have it working first.
Try out my project in the browser:
Look at my code here:
Step 1: Code Structure
Before I started coding I wanted to think about the code structure and how I will build up the project. From the example I am trying to recreate I know that I need a grid with big blocks. Each big block will contain eight smaller blocks inside it. Each big block needs to know what neighbors it has and I need to be able to add and remove big blocks from the grid which should update the neighboring big blocks of the added or removed big block.
For this reason I have chosen to make three classes and work from there. Those three classes are: the grid, the cell and the cellblock. The grid class will contain code about the whole grid and its update functions such as adding a cell. The cell class will contain code about the cell itself and all the functions for the cell and the cellblocks together. The cellblock class will only contain the data for the small block without any other functions.
Because I also wanted to create blocks with mouse clicks I also created a separate class for that. This class will contain everything about the clicking on blocks or clicking to rotate the camera. And the final class used in this project is the class for the movement of the camera. This class will make the camera rotate when certain functions from this class are called from the mouse clicks class.
Step 2: Coordinate system
To place the cell on the right spot and be able to know what cells neighbor other cells I needed a system to keep track of this. I started with having each cell having its world location be its coordinate location. This caused some problems with floating numbers when looking up the exact coordinate of a cell so for this reason I changed the way the coordinates are by having each cell be exactly one unit away from other cells within the coordinate system.
To store the coordinates of all cells and the cell data itself I chose to use a Dictionary. The benefits of a dictionary is that I can lookup the keys which in this case is an integer vector3 really quickly and I can check if a certain coordinate already exist in the dictionary really quick.
Dictionary<Vector3Int, Cell> cells = new Dictionary<Vector3Int, Cell>();
Step 3: Placing blocks & creating data
Now that I have a coordinate system to which I can add coordinates and cells I can start with the placement of cells. I want to place cells with a left mouse click and remove them with a right mouse click. To know where the mouse is pointing at in the 3D environment I use ray casts. Using unity’s build-in ray cast functions I can shoot a ray from the mouse position into 3D environment possibly hitting an object (Unity. z.d.).
bool hit = Physics.Raycast(Camera.main.ScreenPointToRay(Input.mousePosition), out hitInfo);
When this ray hits something I can receive the data about the object the ray has hit. The data I need to be able to know where to place cells is the position of the collided object and the direction the surface the ray hit is pointing. When I want to add a cell to the collided cell I need to know in what direction I need to add that block. By having the coordinate system work with each cell being one unit away I can use the direction the surface of the collided object is pointing, the normal, to add this to the collided objects position to know where to create the new block. When i want to remove a block i do not need the normal info.
if (hit) { Vector3 position = new Vector3( Mathf.Round(hitInfo.collider.transform.position.x), Mathf.Round(hitInfo.collider.transform.position.y), Mathf.Round(hitInfo.collider.transform.position.z)); if (createOrDestroy) { position += hitInfo.normal * grid.scale; grid.CreateCell(Vector3Int.FloorToInt(position) / grid.scale); } else { grid.DestroyCell(Vector3Int.FloorToInt(position) / grid.scale); } }
Now that I have the position of where the new block will be created, I can start adding and creating this data. I need to create a new Cell object, add to the cells dictionary and create actual object in the 3D environment. But before that I need to check if the position of the new cell is not outside of the range I want it to be and if it does not already exist in the dictionary. This is where the use of a dictionary helps a lot because I can use the ‘ContainsKey’ function to check if cell already exists or is outside of the bounds.
if (cells.ContainsKey(position) || position.x > gridSize || position.z > gridSize || position.x < -1 || position.z < -1) { return; }
Now that I know that I have a valid position I can create the Cell object. This object needs a position, scale, prefabs and a Boolean to set it as a ground cell or not.
Cell cellObject = new Cell(position, scale, false); cellObject.prefabs = prefabs;
This cell object will also need eight cellblocks. Because each cell will always have eight cellblocks I chose to have these stored in an array. Each cellblock has position within the cell and an orientation. I can use the local position of the cellblocks because they are all children of the cell. Each cellblock occupies a different corner in cell. With the cell as parent the middle point of this cell is position 0,0,0. Each cellblock needs to be offset in a different corner to this position. Each cellblock also needs to be rotated to face the outside of the cell.
public void SetCellBlockLocations() { float offset = 0.25f; cellBlocks[0] = new Cellblock(new Vector3(-offset, -offset, -offset), new Vector3(0, 180, 180)); cellBlocks[1] = new Cellblock(new Vector3(offset, -offset, -offset), new Vector3(0, 90, 180)); cellBlocks[2] = new Cellblock(new Vector3(-offset, -offset, offset), new Vector3(0, -90, 180)); cellBlocks[3] = new Cellblock(new Vector3(offset, -offset, offset), new Vector3(0, 0, 180)); cellBlocks[4] = new Cellblock(new Vector3(-offset, offset, -offset), new Vector3(0, -90, 0)); cellBlocks[5] = new Cellblock(new Vector3(offset, offset, -offset), new Vector3(0, 180, 0)); cellBlocks[6] = new Cellblock(new Vector3(-offset, offset, offset), new Vector3(0, 0, 0)); cellBlocks[7] = new Cellblock(new Vector3(offset, offset, offset), new Vector3(0, 90, 0)); }
With having made the cell and all the cellblocks I can then add this cell to the dictionary as value with the key being the coordinate. I then update all existing cells and create a cube for each cell in the dictionary.
The cell cube contains a collider cube and eight prefabs of corner pieces for each cellblock. The collider cube is used for the ray casts to hit the right position and also return the right direction. Each cellblock will use one of the corner pieces determent by the cells neighbors.
The collider cubes position and scale is determined by coordinate position and the given scale. The eight prefab positions of the cellblocks are all already set and only need to be assigned.
private void CreateCube(Vector3Int position) { DestroyCube(position); GameObject cube = Instantiate(colliderBlock); cube.transform.position = position * scale; cube.name = position.ToString(); cube.transform.localScale *= scale; cube.transform.parent = this.transform; for (int i = 0; i < cells[position].cellBlocks.Length; i++) { GameObject cubeBlock = Instantiate(cells[position].cellBlocks[i].prefab); cubeBlock.transform.parent = cube.transform; cubeBlock.transform.localScale *= scale * .5f; cubeBlock.transform.localPosition = cells[position].cellBlocks[i].position; cubeBlock.transform.eulerAngles = cells[position].cellBlocks[i].orientation; cubeBlock.name = "CubeBlock: " + i + " xyz: " + cells[position].cellBlocks[i].position; } }
Destroying already created cubes is much simpler, this function checks if there exists a cell on the given coordinate and checks if this cell is not a ground cell and then removes it from the dictionary. Then it destroys the parent collider cube with all its cellblock children. It then updates all other blocks.
public void DestroyCell(Vector3Int position) { if (!cells.ContainsKey(position) || groundCells.Contains(position)) { return; } cells.Remove(position); DestroyCube(position); UpdateAllBlocks(); }
Step 4: Finding Neighbors
Now that it is possible to add and remove cells I want to know what cells neighbor each other. I know that each cell can have at most 6 neighbors. I can use an array to store the neighbors coordinates for this reason. I can check if a cell has a neighbor in a particular direction by using the handy ‘ContainsKey’ function of dictionaries. And because the coordinate system has each cell be exactly one unit away from each other cell I know exactly where the possible neighbor would be in the coordinate system. To add all the neighbors to each cell I loop over each cell in the cells dictionary and check for all six sides if it there exists another cell. If this is not the case then I set that neighbor position in the array to ‘null’.
public void AddPossibleNeigbours() { foreach (KeyValuePair<Vector3Int, Cell> entry in cells) { int x = (int)entry.Key.x; int y = (int)entry.Key.y; int z = (int)entry.Key.z; Cell[] neighbours = new Cell[6]; neighbours[0] = cells.ContainsKey(new Vector3Int(x + 1, y, z)) ? cells[new Vector3Int(x + 1, y, z)] : null; neighbours[1] = cells.ContainsKey(new Vector3Int(x - 1, y, z)) ? cells[new Vector3Int(x - 1, y, z)] : null; neighbours[2] = cells.ContainsKey(new Vector3Int(x, y + 1, z)) ? cells[new Vector3Int(x, y + 1, z)] : null; neighbours[3] = cells.ContainsKey(new Vector3Int(x, y - 1, z)) ? cells[new Vector3Int(x, y - 1, z)] : null; neighbours[4] = cells.ContainsKey(new Vector3Int(x, y, z + 1)) ? cells[new Vector3Int(x, y, z + 1)] : null; neighbours[5] = cells.ContainsKey(new Vector3Int(x, y, z - 1)) ? cells[new Vector3Int(x, y, z - 1)] : null; entry.Value.neighbours = neighbours; entry.Value.CalculateConfiguration(); } }
Step 5: Configurations
With the all the neighbors known I can now calculate which configuration all the cellblocks of the cell need to be in to connect properly to the neighboring cells. With six neighbours that can exist or not there are two to the power of six possible combinations or 64 combinations. To get an usable number out of the configurations I can use binary notation. Where each neighboring side is a different bit out of a 6 bit binary number. A Cell with neighbors in array position zero, two and five would be binary 010101 and converted to decimal 0,1,0,4,0,16,0 summed up to 21. The number 21 can then be used to know what exact configuration is being used.
public void CalculateConfiguration() { neighbourConfigurationNumber = 0; for (int i = 0; i < neighbours.Length; i++) { if (neighbours[i] != null) { neighbourConfigurationNumber += (int)Mathf.Pow(2, i); } } if (isGround) { neighbourConfigurationNumber = 64; } }
Step 6: Creating Shapes
This is the point where I did not know how to proceed. I had my coordinate system, my way of filling a dictionary with the relevant data and I knew in what configuration the neighbors of each cell stood. There is an algorithm named the wave function collapse algorithm that can be used to algorithmically solve how each configuration of neighbors should look, but I did not understand this algorithm well enough to implement it in this project(Heaton, R. H.,2018).
I did not really know how many different shapes I needed for each configuration to work. I first thought that with three basic shapes that I could create each configuration by rotating these three pieces. I was wrong. I had created a spreadsheet to workout the best way of assigning each configuration the different prefab pieces I thought I needed. In this spreadsheet I noticed that a lot of configurations were mirrored versions of other configurations. I thought that in some way I could calculate this mirroring of the configurations and then only have to manually assign 32 different configurations. I did not get this to work. The final list of configurations were ordered by how many neighbors each configuration had and each configuration was paired with a mirrored version of that configuration.
With the deadline getting closer, I chose to stop using different rotations for each configuration and create a lookup table of different numbers. This lookup table is something that I had seen being used in a video about marching cubes. The idea of the lookup table is that for each configuration a different set of numbers is needed with each number corresponding to a cellblock in the cell. I chose to create a dictionary with the configuration number as key and an array of numbers as the configuration. Each number was a different prefab from an list of prefabs.
I then started to manually fill in each configuration in the dictionary with the correct prefab numbers. This went pretty fast because I had ordered the configurations by neighbor amount and mirrored copies. While putting in the numbers I noticed that without rotating the prefabs for each configuration that I needed more prefabs. Every time that got to a configuration where the current prefabs did not work I created a new prefab to make that configuration work. In the end I needed eight different prefabs to complete all the configurations. These are the first 10 configurations:
public static Dictionary<int, int[]> configurationDictionary = new Dictionary<int, int[]>() { {0,new int[]{0,0,0,0,0,0,0,0} }, {1,new int[]{0,3,0,2,0,2,0,3} }, {2,new int[]{2,0,3,0,3,0,2,0} }, {3,new int[]{2,3,3,2,3,2,2,3} }, {4,new int[]{0,0,0,0,1,1,1,1} }, {5,new int[]{0,3,0,2,1,5,1,4} }, {6,new int[]{2,0,3,0,4,1,5,1} }, {7,new int[]{2,3,3,2,4,5,5,4} }, {8,new int[]{1,1,1,1,0,0,0,0} }, {9,new int[]{1,4,1,5,0,2,0,3} }, {10,new int[]{5,1,4,1,3,0,2,0} },
Step 7: Camera movement
I wanted the camera to be able to rotate around the building by clicking the left or right side of the screen in a somewhat smooth way. To align the camera in the right direction and on the right position I first need to calculate the middle point of ground blocks. Using this middle point I can calculate how much the camera should be offset from this point.
I chose to have eight different camera points, on each corner and in the middle of each side. The X and Z values of the positions of the camera are calculated by taking the middle point and adding or subtracting an offset from this. The Y value for all camera positions is the same. The offset is calculated by multiplying the grid size of the grid by two and the result from this will be multiplied by the grid scale.
private void SetCameraPosition() { float offset = (grid.gridSize * 2) * grid.scale; float y = middlePoint.y + offset; positions = new Dictionary<int, Vector3>() { {0,new Vector3(middlePoint.x, y, middlePoint.z+offset)}, {1,new Vector3( -(offset*.5f), y, offset-grid.scale)}, {2,new Vector3( middlePoint.x-offset, y, middlePoint.z)}, {3,new Vector3( -(offset*.5f), y, -(offset*.5f))}, {4,new Vector3( middlePoint.x, y, middlePoint.z-offset)}, {5,new Vector3( offset-grid.scale, y, -(offset*.5f))}, {6,new Vector3( middlePoint.x+offset, y, middlePoint.z)}, {7,new Vector3( offset-grid.scale, y, offset-grid.scale)} }; }
The rotation of each camera position is pretty simple with only the Y value changing by 45 for each new camera position.
private void SetCameraRotation() { for (int i = 0; i < AmountOfAngles; i++) { int y = startYAngle - (rotationAmount * i); rotations.Add(i, Quaternion.Euler(xAngle,y,zAngle)); } }
For the switching between the camera positions I used unity’s lerp function. But I did not really know how to use this lerp function correctly. The first time I tried to use lerp function nothing happened. I then tried to change the time it took to get from the first position to the second position from a small number to Time.deltaTime this made the lerp function work but it would never get to the second position exactly and the speed during the transition changed during the transition.
I found a site that explained the right way to use the lerp function and I used this code to fix my lerp issues. The site describes that instead of a random number being used as time input that it is better to see this time input as a percentage of how far the lerp is done. By calculating the percentage and using this percentage as input I can get a smooth rotation and movement of the camera(BlueRaja, 2014)
private void Lerp() { float timeSinceStarted = Time.time - startLerpTime; float percentageComplete = timeSinceStarted / lerpTime; transform.position = Vector3.Lerp(currentPosition, nextPosition, percentageComplete); transform.rotation = Quaternion.Lerp(currentRotation, nextRotation, percentageComplete); if (percentageComplete >= 1.0f) { isLerping = false; } }
Conclusion
I have severely underestimated the difficulty of this project. I did not think that I would have so many problems with the configurations and all the mesh combinations. Before this project I had the idea of making this into a tool or asset for other developers but during the making of this project I quickly noticed that I would have no time for that. I also regret not being able to understand the wavefunction collapse algorithm well enough that I could implement it within my time limit. At this moment I still do not have an idea on how I would implement it. I also do not really like it that my project is not really scalable. If I wanted to increase the different variations of possible configurations I would need to do this manually.
I am proud of the way that I solved the problems to create what I have at this moment. Thinking about ways to solve problems during this project without using other peoples code was refreshing. It made me enjoy writing the code I wrote. It also showed me that I can use the knowledge I have build up during the previous semesters to solve my problems without using other peoples code or exact tutorials.
The final product is a good addition to my portfolio and I am happy with how product functions in the webGL build.
Future work
If I want to expand this procedural building generation without having to manually update the configuration lookup table I would need to use the wavefunction collapse algorithm. This would take away a lot of manual work that is currently required to edit or expand the current lookup table.
Another thing that I did not do is to make this project be usable for other developers as a way of creating buildings. An expansion to my current work would be to make it work as a functional library or unity asset.
Something that can be improved a lot are the meshes. Currently they are very simple shapes that do not really represent actual buildings. I am not an artist but I also did not put a lot of work into making the different meshes look better than they are right now.
Sources
BlueRaja. (2014, 8 februari). Using Vector3.Lerp() correctly in Unity. One Man’s Trash Is Another Man’s Blog. http://www.blueraja.com/blog/404/how-to-use-unity-3ds-linear-interpolation-vector3-lerp-correctly
Stålberg, O. S. (2015, 30 oktober). Voxel House. Vertex3, 3, 170–175.
Heaton, R. H. (2018, 17 december). The Wavefunction Collapse Algorithm explained very clearly. Robert Heaton. https://robertheaton.com/2018/12/17/wavefunction-collapse-algorithm/
Unity. (z.d.). Unity – Scripting API: Physics.Raycast. Docs.Unity3d.Com. Geraadpleegd op 30 maart 2021, van https://docs.unity3d.com/ScriptReference/Physics.Raycast.html
