[MUD-Dev] Tech: Pathfinding with Rooms

[Nicholas E. Walker]

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 at gnu.org>

_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev