Prim’s Maze Generation Algorithm on a Triangular Grid

Below is an implementation of Prim’s Maze Generation Algorithm on a triangular grid. The example shows how to work with grid edges, and how you can use rhombille grids  to display the edges of triangular grids nicely. This example only uses five tiles, shown below:

[button url=”https://gamelogic.co.za/examples/grids/prims-algorithm-on-a-tri-grid/” arrow=”right”]PLAY INTERACTIVE EXAMPLE[/button]

Note: You need the Unity Web Plugin to play this example.

Core Maze Algorithm

public static IEnumerable GenerateMazeWalls(FlatTriGrid grid)
{
   IGrid<bool, pointyrhombpoint=""> walls = grid.MakeEdgeGrid(); //true indicates passable
   List wallList = new List();

   FlatTriPoint newMaizePoint = grid.RandomItem();
   var inMaze = new List();
   inMaze.Add(newMaizePoint);

   var edges = newMaizePoint.GetEdges();
   wallList.AddRange(edges);

   while (wallList.Any())
   {
      var randomWall = wallList.RandomItem();
      IEnumerable faces = (randomWall as IEdge).GetEdgeFaces().Where(x => grid.Contains(x));

      //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.GetEdges().Where(edge => !(walls[edge]));
         wallList.AddRange(edges);
      }
      else
      {
         wallList.Remove(randomWall);
      }
   }

   yield break;
}

Shell

using UnityEngine;
using System;
using System.Collections;
using System.Linq;
using Gamelogic.Grids;

public class PrimsAlgorithm : GLMonoBehaviour, IResetable
{
   public MazeCell cellPrefab;
   public MazeCell edgePrefab;
   public GameObject root;

   private readonly Vector2 cellDimensions = new Vector2(362, 310);

   public void Start()
   {
      Reset();
   }

   public void Reset()
   {
      root.transform.DestroyChildren();

      StartCoroutine(BuildGrid());
   }   

   private IEnumerator BuildGrid()
   {
      var grid = PointyRhombGrid.Rectangle(10, 10);      
      var offset = new PointyRhombPoint(-2, -5, 0);

      grid.SetGridPointTransforms(
         p => p.MoveBy(offset),
         p => p.MoveBy(offset.Negate()));

      var map = new PointyRhombMap(cellDimensions)
         .SetGridPointTransforms(
            p => p.MoveBy(offset),
            p => p.MoveBy(offset.Negate()))
         .WithWindow(ExampleUtils.ScreenRect)
         .AlignMiddelCenter(grid)
         .Scale(.98f)         
         .Translate(25 * 3.125f, 15 * 3.125f) //Manually Center
         .To3DXY();

      foreach (var point in grid)
      {
         MazeCell cell = Instantiate(cellPrefab);
         cell.transform.parent = root.transform;
         cell.transform.localScale = Vector3.one;
         cell.transform.localPosition = map[point];      

         //Yellow         
         if (InPolygon(point, -2, 3, -3, 2, -2, 3) ||
            InSegmentY(point, 0, 2, -3) && point.I == 2 ||
            InSegmentZ(point, 1, 3, -3) && point.I == 0 ||
            InSegmentX(point, 1, 3, -4) && point.I == 1)
         {
            cell.SetOrientation(point.I, false);
         }
         // Green
         else if(InSegmentX(point, -3, 0, 3) && point.I != 1)
         {
            cell.SetOrientation(3, 2 - point.I/2);
         }
         else if(InSegmentX(point, 1, 3, -4) && point.I != 1)
         {
            cell.SetOrientation(3, 5 - point.I/2);
         }
         else if(
            InSegmentY(point, -4, -1, 4) && point.I != 2 ||
            InSegmentZ(point, 1, 3, -3) && point.I != 0)
         {
            cell.SetOrientation(3, point.I + 5);
         }
         else if(
            InSegmentY(point, 0, 2, -3) && point.I != 2 ||
            InSegmentZ(point, -3, 0, 4) && point.I != 0)
         {
            cell.SetOrientation(3, point.I + 2);
         }
         //Red
         else if(
            InSegmentX(point, -3, 0, 3) && point.I == 1 ||
            InSegmentY(point, 0, 3, -4) && point.I == 2)
         {
            cell.SetOrientation(2, point.I + 5);
         }
         else if(
            InSegmentX(point, 1, 4, -5) && point.I == 1 ||
            InSegmentY(point, -4, -1, 4) && point.I == 2)
         {
            cell.SetOrientation(2, point.I + 2);
         }
         else if(InSegmentZ(point, 1, 4, -4) && point.I == 0)
         {
            cell.SetOrientation(2, point.I + 5);
         }
         else if(InSegmentZ(point, -3, 0, 4) && point.I == 0)
         {
            cell.SetOrientation(2, point.I + 2);
         }
         else
         {
            cell.SetOrientation(4, point.I + 2);
         }

         cell.SetText("");         
         cell.SetColor(Color.white);

         grid[point] = cell;
      }

      var mazeGrid = FlatTriGrid.Hexagon(3);// Rectangle(8, 6);   
      var mazeOffset = offset.MoveBy(new PointyRhombPoint(0, 1, 0));

      foreach (var point in MazeAlgorithms.GenerateMazeWalls(mazeGrid))
      {
         var gridPoint = point.MoveBy(mazeOffset);

         if(grid.Contains(gridPoint))
         {
            grid[gridPoint].SetOrientation(point.I, true);

            yield return null;
         }
      }      
   }

    private bool InPolygon(PointyRhombPoint point, int x0, int x1, int y0, int y1, int z0, int z1)
    {
      return 
         x0 <= point.X && point.X <= x1 &&
         y0 <= point.Y && point.Y <= y1 &&
         z0 <= point.BasePoint.Z && point.BasePoint.Z <= z1;
    }

   private bool InSegmentX(PointyRhombPoint point, int x0, int x1, int y)
   {
      return x0 <= point.X && point.X <= x1 && point.Y == y;
   }

   private bool InSegmentY(PointyRhombPoint point, int y0, int y1, int x)
   {
      return y0 <= point.Y && point.Y <= y1 && point.X == x;
   }

   private bool InSegmentZ(PointyRhombPoint point, int x0, int x1, int z)
   {
      return x0 <= point.X && point.X <= x1 && point.BasePoint.Z == z;
   }
}