The Depth-First Search (DFS) algorithm is a path-finding technique suitable for low-memory devices. Another common use is to build mazes with a few modifications to the list of nodes visited and discovered, however the main algorithm stays the same.
This is a high-level algorithm that relies on each graph's implementation of the general functions, so the algorithm is implemented in the Graph
class.
It is important to
Even though this recipe is only defining a function, please take into consideration the comments in the code to understand the indentation and code flow for effectively:
GetPathDFS
function:public List<Vertex> GetPathDFS(GameObject srcObj, GameObject dstObj) { // next steps }
if (srcObj == null || dstObj == null) return new List<Vertex>();
Vertex src = GetNearestVertex(srcObj.transform.position); Vertex dst = GetNearestVertex(dstObj.transform.position); Vertex[] neighbours; Vertex v; int[] previous = new int[vertices.Count]; for (int i = 0; i < previous.Length; i++) previous[i] = -1; previous[src.id] = src.id; Stack<Vertex> s = new Stack<Vertex>(); s.Push(src);
while (s.Count != 0) { v = s.Pop(); if (ReferenceEquals(v, dst)) { return BuildPath(src.id, v.id, ref previous); } neighbours = GetNeighbours(v); foreach (Vertex n in neighbours) { if (previous[n.id] != -1) continue; previous[n.id] = v.id; s.Push(n); } }
The algorithm is based on the iterative version of DFS. It is also based on the in-order traversing of a graph and the LIFO philosophy using a stack for visiting nodes and adding discovered ones.
We called the function BuildPath
, but we haven't implemented it yet. It is important to note that this function is called by almost every other path-finding algorithm in this chapter, that's why it's not part of the main recipe.
This is the code for the BuildPath
method:
private List<Vertex> BuildPath(int srcId, int dstId, ref int[] prevList) { List<Vertex> path = new List<Vertex>(); int prev = dstId; do { path.Add(vertices[prev]); prev = prevList[prev]; } while (prev != srcId); return path; }