Breadth first search(BFS) is a very powerful and useful algorithm for exploring graph like structures. A BFS searches it’s nearest neighbors first before moving on. It’s main use is to find a path using the fewest hops. Here we use it to explore a grid that can be modified by a user. In this grid, we have verticies (the grid boxes), and edges (the box north, south, east and west).

A plain english example would be as

1. Create a queue with your starting element.
2. while the queue is not empty
   1. shift out the first element.
   2. does that element meet the goal?
      1. If so quit with success
   3. Otherwise for all neighbors of that element add them to the queue if they haven’t been seen yet. Make a note of where we came from.
3. Otherwise fail.

How To Use

1. Change your grid size of anything between 4 and 40 elements wide. Hit the reset grid button.
2. Set your start point using the “place start point” button. There must be exactly one starting point.
3. Place some finish points using the “place finish point” button. There can be many finish points. In a regular BFS these are your target points.
4. Add some constraints by drawing some walls.
5. Hit either “Run” or “Step” to start the BFS
   1. The active node will be surounded with a gold border.
   2. Discovered nodes are surrounded with a dark blue border.
   3. The nodes in the queue are surrounded with a light blue border.
6. After the goal is found it will draw the path back to the starting node. It will be shown in light green

The Explorer

You can view and explore the source code on GitHub. Made with TypeScript because I can.