Skip to content

6

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.

I came across the below problem on Project Euler which is a fantastic website to practice and improve your coding skills by solving interesting challenges such as this:


If we take 47, reverse and add (47 + 74 = 121) it results in a palindrome.

Not all numbers produce palindromes so quickly. For example,

349 + 943 = 1292
1292 + 2921 = 4213
4213 + 3124 = 7337

That is, 349 took three iterations to arrive at a palindrome.

Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome.

A number that never forms a palindrome through the reverse and add process is called a Lychrel number. You can assume that every number below ten-thousand will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome.

In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).

How many Lychrel numbers are there below ten-thousand?


You are encouraged to attempt to solve the problem yourself. See the next page for a possible solution of this problem.

2

Introduction

Ever heard of a zero-player game? Well, that's what Conway's Game of Life is. You can think of it as a very basic evolutionary simulation based on some very simple rules.

As a famous Chinese philosopher once said: "Gifs say more than a thousand words", so here we go:

The rules of the 2D Game of Life are simple:


  1. A live cell with one or zero neighbours dies due to underpopulation.
  2. A live cell with two or three neighbours lives.
  3. A live cell with more than three neighbours dies due to overpopulation.
  4. A dead cell with exactly three live neighbours comes to live due to reproduction.

If you implement the above rules, you get Conway's Game of Life.

So what's this tutorial about? Let's see how we can apply the above rules to a 3D Game of Life!