[Home] [Groups] - Message: [Prev in Group] [Next in Group]
23009: Re: [MUD-Dev] [TECH] Shortest-Path
[Full Header] [Plain Text]
From: Ben Greear <greearb@candelatech.com>
Newsgroups: nu.kanga.list.mud-dev
Date: Sat, 06 Apr 2002 11:37:19 -0700
References: [1]
Organization: Kanga.Nu
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.
Basically, breadth first, and mark the rooms you've already visited
because mud zones often have loops. I put a limit on my algorithm
to around 100 rooms for performance reasons (you have to get that
close to effectively track someone.)
You can find the Tree class that I use to remember the path in my
game at: scry.wanfear.com, but that code is extremely complex, and I
can't easily explain it anymore (it does work, though :))
Ben
--
Ben Greear <greearb@candelatech.com> <Ben_Greear AT excite.com>
President of Candela Technologies Inc http://www.candelatech.com
ScryMUD: http://scry.wanfear.com http://scry.wanfear.com/~greear
_______________________________________________
MUD-Dev mailing list
MUD-Dev@kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev