January 4, 2019
Tactics Movement – AI
AI with A* (A Star)
Youtube – Unity Tutorial – Tactics Movement – Part 6
By: Game Programming Academy
This part of the tutorial implements A* for use as the AI for NPCs. Most tactics games would generally involve some type of action phase, but this tutorial finishes with just getting the movement setup.
NOTES
The tutorial’s breakdown of A*:
- processing the open list by finding the lowest f cost
- put it in the closed list
- checking for the target
- then process adjacency and see if tile is in open list, closed list, or neither (in which case it is added)
Like in many tactics games, the NPCs will still show all of their selectable locations to move before actually selecting one.
For checking distance, tutorial just uses “Vector3.Distance”, but they suggest using the squared magnitude value since it is easier computing because Distance uses square root. Used for setting up simple AI searching algorithm to find the closest thing. It is a simple foreach loop that goes through an array of gameobjects checking the distance between the gameobject itself and each of those individual objects. The distance as well as the object is stored, so whenever a new lower distance is found, the object will be replaced, otherwise, the same object remains there (as that indicates the currently checked object is farther away).
The tutorial tries to keep the TacticsMove script as a generalized class that holds all the helper methods for use in the other classes.
A* uses two lists: an open list and a closed list. A* can also use a priority queue, but C# doesn’t have a built in priority queue. The open list is any tile that has not been processed, and the closed list is those that have been processed. It will finish when the target tile is added to the closed list.
Since we’re using tiles, we could use the “Manhattan Distance” instead. Manhattan distance may work better particularly with arrays though so tutorial sticks with Euclidean distance.
Since we’re using pathing to walk up to a unit, not on top of, the tutorial just decides to follow the A* path and then stop one node before the end (which would be where the target unit is located).
TERMINOLOGY
Manhattan Distance:The sum of the absolute differences of the Cartesian coordinates of two points. This represents the straight line nature of moving around on tiles in this case which is a grid-like layout.
Priority Queue: Like a normal queue but each element within has a priority value associated with it.
TODO
Suggested by the tutorial, program NPC for case where there is no target in range.