I’ve been trying to read and understand as much as I can about how to implement an A* pathfinding algorithm. I’ve looked at about 5 tutorials so far, and each of them gives a good general overview of the algorithm, but there’s one crucial part (at the beginning of the algorithm) that I don’t know how to do, and that’s find the 8 adjacent squares next to my starting square/cell/node.
I have a 2d grid, arranged in a normal grid style such that each cell is the same distance apart. For instance, a grid that’s 10 x 10 squares.
Most tutorials say something like this:
“Look at all the reachable or walkable squares adjacent to the starting point, ignoring squares with walls, water, or other illegal terrain. Add them to the open list, too.”
That’s great, but what’s a good way to find the grid cells adjacent to a given cell? Do people do a distance check between every cell in the master cell array? Should I use a binary heap to find the adjacent nodes? Should I iterate through my grid cell array and somehow find the adjacent nodes to every cell at the start of the game? How do people find adjacent nodes in a simple 2d grid?
In addition, what should I hold these cells in: a built-in array, a list, a dictionary, an index, a struct or something else?
There are many ways to do this. Stuff like this is generally easier if you think about your algorithm from the start, and set up your data structures such that they work nicely with your algorithm by storing data in a way that implicitly tells you as much of what you need to know as possible.
For instance, what I’d probably do here is set up a 2D array of references and fill it according to the scene position of the grid cells. Then it’s super easy to find the 8 adjacent cells for any cell (x, y), because it’s simply all other cells which fall within (x-1, y-1) and (x+1, y+1). In other words, if I were you I’d probably set up my “master cell array” such that I knew which cells were adjacent just by looking at the array. (Also, even if you do have to update stuff dynamically, doing a sort on an appropriately styled data collection is most likely going to be faster than doing distance checks between each pair and so on.)
That’s sounds like a good idea. In my case right now though, I need more help with the actual coding of this, than the concept of it. What you said sounds like what Aron Granberg said, in that he uses simple offsets (i.e. (x+1, y+1)) when getting the adjacent cells for his gridgraph.
All I know how to do in order to get the (x+1, y+1) cell of the cell I’m considering is to iterate through my master cell array and for every single cell check to see if it matches (x+1, y+1) or (x-1, y+1), etc…for each of the 8 cells surrounding a cell, such as this:
//Find the cell closest to a given unit and return the closest cell
//This function returns the cell closest to a given Vector3 position
ClosestCell(manager.listAllUnits[a].transform.position);
for(var b = 0; b < cellArray.Length; b++) {
//Find the eight cells around the closest cell and add them to an array
if(cellArray[b].position.x == closestCell.position.x + 1 cellArray[b].position.z == closestCell.position.z) {
neighborArray.Add(cellArray[b]);
}
if(cellArray[b].position.x == closestCell.position.x + 1 cellArray[b].position.z == closestCell.position.z + 1) {
neighborArray.Add(cellArray[b]);
}
if(cellArray[b].position.x == closestCell.position.x cellArray[b].position.z == closestCell.position.z + 1) {
neighborArray.Add(cellArray[b]);
}
if(cellArray[b].position.x == closestCell.position.x - 1 cellArray[b].position.z == closestCell.position.z + 1) {
neighborArray.Add(cellArray[b]);
}
if(cellArray[b].position.x == closestCell.position.x - 1 cellArray[b].position.z == closestCell.position.z) {
neighborArray.Add(cellArray[b]);
}
if(cellArray[b].position.x == closestCell.position.x - 1 cellArray[b].position.z == closestCell.position.z - 1) {
neighborArray.Add(cellArray[b]);
}
if(cellArray[b].position.x == closestCell.position.x cellArray[b].position.z == closestCell.position.z - 1) {
neighborArray.Add(cellArray[b]);
}
if(cellArray[b].position.x == closestCell.position.x + 1 cellArray[b].position.z == closestCell.position.z - 1) {
neighborArray.Add(cellArray[b]);
}
}
Obviously, it’s a bunch of “if” statements, which doesn’t look pretty, but would it be equivalent speed-wise to what you suggested? Would it be anything like what you are saying?
Practically (and programmatically) speaking, what would you change with my code? I guess, I kind of want some real code to look at, or some pseudo-code in order to study what you’re saying, or to be able to grasp what the concept is.
**Note: the cellArray is an array of cell classes, and the cell class contains variables for position, velocity, density, etc…
If you use a uniform grid of cells, it’s better to store them in a multidimensional array like angrypenguin said.
so if your current cell is cellArray[4,3] you would find the adjacent 8 cells by looking at cellArray[4-1, 3-1], cellArray[4+1, 3+1], cellArray[4+1, 3], etc.
If however your cell layout is not uniform, it’s probably better to store each adjacent cell in an array for each cell.
something like cellArray[×].adjacentCells[a].
I am using a uniform grid of cells. And I am using a multidimensional array of classes (I’m coding with javascript/unityscript) to set up my grid initially. Each “cell” isn’t just a position, it’s an entire class, which does include a position variable. Here is the problem I’m having with your answers though, you say
. But I know WHAT cells I am supposed to look at, I just don’t know HOW to look at them.
So my question isn’t what cells should I look at, it’s HOW should I look at them via programming? Everyone says “look at these cells”… I don’t know how though. Later on in your answer you say “it’s probably better to store each adjacent cell”…HOW do I find and store each adjacent cell? lol.
If I sound annoyed, I’m not. I’m just trying to communicate more effectively what exactly I’m having trouble with.
I appreciate the help so far, but I feel as if an answer to my question has not been fully communicated yet.
Here is a code segment showing how I’m setting up my grid, in case that might help:
function CreateGrid () {
for(var x = 0; x < sizeOfGrid.x; x++) {
//Add "nodesize" amount in addition to the +1 every loop iteration
x += nodeSize;
for(var z = 0; z < sizeOfGrid.z; z++) {
z += nodeSize;
//Instantiate a gameobject at each cells position that helps visually identify the location of each node
Instantiate(cellPrefab, new Vector3(x, .5, z), Quaternion.identity);
//The CellData script is not attached to any gameobject, but is simply in the assets folder.
//It is a class unto itself, simply by being a Javascript script. Each separate script in Javascript is treated as a class automatically by Unity.
var tempClass = new CellData();//Create a new instance of the CellData class
tempClass.position = Vector3(x,0,z);//Set this unique class instance's position variable to a value
jsArray.Add(tempClass);
cellArray = jsArray.ToBuiltin(CellData) as CellData[];
}
}
}
Sorry for the overdue response.
You say you have a multidimensional array where you store them, but I could not see this in your code.
There’s good information on these on here:
Say you have your multidimensional array of CellData objects:
var cellArray : CellData[,] = new CellData[5,5];
You then create the cells and put them in the array.
for(var x = 0; x < sizeOfGrid.x; x++) {
for(var z = 0; z < sizeOfGrid.z; z++) {
cellArray [x,y] = new CellData();
cellArray[x,y].arrayPosition = new Vector2(x,y); // perhaps tell the cell where in the array it is.
cellArray[x,y].worldCoordinates = new Vector3(x*someSpacingVariable, 0.5, y*someSpacingVariable); // store the world position
}
}
So, when you’ve created your array and start examining stuff;
Say we’re looking at the CellData in cellArray[2,2], the adjacent CellData to the right of this one is at cellArray[3,2], just +1 on the X index.
So when your looking at a specific CellData at index X,Y in the array you can find the CellData adjacent to the one at X,Y by just adding/subtracting 1 from the X and Y indices.
Just want to extend the last answer on how to find neighbors in a double for loop then.
Lets say we are looking a cell [5, 7], and we can get the cells i and j position in the array from cell.i and cell.j. Then:
//Look around cell at position cell.j and cell.j, from -1 to +1 in each direction
for(int x = cell.i - 1; x < cell.i+2; x++)
{
for(int y = cell.j -1; y < cell.j+2; y++)
{
//Check if we look at "our" own cell, and skip it if we do
if(x == cell.i y == cell.j)
continue;
//Now do what ever checks you need to do on cell[x, y] here.
}
}
Also remember to include checks such that if x < 0 AND x > maxXValue, then skip the neighbor check (out of the array index)