API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Mar 19th, 2023
61
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 23.12 KB | None | 0 0
raw download clone embed print report
  1. #include <assert.h>
  2. #include <math.h>
  3. #include <stdint.h>
  4.  
  5. #include <array>
  6. #include <list>
  7. #include <string>
  8. #include <utility>
  9. #include <vector>
  10.  
  11. using namespace std;
  12.  
  13. //////// From Lobster's dev/src/lobster/tools.h ////////
  14.  
  15. class PCG32 {
  16.     // This is apparently better than the Mersenne Twister, and its also smaller/faster!
  17.     // Adapted from *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org
  18.     // Licensed under Apache License 2.0 (NO WARRANTY, etc. see website).
  19.     uint64_t state = 0xABADCAFEDEADBEEF;
  20.     uint64_t inc = 0xDEADBABEABADD00D;
  21.  
  22.     public:
  23.  
  24.     uint32_t Random() {
  25.         uint64_t oldstate = state;
  26.         // Advance internal state.
  27.         state = oldstate * 6364136223846793005ULL + (inc | 1);
  28.         // Calculate output function (XSH RR), uses old state for max ILP.
  29.         uint32_t xorshifted = uint32_t(((oldstate >> 18u) ^ oldstate) >> 27u);
  30.         uint32_t rot = oldstate >> 59u;
  31.         return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
  32.     }
  33.  
  34.     void ReSeed(uint32_t s) {
  35.         state = s;
  36.         inc = 0xDEADBABEABADD00D;
  37.     }
  38. };
  39.  
  40. template<typename T> struct RandomNumberGenerator {
  41.     T rnd;
  42.  
  43.     void seed(uint32_t s) { rnd.ReSeed(s); }
  44.  
  45.     int operator()(int max) { return rnd.Random() % max; }
  46.     int operator()() { return rnd.Random(); }
  47.  
  48.     double rnddouble() { return rnd.Random() * (1.0 / 4294967296.0); }
  49.     float rnd_float() { return (float)rnddouble(); } // FIXME: performance?
  50.     float rndfloatsigned() { return (float)(rnddouble() * 2 - 1); }
  51.  
  52.     double n2 = 0.0;
  53.     bool n2_cached = false;
  54.     // Returns gaussian with stddev of 1 and mean of 0.
  55.     // Box Muller method.
  56.     double rnd_gaussian() {
  57.         n2_cached = !n2_cached;
  58.         if (n2_cached) {
  59.             double x, y, r;
  60.             do {
  61.                 x = 2.0 * rnddouble() - 1;
  62.                 y = 2.0 * rnddouble() - 1;
  63.                 r = x * x + y * y;
  64.             } while (r == 0.0 || r > 1.0);
  65.             double d = sqrt(-2.0 * log(r) / r);
  66.             double n1 = x * d;
  67.             n2 = y * d;
  68.             return n1;
  69.         } else {
  70.             return n2;
  71.         }
  72.     }
  73. };
  74.  
  75. inline int PopCount(uint32_t val) {
  76.     #ifdef _MSC_VER
  77.         return (int)__popcnt(val);
  78.     #else
  79.         return __builtin_popcount(val);
  80.     #endif
  81. }
  82.  
  83. inline int PopCount(uint64_t val) {
  84.     #ifdef _MSC_VER
  85.         #ifdef _WIN64
  86.             return (int)__popcnt64(val);
  87.         #else
  88.             return (int)(__popcnt((uint32_t)val) + __popcnt((uint32_t)(val >> 32)));
  89.         #endif
  90.     #else
  91.         return __builtin_popcountll(val);
  92.     #endif
  93. }
  94.  
  95. //////// From Lobster's dev/src/lobster/geom.h  ////////
  96.  
  97. // vec: supports 1..4 components of any numerical type.
  98.  
  99. // Compile time unrolled loops for 1..4 components,
  100. #define DOVEC(F) {                     \
  101.         const int i = 0;               \
  102.         F;                             \
  103.         if constexpr (N > 1) {         \
  104.             const int i = 1;           \
  105.             F;                         \
  106.             if constexpr (N > 2) {     \
  107.                 const int i = 2;       \
  108.                 F;                     \
  109.                 if constexpr (N > 3) { \
  110.                     const int i = 3;   \
  111.                     F;                 \
  112.                 }                      \
  113.             }                          \
  114.         }                              \
  115.     }
  116.  
  117. #define DOVECR(F) { vec<T, N> _t; DOVEC(_t.c[i] = F); return _t; }
  118. #define DOVECRI(F) { vec<int, N> _t; DOVEC(_t.c[i] = F); return _t; }
  119. #define DOVECF(I, F) { T _ = I; DOVEC(_ = F); return _; }
  120. #define DOVECB(I, F) { bool _ = I; DOVEC(_ = F); return _; }
  121.  
  122. union int2float { int i; float f; };
  123. union int2float64 { int64_t i; double f; };
  124. inline void default_debug_value(float   &a) { int2float nan; nan.i = 0x7F800001; a = nan.f; }
  125. inline void default_debug_value(double  &a) { int2float nan; nan.i = 0x7F800001; a = nan.f; }
  126. inline void default_debug_value(int64_t &a) { a = 0x1BADCAFEABADD00D; }
  127. inline void default_debug_value(int32_t &a) { a = 0x1BADCAFE; }
  128. inline void default_debug_value(uint16_t&a) { a = 0x1BAD; }
  129. inline void default_debug_value(uint8_t &a) { a = 0x1B; }
  130.  
  131. template<typename T, int C, int R> class matrix;
  132.  
  133. template<typename T, int N> struct basevec {
  134. };
  135.  
  136. template<typename T> struct basevec<T, 2> {
  137.   union {
  138.     T c[2];
  139.     struct { T x; T y; };
  140.   };
  141. };
  142.  
  143. template<typename T> struct basevec<T, 3> {
  144.   union {
  145.     T c[3];
  146.     struct { T x; T y; T z; };
  147.   };
  148. };
  149.  
  150. template<typename T> struct basevec<T, 4> {
  151.   union {
  152.     T c[4];
  153.     struct { T x; T y; T z; T w; };
  154.   };
  155. };
  156.  
  157. template<typename T, int N> struct vec : basevec<T, N> {
  158.     enum { NUM_ELEMENTS = N };
  159.     typedef T CTYPE;
  160.  
  161.     // Clang needs these, but VS is cool without them?
  162.     using basevec<T, N>::c;
  163.     using basevec<T, N>::x;
  164.     using basevec<T, N>::y;
  165.  
  166.     vec() {
  167.         #ifndef NDEBUG
  168.         DOVEC(default_debug_value(c[i]));
  169.         #endif
  170.     }
  171.  
  172.     explicit vec(T e)         { DOVEC(c[i] = e); }
  173.     explicit vec(const T *v)  { DOVEC(c[i] = v[i]); }
  174.  
  175.     template<typename U> explicit vec(const vec<U,N> &v) { DOVEC(c[i] = (T)v[i]); }
  176.  
  177.     vec(T _x, T _y, T _z, T _w) { x = _x; y = _y; assert(N == 4);
  178.                                   if constexpr (N > 2) c[2] = _z; else (void)_z;
  179.                                   if constexpr (N > 3) c[3] = _w; else (void)_w; }
  180.     vec(T _x, T _y, T _z)       { x = _x; y = _y; assert(N == 3);
  181.                                   if constexpr (N > 2) c[2] = _z; else (void)_z; }
  182.     vec(T _x, T _y)             { x = _x; y = _y; assert(N == 2); }
  183.     vec(const pair<T, T> &p)    { x = p.first; y = p.second; assert(N == 2); }
  184.  
  185.     const T *data()  const { return c; }
  186.     const T *begin() const { return c; }
  187.     const T *end()   const { return c + N; }
  188.  
  189.     T operator[](size_t i) const { return c[i]; }
  190.     T &operator[](size_t i) { return c[i]; }
  191.  
  192.     vec(const vec<T,3> &v, T e) { DOVEC(c[i] = i < 3 ? v[i] : e); }
  193.     vec(const vec<T,2> &v, T e) { DOVEC(c[i] = i < 2 ? v[i] : e); }
  194.  
  195.     vec<T,3>   xyz()     const { assert(N == 4); return vec<T,3>(c); }
  196.     vec<T,2>   xy()      const { assert(N >= 3); return vec<T,2>(c); }
  197.     pair<T, T> to_pair() const { assert(N == 2); return { x, y }; }
  198.  
  199.     vec operator+(const vec &v) const { DOVECR(c[i] + v[i]); }
  200.     vec operator-(const vec &v) const { DOVECR(c[i] - v[i]); }
  201.     vec operator*(const vec &v) const { DOVECR(c[i] * v[i]); }
  202.     vec operator/(const vec &v) const { DOVECR(c[i] / v[i]); }
  203.     vec operator%(const vec &v) const { DOVECR(c[i] % v[i]); }
  204.  
  205.     vec operator+(T e) const { DOVECR(c[i] + e); }
  206.     vec operator-(T e) const { DOVECR(c[i] - e); }
  207.     vec operator*(T e) const { DOVECR(c[i] * e); }
  208.     vec operator/(T e) const { DOVECR(c[i] / e); }
  209.     vec operator%(T e) const { DOVECR(c[i] % e); }
  210.     vec operator&(T e) const { DOVECR(c[i] & e); }
  211.     vec operator|(T e) const { DOVECR(c[i] | e); }
  212.     vec operator<<(T e) const { DOVECR(c[i] << e); }
  213.     vec operator>>(T e) const { DOVECR(c[i] >> e); }
  214.  
  215.     vec operator-() const { DOVECR(-c[i]); }
  216.  
  217.     vec &operator+=(const vec &v) { DOVEC(c[i] += v[i]); return *this; }
  218.     vec &operator-=(const vec &v) { DOVEC(c[i] -= v[i]); return *this; }
  219.     vec &operator*=(const vec &v) { DOVEC(c[i] *= v[i]); return *this; }
  220.     vec &operator/=(const vec &v) { DOVEC(c[i] /= v[i]); return *this; }
  221.  
  222.     vec &operator+=(T e) { DOVEC(c[i] += e); return *this; }
  223.     vec &operator-=(T e) { DOVEC(c[i] -= e); return *this; }
  224.     vec &operator*=(T e) { DOVEC(c[i] *= e); return *this; }
  225.     vec &operator/=(T e) { DOVEC(c[i] /= e); return *this; }
  226.     vec &operator&=(T e) { DOVEC(c[i] &= e); return *this; }
  227.  
  228.     bool operator<=(const vec &v) const {
  229.         DOVECB(true, _ && c[i] <= v[i]);
  230.     }
  231.     bool operator< (const vec &v) const {
  232.         DOVECB(true, _ && c[i] <  v[i]);
  233.     }
  234.     bool operator>=(const vec &v) const {
  235.         DOVECB(true, _ && c[i] >= v[i]);
  236.     }
  237.     bool operator> (const vec &v) const {
  238.         DOVECB(true, _ && c[i] >  v[i]);
  239.     }
  240.     bool operator==(const vec &v) const {
  241.         DOVECB(true, _ && c[i] == v[i]);
  242.     }
  243.     bool operator!=(const vec &v) const {
  244.         DOVECB(false, _ || c[i] != v[i]);
  245.     }
  246.  
  247.     bool operator<=(T e) const { DOVECB(true, _ && c[i] <= e); }
  248.     bool operator< (T e) const { DOVECB(true, _ && c[i] <  e); }
  249.     bool operator>=(T e) const { DOVECB(true, _ && c[i] >= e); }
  250.     bool operator> (T e) const { DOVECB(true, _ && c[i] >  e); }
  251.     bool operator==(T e) const { DOVECB(true, _ && c[i] == e); }
  252.     bool operator!=(T e) const { DOVECB(false, _ || c[i] != e); }
  253.  
  254.     vec<int, N> lte(T e) const { DOVECRI(c[i] <= e); }
  255.     vec<int, N> lt (T e) const { DOVECRI(c[i] <  e); }
  256.     vec<int, N> gte(T e) const { DOVECRI(c[i] >= e); }
  257.     vec<int, N> gt (T e) const { DOVECRI(c[i] >  e); }
  258.     vec<int, N> eq (T e) const { DOVECRI(c[i] == e); }
  259.     vec<int, N> ne (T e) const { DOVECRI(c[i] != e); }
  260.  
  261.     vec iflt(T e, const vec &a, const vec &b) const { DOVECR(c[i] < e ? a[i] : b[i]); }
  262.  
  263.     std::string to_string() const {
  264.         string s = "(";
  265.         DOVEC(if (i) s += ", "; s += std::to_string(c[i]));
  266.         return s + ")";
  267.     }
  268.  
  269.     T volume() const { DOVECF(1, _ * c[i]); }
  270.  
  271.     template<typename T2, int C, int R> friend class matrix;
  272. };
  273.  
  274. typedef vec<int, 2> int2;
  275.  
  276. template<typename T, int N, typename R> inline vec<int, N> rndivec(RandomNumberGenerator<R> &r,
  277.                                                                     const vec<int, N> &max) {
  278.     DOVECR(r(max[i]));
  279. }
  280.  
  281. ////////////////////////////////////////////////////////
  282.  
  283. // Copyright 2018 Wouter van Oortmerssen. All rights reserved.
  284. //
  285. // Licensed under the Apache License, Version 2.0 (the "License");
  286. // you may not use this file except in compliance with the License.
  287. // You may obtain a copy of the License at
  288. //
  289. //     http://www.apache.org/licenses/LICENSE-2.0
  290. //
  291. // Unless required by applicable law or agreed to in writing, software
  292. // distributed under the License is distributed on an "AS IS" BASIS,
  293. // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  294. // See the License for the specific language governing permissions and
  295. // limitations under the License.
  296.  
  297.  
  298. // Very simple tile based Wave Function Collapse ("Simple Tiled Model") implementation.
  299. // See: https://github.com/mxgmn/WaveFunctionCollapse
  300. // Derives adjacencies from an example rather than explicitly specified neighbors.
  301. // Does not do any symmetries/rotations unless they're in the example.
  302.  
  303. // Algorithm has a lot of similarities to A* in how its implemented.
  304. // Uses bitmasks to store the set of possible tiles, which currently limits the number of
  305. // unique tiles to 64. This restriction cool be lifted by using std::bitset instead.
  306.  
  307. // In my testing, generates a 50x50 tile map in <1 msec. 58% of such maps are conflict free.
  308. // At 100x100 that is 3 msec and 34%.
  309. // At 200x200 that is 24 msec and 13%
  310. // At 400x400 that is 205 msec and ~1%
  311. // Algorithm may need to extended to flood more than 2 neighbor levels to make it suitable
  312. // for really gigantic maps.
  313.  
  314. // inmap & outmap must point to row-major 2D arrays of the given size.
  315. // each in tile char must be in range 0..127, of which max 64 may actually be in use (may be
  316. // sparse).
  317. // Returns false if too many unique tiles in input.
  318. template<typename T> bool WaveFunctionCollapse(const int2 &insize, const char **inmap,
  319.                                                const int2 &outsize, char **outmap,
  320.                                                RandomNumberGenerator<T> &rnd,
  321.                                                int &num_contradictions) {
  322.     num_contradictions = 0;
  323.     typedef uint64_t bitmask_t;
  324.     const auto nbits = sizeof(bitmask_t) * 8;
  325.     array<int, 256> tile_lookup;
  326.     tile_lookup.fill(-1);
  327.     struct Tile { bitmask_t sides[4] = {}; int freq = 0; char tidx = 0; };
  328.     vector<Tile> tiles;
  329.     int2 neighbors[] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
  330.     // Collect unique tiles and their frequency of occurrence.
  331.     for (int iny = 0; iny < insize.y; iny++) {
  332.         for (int inx = 0; inx < insize.x; inx++) {
  333.             auto t = inmap[iny][inx];
  334.             if (tile_lookup[t] < 0) {
  335.                 // We use a bitmask_t mask for valid neighbors.
  336.                 if (tiles.size() == nbits - 1) return false;
  337.                 tile_lookup[t] = (int)tiles.size();
  338.                 tiles.push_back(Tile());
  339.             }
  340.             auto &tile = tiles[tile_lookup[t]];
  341.             tile.freq++;
  342.             tile.tidx = t;
  343.         }
  344.     }
  345.     // Construct valid neighbor bitmasks.
  346.     auto to_bitmask = [](size_t idx) { return (bitmask_t)1 << idx; };
  347.     for (int iny = 0; iny < insize.y; iny++) {
  348.         for (int inx = 0; inx < insize.x; inx++) {
  349.             auto t = inmap[iny][inx];
  350.             auto &tile = tiles[tile_lookup[t]];
  351.             int ni = 0;
  352.             for (auto n : neighbors) {
  353.                 auto p = (n + int2(inx, iny) + insize) % insize;
  354.                 auto tn = inmap[p.y][p.x];
  355.                 assert(tile_lookup[tn] >= 0);
  356.                 tile.sides[ni] |= to_bitmask(tile_lookup[tn]);
  357.                 ni++;
  358.             }
  359.         }
  360.     }
  361.     size_t most_common_tile_id = 0;
  362.     int most_common_tile_freq = 0;
  363.     for (auto &tile : tiles) if (tile.freq > most_common_tile_freq) {
  364.         most_common_tile_freq = tile.freq;
  365.         most_common_tile_id = &tile - &tiles[0];
  366.     }
  367.     // Track an open list (much like A*) of next options, sorted by best candidate at the end.
  368.     list<pair<int2, int>> open, temp;
  369.     // Store a bitmask per output cell of remaining possible choices.
  370.     auto max_bitmask = (1 << tiles.size()) - 1;
  371.     enum class State : int { NEW, OPEN, CLOSED };
  372.     struct Cell {
  373.         bitmask_t wf;
  374.         int popcnt = 0;
  375.         State state = State::NEW;
  376.         list<pair<int2, int>>::iterator it;
  377.         Cell(bitmask_t wf, int popcnt) : wf(wf), popcnt(popcnt) {}
  378.     };
  379.     vector<vector<Cell>> cells(outsize.y, vector<Cell>(outsize.x, Cell(max_bitmask,
  380.                                                                        (int)tiles.size())));
  381.     auto start = rndivec<int, 2>(rnd, outsize);
  382.     open.push_back({ start, 0 });  // Start.
  383.     auto &scell = cells[start.y][start.x];
  384.     scell.state = State::OPEN;
  385.     scell.it = open.begin();
  386.     // Pick tiles until no more possible.
  387.     while (!open.empty()) {
  388.         // Simply picking the first list item results in the same chance of conflicts as
  389.         // random picks over equal options, but it is assumed the latter could generate more
  390.         // interesting maps.
  391.         int num_candidates = 1;
  392.         auto numopts_0 = cells[open.back().first.y][open.back().first.x].popcnt;
  393.         for (auto it = ++open.rbegin(); it != open.rend(); ++it)
  394.             if (numopts_0 == cells[it->first.y][it->first.x].popcnt &&
  395.                 open.back().second == it->second)
  396.                 num_candidates++;
  397.             else
  398.                 break;
  399.         auto candidate_i = rnd(num_candidates);
  400.         auto candidate_it = --open.end();
  401.         for (int i = 0; i < candidate_i; i++) --candidate_it;
  402.         auto cur = candidate_it->first;
  403.         temp.splice(temp.end(), open, candidate_it);
  404.         auto &cell = cells[cur.y][cur.x];
  405.         assert(cell.state == State::OPEN);
  406.         cell.state = State::CLOSED;
  407.         bool contradiction = !cell.popcnt;
  408.         if (contradiction) {
  409.             num_contradictions++;
  410.             // Rather than failing right here, fill in the whole map as best as possible just in
  411.             // case a map with bad tile neighbors is still useful to the caller.
  412.             // As a heuristic lets just use the most common tile, as that will likely have the
  413.             // most neighbor options.
  414.             cell.wf = to_bitmask(most_common_tile_id);
  415.             cell.popcnt = 1;
  416.         }
  417.         // From our options, pick one randomly, weighted by frequency of tile occurrence.
  418.         // First find total frequency.
  419.         int total_freq = 0;
  420.         for (size_t i = 0; i < tiles.size(); i++)
  421.             if (cell.wf & to_bitmask(i))
  422.                 total_freq += tiles[i].freq;
  423.         auto freqpick = rnd(total_freq);
  424.         // Now pick.
  425.         size_t picked = 0;
  426.         for (size_t i = 0; i < tiles.size(); i++) if (cell.wf & to_bitmask(i)) {
  427.             picked = i;
  428.             if ((freqpick -= tiles[i].freq) <= 0) break;
  429.         }
  430.         assert(freqpick <= 0);
  431.         // Modify the picked tile.
  432.         auto &tile = tiles[picked];
  433.         outmap[cur.y][cur.x] = tile.tidx;
  434.         cell.wf = to_bitmask(picked);  // Exactly one option remains.
  435.         cell.popcnt = 1;
  436.         // Now lets cycle thru neighbors, reduce their options (and maybe their neighbors options),
  437.         // and add them to the open list for next pick.
  438.         int ni = 0;
  439.         for (auto n : neighbors) {
  440.             auto p = (cur + n + outsize) % outsize;
  441.             auto &ncell = cells[p.y][p.x];
  442.             if (ncell.state != State::CLOSED) {
  443.                 ncell.wf &= tile.sides[ni]; // Reduce options.
  444.                 ncell.popcnt = PopCount(ncell.wf);
  445.                 int totalnnumopts = 0;
  446.                 if (!contradiction) {
  447.                     // Hardcoded second level of neighbors of neighbors, to reduce chance of
  448.                     // contradiction.
  449.                     // Only do this when our current tile isn't a contradiction, to avoid
  450.                     // artificially shrinking options.
  451.                     int nni = 0;
  452.                     for (auto nn : neighbors) {
  453.                         auto pnn = (p + nn + outsize) % outsize;
  454.                         auto &nncell = cells[pnn.y][pnn.x];
  455.                         if (nncell.state != State::CLOSED) {
  456.                             // Collect the superset of possible options. If we remove anything but
  457.                             // these, we are guaranteed the direct neigbor always has a possible
  458.                             //pick.
  459.                             bitmask_t superopts = 0;
  460.                             for (size_t i = 0; i < tiles.size(); i++)
  461.                                 if (ncell.wf & to_bitmask(i))
  462.                                     superopts |= tiles[i].sides[nni];
  463.                             nncell.wf &= superopts;
  464.                             nncell.popcnt = PopCount(nncell.wf);
  465.                         }
  466.                         totalnnumopts += nncell.popcnt;
  467.                         nni++;
  468.                     }
  469.                 }
  470.                 if (ncell.state == State::OPEN) {
  471.                     // Already in the open list, remove it for it to be re-added just in case
  472.                     // its location is not optimal anymore.
  473.                     totalnnumopts = min(totalnnumopts, ncell.it->second);
  474.                     temp.splice(temp.end(), open, ncell.it);  // Avoid alloc.
  475.                 }
  476.                 // Insert this neighbor, sorted by lowest possibilities.
  477.                 // Use total possibilities of neighbors as a tie-breaker to avoid causing
  478.                 // contradictions by needless surrounding of tiles.
  479.                 list<pair<int2, int>>::iterator dit = open.begin();
  480.                 for (auto it = open.rbegin(); it != open.rend(); ++it) {
  481.                     auto onumopts = cells[it->first.y][it->first.x].popcnt;
  482.                     if (onumopts > ncell.popcnt ||
  483.                         (onumopts == ncell.popcnt && it->second >= totalnnumopts)) {
  484.                         dit = it.base();
  485.                         break;
  486.                     }
  487.                 }
  488.                 if (temp.empty()) temp.push_back({});
  489.                 open.splice(dit, temp, ncell.it = temp.begin());
  490.                 *ncell.it = { p, totalnnumopts };
  491.                 ncell.state = State::OPEN;
  492.             }
  493.             ni++;
  494.         }
  495.     }
  496.     return true;
  497. }
  498.  
  499. ////////////////////////////////////////////////////////
  500.  
  501. #include <stdio.h>
  502. #include <stdlib.h>
  503.  
  504. #include <map>
  505. #include <string>
  506.  
  507. // Where to write the generated JSON.
  508. #define OUTPUT_FILE "game/dungeons/0_procgen.json"
  509.  
  510. // Starting positions for map tiles in world space.
  511. #define START_X 75
  512. #define START_Z -1295
  513.  
  514. // Number of tiles on each axis.
  515. #define MAP_WIDTH 10
  516. #define MAP_HEIGHT 20
  517.  
  518. // One contradiction is considered manageable for most maps.
  519. #define MAX_CONTRADICTIONS 1
  520.  
  521. int main(){
  522.     std::map<char,std::string> tile_models;
  523.     tile_models[0x20] = ""; // Space = empty.
  524.     tile_models['+'] = "floor_001.gltf";
  525.     tile_models['/'] = "beach_corner_northwest.gltf";
  526.     tile_models['-'] = "beach_north.gltf";
  527.     tile_models['\\'] = "beach_corner_northeast.gltf";
  528.     tile_models[']'] = "beach_east.gltf";
  529.     tile_models['J'] = "beach_corner_southeast.gltf";
  530.     tile_models['_'] = "beach_south.gltf";
  531.     tile_models['L'] = "beach_corner_southwest.gltf";
  532.     tile_models['['] = "beach_west.gltf";
  533.     tile_models['v'] = "slope_001_north.gltf";
  534.     tile_models['^'] = "slope_001_south.gltf";
  535.     tile_models['>'] = "slope_001_west.gltf";
  536.     tile_models['<'] = "slope_001_east.gltf";
  537.     tile_models['H'] = "bridge_010_x.gltf";
  538.     tile_models['I'] = "bridge_010_z.gltf";
  539.     tile_models['='] = "overpass_010_x.gltf";
  540.  
  541.     // Example data that WFC uses.
  542.     auto insize = int2( 24, 11 );
  543.     std::vector<char*> inmap = {
  544.         (char*)R"(/---^---\ /----------^\ )",
  545.         (char*)R"(<+++++++] [+++++++++++>H)",
  546.         (char*)R"([+++++++>H<+++++++__++] )",
  547.         (char*)R"(<+++++++] [++++++]  [+>H)",
  548.         (char*)R"(L___v___J [++++++]  [+] )",
  549.         (char*)R"(    I     [+++++++\ [+] )",
  550.         (char*)R"( /--^-----++++++++] [+] )",
  551.         (char*)R"(H<++++++++++++++++>H===H)",
  552.         (char*)R"( [++++++++++++++++] [+] )",
  553.         (char*)R"( L__v_____________J LvJ )",
  554.         (char*)R"(    I                I  )"
  555.     };
  556.  
  557.     // Output map.
  558.     auto outsize = int2( MAP_WIDTH, MAP_HEIGHT );
  559.     std::vector<char*> outmap;
  560.     for( int y = 0; y < MAP_HEIGHT; y++ ){
  561.         outmap.push_back( (char*)calloc( MAP_WIDTH, 1 ) );
  562.     }
  563.  
  564.     // RNG.
  565.     RandomNumberGenerator<PCG32> r;
  566.     r.seed( 50 );
  567.  
  568.     // Output JSON.
  569.     std::string outjson = "{ // Generated by wfcgen\n\t\"partitions\": [\n";
  570.  
  571.     for( int i = 0; i < 10000; i++ ){ // 10000 attempts could take hours in some cases.
  572.         // Contradiction counter.
  573.         int num_contradictions = 0;
  574.  
  575.         if( !WaveFunctionCollapse(
  576.                 insize,
  577.                 (const char**)inmap.data(),
  578.                 outsize,
  579.                 outmap.data(),
  580.                 r,
  581.                 num_contradictions ) ){
  582.             fprintf( stderr, "Too many unique tiles in input\n" );
  583.             return 1;
  584.         }
  585.         if( num_contradictions <= MAX_CONTRADICTIONS ){
  586.             // Got a map! Scroll vertically and try to find a near-optimal lower left edge.
  587.             // This part is very specific to RSOD's map and should NOT be used in other games.
  588.             int offset_y = 0;
  589.             for( offset_y = 0; offset_y < MAP_HEIGHT; offset_y++ ){
  590.                 int test_y = (MAP_HEIGHT - 1 + offset_y) % MAP_HEIGHT;
  591.                 bool success = true;
  592.                 for( int x = 1; x <= 7; x++ ){
  593.                     if( outmap[test_y][x] != '+' ) success = false;
  594.                 }
  595.                 if( success ) break;
  596.             }
  597.             // One more RSOD-specific check: Make sure the map does not have sections that are blocked by empty rows.
  598.             bool good_map = true;
  599.             for( int y = 1; y < MAP_HEIGHT; y++ ){
  600.                 for( int x = 0; x < MAP_WIDTH; x++ ){
  601.                     if( outmap[(y + offset_y) % MAP_HEIGHT][x] != 0x20 )
  602.                         break;
  603.                     if( x == MAP_WIDTH - 1 ) good_map = false;
  604.                 }
  605.                 if( !good_map ) break;
  606.             }
  607.             if( good_map ){
  608.                 // Force map edges to be regular cement floors.
  609.                 // Top edge.
  610.                 for( int x = 0; x < MAP_WIDTH; x++ ){
  611.                     char &c = outmap[offset_y % MAP_HEIGHT][x];
  612.                     if( c != 0x20 ) c = '+';
  613.                 }
  614.                 // Bottom edge.
  615.                 for( int x = 0; x < MAP_WIDTH; x++ ){
  616.                     char &c = outmap[(MAP_HEIGHT - 1 + offset_y) % MAP_HEIGHT][x];
  617.                     if( c != 0x20 ) c = '+';
  618.                 }
  619.                 // Left edge.
  620.                 for( int y = 0; y < MAP_HEIGHT; y++ ){
  621.                     char &c = outmap[y][0];
  622.                     if( c != 0x20 ) c = '+';
  623.                 }
  624.                 // Right edge.
  625.                 for( int y = 0; y < MAP_HEIGHT; y++ ){
  626.                     char &c = outmap[y][MAP_WIDTH - 1];
  627.                     if( c != 0x20 ) c = '+';
  628.                 }
  629.                 // Output the map.
  630.                 for( int y = 0; y < MAP_HEIGHT; y++ ){
  631.                     for( int x = 0; x < MAP_WIDTH; x++ ){
  632.                         char c = outmap[(y + offset_y) % MAP_HEIGHT][x];
  633.                         putchar( c );
  634.                         int world_x = x * 50 + START_X, world_z = y * 50 + START_Z;
  635.                         // Select a model.
  636.                         auto it = tile_models.find( c );
  637.                         if( it != tile_models.end()
  638.                             && it->second.length() > 0 ){
  639.                             outjson += std::string( "\t\t{\n" )
  640.                                 + "\t\t\t\"map\": \"" + it->second + "\",\n"
  641.                                 + "\t\t\t\"translation\": [ " + std::to_string( world_x ) + ".0, 0.0, " + std::to_string( world_z ) + ".0 ],\n"
  642.                                 + "\t\t\t\"restitution\": 0.1\n"
  643.                                 + "\t\t},\n";
  644.                         }
  645.                         // Add buildings.
  646.                         if( c == '+' && r(11) < 4 ){
  647.                             std::string model =
  648.                                 r(5) < 2 ? (r(2) ? (r(2) ? "bar" : "store") : (r(2) ? "restaurant" : "apartments")) : "apartments";
  649.                             outjson += std::string( "\t\t{\n" )
  650.                                 + "\t\t\t\"map\": \"" + model + ".gltf\",\n"
  651.                                 + "\t\t\t\"translation\": [ " + std::to_string( world_x ) + ".0, 1.0, " + std::to_string( world_z ) + ".0 ],\n"
  652.                                 + "\t\t\t\"restitution\": 0.1\n"
  653.                                 + "\t\t},\n";
  654.                         }
  655.                     }
  656.                     putchar( '\n' );
  657.                 }
  658.                 printf( "num_contradictions: %d (Attempts made: %d)\n\n", num_contradictions, i + 1 );
  659.                 outjson += "\t]\n}\n";
  660.                 FILE *file = fopen( OUTPUT_FILE, "w" );
  661.                 if( file ){
  662.                     fprintf( file, "%s", outjson.c_str() );
  663.                     fclose( file );
  664.                     printf( "File written: %s\n", OUTPUT_FILE );
  665.                 }
  666.                 return 0;
  667.             }
  668.         }
  669.  
  670.         // Clear the output map and try again.
  671.         for( auto &row : outmap ){
  672.             for( int x = 0; x < MAP_WIDTH; x++ ){
  673.                 row[x] = 0;
  674.             }
  675.         }
  676.     }
  677.     fprintf( stderr,
  678.         "Failed to generate a satisfactory map. Consider changing example data or shrinking the output size." );
  679.     return 2;
  680. }
  681.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!