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.jpgIn 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