Advertisement
Guest User

Untitled

a guest
Mar 19th, 2023
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 23.12 KB | None | 0 0
  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