I need to have an npc take a relatively short route from a to b.
First priority isn't the shortest distance, it's getting there without getting
stuck
My game is in a futuristic setting, so taking the shortest path without
exploring too much
is reasonable because they would have GPS and the like.
--- On Mon, 1/26/09, Brian Fisher <br...@hamsterrepublic.com> wrote:
From: Brian Fisher <br...@hamsterrepublic.com>
Subject: Re: [pygame] Pathfinding
To: pygame-users@seul.org
Date: Monday, January 26, 2009, 11:55 AM
On Sun, Jan 25, 2009 at 7:16 PM, Yanom Mobis <ya...@rocketmail.com> 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 <mar...@gedmin.as> 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 <mdgeo...@cs.cornell.edu> 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 <mdgeo...@cs.cornell.edu> 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.
