Breadth First Search Implementation

Before we continue with implementing the actual algorithm, let's clean up our project a bit.

Right now, we will only use a grid of unweighted nodes so let's first remove the numbers from the tiles. We will later re-enable them when once we implement weighted nodes.

The simplest way to do this is by disabling the Mesh Renderer on the WeightText component which is a sub-component of the Tile Prefab:

Create a new script and call it BreathFirstSearch. The initial code looks as follows:

using UnityEngine;
using System.Collections;
using System.Collections.Generic;

public class BreathFirstSearch : MonoBehaviour
{
    public Color START_COLOR = Color.red;
    public Color END_COLOR = Color.green;
    public Color END_FOUND_COLOR = Color.yellow;
    public Color VISITED_COLOR = Color.cyan;

    private GridCreator gridCreator;
    private Tile start;
    private Tile end;

    public void StartBFS(GridCreator gridCreator)
    {
        this.gridCreator = gridCreator;

        start = randomTile();
        start.SetColor(START_COLOR);

        end = randomTile();
        end.SetColor(END_COLOR);
    }

    private Tile randomTile()
    {
        return gridCreator.Tiles[
            Random.Range(0, gridCreator.gridWidth),
            Random.Range(0, gridCreator.gridHeight)
        ];
    }
}

All the above script does is colorize both a random start and end tile.

Add the above script to the Grid game object. Since we made the color variables public, you will also have the ability to change the color directly from the Unity editor:

Let's create a small drop down menu for the Grid object so we can selectively switch between different algorithms we may want to implement at some point:

using UnityEngine;

public class GridCreator : MonoBehaviour 
{
    public int gridWidth;
    public int gridHeight;

    public GameObject tilePrefab;

    public Tile[,] Tiles { get; private set; }

    [System.Serializable]
    public enum ALGORITHM
    {
        BREATH_FIRST_SEARCH,
        TBD
    }

    public ALGORITHM algorithm;
    ...

Also note that I have added a getter property for the Tiles variable. We will use this in a bit to access the array of tiles.

Now, at the end of the Start() method, let's call the BreathFirst algorithm:

if (algorithm == ALGORITHM.BREATH_FIRST_SEARCH)
{
    breathFirstSearch = GetComponent<BreathFirstSearch>();
    breathFirstSearch.StartBFS(this);
}

If you now run the project, you should see something similar to the following (restarting the application will select other start and end tiles at random):

Let's implement the rest of the breadth first search algorithm.

First, we need a couple additional variables to keep track of our worker queue (frontier) as well as a list of tiles we have already visited (visited):

public class BreathFirstSearch : MonoBehaviour
{
    ...

    private Queue<Tile> frontier;
    private List<Tile> visited;

    public void StartBFS(GridCreator gridCreator)
    {
        ...

        frontier = new Queue<Tile>();
        visited = new List<Tile>();
  }

In order to animate the breadth first search, we are making use of a construct called a Coroutine. You can find more information about it here: https://docs.unity3d.com/ScriptReference/MonoBehaviour.StartCoroutine.html.
It's a way of continuously executing a piece of code. Since we want to continue searching until we find the "end" tile, this works well for our use-case.

Add the following Coroutine to the BreathFirstSearch class:

IEnumerator RunBFS()
{
    frontier.Enqueue(start);
    visited.Add(start);

    bool foundEndTile = false;

    Tile current = null;
    while (frontier.Count != 0)
    {
        if (foundEndTile)
        {
            break;
        }

        current = frontier.Dequeue();

        HashSet<Tile> neighbours = current.GetNeighbors();
        foreach (Tile tile in neighbours)
        {
            if (tile == end)
            {
                tile.SetColor(END_FOUND_COLOR);
                foundEndTile = true;
                break;
            }

            if (!visited.Contains(tile))
            {
                frontier.Enqueue(tile);
                visited.Add(tile);
                tile.SetColor(VISITED_COLOR);
            }
        }

        yield return new WaitForSeconds(.1f);
    }
}

Let's walk through this code:

On line 3, we add the start tile to the worker queue. We will pull tiles from the worker queue as we go through the search.

Line 4 adds the start tile to the visited tiles since we know that the start tile cannot be the end tile. Any tiles in the visited tiles tells the algorithm to skip it as it has already been visited.

Line 9 starts a while loop and it will continue looping as long as we have more tiles in the worker/frontier queue. We retrieve the next tile on line 16, get its neighbours and start iterating over all of them. If any of the neighbours are the tile we are looking for, then we are finished (line 21 - 26). Otherwise, we add the neighbour tile to the visited list and add it into our worker queue.

Line 36 ensures that the program runs with a delay so that we can actually see the animation based on the while loop.

That concludes the actual algorithm. There is one last thing we need to do which is hook up this Coroutine to the rest of the code. Simply add the StartCoroutine call to the end of the StartBFS method:

public void StartBFS(GridCreator gridCreator)
{
    ...

    StartCoroutine("RunBFS");
}

Now, when you run the program, you should see the actual animation for the breath first search:

This concludes this tutorial. Feel free to enhance the current solution. A couple of possible improvements are listed below.

Improvements

• Have multiple destinations and stop once the first one is found
• Using Unity3D's UI capabilities, allow choosing both the start and destination tile by clicking on the grid itself
• Add obstacles on the grid (you will likely want to use a weighted graph for this)
• In addition to the breadth first search here, use an algorithm such as Dijkstra's algorithm to find the shortest path from the start to the destination tile

References

https://en.wikipedia.org/wiki/Breadth-first_search

https://www.ics.uci.edu/~eppstein/161/960215.html

https://docs.unity3d.com/ScriptReference/MonoBehaviour.StartCoroutine.html