A-Star (A*) Algorithm in Python – Update January 25th, 2010

Since there have been many requests over the years for the source code referenced in my A-Star (A*) Algorithm post, I decided to share it. I did a bit of refactoring too, as I have learned some neat things about Python in the years since I wrote that post, like list comprehensions.

A cautionary note to undergrad CS students (who I can only assume are the requestors): CS professors are pretty good at catching cheaters, so learn from others’ code, but write your own.

Source: astar.py

2 comments on “A-Star (A*) Algorithm in Python – Update

  1. pablo says:

    hello, I am triying to use your code to learn about a* algorithm but a dont know how to use it. Can yo explain me how to intruduce a new map with obstacles, a start point and a finish point?

    pd: Sorry about my english, im from guatemala C.A

  2. Jack says:

    Hi,
    Your post is very helpful. I have checked your implementation of A* for puzzle. It looks that in some cases it finds suboptimal path, e.g. for the puzzle: [1, 6, 4, 8, 7, 0, 3, 2, 5] gives 23 hops, but it should be less.
    regards, Jack

Leave a Reply

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>