diff options
Diffstat (limited to 'Source/Randomizer2Core.cpp')
-rw-r--r-- | Source/Randomizer2Core.cpp | 164 |
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 | |||
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 | ||