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

Re: [pygame] Pathfinding

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.