P-E-R-R-Y
Utilitaires, contrats et vendors du moteur, en une seule doc
Loading...
Searching...
No Matches
WaveFunctionCollapse.hpp
Go to the documentation of this file.
1
10
11#pragma once
12
13#include <queue>
14#include <vector>
15#include "Deterministic.hpp"
16
18public:
24 struct Rules {
25 std::vector<std::vector<int>> neighbors;
26 int tileCount() const { return (int)neighbors.size(); }
27 };
28
34 static std::vector<std::vector<int>> collapse(int width, int height,
35 const Rules& rules,
36 uint64_t seed = 0)
37 {
38 if (rules.tileCount() <= 0 || width <= 0 || height <= 0)
39 return std::vector<std::vector<int>>(std::max(0, height),
40 std::vector<int>(std::max(0, width), 0));
41
42 const int W = width, H = height;
43 const int tileCount = rules.tileCount();
44
45 std::vector<int> all(tileCount);
46 for (int i = 0; i < tileCount; ++i) all[i] = i;
47 std::vector<std::vector<std::vector<int>>> cell(
48 H, std::vector<std::vector<int>>(W, all));
49
50 using Entry = std::tuple<int, int, int>;
51 std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> pq;
52 for (int y = 0; y < H; ++y)
53 for (int x = 0; x < W; ++x)
54 pq.emplace(tileCount, x, y);
55
56 const int dxs[4] = {1, -1, 0, 0};
57 const int dys[4] = {0, 0, 1, -1};
58 uint64_t s = seed ? seed : 1;
59
60 while (!pq.empty()) {
61 auto [ent, x, y] = pq.top(); pq.pop();
62 if ((int)cell[y][x].size() != ent) continue; // stale
63 if (cell[y][x].size() <= 1) continue; // collapsed
64
65 s = mix64(s);
66 int choice = cell[y][x][s % cell[y][x].size()];
67 cell[y][x] = {choice};
68
69 std::vector<std::pair<int,int>> work{{x, y}};
70 while (!work.empty()) {
71 auto [cx, cy] = work.back(); work.pop_back();
72
73 std::vector<unsigned char> allow(tileCount, 0);
74 for (int t : cell[cy][cx])
75 for (int a : rules.neighbors[t])
76 if (a >= 0 && a < tileCount) allow[a] = 1;
77
78 for (int d = 0; d < 4; ++d) {
79 int nx = cx + dxs[d], ny = cy + dys[d];
80 if (nx < 0 || nx >= W || ny < 0 || ny >= H) continue;
81
82 std::vector<int> kept;
83 kept.reserve(cell[ny][nx].size());
84 for (int v : cell[ny][nx]) if (allow[v]) kept.push_back(v);
85
86 if (kept.empty()) continue; // contradiction → skip, accept local violation
87
88 if (kept.size() < cell[ny][nx].size()) {
89 cell[ny][nx] = std::move(kept);
90 pq.emplace((int)cell[ny][nx].size(), nx, ny);
91 work.emplace_back(nx, ny);
92 }
93 }
94 }
95 }
96
97 std::vector<std::vector<int>> result(H, std::vector<int>(W));
98 for (int y = 0; y < H; ++y)
99 for (int x = 0; x < W; ++x)
100 result[y][x] = cell[y][x].empty() ? 0 : cell[y][x][0];
101 return result;
102 }
103};
104
Definition WaveFunctionCollapse.hpp:17
static std::vector< std::vector< int > > collapse(int width, int height, const Rules &rules, uint64_t seed=0)
Generate a width x height tile map. Best-effort: returns a complete grid even if a few adjacencies en...
Definition WaveFunctionCollapse.hpp:34
uint64_t mix64(uint64_t x) noexcept
Definition Deterministic.hpp:40
User-defined adjacency rules. Tile IDs are indices 0..neighbors.size()-1. neighbors[t] = list of tile...
Definition WaveFunctionCollapse.hpp:24
int tileCount() const
Definition WaveFunctionCollapse.hpp:26
std::vector< std::vector< int > > neighbors
Definition WaveFunctionCollapse.hpp:25