A drawing is worth ten thousands words
Red are Paths,

Here is the commented code
maze_simple_EXPLAINED.gh (11.4 KB)
private void RunScript(Mesh mesh, int seed, int limit, ref object Walls, ref object Path)
{
//Perfect maze on mesh using Kruskal's algorithm
//Edge of mesh are walls
//Centers of face are used for path
//Laurent Delrieu
//xxxx@xxxx
//V1 : 13 of may 2016
//References
// http://www.astrolog.org/labyrnth/algrithm.htm
// http://www.jamisbuck.org/mazes/
// http://elfnor.com/maze-any-mesh-in-blender.html
// http://www.grasshopper3d.com/forum/topics/wip-maze-definition
//TODO
// NGON mesh using Turtle, Plankton or new rhino 6 mesh
//Creates unconnected Path
List<LDPath> paths = new List<LDPath>();
for (int i = 0; i < mesh.Faces.Count; i++)
{
//A new cell for each face
paths.Add(new LDPath(i));
}
//Wall
//fixed_walls_edge_indice are final walls ot the maze
List<int> walls_edge_indice = new List<int>();
List<int> fixed_walls_edge_indice = new List<int>();
for (int i = 0; i < mesh.TopologyEdges.Count; i++)
{
int[] connectedFaces = mesh.TopologyEdges.GetConnectedFaces(i);
if (connectedFaces.Length == 2) //It is not an edge
{
walls_edge_indice.Add(i);
}
else
{
if (connectedFaces.Length == 1)//It is an edge
{
fixed_walls_edge_indice.Add(i);
}
}
}
Random rnd = new Random(seed);
//if there are many Paths it means that the maze is not finished
int count = 0;
while ((paths.Count > 1) && count < limit)
{
count++;
//Abort if escape pressed
if (GH_Document.IsEscapeKeyDown()) GrasshopperDocument.RequestAbortSolution();
//Choose a random value in walls list
int randomWallNumber = rnd.Next(walls_edge_indice.Count);
int[] connectedFaces = mesh.TopologyEdges.GetConnectedFaces(walls_edge_indice[randomWallNumber]);
//Edge that is inside the mesh, not on the border
if (connectedFaces.Length == 2)
{
int path0 = getPath(paths, connectedFaces[0]);
int path1 = getPath(paths, connectedFaces[1]);
//The wall share same path => we add it to fixed wall
//If on the 2 sides of the wall are from the same list it means they are connected
if (path0 == path1)
{
fixed_walls_edge_indice.Add(walls_edge_indice[randomWallNumber]);
}
//Else they are not connected so we destroy the wall
else
{
paths[path0].Add(paths[path1], connectedFaces[0], connectedFaces[1]);
paths.RemoveAt(path1);
}
walls_edge_indice.RemoveAt(randomWallNumber);
}
else
{
throw new ArgumentException("One wall with just face ! " + connectedFaces.Length);
}
}
//We add all the list containing remaining walls
foreach (var i in walls_edge_indice)
{
fixed_walls_edge_indice.Add(i);
}
List<Line> lines = new List<Line>();
foreach (var edge in fixed_walls_edge_indice)
{
lines.Add(mesh.TopologyEdges.EdgeLine(edge));
}
Walls = lines;
List<Line> pathtLines = new List<Line>();
foreach (LDPath path in paths)
{
pathtLines.AddRange(path.ToLines(mesh));
}
Path = pathtLines;
}
// <Custom additional code>
/// <summary>
/// Class to describe a path
/// </summary>
public class LDPath
{
List<int> faces;//Track all the faces that are in the Path
List<int> faceFromList;//Index of face index from, same size as list Under
List<int> faceToList;//Index of face index to, same size as list Above
/// <summary>
/// Initialize an empty path
/// </summary>
/// <param name="face">Number of the face (frol a mesh)</param>
public LDPath(int face)
{
faces = new List<int>();
faces.Add(face);
faceFromList = new List<int>();
faceToList = new List<int>();
}
/// <summary>
/// Add a new Path
/// </summary>
/// <param name="newPath"></param>
/// <param name="faceFrom"></param>
/// <param name="faceTo"></param>
/// <returns></returns>
public void Add(LDPath newPath, int faceFrom, int faceTo)
{
faceFromList.Add(faceFrom);
faceToList.Add(faceTo);
//Write all faces that are in the Path
foreach (var face in newPath.faces)
{
this.faces.Add(face);
}
//Write all connexions
for (int i = 0; i < newPath.faceFromList.Count; i++)
{
faceFromList.Add(newPath.faceFromList[i]);
faceToList.Add(newPath.faceToList[i]);
}
}
/// <summary>
/// Return all the paths of the maze
/// </summary>
/// <param name="mesh">Mesh that is used to calculate the position of paths</param>
/// <returns>List of Lines</returns>
public List<Line> ToLines(Mesh mesh)
{
List<Line> lines = new List<Line>();
for (int i = 0; i < faceFromList.Count; i++)
{
lines.Add(new Line(FaceCenter(mesh, faceFromList[i]), FaceCenter(mesh, faceToList[i])));
}
return lines;
}
/// <summary>
/// Return true is Path contains
/// </summary>
/// <param name="faceIndex">Face index, usualy the face index of a mesh</param>
/// <returns></returns>
public bool AsFace(int faceIndex)
{
bool retour = false;
foreach(var f in faces)
{
if (f == faceIndex)
{
retour = true;
break;
}
}
return retour;
}
}
/////////////////////////////////////
//Search in list if there is a face in paths
/// <summary>
/// Return the index
/// </summary>
/// <param name="paths"></param>
/// <param name="face"></param>
/// <returns></returns>
public int getPath(List<LDPath> paths, int faceIndex)
{
int retour = -1;
for (int i = 0; i < paths.Count; i++)
{
if (paths[i].AsFace(faceIndex))
{
retour = i;
break;
}
}
return retour;
}
/// <summary>
/// Calculate the center of the face
/// </summary>
/// <param name="mesh"></param>
/// <param name="face"></param>
/// <returns></returns>
public static Point3d FaceCenter(Mesh mesh, int face)
{
Point3d pt = new Point3d(0, 0, 0);
pt = pt + mesh.Vertices[mesh.Faces[face].A] + mesh.Vertices[mesh.Faces[face].B] + mesh.Vertices[mesh.Faces[face].C];
if (mesh.Faces[face].IsQuad)
{
pt = pt + mesh.Vertices[mesh.Faces[face].D];
pt = pt / 4.0;
}
else
{
pt = pt / 3.0;
}
return pt;
}