[MUD-Dev] [TECH] Shortest-Path

[Robert Zubek]

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