Re: [pygame] Pathfinding

[Brian Fisher <brian@xxxxxxxxxxxxxxxxxxx>]

On Sun, Jan 25, 2009 at 7:16 PM, Yanom Mobis <yanom@xxxxxxxxxxxxxx> wrote:
> 1) How is pathfinding done?

>
So what are your pathfinding needs? what exactly is the character or
game element that you need pathfinding for doing? or is this just
research for you?


On Mon, Jan 26, 2009 at 12:53 AM, Marius Gedminas <marius@xxxxxxxxx> wrote:

> My personal snag with A* is that the NPCs seem to know too much about

> the map and directly walk the most optimal path without exploration.
>

I tend to agree with this - the whole purpose of A* is that when
it's used, it finds a provably optimal path to it's goal, also because
it is efficient, it has a strong tendency to find the same path every
time.If those are desireable traits, then it is good for what you want to do. 

Very often though, what you actually want to achieve is an enemy or
character that doesn't look stupid, can be somewhat unpredictable, and
one that seems to have some personality (runs away from bad things,
maybe changes it's speed when appropriate, or maybe it has a hard time
turning). A* can help with the "doesn't look stupid" part, and if you
play with the heuristic and the pathing costs right, you can get some
personality, but it alone can't do everything, it's just one tool in
making "fun" pathing.

I personally think that the best thing with getting good pathing is
really to get in there and play with things, and find tricks that work
well for the domain of your game. It's good to get a good understanding
of A*, and it's an awesome tool to be able to yield, but I always have
it play a fairly small role in the final behavior of the pathing character or object, if it all.

One things that I frequently find useful is doing a hierarchy of
searches, at least in the case of large map games (like rts) - this is usually done by making
"checkpoints" around the map (either by a designer, or by the ai as it
plays) and having an estimate of cost between them. So like if you had a map of a bunch of islands connected by bridges (like a map of denmark or venice or something)
you'd have a checkpoint stored for each island, and you'd have data storing which island is connected to which and the expected cost to travel using that bridge. Then you'd do the path finding on two levels - first complete pathfinding using the checkpoint and store that - then while the character is going from one checkpoint
to the next, do pathfinding just between those 2 checkpoints - so if like an island is filled with stuff, the character would pathfind around that stuff on his way to the bridge.

Another thing that can be helpful in getting "fun" is add a sense of memory to the character. This can complement hierarchical search very well, as having a "memory" of the whole map can be prohibitively expensive, and because it can give the player opportunities for strategic choices. Like in the bridge case above, maybe bridges can be out, or maybe the player can jam up an island somehow. In that case, then when the enemy is trying to follow the choices he made with the bridges and islands, and he is doing local pathfinding from one island to the next, he'll either fail to find a path in the maximum amount of looking he's allowed, or will find it costs much more than his checkpoint estimate told him. So at that point you update the checkpoint data, and then redo the checkpoint level planning.

On Mon, Jan 26, 2009 at 9:01 AM, Michael George <mdgeorge@xxxxxxxxxxxxxx> wrote:
> One possibility to solving this is to have the npc move as it's performing the algorithm.
> i.e. as your search explores a path, the character walks along that path. 
>
in the language of A*, I guess you are suggesting ending the algorithm before it completes, then having the ai follow the stored path with the cheapest sum of (cost to follow the path to some point + heuristic estimate to finish from that point). That sounds like a good suggestion, it's often a practical choice choice because the cost to path grows greater than linear with the distance pathed,

 
On Mon, Jan 26, 2009 at 9:01 AM, Michael George <mdgeorge@xxxxxxxxxxxxxx> wrote:
> This could probably be implemented fairly cleverly by using generators.  You'd probably
> have to experiment with different algorithms to find a more "realistic" approach - I suspect
> that A* would involve lots of wandering since it assumes constant access time for all known
> branches (whereas the character has to walk up and down the tree). 
> DFS would probably be more realistic.

>
I don't know exactly what you mean that A* would "assume constant access time for all known branches" - If you are taking about the idea that the character takes a lot of dead ends and walks back, you can work around that by varying the search depth when the character has taken too many dead ends.

Also depth first search is not mutually exclusive to A* - In fact I find the best way to do A* is usually with "Depth First Search with Iterative deepening", because it saves you the cost of having to store the outer hull of your breadth first data (with depth first you only store the path you are testing as you explore the space). The basic idea is to do depth first a* with a max cost that says how deep you are willing to look (so you bound the cost of the call, but also limit how far you will search), and if you don't find a good path, you step up the depth first limit so you search farther.