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

[John Eikenberry <jae@zhar.net>]

One last update. I've sense figured out I had made a mistake in my A*
implementation. I won't get into the details to save pride, but
basically the bad calculations were causing A* to search most of the
map. 

The fixed version is much faster and seems to find better paths. I've
updated the version on my site. The most up-to-date, though more game
specific version, will also be available via civil's cvs.

John Eikenberry wrote:

> I've put my A* implementation up on my web site. You can find it at:
> 
> http://zhar.net/projects/pygame/
> 
> It includes a few files I use from Civil, as that's my current target.
> 
> John Eikenberry wrote:
> 
> > Found it... turned out to be a heuristic change. I wasn't including the
> > cost-so-far part (opps). This has the effect of only checking the very
> > top of the open list (ie. only the hexes immediately surrounding the
> > direct path were checked).
> 
> One good note from this mistake is that it made me re-examine my
> heuristic and found it doesn't do so well. Should have known, the
> heuristic is almost always the performance bottleneck with search
> algorithms.
>  
> > Back to the optimization drawing board. I'll have to check out whether
> > map makes a difference now, as I was assuming the C loop structure was
> > making the difference and now I have to know. :)
> 
> Tried out map()... it seems to give a small improvement (5%). Much
> closer to what I was expecting and probably not worth the obfuscation it
> adds. I still have hope for a numeric python version. But other than
> that I think I'll concentrate on optimizing the heuristic.
> 
> -- 
> 
> John Eikenberry
> [jae@zhar.net - http://zhar.net]
> ______________________________________________________________
> "They who can give up essential liberty to purchase a little temporary
>  safety, deserve neither liberty nor safety."
>                                           --B. Franklin
> ____________________________________
> pygame mailing list
> pygame-users@seul.org
> http://pygame.seul.org

-- 

John Eikenberry
[jae@zhar.net - http://zhar.net]
______________________________________________________________
"They who can give up essential liberty to purchase a little temporary
 safety, deserve neither liberty nor safety."
                                          --B. Franklin
____________________________________
pygame mailing list
pygame-users@seul.org
http://pygame.seul.org