Added Wave Function Collapse functionality

aardappel · Nov 3, 2018 · 703f674 · 703f674
1 parent 3353e50
commit 703f674
Show file tree

Hide file tree

Showing 5 changed files with 342 additions and 0 deletions.
diff --git a/dev/lobster/language.vcxproj b/dev/lobster/language.vcxproj
@@ -341,6 +341,7 @@
     <ClInclude Include="..\src\lobster\unicode.h" />
     <ClInclude Include="..\src\lobster\vmdata.h" />
     <ClInclude Include="..\src\lobster\wentropy.h" />
+    <ClInclude Include="..\src\lobster\wfc.h" />
   </ItemGroup>
   <Import Project="$(VCTargetsPath)\Microsoft.Cpp.targets" />
   <ImportGroup Label="ExtensionTargets">

diff --git a/dev/lobster/language.vcxproj.filters b/dev/lobster/language.vcxproj.filters
@@ -136,5 +136,8 @@
     <ClInclude Include="..\src\lobster\natreg.h">
       <Filter>common</Filter>
     </ClInclude>
+    <ClInclude Include="..\src\lobster\wfc.h">
+      <Filter>common</Filter>
+    </ClInclude>
   </ItemGroup>
 </Project>
diff --git a/dev/src/builtins.cpp b/dev/src/builtins.cpp
@@ -17,6 +17,7 @@
 #include "lobster/natreg.h"
 
 #include "lobster/unicode.h"
+#include "lobster/wfc.h"
 
 namespace lobster {
 
@@ -1007,6 +1008,36 @@ void AddBuiltins(NativeRegistry &natreg) {
         " a vector of vectors of indices of the circles that are within dist of eachothers radius."
         " pre-filter indicates objects that should appear in the inner vectors.");
 
+    STARTDECL(wave_function_collapse) (VM &vm, Value &tilemap, Value &size) {
+        auto sz = ValueDecToINT<2>(vm, size);
+        auto rows = tilemap.vval()->len;
+        vector<const char *> inmap(rows);
+        intp cols = 0;
+        for (intp i = 0; i < rows; i++) {
+            auto sv = tilemap.vval()->At(i).sval()->strv();
+            if (i) { if ((intp)sv.size() != cols) vm.Error("all columns must be equal length"); }
+            else cols = sv.size();
+            inmap[i] = sv.data();
+        }
+        tilemap.DECRT(vm);
+        auto outstrings = ToValueOfVectorOfStringsEmpty(vm, sz, 0);
+        vector<char *> outmap(sz.y, nullptr);
+        for (int i = 0; i < sz.y; i++) outmap[i] = (char *)outstrings.vval()->At(i).sval()->data();
+        int num_contradictions = 0;
+        auto ok = WaveFunctionCollapse(int2(cols, inmap.size()), inmap.data(), sz, outmap.data(),
+                                        rnd, num_contradictions);
+        if (!ok)
+            vm.Error("tilemap contained too many tile ids");
+        vm.Push(outstrings);
+        return num_contradictions;
+    }
+    ENDDECL2(wave_function_collapse, "tilemap,size", "S]I}:2", "S]I",
+             "returns a tilemap of given size modelled after the possible shapes in the input"
+             " tilemap. Tilemap should consist of chars in the 0..127 range. Second return value"
+             " the number of failed neighbor matches, this should"
+             " ideally be 0, but can be non-0 for larger maps. Simply call this function"
+             " repeatedly until it is 0");
+
     STARTDECL(resume) (VM &vm, Value &co, Value &ret) {
         vm.CoResume(co.cval());
         // By the time CoResume returns, we're now back in the context of co, meaning that the

diff --git a/dev/src/lobster/wfc.h b/dev/src/lobster/wfc.h
@@ -0,0 +1,211 @@
+// Copyright 2018 Wouter van Oortmerssen. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+
+// Very simple tile based Wave Function Collapse ("Simple Tiled Model") implementation.
+// See: https://github.com/mxgmn/WaveFunctionCollapse
+// Derives adjacencies from an example rather than explicitly specified neighbors.
+// Does not do any symmetries/rotations unless they're in the example.
+
+// Algorithm has a lot of similarities to A* in how its implemented.
+// Uses bitmasks to store the set of possible tiles, which currently limits the number of
+// unique tiles to 64. This restriction cool be lifted by using std::bitset instead.
+
+// In my testing, generates a 50x50 tile map in <1 msec. 58% of such maps are conflict free.
+// At 100x100 that is 3 msec and 34%.
+// At 200x200 that is 24 msec and 13%
+// At 400x400 that is 205 msec and ~1%
+// Algorithm may need to extended to flood more than 2 neighbor levels to make it suitable
+// for really gigantic maps.
+
+// inmap & outmap must point to row-major 2D arrays of the given size.
+// each in tile char must be in range 0..127, of which max 64 may actually be in use (may be
+// sparse).
+// Returns false if too many unique tiles in input.
+template<typename T> bool WaveFunctionCollapse(const int2 &insize, const char **inmap,
+                                               const int2 &outsize, char **outmap,
+                                               RandomNumberGenerator<T> &rnd,
+                                               int &num_contradictions) {
+    num_contradictions = 0;
+    typedef uint64_t bitmask_t;
+    const auto nbits = sizeof(bitmask_t) * 8;
+    array<int, 256> tile_lookup;
+    tile_lookup.fill(-1);
+    struct Tile { bitmask_t sides[4] = {}; size_t freq = 0; char tidx = 0; };
+    vector<Tile> tiles;
+    int2 neighbors[] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
+    // Collect unique tiles and their frequency of occurrence.
+    for (int iny = 0; iny < insize.y; iny++) {
+        for (int inx = 0; inx < insize.x; inx++) {
+            auto t = inmap[iny][inx];
+            if (tile_lookup[t] < 0) {
+                // We use a bitmask_t mask for valid neighbors.
+                if (tiles.size() == nbits - 1) return false;
+                tile_lookup[t] = (int)tiles.size();
+                tiles.push_back(Tile());
+            }
+            auto &tile = tiles[tile_lookup[t]];
+            tile.freq++;
+            tile.tidx = t;
+        }
+    }
+    // Construct valid neighbor bitmasks.
+    for (int iny = 0; iny < insize.y; iny++) {
+        for (int inx = 0; inx < insize.x; inx++) {
+            auto t = inmap[iny][inx];
+            auto &tile = tiles[tile_lookup[t]];
+            int ni = 0;
+            for (auto n : neighbors) {
+                auto p = (n + int2(inx, iny) + insize) % insize;
+                auto tn = inmap[p.y][p.x];
+                assert(tile_lookup[tn] >= 0);
+                tile.sides[ni] |= 1 << tile_lookup[tn];
+                ni++;
+            }
+        }
+    }
+    size_t most_common_tile_id = 0;
+    size_t most_common_tile_freq = 0;
+    for (auto &tile : tiles) if (tile.freq > most_common_tile_freq) {
+        most_common_tile_freq = tile.freq;
+        most_common_tile_id = &tile - &tiles[0];
+    }
+    // Track an open list (much like A*) of next options, sorted by best candidate at the end.
+    list<pair<int2, int>> open, temp;
+    // Store a bitmask per output cell of remaining possible choices.
+    auto max_bitmask = (1 << tiles.size()) - 1;
+    enum class State : uchar { NEW, OPEN, CLOSED };
+    struct Cell {
+        bitmask_t wf;
+        uchar popcnt = 0;
+        State state = State::NEW;
+        decltype(open)::iterator it;
+        Cell(bitmask_t wf, uchar popcnt) : wf(wf), popcnt(popcnt) {}
+    };
+    vector<vector<Cell>> cells(outsize.y, vector<Cell>(outsize.x, Cell(max_bitmask, tiles.size())));
+    auto start = rndivec<int, 2>(rnd, outsize);
+    open.push_back({ start, 0 });  // Start.
+    auto &scell = cells[start.y][start.x];
+    scell.state = State::OPEN;
+    scell.it = open.begin();
+    // Pick tiles until no more possible.
+    while (!open.empty()) {
+        // Simply picking the first list item results in the same chance of conflicts as
+        // random picks over equal options, but it is assumed the latter could generate more
+        // interesting maps.
+        size_t num_candidates = 1;
+        auto numopts_0 = cells[open.back().first.y][open.back().first.x].popcnt;
+        for (auto it = ++open.rbegin(); it != open.rend(); ++it)
+            if (numopts_0 == cells[it->first.y][it->first.x].popcnt &&
+                open.back().second == it->second)
+                num_candidates++;
+            else
+                break;
+        auto candidate_i = rnd(num_candidates);
+        auto candidate_it = --open.end();
+        for (int i = 0; i < candidate_i; i++) --candidate_it;
+        auto cur = candidate_it->first;
+        temp.splice(temp.end(), open, candidate_it);
+        auto &cell = cells[cur.y][cur.x];
+        assert(cell.state == State::OPEN);
+        cell.state = State::CLOSED;
+        bool contradiction = !cell.popcnt;
+        if (contradiction) {
+            num_contradictions++;
+            // Rather than failing right here, fill in the whole map as best as possible just in
+            // case a map with bad tile neighbors is still useful to the caller.
+            // As a heuristic lets just use the most common tile, as that will likely have the
+            // most neighbor options.
+            cell.wf = 1 << most_common_tile_id;
+            cell.popcnt = 1;
+        }
+        // From our options, pick one randomly, weighted by frequency of tile occurrence.
+        // First find total frequency.
+        size_t total_freq = 0;
+        for (size_t i = 0; i < tiles.size(); i++) if (cell.wf & (1 << i)) total_freq += tiles[i].freq;
+        auto freqpick = rnd(total_freq);
+        // Now pick.
+        size_t picked = 0;
+        for (size_t i = 0; i < tiles.size(); i++) if (cell.wf & (1 << i)) {
+            picked = i;
+            if ((freqpick -= tiles[i].freq) <= 0) break;
+        }
+        assert(freqpick <= 0);
+        // Modify the picked tile.
+        auto &tile = tiles[picked];
+        outmap[cur.y][cur.x] = tile.tidx;
+        cell.wf = 1 << picked;  // Exactly one option remains.
+        cell.popcnt = 1;
+        // Now lets cycle thru neighbors, reduce their options (and maybe their neighbors options),
+        // and add them to the open list for next pick.
+        int ni = 0;
+        for (auto n : neighbors) {
+            auto p = (cur + n + outsize) % outsize;
+            auto &ncell = cells[p.y][p.x];
+            if (ncell.state != State::CLOSED) {
+                ncell.wf &= tile.sides[ni]; // Reduce options.
+                ncell.popcnt = PopCount(ncell.wf);
+                int totalnnumopts = 0;
+                if (!contradiction) {
+                    // Hardcoded second level of neighbors of neighbors, to reduce chance of
+                    // contradiction.
+                    // Only do this when our current tile isn't a contradiction, to avoid
+                    // artificially shrinking options.
+                    int nni = 0;
+                    for (auto nn : neighbors) {
+                        auto pnn = (p + nn + outsize) % outsize;
+                        auto &nncell = cells[pnn.y][pnn.x];
+                        if (nncell.state != State::CLOSED) {
+                            // Collect the superset of possible options. If we remove anything but
+                            // these, we are guaranteed the direct neigbor always has a possible
+                            //pick.
+                            bitmask_t superopts = 0;
+                            for (size_t i = 0; i < tiles.size(); i++)
+                                if (ncell.wf & (1 << i))
+                                    superopts |= tiles[i].sides[nni];
+                            nncell.wf &= superopts;
+                            nncell.popcnt = PopCount(nncell.wf);
+                        }
+                        totalnnumopts += nncell.popcnt;
+                        nni++;
+                    }
+                }
+                if (ncell.state == State::OPEN) {
+                    // Already in the open list, remove it for it to be re-added just in case
+                    // its location is not optimal anymore.
+                    totalnnumopts = min(totalnnumopts, ncell.it->second);
+                    temp.splice(temp.end(), open, ncell.it);  // Avoid alloc.
+                }
+                // Insert this neighbor, sorted by lowest possibilities.
+                // Use total possibilities of neighbors as a tie-breaker to avoid causing
+                // contradictions by needless surrounding of tiles.
+                decltype(open)::iterator dit = open.begin();
+                for (auto it = open.rbegin(); it != open.rend(); ++it) {
+                    auto onumopts = cells[it->first.y][it->first.x].popcnt;
+                    if (onumopts > ncell.popcnt ||
+                        (onumopts == ncell.popcnt && it->second >= totalnnumopts)) {
+                        dit = it.base();
+                        break;
+                    }
+                }
+                if (temp.empty()) temp.push_back({});
+                open.splice(dit, temp, ncell.it = temp.begin());
+                *ncell.it = { p, totalnnumopts };
+                ncell.state = State::OPEN;
+            }
+            ni++;
+        }
+    }
+    return true;
+}
diff --git a/lobster/samples/wave_function_collapse.lobster b/lobster/samples/wave_function_collapse.lobster
@@ -0,0 +1,96 @@
+// Example of using Wave Function Collapse to generate gameworlds based on tiles.
+// Using ascii chars here for simplicity.
+
+// Using """ string literals so we don't have to escape \ :(
+
+tilemap :== [
+    """   /--\    """,
+    """   |  |    """,
+    """   |  |    """,
+    """/--J  L--\ """,
+    """|        | """,
+    """|        | """,
+    """L--\  /--J """,
+    """   |  |    """,
+    """   |  |    """,
+    """   L--J    """,
+    """           """,
+]
+
+benchmark :== false
+
+if benchmark:
+    no_conflicts := 0
+    for(1000) i:
+        outmap, conflicts := wave_function_collapse(tilemap, xy { 100, 100 })
+        print i + ": " + conflicts
+        if not conflicts: no_conflicts++
+    print no_conflicts
+    print seconds_elapsed()
+
+else:
+    // Just print a single no-conflict example.
+    for(100) i:
+        outmap, conflicts := wave_function_collapse(tilemap, xy { 100, 50 })
+        if not conflicts:
+            print "iteration: " + i
+            for(outmap) s: print s
+            return from program
+
+/*
+
+prints:
+
+           |      |  /-\ /-------J  |    |  L-J                                      /--J
+           |   /--J  | | |          |    |                                           |
+           |   |     | L-J          |    |                                    /-\    |
+-----------J /-J     |              |    |     /------------\                 | |    |             /
+             |       L-\       /----J    |     |            |                 | |    |             |
+             |         |       |      /--J     |            |                 | L----J             |
+             |         |       L-\    |        |            |                 |                    |
+----\        |         L-\       |    | /-\  /-J            |                 |                    L
+    |        |           |       |    | | |  |              L-------------\   |      /---\
+    |        |           | /-----J    L-J L--J                            |   L-\    |   |
+    |        |           | |                                              |     |    |   |
+    |        |           | |                              /-------\       |     |    |   |
+    |        |           | |                              |       |       |     L----J   |
+    |        | /---------J L-----\                        |   /---J       |              |
+  /-J        | |                 |                  /-----J   |         /-J         /----J
+  |          | |                 |         /----\   |         |         |           |
+  |          | |      /-\   /----J         |    |   |         |         |           |
+  |          | |      | |   |              |    |   |         |         |    /------J
+  |          | |      | | /-J  /--\  /-----J    |   |         |         |    |
+  |          L-J      | | |    |  |  |          |   |         |      /--J    |
+  L-----\             | | |    |  L--J          |   L---\     |      |       |    /--\      /----\
+        |   /---\     | | |    |                |       |     L------J       |    |  |      |    |
+        |   |   |     | | |    |                |       |                    |    |  |      |    |
+--\     |   |   L-----J | |    |                |       |                    |    |  |      |    L--
+  |     |   |           | L--\ |       /--------J       |                    |    |  |   /--J
+--J  /--J   |      /-\  |    | |       |                |                 /--J    |  |   |    /-----
+     |      L---\  | |  |    | |       |                |                 |       |  L---J    |
+     |          |  | |  |    | |       |                |      /----\     |       |           |
+     |          L--J |  |    | |       |       /-\      |      |    |     |       |  /----\   L----\
+     |               |  |    L-J       |       | |      |      |    |     |       |  |    |        |
+     L------------\  |  |              L-------J |      |      |    |     |       |  |    |        |
+                  |  |  |                        |      |      |    |     |       |  |    L--\     |
+    /-------------J  |  |          /---\         |      L------J    |     |       |  |       |     |
+    |              /-J  |          |   |     /---J                  |     |       |  |       |     |
+    |              |    L------\   |   L---\ |                      |     |       |  L--\ /--J     |
+    |         /-\  L-\         |   |       | |                      |     L-----\ |     | |        |
+    |         | |    |         |   |       | |         /----\       | /-\       | L--\  | |        |
+--\ |         | |    |         L---J       | L--\      |    |       | | |       |    |  | |        L
+  | |         | |    |                     |    |      |  /-J       | L-J       |    |  | |
+  L-J         L-J    L---------\           |    |      |  |         |        /--J    |  | |
+                               |           L-\  |      |  |         |        |       |  | L---\
+----\                /---\     |             |  L------J  |         |        |       |  |     |  /--
+    |                |   |     |             |            |         |        L--\    |  |     |  |
+    |                L---J     |         /---J            |         |           |    L--J     |  |
+    |                          | /--\    |     /--\       |         |           |             |  |
+    L------\             /-----J |  |    |     |  |       |         |        /--J             |  |
+           |      /--\   |       |  |    |     L--J       |         |        |                |  |
+           |      |  |   |       |  |    |  /-\           L-------\ |        L----------\     |  |
+           |      |  L---J       |  |    |  | |                   | |                   |     L--J
+           |      |              |  |    |  | |                   L-J                   |
+
+*/
+