BFS algorithm - 3D visualization
Visualization of BFS algorithm in a 3d animated scene.
Model, code, animation made with Blender and Python scripts.
BFS is a search algorithm that garantees to find a path with the minimum number of steps between two given nodes of a graph.
It uses a queue data structure implementing the "first in first out" principle to organize priority while exploring.
It will iterate dequeuing the first node from this open list at each loop, first one being the given start node, and visiting all this node's neighbors until it reaches the goal node.
By keeping track of relationships leading from one node to another, we can end up reconstructing the path from goal node to start node going from child to parent.
BFS only works in unweighted graphs, thus if diagonal linkage is allowed, it will not take into account the physical distance between to points, and consider a diagonal move has the same length in space as an orthogonal move.