<!-- MHonArc v2.4.4 --> <!--X-Subject: [MUD-Dev] Re: mobile movement --> <!--X-From-R13: "Qnyvona Fverfvnf Rnexybpx" <pnyvonaNqnexybpx.pbz> --> <!--X-Date: Wed, 6 Jan 1999 15:25:38 -0800 --> <!--X-Message-Id: 00c901be39cd$38201c60$55e5edd0@dev-18.chilisoft.com --> <!--X-Content-Type: text/plain --> <!--X-Head-End--> <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN"> <html> <head> <title>MUD-Dev message, [MUD-Dev] Re: mobile movement</title> <!-- meta name="robots" content="noindex,nofollow" --> <link rev="made" href="mailto:caliban#darklock,com"> </head> <body background="/backgrounds/paperback.gif" bgcolor="#ffffff" text="#000000" link="#0000FF" alink="#FF0000" vlink="#006000"> <font size="+4" color="#804040"> <strong><em>MUD-Dev<br>mailing list archive</em></strong> </font> <br> [ <a href="../">Other Periods</a> | <a href="../../">Other mailing lists</a> | <a href="/search.php3">Search</a> ] <br clear=all><hr> <!--X-Body-Begin--> <!--X-User-Header--> <!--X-User-Header-End--> <!--X-TopPNI--> Date: [ <a href="msg00070.html">Previous</a> | <a href="msg00072.html">Next</a> ] Thread: [ <a href="msg00076.html">Previous</a> | <a href="msg00074.html">Next</a> ] Index: [ <A HREF="author.html#00071">Author</A> | <A HREF="#00071">Date</A> | <A HREF="thread.html#00071">Thread</A> ] <!--X-TopPNI-End--> <!--X-MsgBody--> <!--X-Subject-Header-Begin--> <H1>[MUD-Dev] Re: mobile movement</H1> <HR> <!--X-Subject-Header-End--> <!--X-Head-of-Message--> <UL> <LI><em>To</em>: <<A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A>></LI> <LI><em>Subject</em>: [MUD-Dev] Re: mobile movement</LI> <LI><em>From</em>: "Caliban Tiresias Darklock" <<A HREF="mailto:caliban#darklock,com">caliban#darklock,com</A>></LI> <LI><em>Date</em>: Wed, 6 Jan 1999 15:34:46 -0800</LI> <LI><em>Reply-To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI> </UL> <!--X-Head-of-Message-End--> <!--X-Head-Body-Sep-Begin--> <HR> <!--X-Head-Body-Sep-End--> <!--X-Body-of-Message--> <PRE> -----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. </PRE> <!--X-Body-of-Message-End--> <!--X-MsgBody-End--> <!--X-Follow-Ups--> <HR> <ul compact><li><strong>Follow-Ups</strong>: <ul> <li><strong><A NAME="00074" HREF="msg00074.html">[MUD-Dev] Re: mobile movement</A></strong> <ul compact><li><em>From:</em> "David Bennett" <ddt#discworld,imaginary.com></li></ul> </UL></LI></UL> <!--X-Follow-Ups-End--> <!--X-References--> <!--X-References-End--> <!--X-BotPNI--> <UL> <LI>Prev by Date: <STRONG><A HREF="msg00070.html">[MUD-Dev] Levels versus Skills, who uses them and when.</A></STRONG> </LI> <LI>Next by Date: <STRONG><A HREF="msg00072.html">[MUD-Dev] Re: mobile movement</A></STRONG> </LI> <LI>Prev by thread: <STRONG><A HREF="msg00076.html">[MUD-Dev] [RRE]MediaMOO annual birthday symposia: 1/20</A></STRONG> </LI> <LI>Next by thread: <STRONG><A HREF="msg00074.html">[MUD-Dev] Re: mobile movement</A></STRONG> </LI> <LI>Index(es): <UL> <LI><A HREF="index.html#00071"><STRONG>Date</STRONG></A></LI> <LI><A HREF="thread.html#00071"><STRONG>Thread</STRONG></A></LI> </UL> </LI> </UL> <!--X-BotPNI-End--> <!--X-User-Footer--> <!--X-User-Footer-End--> <ul><li>Thread context: <BLOCKQUOTE><UL> <LI><strong><A NAME="00084" HREF="msg00084.html">[MUD-Dev] Re: [RRE]MediaMOO annual birthday symposia: 1/20</A></strong>, Koster, Raph <a href="mailto:rkoster#origin,ea.com">rkoster#origin,ea.com</a>, Thu 07 Jan 1999, 16:39 GMT <LI><strong><A NAME="00082" HREF="msg00082.html">[MUD-Dev] Keegan's MUD Tree</A></strong>, J C Lawrence <a href="mailto:claw#kanga,nu">claw#kanga,nu</a>, Thu 07 Jan 1999, 05:24 GMT <LI><strong><A NAME="00081" HREF="msg00081.html">[MUD-Dev] OT: Mike Sellers needs some help load testing</A></strong>, J C Lawrence <a href="mailto:claw#kanga,nu">claw#kanga,nu</a>, Thu 07 Jan 1999, 03:11 GMT <LI><strong><A NAME="00076" HREF="msg00076.html">[MUD-Dev] [RRE]MediaMOO annual birthday symposia: 1/20</A></strong>, Bruce Mitchener, Jr. <a href="mailto:bruce#puremagic,com">bruce#puremagic,com</a>, Thu 07 Jan 1999, 02:02 GMT <LI><strong><A NAME="00071" HREF="msg00071.html">[MUD-Dev] Re: mobile movement</A></strong>, Caliban Tiresias Darklock <a href="mailto:caliban#darklock,com">caliban#darklock,com</a>, Wed 06 Jan 1999, 23:25 GMT <UL> <LI><strong><A NAME="00074" HREF="msg00074.html">[MUD-Dev] Re: mobile movement</A></strong>, David Bennett <a href="mailto:ddt#discworld,imaginary.com">ddt#discworld,imaginary.com</a>, Thu 07 Jan 1999, 00:08 GMT </LI> </UL> <UL> <li><Possible follow-up(s)><br> <LI><strong><A NAME="00072" HREF="msg00072.html">[MUD-Dev] Re: mobile movement</A></strong>, Caliban Tiresias Darklock <a href="mailto:caliban#darklock,com">caliban#darklock,com</a>, Wed 06 Jan 1999, 23:38 GMT </LI> <LI><strong><A NAME="00073" HREF="msg00073.html">[MUD-Dev] Re: mobile movement</A></strong>, Koster, Raph <a href="mailto:rkoster#origin,ea.com">rkoster#origin,ea.com</a>, Wed 06 Jan 1999, 23:49 GMT </LI> <LI><strong><A NAME="00105" HREF="msg00105.html">[MUD-Dev] Re: mobile movement</A></strong>, Kylotan <a href="mailto:kylotan#globalnet,co.uk">kylotan#globalnet,co.uk</a>, Mon 11 Jan 1999, 07:25 GMT </LI> </UL> </LI> </UL></BLOCKQUOTE> </ul> <hr> <center> [ <a href="../">Other Periods</a> | <a href="../../">Other mailing lists</a> | <a href="/search.php3">Search</a> ] </center> <hr> </body> </html>