The Problem
I wanted to create a system for open world map generation that struck a balance between a hand crafted and a fully procedural approach. Fully procedural maps tend to be really effective in implementation time and replayability, but struggle to match the design quality and control of hand-made environments. These procedural algorithms also tend to utilize large assemblies of micro-scale props and set pieces, but what about a system that uses macro-scale assets...
The Plan
Enter the Perfect Tetris algorithm! At its core, the map exists on a large grid represented by a 2D matrix. These grid spaces are populated with tiles or blocks in order to create the map terrain. Each block is irregular in shape and placed in a random position and orientation so that the end result is patternless.
Since the map is represented by a 2D matrix, the blocks themselves are represented by smaller sub-matrices. As the algorithm iterates over the map, it flips the integers within the map matrix from 0 to 1 to represent an occupied cell. When all cells are occupied, the algorithm stops and the map generation is complete! You could develop this idea further by using different integers to represent different types of terrain, which could then be used to further control the map generation (or the placement of micro-assets in a second procedural pass). Below you can see the initial design for the algorithm and the helper function for rotating the block matrixes.
The Implementation
Taking the concept over to Unity, we can start generating some examples. These maps were generated using simple colored test blocks and a 6x6 map grid.
This can be scaled up to any arbitrary map size. The random position and rotation of the blocks prevents discernable patterns from emerging, creating a noise-like result with larger map sizes. Here we have an example using the same test pieces and a map size of 20x20.
The next step is to quickly model some terrain tiles and apply them to the current implementation. The idea is that artists can create a complete map tile set by creating a sufficient number of terrain blocks for each block shape. Really large maps might require a greater number of tiles -- or at least a number of "landmark" tiles and generic terrain tiles so that the assets are not noticeably repeating.
Below we can see some examples of the 20x20 map above from a player perspective. Even with grayboxed terrain and a limited tileset, you can see the algorithm is already creating a navigable open world environment that can be reconfigured and regenerated instantly.
PerfectBlock.cs (Script, C#)
This is the complete code for the Unity script in C#. The modeling and scripting together represent about four days of labor.
using System.Collections.Generic;
using UnityEngine;
public class PerfectTetris : MonoBehaviour
{
//Block and Map Dimensions
public int BlockSize;
public int MapSize;
//Block Bank (List of lists)
List<List<GameObject>> prefabList = new List<List<GameObject>>();
//Matrix Bank
List<int[,]> matrixList = new List<int[,]>();
//Terrain Block Lists
public List<GameObject> SingleBlockList = new List<GameObject>();
public List<GameObject> DoubleBlockList = new List<GameObject>();
public List<GameObject> TripleBlockList = new List<GameObject>();
public List<GameObject> SquareBlockList = new List<GameObject>();
public List<GameObject> LBlockList = new List<GameObject>();
public List<GameObject> TBlockList = new List<GameObject>();
public List<GameObject> CornerBlockList = new List<GameObject>();
//Print Matrix
public static void Print2DArray<T>(T[,] matrix)
{
string matrixOutput = "\n";
for (int i = 0; i < matrix.GetLength(0); i++)
{
string col = "";
for (int j = 0; j < matrix.GetLength(1); j++)
{
col += matrix[i,j] + " ";
}
matrixOutput += col + "\n";
}
Debug.Log(matrixOutput);
}
//Rotate Matrix 90 Degrees
public static int[,] Rotate90 (int[,] matrix)
{
int length = matrix.GetLength(0);
int height = matrix.GetLength(1);
int[,] outputMatrix = new int[height, length];
for (var i = 0; i < height; i++)
{
for (var j = length - 1; j >= 0; j--)
{
outputMatrix[i, length - 1 - j] = matrix[j, i];
}
}
return outputMatrix;
}
// Start is called before the first frame update
void Start()
{
//Add Terrain Block Lists to Block Bank
prefabList.Add(SingleBlockList);
prefabList.Add(DoubleBlockList);
prefabList.Add(TripleBlockList);
prefabList.Add(SquareBlockList);
prefabList.Add(LBlockList);
prefabList.Add(TBlockList);
prefabList.Add(CornerBlockList);
//Add Block Matrices to Matrix Bank (Order Matters)
matrixList.Add(new int[1,1] {{1}}); // [0]: SingleBlock
matrixList.Add(new int[2,1] {{1},{1}}); // [1]: DoubleBlock
matrixList.Add(new int[3,1] {{1}, {1}, {1}}); // [2]: TripleBlock
matrixList.Add(new int[2,2] {{1, 1}, {1, 1}}); // [3]: SquareBlock
matrixList.Add(new int[3,2] {{1, 1}, {1, 0}, {1, 0}}); // [4]: LBlock
matrixList.Add(new int[3,2] {{1, 0}, {1, 1}, {1, 0}}); // [5]: TBlock
matrixList.Add(new int[2,2] {{1, 1}, {1, 0}}); // [6]: CornerBlock
//Create Map Matrix
int[,] MapMatrix = new int[MapSize+4, MapSize+4];
for (var i = 0; i < MapSize+4; i++)
{
for (var j = 0; j < MapSize+4; j++)
{
MapMatrix[i,j] = 1;
}
}
for (var i = 2; i < MapSize+2; i++)
{
for (var j = 2; j < MapSize+2; j++)
{
MapMatrix[i,j] = 0;
}
}
//Iterate across map grid
for (var i = 2; i < MapSize+2; i++)
{
for (var j = 2; j < MapSize+2; j++)
{
//Generate random index
int prefabIndex = UnityEngine.Random.Range(1,prefabList.Count); //Exclude single blocks
//Variable Declaration
int x = i;
int y = j;
int[,] BlockMatrix = matrixList[prefabIndex];
int rotationMultiplier = UnityEngine.Random.Range(0,4); //Set rotation of the selected block
for (int a = 0; a < rotationMultiplier; a++) BlockMatrix = Rotate90(BlockMatrix); //Apply rotation
int length = BlockMatrix.GetLength(0);
int height = BlockMatrix.GetLength(1);
bool blockCollision = false;
//Check for map/block collision
for (int a = 0; a < length; a++)
{
for (int b = 0; b < height; b++)
{
if (MapMatrix[i+a,j+b] > 0 && BlockMatrix[a, b] > 0)
{
blockCollision = true;
}
}
}
//Place block on map and map matrix
if (blockCollision == false)
{
//Generate random subindex
int blockIndex = UnityEngine.Random.Range(0,prefabList[prefabIndex].Count);
//Map placement (adjusted for block pivot point)
if (rotationMultiplier == 0)
{
if (length == 1)
Instantiate (prefabList[prefabIndex][blockIndex], new Vector3((i*BlockSize)-BlockSize, 0, j*BlockSize), Quaternion.Euler(0, 90*rotationMultiplier, 0));
else if (length == 3)
Instantiate (prefabList[prefabIndex][blockIndex], new Vector3((i*BlockSize)+BlockSize, 0, j*BlockSize), Quaternion.Euler(0, 90*rotationMultiplier, 0));
else
Instantiate (prefabList[prefabIndex][blockIndex], new Vector3(i*BlockSize, 0, j*BlockSize), Quaternion.Euler(0, 90*rotationMultiplier, 0));
}
else if (rotationMultiplier == 1)
{
if (length == 3)
Instantiate (prefabList[prefabIndex][blockIndex], new Vector3((i*BlockSize)+BlockSize, 0, j*BlockSize), Quaternion.Euler(0, 90*rotationMultiplier, 0));
else
Instantiate (prefabList[prefabIndex][blockIndex], new Vector3((i*BlockSize)-BlockSize, 0, j*BlockSize), Quaternion.Euler(0, 90*rotationMultiplier, 0));
}
else if (rotationMultiplier == 2)
{
if (height == 1) j--;
Instantiate (prefabList[prefabIndex][blockIndex], new Vector3((i*BlockSize)-BlockSize, 0, (j*BlockSize)+BlockSize), Quaternion.Euler(0, 90*rotationMultiplier, 0));
if (height == 1) j++;
}
else if (rotationMultiplier == 3)
{
if (height == 1) j -= 2;
else if (height == 2) j--;
if (length == 1)
Instantiate (prefabList[prefabIndex][blockIndex], new Vector3((i*BlockSize)-BlockSize, 0, (j*BlockSize)+(2*BlockSize)), Quaternion.Euler(0, 90*rotationMultiplier, 0));
else if (length == 3)
Instantiate (prefabList[prefabIndex][blockIndex], new Vector3((i*BlockSize)+BlockSize, 0, (j*BlockSize)+(2*BlockSize)), Quaternion.Euler(0, 90*rotationMultiplier, 0));
else
Instantiate (prefabList[prefabIndex][blockIndex], new Vector3(i*BlockSize, 0, (j*BlockSize)+(2*BlockSize)), Quaternion.Euler(0, 90*rotationMultiplier, 0));
if (height == 1) j += 2;
else if (height == 2) j++;
}
//Matrix placement
for (int a = 0; a < length; a++)
{
for (int b = 0; b < height; b++)
{
if (BlockMatrix[a, b] == 1) MapMatrix[i+a,j+b] += 1;
}
}
//Debug Array Print
Print2DArray<int>(BlockMatrix);
}
}
}
//Fill holes with single blocks
for (var i = 2; i < MapSize+2; i++)
{
for (var j = 2; j < MapSize+2; j++)
{
if (MapMatrix[i,j] == 0)
{
//Generate random subindex
int blockIndex = UnityEngine.Random.Range(0,prefabList[0].Count);
//Place single block
Instantiate (prefabList[0][blockIndex], new Vector3((i*BlockSize)-BlockSize, 0, j*BlockSize), Quaternion.identity);
MapMatrix[i,j] += 1;
}
}
}
//Debug Array Print
Print2DArray<int>(MapMatrix);
}
}
What's next?
One of the most compelling parts of the project to me is the potential to expand and adapt the algorithm to specific use cases. If I were to develop the system further, one of the first things I would add would be different integers to represent different types of terrain. You could have mountains represented by 2s, lakes represented by 3s, support for different biomes, and more. This information could be used to influence the algorithm and give designers/artists specific control over the map generation at the inspector level. For example, you could implement rules where buildings do not spawn adjacent to one another, lakes do not spawn next to mountains, etc.
Another interesting addition would be multiple layers in the map matrix (2D -> 3D) to represent different layers of information. You could have the terrain exist on the first layer, and things like loot and mob density on another layer. These layers could be generated randomly or use data from the terrain layer as a set of input values in a second pass algorithm.
I think it might also be interesting to experiment using the basic system to create new types of terrain -- instead of open world maps, one could potentially generate dungeons or cave systems. I think the idea of fitting irregular tiles together is a really powerful way to organize macro-scale level assets and there are many exciting potential use cases to explore.
I suppose we'll see in version 2.0... ?
(949) 300-9229