Re: Arrays and Linked Lists (long)

From: Anil Mahajan (amahajan@PROXICOM.COM)
Date: 04/27/00

On Wed, 26 Apr 2000 17:21:59 PDT, Zachary Tellman <>

>I searched the archives for previous posts regarding storing the world
>within an array and found some references, but no real practical advice on
>how to create one.  The reason a linked list was used was because linked
>lists have no boundaries or limits, while one must define the limits,
>creating waste or too many rooms.  However, it appears that an array will
>make things infinitely simpler for my mud.  So, my question is this: What's
>a practical manner in which I can discover the required limits for an array
>with minimal time and memory?  Actual code isn't required, rather just an
>explanation of the mechanics.

I re-implemented most of the arrays as binary trees on my mud.
It's a pretty painful process.  But there are some definate advantages
(but you loose a whole lot of compatability with circle).

The way i did it was to use nested BTrees.  (I coded them myself the
first time through,  then wanted to upgrade to AVL trees (which would
have been a great deal harder to program) but found an AVL C package).

The zones are held in one 'world' B-tree.

Each zone contains 3 B-trees and an array.  It has a Room tree, a
mob tree, and an object tree.  The array is for shops.

The object and mobile trees hold prototypes for the actual objects and
mobiles.  When a mob is created it's copied from the prototypes structure.
And, if the prototype is replaced, all mobs created afterwards are then
based off of the new prototype (which is how my crappy OLC system works).
The actual mobs and objects are held, like normal in global linked lists.

The room tree is the actual room data.

Because of this system referencing things changes.  There are no longer
VNUMS and RNUMS.  Now, we just have the builder speicifed number (RNUM).
But, the rnum isn't referenced in the same way anymore.  Because we have
to search 2 trees to get to any single object, things need be referenced
by ZONE and RNUM.  So, if i was to go to the immortal lounge, this would
be zone 12 room 04 (you will need to modify every statement that uses
rnums and vnums, and every command that accesses items (load, vnum, etc)).

This is a big change.  Of course it makes it so that the size limit on your
world is immense (2^32 max zones, and 2^32 max things in each zone).

This cascades into other improvements and changes that you can make.
I've got segmented zones (you can specify sub-zones in each zone for
difference reset timings, and behaviours).  Adding and removing things
becomes rather easy.  I actually installed this system for the ability
to do this with rooms (my worldmap system is based off of creating rooms
on the fly).

It also cascades into lots of changes and incompatabilities with Circle.
Objects who's values represent other objects (door exits, door keys, etc)
all need to be able to reference both Zone and Number now -- so now your
areas aren't compatable anymore.  Finding a 'random' room becomes a
difficult process, too.

It took me a good week of solid coding (and doing nothing else), to get
the B-tree's up and running with the mud.  Then it was a long process
of finding incompatabilities and stuff.  I think it was worth it, except
it makes patching my circleMud a bit of a pain (but I guess any major change
has that problem).

Here's the structure for my base tree element (the zone struct):
/* this is an individual zone.
** it has pointers to the rooms, mobs, objs.
struct world_zone_list {
  int zone_nr,                          /* this zone's number             */
      room_count,                       /* number of rooms in the zone    */
      obj_count,                        /* number of obj proto's in zone  */
      mob_count;                        /* number of mob proto's in zone  */
  AVL_TREE rooms;                       /* rooms in this zone             */
  AVL_TREE objs;                        /* objects in this zone           */
  AVL_TREE mobs;                        /* mobs in this zone              */
  struct shop_data *shops;              /* shop list                      */

  char *mobfile;
  char *objfile;
  char *wldfile;
  char *zonfile;
  char *shpfile;

I hope this helps you out some.  It's been ages since I coded this, so
my memory is a bit faint on it... fainter still because I haven't even
really touched my MUD in 6 months (maybe i should just release the code?).

- Anil
RoadKill@F.U.C.MUD 4000

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

This archive was generated by hypermail 2b30 : 04/10/01 PDT