diff options
author | jbzdarkid <jbzdarkid@gmail.com> | 2019-11-16 14:22:39 -0800 |
---|---|---|
committer | jbzdarkid <jbzdarkid@gmail.com> | 2019-11-16 14:22:39 -0800 |
commit | fc8649b12fc1280d81e8dd4d35736ed69c0d9909 (patch) | |
tree | 7d6686c82dd6d738bdb54eb54d9989a4549cfdb5 /Source | |
parent | 039b48fe49c31f6033a17aabab353b7b7696e11b (diff) | |
download | witness-tutorializer-fc8649b12fc1280d81e8dd4d35736ed69c0d9909.tar.gz witness-tutorializer-fc8649b12fc1280d81e8dd4d35736ed69c0d9909.tar.bz2 witness-tutorializer-fc8649b12fc1280d81e8dd4d35736ed69c0d9909.zip |
Keep WIP
Diffstat (limited to 'Source')
-rw-r--r-- | Source/Memory.cpp | 22 | ||||
-rw-r--r-- | Source/PuzzlerSerializer.cpp | 2 | ||||
-rw-r--r-- | Source/Randomizer2.cpp | 310 | ||||
-rw-r--r-- | Source/Randomizer2Core.cpp | 164 | ||||
-rw-r--r-- | Source/Randomizer2Core.h | 21 | ||||
-rw-r--r-- | Source/Source.vcxproj | 2 |
6 files changed, 371 insertions, 150 deletions
diff --git a/Source/Memory.cpp b/Source/Memory.cpp index bc0725b..e240b90 100644 --- a/Source/Memory.cpp +++ b/Source/Memory.cpp | |||
@@ -170,7 +170,10 @@ void* Memory::ComputeOffset(std::vector<int> offsets) { | |||
170 | cumulativeAddress += offset; | 170 | cumulativeAddress += offset; |
171 | 171 | ||
172 | const auto search = _computedAddresses.find(cumulativeAddress); | 172 | const auto search = _computedAddresses.find(cumulativeAddress); |
173 | if (search == std::end(_computedAddresses)) { | 173 | // This is an issue with re-randomization. Always. Just disable it in debug mode! |
174 | #ifdef NDEBUG | ||
175 | if (search == std::end(_computedAddresses)) { | ||
176 | #endif | ||
174 | // If the address is not yet computed, then compute it. | 177 | // If the address is not yet computed, then compute it. |
175 | uintptr_t computedAddress = 0; | 178 | uintptr_t computedAddress = 0; |
176 | if (bool result = !ReadProcessMemory(_handle, reinterpret_cast<LPVOID>(cumulativeAddress), &computedAddress, sizeof(uintptr_t), NULL)) { | 179 | if (bool result = !ReadProcessMemory(_handle, reinterpret_cast<LPVOID>(cumulativeAddress), &computedAddress, sizeof(uintptr_t), NULL)) { |
@@ -180,7 +183,9 @@ void* Memory::ComputeOffset(std::vector<int> offsets) { | |||
180 | ThrowError(); | 183 | ThrowError(); |
181 | } | 184 | } |
182 | _computedAddresses[cumulativeAddress] = computedAddress; | 185 | _computedAddresses[cumulativeAddress] = computedAddress; |
186 | #ifdef NDEBUG | ||
183 | } | 187 | } |
188 | #endif | ||
184 | 189 | ||
185 | cumulativeAddress = _computedAddresses[cumulativeAddress]; | 190 | cumulativeAddress = _computedAddresses[cumulativeAddress]; |
186 | } | 191 | } |
@@ -188,6 +193,21 @@ void* Memory::ComputeOffset(std::vector<int> offsets) { | |||
188 | } | 193 | } |
189 | 194 | ||
190 | uintptr_t Memory::Allocate(size_t bytes) { | 195 | uintptr_t Memory::Allocate(size_t bytes) { |
196 | /* | ||
197 | uintptr_t ForeignProcessMemory::AllocateMemory(size_t Size, DWORD Flags) const { | ||
198 | if (!ProcessHandle) { | ||
199 | return 0; | ||
200 | } | ||
201 | return (uintptr_t)VirtualAllocEx(ProcessHandle, nullptr, Size, MEM_RESERVE | MEM_COMMIT, Flags); | ||
202 | } | ||
203 | |||
204 | void ForeignProcessMemory::DeallocateMemory(uintptr_t Addr) const { | ||
205 | if (!ProcessHandle || Addr == 0) { | ||
206 | return; | ||
207 | } | ||
208 | VirtualFreeEx(ProcessHandle, (void*)Addr, 0, MEM_RELEASE); | ||
209 | } | ||
210 | */ | ||
191 | uintptr_t current = _freeMem; | 211 | uintptr_t current = _freeMem; |
192 | _freeMem += bytes; | 212 | _freeMem += bytes; |
193 | 213 | ||
diff --git a/Source/PuzzlerSerializer.cpp b/Source/PuzzlerSerializer.cpp index cf013ca..8ab1649 100644 --- a/Source/PuzzlerSerializer.cpp +++ b/Source/PuzzlerSerializer.cpp | |||
@@ -41,6 +41,8 @@ void PuzzleSerializer::WritePuzzle(const Puzzle& p, int id) { | |||
41 | VERTI_GAP_SIZE = HEIGHT_INTERVAL / 2; | 41 | VERTI_GAP_SIZE = HEIGHT_INTERVAL / 2; |
42 | 42 | ||
43 | WriteIntersections(p); | 43 | WriteIntersections(p); |
44 | WriteDots(p); | ||
45 | WriteGaps(p); | ||
44 | WriteEndpoints(p); | 46 | WriteEndpoints(p); |
45 | WriteDecorations(p, id); | 47 | WriteDecorations(p, id); |
46 | WriteSequence(p, id); | 48 | WriteSequence(p, id); |
diff --git a/Source/Randomizer2.cpp b/Source/Randomizer2.cpp index b5218bf..81b6874 100644 --- a/Source/Randomizer2.cpp +++ b/Source/Randomizer2.cpp | |||
@@ -3,6 +3,7 @@ | |||
3 | #include "Random.h" | 3 | #include "Random.h" |
4 | #include "Solver.h" | 4 | #include "Solver.h" |
5 | #include "Memory.h" | 5 | #include "Memory.h" |
6 | #include "Randomizer2Core.h" | ||
6 | #include "PuzzlerSerializer.h" | 7 | #include "PuzzlerSerializer.h" |
7 | #include <cassert> | 8 | #include <cassert> |
8 | #include <string> | 9 | #include <string> |
@@ -155,173 +156,184 @@ void Randomizer2::Randomize() { | |||
155 | 156 | ||
156 | } | 157 | } |
157 | 158 | ||
158 | void DebugColorGrid(const std::vector<std::vector<int>>& colorGrid) { | 159 | void Randomizer2::RandomizeKeep() { |
159 | for (int y=0; y<colorGrid[0].size(); y++) { | 160 | // *** Hedges 1 *** |
160 | std::wstring row; | 161 | { |
161 | for (int x=0; x<colorGrid.size(); x++) { | 162 | Puzzle p; |
162 | row += std::to_wstring(colorGrid[x][y]); | 163 | p.NewGrid(4, 4); |
164 | |||
165 | p.grid[2][1].gap = Cell::Gap::FULL; | ||
166 | p.grid[4][1].gap = Cell::Gap::FULL; | ||
167 | p.grid[6][1].gap = Cell::Gap::FULL; | ||
168 | p.grid[3][2].gap = Cell::Gap::FULL; | ||
169 | p.grid[5][2].gap = Cell::Gap::FULL; | ||
170 | p.grid[8][3].gap = Cell::Gap::FULL; | ||
171 | p.grid[2][5].gap = Cell::Gap::FULL; | ||
172 | p.grid[6][5].gap = Cell::Gap::FULL; | ||
173 | p.grid[7][6].gap = Cell::Gap::FULL; | ||
174 | p.grid[2][7].gap = Cell::Gap::FULL; | ||
175 | p.grid[4][7].gap = Cell::Gap::FULL; | ||
176 | |||
177 | p.grid[4][8].start = true; | ||
178 | p.grid[6][0].end = Cell::Dir::UP; | ||
179 | |||
180 | std::vector<Pos> cutEdges = Randomizer2Core::CutEdgesToBeUnique(p); | ||
181 | assert(cutEdges.size() == 5); | ||
182 | Puzzle copy = p; | ||
183 | std::vector<int> gates = {0x00344, 0x00488, 0x00489, 0x00495, 0x00496}; | ||
184 | for (int i=0; i<gates.size(); i++) { | ||
185 | Pos pos = cutEdges[i]; | ||
186 | copy.grid[pos.x][pos.y].gap = Cell::Gap::BREAK; | ||
187 | SetGate(gates[i], pos.x, pos.y); | ||
163 | } | 188 | } |
164 | row += L'\n'; | 189 | auto solutions = Solver::Solve(copy); |
165 | OutputDebugString(row.c_str()); | 190 | assert(solutions.size() == 1); |
191 | p.sequence = solutions[0].sequence; | ||
192 | PuzzleSerializer(_memory).WritePuzzle(solutions[0], 0x139); | ||
166 | } | 193 | } |
167 | OutputDebugString(L"\n"); | ||
168 | } | ||
169 | |||
170 | void FloodFill(const Puzzle& p, std::vector<std::vector<int>>& colorGrid, int color, int x, int y) { | ||
171 | if (!p.SafeCell(x, y)) return; | ||
172 | if (colorGrid[x][y] != 0) return; // Already processed. | ||
173 | colorGrid[x][y] = color; | ||
174 | 194 | ||
175 | FloodFill(p, colorGrid, color, x, y+1); | 195 | // *** Hedges 2 *** |
176 | FloodFill(p, colorGrid, color, x, y-1); | 196 | { |
177 | FloodFill(p, colorGrid, color, x+1, y); | 197 | Puzzle p; |
178 | FloodFill(p, colorGrid, color, x-1, y); | 198 | p.NewGrid(4, 4); |
179 | } | ||
180 | |||
181 | void FloodFillOutside(const Puzzle&p, std::vector<std::vector<int>>& colorGrid, int x, int y) { | ||
182 | if (!p.SafeCell(x, y)) return; | ||
183 | if (colorGrid[x][y] != 0) return; // Already processed. | ||
184 | if (x%2 != y%2 && p.grid[x][y].gap != Cell::Gap::FULL) return; // Only flood-fill through full gaps | ||
185 | colorGrid[x][y] = 1; // Outside color | ||
186 | |||
187 | FloodFillOutside(p, colorGrid, x, y+1); | ||
188 | FloodFillOutside(p, colorGrid, x, y-1); | ||
189 | FloodFillOutside(p, colorGrid, x+1, y); | ||
190 | FloodFillOutside(p, colorGrid, x-1, y); | ||
191 | } | ||
192 | 199 | ||
193 | /* | 200 | p.grid[2][1].gap = Cell::Gap::FULL; |
194 | undefined -> 1 (color of outside) or * (any colored cell) or -1 (edge/intersection not part of any region) | 201 | p.grid[1][2].gap = Cell::Gap::FULL; |
202 | p.grid[5][2].gap = Cell::Gap::FULL; | ||
203 | p.grid[7][4].gap = Cell::Gap::FULL; | ||
204 | p.grid[4][5].gap = Cell::Gap::FULL; | ||
205 | p.grid[6][5].gap = Cell::Gap::FULL; | ||
206 | p.grid[1][6].gap = Cell::Gap::FULL; | ||
207 | p.grid[2][7].gap = Cell::Gap::FULL; | ||
208 | p.grid[5][8].gap = Cell::Gap::FULL; | ||
195 | 209 | ||
196 | 0 -> {} (this is a special edge case, which I don't need right now) | 210 | p.grid[0][8].start = true; |
197 | 1 -> 0 (uncolored / ready to color) | 211 | p.grid[8][0].end = Cell::Dir::RIGHT; |
198 | 2 -> | ||
199 | */ | ||
200 | std::vector<std::vector<int>> CreateColorGrid(const Puzzle& p) { | ||
201 | std::vector<std::vector<int>> colorGrid; | ||
202 | colorGrid.resize(p.width); | ||
203 | 212 | ||
204 | for (int x=0; x<p.width; x++) { | 213 | std::vector<Pos> cutEdges = Randomizer2Core::CutEdgesToBeUnique(p); |
205 | colorGrid[x].resize(p.height); | 214 | assert(cutEdges.size() == 7); |
206 | for (int y=0; y<p.height; y++) { | 215 | for (Pos pos : cutEdges) { |
207 | // Mark all unbroken edges and intersections as 'do not color' | 216 | p.grid[pos.x][pos.y].gap = Cell::Gap::FULL; |
208 | if (x%2 != y%2) { | 217 | } |
209 | if (p.grid[x][y].gap == Cell::Gap::NONE) colorGrid[x][y] = 1; | 218 | auto solutions = Solver::Solve(p); |
210 | } else if (x%2 == 0 && y%2 == 0) { | 219 | assert(solutions.size() == 1); |
211 | // @Future: What about empty intersections? | 220 | |
212 | colorGrid[x][y] = 1; // do not color intersections | 221 | Puzzle q; |
213 | } | 222 | q.NewGrid(4, 4); |
223 | q.grid[0][8].start = true; | ||
224 | q.grid[8][0].end = Cell::Dir::RIGHT; | ||
225 | q.sequence = solutions[0].sequence; | ||
226 | for (Pos pos : cutEdges) { | ||
227 | q.grid[pos.x][pos.y].gap = Cell::Gap::FULL; | ||
214 | } | 228 | } |
229 | // Cut to 4 of 9 additional edges (total: 11) | ||
230 | Randomizer2Core::CutEdgesNotOutsideNotBreakingSequence(q, 4); | ||
231 | PuzzleSerializer(_memory).WritePuzzle(q, 0x19DC); | ||
215 | } | 232 | } |
233 | |||
234 | // *** Hedges 3 ** | ||
235 | { | ||
236 | std::vector<int> audioMarkers = { | ||
237 | 0x000034a9, | ||
238 | 0x000034b1, | ||
239 | 0x000034be, | ||
240 | 0x000034c4, | ||
241 | 0x000034cb, | ||
242 | 0x000034cc, | ||
243 | 0x000034cd, | ||
244 | 0x000034ce, | ||
245 | 0x000034df, | ||
246 | 0x000034e0, | ||
247 | 0x000034e1, | ||
248 | 0x000034e2, | ||
249 | 0x000034f3, | ||
250 | 0x000131cb, | ||
251 | 0x00017e34, | ||
252 | 0x00017e6f, | ||
253 | 0x00017e76, | ||
254 | 0x00017e77, | ||
255 | 0x00017e7a, | ||
256 | 0x00017e7e, | ||
257 | 0x00017e8b, | ||
258 | 0x00017e8d, | ||
259 | 0x00017eb5, | ||
260 | 0x000394a4, | ||
261 | 0x0003b54e, | ||
262 | }; | ||
263 | std::vector<int> good; | ||
264 | for (int marker : audioMarkers) { | ||
265 | // std::vector<char> assetName = _memory->ReadArray<char>(marker, 0xD8, 100); | ||
266 | std::vector<char> name = {'m', 'a', 'z', 'e', '_', 'p', 'e', 'b', 'b', 'l', 'e', '\0'}; | ||
267 | _memory->WriteNewArray(marker, 0xD8, name); | ||
268 | } | ||
216 | 269 | ||
217 | // @Future: Skip this loop if pillar = true; | 270 | Puzzle p; |
218 | for (int y=1; y<p.height; y+=2) { | 271 | p.NewGrid(4, 4); |
219 | FloodFillOutside(p, colorGrid, 0, y); | ||
220 | FloodFillOutside(p, colorGrid, p.width - 1, y); | ||
221 | } | ||
222 | 272 | ||
223 | for (int x=1; x<p.width; x+=2) { | 273 | p.grid[2][1].gap = Cell::Gap::FULL; |
224 | FloodFillOutside(p, colorGrid, x, 0); | 274 | p.grid[5][2].gap = Cell::Gap::FULL; |
225 | FloodFillOutside(p, colorGrid, x, p.height - 1); | 275 | p.grid[7][2].gap = Cell::Gap::FULL; |
226 | } | 276 | p.grid[4][3].gap = Cell::Gap::FULL; |
277 | p.grid[1][4].gap = Cell::Gap::FULL; | ||
278 | p.grid[6][5].gap = Cell::Gap::FULL; | ||
279 | p.grid[1][6].gap = Cell::Gap::FULL; | ||
280 | p.grid[3][6].gap = Cell::Gap::FULL; | ||
281 | p.grid[6][7].gap = Cell::Gap::FULL; | ||
227 | 282 | ||
228 | int color = 1; | 283 | p.grid[0][8].start = true; |
229 | for (int x=0; x<p.width; x++) { | 284 | p.grid[8][2].end = Cell::Dir::RIGHT; |
230 | for (int y=0; y<p.height; y++) { | 285 | |
231 | if (colorGrid[x][y] != 0) continue; // No dead colors | 286 | std::vector<Pos> cutEdges = Randomizer2Core::CutEdgesToBeUnique(p); |
232 | color++; | 287 | assert(cutEdges.size() == 7); |
233 | FloodFill(p, colorGrid, color, x, y); | 288 | for (Pos pos : cutEdges) { |
289 | p.grid[pos.x][pos.y].gap = Cell::Gap::BREAK; | ||
234 | } | 290 | } |
291 | PuzzleSerializer(_memory).WritePuzzle(p, 0x19E7); | ||
235 | } | 292 | } |
236 | 293 | ||
237 | return colorGrid; | 294 | // *** Hedges 4 *** |
238 | } | 295 | { |
296 | Puzzle p; | ||
297 | p.NewGrid(4, 4); | ||
239 | 298 | ||
240 | void Randomizer2::RandomizeKeep() { | 299 | p.grid[3][0].gap = Cell::Gap::FULL; |
241 | Puzzle p; | 300 | p.grid[4][1].gap = Cell::Gap::FULL; |
242 | p.NewGrid(4, 4); | 301 | p.grid[8][1].gap = Cell::Gap::FULL; |
243 | // p.width = 9; | 302 | p.grid[1][2].gap = Cell::Gap::FULL; |
244 | // p.height = 10; | 303 | p.grid[4][3].gap = Cell::Gap::FULL; |
245 | // p.grid.clear(); | 304 | p.grid[8][3].gap = Cell::Gap::FULL; |
246 | // p.grid.resize(p.width); | 305 | p.grid[1][4].gap = Cell::Gap::FULL; |
247 | // for (int x=0; x<p.width; x++) p.grid[x].resize(p.height); | 306 | p.grid[5][4].gap = Cell::Gap::FULL; |
248 | 307 | p.grid[2][5].gap = Cell::Gap::FULL; | |
249 | p.grid[2][1].gap = Cell::Gap::FULL; | 308 | p.grid[6][5].gap = Cell::Gap::FULL; |
250 | p.grid[4][1].gap = Cell::Gap::FULL; | 309 | p.grid[3][6].gap = Cell::Gap::FULL; |
251 | p.grid[6][1].gap = Cell::Gap::FULL; | 310 | p.grid[0][7].gap = Cell::Gap::FULL; |
252 | p.grid[3][2].gap = Cell::Gap::FULL; | 311 | p.grid[8][7].gap = Cell::Gap::FULL; |
253 | p.grid[5][2].gap = Cell::Gap::FULL; | 312 | p.grid[5][8].gap = Cell::Gap::FULL; |
254 | p.grid[8][3].gap = Cell::Gap::FULL; | ||
255 | p.grid[2][5].gap = Cell::Gap::FULL; | ||
256 | p.grid[6][5].gap = Cell::Gap::FULL; | ||
257 | p.grid[7][6].gap = Cell::Gap::FULL; | ||
258 | p.grid[2][7].gap = Cell::Gap::FULL; | ||
259 | p.grid[4][7].gap = Cell::Gap::FULL; | ||
260 | // p.grid[0][9].gap = Cell::Gap::FULL; | ||
261 | // p.grid[2][9].gap = Cell::Gap::FULL; | ||
262 | // p.grid[6][9].gap = Cell::Gap::FULL; | ||
263 | // p.grid[8][9].gap = Cell::Gap::FULL; | ||
264 | |||
265 | p.grid[6][0].end = Cell::Dir::UP; | ||
266 | p.grid[4][8].start = true; | ||
267 | |||
268 | auto colorGrid = CreateColorGrid(p); | ||
269 | |||
270 | std::vector<Pos> edges; | ||
271 | for (int x=0; x<p.width; x++) { | ||
272 | for (int y=0; y<p.height; y++) { | ||
273 | if (x%2 == y%2) continue; | ||
274 | if (p.grid[x][y].gap != Cell::Gap::NONE) continue; | ||
275 | edges.emplace_back(Pos{x, y}); | ||
276 | } | ||
277 | } | ||
278 | 313 | ||
279 | Puzzle copy = p; | 314 | p.grid[0][8].start = true; |
280 | std::vector<int> gates = {0x00344, 0x00488, 0x00489, 0x00495, 0x00496}; | 315 | p.grid[4][0].end = Cell::Dir::UP; |
281 | for (int i=0; i<5; i++) { | 316 | |
282 | for (int j=0; j<edges.size(); j++) { | 317 | std::vector<Pos> cutEdges = Randomizer2Core::CutEdgesToBeUnique(p); |
283 | int edge = Random::RandInt(0, static_cast<int>(edges.size() - 1)); | 318 | assert(cutEdges.size() == 2); |
284 | Pos pos = edges[edge]; | 319 | for (Pos pos : cutEdges) { |
285 | edges.erase(edges.begin() + edge); | 320 | p.grid[pos.x][pos.y].gap = Cell::Gap::FULL; |
286 | |||
287 | int color1 = 0; | ||
288 | int color2 = 0; | ||
289 | if (pos.x%2 == 0 && pos.y%2 == 1) { // Vertical | ||
290 | if (pos.x > 0) color1 = colorGrid[pos.x-1][pos.y]; | ||
291 | else color1 = 1; | ||
292 | |||
293 | if (pos.x < p.width - 1) color2 = colorGrid[pos.x+1][pos.y]; | ||
294 | else color2 = 1; | ||
295 | } else { // Horizontal | ||
296 | assert(pos.x%2 == 1 && pos.y%2 == 0); | ||
297 | if (pos.y > 0) color1 = colorGrid[pos.x][pos.y-1]; | ||
298 | else color1 = 1; | ||
299 | |||
300 | if (pos.y < p.height - 1) color2 = colorGrid[pos.x][pos.y+1]; | ||
301 | else color2 = 1; | ||
302 | } | ||
303 | // Enforce color1 < color2 | ||
304 | if (color1 > color2) std::swap(color1, color2); | ||
305 | |||
306 | // Colors mismatch, valid cut | ||
307 | if (color1 != color2) { | ||
308 | // @Performance... have a lookup table instead? | ||
309 | for (int x=0; x<p.width; x++) { | ||
310 | for (int y=0; y<p.height; y++) { | ||
311 | if (colorGrid[x][y] == color2) colorGrid[x][y] = color1; | ||
312 | } | ||
313 | } | ||
314 | copy.grid[pos.x][pos.y].gap = Cell::Gap::BREAK; | ||
315 | SetGate(gates[i], pos.x, pos.y); | ||
316 | break; | ||
317 | } | ||
318 | } | 321 | } |
322 | auto solutions = Solver::Solve(p); | ||
323 | assert(solutions.size() == 1); | ||
324 | |||
325 | Puzzle q; | ||
326 | q.NewGrid(4, 4); | ||
327 | q.grid[0][8].start = true; | ||
328 | q.grid[4][0].end = Cell::Dir::UP; | ||
329 | q.sequence = solutions[0].sequence; | ||
330 | for (Pos pos : cutEdges) { | ||
331 | q.grid[pos.x][pos.y].gap = Cell::Gap::FULL; | ||
332 | } | ||
333 | // 9 cuts, -2 from existing cuts | ||
334 | Randomizer2Core::CutEdgesNotOutsideNotBreakingSequence(q, 7); | ||
335 | PuzzleSerializer(_memory).WritePuzzle(q, 0x1A0F); | ||
319 | } | 336 | } |
320 | |||
321 | auto solutions = Solver::Solve(copy); | ||
322 | assert(solutions.size() == 1); | ||
323 | p.sequence = solutions[0].sequence; | ||
324 | PuzzleSerializer(_memory).WritePuzzle(solutions[0], 0x139); | ||
325 | } | 337 | } |
326 | 338 | ||
327 | void Randomizer2::SetGate(int panel, int X, int Y) { | 339 | void Randomizer2::SetGate(int panel, int X, int Y) { |
diff --git a/Source/Randomizer2Core.cpp b/Source/Randomizer2Core.cpp new file mode 100644 index 0000000..2659076 --- /dev/null +++ b/Source/Randomizer2Core.cpp | |||
@@ -0,0 +1,164 @@ | |||
1 | #include "Randomizer2Core.h" | ||
2 | #include "Puzzle.h" | ||
3 | #include "Random.h" | ||
4 | |||
5 | #include <string> | ||
6 | #include <iostream> | ||
7 | #include <cassert> | ||
8 | |||
9 | std::vector<Pos> Randomizer2Core::CutEdgesToBeUnique(const Puzzle& p) { | ||
10 | auto [colorGrid, numColors] = CreateColorGrid(p); | ||
11 | std::vector<Pos> edges; | ||
12 | for (int x=0; x<p.width; x++) { | ||
13 | for (int y=0; y<p.height; y++) { | ||
14 | if (x%2 == y%2) continue; | ||
15 | if (p.grid[x][y].gap != Cell::Gap::NONE) continue; | ||
16 | edges.emplace_back(Pos{x, y}); | ||
17 | } | ||
18 | } | ||
19 | return CutEdgesInternal(p, colorGrid, edges, numColors); | ||
20 | } | ||
21 | |||
22 | void Randomizer2Core::CutEdgesNotOutsideNotBreakingSequence(Puzzle& p, size_t numEdges) { | ||
23 | auto [colorGrid, numColors] = CreateColorGrid(p); | ||
24 | assert(numEdges <= numColors); | ||
25 | std::vector<Pos> edges; | ||
26 | for (int x=1; x<p.width-1; x++) { | ||
27 | for (int y=1; y<p.height-1; y++) { | ||
28 | if (x%2 == y%2) continue; | ||
29 | if (p.grid[x][y].gap != Cell::Gap::NONE) continue; | ||
30 | bool inSequence = false; | ||
31 | for (Pos pos : p.sequence) inSequence |= (pos.x == x && pos.y == y); | ||
32 | if (inSequence) continue; | ||
33 | edges.emplace_back(Pos{x, y}); | ||
34 | } | ||
35 | } | ||
36 | std::vector<Pos> cutEdges = CutEdgesInternal(p, colorGrid, edges, numEdges); | ||
37 | for (Pos pos : cutEdges) { | ||
38 | p.grid[pos.x][pos.y].gap = Cell::Gap::FULL; | ||
39 | } | ||
40 | } | ||
41 | |||
42 | std::vector<Pos> Randomizer2Core::CutEdgesInternal(const Puzzle& p, std::vector<std::vector<int>>& colorGrid, std::vector<Pos>& edges, size_t numEdges) { | ||
43 | std::vector<Pos> cutEdges; | ||
44 | for (int i=0; i<numEdges; i++) { | ||
45 | for (int j=0; j<edges.size(); j++) { | ||
46 | int edge = Random::RandInt(0, static_cast<int>(edges.size() - 1)); | ||
47 | Pos pos = edges[edge]; | ||
48 | edges.erase(edges.begin() + edge); | ||
49 | |||
50 | int color1 = 0; | ||
51 | int color2 = 0; | ||
52 | if (pos.x%2 == 0 && pos.y%2 == 1) { // Vertical | ||
53 | if (pos.x > 0) color1 = colorGrid[pos.x-1][pos.y]; | ||
54 | else color1 = 1; | ||
55 | |||
56 | if (pos.x < p.width - 1) color2 = colorGrid[pos.x+1][pos.y]; | ||
57 | else color2 = 1; | ||
58 | } else { // Horizontal | ||
59 | assert(pos.x%2 == 1 && pos.y%2 == 0); | ||
60 | if (pos.y > 0) color1 = colorGrid[pos.x][pos.y-1]; | ||
61 | else color1 = 1; | ||
62 | |||
63 | if (pos.y < p.height - 1) color2 = colorGrid[pos.x][pos.y+1]; | ||
64 | else color2 = 1; | ||
65 | } | ||
66 | // Enforce color1 < color2 | ||
67 | if (color1 > color2) std::swap(color1, color2); | ||
68 | |||
69 | // Colors mismatch, valid cut | ||
70 | if (color1 != color2) { | ||
71 | // @Performance... have a lookup table instead? | ||
72 | for (int x=0; x<p.width; x++) { | ||
73 | for (int y=0; y<p.height; y++) { | ||
74 | if (colorGrid[x][y] == color2) colorGrid[x][y] = color1; | ||
75 | } | ||
76 | } | ||
77 | cutEdges.emplace_back(pos); | ||
78 | break; | ||
79 | } | ||
80 | } | ||
81 | } | ||
82 | return cutEdges; | ||
83 | } | ||
84 | |||
85 | void Randomizer2Core::DebugColorGrid(const std::vector<std::vector<int>>& colorGrid) { | ||
86 | for (int y=0; y<colorGrid[0].size(); y++) { | ||
87 | std::string row; | ||
88 | for (int x=0; x<colorGrid.size(); x++) { | ||
89 | row += std::to_string(colorGrid[x][y]); | ||
90 | } | ||
91 | std::cerr << row << std::endl; | ||
92 | } | ||
93 | std::cerr << std::endl; | ||
94 | } | ||
95 | |||
96 | void Randomizer2Core::FloodFill(const Puzzle& p, std::vector<std::vector<int>>& colorGrid, int color, int x, int y) { | ||
97 | if (!p.SafeCell(x, y)) return; | ||
98 | if (colorGrid[x][y] != 0) return; // Already processed. | ||
99 | colorGrid[x][y] = color; | ||
100 | |||
101 | FloodFill(p, colorGrid, color, x, y+1); | ||
102 | FloodFill(p, colorGrid, color, x, y-1); | ||
103 | FloodFill(p, colorGrid, color, x+1, y); | ||
104 | FloodFill(p, colorGrid, color, x-1, y); | ||
105 | } | ||
106 | |||
107 | void Randomizer2Core::FloodFillOutside(const Puzzle& p, std::vector<std::vector<int>>& colorGrid, int x, int y) { | ||
108 | if (!p.SafeCell(x, y)) return; | ||
109 | if (colorGrid[x][y] != 0) return; // Already processed. | ||
110 | if (x%2 != y%2 && p.grid[x][y].gap != Cell::Gap::FULL) return; // Only flood-fill through full gaps | ||
111 | colorGrid[x][y] = 1; // Outside color | ||
112 | |||
113 | FloodFillOutside(p, colorGrid, x, y+1); | ||
114 | FloodFillOutside(p, colorGrid, x, y-1); | ||
115 | FloodFillOutside(p, colorGrid, x+1, y); | ||
116 | FloodFillOutside(p, colorGrid, x-1, y); | ||
117 | } | ||
118 | |||
119 | /* | ||
120 | undefined -> 1 (color of outside) or * (any colored cell) or -1 (edge/intersection not part of any region) | ||
121 | |||
122 | 0 -> {} (this is a special edge case, which I don't need right now) | ||
123 | 1 -> 0 (uncolored / ready to color) | ||
124 | 2 -> | ||
125 | */ | ||
126 | std::tuple<std::vector<std::vector<int>>, int> Randomizer2Core::CreateColorGrid(const Puzzle& p) { | ||
127 | std::vector<std::vector<int>> colorGrid; | ||
128 | colorGrid.resize(p.width); | ||
129 | |||
130 | for (int x=0; x<p.width; x++) { | ||
131 | colorGrid[x].resize(p.height); | ||
132 | for (int y=0; y<p.height; y++) { | ||
133 | // Mark all unbroken edges and intersections as 'do not color' | ||
134 | if (x%2 != y%2) { | ||
135 | if (p.grid[x][y].gap == Cell::Gap::NONE) colorGrid[x][y] = 1; | ||
136 | } else if (x%2 == 0 && y%2 == 0) { | ||
137 | // @Future: What about empty intersections? | ||
138 | colorGrid[x][y] = 1; // do not color intersections | ||
139 | } | ||
140 | } | ||
141 | } | ||
142 | |||
143 | // @Future: Skip this loop if pillar = true; | ||
144 | for (int y=1; y<p.height; y+=2) { | ||
145 | FloodFillOutside(p, colorGrid, 0, y); | ||
146 | FloodFillOutside(p, colorGrid, p.width - 1, y); | ||
147 | } | ||
148 | |||
149 | for (int x=1; x<p.width; x+=2) { | ||
150 | FloodFillOutside(p, colorGrid, x, 0); | ||
151 | FloodFillOutside(p, colorGrid, x, p.height - 1); | ||
152 | } | ||
153 | |||
154 | int color = 1; | ||
155 | for (int x=0; x<p.width; x++) { | ||
156 | for (int y=0; y<p.height; y++) { | ||
157 | if (colorGrid[x][y] != 0) continue; // No dead colors | ||
158 | color++; | ||
159 | FloodFill(p, colorGrid, color, x, y); | ||
160 | } | ||
161 | } | ||
162 | |||
163 | return {colorGrid, color}; | ||
164 | } \ No newline at end of file | ||
diff --git a/Source/Randomizer2Core.h b/Source/Randomizer2Core.h new file mode 100644 index 0000000..1b97fba --- /dev/null +++ b/Source/Randomizer2Core.h | |||
@@ -0,0 +1,21 @@ | |||
1 | #pragma once | ||
2 | #include <vector> | ||
3 | |||
4 | struct Pos; | ||
5 | class Puzzle; | ||
6 | |||
7 | class Randomizer2Core { | ||
8 | public: | ||
9 | // CAUTION: Does not actually cut edges, just returns a list of suggested cuts. | ||
10 | // Cuts a number of edges equal to the number of colors in the color grid. | ||
11 | static std::vector<Pos> CutEdgesToBeUnique(const Puzzle& p); | ||
12 | static void CutEdgesNotOutsideNotBreakingSequence(Puzzle& p, size_t numEdges); | ||
13 | |||
14 | private: | ||
15 | static std::vector<Pos> CutEdgesInternal(const Puzzle& p, std::vector<std::vector<int>>& colorGrid, std::vector<Pos>& edges, size_t numEdges); | ||
16 | static void DebugColorGrid(const std::vector<std::vector<int>>& colorGrid); | ||
17 | static void FloodFill(const Puzzle& p, std::vector<std::vector<int>>& colorGrid, int color, int x, int y); | ||
18 | static void FloodFillOutside(const Puzzle& p, std::vector<std::vector<int>>& colorGrid, int x, int y); | ||
19 | static std::tuple<std::vector<std::vector<int>>, int> CreateColorGrid(const Puzzle& p); | ||
20 | }; | ||
21 | |||
diff --git a/Source/Source.vcxproj b/Source/Source.vcxproj index 08e44a1..05f9ffa 100644 --- a/Source/Source.vcxproj +++ b/Source/Source.vcxproj | |||
@@ -165,6 +165,7 @@ | |||
165 | <ClInclude Include="Random.h" /> | 165 | <ClInclude Include="Random.h" /> |
166 | <ClInclude Include="Randomizer.h" /> | 166 | <ClInclude Include="Randomizer.h" /> |
167 | <ClInclude Include="Randomizer2.h" /> | 167 | <ClInclude Include="Randomizer2.h" /> |
168 | <ClInclude Include="Randomizer2Core.h" /> | ||
168 | <ClInclude Include="Solver.h" /> | 169 | <ClInclude Include="Solver.h" /> |
169 | <ClInclude Include="Validator.h" /> | 170 | <ClInclude Include="Validator.h" /> |
170 | </ItemGroup> | 171 | </ItemGroup> |
@@ -176,6 +177,7 @@ | |||
176 | <ClCompile Include="Random.cpp" /> | 177 | <ClCompile Include="Random.cpp" /> |
177 | <ClCompile Include="Randomizer.cpp" /> | 178 | <ClCompile Include="Randomizer.cpp" /> |
178 | <ClCompile Include="Randomizer2.cpp" /> | 179 | <ClCompile Include="Randomizer2.cpp" /> |
180 | <ClCompile Include="Randomizer2Core.cpp" /> | ||
179 | <ClCompile Include="Solver.cpp" /> | 181 | <ClCompile Include="Solver.cpp" /> |
180 | <ClCompile Include="Validator.cpp" /> | 182 | <ClCompile Include="Validator.cpp" /> |
181 | </ItemGroup> | 183 | </ItemGroup> |