[MUD-Dev] Re: mobile movement

[J C Lawrence]

On Wed, 13 Jan 1999 01:33:30 +0000 (BST) 
Ling <K.L.Lo-94 at 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 at kanga.nu
(Contractor)                             Internet: coder at kanga.nu
---------(*)                    Internet: claw at under.engr.sgi.com
...Honorary Member of Clan McFud -- Teamer's Avenging Monolith...