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