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

Re: [pygame] Pathfinding



Yanom Mobis wrote:
1) How is pathfinding done?
2) How do you prevent a moving sprite from being caught in a v-shaped rut made of obstacles?  Like this:
               __
A          ->  # |      B
__|

Others have already talked about the A* Algorithm (<http://en.wikipedia.org/wiki/A*>).

Here's my implementation of it:
http://kschnee.xepher.net/code/080721a_star_pathfinding.zip
Screenshots:
http://kschnee.xepher.net/pics/080720a_star.jpg
http://kschnee.xepher.net/pics/080721a_star.jpg

In English, you have the AI look at a map of costs to enter each area, and compute a minimum-cost path. A* automatically handles escaping from ruts, by terminating the paths it's considering when they prove too expensive. (You can treat walls as having an infinite entry cost.) One interesting feature of A* is that it assumes the AI has perfect knowledge, something fine for games but flawed for "real" AI.

XKCD's comment on this sort of cost-computation method:
http://imgs.xkcd.com/comics/genetic_algorithms.png