Or How to have LOTS of monsters and LOTS of treasure in your Roguelike.

    Here are some tips for conserving precious heap space, so that you
will be able to populate each of your dungeon levels with as many 
monsters and items as you want! This is a good alternative to having to
write a protected mode program, and while it may be a little too slow
for some 386s, the algorithms can be tuned as needed. The basic concept
is that you will only store in RAM as little as you possibly need to 
know about all the monsters and items. All the rest of the stuff 
(specific information about a monster or item) you store on the 
player's hard drive. The speed versus memory usage trade-off is obvious.
You will use a lot less RAM by only storing the indices into the disk
files in a linked list in memory, but your game will be slightly slower
because you must frequently return to the hard drive and read/write
information from it (this is VERY slow compared to reading/writing from
RAM).

Anyway, here is some sample code for storing indices for monsters and
items using ANSI C and assuming that each of your dungeon levels is 80
cells by 25 cells, for a total of 2000 square cells  (this may be
smaller or larger than what you want for your roguelike). My ANSI C is
pretty rusty (I prefer Pascal) so please be aware that this code does
contain syntax errors.

/////////////////////////////////////////////////////////////////////////////////

// BEGIN CODE FRAGMENT
/////////////////////////////////////////////////////////////////////////////////

    #define MAX_ROWS 25
    #define MAX_COLS  80
    typedef unsigned int word;   // 16-bit quantity
    typedef unsigned char byte; // 8-bit quantity
    typedef enum NodeTypes = { MONSTER, ITEMS }; // Different sorts of
data files you will have


/////////////////////////////////////////////////////////////////////////////////

    //  A singly linked list of indices.

/////////////////////////////////////////////////////////////////////////////////

    typedef struct index_list_node;
    typedef index_list_node *index_list_node_ptr;
    struct
    {
         word                       index;
         NodeTypes             node_type;
         index_list_node_ptr link;
     } index_list_node; // Size = 7 bytes
     // Related list functions are new_list(), free_list(),
insert_before(), insert_after(), is_empty(), is_full()
     //  advance_list(), reset_list(), read_list_from_disk(),
write_list_to_disk()


/////////////////////////////////////////////////////////////////////////////////

    //  Records to hold monsters and items on diskette.

/////////////////////////////////////////////////////////////////////////////////

    typedef struct
    {
          byte row, col, depth;
          char symbol; // Whatever data you will have to represent a
monster: name, hit points, AC, etc.
     }monster_record;

    typedef struct
    {
          byte row, col, depth;
          char symbol; // Whatever data you will have to represent an
item: weight, damage, etc.
    }item_record;


/////////////////////////////////////////////////////////////////////////////////

    // Global array of index_list_nodes for each square of the dungeon.
    // Initiallly this array will be MAX_ROWS * MAX_COLS * sizeof
(index_list_node) bytes large
    // 80 * 25 * 7 = 14,000 bytes plus 7 bytes for every monster/item
added.
    // Assuming about 150 monsters and 200 items per level, this gives
you 14,000 + (7 * 350)=16,450 bytes

/////////////////////////////////////////////////////////////////////////////////

    index_list_node object_array[MAX_ROWS][MAX_COLS];


/////////////////////////////////////////////////////////////////////////////////

    // Because the above list will only contain INDICES into permanent
disk files, deleting elements from the list
    // such as when an item is picked up or a monster slain, will be
extremely slow (because the entire level file
    // on disk will have to be re-written minus one single record). To
alleviate this, simply keep a second linked
    // index list of all the indices which need to be deleted from the
permanent disk file when the player leaves this
    // dungeon level (these indices have already been deleted from the
object_array linked lists.) Remember to
    // insert indices into this list EVERY time a monster is killed or
an item is picked up (you might want to
    // have a function delete_monster(which_row, which_col, what_index)
which removes the specified node
    // from the object_array[] linked list and also inserts it into the
deleted_list [Do you see why you need to
    // pass in what_index? That's right, so you can go to the
appropriate (what_row, what_col) element in object_array
    // and traverse that linked list until currPtr->index == what_index,
then you can delete this node and insert the
    // what_index into the deleted_list!] ).

/////////////////////////////////////////////////////////////////////////////////

     index_list_node deleted_list;


/////////////////////////////////////////////////////////////////////////////////

    // You will also have two disk files per dungeon level, one for
MONSTERS and one for ITEMS.
    // You must devise a naming scheme for each (LEVEL01.MON and
LEVEL01.ITM for example)
    // LEVEL01.MON is a random-access file of monster_records and
LEVEL01.ITM is a random-
    // access file of item_records, one record per monster on that level
and one record per item on the
    // level. Note that these disk files may be quite large
(sizeof(monster_record) * num_records bytes).

/////////////////////////////////////////////////////////////////////////////////


/////////////////////////////////////////////////////////////////////////////////

    // stock_depth()
    // Call this function at the start of the game or whenever the level
needs to be completely re-stocked:

/////////////////////////////////////////////////////////////////////////////////

    void stock_depth ()
    {
        // 1. Open the appropriate monster level file (LEVEL01.MON for
example)
        // 2. Read each monster_record one at a time into a local
variable, m
        // 3. Based on the m's (row, col, depth) triple, use the
appropriate element of the global object_array[].
        //     For example, if m.row = 10 and m.col = 10 then
object_array[10][10] would have a singly linked list
        //     of index_list_nodes.
        // 4. Insert the index into the linked list (use insert_after()
from the basic list routines above).
        // 5. Do the same thing for the item level file.
        item_record i;
        monster_record m;
        FILE *infile;
        word index = 0;

        // Add all the monsters to our array of linked lists.
        infile = fopen ("LEVEL01.MON") // This line is not syntactically
correct
        while (!eof(infile))
        {
            fread (infile, m); // Wrong also!
            insert_after (object_array[m.row][m.col], index, MONSTER);
// The index is the record number and the linked list is

// at (m.row, m.col)
            index++;  // Move on to the next record
         }

        // If there are not enough monsters on this level, ADD monsters
until there are enough.

        // Add all the items to our array of linked lists.
        index = 0;
        infile = fopen ("LEVEL01.ITM") // This line is not syntactically
correct
        while (!eof(infile))
        {
            fread (infile, m); // Wrong also!
            insert_after (object_array[i.row][i.col], index, ITEM); //
The index is the record number and the linked list is

// at (m.row, m.col)
            index++;  // Move on to the next record
         }
     }


/////////////////////////////////////////////////////////////////////////////////

    // change_depth()
    // Call this function every time the player changes dungeon levels,
including at the end of the game:

/////////////////////////////////////////////////////////////////////////////////

    void change_depth ()
    {
        // 1. Open the current monster level file (LEVEL01.MON for
example)
        // 2. Open a temporary file
        // 3. Read each record one at a time into a local variable, m.
        // 4. If this record number (index) is NOT in the deleted_list
(see above) then write this
        //     record to the temp file (otherwise DON'T write the record
to the temp file).
        // 5. Close and delete the monster level file.
        // 6. Rename the temp file to the same name as the monster level
file.
        // 7. Now the temp file contains all the records except those
which have been deleted (dead monsters).
        // 8. Do the same with the item level file.
        // 9. Call free_list() to destroy the linked index list.
        // 10. Based on the new depth, call stock_depth() with the new
depth number to load/build the new index_list.
     }


/////////////////////////////////////////////////////////////////////////////////

    // square_has_monster()
    // Simply scan the linked list at object_array[which_row][which_col]
and return TRUE as soon as one of
    // the nodes has a node_type of MONSTER.
    // You can devise a similar function for square_has_item().

/////////////////////////////////////////////////////////////////////////////////

    boolean square_has_monster (byte which_row, byte which_col)
    {
        // List at this square is empty (square has neither monster nor
items)
        if (object_array[which_row][which_col] == NULL) return (FALSE);

        index_list_node currPtr = object_array[which_row][which_col];
        while (currPtr != NULL)
        {
             if (currPtr->node_type == MONSTER) return (TRUE);

             // Move down the list
            currPtr = currPtr->link;
        }
        return (FALSE);
    }

/////////////////////////////////////////////////////////////////////////////////

// END CODE FRAGMENT
/////////////////////////////////////////////////////////////////////////////////