January 1999
- From DevMud: Database module Greg Connor
- From DevMud: Database module Mik Clarke
- From DevMud: Database module Greg Connor
- From DevMud: Database module J C Lawrence
- From DevMud: Database module Greg Connor
- ADMIN: Resends and possible duplicates J C Lawrence
- Info about different skill systems Emil Eifrem
- Info about different skill systems Nathan F Yospe
- Info about different skill systems Ben Greear
- Info about different skill systems Emil Eifrem
- Info about different skill systems Ben Greear
- Info about different skill systems Emil Eifrem
- Info about different skill systems Nathan F Yospe
- Info about different skill systems Travis S. Casey
- Info about different skill systems Mik Clarke
- New features for ScryMUD (Player-run Shops) Ben Greear
- [OT Humor] Mudder's Rhapsody Jon A. Lambert
- [OT Humor] Mudder's Rhapsody Caliban Tiresias Darklock
- [OT Humor] Mudder's Rhapsody The Wildman
- Guild/skill/spell relation (or "webs") Petri Virkkula
- Guild/skill/spell relation (or "webs") David Bennett
- mobile movement Matthew Mihaly
- mobile movement Adam Wiggins
- mobile movement Koster, Raph
- mobile movement Caliban Tiresias Darklock
-----Original Message-----
From: Matthew Mihaly <diablo@best.com>
To: mud-dev@kanga.nu <mud-dev@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. - mobile movement David Bennett
- mobile movement Kylotan
- mobile movement quzah [softhome]
- mobile movement Ling
- mobile movement J C Lawrence
- mobile movement Oliver Jowett
- mobile movement Oliver Jowett
- mobile movement Caliban Tiresias Darklock
- mobile movement Richard Woolcock
- mobile movement J C Lawrence
- mobile movement Ling
- mobile movement Marc Hernandez
- mobile movement J C Lawrence
- mobile movement Ling
- mobile movement Holly Sommer
- mobile movement Caliban Tiresias Darklock
- mobile movement Koster, Raph
- mobile movement Chris Gray
- Intelligent WebGlimpse archive searching at Kanga.Nu (was J C Lawrence
- [RRE]MediaMOO annual birthday symposia: 1/20 Bruce Mitchener, Jr.
- [RRE]MediaMOO annual birthday symposia: 1/20 Koster, Raph
- OT: Mike Sellers needs some help load testing J C Lawrence
- Keegan's MUD Tree J C Lawrence
- Intelligent WebGlimpse archive searching at Kanga.Nu Marian Griffith
- Intelligent WebGlimpse archive searching at Kanga.Nu Caliban Tiresias Darklock
- Intelligent WebGlimpse archive searching at Kanga.Nu Dominic J. Eidson
- Intelligent WebGlimpse archive searching at Kanga.Nu J C Lawrence
- Intelligent WebGlimpse archive searching at Kanga.Nu Marian Griffith
- GRASS GIS Web Site Elis Pomales
- Thoughts Caliban Tiresias Darklock
- mobile movement (the fault of tracking) quzah [softhome]
- ADMIN Name server problems and upes J C Lawrence
- Adjective Server Christopher Allen
- Reputations, More Mazes Eli Stevens {KiZurich}
- Reputations, More Mazes J C Lawrence
- Reputations, More Mazes Eli Stevens {KiZurich}
- Mules (was something different) Marian Griffith
- Mules (was something different) J C Lawrence
- Mules (was something different) Hans-Henrik Staerfeldt
- Levels versus Skills Marian Griffith
- Levels versus Skills Caliban Tiresias Darklock
- Levels versus Skills J C Lawrence
- Levels versus Skills quzah [softhome]
- Levels versus Skills Vladimir Prelovac
- Levels versus Skills quzah [softhome]
- Levels versus Skills J C Lawrence
- Levels versus Skills Petri Virkkula
- Levels versus Skills J C Lawrence
- Levels versus Skills Caliban Tiresias Darklock
- From Devmud: Database module, draft 3 Greg Connor
- Matrix Game Ling
- Graphic design doc Thinus Barnard
- Graphic design doc Chris Gray
- ADMIN: List server and Kanga.Nu host changes J C Lawrence
- ADMIN: List server and Kanga.Nu host changes Koster, Raph
- Sockets and fibers Caliban Tiresias Darklock
- Sockets and fibers Adam J. Thornton
- Sockets and fibers Caliban Tiresias Darklock
- Sockets and fibers J C Lawrence
- Sockets and fibers Jon A. Lambert
- Sockets and fibers Adam J. Thornton
- Sockets and fibers Dr. Cat
- Sockets and fibers Jo Dillon
- [DevMUD] From Devmud: Database module, draft 3 Greg Connor
- META: list "peerage" Koster, Raph
- META: list "peerage" John Bertoglio
- META: list "peerage" diablo@best.com
- META: list "peerage" Andy Cink
- META: list "peerage" Caliban Tiresias Darklock
- META: list "peerage" Quzah [softhome]
- META: list "peerage" Michael.Willey@abnamro.com
- META: list "peerage" Caliban Tiresias Darklock
- META: list "peerage" Holly Sommer
- META: list "peerage" Travis S. Casey
- META: list "peerage" Andy Cink
- META: list "peerage" Quzah [softhome]
- META: list "peerage" Matthew D. Fuller
- META: list "peerage" Laurel Fan
- META: list "peerage" Caliban Tiresias Darklock
- META: list "peerage" David Bennett
- META: list "peerage" Bruce Mitchener, Jr.
- META: list "peerage" diablo@best.com
- META: list "peerage" Matthew D. Fuller
- META: list "peerage" Caliban Tiresias Darklock
- META: list "peerage" Brandon A Downey
- META: list "peerage" Travis Casey
- META: list "peerage" Caliban Tiresias Darklock
- META: list "peerage" Dominic J. Eidson
- META: List "peerage" Marian Griffith
- META: List "peerage" Caliban Tiresias Darklock
- META: list "peerage" Ola Fosheim Grøstad
- META: list "peerage" Sayeed
- Mugu Chris Gray
- META: List peerage and behaviour J C Lawrence
- META: list "peerage" Chris Gray
- ADMIN: We're working again. J C Lawrence
- Java I/O and threads. Elis Pomales
- Java I/O and threads. Jo Dillon
- Java I/O and threads. cynbe@muq.org
- Java I/O and threads. Jo Dillon
- Java I/O and threads. Elis Pomales
- Reset Death Wes Connell
- Reset Death Quzah [softhome]
- Reset Death Wes Connell
- Reset Death Mik Clarke
- Reset Death Andrew C.M. McClintock
- Reset Death Mik Clarke
- PvP and mob capacities (was "List Peerage") Caliban Tiresias Darklock
- combat diablo@best.com
- META: list "peerage" Darrin Hyrup
- META: list "peerage" J C Lawrence
- Telmaron and Mud servers was: META: list "peerage" Elis Pomales
- META: list "peerage" Caliban Tiresias Darklock
- META: list "peerage" Ben Greear
- Who is? (was about level vs skills) Marian Griffith
- Who is? (was about level vs skills) Caliban Tiresias Darklock
- exploration points diablo@best.com
- [MUD-Dev] Juha Lindfors
- Stock Mud Demographics ##Make Nylander
- ADMIN: Off-topic and the ever present reminders on quoting. J C Lawrence
- Mud reviewing Andy Cink
- Mud reviewing Caliban Tiresias Darklock
- Mud reviewing diablo@best.com
- Mud reviewing Andru Luvisi
- Mud reviewing diablo@best.com
- Mud reviewing J C Lawrence
- Mud reviewing Dan Shiovitz
- Mud reviewing diablo@best.com
- Mud reviewing Caliban Tiresias Darklock
- Mud reviewing diablo@best.com
- Mud reviewing Richard Woolcock
- Mud reviewing David Bennett
- Mud reviewing Caliban Tiresias Darklock
- MUD Admin skills Hal Black
- Subdue Holly Sommer
- processors diablo@best.com
- processors John Bertoglio
- processors Wes Connell
- processors Laurel Fan
- processors Mik Clarke
- processors J C Lawrence
- processors diablo@best.com
- processors Quzah [softhome]
- processors Mik Clarke
- processors J C Lawrence
- processors Marc Hernandez
- processors Adam Wiggins
- processors Greg Underwood
- processors Adam Wiggins
- processors Chris Gray
- processors gunderwood@donet.com
- processors Jon A. Lambert
- processors Greg Underwood
- processors Petri Virkkula
- quests involving players diablo@best.com
- quests involving players Darren Henderson
- quests involving players Caliban Tiresias Darklock
- quests involving players Richard Woolcock