[MUD-Dev] Re: mobile movement

[Caliban Tiresias Darklock]

-----Original Message-----
From: Matthew Mihaly <diablo at best.com>
To: mud-dev at kanga.nu <mud-dev at kanga.nu>
Date: Wednesday, January 06, 1999 2:42 PM
Subject: [MUD-Dev] mobile movement


>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.

On a 286/12 processor.

That fast enough? ;)

This is done using Dijkstra's algorithm (which is available in Java all over
the web, hit a search engine and just make sure you spell it right -- or, if
you feel macho, get a college Graph Theory textbook) recursively, basically
taking each room I can get to from here and running the shortest path
algorithm on all of them in turn. A list of which areas have been visited is
maintained, and loop-checking is done. If a loop is detected (a sector
previously visited in the same path), no path exists from this source; if a
previously-visited node is found, the current length is checked against the
length of the other paths, and if it is shorter, the old one is discarded;
otherwise this one is discarded. These termination conditions greatly speed
the process.

The process will probably be a bit slower if you have some sort of weird
method to find out what exits lead out of someplace. In UU, all the links
are in memory all the time (thus the 32K limit due to DOS segment barriers),
so it's a very simple offset-and-iterate search method. I know that the
exits for location 12 are at 6 * 12 in the links array and there are six of
them, so I just need to check links[72] through links[77].

The process will be MUCH slower in softcode. Dynamic exits which may change
during transit would be a complete bitch, as well. ;)

>2) When, for instance, a mobile first is assigned the task of walking to
>another room, you would build a list of the necessary rooms to move
>through so that the above search would only have to be done once. If the
>mobile were tracking to a player, then the list would be built, and
>everytime said player moved logically (as opposed to teleporting, which
>would require the search to be done again), the list would be changed
>accordingly. This seems much faster than method 1, but it also seems
>inferior.


You pretty much have to do this *anyway* in order to get the shortest path
and determine the best rooms to move through.

The primary problem of checking shortest paths is that people check stupid
things, like if you have two exits which have exits to each other, they
check both. Duh. If your shortest path to point A is to go to point B and
then point A, then when you discover a shortcut directly to B you *already*
have a shortest path: just chop A out of the list and move on. Many people
will just ham-handedly recalculate the same path they had before, and then
replace the old one with it. It is important to remember what you've done,
where you've been, and how you got there. If you have been to room A, and it
is not in the last recorded shortest path, then you're not going to do
better. If it IS in the last recorded shortest path, then you either did
better already or you're wasting your time.

Another thought: just go to where you last saw the player. If he's not
there, hang around for a while to see if he comes back, and if not... do the
path thing again. Repeat till you find him. Much less complex, and probably
just as efficient. The Cabal in UU don't track players so much as they track
places where Bad Things happened to them. Then they just go to that area,
and look around for anything that belongs to someone they don't like. (Which
would be anyone who isn't Cabal, making things much easier.)

>Have any of you implemented a system like this, and if not, why not? If
>so, what method did you use? Please keep in mind that I don't know any of
>the coding languages any of you know and that I lack knowledge of general
>coding concepts, so I'd appreciate a minimum of jargon.


Hopefully I haven't confused you with any of the above; mail me if you have
trouble with any of it and I'll explain in less technical terms.