I recently wrote some grid graph based path finding code, and NavMesh for Unity in C#. The first few posts will cover Node sorting, Grid Graph building and pathfinding, followed by building a NavMesh and Octree for more complicated pathfinding solutions. Below are some of the great resources I used to learn the basics. If you are new to path finding I’d recommend visiting the below sites:
1) http://www.policyalmanac.org/games/aStarTutorial.htm
2) Interactive grid visually demonstrating most of the popular algorithms
3) Amit / Red Blog Game Guides
4) AIgameDev.com Fast Pathfinding via Symmetry Breaking
I won’t cover the core concepts in this post. They are covered far better than I could ever hope to in the above links. To validate my understanding of the basic concepts I wrote a quick Manhattan based A* console app. Shown on the right. Randomly generated obstacles (#’s) and starting at the bottom found my way to the top. Now to move onto something more complex: a GG in 3d.
GG based Path finding in 3D is the same as 2d. There are just more possible node connections. The configuration I used is displayed to the left.
For path finding we need a few key items. An object to represent our nodes which holds their heuristic cost, path to cost and total cost. This object must also record who it’s ‘parent’ is. Next we need a container to handle an ‘Open list’ and a ‘Closed list’ of nodes and finally a method that processes nodes until a path is discovered, or it finds none exist.
To begin i’ll start with the open container (for the closed I used a hashset.) Unfortunately the Mono Develop library does not contain a sorted set. So I used a sorted dictionary and made a container that queues nodes based on their total cost. This container needs to perform four essential functions.
1) it needs to handle the sorting of nodes by their total cost (heuristic + path to this node). To accomplish this I used a sorted dictionary with an Enqueu method.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
public void Enqueue(Node toEnqueue) { //no key exists for this value we must create a key and queue if (!theDic.TryGetValue(toEnqueue.totalCost, out aQueue)) { //came back null create a new Queue for this slot aQueue = new Queue<Node>(); aQueue.Enqueue(toEnqueue); theDic.Add(toEnqueue.totalCost, aQueue); } //queue already exists inside the dictionary append to exisiting key else { aQueue.Enqueue(toEnqueue); } } |
2) It needs to return the cheapest node
|
1 2 3 4 5 6 7 8 9 10 11 12 |
/// <summary> /// Dequeues the lowest costing node and returns it. /// </summary> /// <returns></returns> public Node Dequeue() { var nodeQueue= theDic[theDic.Keys.Min()]; Node toReturn = nodeQueue.Dequeue(); //check if nothing is left if so destroy this key if (nodeQueue.Count == 0) { theDic.Remove(theDic.Keys.Min()); } return toReturn; } |
3) The OpenList has to have a way to check how many nodes it holds encase no valid path exists.
|
1 2 3 4 |
/// <summary> /// How many Node values are Enqueue /// </summary> public int Count { get { return theDic.Count; } private set { } } |
4) a check to see if our list already contains a node
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
/// <summary> /// Does the queue contain this node? /// </summary> /// <param name="toCheck"></param> /// <returns></returns> public bool Contains(Node toCheck) { //See if there is a key containing this value if (!theDic.TryGetValue(toCheck.totalCost, out aQueue)) { return false; } //Key exists does its queue contain this node if (aQueue.Contains(toCheck)) { return true; } return false; } |
As one block of code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
/// <summary> /// A Priority based sorted queue for nodes ordered by their 'totalValue' property /// Would use a reg sortedset if this existed in Monodevelop /// </summary> class CheapestNodeQueue { Queue<Node> aQueue; private SortedDictionary<int, Queue<Node>> theDic = new SortedDictionary<int, Queue<Node>>(); public void Enqueue(Node toEnqueue) { //no key exists for this value we must create a key and queue if (!theDic.TryGetValue(toEnqueue.totalCost, out aQueue)) { //came back null create a new Queue for this slot aQueue = new Queue<Node>(); aQueue.Enqueue(toEnqueue); theDic.Add(toEnqueue.totalCost, aQueue); } //queue already exists inside the dictionary append to exisiting key else { aQueue.Enqueue(toEnqueue); } } /// <summary> /// Dequeues the lowest costing node and returns it. /// </summary> /// <returns></returns> public Node Dequeue() { var nodeQueue= theDic[theDic.Keys.Min()]; Node toReturn = nodeQueue.Dequeue(); //check if nothing is left if so destroy this key if (pair.Value.Count == 0) { theDic.Remove(theDic.Keys.Min()); } return toReturn; } /// <summary> /// How many Node values are Enqueue /// </summary> public int Count { get { return theDic.Count; } private set { } } /// <summary> /// Does the queue contain this node? /// </summary> /// <param name="toCheck"></param> /// <returns></returns> public bool Contains(Node toCheck) { //See if there is a key containing this value if (!theDic.TryGetValue(toCheck.totalCost, out aQueue)) { return false; } //Key exists does its queue contain this node if (aQueue.Contains(toCheck)) { return true; } return false; } } |
In the next post I’ll cover my Node class and put everything together. Comments, suggestions or questions are always appreciated. Hopefully these posts are of some help to others looking to learn and implement path finding.
-John