Interactive Breadth First Search in a Grid
2020 December 20

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.

    Remember you can also subscribe using RSS at the top of the page!

    Share this on → Mastodon Twitter LinkedIn Reddit

    A selected list of related posts that you might enjoy:

    Written by Henry J Schmale on 2020 December 20
    Hit Counter