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