A Star

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:

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

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:

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.

TwitterRedditFacebookShare

4 thoughts on “A Star

  1. Steven

    Randy,

    In your A* pseudo code where does p.closed get set to true? I feel it should be before the successors are searched?

    Reply
    1. Randy Gaul Post author

      Steven,

      Yeah looks like you’re spot on; before the successors are searched. If you want to see the current implementation I have it’s here in src/astar.cpp. To warn you it contains a good amount of game-specific code and small modifications. Though, you can look through the changelog if you really want to see the first version that’s nearly one-to-one with the above pseudo code. It looks like I was setting the closed flag inside of the Pop function. I made this article based off of the AStar article from Game Programming Gems, if you wanted to read that as well. I think the Gems article explained a bit more about the Pop function. In their article they had a binary heap, other people online used a sorted array, but I just went with a regular non-sorted array.

      I’ll try adding Pop to the pseudo code…

      Hope that helps!

      Reply
      1. Steven

        Randy,

        That matches my code – I used the same reference material a few years ago writing mine, but i was curious if you had some other ‘trick’ to it.

        Best,

        Steven

        Reply

Leave a Reply

Your email address will not be published. Required fields are marked *