Re: [pygame] Does anyone have a python implementation of A*?

[Magnus Lie Hetland <magnus@hetland.org>]

John Eikenberry <jae@zhar.net>:
>
> 
> I've been working on an A* for civil. Its not organized as well as it
> could be at the moment, but I'm currently in the middle of optimizing
> it.  I've done some work to make it more generic, with distance cost
> algorithms for both square based and hex based maps. Its based primarily
> off Amit Patel's great site.
> 
> I'll put it up somewhere on my site this weekend and let you know.
> 
> 
> BTW, have you done much performance testing on your version of A* Danny?
> 
> My current implementation takes about 1 second (with profiling on) to
> find a path ~100 steps long on a 128x128 map with randomly generated
> terrain. This is with C implementations of the distance cost algorithm
> and static terrain. 

It seems to me that if you want performance, perhaps a full A* is a
bit general? Or, at least, how about doing some preprocessing, or
adding some constraints on the terrain generation or something? After
all, once you have any kind of information about your problem domain,
you can probably do better than in the general case.

--
Magnus Lie Hetland                                  The Anygui Project
http://hetland.org                                  http://anygui.org
____________________________________
pygame mailing list
pygame-users@seul.org
http://pygame.seul.org