## 3 Existing Pathfinding Techniques
### Uninformed Search Algorithms
#### 3.1.1. Breadth First Search Algorithm (BFS)  
BFS was first published in 1959 by [PERSON] and is one of the fundamental Algorithms used in games for pathfinding [20]. A popular use of this Algorithm is to find the shortest path in a grid or a maze [21]. Some of the real-world uses of this Algorithm include GPS tracking, analysis in networks and graphs, and search engines [22]. In BFS, the cells are visited one at a time. Therefore, the cells which are only a single step away from the start cell are visited first, then again, all cells which are two steps away from the start cell are visited, and this continues until all cells are visited [23]. Through BFS, we can find the shortest path from start cell to end cell with minimum number of steps traversed as shown in Figure 5. The main advantage this Algorithm has is that the solution will always be found, no matter the type of problem. If there are multiple solutions, all the solutions will be found by the BFS Algorithm and the minimum cost solution will be selected from all these solutions by the Algorithm. The disadvantage this Algorithm has is its relation to memory usage. All the nodes are stored in the tree by this Algorithm and every node will be tested on level 'n' to get a solution to level 'n + 1' [24]. The time T(n) and space S(n) complexity of the search Algorithm is given in Equations (1) and (2) where s refers to the depth of shallowest solution and n\({}^{\text{i}}\) refers to the number of nodes in level 'i'.  
\[\text{T(n)}=1+n^{2}+n^{3}+\ldots\ \ldots\ +n^{\text{s}}=\text{O(n^{s})} \tag{1}\]  
\[\text{S(n)}=\text{O(n^{s})} \tag{2}\]  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Grid** & **Grid Type** & \begin{tabular}{c} **Grid** \\ **Dimension** \\ \end{tabular} & **Smallest Unit** & **Applications** & **Ref.** & **Year** \\ \hline Triangular & Regular & 2D & \begin{tabular}{c} Equilateral \\ Triangle \\ \end{tabular} & \begin{tabular}{c} Computer Graphics, \\ Image Processing \\ \end{tabular} & [18] & 2015 \\ \hline Square & Regular & 2D & Square & Video Games, Robotics & [5,9] & 2013, 2015 \\ \hline Hexagonal & Regular & 2D & \begin{tabular}{c} Regular \\ Hexagon \\ \end{tabular} & Video Games, Robotics & [17,18] & 2015, 2018 \\ \hline Cubic & Regular & 3D & Cube & \begin{tabular}{c} Computer Graphics, \\ Image Processing, \\ Robotics \\ \end{tabular} & [18] & 2015 \\ \hline Waypoint & Irregular & - & \
\begin{tabular}{c} Navigation \\ Marker \\ \end{tabular} & Video Games, Robotics & [9,17] & 2015, 2018 \\ \hline Visibility Graph & Irregular & - & Graph Node &
\begin{tabular}{c} Games, Computational \\ Geometry \\ \end{tabular} & [5,18] & 2013, 2015 \\ \hline Mesh Navigation & Irregular & - & Edge & Video Games & [18,19] & 2016, 2015 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Grid classification based on grid type, grid dimension, smallest unit, and applications.  
In Figure 5, the BFS Algorithm will traverse the vertices in breadth-wise fashion from the top node in the graph. First, vertex 1 will be visited since it is at the top and put in queue. Next, the child nodes of vertex 1, which are vertices 2 and 3, will be visited as marked in red and put in the queue. The Algorithm 1 will then visit vertex 4 since there are no child nodes in vertex 3 and finally vertex 5.  
```
Input: Set of all vertices. Output: Search Path sequence vertices S_BFS[]  Step 1: Set s as the source vertex, Stack, BF[] = Ø and S_BFS[] = Ø  where S_BFS[] is an array having all the visited vertices and BF[] is a queue to store the vertices for processing Step 2: Push the vertex s in Queue BF[] Step 3: Until BF[] is empty, iterate the steps 4 to 7 Step 4: q = Pop BF[] Step 5: Mark the vertex q as visited and place it in the array S_BFS[] Step 6: If q is the goal, then finish the searching process Step 7: Else push one adjacent vertex of q in BF[] Step 8: Repeat steps 3 to 6 until all the vertices are in S_BFS[]
```  
**Algorithm 1** Breadth First Search Algorithm.