<!-- MHonArc v2.4.4 --> <!--X-Subject: [MUD-Dev] Re: mobile movement --> <!--X-From-R13: X Q Znjerapr <pynjNhaqre.rate.ftv.pbz> --> <!--X-Date: Wed, 13 Jan 1999 14:33:38 -0800 --> <!--X-Message-Id: 199901132233.OAA25953#under,engr.sgi.com --> <!--X-Content-Type: text/plain --> <!--X-Reference: Pine.SOL.3.96.990113012241.3503A-100000@sun-cc203 --> <!--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:claw#under,engr.sgi.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="msg00140.html">Previous</a> | <a href="msg00142.html">Next</a> ] Thread: [ <a href="msg00128.html">Previous</a> | <a href="msg00215.html">Next</a> ] Index: [ <A HREF="author.html#00141">Author</A> | <A HREF="#00141">Date</A> | <A HREF="thread.html#00141">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>: J C Lawrence <<A HREF="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</A>></LI> <LI><em>Date</em>: Wed, 13 Jan 1999 14:33:33 -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> On Wed, 13 Jan 1999 01:33:30 +0000 (BST) Ling <K.L.Lo-94#student,lboro.ac.uk> wrote: > On Tue, 12 Jan 1999, J C Lawrence wrote: >> Plot and follow path from current position to position of target. >> if current position was position of target within last X time >> follow path of target (ie same location motions) if blocked, >> resume plot/follow. if current location is too-old target >> position, resume plot/follow > Log all player movement that is in quick succession. That is, > continuous movement with only brief pauses. Starting a log > requires monitoring the player until the server thinks that the > player really is on the move. Ending the log means waiting for a > significant pause (like over 30 seconds, maybe a minute). > Compare logs of locations traversed, if there are significant > continuous agreements in location between multiple logs, make > these locations a highway with branch offs equal to the start and > end of the players' moves. > Then add code to give highways a score. This score decays to > remove highways that are out of fashion. Highways that are in use > constantly would have their score topped up by the players. Maybe > code to join highways up... Hope this isn't too obscure. This is expensive as it requires rooms to be monitored and to update themselves even when they are inactive. Ouch. It can be made significantly cheaper if you have rooms post-computer their current state when queried, but that still leaves a significant data gathering load. And even cheaper solution, generalised for room and coordinate systems: 1) Quantise your world into cells. If you run a room based world, rooms are your cells. If you're coordinate based, use any convenient tesselating shape shape that maps cheaply to your world You can even vary the tesselation type as needed. The key requirements are that it MUST be cheap to devolve an arbitrary location into a cell reference, and it must be cheap to maintain a simple DB under that reference. 2) Upon an object (say player character) entering a cell a tuple is created which contains an ObjectID, EntryDirection, and EntryTimestamp. This tuple can be hung off the object (as versus the cell). If the tuple is hung off the object then the ObjectId is not needed. 3) Upon an object leaving a cell, the above (#2) tuple is extracted and an ExitDirection and ExitTimeStamp added. The resulting tuple defines a vector, a speed and an owner. 4) Merge the tuple from #3 with a DB of such tuples hung off the cell reference. The result of the merge would be a vector and an associated list of timestamped ObjectID's. A rolling average can also be stored for each vector indicating the average transition speed of that vector (this has other more interesting uses unrelated to path finding). 5) Post-processing would remove older tuple sets from the cell DB, merging them into a single meta-set with an anonymous objectID/timestamp. 6) The meta-set in #5 would have a controlled decay rate (approaches zero in known time) which wuold computed and stored upon query by remote client or #5. Now to create a highway or even path-to-object map starts to be pretty trivial and computation light (if data heavy): a) Get DB set for starting location. b) Get DB for target location. c) Select an arbitrary "path weight", where a path weight is the number of DB entries for a particular vector in a given cell. d) Build a graph of cells, starting from the starting location, and following and considering only vectors with a weight equal to or higher than the threshhold path weight. e) Simultaneously build a parallel graph, starting from the target location. f) Upon finding an intersection of the two graphs (hash tables are your friends), the minimised path route (ordered by maximum sum velocity from #4) is your path from source to target. g) You can of course continue growing the graphs and even store them globally for general reference. If you do store them globally, the following refinement comes to mind: i) Do all of 1 thry 6. ii) Upon a path weight in a given cell exceeding a preset threshold value, that vector and cell reference is added to a global graph. iii) Upon a path weight in a given cell falling below the same threshhold value, the vector and cell are removed from the global graph. iv) To do path analysis, a graph is built as in a thru g from the starting location until a high path weight intersection with the global graph is found. v) Similarly a graph from the target location to the global graph is built. vi) The resultant path is the highest path weight path from the start location, to the global graph, followed by the highest path weight path from there to the intersection found in #vi, and from there back to the target. -- J C Lawrence Internet: claw#kanga,nu (Contractor) Internet: coder#kanga,nu ---------(*) Internet: claw#under,engr.sgi.com ...Honorary Member of Clan McFud -- Teamer's Avenging Monolith... </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="00215" HREF="msg00215.html">[MUD-Dev] Re: mobile movement</A></strong> <ul compact><li><em>From:</em> Ling <K.L.Lo-94#student,lboro.ac.uk></li></ul> </UL></LI></UL> <!--X-Follow-Ups-End--> <!--X-References--> <UL><LI><STRONG>References</STRONG>: <UL> <LI><STRONG><A NAME="00126" HREF="msg00126.html">[MUD-Dev] Re: mobile movement</A></STRONG> <UL><LI><EM>From:</EM> Ling <K.L.Lo-94#student,lboro.ac.uk></LI></UL></LI> </UL></LI></UL> <!--X-References-End--> <!--X-BotPNI--> <UL> <LI>Prev by Date: <STRONG><A HREF="msg00140.html">[MUD-Dev] Re: Levels versus Skills, who uses them and when.</A></STRONG> </LI> <LI>Next by Date: <STRONG><A HREF="msg00142.html">[MUD-Dev] Re: Levels versus Skills, who uses them and when.</A></STRONG> </LI> <LI>Prev by thread: <STRONG><A HREF="msg00128.html">[MUD-Dev] Re: mobile movement</A></STRONG> </LI> <LI>Next by thread: <STRONG><A HREF="msg00215.html">[MUD-Dev] Re: mobile movement</A></STRONG> </LI> <LI>Index(es): <UL> <LI><A HREF="index.html#00141"><STRONG>Date</STRONG></A></LI> <LI><A HREF="thread.html#00141"><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>[MUD-Dev] Re: mobile movement</STRONG>, <EM>(continued)</EM> <ul compact> <ul compact> <LI><strong><A NAME="00114" HREF="msg00114.html">[MUD-Dev] Re: mobile movement</A></strong>, Ling <a href="mailto:K.L.Lo-94#student,lboro.ac.uk">K.L.Lo-94#student,lboro.ac.uk</a>, Tue 12 Jan 1999, 15:41 GMT <UL> <LI><strong><A NAME="00120" HREF="msg00120.html">[MUD-Dev] Re: mobile movement</A></strong>, J C Lawrence <a href="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</a>, Wed 13 Jan 1999, 00:21 GMT <UL> <LI><strong><A NAME="00126" HREF="msg00126.html">[MUD-Dev] Re: mobile movement</A></strong>, Ling <a href="mailto:K.L.Lo-94#student,lboro.ac.uk">K.L.Lo-94#student,lboro.ac.uk</a>, Wed 13 Jan 1999, 01:33 GMT <UL> <LI><strong><A NAME="00128" HREF="msg00128.html">[MUD-Dev] Re: mobile movement</A></strong>, Marc Hernandez <a href="mailto:marc#ias,jb.com">marc#ias,jb.com</a>, Wed 13 Jan 1999, 04:26 GMT </LI> <LI><strong><A NAME="00141" HREF="msg00141.html">[MUD-Dev] Re: mobile movement</A></strong>, J C Lawrence <a href="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</a>, Wed 13 Jan 1999, 22:33 GMT <UL> <LI><strong><A NAME="00215" HREF="msg00215.html">[MUD-Dev] Re: mobile movement</A></strong>, Ling <a href="mailto:K.L.Lo-94#student,lboro.ac.uk">K.L.Lo-94#student,lboro.ac.uk</a>, Sun 17 Jan 1999, 12:44 GMT </LI> </UL> </LI> </UL> </LI> <LI><strong><A NAME="00133" HREF="msg00133.html">[MUD-Dev] Re: mobile movement</A></strong>, Holly Sommer <a href="mailto:hsommer#micro,ti.com">hsommer#micro,ti.com</a>, Wed 13 Jan 1999, 16:13 GMT </LI> </UL> </LI> </UL> </LI> </ul> <LI><strong><A NAME="00129" HREF="msg00129.html">[MUD-Dev] Re: mobile movement</A></strong>, Chris Gray <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Wed 13 Jan 1999, 05:25 GMT </LI> <LI><strong><A NAME="00135" HREF="msg00135.html">[MUD-Dev] Re: mobile movement</A></strong>, Caliban Tiresias Darklock <a href="mailto:caliban#darklock,com">caliban#darklock,com</a>, Wed 13 Jan 1999, 18:22 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>