[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

Re: [pygame] Pathfinding



Brian Fisher wrote:


On Mon, Jan 26, 2009 at 9:01 AM, Michael George <mdgeorge@xxxxxxxxxxxxxx <mailto:mdgeorge@xxxxxxxxxxxxxx>> wrote: > One possibility to solving this is to have the npc move as it's performing the algorithm. > i.e. as your search explores a path, the character walks along that path. > in the language of A*, I guess you are suggesting ending the algorithm before it completes, then having the ai follow the stored path with the cheapest sum of (cost to follow the path to some point + heuristic estimate to finish from that point). That sounds like a good suggestion, it's often a practical choice choice because the cost to path grows greater than linear with the distance pathed,

I was actually thinking that you make the A* function a generator. Each time it explores a new branch, it yields, and then the character moves to that branch. For DFS, iterative deepening this would work well, while for BFS, Dijkstra, or A* it would probably work poorly.

--Mike