[MUD-Dev] Tech: Pathfinding with Rooms

[David Bennett]

On Fri, 30 Nov 2001, Per Vognsen wrote:

> Do you do consistency checking to make sure that the coordinate
> offsets are right? Let's say you start in any room. Initialize a
> vector to (0,0). Now walk around a loop (i.e. a path starting and
> ending in the initial room), adding displacement vectors to the
> initial vector as you go along. Unless it all adds up to (0,0) for
> any loop I think the pathfinding system will get into trouble.

Now and then we wander around and check all the co-ordinates.  If
they do get messed up it makes the algorithm take longer, but it
doesn't stop it from working.  The co-ordinates are like weighted
edges on a graph.  It will always try and take the link which looks
like it is closer to the destination.

> Yeah, I wrote a small handful of articles for Agora on path
> finding last night where I mentioned this. Is the clustering done
> at multiple levels? The nice thing about having multiple
> clustering levels is that it makes precomputation of all shortest
> paths much more feasible. The memory required for storing all
> shortest paths of an n-node graph is O(n^2). But as long as you
> cluster at multiple levels you should be able to keep n relatively
> low. I seem to remember that Hans-Henrik did something similar for
> DikuMUD 2 though the clustering was more static as it was based on
> rooms and zones/areas. If memory is at a premium it probably makes
> more sense to stream parts of the shortest paths matrices to and
> from disk as needed rather than caching and recomputing if
> something is not in the cache.

We only do a single level of clustering, which works quite well.
This is also a little adapted from what the people on Shattered
World did.  They have a similar system of path finding (I had their
code for this at one point too, nice people).

Wombles!
David.

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