How to create a path for this maze without having deadends

Hi Team,
Firstly i would like to thank Laurent for his effort on the maze.I had a doubt about the maze on similar lines.This post was initially posted by @laurent_delrieu laurent

Please find attached grasshopper script.Where is have used ivy and parakeet plugins to create the maze.Now i need to create a defined path as shown in the png where the black line represents walls and the red line represents the path taken .16OCT.gh (12.0 KB) 16THOCT.3dm (257.5 KB)

Hello as the creator of this script I understand your question. But it will be appreciated you give credit to me! For ivy and Parakeet I understand you have the same problem. It is quite logic as we are doing perfect maze.

The solution (for the title question) must not be difficult to solve. You shall find all dead end, connect it to a path and destroy a wall.

sorry for that Laurent …yes i did find this image at one of the grasshopper forum.I am new to this forum.
How do i connect it to a path and destroy a wall? please could u help me out.

I am not on my computer now. There are 2 questions in what you ask
Suppress dead ends (for all maze tools)
Having wall in script (for ivy and Parakeet)

a question
As I suppress all my maze script on the web. Do you have my script ?

Making a maze without dead end could also be done with a different method.

No Laurent I couldn’t find a script on the web. I would be grateful if u could share me.
I hav attached an image below .This is what i am trying to do in my project.I want to create an entry an exit path.The yellow line in the image represents the path taken by a person. The black line represent the wall i need to create.i wanted to know how i can create this wall (blackline).
Thanks:)

I will look at that this weekend.

1 Like

Here is a way of doing


I used Offset from clipper as it is very useful to thicken some curves.

16OCT.gh (12.4 KB)

And with middle wall, not too hard. Clipper is your friend :yum:


16OCT_LD.gh (14.1 KB)

4 Likes

Great work Laurent! What’s the guarantee a closed path exists?

It is no more a maze. It is an offset of a maze path so it is closed. It is one way of walking a surface with a single curve. There is discussion on that.

1 Like

Wonderfull…Thanks a lot Laurent… This what i was looking for…:slight_smile:

1 Like

Hi @laurent_delrieu
Please could explain be the c# script used in this grasshopper script made by you.

A drawing is worth ten thousands words
Red are Paths,
maze_
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;
  }
5 Likes

Thanks a lot. But is there way where i could do the same without using the c# component?

Grasshopper is not adapted for recursion. The first answer is no. You could try with Anemone but this seems difficult. Learn C# vb python

1 Like

okay thanks Laurent :slight_smile:

Hi @laurent_delrieu,
Could you explain how back tracking logic works in the maze component of parakeet plugin.I want to know the logic behind using this component.

Ask the developper for parakeet @motaghi.esmaeil . There are many resources on the web explaining algorithm. I published here the simplest of my maze generator. I developed another that uses a driver that has different logic, random, zigzag, try to come back or oriented in a direction.