At the moment I have some very vindictive mobs, that not only remember a player but will also activley seek them out, unfortunately the system used to choose their next move is almost guaranteed to lead them to the target. Now I want to change this to use the traking skill (builders can asign skills to mobs by specifying a range (or just a min as a fixed value, but that is discouraged) to decide the next step, this frees me from having to use any graphing algorithms, and seems more realistic, if a player can hide their tracks well enough, or lay a set of false tracks that are good enough then the mob should be thrown off. But, I am in the middle of rewriting how tracks and tracking are handled, and I am back on the issue of CPU vs Memory usage, I would like to have the tack information stored in a list (prob really an array *shrug* ) associated with each exit of each room, but if you have a struct for the track information (who, ttl, ifReal, amtHidden - all bytes would be good, since it puts the size of the struct on a 32bit word boundary), and an array of 8 of these on each of 10 exits (n, ne, e, se, s, sw, w, nw, u, d), you have   4 * 8 * 10 = 320 bytes of data, just on track information, for each room, and that is using the smallest amount of information I can (which would mean I couldn't have more than 255 players and mobs - unrealistic I know, just an example).

So, how do other people handle it? Do people use a complicated but hopefully more realistic method, or go for quick and simple. Also once you start adding in scents....

In a word: Simple

Each of our rooms has 1 set of tracks, in 1 direction, at any time. I would think you only need more if player's tracks are likely to cross.

If you need more, then I would assign a disappearance time to each set of tracks in a room, so you'd free memory as old tracks disappeared, and each time a new player entered/left the room add a new track description to the list.

Any tracks I use will have a ttl (Time To Live), it's more an issue of how much to keep, say 6 sets of tracks for a room, or 4 for each exit (possibly 40 per room)..

If you're going the TTL route for your tracks,  you can save oodles of memory by only using dynamically assigned tracks as players move around your world.

Something like this (I don't remember the memory macro names off the top of my head, but you will).

[code]
void playerleft(player, room, direction)
{
struct track *p,*track,tracknext;

 /* first clean out expired or trampled over tracks */
 for(p=NULL,track=room->firsttrack;track;track=tracknext)
 {
    tracknext=track->next;
    if(track->dir = direction || ttl_expired(track))
    {/* these tracks should go */
       if(p)
         p->next=tracknext;
       else
         room->firsttrack=tracknext;
       STRFREE(track->playername);
       DISPOSE(track);
    }
    else
    {/* these tracks don't disappear yet.  keep them. */
      p=track;
    }
 }

 /* fill out new track struct for current player */
 track=ALLOCATE(struct track);
 track->dir = direction;
 track->playername = STRALLOC(player->name);
 track->ttl = make_ttl( TRACK_TTL );

/* add fresh tracks to room */
 track->next=room->firsttrack;
 room->firsttrack=track;
}

[/quote]

Example: Joe just left west.

We scan the list of current tracks in the room, looking for any that went out the west exit.  Dispose those since Joe would have trampled over them.  We also dispose any which have  expired TTL.

We allocate a new track structure.  Fill it out with whatever info you want, plus TTL

Finally add Joe's tracks to the room.  We are done.


This algorithm doesn't need a mostly empty 4*8*10 array per room, just a hook (firsttrack) to hang the first set of tracks in the room.

Rooms that don't get visited often may wind up with a lot of expired tracks that never get cleared unless someone visits the room.  

A nice low-CPU lazy way to clean these up costs you a single integer:  next_vnum_to_clean.

Once per update:

[code]
for(i=0;i<MAX_ROOMCLEANING_PER_UPDATE;i++)
{
if (next_vnum_to_clean IS a valid room number)
{
   scan list of all tracks in the room.
   dispose those that have expired TTL.
}
if(++next_vnum_to_clean>=MAX_ROOM_VNUM)
  next_vnum_to_clean = 0; /* or 1. it matters little */
}

[/quote]

This will guarantee you will not have tracks older than

oldest track age = ( MAX_ROOM_VNUM / MAX_ROOMCLEANING_PER_UPDATE ) * update_period

and it only costs the CPU checking at most MAX_ROOM_CLEANING_PER_UPDATE rooms per update.


Hope this helps.