Unity : A* Part 1

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

2dExampleI 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.

3dDirectionsGG 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.

2) It needs to return the cheapest node

3) The OpenList has to have a way to check how many nodes it holds encase no valid path exists.

4) a check to see if our list already contains a node

As one block of code:

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.


Leave a Reply

Your email address will not be published.