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

[John Eikenberry <jae@zhar.net>]

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