Labyrinth generation by Eller algorithm in Unity
Hello!
Today I would like to talk about how to generate mazes using the Eller algorithm, and how to make a beautiful 3D visualization in Unity, so that you can use it in your games later. Also tell a little about how you can customize post processing inside this solution. And traditionally link GitHub with the generator itself.
Eller's algorithm is a rather popular algorithm for generating “ideal” (there is only one way between two points) mazes, since it is one of the fastest and generates “interesting” mazes. “Interesting” they are obtained due to the fact that this algorithm is not based on the search for a spanning tree in a graph, as a result of which it generates fractal structures less frequently. Including one of the advantages of the algorithm is that it allows you to generate mazes of infinite size in linear time.
')
The algorithm is based on the fact that we combine the cells of the maze into different sets, and in the last step of the algorithm we combine them into one common set. Cells are in one set - if from one cell you can walk to another. Initially, all the walls of the maze are raised, so that all cells are in different sets.
I saw many different descriptions of the algorithm itself (even in Habré), so I won’t do it again, but I’ll write a brief description of my implementation.
The algorithm itself consists of 3 basic steps.
In the loop:
1. We process the string, randomly combining the cells in the string belonging to different sets.
2. Pass by the same line and randomly combine the cells from the line above with our line (with some restrictions)
The final step:
We process the last row by combining cells from different sets.
In general, this is the algorithm.
Labyrinth need to store something. In my decision there are 2 structures for storing labyrinths.
W4Maze - which in essence is an array of cells of 16 types according to the number of raised walls. The W4Cell cell itself contains just 4 bool fields that tell you which walls are raised. This structure is convenient for maze generation by the Eller algorithm and convenient for serialization.
But on the other hand, it is completely inconvenient for generating walls. The idea is that the walls of the labyrinth should have a thickness, in order to implement a similar algorithm, it is graph structures that are convenient. For this, the MazeGraph structure was introduced and the conversion from W4Maze to it was implemented. In addition, for convenience, it was created 2 lists - paths and walls. As a result, having written a simple visualization with the help of Gizmos, we get such a maze. Yellow is the wall, and green is the way.
In general, this is not bad, but there are too many unnecessary nodes in the walls and paths, which will be inconvenient in the future to generate three-dimensional visualization, so that we simplify them. This will allow to generate less meshes and avoid lighting artifacts at the junctions.
The rest is a matter of technology. I have written my own tool for generating planes of the MeshTools class with the simplest triangulation (since we know the order of adding points). In general, unit Quads could be used, but in any case it would be necessary to recalculate the uv coordinates in order to The tiling of the material on all the walls was the same and in this case one material could be used. More details can be viewed at the link to GitHub .
So, the maze is built, correctly exposed uv-shki. Now I want to show the simplest example of the possibility of post processing using the example of automatic light placement. For this, I created the LightPlacer class and here we will again need the W4Maze maze. Algorithm post processing is quite simple. We simply set the illumination levels, translate the cell type to int, and decide whether to set the light source or not.
And here is our final labyrinth!
With the help of such post processing, you can arrange decals, enemies, traps, and anything else.
Thanks for attention! Who would like to get acquainted with the decision details link to GitHub .
If someone would be more interested in the topic of mesh generation, which is an important part of the solution, I can write about this in a separate article.
Today I would like to talk about how to generate mazes using the Eller algorithm, and how to make a beautiful 3D visualization in Unity, so that you can use it in your games later. Also tell a little about how you can customize post processing inside this solution. And traditionally link GitHub with the generator itself.
Eller's algorithm is a rather popular algorithm for generating “ideal” (there is only one way between two points) mazes, since it is one of the fastest and generates “interesting” mazes. “Interesting” they are obtained due to the fact that this algorithm is not based on the search for a spanning tree in a graph, as a result of which it generates fractal structures less frequently. Including one of the advantages of the algorithm is that it allows you to generate mazes of infinite size in linear time.
')
The algorithm is based on the fact that we combine the cells of the maze into different sets, and in the last step of the algorithm we combine them into one common set. Cells are in one set - if from one cell you can walk to another. Initially, all the walls of the maze are raised, so that all cells are in different sets.
I saw many different descriptions of the algorithm itself (even in Habré), so I won’t do it again, but I’ll write a brief description of my implementation.
The algorithm itself consists of 3 basic steps.
In the loop:
1. We process the string, randomly combining the cells in the string belonging to different sets.
Code
private void CreateRow(W4Maze maze, int rowNum) { for(int i = 0; i < maze.ColumnCount - 1; i++) { var cell = maze.GetCell(i, rowNum); var nextCell = maze.GetCell(i + 1, rowNum); if (cell.Set != nextCell.Set) { if (UnityEngine.Random.Range(0, 2) > 0) { RemoveHorizonWallBetweenCells( maze, cell, nextCell, rowNum); } } } } 2. Pass by the same line and randomly combine the cells from the line above with our line (with some restrictions)
Code
private void CreateVerticalConnections( W4Maze maze, int rowNum) { bool removeVertical = false; bool isAddedVertical = false; for (int i = 0; i < maze.ColumnCount - 1; i++) { W4Cell cell = maze.GetCell(i, rowNum); W4Cell nextCell = maze.GetCell(i + 1, rowNum); W4Cell topCell = maze.GetCell(i, rowNum + 1); if (cell.Set != nextCell.Set) { if (!isAddedVertical) { RemoveVerticalWall(cell, topCell); } isAddedVertical = false; } else { removeVertical = Random.Range(0, 2) > 0; if (removeVertical) { RemoveVerticalWall(cell, topCell); isAddedVertical = true; } } } CheckLastVertical(maze, rowNum, isAddedVertical); } The final step:
We process the last row by combining cells from different sets.
Code
private void CreateLastRow(W4Maze maze) { int y = maze.RowCount - 1; for(int i = 0; i < maze.ColumnCount - 1; i++) { var cell = maze.GetCell(i, y); var nextCell = maze.GetCell(i + 1, y); if(cell.Set != nextCell.Set) { RemoveHorizonWallBetweenCells( maze, cell, nextCell, y); } } } In general, this is the algorithm.
Labyrinth need to store something. In my decision there are 2 structures for storing labyrinths.
W4Maze - which in essence is an array of cells of 16 types according to the number of raised walls. The W4Cell cell itself contains just 4 bool fields that tell you which walls are raised. This structure is convenient for maze generation by the Eller algorithm and convenient for serialization.
But on the other hand, it is completely inconvenient for generating walls. The idea is that the walls of the labyrinth should have a thickness, in order to implement a similar algorithm, it is graph structures that are convenient. For this, the MazeGraph structure was introduced and the conversion from W4Maze to it was implemented. In addition, for convenience, it was created 2 lists - paths and walls. As a result, having written a simple visualization with the help of Gizmos, we get such a maze. Yellow is the wall, and green is the way.
In general, this is not bad, but there are too many unnecessary nodes in the walls and paths, which will be inconvenient in the future to generate three-dimensional visualization, so that we simplify them. This will allow to generate less meshes and avoid lighting artifacts at the junctions.
For example, the code for the walls
private void ProcessWallEdges() { for(int i = 0; i < _WallEdges.Count; i++) { for(int j = i + 1; j < _WallEdges.Count; j++) { var edge1 = _WallEdges[i]; var edge2 = _WallEdges[j]; if (Mathf.Abs(edge1.Normal.x) == Mathf.Abs(edge2.Normal.x) && Mathf.Abs(edge1.Normal.y) == Mathf.Abs(edge2.Normal.y)) { if (Edge.IsCanMerge(edge1, edge2)) { var edge = Edge.Merge(edge1, edge2); _WallEdges.Remove(edge1); _WallEdges.Remove(edge2); _WallEdges.Remove(edge); _WallEdges.Insert(i, edge); j = i; } } } } } The rest is a matter of technology. I have written my own tool for generating planes of the MeshTools class with the simplest triangulation (since we know the order of adding points). In general, unit Quads could be used, but in any case it would be necessary to recalculate the uv coordinates in order to The tiling of the material on all the walls was the same and in this case one material could be used. More details can be viewed at the link to GitHub .
So, the maze is built, correctly exposed uv-shki. Now I want to show the simplest example of the possibility of post processing using the example of automatic light placement. For this, I created the LightPlacer class and here we will again need the W4Maze maze. Algorithm post processing is quite simple. We simply set the illumination levels, translate the cell type to int, and decide whether to set the light source or not.
And again the code
public GameObject SetUpLights( W4Maze maze, float height) { GameObject lights = new GameObject(); for(int i = 0; i < maze.ColumnCount; i++) { for(int j = 0; j < maze.RowCount; j++) { var cell = maze.GetCell(i, j); if(cell.ToInt() < (int) _LightLevel) { var lightGo = CreatePointLight(); lightGo.transform.position = new Vector3( i , height * 0.9f, j); } } } return lights; } public enum LightLevel : byte { Low = 3, Medium = 5, High = 10, VeryHigh = 16 } And here is our final labyrinth!
With the help of such post processing, you can arrange decals, enemies, traps, and anything else.
Thanks for attention! Who would like to get acquainted with the decision details link to GitHub .
If someone would be more interested in the topic of mesh generation, which is an important part of the solution, I can write about this in a separate article.
Source: https://habr.com/ru/post/335974/
All Articles