a base algorithm<\/a>:<\/p>\n\r\nOPEN = priority queue containing START\r\nCLOSED = empty set\r\nwhile lowest rank in OPEN is not the GOAL:\r\n current = remove lowest rank item from OPEN\r\n add current to CLOSED\r\n for neighbors of current:\r\n cost = g(current) + movementcost(current, neighbor)\r\n if neighbor in OPEN and cost less than g(neighbor):\r\n remove neighbor from OPEN, because new path is better\r\n if neighbor in CLOSED and cost less than g(neighbor): **\r\n remove neighbor from CLOSED\r\n if neighbor not in OPEN and neighbor not in CLOSED:\r\n set g(neighbor) to cost\r\n add neighbor to OPEN\r\n set priority queue rank to g(neighbor) + h(neighbor)\r\n set neighbor's parent to current\r\n\r\nreconstruct reverse path from goal to start\r\nby following parent pointers\r\n<\/pre>\nImplementing this in C# … in Unity<\/h2>\n
First of all: Unity is broken in how it uses some of the C# syntax<\/strong>. Without going into detail, some valid C# will corrupt when used in Unity – most obviously here: multi-dimensional arrays. You can patch Unity to fix this yourself, but it’s non-trivial. Instead, simply re-implement with crappier, lower-level structures (sad, but practical).<\/p>\nSecondly: Microsoft’s C#\/.NET standard library has a “SortedList” built-in, but IMHO it’s misnamed: you can only have one element for each position (that’s a sorted Map, or a Set-sorted List, not a sorted List). It’s the wrong structure for our case here, although you CAN customize it to work, by making each “item” a List, and moving nodes from list to list. Ugh. Complicated. Again: sad, but practical. Personally I made my own SortedList that does what it pretends to do ;).<\/p>\n
Make a Node class<\/h3>\n
Probably something you already have in your game, e.g.:<\/p>\n
[csharp]
\npublic class Node
\n{
\npublic int x, int y;
\n}
\n[\/csharp]<\/p>\n
And a graph \/ grid class<\/h3>\n
e.g.<\/p>\n
[csharp]
\npublic class Grid
\n{
\npublic Node[] allNodes;
\npublic int nodesAcross, nodesDown; \/\/ needed to workaround Unity bugs
\npublic Node NodeAt( int x, int y ) \/\/ needed to workaround Unity bugs
\n{
\nreturn allNodes[ x + y*nodesAcross];
\n}
\npublic void SetNodeAt( int x, int y, Node n ) \/\/ needed to workaround Unity bugs
\n{
\nallNodes[ x + y*nodesAcross] = n;
\n}
\n[\/csharp]<\/p>\n
Make your own SortedList<\/h3>\n
Fairly easy, but I screwed this up first time around, because I was unfamiliar with some neat tricks C# does internally with foreach loops. I doubt you’ll have problems. For A*, you only need to make a class with these methods:<\/p>\n
[csharp]
\npublic class MySortedList<T> where T: class
\n{
\n\tpublic MySortedList();
\n\tpublic int Count();
\n\tpublic T GetFirst();
\n\tpublic T RemoveFirst();
\n\tpublic void RemoveItem( T victimItem );
\n\tpublic bool Contains( T searchItem );
\n\tpublic int AddWithValue( T newItem, float newValue );
\n}
\n[\/csharp]<\/p>\n
Sanity-checking your algorithm<\/h3>\n
This is a data-sensitive algorithm, and we’ve created some custom data-structures (OK, not dangerous), and … a custom container (hmm: dangerous! Easy to get wrong in subtle ways).<\/p>\n
I strongly recommend you write unit tests for MySortedList. I didn’t (fool! I haven’t adopted a good UnitTesting framework in Unity yet), and regretted it. In particular, focus on:<\/p>\n
\n- Testing the “Contains” check is accurate\n
- Testing the “Remove” methods actually remove items\n<\/ol>\n
…miss either of those and A-star will go into an infinite loop, because it keeps adding more nodes to the list. Especially subtle (and an obvious gotcha): the Contains check, and how it checks for equality — make sure you implemented Equals and GetHashcode on your custom classes!<\/p>\n
Debugging your algorithm<\/h2>\n
Now to the fun stuff. This is a DATA HEAVY algorithm: in real-game use, it will be processing many thousands of nodes on each run, and up to tens of thousands of edges. Debugging that is hell. Don’t do it.<\/p>\n
Instead, your first thought should be:<\/p>\n
\nHow can I make a visualization for this, so that debugging vast datasets becomes quick and easy?\n<\/p><\/blockquote>\n
My route:<\/p>\n
\n- Make a Component for “Calculate A Path”\n
\n- Put start node in there, end node\n
- Write an Editor \/ CustomEditor class for this that adds a button “Calculate Path”\n<\/ol>\n
- A* outputs a “Path” object\n
- My “Calculate Path” takes the output\n
\n- creates a new GameObject\n
- Adds that as a child\n
- Attaches a “PathVisualizer” script\/component\n<\/ol>\n
- PathVisualizer has an OnGizmos() implementation that:\n
\n- Draws a cube at every node in the path\n
- Draws a different coloured cube at start and end nodes\n
- Draws lines between each node showing the order \/ direction of travel along the path\n<\/ol>\n<\/ol>\n
Things to note here:<\/p>\n
\n- Because each path is added to a GameObject, you can tweak your A* implementation, re-run it in Editor, and compare the two output paths, see how well it’s changed from your previous attempt. Awesome!\n
- I didn’t want the overhead of making my Nodes or Paths be Unity MonoBehaviours; no need: I made a visualization-behaviour instead that holds a reference to “Path that you want me to visualize”\n<\/ul>\n
See image at top of post for my first-draft simple visualization.<\/p>\n
Visualize the Graph, and the Costs<\/h3>\n
I also did some work on visualizing the graph itself:<\/p>\n
![\"Screen](\"http:\/\/t-machine.org\/wp-content\/uploads\/Screen-Shot-2014-08-10-at-20.00.49.png\")
<\/p>\n
And the Costs (note: I have implemented my Costs to be bidirectional: it is “cheap” to move downhill, and “expensive” to move uphill. Not by same amount! So each edge has two colours, one for uphill cost, one for downhill):<\/p>\n
![\"Screen](\"http:\/\/t-machine.org\/wp-content\/uploads\/Screen-Shot-2014-08-10-at-19.59.53.png\")
<\/p>\n
Making it less painful to run<\/h3>\n
Unoptimized, your A* algorithm should run in a small fraction of a second, for any grid up to a few thousand nodes. It’s practically instant.<\/p>\n
HOWEVER … when you’ve got bugs, A* tends to go into infinite loops and hang Unity (Unity sadly has ZERO PROTECTION against scripts doing this).<\/p>\n
So, for practical purposes, you want to turn your calculation into a Co-Routine, and put some in-editor info that lets you see if its gone wrong. I decided to add progress bars for how large the Open list and Closed list were. I knew the total number of nodes, and that the two lists couldn’t get larger than that, so I could fill these up:<\/p>\n
![\"Screen](\"http:\/\/t-machine.org\/wp-content\/uploads\/Screen-Shot-2014-08-10-at-20.05.21.png\")
<\/p>\n
Co-routines in Editor<\/h4>\n
Sadly, although Unity allows co-routines in the Editor (Unity’s staff have used them for the recent Editor features in 4.5), you’re not allowed to use them yourself.<\/p>\n
…but the coroutine implementation in Unity is super-simple, and quite easy to write yourself. So, using something like this short class that is a full implementation<\/a> you add that feature for yourself.<\/p>\nI used the same idea (add your own callback to the “update” list, and run the IEnumerator manually), but added some bits about repainting the GUI frequently (not too frequently) and finessed some other minor features.<\/p>\n
Assertions and Exceptions<\/h2>\n
Let me revisit an earlier point:<\/p>\n
\nThis is a DATA HEAVY algorithm: in real-game use, it will be processing many thousands of nodes on each run, and up to tens of thousands of edges. Debugging that is hell. Don’t do it.\n<\/p><\/blockquote>\n
Assertions are your friend. Most AAA pro game developers love them, especially on Console (they’re great for saving you from writing Unit Tests for a machine that doesn’t have spare memory\/performance to run Unit Tests).<\/p>\n
I screwed up my implementation. With a little help from Amit, I added the following assertions to my code:<\/p>\n
\n- Never accept a negative Cost to move from one node to another\n
\n- This should be impossible. Even if you are doing “weird and cool things” with your Costs in your game, you do NOT want this.\n
- …because A* can and will<\/strong> abuse this, running back and forth over your “negative” edge, getting “free energy!” to reduce its total path cost\n
- You MIGHT want to allow zero-cost edges, sometimes – e.g. a teleporter – but be very careful: they can allow the same ping-ponging, infinite-loop problem\n
- In general: Assert whenever you read an edge-cost and it’s “<= 0f\"\n<\/ol>\n
- Last line of Amit’s core loop marks the “current node” as the neighbour’s predecessor. DO NOT ALLOW THIS IF that node is already pointing to the neighbour!\n
\n- Again: this should never happen, if the algorithm is running correctly. It’s absolutely wrong!\n
- (zero or negative costs would allow it to happen)\n
- But worse: don’t allow a chain of links, where one item in the chain is repeated: this becomes an infinite loop later on when you try to process the path\n
- I added a brutal “when adding a node to end of chain, check it’s not anywhere in preceding links in chain” assertion\n<\/ol>\n
- Never allow the open list to have more than the total number of nodes\n
\n- Shouldn’t be possible! Can’t have duplicate nodes!\n<\/ol>\n
- Ditto with the closed list (I actually implemented closed list as a Set. But if you have a bug in your .Equals method, you could still break the standard-library’s Set implementation!)\n<\/ol>\n","protected":false},"excerpt":{"rendered":"
I needed fast, efficient, … but powerful, adaptable … pathfinding for my hobby project. My minions have to fly, walk, crawl, teleport, tunnel their way across a procedural landscape. Getting to that point has been tricky, but the journey’s been interesting. We want something that intelligently routes creatures around obstacles, and picks “shallow” routes instead […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9,20,67,69],"tags":[],"_links":{"self":[{"href":"http:\/\/new.t-machine.org\/index.php\/wp-json\/wp\/v2\/posts\/3302"}],"collection":[{"href":"http:\/\/new.t-machine.org\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/new.t-machine.org\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/new.t-machine.org\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/new.t-machine.org\/index.php\/wp-json\/wp\/v2\/comments?post=3302"}],"version-history":[{"count":7,"href":"http:\/\/new.t-machine.org\/index.php\/wp-json\/wp\/v2\/posts\/3302\/revisions"}],"predecessor-version":[{"id":3313,"href":"http:\/\/new.t-machine.org\/index.php\/wp-json\/wp\/v2\/posts\/3302\/revisions\/3313"}],"wp:attachment":[{"href":"http:\/\/new.t-machine.org\/index.php\/wp-json\/wp\/v2\/media?parent=3302"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/new.t-machine.org\/index.php\/wp-json\/wp\/v2\/categories?post=3302"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/new.t-machine.org\/index.php\/wp-json\/wp\/v2\/tags?post=3302"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
![\"Screen](\"http:\/\/t-machine.org\/wp-content\/uploads\/Screen-Shot-2014-08-10-at-20.09.36.png\")
<\/p>\n