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