about summary refs log tree commit diff stats
path: root/Source/Randomizer2Core.cpp
diff options
context:
space:
mode:
authorjbzdarkid <jbzdarkid@gmail.com>2019-11-16 14:22:39 -0800
committerjbzdarkid <jbzdarkid@gmail.com>2019-11-16 14:22:39 -0800
commitfc8649b12fc1280d81e8dd4d35736ed69c0d9909 (patch)
tree7d6686c82dd6d738bdb54eb54d9989a4549cfdb5 /Source/Randomizer2Core.cpp
parent039b48fe49c31f6033a17aabab353b7b7696e11b (diff)
downloadwitness-tutorializer-fc8649b12fc1280d81e8dd4d35736ed69c0d9909.tar.gz
witness-tutorializer-fc8649b12fc1280d81e8dd4d35736ed69c0d9909.tar.bz2
witness-tutorializer-fc8649b12fc1280d81e8dd4d35736ed69c0d9909.zip
Keep WIP
Diffstat (limited to 'Source/Randomizer2Core.cpp')
-rw-r--r--Source/Randomizer2Core.cpp164
1 files changed, 164 insertions, 0 deletions
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
9std::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
22void 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
42std::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
85void 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
96void 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
107void 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*/
126std::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