On Jan 25, 2009, at 7:16 PM, 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 __| Where A and B are the points the sprite needs to travel, # is the sprite, -> is the direction the sprite is moving, and _ and | are obstacles?
"Naive" algorithms often head directly toward a goal, and then get stuck when, in order to achieve the goal, they have to move away from it. Do some reading on "local maximum problem" and "hill-climbing algorithm."
The way to get out of this rut (heh heh) is to use a better algorithm.For example, if you have a known map where the obstacles don't move, you can make a pre-computed route that your guy # walks along. That's an extremely popular way to do it, and it does really well for dungeon- y type video games. "Guard on patrol."
The super deee-luxe, full-fat algorithm for when the obstacles/goals are moving is to use an algorithm that plots a complete route to the goal, every time, and move along the path.
There are still ways that this can get confused or beaten, of course. Until someone comes out with a low-cost traveling-salesman solver, however, whatever algorithm you find will have some snags.