[MUD-Dev] [TECH] Shortest-Path
Robert Zubek
rob at cs.northwestern.edu
Wed Apr 10 20:58:58 New Zealand Standard Time 2002
From: Amos Wetherbee
> This is also of interest to me. One thing that I am interested in
> is instead of generating the entire path, I want to be able to
> make one call to find the next room closer to where I am trying to
> get too (allowing for weighted values so that NPCs tend to walk on
> roads.)
If you have a heuristic function that can approximate the distance
to the destination, you could try to do a heuristic search.
Heuristic searches work based on an approximation of the path
cost. Imagine you had an oracle that, for every point in the graph,
could tell you the shortest-path distance from that point to your
destination. This would make your path-finding much simpler - at
every step you could simply look at your neighbors, and move to the
one that the oracle says is the closest to the destination.
Now, unfortunately, we don't have such oracles. But for many
applications, we can find heuristic functions that give us a
reasonable guess at shortest-path distance. For example, when the
graph is a simple grid, such as in computer games, we can use simple
as-the-crow-flies point-to-point distance to approximate the
oracle. This is how algorithms such as Best-First or A* work - they
use a heuristic function such as Euclidean distance-to-destination
to guide search.
There are caveats to be aware of. Following a path whose computation
hasn't been completed can lead to strange behavior in case of
unusual spatial configurations.[1] Also, the heuristic function
takes some tuning - in case of A*, for example, one has to be
careful that it underestimate the true distance to the destination.
There's a good discussion of search techniques at
http://www.aaai.org/AITopics/html/seachreason.html
and of the A* heuristics in particular at
http://www-cs-students.stanford.edu/~amitp/Articles/AStar3.html
Hope this helps,
Rob
[1] For example, if you're in a room whose only exit leads away from
the destination, the search will likely first explore moving towards
the wall closer to the destination, before it finds the exit - so it
would be bad to try and follow it too early.
--
Robert Zubek
rob at cs.northwestern.edu
http://www.cs.northwestern.edu/~rob
_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev
More information about the MUD-Dev
mailing list