[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:

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: