[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [pygame] Does anyone have a python implementation of A*?
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