Recently I’ve found a nice piece of pseudo code for implementing A Star after searching through a few lesser or incorrect pseudo code passages:

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 |
clear open and closed let s be start node let e be end node s.loc = startloc s.g = 0 s.h = Cost( s, e ) push s to open while open not empty q = Pop lowest f in open if q == e traverse backpath of q.parent return success for each successor p g = q.g + GridCost( q, p ) if ( p is open or closed ) if ( p.g <= g ) continue p.parent = q p.g = g p.h = Cost( p, e ) p.f = g + p.h if ( p is closed ) p.closed = false if ( p is open ) re-sort open else push p to open return failure |

And here is the Pop function pseudo code (written by me, so it probably has a small error here or there):

1 2 3 4 |
find node with lowest f in open list remove node from open list add node to closed list return node |

My favorite thing about the pseudo code is that the closed list can be implemented with just a flag. The open list becomes the most complicated part of the algorithm. Should the open list be a sorted array, an unsorted array, a binary heap? The answer largely depends on much more memory you need to traverse.

If a small portion of memory needs to be searched all dynamic memory can be allocated up-front on one shot. Otherwise bits of memory should probably be allocated up-front, and more as necessary during the algorithms run.

Just yesterday I implemented AStar in C where my full header file looked like:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#pragma once struct iv2 { int x; int y; }; struct astar_data { iv2 start; iv2 end; int path_count; int* path; }; int AStar( astar_data* data ); |

In my internal C file I only have < 150 lines of code, including some file-scope variables and math functions. Implementation was nearly a one to one transcription of the above pseudo code (so those who are recursion impaired like myself shouldn’t have any problems). This style may not be thread-safe, but hey, most AI related coded can only be done in serial anyway. My grid size was maxed out at 20×15, so pre-allocating memory for your entire search area may not be so practical as it was for me.

Still, I hope this post can provide some bits of intuition that are useful to someone.