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

[John Eikenberry <jae@zhar.net>]

Bob Ippolito wrote:

> It's too bad stock python doesn't support continuations, cause they can 
> make a big difference for something like A*, especially if you want to 
> break processing over a few frames without using, or without the 
> overhead and complications of, real threads.

Yes, continuations would be nice in this situation, but until stackless
python or some such gets accepted... 
 
> The data structure you end up using for the priority queue is also 
> pretty important.. you kinda just have to try a few (and probably a few 
> different implementations of each) for your generic data set and see 
> what ends up working best, especially in a language like python some of 
> the normal optimization rules don't quite apply.

This is an area where some improvement could certainly be seen. The
priority queue python module uses a fibonacci heap which is sub-par for
game's with queues of < 10000 nodes (according to Amit). As this would
apply to nearly all games, a better pqueue would be nice. 

Not being proficient at C (let alone optimized C) I've been looking
around a bit for a good C splay implementation. Splay looks to be the
best general performer for most game sized maps. Haven't had much luck
as of yet though.

-- 

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