This example shows how to implement Prim’s Maze Generation Algorithm on a hex grid. The grid used in the implementation is half the size of the “visual” grid, so that some cells (of the implementation grid) represent faces (of the visual grid) and some cells represent edges. This scheme uses the four tiles below:
You can run the interactive example below (just click on it!) You need the Unity Web Plugin.
[unity src=”936″]
The basic algorithm is similar to the one on the triangular grid, but in this case, only one grid is used. The main difference between the two is in what options are available for tile design. This scheme, for example, allows variations on the face tiles that is not possible with the other scheme.
The following image shows the tiles more clearly:
Core Maze Algorithm
public static IEnumerable GenerateMazeWalls(PointyHexGrid grid) { IGrid<bool, pointyhexpoint=""> walls = grid.CloneStructure(); //true indicates passable foreach(var point in walls) { walls[point] = point.GetColor2_4() == 0; } List wallList = new List(); var newMaizePoint = grid.Where(p => p.GetColor2_4() == 0).RandomItem(); var inMaze = new List(); inMaze.Add(newMaizePoint); var edges = newMaizePoint.GetNeighbors(); wallList.AddRange(edges); while (wallList.Any()) { var randomWall = wallList.RandomItem(); IEnumerable faces = GetEdgeFaces(randomWall).Where(p => grid.Contains(p)); //At least one of the two faces must be in the maze if (faces.Any(point => !inMaze.Contains(point))) { newMaizePoint = faces.First(point => !inMaze.Contains(point)); inMaze.Add(newMaizePoint); walls[randomWall] = true; yield return randomWall; // Add all edges that are not passages edges = newMaizePoint.GetNeighbors().Where(edge => !(walls[edge])); wallList.AddRange(edges); } else { wallList.Remove(randomWall); } } yield break; }
Helper
public static IEnumerable GetEdgeFaces(PointyHexPoint point) { int color = point.GetColor2_4(); List faces = new List(); switch (color) { case 0: //error! break; case 1: faces.Add(point + PointyHexPoint.East); faces.Add(point + PointyHexPoint.West); break; case 2: faces.Add(point + PointyHexPoint.SouthWest); faces.Add(point + PointyHexPoint.NorthEast); break; case 3: faces.Add(point + PointyHexPoint.SouthEast); faces.Add(point + PointyHexPoint.NorthWest); break; } return faces; }
Shell
public class PrimsAlgorithmHex : GLMonoBehaviour, IResetable { public Cell cellPrefab; public GameObject root; private readonly Vector2 cellDimensions = new Vector2(69, 80); public void Start() { Reset(); } public void Reset() { root.transform.DestroyChildren(); StartCoroutine(BuildGrid()); } public IEnumerator BuildGrid() { var grid = PointyHexGrid.Hexagon(6); var map = new PointyHexMap(cellDimensions) .WithWindow(ExampleUtils.ScreenRect) .AlignMiddelCenter(grid) .Scale(.97f) //Makes cells overlap slightly; prevents border artefacts .To3DXY(); foreach (var point in grid) { Cell cell = Instantiate(cellPrefab); cell.transform.parent = root.transform; cell.transform.localScale = Vector3.one; cell.transform.localPosition = map[point]; cell.SetText(""); int color = point.GetColor2_4(); cell.SetFrame(color); grid[point] = cell; } foreach (var point in MazeAlgorithms.GenerateMazeWalls(grid)) { grid[point].SetFrame(0); yield return null; } yield return null; } }
Pingback: Day 2 Game 2: 30 games in 30 days using Grids | Gamelogic
Pingback: What are grid colorings? | Gamelogic