[Home] [Groups] - Message: [Prev in Group] [Next in Group]
21559: Re: [MUD-Dev] Tech: Pathfinding with Rooms
[Full Header] [Plain Text]
From: "Nicholas E. Walker" <new@gnu.org>
Newsgroups: nu.kanga.list.mud-dev
Date: Thu, 29 Nov 2001 16:30:22 +0000
References: [1]
Organization: Kanga.Nu
On Thu, Nov 29, 2001 at 03:50:32AM -0500, Sanxion wrote:
> I'm new to this list. I have a questions about pathfinding in
> MUDs. I know how to handle pathfinding on a grid, but from what I
> understand most MUD rooms do not have a X and Y position as a
> tile/cell would have on a grid. MUD rooms have a series of
> connections to surrounding rooms. So whats the best way to
> pathfind in a MUD Room model? In a grid system you can estimate
> the cost, but without being able to estimate the distance between
> starting and ending point the pathfinding just spreads in all
> directions ending up searching alot of rooms.
> Do you start pathfinding from Starting and Ending point until they
> meet? Is there a smart way to get a good heuristic
> (i.e. manhattan distance) with MUD rooms?
You'd probably be best off using a spanning-tree algorithm.
Read:
http://www.cs.sunysb.edu/~algorith/files/minimum-spanning-tree.shtml
And/or:
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/mst.html
--
Nicholas E. Walker <new@gnu.org>
_______________________________________________
MUD-Dev mailing list
MUD-Dev@kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev