[MUD-Dev] Re: mobile movement

[David Bennett]

On 1/6/99, at 3:34 PM, Caliban Tiresias Darklock wrote: 

>>1) Doing some sort of real-time search (BFS or DFS maybe?) everytime
>>movement was to take place, to find the best room to move to from the
>>current one. Advantages of this, to my mind, are that it allows for the
>>most intelligent movement. The disadvantage of course is that this is
darn
>>slow (how slow, I don't know. I code on Achaea, but I would not really
>>consider myself much of a coder. Maybe one of you could enlighten me as
to
>>just how slow such a routine is likely to be, given that we could limit
>>how many rooms away to search, etc).
>
>
>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.

Wombling down the fluffy path,
David.