[MUD-Dev] Tech: Pathfinding with Rooms

[Per Vognsen]

On 29 Nov 2001, at 17:37, David Bennett wrote:
> On Fri, 29 Jun 2001 vognsen at post10.tele.dk wrote:
 
>> If you really need realistic path finding and the like I don't
>> think the standard room model is up to the task. As you mention
>> yourself, positioning everything on a grid simplifies the
>> problem.
 
> Discworld uses a Depth first search, with weighting based on
> pseudo-coordinates.  The co-ordinates are calculated using the
> exit directions, every exit has a direction associated with them
> and an offset from the current rooms co-ordinates.  This works
> quite well.

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.

> We then 'cluster' the rooms together into blobs and do route
> finding on the clustered blobs.  Then find routes through the
> blobs themselves, caching the results.  It is relatively efficent
> for finding quite long routes.  We cache the routes too.  We don't
> load all the rooms either, all the room data is stored in a
> database which we use for the route finding.

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.

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