[MUD-Dev] Re: mobile movement

[Kylotan]

-----Original Message-----
From: David Bennett <ddt at discworld.imaginary.com>
To: mud-dev at kanga.nu <mud-dev at kanga.nu>
Date: 07 January 1999 00:23
Subject: [MUD-Dev] Re: mobile movement

>On 1/6/99, at 3:34 PM, Caliban Tiresias Darklock wrote:
>
>>Ultimate Universe can perform a 30-deep search of a weightless directed
>>graph (it costs the same to move from any room to any connected room, and
>>moving from room A to room B does not necessarily mean you can move from
>>room B to room A: just like most MUDs which use rooms) with no more than
>>32,000 exits across the entire graph --- in less than ten seconds.
>
>A nice method of speeding up this sort of thing (that was suggested to me
>by Mike McGaugerty of Shattered World) was to make up clusters of rooms.
>Then do a path find through the clusters and then a path find through each
>cluster.  This significantly reduces the number of searches you need to do
>at a fairly minimal memory cost.  This is especially good if you do route
>finding quite often.  A cluster of rooms would be a connected set of rooms,
>up to some random cut off number, say 12 or so.  You then keep track of the
>connections between clusters and any pre-determined routes through a
>cluster.  Makes everything a lot faster and is quite a neat solution.

Many muds already have such 'clusters' inbuilt into the game, except they
are called areas or zones. :-)  It is a trivial task to track through the
area list, and then through the individual areas, as you would for clusters.
Since each area may have very few exits to other areas, precalculating the
possible routes through each area can be a lot of help (assuming you do not
have a lot of dynamic exits, random mazes or other such blockages).

Of course, you can quite rightly point out that, given the varying number of
rooms in an area, this method does not guarantee the shortest path from A to
B. However, in some cases (soft-coded servers perhaps?), the performance
gain might be worth the accuracy trade-off.

Secondly, real-life studies indicate that people tend to navigate by using
waypoints, such as landmarks or settlements, rather than a mathematical
consideration of the shortest path, especially when such a consideration
only makes a small difference overall. Many people will take a slightly
longer route if it lessens the chances of getting lost, for example. Also,
should the average NPC know enough about all the interposing areas such that
he or she can make such an accurate mental calculation? Therefore, given
that areas tend to correlate highly with what might be waypoints on a mud,
this could also be viewed as an improvement to NPC AI :-)

Kylotan.