{"id":194,"date":"2010-01-09T17:51:16","date_gmt":"2010-01-09T15:51:16","guid":{"rendered":"http:\/\/crawl.develz.org\/wordpress\/?p=194"},"modified":"2011-05-09T13:13:58","modified_gmt":"2011-05-09T11:13:58","slug":"shoal-buildin","status":"publish","type":"post","link":"https:\/\/crawl.develz.org\/wordpress\/shoal-buildin","title":{"rendered":"Shoal Buildin’"},"content":{"rendered":"

\n The Lair is the highway most Crawl characters take to go from the
\n stressful early game (many players attribute later psychosocial
\n problems to D:2 bullying by Sigmund) to the more predictable
\n midgame. Along the way, you pick up lots of relatively safe
\n experience, and up to three runes from the Snake Pit, the Swamp and
\n the Slime Pits. Dying on the Lair superhighway is optional, but a
\n lot of players seem to enjoy it.\n<\/p>\n

\nFor a while now, players have been chafing under the injustice of
\nhaving to do the Swamp, since its devilish generosity with rune and
\nitems and shops forces players to brave the menacing terrain to rescue
\nthese poor lost items, in the process running into charming monsters
\nlike swamp worms that get double damage attacks while the character
\nwades in shallow water. When not being torn apart by suave swamp worms
\nin shallow water, our heroes are usually demolished by humane hydras,
\nwhich can swim much faster in water than most characters can walk on
\ndry land, and the occasional urbane unique.\n<\/p>\n

\nThe Crawl devteam has naturally been eager to improve the situation,
\nand has turned to a new branch that has an even chance of replacing
\nthe treachery of the Swamp with outright murder — tasteful, exciting
\nmurder. Murder with turtles in it. A new branch called the Shoals!\n<\/p>\n

\nThe Shoals are set near the sea, in a little archipelago of islands
\nwith beaches, tides, mangroves, and the occasional man-eating monster
\nthrown in for seasoning. It’s a long, fascinating story (you’ll never
\nguess how many useful things harpies can do with human entrails!), but
\ntoday we’re going to talk about how Shoals levels are generated, and
\nhow the tide works in the Shoals.\n<\/p>\n

<\/p>\n

Shoals Level Generation<\/h2>\n

\nShoal levels have two main characteristics:\n<\/p>\n

    \n
  1. the islands<\/li>\n
  2. the tide<\/li>\n<\/ol>\n

    \nThe Shoals level generator creates a 3d heightmap of the level, where
    \na height of 0 at any given point is assumed to be sea-level, negative
    \nheights being underwater, and positive heights being above water.\n<\/p>\n

    \nThere are different ways of making reasonably realistic islands on a
    \nheightmap; here’s the approach we use:\n<\/p>\n

      \n
    • Start with the entire map at a depth that’s just into deep water.<\/li>\n
    • Pick a random set of points on the map as island centres.<\/li>\n
    • \n For each island center, pick a few more random points near it as
      \n local high points on the island. i.e. each island can have multiple
      \n high points or hillocks on it.\n <\/li>\n
    • \n

      \n For each high point C on each island (the island centre and the
      \n other hillocks), raise the height of points near the high point
      \n C using this process:\n <\/p>\n

        \n
      1. \n Pick a random point P near C at a distance (randomly chosen
        \n for each point) of 0 to R from C, where R is a rough radius for
        \n that high point — think of it as the radius of a conical
        \n mountain’s base.\n <\/li>\n
      2. Raise the height at the point P.<\/li>\n
      3. Repeat (1) and (2) a few hundred times.<\/li>\n<\/ol>\n

        \n Most of the random points P will be close to the island centre,
        \n and the island centre will thus be approximately the highest
        \n point, with surrounding points at lower heights.\n <\/p>\n<\/li>\n

      4. \n

        \n At this point, our heightmap has recognisable islands, but they
        \n look extremely choppy because of our scattershot island building.
        \n (Map legend: ^ – very high point on island, space – floor, close
        \n to sea level, = – shallow water, # – deep water)\n <\/p>\n

        \n Note the complete lack of shallow water at this stage.\n <\/p>\n

        \n
        \n#######################<\/font> ##############################################<\/font>
        \n####################<\/font>   ###############################################<\/font>
        \n#################<\/font> ####<\/font> ###############################################<\/font>
        \n####################<\/font> #################################################<\/font>
        \n##################<\/font>  #<\/font>^<\/font>##<\/font> #############################################<\/font>
        \n#################<\/font> ####<\/font>  ##############################################<\/font>
        \n####################<\/font> #<\/font> ##<\/font> ############################################<\/font>
        \n##################<\/font> #####<\/font> #############################################<\/font>
        \n#####################<\/font> #<\/font> #<\/font> ############################################<\/font>
        \n####################<\/font>    ##############################################<\/font>
        \n####################<\/font> #<\/font>  ##############################################<\/font>
        \n####################<\/font>   ^<\/font>  ############################################<\/font>
        \n####################<\/font>  #<\/font>  #############################################<\/font>
        \n######################<\/font>  #<\/font> ############################################<\/font>
        \n############<\/font> #<\/font> ######<\/font>   ##############################################<\/font>
        \n############<\/font> ##################################<\/font> ######################<\/font>
        \n##########<\/font>   #########################################################<\/font>
        \n###########<\/font> ^^<\/font>  #<\/font> #############################<\/font> ######################<\/font>
        \n##########<\/font>   #######<\/font> ###################<\/font> #############################<\/font>
        \n##########<\/font> #<\/font>  #<\/font> ##############################<\/font>   #####################<\/font>
        \n##########<\/font> #<\/font>    ###############################<\/font> #<\/font> #####<\/font> ##############<\/font>
        \n##################<\/font>  ##<\/font> ##############<\/font>   ##<\/font>  #####<\/font>  ####<\/font> ##############<\/font>
        \n#########<\/font> ###<\/font> ##<\/font> #<\/font> ##<\/font>  ##############<\/font> ^<\/font>  #<\/font>  ######<\/font> #<\/font> #<\/font> #<\/font>  #<\/font> ##########<\/font>
        \n#############<\/font> #<\/font> ^^<\/font>  #<\/font> #<\/font> #############<\/font>   #<\/font>  ^<\/font> #<\/font>    ###<\/font>^<\/font>  ##############<\/font>
        \n##########<\/font> ####<\/font>  #<\/font>^<\/font> #<\/font> #########<\/font> ####<\/font> #########<\/font> #<\/font>  #<\/font> ^^^<\/font>#<\/font>^<\/font> ############<\/font>
        \n#############<\/font> ##<\/font>      ##################<\/font> ###<\/font>^<\/font>##<\/font>  ^<\/font>     ^<\/font> #<\/font>  ##########<\/font>
        \n###############<\/font>  #<\/font> #########<\/font> #####<\/font>  ##<\/font>^<\/font>#<\/font>   #<\/font>   #<\/font> ^<\/font>     ##<\/font> #<\/font>  #########<\/font>
        \n##############<\/font> #<\/font>   ######<\/font>  #######<\/font>   #<\/font>  ##<\/font> #<\/font> ^<\/font>   ##<\/font> #<\/font> ###<\/font> ############<\/font>
        \n###################<\/font> ####<\/font> ##<\/font> #<\/font>  ####<\/font>  ^<\/font>##<\/font>  #<\/font> ##<\/font> ^<\/font> #<\/font>  ######<\/font> ###########<\/font>
        \n############<\/font> ###<\/font> #######<\/font> ###<\/font> ^<\/font> #<\/font>   ^^<\/font>    #<\/font>^<\/font>####<\/font>^^^^<\/font>  #################<\/font>
        \n########################<\/font> ##<\/font> #<\/font> ###<\/font>    ###<\/font>^<\/font> #<\/font> ^^^^^^<\/font> #<\/font> #################<\/font>
        \n########################<\/font>    #<\/font>   ##<\/font> ^<\/font>   ^^^<\/font> ^^<\/font>   ^^<\/font>  ##################<\/font>
        \n############################<\/font> #<\/font> ##<\/font>   ^<\/font> #<\/font> #<\/font>   ^^<\/font> #<\/font>^^<\/font> ###################<\/font>
        \n############################<\/font>        ^<\/font>#<\/font> ^<\/font>#<\/font> ##<\/font>^<\/font>     #<\/font> ##################<\/font>
        \n#########################<\/font> ###<\/font>   #<\/font> #<\/font>    #<\/font> #<\/font>     ^<\/font>#<\/font>   ##################<\/font>
        \n#######################<\/font> ###<\/font> #<\/font>  #<\/font>     #<\/font> #<\/font>           #<\/font> #################<\/font>
        \n########################<\/font> #<\/font>    ^<\/font> #<\/font> ^<\/font>   #<\/font>  #<\/font>^^<\/font>    ^<\/font> ####################<\/font>
        \n#######################<\/font> #<\/font>  ##<\/font>     ^^<\/font> ###<\/font>      ##<\/font>  #<\/font> ##################<\/font>
        \n#####################<\/font>   ######<\/font> ##<\/font> ^^<\/font>  ^<\/font>   #<\/font>^<\/font>###<\/font> ###<\/font> ##################<\/font>
        \n#######################<\/font> ##<\/font>  #<\/font> #<\/font> #<\/font>   ^<\/font>  #<\/font>     #########################<\/font>
        \n######################<\/font>  #<\/font>^<\/font>##<\/font>  ^<\/font>  #<\/font>^^^<\/font>  ##<\/font>     #####<\/font> ##################<\/font>
        \n######################<\/font>  #<\/font> #<\/font>  ##<\/font>^<\/font>#<\/font>     #<\/font> #<\/font> #<\/font>    #######################<\/font>
        \n###############<\/font> #######<\/font>  #<\/font> ^<\/font>#<\/font> ^<\/font> ^<\/font>    #<\/font> #<\/font> ^^^^^<\/font>########################<\/font>
        \n##############<\/font>  #<\/font>  #<\/font>    #<\/font>   ^<\/font>  ###<\/font>^<\/font> #<\/font> ^<\/font> #<\/font>   #<\/font> ########################<\/font>
        \n##############<\/font>  ^<\/font>  ###<\/font>   ^^<\/font> #<\/font>^<\/font>#<\/font>   #<\/font> #<\/font> #<\/font> ##<\/font>   #<\/font> #######################<\/font>
        \n##############<\/font>  #<\/font> ###<\/font> #<\/font>  ^^^<\/font>  ^<\/font>   ######<\/font> #####<\/font> #######################<\/font>
        \n###############<\/font> ####<\/font> #<\/font>^<\/font>    ^<\/font>#<\/font>    #<\/font>  ##<\/font>^<\/font> ##<\/font> #<\/font> #########################<\/font>
        \n######################<\/font>   ^<\/font>  ^<\/font>#<\/font>     #<\/font> #<\/font> ##<\/font> #<\/font> ###<\/font> ######################<\/font>
        \n######################<\/font>^<\/font> #<\/font>^<\/font> ^<\/font>   ^<\/font>#<\/font> ##<\/font>^<\/font>##<\/font> ###<\/font>   ##<\/font> #####################<\/font>
        \n####################<\/font>  ^^^^^^<\/font> #<\/font> ###<\/font> #####<\/font> ###<\/font> #########################<\/font>
        \n######################<\/font> ^^^<\/font>   ^<\/font>  #####<\/font> #<\/font> ####<\/font>^<\/font>  #######################<\/font>
        \n#######################<\/font>    ^<\/font>  #<\/font>  #########<\/font>   #########################<\/font>
        \n######################<\/font> ###<\/font>    #<\/font> ############<\/font> #########################<\/font>
        \n#####################<\/font>  ###<\/font> #<\/font> ####<\/font> #######<\/font>  #<\/font> #<\/font> ##<\/font> ####################<\/font>
        \n#######################<\/font>^<\/font>#<\/font> ####<\/font> ##<\/font>  #######<\/font> #<\/font> #<\/font> #<\/font> #####################<\/font>
        \n#########################<\/font> ###############<\/font> #<\/font> ##########################<\/font>
        \n######################################################################<\/font>
        \n######################################################################<\/font>
        \n######################################################################<\/font>
        \n######################################################################<\/font>
        \n<\/font>\n <\/div>\n
      5. \n

        \n To fix this, we run a smoothing pass to average out the heights
        \n in our heightmap, simulating erosion:\n <\/p>\n

        \n At each point P on the map, calculate a weighted average of the
        \n height at P and the heights at all points adjacent to P. The
        \n height at P is weighted more than the heights at adjacent points,
        \n and points on the cardinals are weighted higher than points on
        \n diagonals.\n <\/p>\n

        \n Et voila, we have a Shoals map!\n <\/p>\n

        \n
        \n###################<\/font>===<\/font>  =<\/font>#############################################<\/font>
        \n################<\/font>=====<\/font>  ==<\/font>#############################################<\/font>
        \n################<\/font>==<\/font>#<\/font>======<\/font>#############################################<\/font>
        \n#################<\/font>===<\/font>   ===<\/font>############################################<\/font>
        \n################<\/font>====<\/font>   ===<\/font>############################################<\/font>
        \n################<\/font>====<\/font>    ===<\/font>###########################################<\/font>
        \n#################<\/font>===<\/font>   ====<\/font>###########################################<\/font>
        \n#################<\/font>======<\/font>  ==<\/font>###########################################<\/font>
        \n##################<\/font>==<\/font>      =<\/font>###########################################<\/font>
        \n###################<\/font>=<\/font>     ==<\/font>###########################################<\/font>
        \n###################<\/font>   ^^^<\/font> ==<\/font>##########################################<\/font>
        \n##################<\/font>=<\/font>   ^^<\/font>  ==<\/font>##########################################<\/font>
        \n##################<\/font>==<\/font>      ==<\/font>##########################################<\/font>
        \n###########<\/font>=====<\/font>###<\/font>==<\/font>     ==<\/font>##########################################<\/font>
        \n###########<\/font>=<\/font> ===<\/font>####<\/font>=<\/font>   ====<\/font>##################<\/font>===<\/font>#####################<\/font>
        \n#########<\/font>==<\/font>  ==<\/font>#####<\/font>=======<\/font>###################<\/font>===<\/font>#####################<\/font>
        \n#########<\/font>==<\/font>    ====<\/font>##<\/font>====<\/font>#####################<\/font>===<\/font>#####################<\/font>
        \n#########<\/font>=<\/font>  ^<\/font>  =======<\/font>#################<\/font>===<\/font>####<\/font>===<\/font>#####################<\/font>
        \n#########<\/font>=<\/font>     =======<\/font>#################<\/font>===<\/font>###<\/font>=<\/font>   =<\/font>####################<\/font>
        \n#########<\/font>=<\/font>      ==<\/font>#<\/font>==<\/font>##################<\/font>===<\/font>###<\/font>    ==<\/font>###<\/font>===<\/font>#############<\/font>
        \n#########<\/font>=<\/font> =<\/font>    ========<\/font>############<\/font>==<\/font>  ==<\/font>  ==<\/font>     =<\/font>##<\/font>===<\/font>#############<\/font>
        \n########<\/font>========<\/font>    =<\/font>  =<\/font>############<\/font>=<\/font> ^<\/font>     =====<\/font>  ====<\/font> =====<\/font>#########<\/font>
        \n########<\/font>=====<\/font> =<\/font>        ==<\/font>###########<\/font> ^^<\/font>    ^<\/font>       =<\/font>     ====<\/font>#########<\/font>
        \n########<\/font>======<\/font>         ==<\/font>#####<\/font>===<\/font>##<\/font>=<\/font>      ^^<\/font>         ^<\/font>    ==<\/font>##########<\/font>
        \n#########<\/font>=====<\/font>        ===<\/font>#####<\/font>==<\/font>###<\/font>=<\/font>             ^<\/font>   ^<\/font>     ==<\/font>#########<\/font>
        \n#########<\/font>======<\/font>       ==<\/font>###<\/font>===<\/font>###<\/font>==<\/font> =<\/font>           ^^<\/font>          ==<\/font>########<\/font>
        \n############<\/font>==<\/font>      ===<\/font>#<\/font>=====<\/font>####<\/font>=<\/font>                         ===<\/font>########<\/font>
        \n#############<\/font>       ============<\/font>#<\/font>=<\/font>                    ===<\/font> ===<\/font>#########<\/font>
        \n###########<\/font>=======<\/font>  ==<\/font>#<\/font>=====<\/font>   ==<\/font>  ^^^<\/font>          ^^^<\/font>   ======<\/font>##########<\/font>
        \n###########<\/font>==========<\/font>##<\/font>====<\/font>    =<\/font>   ^^<\/font>          ^^^^<\/font>   =====<\/font>###########<\/font>
        \n###########<\/font>========<\/font>####<\/font>=<\/font> =<\/font>              ^<\/font>  ^^^^^^^<\/font>   ==<\/font>###############<\/font>
        \n#######################<\/font>====<\/font>     =<\/font>  ^^<\/font>   ^<\/font> ^^^^^^^^<\/font>   ==<\/font>###############<\/font>
        \n#######################<\/font>=====<\/font>       ^^<\/font>      ^^^<\/font>  ^^<\/font>  ===<\/font>###############<\/font>
        \n########################<\/font>====<\/font>                ^<\/font>       ==<\/font>################<\/font>
        \n######################<\/font>======<\/font>                        ==<\/font>################<\/font>
        \n######################<\/font>====<\/font>                 ^^<\/font>       ==<\/font>################<\/font>
        \n######################<\/font>==<\/font>      ^<\/font>  ^^^<\/font>      ^^<\/font>       ===<\/font>################<\/font>
        \n####################<\/font>==<\/font>     =<\/font>     ^^^<\/font>               ===<\/font>################<\/font>
        \n####################<\/font>==<\/font>  ====<\/font>      ^^<\/font>          =======<\/font>#################<\/font>
        \n####################<\/font>==<\/font>            ^^^<\/font>         =======<\/font>#################<\/font>
        \n#####################<\/font>=<\/font>            ^^^<\/font>          ==<\/font>#<\/font>===<\/font>#################<\/font>
        \n##############<\/font>===<\/font>####<\/font>=<\/font>        ^^<\/font>          ^^^<\/font>  ==<\/font>#<\/font>==<\/font>##################<\/font>
        \n#############<\/font>========<\/font>        ^^<\/font>          ^^^^<\/font>  ==<\/font>#####################<\/font>
        \n#############<\/font>=<\/font>     ==<\/font>                      ^<\/font>   ==<\/font>#####################<\/font>
        \n#############<\/font>=<\/font>     ==<\/font>   ^^^^<\/font>                   ==<\/font>#####################<\/font>
        \n#############<\/font>=<\/font>    ==<\/font>    ^^^^<\/font>  ^<\/font>    ==<\/font>         ==<\/font>######################<\/font>
        \n#############<\/font>==<\/font> =====<\/font>    ^^<\/font>             =<\/font>   =====<\/font>#####################<\/font>
        \n#############<\/font>========<\/font>    ^^<\/font>            ====<\/font> ======<\/font>####################<\/font>
        \n###################<\/font>==<\/font> ^^^^^^<\/font>   ^<\/font>     ==<\/font> ===<\/font>  =====<\/font>####################<\/font>
        \n###################<\/font>=<\/font>  ^^^^^^<\/font>      =========<\/font>   ===<\/font>#####################<\/font>
        \n###################<\/font>==<\/font> ^^^^^^^<\/font>    ==========<\/font>   ==<\/font>######################<\/font>
        \n####################<\/font>=<\/font>     ^^<\/font>     =========<\/font>    ==<\/font>######################<\/font>
        \n####################<\/font>=<\/font>          ====<\/font>#####<\/font>==<\/font>   ======<\/font>###################<\/font>
        \n####################<\/font>=<\/font>        =======<\/font>####<\/font>=<\/font>     =====<\/font>###################<\/font>
        \n####################<\/font>==<\/font>    ==========<\/font>####<\/font>==<\/font> =======<\/font>####################<\/font>
        \n#####################<\/font>====<\/font> =========<\/font>#####<\/font>=========<\/font>#####################<\/font>
        \n######################<\/font>======<\/font>#############<\/font>====<\/font>#########################<\/font>
        \n######################################################################<\/font>
        \n######################################################################<\/font>
        \n######################################################################<\/font>
        \n<\/font>\n<\/div>\n

        \n A point of interest here: you’ll notice islands often overlap,
        \n and overlapping islands make for more interesting maps than
        \n simple isolated islands.\n <\/p>\n<\/li>\n<\/ul>\n

        \n The Shoals level generator in the current DCSS development branch
        \n adds some refinements to this vanilla level builder, adding things
        \n such as cliffs and clusters of plants (mangroves!), but we’ve
        \n covered the essentials here.\n<\/p>\n

        \n And here’s the code (C++).<\/p>\n

        \r\n#include<\/span> <iostream><\/span>\r\n#include<\/span> <cstdlib><\/span>\r\n#include<\/span> <cmath><\/span>\r\n#include<\/span> <algorithm><\/span>\r\n\r\nconst<\/span> int<\/span> N_PERTURB_ISLAND_CENTER<\/span> = 50;\r\nconst<\/span> int<\/span> ISLAND_CENTER_RADIUS_LOW<\/span> = 3;\r\nconst<\/span> int<\/span> ISLAND_CENTER_RADIUS_HIGH<\/span> = 10;\r\n\r\nconst<\/span> int<\/span> N_PERTURB_OFFSET_LOW<\/span>  = 25;\r\nconst<\/span> int<\/span> N_PERTURB_OFFSET_HIGH<\/span> = 45;\r\nconst<\/span> int<\/span> PERTURB_OFFSET_RADIUS_LOW<\/span> = 2;\r\nconst<\/span> int<\/span> PERTURB_OFFSET_RADIUS_HIGH<\/span> = 7;\r\n\r\nconst<\/span> int<\/span> GXM<\/span> = 70;\r\nconst<\/span> int<\/span> GYM<\/span> = 60;\r\n\r\nint<\/span> nislands<\/span> = 15;\r\n\r\nstruct<\/span> coord_def<\/span> {\r\n  int<\/span> x<\/span>, y<\/span>;\r\n  explicit<\/span> coord_def<\/span>(int<\/span> _x<\/span>, int<\/span> _y<\/span>) : x(_x), y(_y) { }\r\n  coord_def<\/span>(const<\/span> coord_def<\/span> &c<\/span>) : x(c.x), y(c.y) { }\r\n  int<\/span> abs<\/span>() const<\/span> { return<\/span> x * x + y * y; }\r\n  coord_def<\/span> operator<\/span> +<\/span> (const<\/span> coord_def<\/span> &c<\/span>) const<\/span> {\r\n    return<\/span> coord_def(x + c.x, y + c.y);\r\n  }\r\n  coord_def<\/span> operator<\/span> -<\/span> (const<\/span> coord_def<\/span> &c<\/span>) const<\/span> {\r\n    return<\/span> coord_def(x - c.x, y - c.y);\r\n  }\r\n  coord_def<\/span> operator<\/span> *<\/span> (int<\/span> mul<\/span>) const<\/span> {\r\n    return<\/span> coord_def(x * mul, y * mul);\r\n  }\r\n  coord_def<\/span> operator<\/span> \/<\/span> (int<\/span> div<\/span>) const<\/span> {\r\n    return<\/span> coord_def(x \/ div, y \/ div);\r\n  }\r\n  coord_def<\/span> &operator<\/span> +=<\/span> (const<\/span> coord_def<\/span> &c<\/span>) {\r\n    x += c.x;\r\n    y += c.y;\r\n    return<\/span> *this<\/span>;\r\n  }\r\n  coord_def<\/span> &operator<\/span> -=<\/span> (const<\/span> coord_def<\/span> &c<\/span>) {\r\n    x -= c.x;\r\n    y -= c.y;\r\n    return<\/span> *this<\/span>;\r\n  }\r\n  coord_def<\/span> &operator<\/span> *=<\/span> (int<\/span> mul<\/span>) {\r\n    x *= mul;\r\n    y *= mul;\r\n    return<\/span> *this<\/span>;\r\n  }\r\n  coord_def<\/span> &operator<\/span> \/=<\/span> (int<\/span> div<\/span>) {\r\n    x \/= div;\r\n    y \/= div;\r\n    return<\/span> *this<\/span>;\r\n  }\r\n};\r\n\r\ninline<\/span> int<\/span> dist2<\/span>(const<\/span> coord_def<\/span> &a<\/span>, const<\/span> coord_def<\/span> &b<\/span>) {\r\n  coord_def<\/span> delta<\/span> = a - b;\r\n  return<\/span> a.x * a.x + a.y * a.y;\r\n}\r\n\r\nint<\/span> grid<\/span>[GYM][GXM];\r\n\r\nint<\/span> random_max<\/span>(int<\/span> max<\/span>) {\r\n  return<\/span> (max <= 1 ? 0 : random() % max);\r\n}\r\n\r\nint<\/span> random_range<\/span>(int<\/span> low<\/span>, int<\/span> high<\/span>) {\r\n  if<\/span> (low > high)\r\n    std<\/span>::swap(low, high);\r\n  return<\/span> low + random_max(high - low + 1);\r\n}\r\n\r\nint<\/span> random_height<\/span>() {\r\n  \/\/ <\/span>This could be skewed toward more water at greater depths.\r\n<\/span>  return<\/span> -17; \/\/<\/span>random_range(-25 - depth * 10, -1);\r\n<\/span>}\r\n\r\nvoid<\/span> init_heightmap<\/span>() {\r\n  for<\/span> (int<\/span> y<\/span> = 0; y < GYM; ++y) {\r\n    for<\/span> (int<\/span> x<\/span> = 0; x < GXM; ++x) {\r\n      grid[y][x] = random_height();\r\n    }\r\n  }\r\n}\r\n\r\nint<\/span> height_char<\/span>(int<\/span> height<\/span>) {\r\n  return<\/span> height >= 100? '^'<\/span> :\r\n    height >= 0? ' '<\/span> :\r\n    height >= -14? '='<\/span> : '#'<\/span>;\r\n}\r\n\r\nvoid<\/span> dump_map<\/span>() {\r\n  char<\/span> buf<\/span>[GXM + 1];\r\n  for<\/span> (int<\/span> y<\/span> = 0; y < GYM; ++y) {\r\n    for<\/span> (int<\/span> x<\/span> = 0; x < GXM; ++x) {\r\n      const<\/span> int<\/span> height<\/span> = grid[y][x];\r\n      buf[x] = height_char(height);\r\n    }\r\n    buf[GXM] = 0;\r\n    std<\/span>::cout << buf << std<\/span>::endl;\r\n  }\r\n}\r\n\r\ncoord_def<\/span> random_point<\/span>(int<\/span> offset<\/span> = 0) {\r\n  return<\/span> coord_def(random_range(offset, GXM - offset - 1),\r\n                   random_range(offset, GYM - offset - 1));\r\n}\r\n\r\nbool<\/span> in_bounds<\/span>(const<\/span> coord_def<\/span> &c<\/span>) {\r\n  return<\/span> c.x >= 0 && c.x < GXM && c.y >= 0 && c.y < GYM;\r\n}\r\n\r\ncoord_def<\/span> random_point_from<\/span>(const<\/span> coord_def<\/span> &c<\/span>, int<\/span> radius<\/span>) {\r\n  while<\/span> (true<\/span>) {\r\n    const<\/span> double<\/span> angle<\/span> = random_max(360) * M_PI \/ 180;\r\n    coord_def<\/span> res<\/span> = c + coord_def(radius * cos(angle), radius * sin(angle));\r\n    \/\/<\/span>coord_def res = c + coord_def(random_range(0, radius),\r\n<\/span>    \/\/                              <\/span>random_range(0, radius));\r\n<\/span>    if<\/span> (in_bounds(res))\r\n      return<\/span> res;\r\n  }\r\n}\r\n\r\nvoid<\/span> island_center<\/span>(const<\/span> coord_def<\/span> &c<\/span>, int<\/span> n_perturb<\/span>, int<\/span> radius<\/span>,\r\n                   int<\/span> bounce_low<\/span>, int<\/span> bounce_high<\/span>) {\r\n  for<\/span> (int<\/span> i<\/span> = 0; i < n_perturb; ++i) {\r\n    coord_def<\/span> p<\/span> = random_point_from(c, random_max(1 + radius));\r\n    grid[p.y][p.x] += random_range(bounce_low, bounce_high);\r\n  }\r\n}\r\n\r\nvoid<\/span> build_island<\/span>(int<\/span> sign<\/span> = 1) {\r\n  coord_def<\/span> c<\/span> = random_point(10);\r\n  island_center(c, N_PERTURB_ISLAND_CENTER,\r\n                random_range(ISLAND_CENTER_RADIUS_LOW,\r\n                             ISLAND_CENTER_RADIUS_HIGH),\r\n                40 * sign, 60 * sign);\r\n\r\n  const<\/span> int<\/span> additional_heights<\/span> = random_max(4);\r\n  for<\/span> (int<\/span> i<\/span> = 0; i < additional_heights; ++i) {\r\n    const<\/span> int<\/span> addition_offset<\/span> = random_range(2, 10);\r\n\r\n    coord_def<\/span> offsetC<\/span> = random_point_from(c, addition_offset);\r\n\r\n    island_center(offsetC, random_range(N_PERTURB_OFFSET_LOW,\r\n                                        N_PERTURB_OFFSET_HIGH),\r\n                  random_range(PERTURB_OFFSET_RADIUS_LOW,\r\n                               PERTURB_OFFSET_RADIUS_HIGH),\r\n                  25 * sign, 35 * sign);\r\n  }\r\n}\r\n\r\nvoid<\/span> init_islands<\/span>() {\r\n  for<\/span> (int<\/span> i<\/span> = 0; i < nislands; ++i) {\r\n    build_island();\r\n  }\r\n}\r\n\r\nvoid<\/span> smooth_at<\/span>(const<\/span> coord_def<\/span> &c<\/span>, int<\/span> radius<\/span>) {\r\n  int<\/span> max_delta<\/span> = radius * radius * 2 + 2;\r\n  int<\/span> divisor<\/span> = 0;\r\n  int<\/span> total<\/span> = 0;\r\n  for<\/span> (int<\/span> y<\/span> = c.y - radius; y <= c.y + radius; ++y) {\r\n    for<\/span> (int<\/span> x<\/span> = c.x - radius; x <= c.x + radius; ++x) {\r\n      const<\/span> coord_def<\/span> p<\/span>(x, y);\r\n      if<\/span> (!in_bounds(p))\r\n        continue<\/span>;\r\n      const<\/span> coord_def<\/span> off<\/span> = c - p;\r\n      int<\/span> weight<\/span> = max_delta - off.abs();\r\n      divisor += weight;\r\n      total += grid[p.y][p.x] * weight;\r\n    }\r\n  }\r\n  grid[c.y][c.x] = total \/ divisor;\r\n}\r\n\r\nvoid<\/span> smooth_level<\/span>() {\r\n  for<\/span> (int<\/span> y<\/span> = 0; y < GYM; ++y) {\r\n    for<\/span> (int<\/span> x<\/span> = 0; x < GXM; ++x) {\r\n      smooth_at(coord_def(x, y), 1);\r\n    }\r\n  }\r\n}\r\n\r\nvoid<\/span> smooth_bumps<\/span>() {\r\n  const<\/span> int<\/span> nsmooth<\/span> = 1;\r\n  for<\/span> (int<\/span> i<\/span> = 0; i < nsmooth; ++i)\r\n    smooth_level();\r\n}\r\n\r\nint<\/span> main<\/span>(int<\/span> argc<\/span>, char<\/span> **argv<\/span>) {\r\n  if<\/span> (argc > 1) {\r\n    nislands = atoi(argv[1]);\r\n    if<\/span> (nislands < 1)\r\n      nislands = 1;\r\n  }\r\n  srandom(5);\r\n  init_heightmap();\r\n  init_islands();\r\n  smooth_bumps();\r\n  dump_map();\r\n  return<\/span> 0;\r\n}\r\n<\/pre>\n<\/p>\n
        Shoals Tides<\/h2>\n
        \n  Once we have a heightmap from level generation, tides are trivial to
        \n  implement. If the current height of the tide is tracked as ‘t’, and
        \n  the height of a given point is ‘h’, then the effective height of the
        \n  point with respect to the tide is (h – t). Thus if you have a point
        \n  with height 3, and the tide is at height 10, the effective height of
        \n  the point is -7, which places it underwater.\n<\/p>\n
        \n  There are some subtleties to handling the tide, such as propagating
        \n  the tide inward only from the open sea — isolated pools of water
        \n  which are surrounded by land should not grow and shrink with the tide,
        \n  but these are minor details.<\/p>\n","protected":false},"excerpt":{"rendered":"
        The Lair is the highway most Crawl characters take to go from the stressful early game (many players attribute later psychosocial problems to D:2 bullying by Sigmund) to the more predictable midgame. Along the way, you pick up lots of relatively safe experience, and up to three runes from the Snake Pit, the Swamp and […]<\/p>\n","protected":false},"author":13,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[9],"tags":[],"_links":{"self":[{"href":"https:\/\/crawl.develz.org\/wordpress\/wp-json\/wp\/v2\/posts\/194"}],"collection":[{"href":"https:\/\/crawl.develz.org\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/crawl.develz.org\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/crawl.develz.org\/wordpress\/wp-json\/wp\/v2\/users\/13"}],"replies":[{"embeddable":true,"href":"https:\/\/crawl.develz.org\/wordpress\/wp-json\/wp\/v2\/comments?post=194"}],"version-history":[{"count":12,"href":"https:\/\/crawl.develz.org\/wordpress\/wp-json\/wp\/v2\/posts\/194\/revisions"}],"predecessor-version":[{"id":1836,"href":"https:\/\/crawl.develz.org\/wordpress\/wp-json\/wp\/v2\/posts\/194\/revisions\/1836"}],"wp:attachment":[{"href":"https:\/\/crawl.develz.org\/wordpress\/wp-json\/wp\/v2\/media?parent=194"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/crawl.develz.org\/wordpress\/wp-json\/wp\/v2\/categories?post=194"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/crawl.develz.org\/wordpress\/wp-json\/wp\/v2\/tags?post=194"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}