Introduction
In this tutorial, we learn about the breadth first search (BFS) algorithm and how to apply it a simple 2D grid of nodes.
How does BFS work?
There are plenty of great resources on the internet that explain how BFS works with different types of graphs (see References section to get you started). But simply put, the BFS algorithm we will implement works as follows:
- From a given start position, find all adjacent nodes
- For each node, do the following:
- Is the node the target node? If yes, then we are done.
- Has the node already been visited? If yes, ignore this node
- Add all neighbors of this node to the list of nodes to visit
- Mark the node as visited
Using Unity3d, we will show how the algorithm works visually by highlighting the different steps BFS goes through in order to find its destination.
Unity3d Project Setup
We will use Unity3d to visualize the search algorithm. This section covers the basic project setup.
Create a new 2D project:
To keep our project clean and organized, create the following directories and save the current scene under the scene directory:
Now, let's create the basic tile we will be using for out search algorithm. Create an Cube (under GameObject -> 3D Object), add an empty GameObject as a child and add a TextMesh (under Component -> Mesh -> Text Mesh) to the child GameObject. I suggest the following Text Mesh configuration (character size: 0.015, font size: 300):
This should result in a cube containing the number 10:
Set the main Tile GameObject's x and y scale both to 0.95. This will ensure that when we draw the grid there is some spacing between the tiles.
Add a script called Tile to the Tile parent object. Change the script to the following:
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class Tile : MonoBehaviour
{
private int weight;
private TextMesh weightText;
public void Awake()
{
weightText = GetComponentInChildren<TextMesh>();
}
public void SetWeight(int weight)
{
this.weight = weight;
weightText.text = string.Format("{0}", weight);
}
}
The above code allows us to programmatically change the weight of the given tile.
Move the Tile object from the Hierarchy to your prefabs folder to create a prefab of our newly created object. Once the prefab is created, remove the Tile from the hierarchy.
Next, let's create a grid of tiles by creating a new empty GameObject and adding a new script to it called GridCreator:
Open the GridCreator script. Let's add some public variables (so that they are exposed in the editor) to define our grid:
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class GridCreator : MonoBehaviour
{
public int gridWidth;
public int gridHeight;
public GameObject tilePrefab;
void Start()
{
}
}
Define the grid with and height in the Unity editor and add the Tile prefab:
Let's create a 10 by 10 grid of tiles by adding the following code in the Start() method of the GridCreator script:
for (int w = 0; w < gridWidth; w++)
{
for (int h = 0; h < gridHeight; h++)
{
GameObject gameObject = Instantiate(tilePrefab, new Vector2(w, h), Quaternion.identity);
Tile tile = gameObject.GetComponentInChildren<Tile>();
tile.SetWeight(w * gridWidth + h);
}
}
Center the camera by using the following Main Camera configuration:
This should result in something similar to the following:
Perfect! We now have the basic grid setup. In the next chapter, we will link up the different tiles to properly describe a grid of tiles, each tile only "knowing" its own neighbors.
