searchdepth-first-searchmazestate-space

How do I Backtrack a Stack-Based Depth First Search


I am trying to implement a DFS algorithm to work in a maze. The maze has walls. The DFS gets stuck in a corner and does not backtrack therefore it results in an infinite loop. How should I rewrite my code to get it to backtrack. This is code for a space-search type of DFS.

Depth-First-Search Function

public List<Node<Point2D>> DFS(Problem p)
        {
            Node<Point2D> root = new Node<Point2D>() { Data = p.initial, Parent = null };

            frontierStack.Push(root);

            while (frontierStack.Count > 0 && explored.Count < 55)
            {
                Node<Point2D> currentNode = frontierStack.Pop();
                explored.Add(currentNode.Data.ToString());
                Console.WriteLine(currentNode);

                //Debug.WriteLine(explored.Count);

                foreach (string action in p.Action)
                {
                    if (p.Result(currentNode.Data, action) != null)
                    {
                        Node<Point2D> adjacentNode
                        = new() { Data = p.Result(currentNode.Data, action), Parent = currentNode };

                        if (explored.Contains(adjacentNode.Data.ToString()) == false || frontierStack.Contains(adjacentNode) == false)
                        {
                            if (p.GoalTest(adjacentNode.Data) == true)
                            {
                                return GetNodes(adjacentNode);
                            }
                        }
                        frontierStack.Push(adjacentNode);
                    }


                }
            }

            return null;
        }

Here is Where it gets stuck:
DFS Search

The black line is the path it took, the blue 'X' are walls and the red 'X' is where it gets stuck at point (1,3) - (1,4). I have been trying to resolve this for a few hours now. Nothing seems to be working. I am still a beginner so sorry for asking something so trivial and thank you for your help in advance.


Solution

  • Solved it. Hope this is useful for other beginners out there.

    Updated DFS Algorithm

    foreach (string action in p.Action)
    {
      if (p.Result(currentNode.Data, action) != null)
      {
        Node<Point2D> adjacentNode = new() {
          Data = p.Result(currentNode.Data, action),
          Parent = currentNode
        };
        frontierStack.Push(adjacentNode);
    
        if (explored.Contains(adjacentNode.Data.ToString()) == false || frontierStack.Contains(adjacentNode) == false)
        {
          if (p.GoalTest(adjacentNode.Data) == true)
          {
            return GetNodes(adjacentNode);
          }
        }
        else if (explored.Contains(adjacentNode.Data.ToString()) == true && frontierStack.Contains(adjacentNode) == true)
        {
          frontierStack.Pop();
        }
      }
    }
    

    Add the else if to check if it is either visited/explored and still in the frontier.