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