34 static std::vector<std::vector<int>>
collapse(
int width,
int height,
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));
42 const int W = width, H = height;
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));
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);
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;
61 auto [ent, x, y] = pq.top(); pq.pop();
62 if ((
int)cell[y][x].size() != ent)
continue;
63 if (cell[y][x].size() <= 1)
continue;
66 int choice = cell[y][x][s % cell[y][x].size()];
67 cell[y][x] = {choice};
69 std::vector<std::pair<int,int>> work{{x, y}};
70 while (!work.empty()) {
71 auto [cx, cy] = work.back(); work.pop_back();
73 std::vector<unsigned char> allow(tileCount, 0);
74 for (
int t : cell[cy][cx])
76 if (a >= 0 && a < tileCount) allow[a] = 1;
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;
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);
86 if (kept.empty())
continue;
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);
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];