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