[MUD-Dev] [TECH] Shortest-Path

Miroslav Silovic miro at vams.com
Mon Apr 8 10:54:44 New Zealand Standard Time 2002


William Murdick wrote:

> Quick question for everyone about shortest-path
> sorting/searching. Helping write a mud from the ground up and I'm
> having to rewrite much of the shortest-path calculations due to
> the differences in our mud design. I have an undirected graph
> loaded into an adjacency list. What I want to do, of course, is
> trace a path from Point A which is the NPC to Point B and then
> return the entire path so that the NPC can then "walk" the path
> path.

> Trying to figure out what the best algorithm would be to use for
> this...  Djikstra, Depth-First, Breadth-First, or some other. Does
> anyone have any suggestions? This is my first foray into this sort
> of sorting and searching and so I am not that familiar with it
> all.

This could be helpful: 

  http://www.boost.org/libs/graph/doc/table_of_contents.html

It's from the Boost library (the implementation itself is decent,
too, if you don't mind template bloat and weird building system).

    Miro


_______________________________________________
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