Prim’s Maze Generation Algorithm on a Hexagonal Grid

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;
   }
}