Learn how to code the depth first search pathfinding algorithm in this coding tutorial using Processing and Java. Then watch how the explored nodes and chosen path appear in the graphical demo.
Introduction
The depth first search algorithm will explore the first node it finds and continue picking the first connected node until it either finds the goal or runs into a dead end. At which point it will backtrack and pick the next unexplored node. It will continue doing this until the goal is found or every node is explored.
In the last tutorial, we generated a node graph in Processing. This tutorial will add code to the existing code from the last tutorial. So make sure you follow the last tutorial first if you want to see a graphical demo of the pathfinding in action. Or read on if you just want to learn about the depth first search algorithm.
Open Processing
Open Processing, then add these imports to the main tab. We will need them later for the pathfinding algorithm.
import java.util.Collections;
import java.util.Stack;
Then add an array list. This will be used for showing the nodes which the depth first search algorithm has explored in the graphical demo.
ArrayList<Node> exploredNodes = new ArrayList<Node>();
int currentExploredSize = 0;
Now add an array list called path. This will store the path chosen by the pathfinding algorithm.
ArrayList<Node> path = new ArrayList<Node>();
int currentPathSize = 0;
Finally add one more variable. This will be used as a timer to control how often the path is updated when rendering.
int startTime = 0;
Node
Open the “Node tab”
Add two new variables to the Node class.
class Node
{
PVector position = new PVector();
ArrayList<Node> adjacentNodes = new ArrayList<Node>();
Node parent = null;
boolean explored = false;
void Add(Node other)
{
adjacentNodes.add(other);
}
}
The “parent” node is the previous node we travelled through to get to the current node.
The “explored” boolean is used to mark whether this node has been explored yet or not.
Depth First Search
Create a new tab called “Pathfinding”.
Then create a new function. This function will run the depth first search pathfinding algorithm. It takes the start node, goal node and the path. The path will only be set if we find the goal, since it’s possible the goal is inaccessible.
boolean DepthFirstSearch(Node start, Node goal, ArrayList<Node> path)
{
}
First we will clear the path list and the explored nodes list. Then we will create a variable to record the number of moves the algorithm has taken to get to the goal.
path.clear();
exploredNodes.clear();
int moves = 0;
Next we will check if the start node is actually the goal node.
if(start == goal)
{
println("Goal is start node");
path.add(start);
return true;
}
Now for the main algorithm. We create a stack and push the start node into it. Then we create an empty node variable called “current”.
Stack<Node> stack = new Stack<Node>();
stack.push(start);
Node current = null;
Next we check if the stack is empty in a while loop. If the stack is empty, then we are done searching the node graph.
while(!stack.empty())
{
}
First we increment the number of moves.
++moves;
Then get the current node from the stack. If it is explored, then we will continue. Else we mark the node as explored, and add the current node to the explored nodes list.
current = stack.pop();
if(current.explored) continue;
current.explored = true;
exploredNodes.add(current);
Now we will loop through the current node’s adjacent connected nodes.
for(Node node : current.adjacentNodes)
{
}
First we need to check if the node has been explored.
if(node.explored) continue;
If the node hasn’t been explored, then we can add it to the stack. We will set the parent node to the current node.
stack.push(node);
node.parent = current;
Next we check if the current node is the goal.
if(node == goal)
{
}
If the node is the goal, then we can create the path by backtracking from the goal.
We first print the number of moves taken.
println("Goal has been found in " + moves + " moves");
Then we clear the path list and set the current node to the node variable. Then we will loop through all of the parents of the current node, until we reach the start point which doesn’t have a parent node. Finally we just need to return true and reverse the list, so it starts from the start point instead of the goal point.
path.clear();
current = node;
while(current != null)
{
path.add(current);
current = current.parent;
}
Collections.reverse(path);
return true;
Then outside of the while loop (which checks if the stack is empty) at the end of the function, we will return false and print the number of moves taken, if the algorithm fails to find the goal.
println("Failed to find the goal in", moves, "moves");
return false;
Full algorithm code:
boolean DepthFirstSearch(Node start, Node goal, ArrayList<Node> path)
{
path.clear();
exploredNodes.clear();
int moves = 0;
if(start == goal)
{
println("Goal is start node");
path.add(start);
return true;
}
Stack<Node> stack = new Stack<Node>();
stack.push(start);
Node current = null;
while(!stack.empty())
{
++moves;
current = stack.pop();
if(current.explored) continue;
current.explored = true;
exploredNodes.add(current);
for(Node node : current.adjacentNodes)
{
if(node.explored) continue;
stack.push(node);
node.parent = current;
if(node == goal)
{
exploredNodes.add(node);
println("Goal has been found in " + moves + " moves");
path.clear();
current = node;
while(current != null)
{
path.add(current);
current = current.parent;
}
Collections.reverse(path);
return true;
}
}
}
println("Failed to find the goal in", moves, "moves");
return false;
}
Setup
Go back to the main tab. Then edit the “setup” function. We will use it to set the window size, generate the node graph and run the depth first search pathfinding algorithm. Then finally we will set the start time to the current time in milliseconds since the program was run.
void setup()
{
size(720, 720);
CreateNodeGraph();
DepthFirstSearch(start, goal, path);
startTime = millis();
}
Rendering
Now we will render a graphical demo of the pathfinding in action!
Create a function for rendering the path.
void RenderPath()
{
}
Add this code inside the function. Every 100 milliseconds it will draw 1 explored node or 1 path node.
// Control size of path
if(millis() - startTime > 100)
{
startTime = millis();
if(currentExploredSize == exploredNodes.size())
{
currentPathSize = min(++currentPathSize, path.size());
}
currentExploredSize = min(++currentExploredSize, exploredNodes.size());
}
Then render the current explored nodes.
// Draw the nodes depth first search explores
stroke(10);
strokeWeight(4);
fill(20, 200, 200);
Node node = null;
for(int i=0; i<currentExploredSize; ++i)
{
node = exploredNodes.get(i);
circle(node.position.x, node.position.y, extent);
}
And finally render the current path nodes.
// Draw the path depth first search takes
stroke(10);
strokeWeight(4);
fill(200, 200, 20);
for(int i=0; i<currentPathSize; ++i)
{
node = path.get(i);
circle(node.position.x, node.position.y, extent);
}
Now edit the “draw” function, and add the new “RenderPath” function to the draw order.
void draw()
{
background(50);
RenderConnections();
RenderNodes();
RenderPath();
RenderStartAndGoal();
}
Keyboard
Add this code to restart the animation using the “R” key.
void keyPressed()
{
if(key == 'r' || key == 'R')
{
currentExploredSize = 0;
currentPathSize = 0;
startTime = millis();
}
}
Finally you just need to run the sketch, and you should see a cool graphical demo of the pathfinding in action!
Exploring All Nodes
If you want to see the depth first search algorithm explore every connected node in the node graph. Then remove the check which exits after finding the goal.
if(node == goal)
{
}
Conclusion
Thanks for reading this tutorial. You have learned how to code the depth first search algorithm so that it searches a node graph. And can view a graphical demo as it explores nodes and draws the path it has taken.
In the next tutorial we will explore a grid using breadth first search.
Agate DRAGON Games 