123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901 |
- #ifndef __GRID_H
- #define __GRID_H
- #include "neighbors.h"
- #include "random.h"
- #include <algorithm>
- #include <unordered_set>
- #include <unordered_map>
- #include <limits>
- #include <iostream>
- namespace grid {
- typedef std::pair<unsigned int, unsigned int> pt;
- struct Map {
- unsigned int w;
- unsigned int h;
- std::vector<float> grid;
- std::vector<float> karma;
-
- std::unordered_set<pt> walkmap;
- std::unordered_set<pt> watermap;
- std::unordered_set<pt> floormap;
- std::unordered_set<pt> cornermap;
- std::unordered_set<pt> shoremap;
- std::unordered_set<pt> lakemap;
- std::unordered_set<pt> lowlands;
- struct genmaps_t {
-
- std::vector<pt> walkmap;
- std::vector<pt> watermap;
- std::vector<pt> floormap;
- std::vector<pt> cornermap;
- std::vector<pt> shoremap;
- std::vector<pt> lakemap;
- std::vector<pt> lowlands;
- std::unordered_set<pt> nogens;
- bool is_nogen(unsigned int x, unsigned int y) {
- return nogens.count(pt(x, y));
- }
- void add_nogen(unsigned int x, unsigned int y) {
- nogens.insert(pt(x, y));
- }
- void add_nogen_expand(neighbors::Neighbors& neigh,
- unsigned int x, unsigned int y, unsigned int depth) {
- pt xy(x, y);
- std::set<pt> ng;
- for (const auto& xy_ : neigh(xy)) {
- ng.insert(neigh.mk(xy_, xy));
- }
- std::set<pt> proc;
-
- nogens.insert(xy);
- proc.insert(xy);
- for (unsigned int i = 1; i < depth; ++i) {
-
- std::set<pt> ngtmp;
- for (const pt& z : ng) {
- if (proc.count(z) != 0)
- continue;
- proc.insert(z);
- for (const auto& xy_ : neigh(z)) {
- ngtmp.insert(neigh.mk(xy_, z));
- }
- }
- ng.insert(ngtmp.begin(), ngtmp.end());
- }
- nogens.insert(ng.begin(), ng.end());
- }
- bool _one_of(rnd::Generator& rng, const std::vector<pt>& map, pt& ret) const {
- if (map.empty())
- return false;
- for (unsigned int i = 0; i < 10; ++i) {
- ret = map[rng.n(map.size())];
- if (nogens.count(ret) != 0)
- continue;
- return true;
- }
- return false;
- }
- bool one_of_walk(rnd::Generator& rng, pt& ret) const {
- return _one_of(rng, walkmap, ret);
- }
- bool one_of_floor(rnd::Generator& rng, pt& ret) const {
- return _one_of(rng, floormap, ret);
- }
- bool one_of_corner(rnd::Generator& rng, pt& ret) const {
- return _one_of(rng, cornermap, ret);
- }
- bool one_of_shore(rnd::Generator& rng, pt& ret) const {
- return _one_of(rng, shoremap, ret);
- }
- bool one_of_water(rnd::Generator& rng, pt& ret) const {
- return _one_of(rng, watermap, ret);
- }
- bool one_of_lake(rnd::Generator& rng, pt& ret) const {
- return _one_of(rng, lakemap, ret);
- }
- bool one_of_lowlands(rnd::Generator& rng, pt& ret) const {
- return _one_of(rng, lowlands, ret);
- }
- template <typename T>
- genmaps_t(const T& g) {
- walkmap.assign(g.walkmap.begin(), g.walkmap.end());
- floormap.assign(g.floormap.begin(), g.floormap.end());
- cornermap.assign(g.cornermap.begin(), g.cornermap.end());
- shoremap.assign(g.shoremap.begin(), g.shoremap.end());
- watermap.assign(g.watermap.begin(), g.watermap.end());
- lakemap.assign(g.lakemap.begin(), g.lakemap.end());
- lowlands.assign(g.lowlands.begin(), g.lowlands.end());
- }
- template <typename T>
- genmaps_t(const genmaps_t& maps, const T& g) : genmaps_t(g) {
- nogens = maps.nogens;
- }
- void swap(genmaps_t&& maps) {
- walkmap.swap(maps.walkmap);
- floormap.swap(maps.floormap);
- cornermap.swap(maps.cornermap);
- shoremap.swap(maps.shoremap);
- watermap.swap(maps.watermap);
- lakemap.swap(maps.lakemap);
- lowlands.swap(maps.lowlands);
- nogens.swap(maps.nogens);
- }
- };
- void init(unsigned int _w, unsigned int _h) {
- w = _w;
- h = _h;
- grid.resize(w*h);
- karma.resize(w*h);
- walkmap.clear();
- watermap.clear();
- floormap.clear();
- cornermap.clear();
- shoremap.clear();
- lakemap.clear();
- lowlands.clear();
- for (size_t i = 0; i < w*h; ++i) {
- grid[i] = 10.0;
- karma[i] = 0.0;
- }
- }
- void clear() {
- init(w, h);
- }
- float& _get(unsigned int x, unsigned int y) {
- return grid[y*w+x];
- }
- float& _get(const pt& xy) {
- return grid[xy.second*w+xy.first];
- }
- float& get_karma(unsigned int x, unsigned int y) {
- return karma[y*w+x];
- }
- float get(unsigned int x, unsigned int y) const {
- return grid[y*w+x];
- }
- /*** *** *** *** *** ***/
- void subdivide_mapgen(rnd::Generator& rng,
- unsigned int a, unsigned int b,
- unsigned int c, unsigned int d, bool domid) {
- unsigned int x = ((c - a) / 2) + a;
- unsigned int y = ((d - b) / 2) + b;
- if ((a == x || c == x) &&
- (b == y || d == y))
- return;
- //int s = std::max(c-a, d-b);
- int step = 0;
- int s = 1;
- double mid;
- if (!domid) {
- mid = _get(x, y);
- } else {
- mid = _get(a, b) + _get(c, b) + _get(a, d) + _get(c, d);
- mid = (mid / 4.0) - step + rng.range(-s, s);
- _get(x, y) = mid;
- }
- double top = ((_get(a, b) + _get(c, b) + mid) / 3.0) - step + rng.range(-s, s);
- _get(x, b) = top;
- double bot = ((_get(a, d) + _get(c, d) + mid) / 3.0) - step + rng.range(-s, s);
- _get(x, d) = bot;
- double lef = ((_get(a, b) + _get(a, d) + mid) / 3.0) - step + rng.range(-s, s);
- _get(a, y) = lef;
- double rig = ((_get(c, b) + _get(c, d) + mid) / 3.0) - step + rng.range(-s, s);
- _get(c, y) = rig;
- subdivide_mapgen(rng, a, b, x, y, true);
- subdivide_mapgen(rng, x, b, c, y, true);
- subdivide_mapgen(rng, a, y, x, d, true);
- subdivide_mapgen(rng, x, y, c, d, true);
- }
- void normalize() {
- double avg = 0.0;
- double min = std::numeric_limits<double>::max();
- double max = std::numeric_limits<double>::min();
- for (double i : grid) {
- avg += i;
- }
- avg /= (w * h);
- for (float& i : grid) {
- i -= avg;
- if (i > max) max = i;
- else if (i < min) min = i;
- }
- double scale = (max - min) / 20.0;
- for (float& i : grid) {
- i = (i / scale);
- if (i > 10.0) i = 10.0;
- else if (i < -10.0) i = -10.0;
- }
- }
- void makegrid(rnd::Generator& rng) {
- _get((w-1)/2, (h-1)/2) = -10;
- subdivide_mapgen(rng, 0, 0, w - 1, h - 1, false);
- normalize();
- }
- template <typename PARAMS>
- void flow(neighbors::Neighbors& neigh, rnd::Generator& rng, const PARAMS& genparams,
- const pt& xy, std::unordered_set<pt>& out, double n) {
- if (n < genparams.flow_epsilon) {
- return;
- }
- if (out.count(xy) != 0)
- return;
- out.insert(xy);
- double v0 = _get(xy);
- std::vector< std::pair<double, pt> > l;
- double vtotal = 0.0;
- for (const auto& _xy_ : neigh(xy)) {
- auto xy_ = neigh.mk(_xy_, xy);
- double v = _get(xy_);
- if (out.count(xy_) == 0 && v <= v0) {
- l.push_back(std::make_pair(v, xy_));
- vtotal += v;
- }
- }
- if (l.size() == 0) {
- return;
- }
- for (auto& i : l) {
- flow(neigh, rng, genparams, i.second, out, n * (i.first / vtotal));
- }
- }
- template <typename PARAMS>
- void makeflow(neighbors::Neighbors& neigh,
- rnd::Generator& rng,
- const PARAMS& genparams,
- std::discrete_distribution<size_t>& ddist,
- std::unordered_set<pt>& gout,
- std::unordered_map<pt, unsigned int>& watr,
- double n, double q) {
- size_t index = ddist(rng.gen);
-
- unsigned int y = index / w;
- unsigned int x = index % w;
- std::unordered_set<pt> out;
- flow(neigh, rng, genparams, pt(x, y), out, n);
- for (const pt& xy : out) {
- watr[xy] += 1;
- float& i = _get(xy);
- i -= q;
- if (i < -10.0) i = -10.0;
- }
- gout.insert(out.begin(), out.end());
- }
- template <typename PARAMS>
- void makerivers(neighbors::Neighbors& neigh, rnd::Generator& rng, const PARAMS& genparams) {
- std::unordered_set<pt> gout;
- std::unordered_map<pt, unsigned int> watr;
- unsigned int N1 = grid.size() / genparams.flow_n_freq; //100;
- double N2 = genparams.flow_volume;
- double N3 = genparams.flow_erosion;
- {
- std::discrete_distribution<size_t> ddist;
- for (unsigned int i = 0; i < N1; i++) {
- if (i % genparams.flow_renorm_freq == 0) {
- std::vector<double> grid_norm;
- for (double v : grid) {
- grid_norm.push_back((v + 10.0) * genparams.flow_renorm_scale); //5);
- }
- ddist = std::discrete_distribution<size_t>(grid_norm.begin(), grid_norm.end());
- }
- makeflow(neigh, rng, genparams, ddist, gout, watr, N2, N3);
- }
- }
- double hmin = 10;
- unsigned int wmax = 0;
- for (const pt& xy : gout) {
- double h = _get(xy);
- auto tmp = watr.find(xy);
- unsigned int w = (tmp == watr.end() ? 0 : tmp->second);
- hmin = std::min(hmin, h);
- wmax = std::max(wmax, w);
- }
- double walk_threshold = std::max(genparams.walk_threshold, hmin);
- unsigned int lowlands_threshold = std::min(genparams.lowlands_threshold, wmax);
- for (const pt& xy : gout) {
- double h = _get(xy);
- auto tmp = watr.find(xy);
- unsigned int w = (tmp == watr.end() ? 0 : tmp->second);
- if (h <= walk_threshold) {
- walkmap.insert(xy);
- if (h <= hmin && w >= lowlands_threshold) {
- lowlands.insert(xy);
- }
- }
- }
- if (walkmap.empty() || lowlands.empty())
- throw std::runtime_error("Failed to generate map");
- ///
-
- std::vector< std::pair<unsigned int,pt> > watr_r;
- for (const auto& v : watr) {
- watr_r.push_back(std::make_pair(v.second, v.first));
- }
- std::sort(watr_r.begin(), watr_r.end());
- std::reverse(watr_r.begin(), watr_r.end());
- unsigned int pctwater = rng.gauss(genparams.water_quantile_mean, genparams.water_quantile_dev);
- if (pctwater <= 1) pctwater = 1;
- pctwater = watr_r.size() / pctwater;
- if (watr_r.size() > pctwater) {
- watr_r.resize(pctwater);
- }
- for (const auto& v : watr_r) {
- watermap.insert(v.second);
- }
- }
- template <typename PARAMS, typename FUNC>
- void flatten_pass(neighbors::Neighbors& neigh, const PARAMS& genparams, FUNC progressbar,
- size_t np_walk, size_t np_water) {
- std::unordered_set<pt> newwalkmap;
- auto* walkmap_p = &walkmap;
- size_t npass = std::max(np_walk, np_water);
-
- for (size_t np = 0; np < npass; ++np) {
- if (walkmap_p->size() > 2000)
- progressbar(" ..."_m);
- std::unordered_map<pt, size_t> nwalk;
- std::unordered_map<pt, size_t> nwater;
- for (const auto& xy : *walkmap_p) {
- bool iswater = watermap.count(xy);
- for (const auto& ij_ : neigh(xy)) {
- auto ij = neigh.mk(ij_, xy);
- // For all solid squares neighboring a walkable square,
- // count the number of neighbor walkable squares.
- if (np < np_walk && walkmap.count(ij) == 0)
- nwalk[ij]++;
- // For all dry squares neighboring a walkable water square,
- // count the number of neighbor walkable water squares.
- if (np < np_water && iswater && watermap.count(ij) == 0)
- nwater[ij]++;
- }
- }
- newwalkmap.clear();
- auto add_newwalkmap = [&](const pt& xy) {
- newwalkmap.insert(xy);
- for (const auto& ij_ : neigh(xy)) {
- auto ij = neigh.mk(ij_, xy);
- if (walkmap.count(ij))
- newwalkmap.insert(ij);
- }
- };
-
- for (const auto& z : nwalk) {
- if (genparams.flatten_walk_ng & (1 << z.second)) {
- walkmap.insert(z.first);
- add_newwalkmap(z.first);
- }
- }
- for (const auto& z : nwater) {
- if (genparams.flatten_water_ng & (1 << z.second)) {
- watermap.insert(z.first);
- walkmap.insert(z.first);
- add_newwalkmap(z.first);
- }
- }
- walkmap_p = &newwalkmap;
- }
- }
- template <typename PARAMS, typename FUNC>
- void unflow(neighbors::Neighbors& neigh, const PARAMS& genparams, FUNC progressbar, size_t npass) {
- std::unordered_set<pt> unwater;
- auto* watermap_p = &watermap;
- for (size_t np = 0; np < npass; ++np) {
- if (watermap_p->size() > 2000)
- progressbar(" ..."_m);
-
- unwater.clear();
- for (const pt& xy : *watermap_p) {
- unsigned int nwater = 0;
- for (const auto& xy_ : neigh(xy)) {
- if (watermap.count(neigh.mk(xy_, xy)) != 0)
- nwater++;
- }
- if (genparams.unflow_ng & (1 << nwater)) {
- unwater.insert(xy);
- }
- }
- for (const pt& xy : unwater) {
- watermap.erase(xy);
- }
- watermap_p = &unwater;
- }
- }
- template <typename PARAMS, typename FUNC>
- void flatten(neighbors::Neighbors& neigh, const PARAMS& genparams, FUNC progressbar) {
- {
- progressbar("Aging rock..."_m);
- flatten_pass(neigh, genparams, progressbar, genparams.nflatten_walk, genparams.nflatten_water);
- }
- {
- progressbar("Flowing water..."_m);
- unflow(neigh, genparams, progressbar, genparams.nunflow);
- }
- }
- void _set_maps(neighbors::Neighbors& neigh) {
- for (const pt& xy : walkmap) {
- if (watermap.count(xy) == 0) {
- floormap.insert(xy);
- for (const auto& v : neigh(xy)) {
- if (watermap.count(neigh.mk(v, xy)) != 0) {
- shoremap.insert(xy);
- break;
- }
- }
- }
- for (const auto& v : neigh(xy)) {
- if (walkmap.count(neigh.mk(v, xy)) == 0) {
- cornermap.insert(xy);
- break;
- }
- }
- }
- for (const pt& xy : watermap) {
- if (walkmap.count(xy) != 0) {
- lakemap.insert(xy);
- }
- }
- }
- template <typename PARAMS>
- void make_karma(rnd::Generator& rng, const PARAMS& genparams) {
- for (unsigned int y = 0; y < h; ++y) {
- for (unsigned int x = 0; x < w; ++x) {
- float& k = get_karma(x, y);
- if (y > 0 && x > 0) {
- k = ((get_karma(x-1, y) + get_karma(x, y-1) + get_karma(x-1, y-1)) / 3.0);
- }
- k += rng.gauss(genparams.karma_mean, genparams.karma_dev);
- k = std::min(std::max(k, -1.0f), 1.0f);
- }
- }
- }
- template <typename PARAMS, typename FUNC>
- void generate(neighbors::Neighbors& neigh,
- rnd::Generator& rng,
- const PARAMS& genparams,
- FUNC progressbar) {
- clear();
- {
- progressbar("Placing shiprock..."_m);
- makegrid(rng);
- }
- {
- progressbar("Placing water..."_m);
- makerivers(neigh, rng, genparams);
- }
- flatten(neigh, genparams, progressbar);
- for (const auto& xy : lakemap) {
- if (walkmap.count(xy) == 0)
- throw std::runtime_error("Sanity error 0.1.1");
- if (watermap.count(xy) == 0)
- throw std::runtime_error("Sanity error 0.1.2");
- }
- for (const auto& xy : shoremap) {
- if (walkmap.count(xy) == 0)
- throw std::runtime_error("Sanity error 0.1.3");
- }
- //
- {
- progressbar("Allotting karma..."_m);
- make_karma(rng, genparams);
- }
- {
- progressbar("Combining..."_m);
- set_maps(neigh);
- }
- }
- void set_maps(neighbors::Neighbors& neigh) {
- floormap.clear();
- shoremap.clear();
- cornermap.clear();
- lakemap.clear();
- _set_maps(neigh);
- for (const auto& xy : lakemap) {
- if (walkmap.count(xy) == 0)
- throw std::runtime_error("Sanity error 0.2.1");
- if (watermap.count(xy) == 0)
- throw std::runtime_error("Sanity error 0.2.2");
- }
- for (const auto& xy : shoremap) {
- if (walkmap.count(xy) == 0)
- throw std::runtime_error("Sanity error 0.2.3");
- }
- }
- /*** *** *** *** ***/
- void set_height(unsigned int x, unsigned int y, double h) {
- _get(x, y) = h;
- }
- double get_height(unsigned int x, unsigned int y) {
- return _get(x, y);
- }
- bool is_walk(unsigned int x, unsigned int y) const {
- return (walkmap.count(pt(x, y)) != 0);
- }
- bool is_water(unsigned int x, unsigned int y) const {
- return (watermap.count(pt(x, y)) != 0);
- }
- bool is_lake(unsigned int x, unsigned int y) const {
- return (lakemap.count(pt(x, y)) != 0);
- }
- bool is_floor(unsigned int x, unsigned int y) const {
- return (floormap.count(pt(x, y)) != 0);
- }
- bool is_corner(unsigned int x, unsigned int y) const {
- return (cornermap.count(pt(x, y)) != 0);
- }
- bool is_shore(unsigned int x, unsigned int y) const {
- return (shoremap.count(pt(x, y)) != 0);
- }
- bool is_lowlands(unsigned int x, unsigned int y) const {
- return (lowlands.count(pt(x, y)) != 0);
- }
- void _set_maps_of(neighbors::Neighbors& neigh, const std::set<pt>& affected) {
- for (const pt& xy : affected) {
- floormap.erase(xy);
- shoremap.erase(xy);
- cornermap.erase(xy);
- lakemap.erase(xy);
- if (walkmap.count(xy) == 0) {
- lowlands.erase(xy);
- continue;
- }
-
- if (watermap.count(xy) != 0) {
- lakemap.insert(xy);
- } else {
- floormap.insert(xy);
- }
- for (const auto& v_ : neigh(xy)) {
- auto v = neigh.mk(v_, xy);
- if (watermap.count(v) != 0 && walkmap.count(v) != 0) {
- shoremap.insert(xy);
- }
- if (walkmap.count(v) == 0) {
- cornermap.insert(xy);
- }
- }
- }
- }
- void set_walk_water(neighbors::Neighbors& neigh, unsigned int x, unsigned int y, bool walk, bool water) {
- pt tmp(x, y);
- if (walk) {
- walkmap.insert(tmp);
- } else {
- walkmap.erase(tmp);
- }
- if (water) {
- watermap.insert(tmp);
- } else {
- watermap.erase(tmp);
- }
- std::set<pt> affected;
- for (const auto& v : neigh(tmp)) {
- affected.insert(neigh.mk(v, tmp));
- }
- affected.insert(tmp);
- _set_maps_of(neigh, affected);
- }
- bool _one_of(rnd::Generator& rng, const std::unordered_set<pt>& s, pt& ret) {
- if (s.size() == 0)
- return false;
- size_t n = rng.n(s.size());
- auto i = s.begin();
- while (n > 0) {
- ++i;
- --n;
- }
- ret = *i;
- return true;
- }
- bool one_of_walk(rnd::Generator& rng, pt& ret) {
- return _one_of(rng, walkmap, ret);
- }
- bool one_of_floor(rnd::Generator& rng, pt& ret) {
- return _one_of(rng, floormap, ret);
- }
- bool one_of_corner(rnd::Generator& rng, pt& ret) {
- return _one_of(rng, cornermap, ret);
- }
- bool one_of_shore(rnd::Generator& rng, pt& ret) {
- return _one_of(rng, shoremap, ret);
- }
- bool one_of_water(rnd::Generator& rng, pt& ret) {
- return _one_of(rng, watermap, ret);
- }
- bool one_of_lake(rnd::Generator& rng, pt& ret) {
- return _one_of(rng, lakemap, ret);
- }
- bool one_of_lowlands(rnd::Generator& rng, pt& ret) {
- return _one_of(rng, lowlands, ret);
- }
- // Fake functions to adhere to a template interface.
- bool is_nogen(unsigned int x, unsigned int y) { return false; }
- void add_nogen(unsigned int x, unsigned int y) { }
- };
- }
- namespace serialize {
- template <>
- struct reader<grid::Map> {
- void read(Source& s, grid::Map& t) {
- serialize::read(s, t.w);
- serialize::read(s, t.h);
- serialize::read(s, t.grid);
- serialize::read(s, t.karma);
- serialize::read(s, t.walkmap);
- serialize::read(s, t.watermap);
- serialize::read(s, t.floormap);
- serialize::read(s, t.cornermap);
- serialize::read(s, t.shoremap);
- serialize::read(s, t.lakemap);
- serialize::read(s, t.lowlands);
- }
- };
- template <>
- struct writer<grid::Map> {
- void write(Sink& s, const grid::Map& t) {
- serialize::write(s, t.w);
- serialize::write(s, t.h);
- serialize::write(s, t.grid);
- serialize::write(s, t.karma);
- serialize::write(s, t.walkmap);
- serialize::write(s, t.watermap);
- serialize::write(s, t.floormap);
- serialize::write(s, t.cornermap);
- serialize::write(s, t.shoremap);
- serialize::write(s, t.lakemap);
- serialize::write(s, t.lowlands);
- }
- };
- }
- #endif
|