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:
