Multi-Grid Graph Navigation Tutorial

This tutorial was originally posted to Namespace studio's dev blog, April 21, 2016

The A* pathfinding project is quite powerful, and allows multiple grid graphs out of the box, which is quite handy considering the requirements of our game. However, I didn’t find that many helpful resources for using grid graphs in the way we intended. What we wanted to do was move our AI from graph to graph as needed, without the graphs having to overlap. Essentially, we wanted our AI to go to the destination, even if the AI and the destination are one two different graphs. We ended up with a method to do just that, which I’ve documented here.

First off, our goal is to get an AI to move from its start position to a target position, even if the two positions are on different graphs. Lets start by doing a bit of housekeeping. Make sure to import the A* pathfinding project package into your project, and make a new scene.

Setting the Scene

As you can see, I’ve divided the level into four quadrants, with quadrant one (grey) positioned at (5,0,5) so that it’s bottom left corner is at the origin. This will be important later. In addition I’ve thrown some boxes around to give the AI obstacles to deal with. I’ve also made an empty game object and parented all of the level objects to it. This is just to make the scene view easier to navigate, and is entirely optional.

Making a Seeker

Next up is to make an AI to move around. Start by making a capsule object in the scene, naming it ‘Seeker’, and adding the Pathfinding > Seeker component to it from the add component menu. Also, go ahead and make an AstarAI.cs file in the assets inspector. Because we’re focusing on how to move from grid to grid instead of the intricacies of pathfinding, I’m going to use the “getting started” movement code instead of anything fancy. code is from here: How to setup the A* Pathfinding Project in a 2D Unity environment

For now, we’ll just copy paste this code into our AstarAI.cs file, and then add the script to our seeker object. After adding the script, create an empty game object called “target” and assign it to the AstarAI’s target field.

Generating Paths

Now that we have our seeker setup, lets make some paths for it to follow! If we tried to run the program now, we’ll get the error “There are no graphs in the scene.” To give the seeker something to follow, we have to first make an empty game object, and then add an Astar Path script to it. This script gives us a bunch of setting for generating grid graphs, and you should see one in the scene already, centered on our empty object.

Set Up the First Grid Graph

Lets get the Graph all sorted out. On the Astar Path script, click “Add New Graph” and then “Grid Graph,” then click the name of the resulting graph to change it from grid graph to Graph1. Leave the width, depth, node size and aspect ratio all at their defaults, and we should have a graph capable of perfectly covering one of our quadrants. So the first step is make sure the center of the graph lines up with the center of the plane that makes up quadrant one. In this case, we set the center to (5, 1, 5), so that our AstarAI script will keep the capsule up out of the ground. The only other thing we modify are the collision settings, which we modify by unchecking the Height testing bool and setting the mask for collision testing to everything.

Ogres are like Onions (Using Layers to Get Scanning Right)

If you click scan at the bottom of the Astar Path script, the script will generate a new grid graph for you, indicating the unavailable nodes with red cubes, and showing the connections of available nodes. Right away you’ll notice that the seeker capsule has caused surrounding nodes to be marked as impassible. To fix this, create a new layer called “AI” and assign the seeker capsule to it. Then, go back and uncheck the AI layer from the grid graph’s collision mask dropdown. Now after scanning the Seeker capsule shouldn’t affect the graph!

A Quick Test

If we’ve done everything right, putting the target on the same grid graph as the AI will cause the Seeker capsule to move to the target when we run the program. (Notice that I’ve changed the AstarAI’s next waypoint distance to 0.5 to make it get closer to the target before calling path complete).

Adding the Other Graphs

Now that we have that working, lets set up the other graphs! These graphs are set up in the same way as the first one, with only the center point changing. Here, you can see which graphs I’ve assigned to which quadrants. It’s crucially important to remember which graphs go with which quadrants, although you do not necessarily have to mimic my set up. If you do a different setup, make sure you keep track of what graph goes to what quadrant.

Trying to Move Between Graphs

As you can see, we never get our seeker moving because the path that we ask for comes back with an error. Right now we’re limited to only having the target on the same grid as our seeker.

Checkpoint

So this is all well and good, but we’ve basically just made the quick start tutorial with portions of the level that we can’t access. Weren’t we supposed to get the AI to move from grid to grid? To figure out how to get the AI to transfer grids, lets do some experiments with graph1 only. Specifically, I want to know what happens when our target or our Seeker aren’t on the grid.

Experiment 1 – Target off the grid

When we ask the seeker to go to a destination that is off the grid graph, it appears to find the closest node it can, and go to there, then stop.

Experiment 2 – Seeker Off the Grid

When the seeker itself is off of the grid, we can see that it moves to the nearest node to it, and then continues on to the target.

Method to the Madness

The purpose of these experiments was to show how we’re going to get the transfer from grid to grid to work. Basically, we want the seeker to move as far as possible on the grid that it starts in. when it gets to the edge of it’s graph, we want to create a new path using the grid that our seeker is next to. Because the seeker will move to the closest possible node on its graph even if the target is off grid, (or on a different grid) we don’t need to do any special waypoint calculations. Likewise, because the Seeker will move to a target even if it is off of the grid, we don’t need any special waypoint calculations for the new path either. All we have to figure out is which grid graph we should be looking at. It turns out that there is another implementation of the seeker.startPath command that takes a fourth argument. This argument is a bitmask that tells the pathfinder which graph(s) to check. Perfect!

A Bit More About Bit Masks

As we saw earlier, the grid graphs in A* pathfinding project aren’t smart enough to connect the dots themselves, so we have to tell the pathfinder exactly which graph we want to look at. The way we do this is through bit masks. There are many tutorials on bit masks, so I’m just going to give a brief explanation using only the parts that we need. Bit masks are a series of bits used to select, in this case, different graphs. Imagine a series of switches, where each switch is either 0 (off) or 1 (on). Each switch corresponds to a specific graph. So, because we have 4 graphs, our bit mask looks like this: 0000 where the rightmost 0 is the switch for graph 1, second from the right is graph 2, and so on. If I want to say “only look at graphs 1 and 3, and ignore the rest, then the bit mask I would create is: 0101. However, there isn’t a bit mask type with unity. Instead, you’ll notice that the bit mask argument in the startPath function is an int! This is because c# takes the integer and turns it into a string of binary when needed. So, instead of writing 0101, we would just input “5” into the parameter to get the same effect. Now, that’s a bit messy, so instead, we’ll use bitwise operations. The expression 1 << 2 takes the number 1 (binary 0001) and shifts it to the left by 2 spaces, resulting in a binary of 0100. in other words, 1 << 2 = 4.

The Graph Mask

The pathfinding project stores an array of all of the graphs in a scene. To tell the pathfinding project that we want the first graph in it’s array, we would use the operation 1 << 0 to get the bit mask for that graph. To find just the second graph we would use the operation 1 << 1, and so on. So, if we keep track of what order our graphs were created in, we can write a simple function to get the bit mask for a graph, given the bit offset for that graph.

public int GetGraphBitmask(int bitOffset) {return 1 << bitOffset; }

Finding the Graph Mask on the Fly

So, that’s a nifty way to get the bit mask that we need, but what about the graph offset? Well, we need to store it somewhere, so we can feed it to the function later. Also, we need a way of telling which graph our seeker is currently on. The easiest way to do that would be to store the bit offset for a graph in a dictionary, with the position of that graph as the key. However, we also need a way to relate the seeker’s position and the graph that they’re in. Rather than looking through the entire array of graphs, getting the center of each one, and finding which one is the closest to the seeker (although that would work, it would be slow) lets instead abstract the game world into a top down grid. For this to work we have several requirements. Each grid graph has to be the same size, and square, so that we end up with a perfectly square grid where each cell is the size of a grid graph. These are required because we need to be able to easily convert an object’s position in world coordinates into a cell coordinate. If we can easily convert an objects position into cell coordinates, then we can use the cell co-ordinates as the keys for our bitOffset dictionary, and thus easily pick out which graph the seeker should be looking at at any given position. Let’s also require, for the sake of simplicity, that cells have their origin at the bottom left. For us what this means is an object is in the cell(0,0) if that object has an x and z from (0,0), all the way to an x and z of (10,10). If an object has an x and z of (11, 5), then that object is in cell(1,0) and so on. basically, we divide the world into 10 x 10 cells, along the x/z plain. To get an object’s position in cell coordinates, all we have to do is take their position, divide by 10, and then round down (or cast to an integer).

The Levelmanager

This is all a bit much to do with just the AstarAI, so we’re going to make a level manager script to hold the logic to find the cell coordinates of an object, as well as the dictionary containing the offsets for the graphs, or in other words, a dictionary that tells us which graph goes to which cell. Go ahead and create a LevelManager.cs script, and attach it to a new, empty game object in the scene. Then, open the script in monodevelop so we can get scripting!

The One and Only LevelManager

Because the level manager is a unique object, we really only want there to be one of it at any one time. To do this, we add the following lines:

this code makes sure that there is only one levelManager at a time, and that we can access that instance from anywhere with LevelManager.instance.

Now is a good time to add some fields to store the level size and the dictionary of bitOffsets, so add the following lines above the Awake() function:

Finding Cell Coordinates

Now, you may notice that CellCoord doesn’t exist. I found it helpful to make a new struct to hold the x and z coordinates of the cells, So let’s fix those errors by making the CellCoord data type. I’m going to make it right in the level manager file, just because I don’t feel like making an extra file just to contain a struct definition that’s so small. Type the following above the class definition of LevelManager:

The serializable attribute is so that this datatype will be editable in the unity editor.

Finding Cell Coordinates Cont.

Since we now have a Data type to represent cell coords, lets make a function to convert a Vector3 into a cell coordinate object. As mentioned before, this is simply a matter of dividing the relevant position coordinate by our cell size, and then casting to an int (which will cut off any pesky trailing decimals.) Add the following code below the Awake() function:

I’ve made the function static so that we can access it from anywhere (specifically the AstarAI script) using LevelManager.GetCellCoord(), and without having to store a reference to the level manager object.

Getting the bitOffset

The next thing we need to do is return a bitOffset to help us find a specific grid graph, when given a specific cell coordinate. We could access the dictionary with LevelManager.instance.graphMaskOffsets[cellCoord] but that’s a little unwieldy. Instead, lets make another static function to access the dictionary internally, so our AstarAI can get access smoothly.

Adding Offsets in the Editor

The final thing we have to do for the level manager is to make it possible to add bitOffsets to the dictionary from the editor. Note that dictionaries do not show up in the inspector, so instead we’ll make an array with all of the relevant information, and then transfer that information to the dictionary during the awake function. As before, I’m going to create a new data type, which is simply the combination of our CellCoord data type and an integer representing the graph’s index in the graph array (i.e. the bitOffset). Also as before, I’m just going to add it to the level manager file instead of making a new file just for it. Add the following code above the LevelManager class definition:

Then add the following code above the Awake() function:

Finally, add this for loop to the last part of the Awake() function:

Adding the Graph Data in the Inspector

We can now open the levelManager script in the inspector, and add our cell definitions. For example, if graph2 is in the bottom right quadrant, then we can make a new element on the gridGraphBitOffsets array, set the cell coords to (1,0), and the bitOffset to 1. Do this for each graph, and all of our cells will be defined.

Setting the Graph from cellCoord

With the levelManager complete, we can focus on the AstarAI. Basically, besides moving from point A to point B, the only other job our AI will have is to handle the transition from one grid to another. To start with, if we give our AI a cell coord, we need to be able to get the graph associated with that cell. To do this, open the AstarAI script, and add the following code below the fixedUpdate function:

You’ll notice that this is the equation from the bit mask section. What this function does is return a bit mask that specifies the graph for the given cellCoord.

Setting the Graph from Vector3

It will also be useful to add an implementation of the GetGraphMask function that finds the mask directly from the given position. Add the following code below the previous function:

Getting the Start Graph

Now that we have a way to get the graph mask, we can change the startPath() call in the Start() function by adding a call to GetGraphMask() as the final argument. after modification, the startPath call should look like this:

Progress

If we run the program now, the seeker should move towards the target no matter where that target is, but it will stop when it reaches the end of the graph that it starts on. Here is where we handle the transition.

Getting the Next Graph

We need a function to tell us which graph we should look at next, given our current position in cell coordinates, and the target position in world coordinates. The following function looks a little complicated, but the steps are relatively simple. To find out where we should go, we first take the target’s position in world coordinates, and subtract our current position in world coordinates to get a vector pointing from us to the target. Next, we check the magnitudes of the different components of the vector to see if the x or the z is larger (the y axis we don’t care about in this case). If the x axis is larger we add an offset to our current cell position in the direction of the sign in the x axis. e.g. if the x axis has a larger magnitude and was -3, then we add -1 to the x value of our current cell position. If the z value is higher, we do the same, but for the z value of our current cell position. We then return the value of our current cell position plus the offset to get the coordinates of the cell that our seeker AI should transfer to next. Add the following code below the previous functions:

Getting a New Path

Of course, this function is useless without calling it! To tell the AI to keep going, we’ll need to tell it to start another path, with the next graph selected after it gets to the edge of it’s current graph. To do this all we have to do is check the AI’s position against the distance to the next waypoint plus an offset (so it doesn’t get confused when we actually finish our path). If we’re still far away from our target and we’ve reached the end of our path, then we have to keep going! You’ll also have to add a private bool to check to see if we’re already trying to calculate a path. If your computer is slow in finding a path, we could accidentally trigger another search, which would override the path you’re already looking for, and our AI would go nowhere. Add the following code above the start function:

Also, we’ll have to change the OnPathComplete function to use the new bool. Change the OnPathComplete function to look like the following:

Finally, we can update the way we determine we have reached the end of the path, in order to accommodate multiple grids.

Add the following code to the fixedUpdate call, in the body of the current waypoint check. After modifying, the body of the current waypoint check should look like this:

Putting it All Together

Now, if everything is working properly, we should be able to see our seeker move to our target position regardless of which graph it’s on when we run the scene!

You’ll notice that the seeker always moves to the closes node to the target that it is currently on before moving to the next graph. This can give some weird behavior specifically because we don’t have our GetNextCellCoord set up to do diagonal offsets. Just something to keep in mind!