about summary refs log tree commit diff stats
path: root/Source/Randomizer2Core.cpp
diff options
context:
space:
mode:
authorStar Rauchenberger <fefferburbia@gmail.com>2021-08-21 17:12:29 -0400
committerStar Rauchenberger <fefferburbia@gmail.com>2021-08-21 17:12:29 -0400
commitc60df0e75e63f488d94fd744ad70df8124dc7724 (patch)
tree92940cd8c0da9102c7f1f9ef37ed4d4b5d341985 /Source/Randomizer2Core.cpp
parent02327bf40bb9f6ef8d5e17fa982da70a3fe93eb4 (diff)
downloadwitness-tutorializer-c60df0e75e63f488d94fd744ad70df8124dc7724.tar.gz
witness-tutorializer-c60df0e75e63f488d94fd744ad70df8124dc7724.tar.bz2
witness-tutorializer-c60df0e75e63f488d94fd744ad70df8124dc7724.zip
Souped up the UI
Diffstat (limited to 'Source/Randomizer2Core.cpp')
-rw-r--r--Source/Randomizer2Core.cpp203
1 files changed, 0 insertions, 203 deletions
diff --git a/Source/Randomizer2Core.cpp b/Source/Randomizer2Core.cpp deleted file mode 100644 index 867fa5a..0000000 --- a/Source/Randomizer2Core.cpp +++ /dev/null
@@ -1,203 +0,0 @@
1#include "pch.h"
2#include "Randomizer2Core.h"
3#include "Random.h"
4
5std::vector<Pos> Randomizer2Core::CutEdges(const Puzzle& p, size_t numEdges) {
6 return CutEdgesInternal(p, 0, p.width, 0, p.height, numEdges);
7}
8
9std::vector<Pos> Randomizer2Core::CutInsideEdges(const Puzzle& p, size_t numEdges) {
10 return CutEdgesInternal(p, 1, p.width-1, 1, p.height-1, numEdges);
11}
12
13std::vector<Pos> Randomizer2Core::CutSymmetricalEdgePairs(const Puzzle& p, size_t numEdges) {
14 Puzzle copy = p;
15 // Prevent cuts from landing on the midline
16 if (p.symmetry == Puzzle::Symmetry::X) {
17 for (int y=0; y<p.height; y++) {
18 copy.grid[p.width/2][y].gap = Cell::Gap::FULL;
19 }
20 return CutEdgesInternal(copy, 0, (p.width-1)/2, 0, p.height, numEdges);
21 } else if (p.symmetry == Puzzle::Symmetry::Y) {
22 for (int x=0; x<p.width; x++) {
23 copy.grid[x][p.height/2].gap = Cell::Gap::FULL;
24 }
25 return CutEdgesInternal(copy, 0, p.width, 0, (p.height-1)/2, numEdges);
26 } else {
27 assert(p.symmetry == Puzzle::Symmetry::XY);
28 int midX = p.width/2;
29 int midY = p.height/2;
30 if (p.width%4 == 1 && p.height%4 == 1) { // For double-even grids, cut around the center
31 copy.grid[midX-1][midY].gap = Cell::Gap::FULL;
32 copy.grid[midX][midY-1].gap = Cell::Gap::FULL;
33 copy.grid[midX][midY+1].gap = Cell::Gap::FULL;
34 copy.grid[midX+1][midY].gap = Cell::Gap::FULL;
35 } else if (p.width%4 == 1 && p.height%4 == 3) { // For half-even grids, there's only one line to cut
36 copy.grid[midX][midY].gap = Cell::Gap::FULL;
37 } else if (p.width%4 == 3 && p.height%4 == 1) { // For half-even grids, there's only one line to cut
38 copy.grid[midX][midY].gap = Cell::Gap::FULL;
39 }
40 return CutEdgesInternal(copy, 0, p.width, 0, p.height, numEdges);
41 }
42}
43
44std::vector<Pos> Randomizer2Core::CutEdgesInternal(const Puzzle& p, int xMin, int xMax, int yMin, int yMax, size_t numEdges) {
45 std::vector<Pos> edges;
46 for (int x=xMin; x<xMax; x++) {
47 for (int y=yMin; y<yMax; y++) {
48 if (x%2 == y%2) continue;
49 if (p.grid[x][y].gap != Cell::Gap::NONE) continue;
50 if (p.grid[x][y].start) continue;
51 if (p.grid[x][y].end != Cell::Dir::NONE) continue;
52
53 if (p.symmetry == Puzzle::Symmetry::XY) {
54 assert(p.width == p.height); // TODO: This solution only supports square rotational symmetry.
55 if (x > y) continue; // Only allow cuts bottom-left of the diagonal
56 }
57
58 // If the puzzle already has a sequence, don't cut along it.
59 bool inSequence = false;
60 for (Pos pos : p.sequence) inSequence |= (pos.x == x && pos.y == y);
61 if (inSequence) continue;
62 edges.emplace_back(x, y);
63 }
64 }
65 assert(numEdges <= edges.size());
66
67 auto [colorGrid, numColors] = CreateColorGrid(p);
68 assert(numEdges <= numColors);
69
70 // @Hack... sort of. I couldn't think of a better way to do this.
71 if (p.symmetry == Puzzle::Symmetry::XY) {
72 // Recolor the diagonal so that opposite cells share a color. This is because we're only cutting along half their edges,
73 // so they are in fact two sides of the same cell.
74 for (int x=1; x<p.width/2; x+=2) {
75 assert(p.width == p.height); // TODO: This solution only supports square rotational symmetry.
76 colorGrid[x][x] = colorGrid[p.width-x-1][p.width-x-1];
77 }
78 }
79
80 std::vector<Pos> cutEdges;
81 for (int i=0; i<numEdges; i++) {
82 while (edges.size() > 0) {
83 int edge = Random::RandInt(0, static_cast<int>(edges.size() - 1));
84 Pos pos = edges[edge];
85 edges.erase(edges.begin() + edge);
86
87 int color1 = 0;
88 int color2 = 0;
89 if (pos.x%2 == 0 && pos.y%2 == 1) { // Vertical
90 if (pos.x > 0) color1 = colorGrid[pos.x-1][pos.y];
91 else color1 = 1;
92
93 if (pos.x < p.width - 1) color2 = colorGrid[pos.x+1][pos.y];
94 else color2 = 1;
95 } else { // Horizontal
96 assert(pos.x%2 == 1 && pos.y%2 == 0);
97 if (pos.y > 0) color1 = colorGrid[pos.x][pos.y-1];
98 else color1 = 1;
99
100 if (pos.y < p.height - 1) color2 = colorGrid[pos.x][pos.y+1];
101 else color2 = 1;
102 }
103 // Enforce color1 < color2
104 if (color1 > color2) std::swap(color1, color2);
105
106 // Colors mismatch, valid cut
107 if (color1 != color2) {
108 // @Performance... have a lookup table instead?
109 for (int x=0; x<p.width; x++) {
110 for (int y=0; y<p.height; y++) {
111 if (colorGrid[x][y] == color2) colorGrid[x][y] = color1;
112 }
113 }
114 cutEdges.emplace_back(pos);
115 break;
116 }
117 }
118 }
119 assert(cutEdges.size() == numEdges);
120 return cutEdges;
121}
122
123#ifndef NDEBUG
124#include <Windows.h>
125#endif
126
127void Randomizer2Core::DebugColorGrid(const std::vector<std::vector<int>>& colorGrid) {
128#ifndef NDEBUG
129 static std::string colors = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
130 for (int y=0; y<colorGrid[0].size(); y++) {
131 std::string row;
132 for (int x=0; x<colorGrid.size(); x++) {
133 row += colors[colorGrid[x][y]];
134 }
135 row += "\n";
136 OutputDebugStringA(row.c_str());
137 }
138 OutputDebugStringA("\n");
139#endif
140}
141
142void Randomizer2Core::FloodFill(const Puzzle& p, std::vector<std::vector<int>>& colorGrid, int color, int x, int y) {
143 if (!p.SafeCell(x, y)) return;
144 if (colorGrid[x][y] != 0) return; // Already processed.
145 colorGrid[x][y] = color;
146
147 FloodFill(p, colorGrid, color, x, y+1);
148 FloodFill(p, colorGrid, color, x, y-1);
149 FloodFill(p, colorGrid, color, x+1, y);
150 FloodFill(p, colorGrid, color, x-1, y);
151}
152
153void Randomizer2Core::FloodFillOutside(const Puzzle& p, std::vector<std::vector<int>>& colorGrid, int x, int y) {
154 if (!p.SafeCell(x, y)) return;
155 if (colorGrid[x][y] != 0) return; // Already processed.
156 if (x%2 != y%2 && p.grid[x][y].gap == Cell::Gap::NONE) return; // Only flood-fill through gaps
157 colorGrid[x][y] = 1; // Outside color
158
159 FloodFillOutside(p, colorGrid, x, y+1);
160 FloodFillOutside(p, colorGrid, x, y-1);
161 FloodFillOutside(p, colorGrid, x+1, y);
162 FloodFillOutside(p, colorGrid, x-1, y);
163}
164
165// Color key:
166// 0 (default): Uncolored
167// 1: Outside color and separator color
168// 2+: Flood-filled region color
169std::tuple<std::vector<std::vector<int>>, int> Randomizer2Core::CreateColorGrid(const Puzzle& p) {
170 std::vector<std::vector<int>> colorGrid;
171 colorGrid.resize(p.width);
172
173 for (int x=0; x<p.width; x++) {
174 colorGrid[x].resize(p.height);
175 for (int y=0; y<p.height; y++) {
176 if (x%2 == 1 && y%2 == 1) continue;
177 // Mark all unbroken edges and intersections as 'do not color'
178 if (p.grid[x][y].gap == Cell::Gap::NONE) colorGrid[x][y] = 1;
179 }
180 }
181
182 // @Future: Skip this loop if pillar = true;
183 for (int y=0; y<p.height; y++) {
184 FloodFillOutside(p, colorGrid, 0, y);
185 FloodFillOutside(p, colorGrid, p.width - 1, y);
186 }
187
188 for (int x=0; x<p.width; x++) {
189 FloodFillOutside(p, colorGrid, x, 0);
190 FloodFillOutside(p, colorGrid, x, p.height - 1);
191 }
192
193 int color = 1;
194 for (int x=0; x<p.width; x++) {
195 for (int y=0; y<p.height; y++) {
196 if (colorGrid[x][y] != 0) continue; // No dead colors
197 color++;
198 FloodFill(p, colorGrid, color, x, y);
199 }
200 }
201
202 return {colorGrid, color};
203} \ No newline at end of file