Shoal Buildin’ « Dungeon Crawl Stone Soup

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
the Slime Pits. Dying on the Lair superhighway is optional, but a
lot of players seem to enjoy it.

For a while now, players have been chafing under the injustice of
having to do the Swamp, since its devilish generosity with rune and
items and shops forces players to brave the menacing terrain to rescue
these poor lost items, in the process running into charming monsters
like swamp worms that get double damage attacks while the character
wades in shallow water. When not being torn apart by suave swamp worms
in shallow water, our heroes are usually demolished by humane hydras,
which can swim much faster in water than most characters can walk on
dry land, and the occasional urbane unique.

The Crawl devteam has naturally been eager to improve the situation,
and has turned to a new branch that has an even chance of replacing
the treachery of the Swamp with outright murder — tasteful, exciting
murder. Murder with turtles in it. A new branch called the Shoals!

The Shoals are set near the sea, in a little archipelago of islands
with beaches, tides, mangroves, and the occasional man-eating monster
thrown in for seasoning. It’s a long, fascinating story (you’ll never
guess how many useful things harpies can do with human entrails!), but
today we’re going to talk about how Shoals levels are generated, and
how the tide works in the Shoals.

Shoals Level Generation

Shoal levels have two main characteristics:

the islands
the tide

The Shoals level generator creates a 3d heightmap of the level, where
a height of 0 at any given point is assumed to be sea-level, negative
heights being underwater, and positive heights being above water.

There are different ways of making reasonably realistic islands on a
heightmap; here’s the approach we use:

Start with the entire map at a depth that’s just into deep water.
Pick a random set of points on the map as island centres.
For each island center, pick a few more random points near it as
local high points on the island. i.e. each island can have multiple
high points or hillocks on it.
For each high point C on each island (the island centre and the
other hillocks), raise the height of points near the high point
C using this process:
1. Pick a random point P near C at a distance (randomly chosen
  for each point) of 0 to R from C, where R is a rough radius for
  that high point — think of it as the radius of a conical
  mountain’s base.
2. Raise the height at the point P.
3. Repeat (1) and (2) a few hundred times.
Most of the random points P will be close to the island centre,
and the island centre will thus be approximately the highest
point, with surrounding points at lower heights.
At this point, our heightmap has recognisable islands, but they
look extremely choppy because of our scattershot island building.
(Map legend: ^ – very high point on island, space – floor, close
to sea level, = – shallow water, # – deep water)

Note the complete lack of shallow water at this stage.

####################### ##############################################
####################   ###############################################
################# #### ###############################################
#################### #################################################
##################  #^## #############################################
################# ####  ##############################################
#################### # ## ############################################
################## ##### #############################################
##################### # # ############################################
####################    ##############################################
#################### #  ##############################################
####################   ^  ############################################
####################  #  #############################################
######################  # ############################################
############ # ######   ##############################################
############ ################################## ######################
##########   #########################################################
########### ^^  # ############################# ######################
##########   ####### ################### #############################
########## #  # ##############################   #####################
########## #    ############################### # ##### ##############
##################  ## ##############   ##  #####  #### ##############
######### ### ## # ##  ############## ^  #  ###### # # #  # ##########
############# # ^^  # # #############   #  ^ #    ###^  ##############
########## ####  #^ # ######### #### ######### #  # ^^^#^ ############
############# ##      ################## ###^##  ^     ^ #  ##########
###############  # ######### #####  ##^#   #   # ^     ## #  #########
############## #   ######  #######   #  ## # ^   ## # ### ############
################### #### ## #  ####  ^##  # ## ^ #  ###### ###########
############ ### ####### ### ^ #   ^^    #^####^^^^  #################
######################## ## # ###    ###^ # ^^^^^^ # #################
########################    #   ## ^   ^^^ ^^   ^^  ##################
############################ # ##   ^ # #   ^^ #^^ ###################
############################        ^# ^# ##^     # ##################
######################### ###   # #    # #     ^#   ##################
####################### ### #  #     # #           # #################
######################## #    ^ # ^   #  #^^    ^ ####################
####################### #  ##     ^^ ###      ##  # ##################
#####################   ###### ## ^^  ^   #^### ### ##################
####################### ##  # # #   ^  #     #########################
######################  #^##  ^  #^^^  ##     ##### ##################
######################  # #  ##^#     # # #    #######################
############### #######  # ^# ^ ^    # # ^^^^^########################
##############  #  #    #   ^  ###^ # ^ #   # ########################
##############  ^  ###   ^^ #^#   # # # ##   # #######################
##############  # ### #  ^^^  ^   ###### ##### #######################
############### #### #^    ^#    #  ##^ ## # #########################
######################   ^  ^#     # # ## # ### ######################
######################^ #^ ^   ^# ##^## ###   ## #####################
####################  ^^^^^^ # ### ##### ### #########################
###################### ^^^   ^  ##### # ####^  #######################
#######################    ^  #  #########   #########################
###################### ###    # ############ #########################
#####################  ### # #### #######  # # ## ####################
#######################^# #### ##  ####### # # # #####################
######################### ############### # ##########################
######################################################################
######################################################################
######################################################################
######################################################################
To fix this, we run a smoothing pass to average out the heights
in our heightmap, simulating erosion:

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

Et voila, we have a Shoals map!

###################===  =#############################################
################=====  ==#############################################
################==#======#############################################
#################===   ===############################################
################====   ===############################################
################====    ===###########################################
#################===   ====###########################################
#################======  ==###########################################
##################==      =###########################################
###################=     ==###########################################
###################   ^^^ ==##########################################
##################=   ^^  ==##########################################
##################==      ==##########################################
###########=====###==     ==##########################################
###########= ===####=   ====##################===#####################
#########==  ==#####=======###################===#####################
#########==    ====##====#####################===#####################
#########=  ^  =======#################===####===#####################
#########=     =======#################===###=   =####################
#########=      ==#==##################===###    ==###===#############
#########= =    ========############==  ==  ==     =##===#############
########========    =  =############= ^     =====  ==== =====#########
########===== =        ==########### ^^    ^       =     ====#########
########======         ==#####===##=      ^^         ^    ==##########
#########=====        ===#####==###=             ^   ^     ==#########
#########======       ==###===###== =           ^^          ==########
############==      ===#=====####=                         ===########
#############       ============#=                    === ===#########
###########=======  ==#=====   ==  ^^^          ^^^   ======##########
###########==========##====    =   ^^          ^^^^   =====###########
###########========####= =              ^  ^^^^^^^   ==###############
#######################====     =  ^^   ^ ^^^^^^^^   ==###############
#######################=====       ^^      ^^^  ^^  ===###############
########################====                ^       ==################
######################======                        ==################
######################====                 ^^       ==################
######################==      ^  ^^^      ^^       ===################
####################==     =     ^^^               ===################
####################==  ====      ^^          =======#################
####################==            ^^^         =======#################
#####################=            ^^^          ==#===#################
##############===####=        ^^          ^^^  ==#==##################
#############========        ^^          ^^^^  ==#####################
#############=     ==                      ^   ==#####################
#############=     ==   ^^^^                   ==#####################
#############=    ==    ^^^^  ^    ==         ==######################
#############== =====    ^^             =   =====#####################
#############========    ^^            ==== ======####################
###################== ^^^^^^   ^     == ===  =====####################
###################=  ^^^^^^      =========   ===#####################
###################== ^^^^^^^    ==========   ==######################
####################=     ^^     =========    ==######################
####################=          ====#####==   ======###################
####################=        =======####=     =====###################
####################==    ==========####== =======####################
#####################==== =========#####=========#####################
######################======#############====#########################
######################################################################
######################################################################
######################################################################

A point of interest here: you’ll notice islands often overlap,
and overlapping islands make for more interesting maps than
simple isolated islands.

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

And here’s the code (C++).

#include <iostream>
#include <cstdlib>
#include <cmath>
#include <algorithm>

const int N_PERTURB_ISLAND_CENTER = 50;
const int ISLAND_CENTER_RADIUS_LOW = 3;
const int ISLAND_CENTER_RADIUS_HIGH = 10;

const int N_PERTURB_OFFSET_LOW  = 25;
const int N_PERTURB_OFFSET_HIGH = 45;
const int PERTURB_OFFSET_RADIUS_LOW = 2;
const int PERTURB_OFFSET_RADIUS_HIGH = 7;

const int GXM = 70;
const int GYM = 60;

int nislands = 15;

struct coord_def {
  int x, y;
  explicit coord_def(int _x, int _y) : x(_x), y(_y) { }
  coord_def(const coord_def &c) : x(c.x), y(c.y) { }
  int abs() const { return x * x + y * y; }
  coord_def operator + (const coord_def &c) const {
    return coord_def(x + c.x, y + c.y);
  }
  coord_def operator - (const coord_def &c) const {
    return coord_def(x - c.x, y - c.y);
  }
  coord_def operator * (int mul) const {
    return coord_def(x * mul, y * mul);
  }
  coord_def operator / (int div) const {
    return coord_def(x / div, y / div);
  }
  coord_def &operator += (const coord_def &c) {
    x += c.x;
    y += c.y;
    return *this;
  }
  coord_def &operator -= (const coord_def &c) {
    x -= c.x;
    y -= c.y;
    return *this;
  }
  coord_def &operator *= (int mul) {
    x *= mul;
    y *= mul;
    return *this;
  }
  coord_def &operator /= (int div) {
    x /= div;
    y /= div;
    return *this;
  }
};

inline int dist2(const coord_def &a, const coord_def &b) {
  coord_def delta = a - b;
  return a.x * a.x + a.y * a.y;
}

int grid[GYM][GXM];

int random_max(int max) {
  return (max <= 1 ? 0 : random() % max);
}

int random_range(int low, int high) {
  if (low > high)
    std::swap(low, high);
  return low + random_max(high - low + 1);
}

int random_height() {
  // This could be skewed toward more water at greater depths.
  return -17; //random_range(-25 - depth * 10, -1);
}

void init_heightmap() {
  for (int y = 0; y < GYM; ++y) {
    for (int x = 0; x < GXM; ++x) {
      grid[y][x] = random_height();
    }
  }
}

int height_char(int height) {
  return height >= 100? '^' :
    height >= 0? ' ' :
    height >= -14? '=' : '#';
}

void dump_map() {
  char buf[GXM + 1];
  for (int y = 0; y < GYM; ++y) {
    for (int x = 0; x < GXM; ++x) {
      const int height = grid[y][x];
      buf[x] = height_char(height);
    }
    buf[GXM] = 0;
    std::cout << buf << std::endl;
  }
}

coord_def random_point(int offset = 0) {
  return coord_def(random_range(offset, GXM - offset - 1),
                   random_range(offset, GYM - offset - 1));
}

bool in_bounds(const coord_def &c) {
  return c.x >= 0 && c.x < GXM && c.y >= 0 && c.y < GYM;
}

coord_def random_point_from(const coord_def &c, int radius) {
  while (true) {
    const double angle = random_max(360) * M_PI / 180;
    coord_def res = c + coord_def(radius * cos(angle), radius * sin(angle));
    //coord_def res = c + coord_def(random_range(0, radius),
    //                              random_range(0, radius));
    if (in_bounds(res))
      return res;
  }
}

void island_center(const coord_def &c, int n_perturb, int radius,
                   int bounce_low, int bounce_high) {
  for (int i = 0; i < n_perturb; ++i) {
    coord_def p = random_point_from(c, random_max(1 + radius));
    grid[p.y][p.x] += random_range(bounce_low, bounce_high);
  }
}

void build_island(int sign = 1) {
  coord_def c = random_point(10);
  island_center(c, N_PERTURB_ISLAND_CENTER,
                random_range(ISLAND_CENTER_RADIUS_LOW,
                             ISLAND_CENTER_RADIUS_HIGH),
                40 * sign, 60 * sign);

  const int additional_heights = random_max(4);
  for (int i = 0; i < additional_heights; ++i) {
    const int addition_offset = random_range(2, 10);

    coord_def offsetC = random_point_from(c, addition_offset);

    island_center(offsetC, random_range(N_PERTURB_OFFSET_LOW,
                                        N_PERTURB_OFFSET_HIGH),
                  random_range(PERTURB_OFFSET_RADIUS_LOW,
                               PERTURB_OFFSET_RADIUS_HIGH),
                  25 * sign, 35 * sign);
  }
}

void init_islands() {
  for (int i = 0; i < nislands; ++i) {
    build_island();
  }
}

void smooth_at(const coord_def &c, int radius) {
  int max_delta = radius * radius * 2 + 2;
  int divisor = 0;
  int total = 0;
  for (int y = c.y - radius; y <= c.y + radius; ++y) {
    for (int x = c.x - radius; x <= c.x + radius; ++x) {
      const coord_def p(x, y);
      if (!in_bounds(p))
        continue;
      const coord_def off = c - p;
      int weight = max_delta - off.abs();
      divisor += weight;
      total += grid[p.y][p.x] * weight;
    }
  }
  grid[c.y][c.x] = total / divisor;
}

void smooth_level() {
  for (int y = 0; y < GYM; ++y) {
    for (int x = 0; x < GXM; ++x) {
      smooth_at(coord_def(x, y), 1);
    }
  }
}

void smooth_bumps() {
  const int nsmooth = 1;
  for (int i = 0; i < nsmooth; ++i)
    smooth_level();
}

int main(int argc, char **argv) {
  if (argc > 1) {
    nislands = atoi(argv[1]);
    if (nislands < 1)
      nislands = 1;
  }
  srandom(5);
  init_heightmap();
  init_islands();
  smooth_bumps();
  dump_map();
  return 0;
}

Shoals Tides

Once we have a heightmap from level generation, tides are trivial to
implement. If the current height of the tide is tracked as ‘t’, and
the height of a given point is ‘h’, then the effective height of the
point with respect to the tide is (h – t). Thus if you have a point
with height 3, and the tide is at height 10, the effective height of
the point is -7, which places it underwater.

There are some subtleties to handling the tide, such as propagating
the tide inward only from the open sea — isolated pools of water
which are surrounded by land should not grow and shrink with the tide,
but these are minor details.

4 Responses to "Shoal Buildin’".

1. Comment by Napkin

10/Jan/2010 at 02:30

Just awesome! :D

2. Comment by evktalo

11/Jan/2010 at 11:32

Hehe, a great post. I particularly enjoyed the analysis of the Lair branch in the beginning. I wonder if this is true in 0.6 – the shortening of Lair has made it not feel like the start of the easy mode for me.

–Eino

3. Comment by greensnark

11/Jan/2010 at 12:12

The Lair’s more interesting in 0.6 than in 0.5, definitely, but it’s still distinctly easier than diving on into the main dungeon. :-)

4. Pingback by A Tide of Tiles « Dungeon Crawl Stone Soup

31/Mar/2010 at 15:50

[...] in a series of baffling commits greatly overhauled the Shoals’ level generation — and introduced tides! Without the islands’ previous strongly elliptic shape, the levels now look much more natural [...]

Comments are closed now!

Dungeon Crawl Stone Soup

Development live!

Shoal Buildin’

Shoals Level Generation

Shoals Tides