Search Algorithms - Making of Path Finding API

Breadth First Search(B.F.S) - Speaking of this algorithm, it is a generalization of the tree traversal method. In addition, it's derived searches use a tree structure to search the state space(i.e., the terrain) so a tree node data structure for planning will be necessary. Here's an example of the skeleton of such a node data structure: PlannerNode{ Node* parent; SearchNode* vertex};

Here's a sketch of how a breadth-first search would work over tiles:

Greedy Best First Search(G.B.F.S) - While the BFS algorithm will find the solution path with the least number of planner nodes, it may create an extremely large number of them before that happens. The main issue here is that the open list is treated like a regular queue. By changing the behavior of the open list so that it orders a node certain way, attempting a more efficient search is a good idea!

The GBFS orders its nodes so that the ones closest to the goal are the nearest to the front of the open list using a priority queue. This algorithm is informed because its ordering is based on goal information. Using the distance to the goal to estimate which open node is "best" is an example of heuristic.

Here's a sketch of how a greedy search would work over tiles:

Uniform Cost Search(U.C.S) - Both the BFS and GBFS assume that each passable tiles incur same cost to traverse. The U.C.S algorithm which is actually a variant of Dijkstra's algorithm that searches one goal instead of multiple goals - handles the different tile weights by incorporating them into each planner node's given cost, which the algorithm  then uses to order its open nodes.

Since the ordering imposed on the open nodes is not based on any goal information, this algorithm, like BFS is uninformed. It is also optimal in terms of the solution it finds which always have lowest cost, while the BFS algorithm is optimal with regards to the number of the nodes in the path.

Here's a sketch of how uniform cost search would work over tiles:

A*(A-Star) - A* combines the look-ahead abilities of the GBFS algorithm with look-behind abilities of the UCS algorithm by taking into account both the heuristic cost and the given cost of each planner node. While the definition of the given cost hasn't changed, the heuristic cost is now the product of the greedy search heuristic cost and the heuristic weight, whose value can be changed to customize the behavior of A*. The sum of the new heuristic cost and the given cost is the final cost, which A* then uses to sort the open nodes.

A* favors paths that head more directly toward the goal, it tries to avoid crossing regions with higher weights until there is no other choice.

Here's a sketch of how A* would work over tiles: