Pathfinding for tile maps

Unity already comes with a pretty awesome feature which can be used for path finding and obstacle avoidance. I'm of course referring to the Nav Mesh and its other components.

However, I found that not very useful when it comes to 2D and tile map kind of games. It is of course possible to use it if you decide to utilize quads and planes, but I wanted to implement my own path finding system.

It turns out, it is not really hard, especially when there are algorithms out there that have been tested and used for years. For this project, I will show you how I wrote my "own version" of the Dijkstra algorithms. No, not the guy from The Witcher 3.

I will not post the whole project code as it is extensive and rather messy at this stage, however, I will put the main functions and classes needed.

First of all, we need a map, a simple grid of objects and our player of course.
In my experiment I created a small "level editor" by coding a custom editor so it would be easier to layout an awesome map.

And this is the awesome map itself:

Awesome indeed.

As you can see, I have 3 types of tiles: the "grass" tile, green color, the "sand" tile, yellow(ish) color and the "wall" tile, grey color.

The reason is to show how smart this algorithm can be. Every type of tile has a "cost": the grass tile costs 1 to move in to, the sand tile 15 and the wall is pretty much set to infinity.

When calculating the path you will see that the player (the little capsule on the bottom left corner) will attempt to avoid the sand when possible as it is "too expensive" to move in to. In simple words, it will try to find the least expensive path, which is not necessarily the shortest.

Here's a picture which illustrates this:

The player is trying to get to the tile in the red circle. It could very well cross the "sand field" by walking straight down south, instead, the calculated path would rather go around it. Each sand tile costs 15 action points (let's call them such) to move in to, and the player would have 5 sand tiles in front of him to reach the target tile, which makes a total of 75. By going around it as shown by the line, he would have to traverse 10 grass tiles, which cost 1 AP each, for a total of 10. So, 10 APs are much cheaper than 75.

The first class we need is the Node class:

public class Node  {

    public List<Node> tileNeighbors;
    public Map mapReference;

    public int x, y;

    public float distanceFromSource;
    public Node previousNode;

    public Node()
    {
        tileNeighbors = new List<Node>();
  //Debug.Log ("List initialized");
    }

    public float DistanceTo(Node n)
    {
        float d = 0;
        Vector3 current = mapReference.GetTilePositionAt(x, y);
        Vector3 to = mapReference.GetTilePositionAt(n.x, n.y);
        d = Vector2.Distance(current, to);

        return d;
    
    }


}

This class represents each tile on the map. The most important parameters in this class are: the list of nodes, which will contain all the neighbors tiles, the float distanceFromSource, which is the tile's physical distance form the source and a reference to the previous Node with the shortest path.

As part of the Dijkstra algorithm, we need to generate a so called "graph" with this Node class.
A graph is nothing but a two dimensional array of nodes.

  void GeneratePathGraph()
    {

        graph = new Node[mapWidth, mapHeight];

        //Populate neighbours list
        for (int x = 0; x < mapWidth; x++)
        {
            for (int y = 0; y < mapHeight; y++)
            {
                graph[x, y] = new Node();
                graph[x, y].mapReference = this;
                graph[x, y].x = x;
                graph[x, y].y = y;


            
            }
        }

  for (int x = 0; x < mapWidth; x++) {
   for (int y = 0; y < mapHeight; y++) {

    if (x > 0) {
     graph [x, y].tileNeighbors.Add (graph [x - 1, y]);

     //Diagonals
     /*
     if (y < mapHeight - 1) {
      graph [x, y].neighbours.Add (graph [x-1, y + 1]);
     }
     if (y > 0) {
      graph [x, y].neighbours.Add (graph [x-1, y - 1]);
     }*/
    }
    if (x < mapWidth - 1) {
     graph [x, y].tileNeighbors.Add (graph [x + 1, y]);

     //Diagonals
     /*
     if (y < mapHeight - 1) {
      graph [x, y].neighbours.Add (graph [x+1, y + 1]);
     }
     if (y > 0) {
      graph [x, y].neighbours.Add (graph [x+1, y - 1]);
     }*/
    }
    if (y > 0) {
     graph [x, y].tileNeighbors.Add (graph [x, y - 1]);
    }
    if (y < mapHeight - 1) {
     graph [x, y].tileNeighbors.Add (graph [x, y + 1]);
    }
   }
  }     
    
    }

With this function I generate this array and populate it with nodes. Also, through a second iteration, I populate the list of neighbors of each node with the neighbors tiles. As you can see, I commented out the diagonal tiles, and that is simply because I do not want diagonal movement. If you wish to have it, simply uncomment those lines.

Now, to the path generating function.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

public void GeneratePath() { List<Node> uncheckedNodes = new List<Node>(); List<Node> currentPath = new List<Node>(); Node sourceNode = graph[unitToMove.GetComponent<Unit>().currentTileX, unitToMove.GetComponent<Unit>().currentTileY]; Node targetNode = graph[targetX,targetY]; sourceNode.distanceFromSource = 0; sourceNode.previousNode = null; foreach (Node n in graph) { if (n != sourceNode) { n.distanceFromSource = Mathf.Infinity; n.previousNode = null; } uncheckedNodes.Add (n); } while (uncheckedNodes.Count > 0) { Node nodeWithMinDistance = GetNodeWithMinDistance (uncheckedNodes); if (nodeWithMinDistance == targetNode) break; uncheckedNodes.Remove (nodeWithMinDistance); foreach (Node n in nodeWithMinDistance.tileNeighbors) { float distance = nodeWithMinDistance.distanceFromSource + n.DistanceTo(nodeWithMinDistance)+ GetTileMovementCost (n.x, n.y); if (distance < n.distanceFromSource) { n.distanceFromSource = distance; n.previousNode = nodeWithMinDistance; } } } // Close while if (targetNode.previousNode == null) { Debug.Log ("No Path foud"); line.SetVertexCount (0); } else { Node current = targetNode; while (current != null) { currentPath.Add (current); current = current.previousNode; } currentPath.Reverse (); unitToMove.GetComponent<Unit> ().currentPath = currentPath; DrawPath (currentPath); } }

Declare 2 lists of nodes, one for the unvisited nodes and the other one which will hold the generated path.

After that, create 2 node, the source node and the target node. The source node coordinates are taken from the Unit script, which is attached to the player. The script simply raycast downwards and detect the tile underneath and retrieves its coordinates, so it is constantly updated.

Similar thing for the target node, this time the mouse will update the coordinates, again, by raycast.

We then initialize the source node: its distance from the source is 0 (that node IS the source) and there's no previous node before it.

Next, we initialize every node in the our graph array: set their distance to infinity and the previous node reference to null. Also, add every node to the list of unvisited nodes.

On line 28 we start iterating inside this list. We create a temporary node object (nodeWithMinDistance ) and we set it to the node in the list with the least distance from the source. That's what the method GetNodeWithMinDistance(...) does, simply iterates inside the list and return the one with the minimum distance. In the first iteration, it should return the source node, as it has a distance of 0 and all the others have infinity.

This is the point where we check if we have reached our target node, in that case we break out of the while loop.

Also, very impostant, we remove the returned node from the list of unvisited nodes.

If not, we iterate inside the neighbor list of the returned node.

For each neighbr node we assign it a value to the  distanceFromSource parameter. This value, temporarily stored in the distance parameter, is calculated by adding the value of the same parameter of the current node (the one containing the neighbor list we are iterating in. In the first iteration of the while loop, is the source node), added to the physical distance between the tiles and also the movement cost.

Here is what's happening:

Let's assume that we are considering diagonals too. Starting from the source node on the bottom left, we have 3 neigbors tiles. The one above will have a distance from the source of 2. That is because the distance of the source node (which is 0) is added to the physical distance of the 2 tiles (which is 1 in this case as the tiles are nothing but 1x1 cubes) and its movement cost is added as well, which is 1 (because it's a grass tile). The total is 2.

For the diagonal tile, the distance is 2.4 because the physical distance between that tile and the source node is 1.4 (square root of 2 basically), plus its movement cost of course.

It is important to consider the physical distance for diagonal tiles for one reason: if diagonal tiles are considered at the same distance as adjacent tiles, this could happen:

Going frm tile A to tile B, the path generated has no reason to prefer adjacent tile to diagonal tiles, as they are mathematically at the same distance. So rather than going through a straight line, it might decide to act like in the picture above.

By calculating the physical distance of each tile, diagonals will have a value of distance from the source a little higher, which makes them a less favorable path to follow.

Continuing with our script, if the distance calculated is smaller than the current distance, that means that a shorter path has been found and the distanceFromSource parameter is updated.

This process will continue for each node until we reach the target node.

When we do, the program will exit the while loop.

At this point, if the previousNode of the target node is null means that no path was found, so the while loop iterated through the whole list of nodes without finding a route.

If not, we simply populate the currentPath list by grabbing the previousNode node in each previousNode reference of each node starting from the target node. This is a linked list technique, you can find plenty of tutorials on it online.

At this point the currentPath list contains all the nodes, from target to source. After reversing it, we can assign it to the player (called unitToMove) so it has a path to follow and we can draw the path using line renderers.

It is important to kow that with this system, the player will still be able to travers WALL tiles if no other path is found. That is because the value assigned is not (obviously) infinity, so it can be calculated. To avoid that we can simply detect if the path goes through tiles of type wall and break it when it happens.

Nonetheless, this is one of the ways we can implement path finding for tile based games.

Example scene here.

Navigation and click-to-move

Navigation is one of the awesome features of the engine. It provides a sort of basic AI for your objects which allows them to navigate the scene autonomously avoiding obstacles.

Let's see how we can achieve that, by making move a character on a plane using the mouse and making sure he doesn't try to run through walls.

For this simple projects I used some of the assets found in the StandardAsset by UnityTechnologies, downloadable for free on the Asset Store.

Let's start by placing our floor in the scene by draggin the prefab FloorPrototype64x01x64. For simplicity, we will rename it Floor. Let's set its layer mask to a new mask called Ground. In order to use the navigaition system, we need to tell Unity that this object is Static. More specifically, Navigation Static. We can achieve this by simply click on the Static label on the top right (Fig 1).

Fig 1

We can now place some obstacles in the scene, can can either drag in some prefabs from the standard asset or simply create cubes. Let's also set them to static. Finally, let's drag in the character model from the folder Characters -> ThirdPersonCharacters -> Prefabs ->ThirdPersonController.

My scene looks like this:

Now, it is time to bake it. Yes, bake it.

In order to get the navigation system to work we have to bake the scene. To open the navigation window we go to Window -> Navigation. (Fig 2)

Fig 2

Once the navigation window opens, we select the bake tab. (Fig 3)

Fig  3

Now, I could go on and explain all the parameters in the window, but I really believe that the best way to understand what they do is simply to play around with them. For the moment we leave them as they are, we proceed by pressing the button Bake, placed to the bottom right of the window. (Fig 4)

At this point magic will happen.

In the editor, the scene will look like this:

The blue area represents the "walkable" part of the scene, while the "sort of greyd out" parts are considered obstacles. During the baking process, Unity will check all the objects in the scene which are tagged Static and will make them obstacles and, therefore, to be avoided by any NavMeshagent navigating the scene.

We can now remove the 2 scripts attached to our player character (ThirdPersonUserControl and ThirdPersonCharacter) as we are going to write a new script to move the character via mouse clicking. Also, we need to add the component NavMeshAgent to our model, which is the component that will drive our player through the scene.

Let's create a new C# script and call it PlayerMovement. I will noe show you the code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

public class PlayerMovement : MonoBehaviour { Animator anim; NavMeshAgent nma; Ray ray; RaycastHit hit; float speed = 0.5f; // Use this for initialization void Start () { anim = GetComponent<Animator> (); nma = GetComponent<NavMeshAgent> (); nma.speed = speed; } // Update is called once per frame void Update () { ray = Camera.main.ScreenPointToRay (Input.mousePosition); RayCastFromCamera (); Vector3 proj = Vector3.Project (nma.desiredVelocity, transform.forward); anim.SetFloat ("Forward", proj.magnitude); } void RayCastFromCamera() { if (Physics.Raycast (ray, out hit, 500, LayerMask.GetMask ("Ground"))) { if (Input.GetMouseButtonDown (0)) { nma.SetDestination (hit.point); nma.Resume (); } } } }

Le's break it down.

We get all our component references (Animator and NavMeshAgent).

We then create a Ray variable and a RayCastHit variable. If you are not sure how to use Raycasting check the unity official documentation. I might make a tutorial about it if required.

In the Start method we initialize all our variables.

In the Update method, we perform a Raycast to check where in the scene world we are pointing with the mouse, based on the ray created from the camera to the world space (Line 22).

If we hit anything that is on the LayerMask Ground (Line 34) and we click the left mouse button (Line 36), we pass to the NavMeshAget the collision point.

Now, for this particular example the animation might behave strangley and that is because I'm not setting the rotation animation in order to keep the script simple. If you are interested, please let me know, I will make a tutorial on it.

The character movement is controlled by the animator, and its speed is determined by the animation speed (we are using RootMotion). Therefore, the higher value we feed into the Forward variable of the animator, the fastest the character will run. To get a smooth movement, we use Vector Projection.

In simple words, by calculating the magnitude of the Vector Projection of the NavMeshAgent desired velocity and the character transform forward we get a value for the speed that goes from 0 (when the NavMeshAgent destination is very close to the agent itseld) to its maximum possible value (the NavMeshAgent speed variable, in our case, 0.5). I set the speed to 0.5 so we always get a walking animation as the running animation can create complication unless we adjust other parameters (like animation rotation). That is simply because the Animator is using blend trees and needs extra parameters to allow for smooth animations. I will make a tutorial eventually on how to achieve that using this technique.

We calculate the projection using the NavMeshAgent desired velocity, as it is the velocity the agent wants to head owards (therefore, towards the destination) and it will account for obstacle avoidance. If we had used NavMeshAgent.Destination we would se the character attempting to walk towards the target ignoring obstacles on the path.

By the way, if you would like to know more about Vector Projection and NavMeshAgent movement I strongly suggest you to go and check the "Stealth" complete project tutorial on the official Unity website.

However, for our purpose this is enough. We now have a character that will move in the direction of our clicking point and avoiding obstacles.

A few things to remember:

- Every time we place or remove obstacles in the scene, we need to rebake the scene.
- It is important to mark as Static all the objects that we want to be avoided by our character in the scene
- It is possible to create "bridges" to walk over areas that are not navigable using OfMeshLink. (a more in depth topic for another tutorial).
- Notice how, when you play the scene, if we click outside the "level", the character will get to the closest point and then stop. There's a way to avoid tha by using the method hasPath() of the NavMeshAgent. If the method returns a false, we ca just set the speed to 0 or stop the agent so the character will not move.

Well, that's about it.

An example scene here. I took advantage of the Stecil buffer shaders I wrote in the previous posts, so we will be able to see the character behind the walls. To make it stand out, the player model is rendered in a single color, in this case, green.