Tree search

Motivation:

You want to create a tree system where an NPC can move around to chase a player.

So this tutorial is about trying to understand tree search with Breadth-First-Search  (BFS) and Depth-FirstSearch (DFS).

To do so we will:

  • Define a tree
  •  Define BFS/DFS
  • Define Queue/stack
  • Basic implementation
  • Avoid recursion of the same node
  • How and where to use it

1 – Define a tree

Tree

The picture shows a tree, often you will see them with the A node on top but whatever the orientation of the tree mine goes rightward.

I defined a tree as such (note that I say “I defined” and not “it is defined”, some terms may differ but the idea remains):

  • The tree is made of nodes
  • A node is a connection (vertex)
  • A node has relation with other nodes as parent/child
  • A node can only have one parent but can have many children
  • A node is connecting to its pairs via branches (edge)
  • Branches can only be one way while processing
  • The top node has no parent and is the starting node
  • A tree is made of generations, on the picture, A is first generation, B and C are second and so on.
  • A node cannot appear twice in a tree
  • We have a path defined by a start node and a target node
  • The start node is always the top node
  • The target node may be any node, including the start node or no node on the tree.

Tree could be more complex like having multiple parents and looping but we will not consider them in here. Just the simple one that can get you going right away.

2 – Defining DFS/BFS

So I mentioned those earlier and simply they are algorithms. They pretty much do the same thing but in a different way, ok that sounds wrong but hear me now.

Consider we are looking for a path between A and I, there is two ways we can consider the search, first we obviously start from A. Then we go down one generation and find B and C. This is when we decide if we should take care of B and then C or should we take care of B and go down the branch and once we are done with all related to B, then we do the same with C. Let me clarify that.

Let’s take a first case, we have A, is it the target node? Nope, so we find B and C as children, we store them in a collection. Now we take B out of the collection, is it the target node? Nope, so we find FGH as children and we store them in the collection. Now what do we do, are we going down the branch with F or are we finishing the generation taking care of C?

This is all the main difference between Breadth-First-Search and Depth-First-Search (as for implementation), if we do generation by generation we use BFS because we working in breadth of the tree, if we go down the branches we are using DFS because…because we go in depth first for our search.

But which one to choose? Which one is best? I leave the deep research to you and your friend google, this field is way too broad to be covered in one article. The main difference is that BFS will return the shortest path by generation while DFS will return a path which will be the first found.  I insist on the fact the shortest path found is only valid generation wise. BFS or DFS are not returning the shortest path based on weight, this would Dijkstra’ algorithm.

There are other more advanced differences like the fact that DFS is more memory efficient but we just draw the big lines for now.

Depending on the target, one will find the path faster than the other but when dealing with algorithm, we do not consider case by case but more likely a generic vision of it or even most likely the worst case. The notation used is the big O notation and in our case we have O(n) which means in the worst case we have to consider n iteration where n is the amount of element in the tree. Worst case being our target is the last node to be taken care. The best case would be 1 where start is target.

This is because those algorithms are considered Brute-Force, which means they try until they find just like when you try to remember your password until you hit the right one. This is what makes the difference with A* which uses Heuristic to consider and discard some paths.

What is the good point of those then? If a path exists, they will find it. This is applicable if the tree is finite, that is it does not have recursive nodes and it is made sure the tree has a final generation. If the tree can endlessly be extended then it is required to set a maximum amount of iteration or the search will end up with memory shortage. This is logical since the algorithm would keep on adding data without removing. In our case, the real advantage is that we control the paths since we are defining the connections manually.

Again, this article only focus on simple tree that are finite, no repetition, no recursion either, just a simple tree.

Below are the algorithms for DFS/BFS (that you are probably about to skip):

Node[]DFS(Node start, Node end)
   target as Node
   stack as Stack of Node
   if start is target then
      return array with start
   push children of start->stack
   while stack is not empty do
      pop out -> stack
      if node is target then
         target = node
         break loop
   push node children -> stack
   previous as Node
   previous = target
   parent as Node
   list as List of Node
   while parent is not null do
      add prev -> list
      prev = target
      parent = prev.parent
      add start -> list
   reverse list
   return list as array
Node[]BFS(Node start, Node end)
   target as Node
   queue as Queue of Node
   if start is target then
      return array with start
   enqueue start children -> queue
   while queue is not empty do
      dequeue -> node
      if node is target then
         target = node
         break loop
   enqueue node children -> queue
   previous as Node
   previous = target
   parent as Node
   list as List of Node
   while parent is not null do
      add previous -> list
      previous = target
      parent = previous.parent
      add start -> list
   reverse list
   return list

3 – Queue vs Stack

So we saw in the previous paragraph that both algorithms are pretty similar and mainly it is about container. What makes them so different? Well, it is their principle of functioning.

A queue is known as FIFO (First-In-First-Out), just like when you go queuing at the shop, the first who came in is the first who gets served, when one comes in, he joins at the end of the queue and wait for his turn to come once anyone who came before is done.

Queue are often used in networking, where data are flooding in, they are all enqueued on a buffer waiting in line to be treated in order.

Queue only allows  Enqueue or Dequeue

A stack is known as LIFO (Last-in-First-Out). It is the unfair one, the guy who came last is the first one to be served. Think of it like a pile of plates, you can add plates on top and take one on top but taking one at the bottom would require to first remove all others above (considering you don’t want to make a mess). This is what a stack is. You push data in and pop data out. For instance, if you push A and then B and then C you have a stack like this:

C

B

A

If you pop out a data, it can only be C. Should you be looking for A, you first need to pop C and then B and finally you get A.

Stack only allows Push or Pop

BFShttp---makeagif.com--media-3-23-2014-zC3txSDFShttp---makeagif.com--media-3-23-2014-pNa3rq

4 – Basic implementation

Since DFS and BFS are pretty similar in implementation, I will only focus on BFS and also because it minimizes the recursion issue.

First we need to define a node class. Well we saw that a node has a parent node and an array of child nodes. Easy then:

public class Node : MonoBehaviour
{
    public Node m_parent;
    public Node[] children;
}

Pretty simple isn’t it?

Now we need to populate that via the inspector. We first create a bunch of empty game objects and add the script. Then we start making the connections. I would recommend to place them in a tree like shape to ease the use. Also give them name like A-B-C where A is the top node and B-C the second generation and so on. Then simply start the drag and drop process of nodes into each other. You can use the picture at the beginning of the article for model (If you are a little familiar with what we are doing, you are probably getting nervous and ready to drop a complain comment, please read until the end before doing so).

And finally comes the implementation of the BFS:

public static class BFS
{
    public static Node[] BFSMethod(Node start, Node target)
    {
        Node final = null;
        // Check if starting node is the target node
        // return it in array if so
        if(start == target)
        {
            Node[] nodeArray = { start };
            return nodeArray;
        } 
        // Declare the queue
        Queue<Node>queue = new Queue<Node>();
        // Get all children of the first node
        Node[] children = start.children;
        // Enqueue them all in a loop
        foreach(Node node in children)
        {
            queue.Enqueue(node);
        }
        // while the queue is not empty
        while(queue.Count > 0)
        {
            // Get the first node of the queue
            Node n = queue.Dequeue();
            // Check if target
            if(n == target)
            {
                // Make him final node if target
                final = n;
                break;
            }
            Node[]c = n.children;
            foreach(Node nod in c)
            {
                queue.Enqueue(nod);
            }
        }
        // If final is null we could not find a path
        if(final == null)return null;
        // Get the parent node of the final node
        Node parent = final.parent;
        List<Node>list = new List<Node>();

        // While the parent is not the start node
        // This will go back up parent of each node
        // and then define the parent as current node
        while(parent != null)
        {
            list.Add(final);
            final = parent;
            parent = final.parent;
         }
         // We add the last two remaining ones
         list.Add(final);
         // The list is from target to start
         // We reverse it
         list.Reverse();
         // And convert it to array
         return list.ToArray();
    }
    return null;
}

This is nothing more than putting code on the algorithm.

               
Node final = null;
// Check if starting node is the target node
// return it in array if so
if(start == target)
{
    Node[] nodeArray = { start };
    return nodeArray;
}
// Declare the queue
Queue<Node>queue = new Queue<Node>();
// Get all children of the first node
Node[] children = start.children;
// Enqueue them all in a loop
foreach(Node node in children)
{
    queue.Enqueue(node);
}

We create a final Node reference where we will store our final node

You can test it creating empty game objects, add the Node script and start creating relation, make sure for the time being to avoid using twice the same node as parent and later on as child or you will see Unity starting and never ending the search.

Then we need a test class:

public class TestScript : MonoBehaviour 
{
    private void Start () 
    {
        // Start and target node
        Node start = GameObject.Find ("A").GetComponent<Node>();
        Node target = GameObject.Find ("E").GetComponent<Node>();
        // Call the method
        Node[] node = BFS.BFSMethod(start,target);
        // Print the path we found
        foreach(Node n in node)
        {
            Debug.Log (n.name);
        }
    }
}

And that will print your valid path.

But hold on what if we need to go from H to A for instance or from any node to any other? As it is this is only valid for starting from A, yes it is.

While describing a tree, I mentioned the branches can only be one way while processing. This is true while we are processing the path but this is not when we are defining the possible paths.

We will change a couple of things, first off, we do not need  the parent anymore because they will change all the time. So we will set them in the code as we go. Second, all nodes needs to also be connected to what was their parent and this one becomes a children as well. So looking at our tree A has B and C as children but B has A-D-E as children, A is added. This will allow us to go both directions.

So the longest part is to assign all possible paths up and down.

The code will just a little as well:

public static Node[] BFSMethod(Node start, Node target)
{
    Node final = null;
    if(start == target)
    {
        Node[] nodeArray = { start };
        return nodeArray;
    }
    // Set this one to null
    start.parent = null;
    Queue<Node>queue = new Queue<Node>();
    Node[] children = start.children;

    foreach(Node node in children)
    {
        // Set the parent for those node as the start node		
        node.parent = start;
        queue.Enqueue(node);
    }
    while(queue.Count > 0)
    {
        Node n = queue.Dequeue();
        if(n == target)
        {
            final = n;
            break;
        }
        Node[]c = n.children;
        foreach(Node nod in c)
        {
            if(nod.used){ continue; }
            // Set parent node
            nod.parent = n;
            queue.Enqueue(nod);
        }
    }
    // Same code below
}

And this is it, you can now find path from any node to any other node.

5 – Avoid recursion of same node

So remember we needed to avoid using the same node twice in our tree but what if we do?

So all we need is prevent the recursion simply by avoiding to use twice the same node.

public class Node:MonoBehaviour
{
    public Node parent;
    public Node[] children;
    public bool used = false;
}

I call the new variable used but you may see it as ‘visited’.

We just add that variable but we need to set it to false for all nodes in the first place or this is only valid for one round. So we need to keep a list of all nodes and set them all to false when triggering the method.

Tree1

You will notice that even though you are setting the system to be wrong, it may not affect the result, you could just notice that some repetition are happening. Our tree is small, so by the time the recursion is repeating itself the target is found. Consider if the target is 100 nodes down and the recursion happens early, you may create an endless loop.

So we add one variable to our node class and we check it in the DFSMethod but first we need a method to reset them all:

public static class BFS
{
    // static array, could also be non static.
    static Node[] nodes;
    // ctor, all nodes are found
    static BFS(){
        nodes = (Node[])MonoBehaviour.FindObjectsOfType(typeof(Node));
    }
    // Iterate and set
    static void ResetNode()
    {
        for(int i = 0 ;  i < nodes.Length; i++)
        {
            nodes[i].used = false;
        }
    }
}

And here comes the BFSMethod:

// while the queue is not empty
ResetNode();
// set used to true for starting node
start.used = true;
while(queue.Count > 0)
{
    // This will print the status of the queue
    foreach(Node nd in queue)
    { MonoBehaviour.print(nd.name);}
    MonoBehaviour.print("next");
    // Get the first node of the queue
    Node n = queue.Dequeue(); 
    n.used = true;
    // Check if target
    if(n == target)
    {
        final = n;
        break;
    }
    Node[]c = n.children;
    foreach(Node nod in c)
    {
        if(nod.used)continue; // Discard if already used
        nod.parent = n;
        queue.Enqueue(nod);
    }
}

And this is it for our basic BFS implementation.

6 – Where and how to use it?

So we have it all working but you would like an example you can copy paste and use (and then jump to UA because it does not work and you don’t know why since you just looked but not read the article…I know).

So the idea here is that we have a player, I will make him really simple and a chaser. But this chaser can only use the node of a tree.

First let’s define the player:

public class Player : MonoBehaviour 
{
    private Vector3 prevPos = Vector3.zero;
    public delegate void HandlerEvent();
    public static event HandlerEvent OnMove = new HandlerEvent(()=>{});
    private void Start () 
    {
        prevPos = transform.position;
    }
    private void Update () 
    {
        if(prevPos != transform.position){
            OnMove();
            prevPos = transform.position;
        }
     }
}

The whole point is the event (you can use GetComponent if you wish or you can read this article). Then it is just about checking if the player has moved and call the event incase of.

For the NPC, it is a little more complex (just a little). First we need to listen to the event for any player movement, then we get the path between the NPC and the player, we move there and finally we need to check for distance to know if we reach the target.

public class AiScript : MonoBehaviour 
{
    private Transform m_player;
    Node[]m_path = null;
    int i_index = 0;
    float f_range = 0.2f;
    float f_attackRange = 1f;
    float f_speed = 2f;
    private void Start () 
    {
        m_player = GameObject.Find("Player").GetComponent<Transform>();
        if(m_path == null) { AIMethod(); }
        Player.OnMove += AIMethod;
    } 
    private void Update () {
        if(i_index == -1 || i_index == m_path.Length){
            Vector3 direction = (m_player.position - transform.position);
            if(direction.sqrMagnitude > f_attackRange)
            {
                transform.Translate(direction.normalized * Time.deltaTime * f_speed);
            }
            else
            { 
                 Debug.Log("Attack");
            }
         else
         {
             Vector3 position = m_path[i_index].transform.position;
             Vector3 direction = (position - transform.position).normalized;
             transform.Translate(direction * Time.deltaTime * f_speed);
             if((m_player.position - transform.position).sqrMagnitude < f_attackRange)
             {
                 i_index = -1;
             }
             else if((position - transform.position).sqrMagnitude < f_range)
             {
                 i_index++;
                     //if(++index == path.Length)AIMethod();
             }
         }
    }

    private void AIMethod()
    {
        i_index = 0;
        Node start = GetClosestNode(transform.position);
        Node end = GetClosestNode(m_player.position);
        m_path = BFS.BFSMethod(start, end); 
    }
    private Node GetClosestNode(Vector3 position){
        Node [] node = BFS.Nodes;
        float distance = float.PositiveInfinity;
        Node target = null;
        for(int i = 0; i < node.Length; i++)
        {
            float dist = (position - node[i].transform.position).sqrMagnitude;
            if(dist < distance)
            {
                distance = dist;
                target = node[i];
            }
        }
        return target;
    }
}

Let’s look at the methods, the Start just finds the player, gets the first path and subscribe to the event from the player class.

private void Update () 
{
    if(i_index == -1 || i_index == m_path.Length)
    {
         Vector3 direction = (m_player.position - transform.position);
         if(direction.sqrMagnitude > f_attackRange)
         {
             transform.Translate(direction.normalized * Time.deltaTime * f_speed);	
         }
         else
         { 
             Debug.Log("Attack");
    }
    else
    {
        Vector3 position = m_path[i_index].transform.position;
        Vector3 direction = (position - transform.position).normalized;
        transform.Translate(direction * Time.deltaTime * f_speed);
        if((m_player.position - transform.position).sqrMagnitude < f_attackRange)
        {
            i_index = -1;
        }
        else if((position - transform.position).sqrMagnitude < f_range)
        {
            i_index++;
        }
    }
}

Update is asking a little more, first if we have reached the end of the path or the player we move towards the player. If close enough, we attack (with a printing, yep not so scary).

If we are still on the way, we get the direction to the next node and move there. If we are too close to the node we get the next one.

private void AIMethod()
{
    i_index = 0;
    Node start = GetClosestNode(transform.position);
    Node end = GetClosestNode(m_player.position);
    m_path = BFS.BFSMethod(start, end); 
}

Simple reset the index to 0, get the start node which is the closest node to the NPC and the end node which is the closest node to the player.

And then we get our path.

I won’t go through GetClosestNode since it does what it says.

And this is it. Now you can add a two cubes to your scene, one with the AiScript and the other with the Player script that you name “Player”. Run the game and move the player in the Scene view (or set an input system to move it in the Game View).

Try to stay in the tree as we did not define any way to prevent the NPC from leaving the tree. Also, this is all too basic as it moves with Transform, but this was not the point here (the BFS was, wasn’t it?) so I kept it really simple.

Conclusion

You may be looking for a project to download butthere is none. The reason is simple, what would you learn if you just download and try and use??

Think for instance of a 2D platformer, you have one NPC that is able to go up and down platform to chase the player, how about placing nodes all over the place, then when the NPC needs to chase you, find the closest node to the NPC and the closest node to the player and run your BFSMethod. The return array will guide your NPC to your player. Obviously, as you are constantly moving it needs to be updated frequently but as I said, this is just a base for you to start with. Hopefully that would guide you down the path of pathfinding.

Also, those are heavily used in networking, when a connection between two routers needs to be done for instance. Obviously they use a way more advance version as they need to consider if the router is available, which path is more efficient and so on but the base is here.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s