fiddlerwoaroof/crawl - Change OY7KHQPESOUHPBXRZ2JSNUKPAC7DCDY73TAUHCSJG5V6TPAHBVYQC

Experimental new labyrinth maze generation. The right-hand rule still works;

the maze can be very hard if we make it braided.

git-svn-id: https://crawl-ref.svn.sourceforge.net/svnroot/crawl-ref/trunk@1615 c06c8d41-db1a-0410-9941-cceddc491573

Created by dshaligram on June 21, 2007

OY7KHQPESOUHPBXRZ2JSNUKPAC7DCDY73TAUHCSJG5V6TPAHBVYQC

Dependencies

In channels

main

Change contents

Insertion in crawl-ref/source/dungeon.cc at line 182 [4.3429798]
[2.4768]
[3.821]
```
typedef std::list<coord_def> coord_list;
```

Replacement in crawl-ref/source/dungeon.cc at line 2694 [4.3429798]

B:BD[5.249] → [5.249:297]

                random_range(MAPGEN_BORDER + 1,

[5.249]

[5.297]

                random_range(MAPGEN_BORDER,

Replacement in crawl-ref/source/dungeon.cc at line 2696 [4.3429798]

B:BD[5.368] → [5.368:416]

                random_range(MAPGEN_BORDER + 1,

[5.368]

[5.416]

                random_range(MAPGEN_BORDER,

Replacement in crawl-ref/source/dungeon.cc at line 2816 [4.3429798]

B:BD[6.152572] → [5.883:1008]

        if (dig_at.x < MAPGEN_BORDER + 1 || dig_at.x > (GXM - MAPGEN_BORDER - 1)
            || dig_at.y < MAPGEN_BORDER + 1

[6.152572]

[5.1008]

        if (dig_at.x < MAPGEN_BORDER || dig_at.x > (GXM - MAPGEN_BORDER - 1)
            || dig_at.y < MAPGEN_BORDER

Replacement in crawl-ref/source/dungeon.cc at line 2935 [4.3429798]

B:BD[7.6964] → [7.6964:7017]

        coord_def c( random_range(MAPGEN_BORDER + 1,

[7.6964]

[7.7017]

        coord_def c( random_range(MAPGEN_BORDER,

Replacement in crawl-ref/source/dungeon.cc at line 2937 [4.3429798]

B:BD[7.7077] → [7.7077:7130]

                     random_range(MAPGEN_BORDER + 1,

[7.7077]

[7.7130]

                     random_range(MAPGEN_BORDER,

Insertion in crawl-ref/source/dungeon.cc at line 4670 [4.3429798]

[4.3662593]


static void find_maze_neighbours(const coord_def &c, coord_list &ns)
{
    std::vector<coord_def> coords;
    for (int yi = -2; yi <= 2; yi += 2)
    {
        for (int xi = -2; xi <= 2; xi += 2)
        {
            if (!!xi == !!yi)
                continue;
            
            const coord_def cp(c.x + xi, c.y + yi);
            if (cp.x >= MAPGEN_BORDER * 3 && cp.x < GXM - MAPGEN_BORDER * 3
                && cp.y >= MAPGEN_BORDER * 3 && cp.y < GYM - MAPGEN_BORDER * 3)
            {
                coords.push_back(cp);
            }
        }
    }
    while (!coords.empty())
    {
        const int n = random2(coords.size());
        ns.push_back(coords[n]);
        coords.erase( coords.begin() + n );
    }
}
static void labyrinth_maze_recurse(const coord_def &c)
{
    coord_list neighbours;
    find_maze_neighbours(c, neighbours);

Insertion in crawl-ref/source/dungeon.cc at line 4704 [4.3429798]

[4.3662594]

    coord_list deferred;
    for (coord_list::iterator i = neighbours.begin();
         i != neighbours.end(); ++i)
    {
        const coord_def &nc = *i;
        if (grd(nc) == DNGN_ROCK_WALL)
        {
            grd(nc) = DNGN_FLOOR;
            grd(c + (nc - c) / 2) = DNGN_FLOOR;
            if (!one_chance_in(3))
                labyrinth_maze_recurse(nc);
            else
                deferred.push_back(nc);
        }
    }
    for (coord_list::iterator i = deferred.begin(); i != deferred.end(); ++i)
        labyrinth_maze_recurse(*i);
}
static coord_def random_point_in_lab()
{
    return coord_def( random_range(MAPGEN_BORDER * 3,
                                   GXM - MAPGEN_BORDER * 3 - 1),
                      random_range(MAPGEN_BORDER * 3,
                                   GYM - MAPGEN_BORDER * 3 - 1) );
}
static void labyrinth_build_maze(coord_def &e)
{
    labyrinth_maze_recurse(random_point_in_lab());
    do
        e = random_point_in_lab();
    while (grd(e) != DNGN_FLOOR);
}
static void labyrinth_place_items(const coord_def &end)
{
    int num_items = 8 + random2avg(9, 2);
    for (int i = 0; i < num_items; i++)
    {
        int temp_rand = random2(11);
        const object_class_type
            glopop = ((temp_rand == 0 || temp_rand == 9)  ? OBJ_WEAPONS :
                  (temp_rand == 1 || temp_rand == 10) ? OBJ_ARMOUR :
                  (temp_rand == 2)                    ? OBJ_MISSILES :
                  (temp_rand == 3)                    ? OBJ_WANDS :
                  (temp_rand == 4)                    ? OBJ_MISCELLANY :
                  (temp_rand == 5)                    ? OBJ_SCROLLS :
                  (temp_rand == 6)                    ? OBJ_JEWELLERY :
                  (temp_rand == 7)                    ? OBJ_BOOKS
                  /* (temp_rand == 8) */              : OBJ_STAVES);
        const int treasure_item =
            items( 1, glopop, OBJ_RANDOM, true, 
                   you.your_level * 3, MAKE_ITEM_RANDOM_RACE );
        if (treasure_item != NON_ITEM)
        {
            mitm[treasure_item].x = end.x;
            mitm[treasure_item].y = end.y;
        }
    }
}
static void labyrinth_place_exit(const coord_def &end)
{
    labyrinth_place_items(end);
    mons_place( MONS_MINOTAUR, BEH_SLEEP, MHITNOT, true, end.x, end.y );
    grd(end) = DNGN_ROCK_STAIRS_UP;
}

Insertion in crawl-ref/source/dungeon.cc at line 4782 [4.3429798]

[4.3662642]

[4.3662710]

    coord_def end;
    labyrinth_build_maze(end);
    labyrinth_place_exit(end);
    link_items();
    // turn rock walls into undiggable stone or metal:
    dungeon_feature_type wall_xform =
        ((random2(50) > 10) ? DNGN_STONE_WALL   // 78.0%
         : DNGN_METAL_WALL); // 22.0%
    replace_area(0,0,GXM-1,GYM-1,DNGN_ROCK_WALL,wall_xform);
    
#ifdef OBSOLETE_LABYRINTH

Replacement in crawl-ref/source/dungeon.cc at line 4965 [4.3429798]
B:BD[4.3666620] → [4.3666620:3666621]
[4.3666620]
[4.3666621]
```
#endif
```