From 9a308a7dd9f9abb274e2024d41239c587dd7eb77 Mon Sep 17 00:00:00 2001 From: Darshan Shaligram Date: Wed, 13 Jan 2010 21:39:16 +0530 Subject: Move island-building code from dgn-shoals.cc->dgn-height.cc. --- crawl-ref/source/dgn-height.cc | 171 +++++++++++++++++++++++++++++++++++ crawl-ref/source/dgn-height.h | 104 +++++++++++++++++++++ crawl-ref/source/dgn-shoals.cc | 201 ++++++++--------------------------------- crawl-ref/source/dungeon.cc | 6 ++ crawl-ref/source/dungeon.h | 1 + crawl-ref/source/makefile.obj | 1 + 6 files changed, 323 insertions(+), 161 deletions(-) create mode 100644 crawl-ref/source/dgn-height.cc create mode 100644 crawl-ref/source/dgn-height.h (limited to 'crawl-ref') diff --git a/crawl-ref/source/dgn-height.cc b/crawl-ref/source/dgn-height.cc new file mode 100644 index 0000000000..8a52736fb5 --- /dev/null +++ b/crawl-ref/source/dgn-height.cc @@ -0,0 +1,171 @@ +/* + * File: dgn-height.cc + * Summary: Dungeon heightmap routines. + */ + +#include "AppHdr.h" + +#include "coord.h" +#include "coordit.h" +#include "dgn-height.h" +#include "dungeon.h" +#include "random.h" + +const int SHOALS_ISLAND_COLLIDE_DIST2 = 5 * 5; + +void dgn_initialise_heightmap(int height) +{ + env.heightmap.reset(new grid_heightmap); + for (rectangle_iterator ri(0); ri; ++ri) + dgn_height_at(*ri) = height; +} + +int resolve_range(int_range range, int nrolls) +{ + return random_range(range.first, range.second, nrolls); +} + +void dgn_island_centred_at(const coord_def &c, + int n_points, + int radius, + int_range height_delta_range, + int border_margin, + bool make_atoll) +{ + for (int i = 0; i < n_points; ++i) { + const int thisrad = make_atoll? radius : random2(1 + radius); + const coord_def p = dgn_random_point_from(c, thisrad, border_margin); + if (!p.origin()) + dgn_height_at(p) += resolve_range(height_delta_range); + } +} + +void dgn_smooth_height_at(coord_def c, int radius, int max_height) +{ + const int height = dgn_height_at(c); + if (max_height != DGN_UNDEFINED_HEIGHT && height > max_height) + return; + + const 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 int nheight = dgn_height_at(p); + if (max_height != DGN_UNDEFINED_HEIGHT && nheight > max_height) + continue; + const coord_def off = c - p; + const int weight = max_delta - off.abs(); + divisor += weight; + total += nheight * weight; + } + } + dgn_height_at(c) = total / divisor; +} + +void dgn_smooth_heights(int radius, int npasses) +{ + for (int i = 0; i < npasses; ++i) + { + for (rectangle_iterator ri(0); ri; ++ri) + dgn_smooth_height_at(*ri, radius); + } +} + +////////////////////////////////////////////////////////////////////// +// dgn_island_plan + +dgn_island_plan dgn_island_plan::shoals_islands(int margin) +{ + dgn_island_plan plan; + plan.level_border_depth = margin; + plan.n_aux_centres = int_range(0, 3); + plan.aux_centre_offset_range = int_range(2, 10); + + plan.atoll_roll = 10; + plan.island_separation_dist2 = SHOALS_ISLAND_COLLIDE_DIST2; + + plan.n_island_centre_delta_points = int_range(50, 60); + plan.island_centre_radius_range = int_range(3, 10); + plan.island_centre_point_height_increment = int_range(40, 60); + + plan.n_island_aux_delta_points = int_range(25, 45); + plan.island_aux_radius_range = int_range(2, 7); + plan.island_aux_point_height_increment = int_range(25, 35); + + return (plan); +} + +void dgn_island_plan::build(int nislands) +{ + for (int i = 0; i < nislands; ++i) + build_island(); +} + +coord_def dgn_island_plan::pick_island_spot() +{ + coord_def c; + // Try to find a spot that's not too close to other islands; this + // is not a guarantee, though. + for (int i = 0; i < 15; ++i) + { + // Primary island centres should have a little clearance + // around them, so use 2x the actual margin. + c = dgn_random_point_in_margin(level_border_depth * 2); + + bool collides = false; + for (int j = 0, size = islands.size(); j < size; ++j) + { + const coord_def island = islands[j]; + const coord_def dist = island - c; + if (dist.abs() < island_separation_dist2) + { + collides = true; + break; + } + } + if (!collides) + break; + } + islands.push_back(c); + return c; +} + +void dgn_island_plan::build_island() +{ + const coord_def c = pick_island_spot(); + dgn_island_centred_at(c, resolve_range(n_island_centre_delta_points), + resolve_range(island_centre_radius_range), + island_centre_point_height_increment, + level_border_depth, + x_chance_in_y(atoll_roll, 100)); + + const int additional_heights = resolve_range(n_aux_centres); + for (int i = 0; i < additional_heights; ++i) { + const int addition_offset = resolve_range(aux_centre_offset_range); + + const coord_def offsetC = + dgn_random_point_from(c, addition_offset, level_border_depth); + if (!offsetC.origin()) + dgn_island_centred_at( + offsetC, resolve_range(n_island_aux_delta_points), + resolve_range(island_aux_radius_range), + island_aux_point_height_increment, + level_border_depth, + x_chance_in_y(atoll_roll, 100)); + } +} + +coord_def dgn_island_plan::pick_and_remove_random_island() +{ + if (islands.empty()) + return coord_def(0, 0); + + const int lucky_island = random2(islands.size()); + const coord_def c = islands[lucky_island]; + islands.erase(islands.begin() + lucky_island); + return c; +} diff --git a/crawl-ref/source/dgn-height.h b/crawl-ref/source/dgn-height.h new file mode 100644 index 0000000000..1ab5954db4 --- /dev/null +++ b/crawl-ref/source/dgn-height.h @@ -0,0 +1,104 @@ +#ifndef DGN_HEIGHT_H +#define DGN_HEIGHT_H + +#include "AppHdr.h" +#include "externs.h" +#include "env.h" +#include "fixedarray.h" +#include + +// The caller is responsible for ensuring that env.heightmap is set. +static inline short &dgn_height_at(const coord_def &c) +{ + return (*env.heightmap)(c); +} + +typedef FixedArray grid_bool; +typedef FixedArray grid_short; +typedef std::pair int_range; + +const int DGN_UNDEFINED_HEIGHT = -10000; + +int resolve_range(int_range range, int nrolls = 1); + +void dgn_initialise_heightmap(int initial_height = 0); +void dgn_smooth_height_at(coord_def c, int radius = 1, + int max_height = DGN_UNDEFINED_HEIGHT); +void dgn_smooth_heights(int radius = 1, int npasses = 1); + + +void dgn_island_centred_at(const coord_def &c, + // Number of times to raise heights of + // points near c. + int n_points, + + // Radius within which all height + // increments are applied. + int radius, + + // Lower and upper limits to the height + // delta per perturbation. + int_range height_delta_range, + + int border_margin = 6, + + // If make_atoll is set, all points chosen for + // height increment will be close to the specified + // radius from c, thus producing a ragged ring. + bool make_atoll = false); + +struct dgn_island_plan +{ +public: + // Number of squares of border to leave around the level. + int level_border_depth; + + // Number of auxiliary high points for each island. + int_range n_aux_centres; + + // Distance from the island centre where the aux high points are placed. + int_range aux_centre_offset_range; + + // Percentage of island (aux) centres that are built as atolls. + int atoll_roll; + + // The positions of the primary centre of each island. + std::vector islands; + + // The square of the minimum distance that must separate any two + // island centres. This is not intended to prevent island overlap, only + // to prevent too much clumping of islands. + int island_separation_dist2; + + // Number of points near each island centre that will be raised by + // the island builder. + int_range n_island_centre_delta_points; + + // Range of radii for island primary centres. + int_range island_centre_radius_range; + + int_range island_centre_point_height_increment; + + // Number of points near secondary island centres that will be + // raised by the island builder. + int_range n_island_aux_delta_points; + + // Range of radii for island aux centres. + int_range island_aux_radius_range; + + int_range island_aux_point_height_increment; + +public: + static dgn_island_plan shoals_islands(int margin); + static dgn_island_plan snake_chambers(int margin); + +public: + void build(int nislands); + coord_def pick_and_remove_random_island(); + +private: + coord_def pick_island_spot(); + void build_island(); +}; + +#endif diff --git a/crawl-ref/source/dgn-shoals.cc b/crawl-ref/source/dgn-shoals.cc index 084403a9c0..18290e7f5a 100644 --- a/crawl-ref/source/dgn-shoals.cc +++ b/crawl-ref/source/dgn-shoals.cc @@ -6,6 +6,7 @@ #include "coordit.h" #include "dungeon.h" #include "dgn-shoals.h" +#include "dgn-height.h" #include "env.h" #include "flood_find.h" #include "items.h" @@ -28,22 +29,7 @@ typedef FixedArray grid_short; const char *ENVP_SHOALS_TIDE_KEY = "shoals-tide-height"; const char *ENVP_SHOALS_TIDE_VEL = "shoals-tide-velocity"; -inline short &shoals_heights(const coord_def &c) -{ - return (*env.heightmap)(c); -} - -static std::vector _shoals_islands; - -const int ISLAND_COLLIDE_DIST2 = 5 * 5; -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; +static dgn_island_plan _shoals_islands; // The raw tide height / TIDE_MULTIPLIER is the actual tide height. The higher // the tide multiplier, the slower the tide advances and recedes. A multiplier @@ -99,7 +85,7 @@ static dungeon_feature_type _shoals_feature_by_height(int height) static dungeon_feature_type _shoals_feature_at(const coord_def &c) { - const int height = shoals_heights(c); + const int height = dgn_height_at(c); return _shoals_feature_by_height(height); } @@ -139,108 +125,37 @@ static inline bool _shoals_tide_passable_feat(dungeon_feature_type feat) static void _shoals_init_heights() { - env.heightmap.reset(new grid_heightmap); - for (rectangle_iterator ri(0); ri; ++ri) - shoals_heights(*ri) = SHT_SHALLOW_WATER - 3; -} - -static coord_def _random_point_from(const coord_def &c, int radius) -{ - return dgn_random_point_from(c, radius, _shoals_margin); -} - -static coord_def _random_point(int offset = 0) -{ - return coord_def(random_range(offset, GXM - offset - 1), - random_range(offset, GYM - offset - 1)); -} - -static void _shoals_island_center(const coord_def &c, int n_perturb, int radius, - int bounce_low, int bounce_high, - bool make_atoll = false) -{ - for (int i = 0; i < n_perturb; ++i) { - const int thisrad = make_atoll? radius : random2(1 + radius); - coord_def p = _random_point_from(c, thisrad); - if (!p.origin()) - shoals_heights(p) += random_range(bounce_low, bounce_high); - } -} - -static coord_def _shoals_pick_island_spot() -{ - coord_def c; - for (int i = 0; i < 15; ++i) - { - c = _random_point(_shoals_margin * 2); - - bool collides = false; - for (int j = 0, size = _shoals_islands.size(); j < size; ++j) - { - const coord_def island = _shoals_islands[j]; - const coord_def dist = island - c; - if (dist.abs() < ISLAND_COLLIDE_DIST2) - { - collides = true; - break; - } - } - if (!collides) - break; - } - _shoals_islands.push_back(c); - return c; -} - -static void _shoals_build_island() -{ - coord_def c = _shoals_pick_island_spot(); - _shoals_island_center(c, N_PERTURB_ISLAND_CENTER, - random_range(ISLAND_CENTER_RADIUS_LOW, - ISLAND_CENTER_RADIUS_HIGH), - 40, 60, one_chance_in(10)); - const int additional_heights = random2(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); - if (!offsetC.origin()) - _shoals_island_center(offsetC, random_range(N_PERTURB_OFFSET_LOW, - N_PERTURB_OFFSET_HIGH), - random_range(PERTURB_OFFSET_RADIUS_LOW, - PERTURB_OFFSET_RADIUS_HIGH), - 25, 35, one_chance_in(10)); - } + dgn_initialise_heightmap(SHT_SHALLOW_WATER - 3); } static void _shoals_init_islands(int depth) { const int nislands = 20 - depth * 2; - for (int i = 0; i < nislands; ++i) - _shoals_build_island(); + _shoals_islands = dgn_island_plan::shoals_islands(_shoals_margin); + _shoals_islands.build(nislands); } -// Cliffs are usually constructed in shallow water adjacent to deep -// water (for effect). static void _shoals_build_cliff() { - coord_def cliffc = _random_point(_shoals_margin * 2); - if (in_bounds(cliffc)) + const coord_def cliffc = dgn_random_point_in_margin(_shoals_margin * 2); + const int length = random_range(6, 15); + const double angle = dgn_degrees_to_radians(random2(360)); + const int_range n_cliff_points(40, 60); + const int cliff_point_radius = 3; + const int_range cliff_height_increment(100, 130); + + for (int i = 0; i < length; i += 3) { - const int length = random_range(6, 15); - double angle = dgn_degrees_to_radians(random2(360)); - for (int i = 0; i < length; i += 3) - { - int distance = i - length / 2; - coord_def place = - cliffc + coord_def(static_cast(distance * cos(angle)), - static_cast(distance * sin(angle))); - coord_def fuzz = coord_def(random_range(-2, 2), - random_range(-2, 2)); - place += fuzz; - _shoals_island_center(place, random_range(40, 60), 3, - 100, 130); - } + const int distance = i - length / 2; + coord_def place = + cliffc + coord_def(static_cast(distance * cos(angle)), + static_cast(distance * sin(angle))); + const coord_def fuzz = coord_def(random_range(-2, 2), + random_range(-2, 2)); + place += fuzz; + dgn_island_centred_at(place, resolve_range(n_cliff_points), + cliff_point_radius, cliff_height_increment, + _shoals_margin); } } @@ -251,43 +166,10 @@ static void _shoals_cliffs() _shoals_build_cliff(); } -static void _shoals_smooth_at(const coord_def &c, int radius, - int max_height = SHT_UNDEFINED) -{ - const int height = shoals_heights(c); - if (max_height != SHT_UNDEFINED && height > max_height) - return; - - 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 int nheight = shoals_heights(p); - if (max_height != SHT_UNDEFINED && nheight > max_height) - continue; - const coord_def off = c - p; - int weight = max_delta - off.abs(); - divisor += weight; - total += nheight * weight; - } - } - shoals_heights(c) = total / divisor; -} - -static void _shoals_smooth() -{ - for (rectangle_iterator ri(0); ri; ++ri) - _shoals_smooth_at(*ri, 1); -} - static void _shoals_smooth_water() { for (rectangle_iterator ri(0); ri; ++ri) - _shoals_smooth_at(*ri, 1, SHT_SHALLOW_WATER - 1); + dgn_smooth_height_at(*ri, 1, SHT_SHALLOW_WATER - 1); } static void _shoals_apply_level() @@ -312,7 +194,7 @@ static std::vector _shoals_water_depth_change_points() static inline void _shoals_deepen_water_at(coord_def p, int distance) { - shoals_heights(p) -= distance * 7; + dgn_height_at(p) -= distance * 7; } static void _shoals_deepen_water() @@ -355,10 +237,7 @@ static void _shoals_deepen_water() static coord_def _pick_shoals_island() { - const int lucky_island = random2(_shoals_islands.size()); - const coord_def c = _shoals_islands[lucky_island]; - _shoals_islands.erase(_shoals_islands.begin() + lucky_island); - return c; + return _shoals_islands.pick_and_remove_random_island(); } void place_feature_at_random_floor_square(dungeon_feature_type feat, @@ -400,7 +279,7 @@ static void _shoals_furniture(int margin) false); } - const int nhuts = std::min(8, int(_shoals_islands.size())); + const int nhuts = std::min(8, int(_shoals_islands.islands.size())); for (int i = 2; i < nhuts; ++i) { // Place (non-rune) minivaults on the other islands. We @@ -434,16 +313,16 @@ static void _shoals_deepen_edges() { for (int x = 1; x <= edge; ++x) { - shoals_heights(coord_def(x, y)) -= 800; - shoals_heights(coord_def(GXM - 1 - x, y)) -= 800; + dgn_height_at(coord_def(x, y)) -= 800; + dgn_height_at(coord_def(GXM - 1 - x, y)) -= 800; } } for (int x = 1; x < GXM - 2; ++x) { for (int y = 1; y <= edge; ++y) { - shoals_heights(coord_def(x, y)) -= 800; - shoals_heights(coord_def(x, GYM - 1 - y)) -= 800; + dgn_height_at(coord_def(x, y)) -= 800; + dgn_height_at(coord_def(x, GYM - 1 - y)) -= 800; } } } @@ -608,7 +487,8 @@ static void _shoals_make_plant_near(coord_def c, int radius, const int ntries = 5; for (int i = 0; i < ntries; ++i) { - const coord_def plant_place(_random_point_from(c, random2(1 + radius))); + const coord_def plant_place( + dgn_random_point_from(c, random2(1 + radius), _shoals_margin)); if (!plant_place.origin() && !monster_at(plant_place)) { @@ -644,7 +524,7 @@ static void _shoals_plant_supercluster(coord_def c, for (int i = 0; i < nadditional_clusters; ++i) { const coord_def satellite( - _random_point_from(c, random_range(2, 12))); + dgn_random_point_from(c, random_range(2, 12), _shoals_margin)); if (!satellite.origin()) _shoals_plant_cluster(satellite, random_range(5, 12, 2), random_range(2, 7), @@ -793,10 +673,9 @@ void prepare_shoals(int level_number) const int shoals_depth = level_id::current().depth - 1; dgn_replace_area(0, 0, GXM-1, GYM-1, DNGN_ROCK_WALL, DNGN_OPEN_SEA); _shoals_init_heights(); - _shoals_islands.clear(); _shoals_init_islands(shoals_depth); _shoals_cliffs(); - _shoals_smooth(); + dgn_smooth_heights(); _shoals_apply_level(); _shoals_deepen_water(); _shoals_deepen_edges(); @@ -828,7 +707,7 @@ void shoals_postprocess_level() // It would be nice to do actual height contours within // vaults, but for now, keep it simple. if (feat != expected_feat) - shoals_heights(c) = _shoals_feature_height(feat); + dgn_height_at(c) = _shoals_feature_height(feat); } } @@ -868,9 +747,9 @@ static coord_def _shoals_escape_place_from(coord_def bad_place, if (!act || !actor_at(p)) { - if (best_height == -1000 || shoals_heights(p) > best_height) + if (best_height == -1000 || dgn_height_at(p) > best_height) { - best_height = shoals_heights(p); + best_height = dgn_height_at(p); chosen = p; } } @@ -967,7 +846,7 @@ static tide_direction _shoals_feature_tide_height_change( static void _shoals_apply_tide_at(coord_def c, int tide) { - const int effective_height = shoals_heights(c) - tide; + const int effective_height = dgn_height_at(c) - tide; dungeon_feature_type newfeat = _shoals_feature_by_height(effective_height); // Make sure we're not sprouting new walls. diff --git a/crawl-ref/source/dungeon.cc b/crawl-ref/source/dungeon.cc index 442ff363b1..f1d1c8182c 100644 --- a/crawl-ref/source/dungeon.cc +++ b/crawl-ref/source/dungeon.cc @@ -2934,6 +2934,12 @@ bool dgn_has_adjacent_feat(coord_def c, dungeon_feature_type feat) return false; } +coord_def dgn_random_point_in_margin(int margin) +{ + return coord_def(random_range(margin, GXM - margin - 1), + random_range(margin, GYM - margin - 1)); +} + static inline bool _point_matches_feat(coord_def c, dungeon_feature_type searchfeat, unsigned mapmask, diff --git a/crawl-ref/source/dungeon.h b/crawl-ref/source/dungeon.h index f9a3f20a22..1ae794b96e 100644 --- a/crawl-ref/source/dungeon.h +++ b/crawl-ref/source/dungeon.h @@ -182,6 +182,7 @@ void dgn_flush_map_memory(); double dgn_degrees_to_radians(int degrees); bool dgn_has_adjacent_feat(coord_def c, dungeon_feature_type feat); +coord_def dgn_random_point_in_margin(int margin); coord_def dgn_random_point_in_bounds( dungeon_feature_type searchfeat, unsigned mapmask = MMT_VAULT, diff --git a/crawl-ref/source/makefile.obj b/crawl-ref/source/makefile.obj index 74ec8b4fee..965b16bbf8 100644 --- a/crawl-ref/source/makefile.obj +++ b/crawl-ref/source/makefile.obj @@ -34,6 +34,7 @@ dgnevent.o \ directn.o \ dlua.o \ dungeon.o \ +dgn-height.o \ dgn-shoals.o \ effects.o \ exclude.o \ -- cgit v1.2.3-54-g00ecf