Based on the famous Dijkstra's search algorithm, the A* algorithm includes the use of a heuristic function to prioritize searching in the direction of the target.
The A* algorithm is guaranteed to find a path from start to end goal (unless this is impossible due to obstacles), and will always find the optimal shortest path.
In this visualization the different kinds of cells are highlighted in different colours:
The algorithm will iterate through cells in the grid looking for the end goal. At each iteration the algorithm will examine a cell (checking if it is at the end goal) and if not it will add the current cell's valid neighbours (the adjacent cells which can be visited) to a shortlist of visitable cells (the open set). Any cells that have been checked already are added to a list of visited cells (the closed set).
The key ingredient in the A* algorithm is how the next cell to be examined is chosen. A heuristic function is used to evaluate the cells in the open set and the best looking candidates are chosen to be checked first. This helps avoid needlessly checking options that are unlikely to work (unless no other options are available).
Breadth first search (BFS) algorithm is based on the basic idea that in order to find the end goal you should prioritize searching wide (not deep).
The BFS algorithm is guaranteed to find a path from start to end goal (unless this is impossible due to obstacles), and will always find the optimal shortest path.
BFS is commonly implemented using a queue to determine the cell exploration order. A queue follows the FIFO convention: (First In First Out). When a new cell is visited its connected neighbours are added to the queue. A new cell is then chosen from the back of the queue and visited. Any valid neighbours this new cell has are then added to the back of the search queue and so will be visited only after all neighbours of the original cell have been visited.
In contrast with DFS Depth first search (DFS) algorithm prioritizes searching deep (not wide).
The DFS algorithm is guaranteed to find a path from start to end goal (unless this is impossible due to obstacles), but is NOT guaranteed to find the optimal shortest path - in fact in most cases the DFS algorithm produces very convoluted pathing.
DFS algorithm is most commonly implemented recursively but can be implemented iteratively using a stack to determine the cell exploration order. A stack follows the LIFO convention: (Last In First Out). When a new cell is visited its connected neighbours are added to the stack. A new cell is then chosen from the top of the stack and visited. Any valid neighbours this new cell has are then added to the top of the search stack and so will be visited before any neighbours of the original cell are visited.