Ticket #156: generate.c

/* File: generate.c */

/* 
 * Dungeon generation
 *
 * Code for making, stocking, and populating levels when generated.  
 * Includes rooms of every kind, pits, vaults (inc. interpretation of 
 * vault.txt), streamers, tunnelling, etc.  Level feelings and other 
 * messages, autoscummer behavior.  Creation of the town.
 *
 * Copyright (c) 2001 Ben Harrison, James E. Wilson, Robert A. Koeneke
 *
 * This software may be copied and distributed for educational, research,
 * and not for profit purposes provided that this copyright and statement
 * are included in all such copies.  Other copyrights may also apply.
 */

#include "angband.h"



/*
 * Level generation is not an important bottleneck, though it can be 
 * annoyingly slow on older machines...  Thus we emphasize simplicity 
 * and correctness over speed.  See individual functions for notes.
 *
 * This entire file is only needed for generating levels.
 * This may allow smart compilers to only load it when needed.
 *
 * The "vault.txt" file is used to store vault generation info.
 */


/*
 * Dungeon generation values
 */
#define DUN_ROOMS                       30      /* Number of rooms to attempt */
#define DEST_LEVEL_CHANCE       30      /* 1/chance of being a destroyed level */


/*
 * Dungeon tunnel generation values
 */
#define DUN_TUN_RND     30      /* 1 in # chance of random direction */
#define DUN_TUN_ADJ     10      /* 1 in # chance of adjusting direction */
#define DUN_TUN_PEN     35      /* Chance of doors at room entrances */
#define DUN_TUN_JCT     70     /* Chance of doors at tunnel junctions */

/*
 * Dungeon streamer generation values
 */
#define DUN_STR_WID     2       /* Width of streamers (can sometimes be higher) */
#define DUN_STR_MAG     3       /* Number of magma streamers */
#define DUN_STR_MC      70      /* 1/chance of treasure per magma */
#define DUN_STR_QUA     2       /* Number of quartz streamers */
#define DUN_STR_QC      35      /* 1/chance of treasure per quartz */
#define DUN_STR_CHG     16      /* 1/(4 + chance) of altering direction */

/*
 * Dungeon treasure allocation values
 */
#define DUN_AMT_ROOM    9       /* Amount of objects for rooms */
#define DUN_AMT_ITEM    3       /* Amount of objects for rooms/corridors */
#define DUN_AMT_GOLD    3       /* Amount of treasure for rooms/corridors */

/*
 * Hack -- Dungeon allocation "places"
 */
#define ALLOC_SET_CORR          1       /* Hallway */
#define ALLOC_SET_ROOM          2       /* Room */
#define ALLOC_SET_BOTH          3       /* Anywhere */

/*
 * Hack -- Dungeon allocation "types"
 */
#define ALLOC_TYP_RUBBLE        1       /* Rubble */
#define ALLOC_TYP_TRAP          3       /* Trap */
#define ALLOC_TYP_GOLD          4       /* Gold */
#define ALLOC_TYP_OBJECT        5       /* Object */


/*
 * Maximum numbers of rooms along each axis (currently 6x18)
 */
#define MAX_ROOMS_ROW   (DUNGEON_HGT / BLOCK_HGT)
#define MAX_ROOMS_COL   (DUNGEON_WID / BLOCK_WID)

/*
 * Maximal number of room types
 */
#define ROOM_MAX        8

/*
 * Bounds on some arrays used in the "dun_data" structure.
 * These bounds are checked, though usually this is a formality.
 */
#define CENT_MAX        DUN_ROOMS
#define DOOR_MAX        100
#define WALL_MAX        40
#define TUNN_MAX        300
#define STAIR_MAX       30

/*
 * Simple structure to hold a map location
 */
typedef struct coord coord;

struct coord
{
        byte y;
        byte x;
};

/*
 * Structure to hold all dungeon generation data
 */

typedef struct dun_data dun_data;

struct dun_data
{
        /* Array of centers of rooms */
        int cent_n;
        coord cent[CENT_MAX];

        /* Array to store whether rooms are connected or not. */
        bool connected[CENT_MAX];

        /* Array of possible door locations */
        int door_n;
        coord door[DOOR_MAX];

        /* Array of wall piercing locations */
        int wall_n;
        coord wall[WALL_MAX];

        /* Array of tunnel grids */
        int tunn_n;
        coord tunn[TUNN_MAX];

        /* Array of good potential stair grids */
        int stair_n;
        coord stair[STAIR_MAX];

        /* Number of blocks along each axis */
        int row_rooms;
        int col_rooms;

        /* Array to store block usage */
        int room_map[MAX_ROOMS_ROW][MAX_ROOMS_COL];
};

/*
 * Dungeon generation data -- see "cave_gen()"
 */
static dun_data *dun;


/*
 * Room type information
 */
typedef struct room_data room_data;

struct room_data
{
        /* Allocation information. */
        s16b room_gen_num[11];

        /* Minimum level on which room can appear. */
        byte min_level;
};

/*
 * Table of values that control how many times each type of room will, 
 * on average, appear on 100 levels at various depths.  Each type of room 
 * has its own row, and each column corresponds to dungeon levels 0, 10, 
 * 20, and so on.  The final value is the minimum depth the room can appear 
 * at.  -LM-
 *
 * Level 101 and below use the values for level 100.
 *
 * Rooms with lots of monsters or loot may not be generated if the object or 
 * monster lists are already nearly full.  Rooms will not appear above their 
 * minimum depth.  No type of room (other than type 1) can appear more than 
 * DUN_ROOMS/2 times in any level.
 *
 * The entries for room type 1 are blank because these rooms are built once 
 * all other rooms are finished -- until the level fills up, or the room 
 * count reaches the limit (DUN_ROOMS).
 */
static room_data room[ROOM_MAX] = 
{
   /* Depth:          0   10   20   30   40   50   60   70   80   90  100   min */

   /* Nothing */  {{  0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0 },  0 },
   /* Simple */   {{  0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0 },  0 },
   /* Overlap */  {{ 60,  80, 100, 120, 140, 165, 180, 200, 220, 240, 260 },  1 },
   /* Cross */    {{  0,  25,  50,  70,  85, 100, 110, 120, 130, 140, 150 },  3 },
   /* Large */    {{  0,  25,  50,  70,  85, 100, 110, 120, 130, 140, 150 },  3 },
   /* Pit      */ {{  0,   6,  13,  28,  35,  40,  45,  45,  45,  45,  45 },  5 },
   /* L. Vault */ {{  0,   1,   4,   9,  16,  27,  40,  55,  70,  80,  90 },  5 },
   /* G. Vault */ {{  0,   0,   1,   2,   3,   4,   6,   7,   8,  10,  12 }, 20 }
};



/*
 * This table takes a depth, and returns a suitable monster symbol.  Depth 
 * input is assumed to be player depth.  It is also assumed that monsters 
 * can be generated slightly out of depth.  -LM-
 *
 * Depths greater than 60 should map to the row for level 60.
 *
 * - Symbol '*' is any creature of a randomly-chosen racial char.
 * - Symbol '1' is any animal.
 * - Symbol '2' is any insect ('a', 'c', 'l', 'F', 'I', 'K').
 * - Symbol '3' is any naga, snake, hydra, or other reptile.
 * - Symbol '4' is any jelly, mold, icky thing ('i', 'j', or 'm').
 *
 * - Symbol '%' is any orc, ogre, troll, or giant.
 * - Symbol 'N' is any undead.  Upon occasion, deep in the dungeon, the 
 *   racial type may be forced to 'G', 'L', 'V', or 'W'.
 * - Symbols 'p' and 'h' may sometimes be found in combination.  If they 
 *   are, they are usually all of a given class (magical, pious, natural, 
 *   assassination/thievery, or warrior)
 * - Symbols 'E' and 'v' may be found in combination.  If they are, they 
 *   will always be of a given elemental type.
 * - Symbols 'd' and 'D' both mean dragons of either char.  Dragons are 
 *   often of a particular type (blue, red, gold, shadow/ethereal etc.).
 * - Symbols 'u' and 'U' may mean lesser demons, greater demons, or both, 
 *   depending on depth. 
 * - Symbol 'A' is angels.
 * 
 * - Other symbols usually represent specific racial characters.
 *
 * 80% of the time, one of the first seven characters will be chosen.  
 * 20% of the time, one of the last six will be.
 */
static char mon_symbol_at_depth[12][13] = 
{
        /*      common pits                            rare pits         */

        /* Levels 5, 10, 15, and 20 */
        {'1', '1', '4', '4', '4', 'k', 'y',   '*', '*', '2', 'a', '3', 'S' },
        {'1', '4', '4', 'o', 'o', 'N', '2',   '*', 'C', 'f', 'a', '3', 'S' },
        {'1', '4', 'o', 'o', 'o', 'u', '*',   '#', '#', 'S', 'E', '3', 'Z' },
        {'1', '4', '4', 'o', 'T', 'T', '#',   'p', 'h', 'f', '2', '*', 'Z' },

        /* Levels 25, 30, 35, and 40 */
        {'1', '4', 'T', 'T', 'u', 'P', 'P',   'p', 'v', 'd', '2', 'S', '3' },
        {'1', '1', 'T', 'P', 'P', 'N', 'd',   'p', 'h', 'f', 'v', 'g', 'Z' },
        {'1', '4', 'T', 'P', 'N', 'u', 'd',   'p', 'H', 'E', '2', '*', '3' },
        {'1', '1', 'T', 'P', 'N', 'u', 'd',   'p', 'h', 'g', 'E', '*', 'Z' },

        /* Levels 45, 50, 55, and 60 */
        {'1', 'P', 'N', 'u', 'd', 'd', '*',   'p', 'h', 'v', 'E', '*', 'Z' },
        {'N', 'N', 'U', 'U', 'D', 'D', '*',   'p', 'h', 'v', 'T', 'B', 'Z' },
        {'1', 'N', 'U', 'U', 'D', 'D', '*',   'p', 'h', 'W', 'G', '*', 'Z' },
        {'N', 'N', 'U', 'U', 'D', 'D', '*',   'p', 'h', 'v', '*', 'D', 'Z' } 
};

/* 
 * Restrictions on monsters, used in pits, etc.
 */
static bool allow_unique;
static char d_char_req[10];
static byte d_attr_req[4];
static u32b racial_flag_mask;
static u32b breath_flag_mask;



/*
 * Table of monster descriptions.  Used to make descriptions for kinds 
 * of pits and rooms of chambers that have no special names.
 */
cptr d_char_req_desc[] =
{
        "B:bird",
        "C:canine",
        "D:dragon",
        "E:elemental",
        "F:dragon fly",
        "G:ghost",
        "H:hybrid",
        "I:insect",
        "J:snake",
        "K:killer beetle",
        "L:lich",
        "M:multi-headed hydra",
        "O:ogre",
        "P:giant",
        "Q:quylthulg",
        "R:reptile",
        "S:spider",
        "T:troll",
        "U:demon",
        "V:vampire",
        "W:wraith",
        "Y:yeti",
        "Z:zephyr hound",
        "a:ant",
        "b:bat",
        "c:centipede",
        "d:dragon",
        "e:floating eye",
        "f:feline",
        "g:golem",
        "h:humanoid",
        "i:icky thing",
        "j:jelly",
        "k:kobold",
        "l:louse",
        "m:mold",
        "n:naga",
        "o:orc",
        "p:human",
        "q:quadruped",
        "r:rodent",
        "s:skeleton",
        "t:townsperson",
        "u:demon",
        "v:vortex",
        "w:worm",
        "y:yeek",
        "z:zombie",
        ",:mushroom patch",
        NULL
};




/**************************************************************/
/*                                                            */
/*                 The monster-selection code                 */
/*                                                            */
/**************************************************************/


/*
 * Use various selection criteria (set elsewhere) to restrict monster 
 * generation.
 *
 * This function is capable of selecting monsters by:
 *   - racial symbol (may be any of the characters allowed)
 *   - symbol color (may be any of up to four colors).
 *   - racial flag(s) (monster may have any allowed flag)
 *   - breath flag(s) (monster must have exactly the flags specified)
 *
 * Uniques may be forbidden, or allowed on rare occasions.
 *
 * Some situations (like the elemental war themed level) require special 
 * processing; this is done in helper functions called from this one.
 */
static bool mon_select(int r_idx)
{
        monster_race *r_ptr = &r_info[r_idx];
        bool ok = FALSE;


        /* Require that the monster symbol be correct. */
        if (d_char_req[0] != '\0')
        {
                if (strchr(d_char_req, r_ptr->d_char) == 0) return (FALSE);
        }

        /* Require correct racial type. */
        if (racial_flag_mask)
        {
                if (!(r_ptr->flags3 & (racial_flag_mask))) return (FALSE);

                /* Hack -- no invisible undead until deep. */
                if ((p_ptr->depth < 40) && (r_ptr->flags3 & (RF3_UNDEAD)) && 
                        (r_ptr->flags2 & (RF2_INVISIBLE))) return (FALSE);
        }

        /* Require that monster breaths be exactly those specified. */
        if (breath_flag_mask)
        {
                if (r_ptr->flags4 != breath_flag_mask) return (FALSE);
        }

        /* Require that the monster color be correct. */
        if (d_attr_req[0])
        {
                /* Check all allowed colors, if given. */
                if ((d_attr_req[0]) && (r_ptr->d_attr == d_attr_req[0])) ok = TRUE;
                if ((d_attr_req[1]) && (r_ptr->d_attr == d_attr_req[1])) ok = TRUE;
                if ((d_attr_req[2]) && (r_ptr->d_attr == d_attr_req[2])) ok = TRUE;
                if ((d_attr_req[3]) && (r_ptr->d_attr == d_attr_req[3])) ok = TRUE;

                /* Hack -- No multihued dragons allowed in the arcane dragon pit. */
                if ((strchr(d_char_req, 'd') || strchr(d_char_req, 'D')) && 
                        (d_attr_req[0] == TERM_VIOLET) && 
                        (r_ptr->flags4 == (RF4_BR_ACID | 
                                RF4_BR_ELEC | RF4_BR_FIRE | 
                                RF4_BR_COLD | RF4_BR_POIS)))
                {
                        return (FALSE);
                }

                /* Doesn't match any of the given colors?  Not good. */
                if (!ok) return (FALSE);
        }

        /* Usually decline unique monsters. */
        if (r_ptr->flags1 & (RF1_UNIQUE))
        {
                if (!allow_unique) return (FALSE);
                else if (rand_int(5) != 0) return (FALSE);
        }

        /* Okay */
        return (TRUE);
}


/*
 * Accept characters representing a race or group of monsters and 
 * an (adjusted) depth, and use these to set values for required racial 
 * type, monster symbol, monster symbol color, and breath type.  -LM-
 *
 * This function is called to set restrictions, point the monster 
 * allocation function to "mon_select()", and remake monster allocation.  
 * It undoes all of this things when called with the symbol '\0'.
 * 
 * Describe the monsters (used by cheat_room) and determine if they 
 * should be neatly ordered or randomly placed (used in monster pits).
 */
static char *mon_restrict(char symbol, byte depth, bool *ordered, bool unique_ok)
{
        int i, j;

        /* Assume no definite name */
        char name[80] = "misc";

        /* Clear global monster restriction variables. */
        allow_unique = unique_ok;
        for (i = 0; i < 10; i++) d_char_req[i] = '\0';
        for (i = 0; i < 4; i++) d_attr_req[i] = 0;
        racial_flag_mask = 0; breath_flag_mask = 0;


        /* No symbol, no restrictions. */
        if (symbol == '\0')
        {
                get_mon_num_hook = NULL;
                get_mon_num_prep();
                return ("misc");
        }

        /* Handle the "wild card" symbol '*'  */
        if (symbol == '*')
        {
                for (i = 0; i < 2500; i++)
                {
                        /* Get a random monster. */
                        j = randint(z_info->r_max - 1);

                        /* Must be a real monster */
                        if (!r_info[j].rarity) continue;

                        /* Try for close to depth, accept in-depth if necessary */
                        if (i < 200)
                        {
                                if ((!(r_info[j].flags1 & RF1_UNIQUE)) && 
                                      (r_info[j].level != 0) && 
                                      (r_info[j].level <= depth) && 
                                      (ABS(r_info[j].level - p_ptr->depth) < 
                                      1 + (p_ptr->depth / 4))) break;
                        }
                        else
                        {
                                if ((!(r_info[j].flags1 & RF1_UNIQUE)) && 
                                      (r_info[j].level != 0) && 
                                      (r_info[j].level <= depth)) break;
                        }
                }

                /* We've found a monster. */
                if (i < 2499)
                {
                        /* ...use that monster's symbol for all monsters. */
                        symbol = r_info[j].d_char;
                }
                else
                {
                        /* Paranoia - pit stays empty if no monster is found */
                        return (NULL);
                }
        }

        /* Apply monster restrictions according to symbol. */
        switch (symbol)
        {
                /* All animals */
                case '1':
                {
                        strcpy(name, "animal");
                        racial_flag_mask = RF3_ANIMAL;
                        *ordered = FALSE;
                        break;
                }

                /* Insects */
                case '2':
                {
                        strcpy(name, "insect");
                        strcpy(d_char_req, "aclFIK");
                        *ordered = FALSE;
                        break;
                }

                /* Reptiles */
                case '3':
                {
                        strcpy(name, "reptile");
                        strcpy(d_char_req, "nJRM");
                        *ordered = FALSE;
                        break;
                }

                /* Jellies, etc. */
                case '4':
                {
                        strcpy(name, "jelly");
                        strcpy(d_char_req, "ijm,");
                        *ordered = FALSE;
                        break;
                }

                /* Humans and humaniods */
                case 'p':
                case 'h':
                {
                        /* 'p's and 'h's can coexist. */
                        if (rand_int(3) == 0) 
                        {
                                strcpy(d_char_req, "ph");

                                /* If so, they will usually all be of similar classes. */
                                if (rand_int(4) != 0)
                                {
                                        /* Randomizer. */
                                        i = rand_int(5);

                                        /* Magicians and necromancers */
                                        if (i == 0)
                                        {
                                                d_attr_req[0] = TERM_RED;
                                                d_attr_req[1] = TERM_L_RED;
                                                d_attr_req[2] = TERM_VIOLET;
                                                strcpy(name, "school of sorcery");
                                        }
                                        /* Priests and paladins */
                                        else if (i == 1)
                                        {
                                                d_attr_req[0] = TERM_GREEN;
                                                d_attr_req[1] = TERM_L_GREEN;
                                                d_attr_req[2] = TERM_WHITE;
                                                d_attr_req[3] = TERM_L_WHITE;
                                                strcpy(name, "temple of piety");
                                        }
                                        /* Druids and ninjas */
                                        else if (i == 2)
                                        {
                                                d_attr_req[0] = TERM_ORANGE;
                                                d_attr_req[1] = TERM_YELLOW;
                                                strcpy(name, "gathering of nature");
                                        }
                                        /* Thieves and assassins */
                                        else if (i == 3)
                                        {
                                                d_attr_req[0] = TERM_BLUE;
                                                d_attr_req[1] = TERM_L_BLUE;
                                                d_attr_req[2] = TERM_SLATE;
                                                d_attr_req[3] = TERM_L_DARK;
                                                strcpy(name, "den of thieves");
                                        }
                                        /* Warriors and rangers */
                                        else 
                                        {
                                                d_attr_req[0] = TERM_UMBER;
                                                d_attr_req[1] = TERM_L_UMBER;
                                                strcpy(name, "fighter's hall");
                                        }
                                }
                                else
                                {
                                        strcpy(name, "humans and humaniods");
                                }
                        }

                        /* Usually, just accept the symbol. */
                        else 
                        {
                                d_char_req[0] = symbol;

                                if (symbol == 'p') strcpy(name, "human");
                                else if (symbol == 'h') strcpy(name, "humanoid");
                        }

                        *ordered = FALSE;
                        break;
                }

                /* Orcs */
                case 'o':
                {
                        strcpy(name, "orc");
                        strcpy(d_char_req, "o");
                        *ordered = TRUE;
                        break;
                }

                /* Trolls */
                case 'T':
                {
                        strcpy(name, "troll");
                        strcpy(d_char_req, "T");
                        *ordered = TRUE;
                        break;
                }

                /* Giants (sometimes ogres at low levels) */
                case 'P':
                {
                        strcpy(name, "giant");
                        if ((p_ptr->depth < 30) && (rand_int(3) == 0)) 
                             strcpy(d_char_req, "O");
                        else strcpy(d_char_req, "P");
                        *ordered = TRUE;
                        break;
                }

                /* Orcs, ogres, trolls, or giants */
                case '%':
                {
                        strcpy(name, "moria");
                        strcpy(d_char_req, "oOPT");
                        *ordered = FALSE;
                        break;
                }

                /* Monsters found in caves */
                case '0':
                {
                        strcpy(name, "dungeon monsters");
                        strcpy(d_char_req, "ykoOT");
                        *ordered = FALSE;
                        break;
                }



                /* Undead */
                case 'N':
                {
                        /* Sometimes, restrict by symbol. */
                        if ((depth > 40) && (rand_int(3) == 0))
                        {
                                for (i = 0; i < 500; i++)
                                {
                                        /* Find a suitable monster near depth. */
                                        j = randint(z_info->r_max - 1);

                                        /* Require a non-unique undead. */
                                        if ((r_info[j].flags3 & RF3_UNDEAD) && 
                                            (!(r_info[j].flags1 & RF1_UNIQUE)) && 
                                            (strchr("GLWV", r_info[j].d_char)) && 
                                            (ABS(r_info[j].level - p_ptr->depth) < 
                                            1 + (p_ptr->depth / 4)))
                                        {
                                                break;
                                        }
                                }

                                /* If we find a monster, */
                                if (i < 499)
                                {
                                        /* Use that monster's symbol for all monsters */
                                        d_char_req[0] = r_info[j].d_char;

                                        /* No pit name (yet) */

                                        /* In this case, we do order the monsters */
                                        *ordered = TRUE;
                                }
                                else
                                {
                                        /* Accept any undead. */
                                        strcpy(name, "undead");
                                        racial_flag_mask = RF3_UNDEAD;
                                        *ordered = FALSE;
                                }
                        }
                        else
                        {
                                /* No restrictions on symbol. */
                                strcpy(name, "undead");
                                racial_flag_mask = RF3_UNDEAD;
                                *ordered = FALSE;
                        }
                        break;
                }

                /* Demons */
                case 'u':
                case 'U':
                {
                        strcpy(name, "demon");
                        if (depth > 55)      strcpy(d_char_req, "U");
                        else if (depth < 40) strcpy(d_char_req, "u");
                        else                 strcpy(d_char_req, "uU");
                        *ordered = TRUE;
                        break;
                }

                /* Dragons */
                case 'd':
                case 'D':
                {
                        strcpy(d_char_req, "dD");

                        /* Dragons usually associate with others of their kind. */
                        if (rand_int(6) != 0)
                        {
                                /* Dragons of a single kind are ordered. */
                                *ordered = TRUE;

                                /* Some dragon types are not found everywhere */
                                if (depth > 70) i = rand_int(35);
                                else if (depth > 45) i = rand_int(32);
                                else if (depth > 32) i = rand_int(30);
                                else if (depth > 23) i = rand_int(28);
                                else i = rand_int(24);

                                if (i < 4)
                                {
                                        breath_flag_mask = (RF4_BR_ACID);
                                        strcpy(name, "dragon - acid");
                                }
                                else if (i < 8)