Added a new Island branch, based on dpeg's ideas.

In any given game, either the Islands or the Swamp will be generated (50%
chance of each) as Lair subbranches.
The Islands have a ranged-attackers theme and are 5 levels deep.
THIS IMPLEMENTATION IS INCOMPLETE, so beware! The following things need
to be added:
1. A level-5 vault to contain the islands rune (the rune is coded, but
it doesn't show up yet - so for now, if you get the Islands, you'll be
stuck with one less rune.) A unique Cyclops, Polyphemus, to guard it might
be a nice idea. Perhaps we should block controlled teleport until he's
dead, too.
2. Making the island structure depth-dependent (i.e., more islands on
deeper levels.)
3. Shallow water fractalisation.
4. Probably more stuff I forgot.

I also put in various minor fixes.

Breaks savefiles, possibly highscores too. I'll put in a savefile version
bump later.


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

13 files changed, 329 insertions, 138 deletions

diff --git a/crawl-ref/source/branch.cc b/crawl-ref/source/branch.cc
index 1f7409a451..000dcbb74e 100644
--- a/crawl-ref/source/branch.cc
+++ b/crawl-ref/source/branch.cc
@@ -62,6 +62,14 @@ Branch branches[] = {
       true, true, BROWN, BROWN,
       mons_swamp_rare, mons_swamp_level, 
       0, 'S' },
+    
+    { BRANCH_ISLANDS, BRANCH_LAIR, 5, 4,
+      DNGN_ENTER_ISLANDS, DNGN_RETURN_FROM_ISLANDS,
+      "Islands", "the Islands", "Isle",
+      NULL,
+      true, true, BROWN, BROWN,
+      mons_islands_rare, mons_islands_level,
+      0, 'A' },
 
     { BRANCH_SLIME_PITS, BRANCH_LAIR, 6, 4,
       DNGN_ENTER_SLIME_PITS, DNGN_RETURN_FROM_SLIME_PITS,
diff --git a/crawl-ref/source/direct.cc b/crawl-ref/source/direct.cc
index 48d1a05c4d..e88991a638 100644
--- a/crawl-ref/source/direct.cc
+++ b/crawl-ref/source/direct.cc
@@ -1261,6 +1261,8 @@ std::string feature_description(int grid)
         return ("A staircase to the Tomb.");
     case DNGN_ENTER_SWAMP:
         return ("A staircase to the Swamp.");
+    case DNGN_ENTER_ISLANDS:
+        return ("A staircase to the Islands.");
     case DNGN_RETURN_FROM_ORCISH_MINES:
     case DNGN_RETURN_FROM_HIVE:
     case DNGN_RETURN_FROM_LAIR:
@@ -1270,6 +1272,7 @@ std::string feature_description(int grid)
     case DNGN_RETURN_FROM_SLIME_PITS:
     case DNGN_RETURN_FROM_SNAKE_PIT:
     case DNGN_RETURN_FROM_SWAMP:
+    case DNGN_RETURN_FROM_ISLANDS:
         return ("A staircase back to the Lair.");
     case DNGN_RETURN_FROM_CRYPT:
     case DNGN_RETURN_FROM_HALL_OF_BLADES:
diff --git a/crawl-ref/source/dungeon.cc b/crawl-ref/source/dungeon.cc
index 035afd5bff..794e4adadd 100644
--- a/crawl-ref/source/dungeon.cc
+++ b/crawl-ref/source/dungeon.cc
@@ -97,10 +97,11 @@ static void place_specific_stair(int stair, const std::string &tag = "", int dl
 static void place_branch_entrances(int dlevel, char level_type);
 static void place_special_minivaults(int level_number, int level_type);
 static void place_traps( int level_number );
-static void prepare_swamp(void);
+static void prepare_swamp();
+static void prepare_islands();
 static void prepare_water( int level_number );
-static void check_doors(void);
-static void hide_doors(void);
+static void check_doors();
+static void hide_doors();
 static void make_trail(int xs, int xr, int ys, int yr,int corrlength, int intersect_chance,
     int no_corr, unsigned char begin, unsigned char end=0);
 static bool make_room(int sx,int sy,int ex,int ey,int max_doors, int doorlevel);
@@ -118,14 +119,14 @@ static void build_river(unsigned char river_type); //mv
 static void build_lake(unsigned char lake_type); //mv
 
 static void spotty_level(bool seeded, int iterations, bool boxy);
-static void bigger_room(void);
+static void bigger_room();
 static void plan_main(int level_number, char force_plan);
-static char plan_1(void);
-static char plan_2(void);
-static char plan_3(void);
+static char plan_1();
+static char plan_2();
+static char plan_3();
 static char plan_4(char forbid_x1, char forbid_y1, char forbid_x2,
                    char forbid_y2, unsigned char force_wall);
-static char plan_5(void);
+static char plan_5();
 static char plan_6(int level_number);
 static bool octa_room(spec_room &sr, int oblique_max, unsigned char type_floor);
 static void labyrinth_level(int level_number);
@@ -166,8 +167,8 @@ static int vault_grid( vault_placement &,
                        int &num_runes, int rune_subst = -1, bool foll = false);
 
 // ALTAR FUNCTIONS
-static dungeon_feature_type pick_an_altar(void);
-static void place_altar(void);
+static dungeon_feature_type pick_an_altar();
+static void place_altar();
 
 //////////////////////////////////////////////////////////////////////////
 // Static data
@@ -403,7 +404,8 @@ static void build_layout_skeleton(int level_number, int level_type,
     if (skip_build == BUILD_CONTINUE)
     {
         // do 'normal' building.  Well, except for the swamp.
-        if (!player_in_branch( BRANCH_SWAMP ))
+        if (!player_in_branch(BRANCH_SWAMP) &&
+            !player_in_branch(BRANCH_ISLANDS))
             skip_build = builder_normal(level_number, level_type, sr);
 
         if (skip_build == BUILD_CONTINUE)
@@ -549,6 +551,8 @@ static void build_dungeon_level(int level_number, int level_type)
     // time to make the swamp {dlb}:
     if (player_in_branch( BRANCH_SWAMP ))
         prepare_swamp();
+    else if (player_in_branch(BRANCH_ISLANDS))
+        prepare_islands();
 
     place_branch_entrances( level_number, level_type );
 
@@ -581,7 +585,9 @@ static void build_dungeon_level(int level_number, int level_type)
 
     link_items();
 
-    if (!player_in_branch(BRANCH_COCYTUS) && !player_in_branch(BRANCH_SWAMP))
+    if (!player_in_branch(BRANCH_COCYTUS) &&
+        !player_in_branch(BRANCH_SWAMP) &&
+        !player_in_branch(BRANCH_ISLANDS))
         prepare_water( level_number );
 }                               // end builder()
 
@@ -3074,13 +3080,13 @@ static int give_weapon(monsters *mon, int level)
         break;
     }
     case MONS_ORC_WARLORD:
-        // being at the top has it's priviledges
+        // being at the top has its privileges
         if (one_chance_in(3))
             level = MAKE_GOOD_ITEM;
         // deliberate fall-through
     case MONS_ORC_KNIGHT:
         item_race = MAKE_ITEM_ORCISH;
-        // deliberate fall-through, I guess {dlb}
+        // deliberate fall-through
     case MONS_NORBERT:
     case MONS_JOZEF:
     case MONS_URUG:
@@ -3668,7 +3674,7 @@ static void set_weapon_special(int the_weapon, int spwpn)
     set_item_ego_type( mitm[the_weapon], OBJ_WEAPONS, spwpn );
 }                               // end set_weapon_special()
 
-static void check_doors(void)
+static void check_doors()
 {
     for (int x = 1; x < GXM-1; x++)
     {
@@ -3696,7 +3702,7 @@ static void check_doors(void)
     }
 }                               // end check_doors()
 
-static void hide_doors(void)
+static void hide_doors()
 {
     unsigned char dx = 0, dy = 0;     // loop variables
     unsigned char wall_count = 0;     // clarifies inner loop {dlb}
@@ -3731,16 +3737,145 @@ static void hide_doors(void)
     }
 }                               // end hide_doors()
 
-static void prepare_swamp(void)
+// Places a randomized ellipse with centre (x,y) and half axes a and b
+static void place_ellipse(int x, int y, int a, int b, int feat, int margin)
 {
-    int i, j;                   // loop variables
-    int temp_rand;              // probability determination {dlb}
+    for (int i = std::max(x-a,margin); i <= std::min(x+a,GXM-margin); ++i)
+        for (int j = std::max(y-b,margin); j <= std::min(y+b, GYM-margin); ++j)
+            if ( (x-i)*(x-i)*b*b + (y-j)*(y-j)*a*a <=
+                 a*a*b*b/2 + roll_dice(2, a*a*b*b)/4 + random2(3) )
+                grd[i][j] = feat;
+}
+
+// count how many neighbours of grd[x][y] are the feature feat.
+static int count_neighbours(int x, int y, int feat)
+{
+    int result = 0;
+    for ( int i = -1; i <= 1; ++i )
+        for ( int j = -1; j <= 1; ++j )
+            if ( grd[x+i][y+j] == feat )
+                ++result;
+    return result;
+}
+
+
+static void prepare_islands()
+{
+    // dpeg's algorithm.
+    // We could have just used spotty_level() and changed rock to
+    // water, but this is much cooler. Right?
+    const int margin = 6;
+    coord_def centres[10];
 
+    // It seems very difficult to get these numbers right, so I'm
+    // fixing them for now.
+    // const int estradius = std::max(50 - num_islands*10, 10);
+    // const int num_islands = std::min(player_branch_depth(), 10);
+    const int num_islands = 4;
+    const int estradius = 12;
+
+    for (int x = margin; x < GXM-margin; ++x)
+        for (int y = margin; y < GYM-margin; ++y)
+            grd[x][y] = DNGN_DEEP_WATER;
+    
+    for (int i = 0; i < num_islands; ++i)
+    {
+        // smaller axis
+        int b = (2 * estradius + roll_dice(3, estradius)) / 4;
+        b = std::max(b,4);
+        b = std::min(b, (GYM - margin) / 2);
+
+        int a = b + roll_dice(2,b)/3; // more wide than tall
+        a = std::min(a, (GXM - margin) / 2);       
+        
+        int island_distance = estradius*estradius * (2 + num_islands/3);
+        
+        bool centre_ok;
+        do
+        {
+            centre_ok = true;
+
+            centres[i].x = a + random2(GXM-2*a-1);
+            centres[i].y = b + random2(GYM-2*b-1);          
+            
+            for (int j = 0; j < i; ++j)
+            {
+                // calculate the distance from the centers of
+                // previous islands
+                if ( distance(centres[i].x, centres[i].y,
+                              centres[j].x, centres[j].y) < island_distance )
+                {
+                    centre_ok = false;
+                    break;
+                }                   
+            }
+            if ( random2(num_islands) && island_distance )
+                --island_distance;
+        } while ( !centre_ok );
+        
+        // place an ellipse around the new coordinate
+        place_ellipse( centres[i].x, centres[i].y, a, b, DNGN_FLOOR, margin);
+    }
+
+
+    // Adding shallow water at deep water adjacent to floor.
+    // Randomisation: place shallow water if at least 1d(1d3) floor neighbours
+    for ( int i = margin; i < GXM - margin; ++i)
+        for ( int j = margin; j < GYM - margin; ++j)
+            if (grd[i][j] == DNGN_DEEP_WATER &&
+                count_neighbours(i, j, DNGN_FLOOR) > random2(random2(3)+1))
+                grd[i][j] = DNGN_SHALLOW_WATER;
+
+    // Placing sandbanks
+    for (int banks = 0; banks < 8; ++banks)
+    {
+        int xsize = 3+random2(3);  // random rectangle
+        int ysize = 3+random2(3);  
+        int xb = random2(GXM - 2 * margin - 10) + margin + 2;
+        int yb = random2(GYM - 2 * margin - 10) + margin + 2;
+
+        bool ok_place = true;
+        for ( int i = xb; i < xb + xsize; ++i )
+            for ( int j = yb; j < yb + ysize; ++j )
+                if ( grd[i][j] != DNGN_DEEP_WATER )
+                    ok_place = false;
+
+        if (ok_place)
+        {
+            for ( int i = xb; i < xb + xsize; ++i )
+                for ( int j = yb; j < yb + ysize; ++j )
+                    if ( !one_chance_in(3) )
+                        grd[i][j] = DNGN_SHALLOW_WATER;
+        }
+    }
+
+    // XXX TODO: fractalisation
+
+    // Place stairs randomly. No elevators.
+    for ( int i = 0; i < 3; ++i )
+    {
+        int x, y;
+        do {
+            x = random2(GXM);
+            y = random2(GYM);
+        } while ( grd[x][y] != DNGN_FLOOR );
+        grd[x][y] = DNGN_STONE_STAIRS_DOWN_I + i;
+
+        do {
+            x = random2(GXM);
+            y = random2(GYM);
+        } while ( grd[x][y] != DNGN_FLOOR );
+        grd[x][y] = DNGN_STONE_STAIRS_UP_I + i;
+    }
+}
+
+static void prepare_swamp()
+{
     const int margin = 10;
 
-    for (i = margin; i < (GXM - margin); i++)
+    for (int i = margin; i < (GXM - margin); i++)
     {
-        for (j = margin; j < (GYM - margin); j++)
+        for (int j = margin; j < (GYM - margin); j++)
         {
             // doors -> floors {dlb}
             if (grd[i][j] == DNGN_CLOSED_DOOR || grd[i][j] == DNGN_SECRET_DOOR)
@@ -3753,7 +3888,7 @@ static void prepare_swamp(void)
             // walls -> deep/shallow water or remain unchanged {dlb}
             if (grd[i][j] == DNGN_ROCK_WALL)
             {
-                temp_rand = random2(6);
+                const int temp_rand = random2(6);
 
                 if (temp_rand > 0)      // 17% chance unchanged {dlb}
                 {
@@ -7251,6 +7386,9 @@ void item_colour( item_def &item )
             case RUNE_SWAMP:                    // decaying
                 item.colour = BROWN;
                 break;
+                
+            case RUNE_ISLANDS:
+                item.colour = BLUE;             // liquid
 
             // These two are hardly unique, but since colour isn't used for 
             // stacking, so we don't have to worry to much about this. -- bwr
@@ -7306,7 +7444,7 @@ void item_colour( item_def &item )
 }                               // end item_colour()
 
 //jmf: generate altar based on where you are, or possibly randomly
-static dungeon_feature_type pick_an_altar(void)
+static dungeon_feature_type pick_an_altar()
 {
     dungeon_feature_type altar_type;
     int temp_rand;              // probability determination {dlb}
@@ -7395,7 +7533,7 @@ static dungeon_feature_type pick_an_altar(void)
     return (altar_type);
 }                               // end pick_an_altar()
 
-static void place_altar(void)
+static void place_altar()
 {
     int px, py;
     int i, j;
@@ -7742,7 +7880,7 @@ static void spotty_level(bool seeded, int iterations, bool boxy)
     }
 }                               // end spotty_level()
 
-static void bigger_room(void)
+static void bigger_room()
 {
     unsigned char i, j;
 
@@ -7823,7 +7961,7 @@ static void plan_main(int level_number, char force_plan)
         replace_area(0,0,GXM-1,GYM-1,DNGN_ROCK_WALL,special_grid);
 }                               // end plan_main()
 
-static char plan_1(void)
+static char plan_1()
 {
     int temp_rand = 0;          // probability determination {dlb}
 
@@ -7890,7 +8028,7 @@ static char plan_1(void)
 }                               // end plan_1()
 
 // just a cross:
-static char plan_2(void)
+static char plan_2()
 {
     char width2 = (5 - random2(5));     // value range of [1,5] {dlb}
 
@@ -7902,7 +8040,7 @@ static char plan_2(void)
     return (one_chance_in(4) ? 2 : 3);
 }                               // end plan_2()
 
-static char plan_3(void)
+static char plan_3()
 {
 
     /* Draws a room, then another and links them together, then another and etc
@@ -8113,7 +8251,7 @@ static char plan_4(char forbid_x1, char forbid_y1, char forbid_x2,
     return 2;
 }                               // end plan_4()
 
-static char plan_5(void)
+static char plan_5()
 {
     unsigned char imax = 5 + random2(20);       // value range of [5,24] {dlb}
 
diff --git a/crawl-ref/source/enum.h b/crawl-ref/source/enum.h
index 937a2a6b62..65112200c4 100644
--- a/crawl-ref/source/enum.h
+++ b/crawl-ref/source/enum.h
@@ -462,6 +462,7 @@ enum branch_type                // you.where_are_you
     BRANCH_ELVEN_HALLS,
     BRANCH_LAIR,
     BRANCH_SWAMP,
+    BRANCH_ISLANDS,
     BRANCH_SLIME_PITS,
     BRANCH_SNAKE_PIT,
     BRANCH_HIVE,
@@ -1017,7 +1018,7 @@ enum dungeon_feature_type
     DNGN_ENTER_ELVEN_HALLS,            //  120
     DNGN_ENTER_TOMB,
     DNGN_ENTER_SWAMP,                  //  122
-    DNGN_ENTER_RESERVED_1,
+    DNGN_ENTER_ISLANDS,
     DNGN_ENTER_RESERVED_2,
     DNGN_ENTER_RESERVED_3,
     DNGN_ENTER_RESERVED_4,             // 126 
@@ -1035,7 +1036,7 @@ enum dungeon_feature_type
     DNGN_RETURN_FROM_ELVEN_HALLS,      //  140
     DNGN_RETURN_FROM_TOMB,
     DNGN_RETURN_FROM_SWAMP,               //  142
-    DNGN_RETURN_RESERVED_1,
+    DNGN_RETURN_FROM_ISLANDS,
     DNGN_RETURN_RESERVED_2,
     DNGN_RETURN_RESERVED_3,
     DNGN_RETURN_RESERVED_4,             // 146 
@@ -2842,6 +2843,7 @@ enum rune_type
     RUNE_ELVEN_HALLS = BRANCH_ELVEN_HALLS, // unused
     RUNE_TOMB        = BRANCH_TOMB,
     RUNE_SWAMP       = BRANCH_SWAMP,
+    RUNE_ISLANDS     = BRANCH_ISLANDS,
 
     // Runes 50 and 51 are for Pandemonium (general demon) and the Abyss
     RUNE_DEMONIC                = 50,
diff --git a/crawl-ref/source/itemname.cc b/crawl-ref/source/itemname.cc
index db67c40cdb..31536d7c73 100644
--- a/crawl-ref/source/itemname.cc
+++ b/crawl-ref/source/itemname.cc
@@ -1451,6 +1451,7 @@ static const char *item_name_2(
                           (it_plus == RUNE_ELVEN_HALLS)  ? "elven" :
                           (it_plus == RUNE_TOMB)         ? "golden" :
                           (it_plus == RUNE_SWAMP)        ? "decaying" :
+                          (it_plus == RUNE_ISLANDS)      ? "liquid" :
  
                           // pandemonium and abyss runes:
                           (it_plus == RUNE_DEMONIC)      ? "demonic" :
diff --git a/crawl-ref/source/items.cc b/crawl-ref/source/items.cc
index 2ec10821ea..0a50b14d7e 100644
--- a/crawl-ref/source/items.cc
+++ b/crawl-ref/source/items.cc
@@ -615,6 +615,9 @@ static void describe_floor() {
             case DNGN_ENTER_SWAMP:
                 mpr("There is a staircase to the Swamp here.");
                 break;
+            case DNGN_ENTER_ISLANDS:
+                mpr("There is a staircase to the Islands here.");
+                break;
             case DNGN_RETURN_FROM_ORCISH_MINES:
             case DNGN_RETURN_FROM_HIVE:
             case DNGN_RETURN_FROM_LAIR:
@@ -625,6 +628,7 @@ static void describe_floor() {
             case DNGN_RETURN_FROM_SLIME_PITS:
             case DNGN_RETURN_FROM_SNAKE_PIT:
             case DNGN_RETURN_FROM_SWAMP:
+            case DNGN_RETURN_FROM_ISLANDS:
                 mpr("There is a staircase back to the Lair here.");
                 break;
             case DNGN_RETURN_FROM_CRYPT:
diff --git a/crawl-ref/source/mon-pick.cc b/crawl-ref/source/mon-pick.cc
index b06023d686..a8e9d89e9c 100644
--- a/crawl-ref/source/mon-pick.cc
+++ b/crawl-ref/source/mon-pick.cc
@@ -1874,6 +1874,67 @@ int mons_tomb_rare(int mcls)
     }
 }                               // end mons_tomb_rare()
 
+int mons_islands_level(int mcls)
+{
+    int mlev = absdungeon_depth(BRANCH_ISLANDS, 1);
+    switch (mcls)
+    {
+    case MONS_BUTTERFLY:
+    case MONS_PLANT:
+        break;
+
+    case MONS_CENTAUR:
+    case MONS_ETTIN:
+    case MONS_SHEEP:
+        mlev++;
+        break;
+    case MONS_CENTAUR_WARRIOR:
+    case MONS_CYCLOPS:          // will have a sheep band
+    case MONS_YAKTAUR:
+        mlev += 2;
+        break;
+    case MONS_STONE_GIANT:
+    case MONS_YAKTAUR_CAPTAIN:
+    case MONS_OKLOB_PLANT:
+        mlev += 4;
+        break;
+    default:
+        mlev += 99;
+    }
+    return mlev;
+}
+
+int mons_islands_rare(int mcls)
+{
+    switch (mcls)
+    {
+    case MONS_PLANT:
+        return 150;
+
+    case MONS_ETTIN:
+    case MONS_CENTAUR:
+        return 50;
+
+    case MONS_SHEEP:
+    case MONS_BUTTERFLY:
+    case MONS_YAKTAUR:
+        return 35;
+
+    case MONS_CYCLOPS:
+    case MONS_CENTAUR_WARRIOR:
+        return 20;
+
+    case MONS_STONE_GIANT:
+    case MONS_YAKTAUR_CAPTAIN:
+        return 10;
+        
+    case MONS_OKLOB_PLANT:
+        return 5;
+    default:
+        return 0;
+    }
+}
+
 int mons_swamp_level(int mcls)
 {
     int mlev = absdungeon_depth(BRANCH_SWAMP, 1);
diff --git a/crawl-ref/source/mon-pick.h b/crawl-ref/source/mon-pick.h
index 47d047f0cd..b04f8f3cea 100644
--- a/crawl-ref/source/mon-pick.h
+++ b/crawl-ref/source/mon-pick.h
@@ -75,6 +75,8 @@ int mons_standard_level(int mcls);
 int mons_standard_rare(int mcls);
 int mons_swamp_level(int mcls);
 int mons_swamp_rare(int mcls);
+int mons_islands_level(int mcls);
+int mons_islands_rare(int mcls);
 int mons_tartarus_level(int mcls);
 int mons_tartarus_rare(int mcls);
 int mons_tomb_level(int mcls);
diff --git a/crawl-ref/source/monplace.cc b/crawl-ref/source/monplace.cc
index 7ba66f56e1..f0831b3b0a 100644
--- a/crawl-ref/source/monplace.cc
+++ b/crawl-ref/source/monplace.cc
@@ -36,8 +36,8 @@
 
 #define BIG_BAND        20
 
-static int band_member(int band, int power);
-static int choose_band( int mon_type, int power, int &band_size );
+static int band_member(band_type band, int power);
+static band_type choose_band( int mon_type, int power, int &band_size );
 static int place_monster_aux(int mon_type, char behaviour, int target,
     int px, int py, int power, int extra, bool first_band_member,
     int dur = 0);
@@ -235,7 +235,7 @@ bool place_monster(int &id, int mon_type, int power, char behaviour,
 
     if (allow_bands)
     {
-        int band = choose_band(mon_type, power, band_size);
+        const band_type band = choose_band(mon_type, power, band_size);
         band_size ++;
 
         for (i = 1; i < band_size; i++)
@@ -569,7 +569,7 @@ static int place_monster_aux( int mon_type, char behaviour, int target,
     menv[id].attitude = ATT_HOSTILE;
     menv[id].behaviour = behaviour;
 
-    if (mon_type == MONS_ORANGE_STATUE || mon_type == MONS_SILVER_STATUE)
+    if (mons_is_statue(mon_type))
         menv[id].behaviour = BEH_WANDER;
 
     menv[id].foe_memory = 0;
@@ -610,11 +610,11 @@ static int place_monster_aux( int mon_type, char behaviour, int target,
 }                               // end place_monster_aux()
 
 
-static int choose_band( int mon_type, int power, int &band_size )
+static band_type choose_band( int mon_type, int power, int &band_size )
 {
     // init
     band_size = 0;
-    int band = BAND_NO_BAND;
+    band_type band = BAND_NO_BAND;
 
     switch (mon_type)
     {
@@ -623,7 +623,7 @@ static int choose_band( int mon_type, int power, int &band_size )
             break;
         // intentional fall-through {dlb}
     case MONS_ORC_WARRIOR:
-        band = BAND_ORCS;       // orcs
+        band = BAND_ORCS;
         band_size = 2 + random2(3);
         break;
 
@@ -644,62 +644,62 @@ static int choose_band( int mon_type, int power, int &band_size )
         break;
 
     case MONS_KILLER_BEE:
-        band = BAND_KILLER_BEES;       // killer bees
+        band = BAND_KILLER_BEES;
         band_size = 2 + random2(4);
         break;
 
     case MONS_FLYING_SKULL:
-        band = BAND_FLYING_SKULLS;       // flying skulls
+        band = BAND_FLYING_SKULLS;
         band_size = 2 + random2(4);
         break;
     case MONS_SLIME_CREATURE:
-        band = BAND_SLIME_CREATURES;       // slime creatures
+        band = BAND_SLIME_CREATURES;
         band_size = 2 + random2(4);
         break;
     case MONS_YAK:
-        band = BAND_YAKS;       // yaks
+        band = BAND_YAKS;
         band_size = 2 + random2(4);
         break;
     case MONS_UGLY_THING:
-        band = BAND_UGLY_THINGS;       // ugly things
+        band = BAND_UGLY_THINGS;
         band_size = 2 + random2(4);
         break;
     case MONS_HELL_HOUND:
-        band = BAND_HELL_HOUNDS;       // hell hound
+        band = BAND_HELL_HOUNDS;
         band_size = 2 + random2(3);
         break;
     case MONS_JACKAL:
-        band = BAND_JACKALS;      // jackal
+        band = BAND_JACKALS;
         band_size = 1 + random2(3);
         break;
     case MONS_HELL_KNIGHT:
     case MONS_MARGERY:
-        band = BAND_HELL_KNIGHTS;      // hell knight
+        band = BAND_HELL_KNIGHTS;
         band_size = 4 + random2(4);
         break;
     case MONS_JOSEPHINE:
     case MONS_NECROMANCER:
     case MONS_VAMPIRE_MAGE:
-        band = BAND_NECROMANCER;      // necromancer
+        band = BAND_NECROMANCER;
         band_size = 4 + random2(4);
         break;
     case MONS_ORC_HIGH_PRIEST:
-        band = BAND_ORC_HIGH_PRIEST;      // orc high priest
+        band = BAND_ORC_HIGH_PRIEST;
         band_size = 4 + random2(4);
         break;
     case MONS_GNOLL:
-        band = BAND_GNOLLS;      // gnoll
+        band = BAND_GNOLLS;
         band_size = ((coinflip())? 3 : 2);
         break;
     case MONS_BUMBLEBEE:
-        band = BAND_BUMBLEBEES;      // bumble bees
+        band = BAND_BUMBLEBEES;
         band_size = 2 + random2(4);
         break;
     case MONS_CENTAUR:
     case MONS_CENTAUR_WARRIOR:
         if (power > 9 && one_chance_in(3))
         {
-            band = BAND_CENTAURS;  // centaurs
+            band = BAND_CENTAURS;
             band_size = 2 + random2(4);
         }
         break;
@@ -708,21 +708,21 @@ static int choose_band( int mon_type, int power, int &band_size )
     case MONS_YAKTAUR_CAPTAIN:
         if (coinflip())
         {
-            band = BAND_YAKTAURS;  // yaktaurs
+            band = BAND_YAKTAURS;
             band_size = 2 + random2(3);
         }
         break;
 
     case MONS_DEATH_YAK:
-        band = BAND_DEATH_YAKS;      // death yaks
+        band = BAND_DEATH_YAKS;
         band_size = 2 + random2(4);
         break;
     case MONS_INSUBSTANTIAL_WISP:
-        band = BAND_INSUBSTANTIAL_WISPS;      // wisps
+        band = BAND_INSUBSTANTIAL_WISPS;
         band_size = 4 + random2(5);
         break;
     case MONS_OGRE_MAGE:
-        band = BAND_OGRE_MAGE;      // ogre mage
+        band = BAND_OGRE_MAGE;
         band_size = 4 + random2(4);
         break;
     case MONS_BALRUG:
@@ -753,7 +753,7 @@ static int choose_band( int mon_type, int power, int &band_size )
     case MONS_DEEP_ELF_FIGHTER:
         if (coinflip())
         {
-            band = BAND_DEEP_ELF_FIGHTER;  // deep elf warrior
+            band = BAND_DEEP_ELF_FIGHTER;
             band_size = 3 + random2(4);
         }
         break;
@@ -761,7 +761,7 @@ static int choose_band( int mon_type, int power, int &band_size )
     case MONS_DEEP_ELF_KNIGHT:
         if (coinflip())
         {
-            band = BAND_DEEP_ELF_KNIGHT;  // deep elf knight
+            band = BAND_DEEP_ELF_KNIGHT;
             band_size = 3 + random2(4);
         }
         break;
@@ -769,7 +769,7 @@ static int choose_band( int mon_type, int power, int &band_size )
     case MONS_DEEP_ELF_HIGH_PRIEST:
         if (coinflip())
         {
-            band = BAND_DEEP_ELF_HIGH_PRIEST;  // deep elf high priest
+            band = BAND_DEEP_ELF_HIGH_PRIEST;
             band_size = 3 + random2(4);
         }
         break;
@@ -777,68 +777,75 @@ static int choose_band( int mon_type, int power, int &band_size )
     case MONS_KOBOLD_DEMONOLOGIST:
         if (coinflip())
         {
-            band = BAND_KOBOLD_DEMONOLOGIST;  // kobold demonologist
+            band = BAND_KOBOLD_DEMONOLOGIST;
             band_size = 3 + random2(6);
         }
         break;
 
     case MONS_NAGA_MAGE:
     case MONS_NAGA_WARRIOR:
-        band = BAND_NAGAS;      // Nagas
+        band = BAND_NAGAS;
         band_size = 3 + random2(4);
         break;
     case MONS_WAR_DOG:
-        band = BAND_WAR_DOGS;      // war dogs
+        band = BAND_WAR_DOGS;
         band_size = 2 + random2(4);
         break;
     case MONS_GREY_RAT:
-        band = BAND_GREY_RATS;      // grey rats
+        band = BAND_GREY_RATS;
         band_size = 4 + random2(6);
         break;
     case MONS_GREEN_RAT:
-        band = BAND_GREEN_RATS;      // green rats
+        band = BAND_GREEN_RATS;
         band_size = 4 + random2(6);
         break;
     case MONS_ORANGE_RAT:
-        band = BAND_ORANGE_RATS;      // orange rats
+        band = BAND_ORANGE_RATS;
         band_size = 3 + random2(4);
         break;
     case MONS_SHEEP:
-        band = BAND_SHEEP;      // sheep
+        band = BAND_SHEEP;
         band_size = 3 + random2(5);
         break;
     case MONS_GHOUL:
-        band = BAND_GHOULS;      // ghoul
+        band = BAND_GHOULS;
         band_size = 2 + random2(3);
         break;
     case MONS_HOG:
-        band = BAND_HOGS;      // hog
+        band = BAND_HOGS;
         band_size = 1 + random2(3);
         break;
     case MONS_GIANT_MOSQUITO:
-        band = BAND_GIANT_MOSQUITOES;      // mosquito
+        band = BAND_GIANT_MOSQUITOES;
         band_size = 1 + random2(3);
         break;
     case MONS_DEEP_TROLL:
-        band = BAND_DEEP_TROLLS;      // deep troll
+        band = BAND_DEEP_TROLLS;
         band_size = 3 + random2(3);
         break;
     case MONS_HELL_HOG:
-        band = BAND_HELL_HOGS;      // hell-hog
+        band = BAND_HELL_HOGS;
         band_size = 1 + random2(3);
         break;
     case MONS_BOGGART:
-        band = BAND_BOGGARTS;      // boggart
+        band = BAND_BOGGARTS;
         band_size = 2 + random2(3);
         break;
     case MONS_BLINK_FROG:
-        band = BAND_BLINK_FROGS;      // blink frog
+        band = BAND_BLINK_FROGS;
         band_size = 2 + random2(3);
         break;
     case MONS_SKELETAL_WARRIOR:
-        band = BAND_SKELETAL_WARRIORS;      // skeletal warrior
+        band = BAND_SKELETAL_WARRIORS;
         band_size = 2 + random2(3);
         break;
+    case MONS_CYCLOPS:
+        if ( one_chance_in(5) || player_in_branch(BRANCH_ISLANDS) )
+        {
+            band = BAND_SHEEP;  // Odyssey reference
+            band_size = 2 + random2(3);
+        }
+        break;
     // Journey -- Added Draconian Packs  
     case MONS_WHITE_DRACONIAN:
     case MONS_RED_DRACONIAN:
@@ -883,7 +890,7 @@ static int choose_band( int mon_type, int power, int &band_size )
     return (band);
 }
 
-static int band_member(int band, int power)
+static int band_member(band_type band, int power)
 {
     int mon_type = -1;
     int temp_rand;
@@ -1124,6 +1131,8 @@ static int band_member(int band, int power)
                                     MONS_RED_DRACONIAN );       // 3 in 34
         break;
     }
+    default:
+        break;
     }
 
     return (mon_type);
diff --git a/crawl-ref/source/newgame.cc b/crawl-ref/source/newgame.cc
index e61f3a944c..3f7c7aef65 100644
--- a/crawl-ref/source/newgame.cc
+++ b/crawl-ref/source/newgame.cc
@@ -354,7 +354,16 @@ static void initialise_branch_depths()
     branches[BRANCH_LAIR].startdepth = random_range(8, 13);
     branches[BRANCH_HIVE].startdepth = random_range(11, 16);
     branches[BRANCH_SLIME_PITS].startdepth = random_range(3, 9);
-    branches[BRANCH_SWAMP].startdepth = random_range(2, 7);
+    if ( coinflip() )
+    {
+        branches[BRANCH_SWAMP].startdepth = random_range(2, 7);
+        branches[BRANCH_ISLANDS].startdepth = -1;
+    }
+    else
+    {
+        branches[BRANCH_SWAMP].startdepth = -1;
+        branches[BRANCH_ISLANDS].startdepth = random_range(2, 7);
+    }
     branches[BRANCH_SNAKE_PIT].startdepth = random_range(3, 8);
     branches[BRANCH_VAULTS].startdepth = random_range(14, 19);
     branches[BRANCH_CRYPT].startdepth = random_range(2, 4);
diff --git a/crawl-ref/source/overmap.cc b/crawl-ref/source/overmap.cc
index 0dfa0c47fe..117e8d96d6 100644
--- a/crawl-ref/source/overmap.cc
+++ b/crawl-ref/source/overmap.cc
@@ -425,68 +425,16 @@ void seen_staircase( unsigned char which_staircase, const coord_def& pos )
     //   - stairs returning to dungeon - predictable
     //   - entrances to the hells - always in vestibule
 
-    branch_type which_branch = BRANCH_MAIN_DUNGEON;
-
-    switch ( which_staircase )
+    int i;
+    for ( i = 0; i < NUM_BRANCHES; ++i )
     {
-    case DNGN_ENTER_ORCISH_MINES:
-        which_branch = BRANCH_ORCISH_MINES;
-        break;
-    case DNGN_ENTER_HIVE:
-        which_branch = BRANCH_HIVE;
-        break;
-    case DNGN_ENTER_LAIR:
-        which_branch = BRANCH_LAIR;
-        break;
-    case DNGN_ENTER_SLIME_PITS:
-        which_branch = BRANCH_SLIME_PITS;
-        break;
-    case DNGN_ENTER_VAULTS:
-        which_branch = BRANCH_VAULTS;
-        break;
-    case DNGN_ENTER_CRYPT:
-        which_branch = BRANCH_CRYPT;
-        break;
-    case DNGN_ENTER_HALL_OF_BLADES:
-        which_branch = BRANCH_HALL_OF_BLADES;
-        break;
-    case DNGN_ENTER_ZOT:
-        which_branch = BRANCH_HALL_OF_ZOT;
-        break;
-    case DNGN_ENTER_TEMPLE:
-        which_branch = BRANCH_ECUMENICAL_TEMPLE;
-        break;
-    case DNGN_ENTER_SNAKE_PIT:
-        which_branch = BRANCH_SNAKE_PIT;
-        break;
-    case DNGN_ENTER_ELVEN_HALLS:
-        which_branch = BRANCH_ELVEN_HALLS;
-        break;
-    case DNGN_ENTER_TOMB:
-        which_branch = BRANCH_TOMB;
-        break;
-    case DNGN_ENTER_SWAMP:
-        which_branch = BRANCH_SWAMP;
-        break;
-    case DNGN_ENTER_DIS:
-        which_branch = BRANCH_DIS;
-        break;
-    case DNGN_ENTER_GEHENNA:
-        which_branch = BRANCH_GEHENNA;
-        break;
-    case DNGN_ENTER_COCYTUS:
-        which_branch = BRANCH_COCYTUS;
-        break;
-    case DNGN_ENTER_TARTARUS:
-        which_branch = BRANCH_TARTARUS;
-        break;
-    default:
-        break;
+        if ( branches[i].entry_stairs == which_staircase )
+        {
+            stair_level[branches[i].id] = level_id::current();
+            break;
+        }
     }
-
-    ASSERT(which_branch != BRANCH_MAIN_DUNGEON);
-
-    stair_level[which_branch] = level_id::current();
+    ASSERT( i != NUM_BRANCHES );
 }
 
 // if player has seen an altar; record it
diff --git a/crawl-ref/source/travel.cc b/crawl-ref/source/travel.cc
index 04a8800126..233a9dee60 100644
--- a/crawl-ref/source/travel.cc
+++ b/crawl-ref/source/travel.cc
@@ -521,6 +521,7 @@ void initialise_travel()
     traversable_terrain[DNGN_ENTER_ELVEN_HALLS] =
     traversable_terrain[DNGN_ENTER_TOMB] =
     traversable_terrain[DNGN_ENTER_SWAMP] =
+    traversable_terrain[DNGN_ENTER_ISLANDS] =
     traversable_terrain[DNGN_RETURN_FROM_ORCISH_MINES] =
     traversable_terrain[DNGN_RETURN_FROM_HIVE] =
     traversable_terrain[DNGN_RETURN_FROM_LAIR] =
@@ -534,6 +535,7 @@ void initialise_travel()
     traversable_terrain[DNGN_RETURN_FROM_ELVEN_HALLS] =
     traversable_terrain[DNGN_RETURN_FROM_TOMB] =
     traversable_terrain[DNGN_RETURN_FROM_SWAMP] =
+    traversable_terrain[DNGN_RETURN_FROM_ISLANDS] =
     traversable_terrain[DNGN_ALTAR_ZIN] =
     traversable_terrain[DNGN_ALTAR_SHINING_ONE] =
     traversable_terrain[DNGN_ALTAR_KIKUBAAQUDGHA] =
@@ -643,6 +645,7 @@ bool is_travelable_stair(unsigned gridc)
     case DNGN_ENTER_ELVEN_HALLS:
     case DNGN_ENTER_TOMB:
     case DNGN_ENTER_SWAMP:
+    case DNGN_ENTER_ISLANDS:
     case DNGN_RETURN_FROM_ORCISH_MINES:
     case DNGN_RETURN_FROM_HIVE:
     case DNGN_RETURN_FROM_LAIR:
@@ -656,6 +659,7 @@ bool is_travelable_stair(unsigned gridc)
     case DNGN_RETURN_FROM_ELVEN_HALLS:
     case DNGN_RETURN_FROM_TOMB:
     case DNGN_RETURN_FROM_SWAMP:
+    case DNGN_RETURN_FROM_ISLANDS:
         return true;
     default:
         return false;
@@ -2108,7 +2112,7 @@ command_type stair_direction(int stair)
     return ((stair < DNGN_STONE_STAIRS_UP_I
                 || stair > DNGN_ROCK_STAIRS_UP)
                 && (stair < DNGN_RETURN_FROM_ORCISH_MINES 
-                || stair > DNGN_RETURN_FROM_SWAMP))
+                || stair > DNGN_RETURN_RESERVED_4))
         ? CMD_GO_DOWNSTAIRS : CMD_GO_UPSTAIRS;
 }
 
diff --git a/crawl-ref/source/view.cc b/crawl-ref/source/view.cc
index 84506e823f..5f855bb9da 100644
--- a/crawl-ref/source/view.cc
+++ b/crawl-ref/source/view.cc
@@ -1825,6 +1825,7 @@ bool is_feature(int feature, int x, int y)
         case DNGN_RETURN_FROM_ELVEN_HALLS:
         case DNGN_RETURN_FROM_TOMB:
         case DNGN_RETURN_FROM_SWAMP:
+        case DNGN_RETURN_FROM_ISLANDS:
             return true;
         default:
             return false;
@@ -1848,6 +1849,7 @@ bool is_feature(int feature, int x, int y)
         case DNGN_ENTER_ELVEN_HALLS:
         case DNGN_ENTER_TOMB:
         case DNGN_ENTER_SWAMP:
+        case DNGN_ENTER_ISLANDS:
             return true;
         default:
             return false;
@@ -2995,7 +2997,7 @@ void init_feature_table( void )
         case DNGN_ENTER_ELVEN_HALLS:
         case DNGN_ENTER_TOMB:
         case DNGN_ENTER_SWAMP:
-        case DNGN_ENTER_RESERVED_1:
+        case DNGN_ENTER_ISLANDS:
         case DNGN_ENTER_RESERVED_2:
         case DNGN_ENTER_RESERVED_3:
         case DNGN_ENTER_RESERVED_4:
@@ -3026,7 +3028,7 @@ void init_feature_table( void )
         case DNGN_RETURN_FROM_ELVEN_HALLS:
         case DNGN_RETURN_FROM_TOMB:
         case DNGN_RETURN_FROM_SWAMP:
-        case DNGN_RETURN_RESERVED_1:
+        case DNGN_RETURN_FROM_ISLANDS:
         case DNGN_RETURN_RESERVED_2:
         case DNGN_RETURN_RESERVED_3:
         case DNGN_RETURN_RESERVED_4: