Re: non-recursive tracking algorithm (that works)

From: Gary Barnett (gbarnett@POLARNET.COM)
Date: 10/13/97

On Monday, October 13, 1997 9:41 AM, Sean Butler [SMTP:sbutler@DEVEAST.COM]
> In Circle3 there is a graph.c file which contains the tracking algorithm
> the skill track.  Although this algorithm may have at one time worked okay,
> after extensive changes to rooms, wilderness, etc., it doen't work now.  I
> never liked it anyway.  It is poorly commented and clumsily designed.
> Does anyone have a decent idea as to how to do this the right way.  For
> example, one that doesn't mark the rooms as it goes.  One that doesn't use
> an expensive recursion. One that can be called a thousand times per minute
> without inducing server lag.
> All I am looking for is a desgn, a theory, I don't need the actual code.
> Thanks to any that reply.
I spent a good deal of time thinking about this myself. I haven't translated
my ideas
into code as yet, but here's what I've settled on as a working plan.

1) Create a 3d array of ints to represent a zone. Each room will plug into
the array
   in whatever spot it is in relation to the other rooms. (sparse array)

2) Create a  3d array of bytes to represent the world. Each zone will plug
into the array
    in whatever spot it is in relation to the other zones. (sparse array)

3) (optional) Create an array of ubytes to represent the room. Terrain can be
in the room by storing a terrain # in the correct spot. Creating a standard
for terrain
allows a stream to block movement, a wall to block fire at someone who is
and provides the ability for targeted smoke affects, real sneak, backstab,
etc. The
downside is that you have scaling difficulties in representing different
sized rooms.

4) Create routines to determine the distance and direction to any spot from
    other, and to compute the possiblility of traveling there within the
    of the caller. i.e. someone who is walking w/o a boat vs someone who is
    driving a hovercraft.

This will make the next_step calls in track much faster. Store the rooms that
computed when the call was made, and pop them off the list as you walk each

This will use a fair amount of memory. If written right the routines to
search the
database would be fast enough.

This doesn't replace the directions or any other stock code. I plan on using
it just
to support the lookups needed for the following:

1) Tracking
2) Radio Communication Distances/garbling
3) Trade - Distance from producer to user
4) Artillery and direct fire weapons
5) Air/Sea travel distances/fuel consumption (non-room based)
6) Yell/Shout fadouts
7) Sight Distances
8) Smell (with wind direction)

All of these systems are in, more or less, but tying them to the grid will be
the final piece towards making them useful, integrated components of the mud.


I can picture in my mind a world without war, a world without hate.
And I can picture us attacking that world, because they'd never
expect it.     - Jack Handey

     | Ensure that you have read the CircleMUD Mailing List FAQ:  |
     | |

This archive was generated by hypermail 2b30 : 12/08/00 PST