[MUD-Dev] Re: mobile movement

[Ling]

On Wed, 13 Jan 1999, J C Lawrence wrote:

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

[snip snip!  recap: stuff about highways]

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

Do you quantise your co-ord based mud world into cells at the moment?  If
so, are they oblong cells or irregular 3D blobs?  How do you store mana
density?  On a domain basis?  Or do they look like globes, pin pricks in
space with a radius and falloff?

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

Oh?  Please enlighten!

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

After some thought, the average for two vectors in opposite directions is
zero.  This wouldn't be much of a problem for a true crossroad with four
directions and players running up, down, left and right.  The above would
indicate any cell to have no net drift (assuming statistically players
will go from A to B as often as they go from B to A by foot).

Unfortunately, I have no great thoughts upon a solution to this possible
problem.  I suppose it's all down to the post-processing data merging bit,
step #5.  A good algorithm that will extract discrete directions players
tend to go is needed here. 

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

Looks like a very large weather map.  Npcs move with the grace of airships
in a very strong hurricane.

Another random thought I had.  Link mana to be inversely proportional to
the traffic in a cell.  Think of it as players leaving a wake in the mana
ocean.  It'll make popular spots and highways contain less mana and
possibly safer places.  Players will also find they're forced to go look
for new, exciting places while I'll refuse to come out of my cubby hole. 

Side effect is that you could use the wake as a method to track people
down.  Buzzing cities will have very little mana whilst the quiet village
will still have a good amount.  It'll also make armies useful against
mages provided they can overrun the mana ocean (mages, never pick a fight
with an army on their home turf). 

  |    Ling Lo (aka Stressed Lad)
_O_O_  kllo at iee.org