AGrid System Breakdown for A* Pathfinding

May 5, 2020

A* Pathfinding

AGrid System Breakdown

AGrid class:
- this class sets up the initial node grid

1) Determining grid size and resolution
- Input: nodeRadius - parameter to create a nodeDiameter (which is the "real world" size of the nodes)
- Input: GridWorldSize - determines an x and y distance for the grid to cover (in real world units)
- broken into GridWorldSizeX and GridWorldSizeY
- Output: number of nodes (node resolution) - System uses these GridWorldSize values and the nodeDiameter to determine how many nodes it needs to create to fill this area
- i.e. Inputs: GridWorldSize x = 10; GridWorldSize y = 10; nodeRadius = 1
- Output: Creates grid that is 5 nodes (2 diameter size) by 5 nodes (2 diameter size)
- Note: diameter size is a bit misleading since they aren't circle shaped by any means; most dimensions are used in a more rectangular fashion (so diameter is more like edge length)

2) Positioning Nodes in Real World Space
- The transform of the empty object this AGrid class is attached to is used as the central real world location for the grid
- This value is then used to find the bottom left corner location which everything builds off of
- Vector3 worldBottomLeft = transform.position - Vector3.right * gridWorldSize.x / 2 - Vector3.forward * gridWorldSize.y / 2;
- starting at the central point, this moves to point which is half the total width in the x direction, then down half the total height in the z direction
- The first node created goes at this bottom left corner, then it places nodes that are spaced nodeDiameter apart from this location continually until it fills the grid
- It fills in an entire column, then moves to the next one across the grid
- Finally, each node starts at some arbitrarily placed y-value for its elevation and casts a ray until it hits the terrain
- Each node uses this information to finally place itself at the height where its ray intersects the terrain


3) Adding Values to the Nodes
a) Raycast Values
- During the raycasting process, the node can pick up on either: obstacles or terrain types
- Obstacles: tells the node it is unwalkable, so it will be ignored for A* pathfinding logic
- Terrain Type: Can add inherent excess movement costs based on the type of terrain to that node in particular
b) Applying Influence
- The AGrid class receives information on any Influence class objects placed in the area
- Using this information, it then calls the ApplyInfluence method of all the Influence objects found to add their values to the proper nodes

4) Blending Values
- *Excess that may not be needed
- There is a step to blend the movement penalty costs over the terrain, which basically keeps hard value borders from existing
- i.e. If Nodes have penalty value "A" near Nodes of value "B", the nodes in between will vary between the ranges of A and B
- This currently only applies to movement penalties, but could be extended to other values if it seems useful