November 20, 2019
A* Tutorial Series
Pt. 02 – Node Grid
A* Pathfinding (E02: node grid)
By: Sebastian Lague
Intro:
This started by creating the overall Node class to contain valuable information for each individual node, and the Grid class that would be dealing with the overall grid of all the nodes (I rename this to AGrid to avoid errors in Unity).
Node
For now, this simply holds a bool walkable, which represents whether this node contains an obstacle or not, and a Vector3 worldPosition, which contains data on its Unity real world position.
AGrid
This class has a couple parameters that influence the coverage and resolution of the overall A* system. The gridWorldSize represents the two dimensions covered by the entire grid (so 30, 30 will cover a 30 by 30 area in Unity units). The nodeRadius is half the dimension of a node square, which will be used to fill the entire grid. The lower the nodeRadius, the more nodes (so higher resolution, but more computing cost).
The intial setup is a lot of work that simply breaks down whatever the overall area being covered by the grid into int size chunks to use as indices to work with a 2D array containing all the nodes. The NodeFromWorldPoint method is also created, which is a nice method that takes in a Vector3 value and returns the node encompassing that point. I like the extra step of clamping the values here to reduce possible errors in the future.
Unity Feature Notes:
Clamp Example:
// Clamped to prevent values from going out of bounds (will never be less than 0 or greater than 1)percentX = Mathf.Clamp01(percentX);percentY = Mathf.Clamp01(percentY);
Mathf.Clamp01 clamps a value within the bounds of 0 and 1. This percent value should never be outside of those for the purposes of the grid anyway (they help determine basically what percentage away a node is on the x and y axes separately relative to the bottom left node). So in error cases, this will simply give a node that is at least on the border of the grid.
The CreateGrid method in the AGrid script uses a Physics.CheckSphere method to determine if a node is traversable or not. This simply creates a collision sphere of a determined radius that returns information on anything it collides with.
Gizmos:
They use the DrawWireCube Gizmos, which just lets you create a wire cube outline with defined dimensions. This is very nifty for conveying the general area covered by something visually in your editor.
Warning:
Unity had an issue with naming the one script “Grid”, as they already something named Grid built into the system. It gave me a warning that I would not be able to use components with this object. Just to make sure I did not run into any future issues, I renamed it “AGrid”.