Game AI Unity A* Path-finding
- Nolan Roher
- Apr 30, 2019
- 2 min read
Building off the same project I referenced before in an earlier post, I incorporated A* path-finding into the project to allow the enemies to find the best route to the player before they begin to chase after them. Once again, here's the GitHub Link with an explanation below: https://github.com/maniacalspy/GameAIFinal/blob/master/Assets/AStarNav.cs
The A* path-finding works off of a grid component that is located in another script and will be elaborated on once I update the repository to include the correct versions of the files. For now, the simplest explanation is that the Unity scene has a uniform grid across it that consists of nodes, each node either is a wall or isn't, they keep track of few scores (the distance of the path traveled from the start, distance to the end in a straight line, and those two scores combined), and it remembers which node came before it in the path. Wall nodes can't be traveled across. Currently, the main purpose of the script is to call FindPath when an agent wants to find the best path from point A to point B. The script finds the nodes closest to the starting point and the end point and begins to find the path between them, it begins with the starting node and looks at all the neighboring nodes to figure out which has the lowest overall score (for the starting node this generally means which one is closest to the end), and puts them all in a list of nodes that haven't been explored. Then, it moves on to the node that hasn't been explored in the list with the lowest score, then it removes the node it just moved to from the list and puts it into a separate list of explored nodes. After moving to the next node, it checks all the neighboring nodes again, any nodes that it hasn't seen before get put into the open node list, and any nodes in the open node list get updated if it turns out that this path leads to a lower score (this usually means you found a faster way to get to this node than you had before). The script repeats this process until it either runs out of nodes to explore, or it finds its way to the ending node. Then after it finds the ending node, it retraces the path by referring to the parent of each node until the starting node has been found again, putting each node into a separate list along the way. The script then returns that list which now contains the final path to the destination to the agent, who then moves along that path until they get to the end point.


Comments