pygame is
Python
Simple DirectMedia Layer
 
 
pygame.org is
Site Swing
AStar

AStar - 1.1

John Eriksson (wmjoers)

Tags:

Description

A simple python implementation of the A* (a-star) path finding algorithm. The source contains the algorithm and a simple proof-of-concept example using pygame.

The code only implements support for a plain square map but it should be fairly simple to implement support for any map type. If you have any questions regarding this don't hesitate to ask.

Example instructions:
Edit the map by first selecting a tile type. The blocking tiles can not be passed. The walkable tiles has values from 1-4 (also known as move cost) where 1 represents easy terrain (low cost) and 4 is rough terrain (high cost). You can also place the start and ending points. When you are finished editing press the Find path button and the AStar algorithm will try to find the path with the lowest cost. If any path is found it will be displayed with white lines.

Changes

Added some very needed optimization and modified the printout in the example to show execution time.

Links

Home Page: http://arainyday.se
Source: http://arainyday.se/projects/python/AStar/AStar_v1.1.tar.gz

Screenshot


click to view original size

Releases

AStar - 1.1 - Feb 10, 2006
AStar - 1.0 - Feb 8, 2006

Pygame.org account Comments

If you wish to leave a comment with your pygame.org account, please sign in first.

June 21, 2008 3:55am - John Eriksson - nickname: (wmjoers)
Thanks for your comments *smile*

This implementation wasn't designed for speed nor was it designed to be used by 2d grids only. The main idea behind this example is to present an A* implementaton that can be used for every kind of map.

I'll try to explain it a little:

The files:
AStar.py - Contains the A* logic.
AStarExample.py - Is a simple example on how to implement the AStar logic.

Generic A* classes:
Path - Represents the solution.
Node - This represents a generic node in a generic map.
AStar - The actual A* algorithm. Requiers a maphandler. The only public method is findPath (resturns a Path object).

2D grid map specific classes:
SQ_Location - Represents a location in a uniform 2d grid map.
SQ_MapHandler - Contains the actual map information and logic to determine adjacent nodes etc.

To add support for other types of maps you'll just have to implement a specific Location and MapHandler class.
May 6, 2008 11:40pm - Shaon - nickname: (shaon) - 2/5
There are many programmers out there who are limited in their game design prowess because sadly they are not a level to implement the A* algorithm, but if they can get a path-finding algorithm it saves them a lot of time and makes them more productive. I wasn't sure if this was actually suppose to be usable by new programmers, as I found it hard to implement in my game. I felt a strong urge to criticize it below, and possibly I might post up my version of A* which is much faster than this one.

A very good example case, though I felt the actual A* could've been much improved. The time it takes to find a path on such a small map is too long. Generally it took about 15 ms on my Core 2 Duo to go from one side to the other, If I put blocks there, it ended up sometimes taking up 246 ms. A terrible speed for games where 25 fps is a minimum (that means you have 40 ms to work with for your game).

Also the system in which you took your data was awkward. Your whole grid was set in a single dimension array, when good programming practice says that a 2d map should in either a 2d array or held in dictionary. If it suppose to be usable to other programmers, it is a bit pricey for them to have to convert their 2d/dictionary grid system into a sigle dimension list.

At first I thought you were forcing a single dimension array in order to keep them in a binary heap stack, but that turned out to be false, since your search system for "best node" was a for loop rather than the implementing heap functions.

The commenting wasn't very helpful either. You had few classes, and upon first look, I couldn't link up where your code started and ended since each object kept calling on other objects. I nice logic paragraph at the start might have been useful.

In general, this could be much more improved in terms of efficiency, and the overall system in which data is handled. Commenting was also not very good. It is however nonetheless a decent implementation of A*.

I think I will post my version as well, but I'm going to make it so that the whole think is packaged into a simple class for the people who want path finding with out caring how it works.
August 23, 2006 11:44am - Michael Brunton-Spall - nickname: (mibgames)
oops, that previous comment was me, I forgot to sign in
August 23, 2006 11:43am - Anonymous - nickname: () - 4/5
Excellent AStar implementation, but I can't seem to find anywhere to report a bug.
It fails to find the correct path when end and beginning are the same, instead it always takes the first open node and then comes back, creating a path with start, 1 node, and end in it.
I've coded round it at my end for now, as I couldn't figure a neat way of doing that check in the code.
spotlight

 
our projects
pygame.org welcomes all python game, art, music, sound, video and multimedia projects. If they use pygame or not.
 
recent releases
Apr 21, 2014


Apr 19, 2014

Apr 16, 2014

Apr 13, 2014

Apr 9, 2014

Mar 18, 2014


Mar 15, 2014


Mar 14, 2014

Mar 13, 2014

... more!
 
for pygame related questions, comments, and suggestions, please see help (lists, irc)