diff options
Diffstat (limited to 'Source')
-rw-r--r-- | Source/Memory.cpp | 3 | ||||
-rw-r--r-- | Source/Memory.h | 8 | ||||
-rw-r--r-- | Source/Randomizer2.cpp | 187 | ||||
-rw-r--r-- | Source/Randomizer2.h | 3 | ||||
-rw-r--r-- | Source/Solver.cpp | 2 | ||||
-rw-r--r-- | Source/Solver.h | 5 |
6 files changed, 164 insertions, 44 deletions
diff --git a/Source/Memory.cpp b/Source/Memory.cpp index c3b89d0..98b06f9 100644 --- a/Source/Memory.cpp +++ b/Source/Memory.cpp | |||
@@ -152,7 +152,8 @@ int Memory::ExecuteSigScans() | |||
152 | 152 | ||
153 | void Memory::ThrowError() { | 153 | void Memory::ThrowError() { |
154 | std::wstring message(256, '\0'); | 154 | std::wstring message(256, '\0'); |
155 | int length = FormatMessageW(FORMAT_MESSAGE_FROM_SYSTEM, nullptr, GetLastError(), 1024, &message[0], static_cast<DWORD>(message.size()), nullptr); | 155 | DWORD error = GetLastError(); |
156 | int length = FormatMessageW(FORMAT_MESSAGE_FROM_SYSTEM, nullptr, error, 1024, &message[0], static_cast<DWORD>(message.size()), nullptr); | ||
156 | message.resize(length); | 157 | message.resize(length); |
157 | #ifndef NDEBUG | 158 | #ifndef NDEBUG |
158 | MessageBox(NULL, message.c_str(), L"Please tell darkid about this", MB_OK); | 159 | MessageBox(NULL, message.c_str(), L"Please tell darkid about this", MB_OK); |
diff --git a/Source/Memory.h b/Source/Memory.h index 95de884..6b8403f 100644 --- a/Source/Memory.h +++ b/Source/Memory.h | |||
@@ -5,8 +5,8 @@ | |||
5 | #include <vector> | 5 | #include <vector> |
6 | #include <windows.h> | 6 | #include <windows.h> |
7 | 7 | ||
8 | // #define GLOBALS 0x5B28C0 | 8 | #define GLOBALS 0x5B28C0 |
9 | #define GLOBALS 0x62D0A0 | 9 | // #define GLOBALS 0x62D0A0 |
10 | 10 | ||
11 | #define HEARTBEAT 0x401 | 11 | #define HEARTBEAT 0x401 |
12 | enum class ProcStatus { | 12 | enum class ProcStatus { |
@@ -102,6 +102,8 @@ private: | |||
102 | }; | 102 | }; |
103 | 103 | ||
104 | #if GLOBALS == 0x5B28C0 | 104 | #if GLOBALS == 0x5B28C0 |
105 | #define POSITION 0x24 | ||
106 | #define ORIENTATION 0x34 | ||
105 | #define PATH_COLOR 0xC8 | 107 | #define PATH_COLOR 0xC8 |
106 | #define REFLECTION_PATH_COLOR 0xD8 | 108 | #define REFLECTION_PATH_COLOR 0xD8 |
107 | #define DOT_COLOR 0xF8 | 109 | #define DOT_COLOR 0xF8 |
@@ -169,6 +171,8 @@ private: | |||
169 | #define METADATA 0xF2 // sizeof(short) | 171 | #define METADATA 0xF2 // sizeof(short) |
170 | #define HOTEL_EP_NAME 0x4BC640 | 172 | #define HOTEL_EP_NAME 0x4BC640 |
171 | #elif GLOBALS == 0x62D0A0 | 173 | #elif GLOBALS == 0x62D0A0 |
174 | #define POSITION #error | ||
175 | #define ORIENTATION #error | ||
172 | #define PATH_COLOR 0xC0 | 176 | #define PATH_COLOR 0xC0 |
173 | #define REFLECTION_PATH_COLOR 0xD0 | 177 | #define REFLECTION_PATH_COLOR 0xD0 |
174 | #define DOT_COLOR 0xF0 | 178 | #define DOT_COLOR 0xF0 |
diff --git a/Source/Randomizer2.cpp b/Source/Randomizer2.cpp index fcfec9a..537c30b 100644 --- a/Source/Randomizer2.cpp +++ b/Source/Randomizer2.cpp | |||
@@ -2,6 +2,38 @@ | |||
2 | #include "Puzzle.h" | 2 | #include "Puzzle.h" |
3 | #include "Random.h" | 3 | #include "Random.h" |
4 | #include "Solver.h" | 4 | #include "Solver.h" |
5 | #include "Memory.h" | ||
6 | |||
7 | void FloodFillInternal(const Puzzle& p, std::vector<std::vector<bool>>& reached, int x, int y) { | ||
8 | if (x%2 == 1 && y%2 == 1) return; | ||
9 | auto cell = p.GetCell(x, y); | ||
10 | if (cell.undefined) return; | ||
11 | if (cell.gap != Cell::Gap::NONE) return; | ||
12 | if (reached[x][y]) return; | ||
13 | |||
14 | reached[x][y] = true; | ||
15 | FloodFillInternal(p, reached, x-1, y); | ||
16 | FloodFillInternal(p, reached, x+1, y); | ||
17 | FloodFillInternal(p, reached, x, y-1); | ||
18 | FloodFillInternal(p, reached, x, y+1); | ||
19 | } | ||
20 | |||
21 | // Returns true: All nodes reachable / false: Some node disconnected | ||
22 | bool FloodFill(const Puzzle& p) { | ||
23 | std::vector<std::vector<bool>> reached; | ||
24 | reached.resize(p.width); | ||
25 | for (int x=0; x<p.width; x++) reached[x].resize(p.height); | ||
26 | FloodFillInternal(p, reached, 0, 0); | ||
27 | |||
28 | for (int x=0; x<p.width; x++) { | ||
29 | for (int y=0; y<p.height; y++) { | ||
30 | if (x%2 == 0 && y%2 == 0) { // @Specialized | ||
31 | if (!reached[x][y]) return false; | ||
32 | } | ||
33 | } | ||
34 | } | ||
35 | return true; | ||
36 | } | ||
5 | 37 | ||
6 | Randomizer2::Randomizer2(const std::shared_ptr<Memory>& memory) : _memory(memory) {} | 38 | Randomizer2::Randomizer2(const std::shared_ptr<Memory>& memory) : _memory(memory) {} |
7 | 39 | ||
@@ -12,9 +44,7 @@ void Randomizer2::Randomize() { | |||
12 | // end (x=8, y=0) Up | 44 | // end (x=8, y=0) Up |
13 | // 1 solution | 45 | // 1 solution |
14 | Puzzle p; | 46 | Puzzle p; |
15 | int attemptCount = 0; | ||
16 | while (true) { | 47 | while (true) { |
17 | attemptCount++; | ||
18 | p.NewGrid(4, 4); | 48 | p.NewGrid(4, 4); |
19 | 49 | ||
20 | std::vector<Pos> corners; | 50 | std::vector<Pos> corners; |
@@ -29,40 +59,34 @@ void Randomizer2::Randomize() { | |||
29 | } | 59 | } |
30 | 60 | ||
31 | for (int i=0; i<14; i++) { | 61 | for (int i=0; i<14; i++) { |
32 | int edge = Random::RandInt(0, static_cast<int>(edges.size() - 1)); | 62 | for (int j=0; j<edges.size(); j++) { |
33 | Pos pos = edges[edge]; | 63 | int edge = Random::RandInt(0, static_cast<int>(edges.size() - 1)); |
34 | p.grid[pos.x][pos.y].gap = Cell::Gap::FULL; | 64 | Pos pos = edges[edge]; |
35 | edges.erase(edges.begin() + edge); | 65 | p.grid[pos.x][pos.y].gap = Cell::Gap::FULL; |
66 | edges.erase(edges.begin() + edge); | ||
67 | |||
68 | if (FloodFill(p)) { | ||
69 | break; | ||
70 | } else { | ||
71 | p.grid[pos.x][pos.y].gap = Cell::Gap::NONE; | ||
72 | } | ||
73 | } | ||
36 | } | 74 | } |
37 | 75 | ||
38 | p.grid[0][8].start = true; | 76 | p.grid[0][8].start = true; |
39 | p.grid[8][0].end = Cell::Dir::UP; | 77 | p.grid[8][0].end = Cell::Dir::UP; |
40 | 78 | ||
41 | auto solutions = Solver::Solve(p); | 79 | auto solutions = Solver::Solve(p); |
42 | if (solutions.size() == 1) { | 80 | if (solutions.size() > 0) break; |
43 | auto solution = solutions[0]; | ||
44 | int solutionLength = 0; | ||
45 | for (int x=0; x<solution.width; x++) { | ||
46 | for (int y=0; y<solution.height; y++) { | ||
47 | if (solution.grid[x][y].color == Cell::Color::BLACK) solutionLength++; | ||
48 | } | ||
49 | } | ||
50 | if (solutionLength == 25) break; | ||
51 | } | ||
52 | } | 81 | } |
53 | PuzzleSerializer(_memory).WritePuzzle(p, 0x293); | 82 | PuzzleSerializer(_memory).WritePuzzle(p, 0x293); |
54 | 83 | ||
55 | |||
56 | |||
57 | |||
58 | // 7x7 | 84 | // 7x7 |
59 | // 35 gaps | 85 | // 35 gaps |
60 | // start (x=8, y=8) | 86 | // start (x=8, y=8) |
61 | // end (x=4, y=0) Up | 87 | // end (x=4, y=0) Up |
62 | // 2 solutions, 37 & 39 | 88 | // 2 solutions, 37 & 39 |
63 | attemptCount = 0; | ||
64 | while (true) { | 89 | while (true) { |
65 | attemptCount++; | ||
66 | p.NewGrid(7, 7); | 90 | p.NewGrid(7, 7); |
67 | 91 | ||
68 | std::vector<Pos> corners; | 92 | std::vector<Pos> corners; |
@@ -77,28 +101,117 @@ void Randomizer2::Randomize() { | |||
77 | } | 101 | } |
78 | 102 | ||
79 | for (int i=0; i<35; i++) { | 103 | for (int i=0; i<35; i++) { |
80 | int edge = Random::RandInt(0, static_cast<int>(edges.size() - 1)); | 104 | for (int j=0; j<edges.size(); j++) { |
81 | Pos pos = edges[edge]; | 105 | // TODO: Precompute edge weights and make a weighted cut. |
82 | p.grid[pos.x][pos.y].gap = Cell::Gap::FULL; | 106 | // This will also preclude the need for flood filling. |
83 | edges.erase(edges.begin() + edge); | 107 | // https://en.wikipedia.org/wiki/Biconnected_component |
108 | |||
109 | int edge = Random::RandInt(0, static_cast<int>(edges.size() - 1)); | ||
110 | Pos pos = edges[edge]; | ||
111 | p.grid[pos.x][pos.y].gap = Cell::Gap::FULL; | ||
112 | edges.erase(edges.begin() + edge); | ||
113 | |||
114 | if (FloodFill(p)) { | ||
115 | break; | ||
116 | } else { | ||
117 | p.grid[pos.x][pos.y].gap = Cell::Gap::NONE; | ||
118 | } | ||
119 | } | ||
84 | } | 120 | } |
85 | 121 | ||
86 | p.grid[8][8].start = true; | 122 | switch (Random::RandInt(1, 4)) { |
87 | p.grid[4][0].end = Cell::Dir::UP; | 123 | case 1: |
124 | p.grid[Random::RandInt(0, p.width-1)][0].end = Cell::Dir::UP; | ||
125 | break; | ||
126 | case 2: | ||
127 | p.grid[Random::RandInt(0, p.width-1)][p.height-1].end = Cell::Dir::DOWN; | ||
128 | break; | ||
129 | case 3: | ||
130 | p.grid[0][Random::RandInt(0, p.height-1)].end = Cell::Dir::LEFT; | ||
131 | break; | ||
132 | case 4: | ||
133 | p.grid[p.width-1][Random::RandInt(0, p.height-1)].end = Cell::Dir::RIGHT; | ||
134 | break; | ||
135 | } | ||
136 | switch (Random::RandInt(1, 3)) { | ||
137 | case 1: // Horiz (6) [5/7][4/6/8] | ||
138 | p.grid[Random::RandInt(0, 1)*2 + 5][Random::RandInt(0, 2)*2 + 4].start = true; | ||
139 | break; | ||
140 | case 2: // Verti (6) [4/6/8][5/7] | ||
141 | p.grid[Random::RandInt(0, 2)*2 + 4][Random::RandInt(0, 1)*2 + 5].start = true; | ||
142 | break; | ||
143 | case 3: // Inter (9) [4/6/8][4/6/8] | ||
144 | p.grid[Random::RandInt(0, 2)*2 + 4][Random::RandInt(0, 2)*2 + 4].start = true; | ||
145 | break; | ||
146 | } | ||
88 | 147 | ||
89 | auto solutions = Solver::Solve(p); | 148 | auto solutions = Solver::Solve(p); |
90 | if (solutions.size() > 0) break; | 149 | if (solutions.size() > 0) break; |
91 | if (solutions.size() > 0 && solutions.size() < 5) { | ||
92 | auto solution = solutions[0]; | ||
93 | int solutionLength = 0; | ||
94 | for (int x=0; x<solution.width; x++) { | ||
95 | for (int y=0; y<solution.height; y++) { | ||
96 | if (solution.grid[x][y].color == Cell::Color::BLACK) solutionLength++; | ||
97 | } | ||
98 | } | ||
99 | if (solutionLength > 30 && solutionLength < 40) break; | ||
100 | } | ||
101 | } | 150 | } |
102 | PuzzleSerializer(_memory).WritePuzzle(p, 0x295); | 151 | PuzzleSerializer(_memory).WritePuzzle(p, 0x295); |
103 | 152 | ||
104 | } | 153 | } |
154 | |||
155 | void Randomizer2::RandomizeKeep() { | ||
156 | Puzzle p; | ||
157 | p.width = 9; | ||
158 | p.height = 10; | ||
159 | p.grid.clear(); | ||
160 | p.grid.resize(p.width); | ||
161 | for (int x=0; x<p.width; x++) p.grid[x].resize(p.height); | ||
162 | |||
163 | p.NewGrid(5, 5); | ||
164 | p.grid[2][1].gap = Cell::Gap::FULL; | ||
165 | p.grid[4][1].gap = Cell::Gap::FULL; | ||
166 | p.grid[6][1].gap = Cell::Gap::FULL; | ||
167 | p.grid[8][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 | p.grid[0][9].gap = Cell::Gap::FULL; | ||
177 | p.grid[2][9].gap = Cell::Gap::FULL; | ||
178 | p.grid[6][9].gap = Cell::Gap::FULL; | ||
179 | p.grid[8][9].gap = Cell::Gap::FULL; | ||
180 | |||
181 | p.grid[8][0].end = Cell::Dir::UP; | ||
182 | p.grid[4][9].start = true; | ||
183 | |||
184 | // 0x00496 | ||
185 | // 0x00344 | ||
186 | // 0x00495 | ||
187 | // 0x00488 | ||
188 | // 0x00489 | ||
189 | |||
190 | SetGate(0x00496, 2, 1); | ||
191 | } | ||
192 | |||
193 | void Randomizer2::SetGate(int panel, int X, int Y) { | ||
194 | // x: (-1.5)X + (0.7)Y + 67.1 | ||
195 | // y: (0.3)X + (1.5)Y + 106.9 | ||
196 | // z: -19.1 | ||
197 | // Horizontal: (0, 0, -.1, 1) | ||
198 | // Vertical: (0, 0, -.77, .63) | ||
199 | |||
200 | float x = -1.5f * X + 0.7f * Y + 67.1f; | ||
201 | float y = 0.3f * X + 1.5f * Y + 106.9f; | ||
202 | _memory->WritePanelData<float>(panel, POSITION, {x, y, 19.1f}); | ||
203 | |||
204 | float z, w; | ||
205 | if (X%2 == 0 && Y%2 == 1) { // Horizontal | ||
206 | z = -0.1f; | ||
207 | w = 1.0f; | ||
208 | } else if (X%2 == 1 && Y%2 == 0) { // Vertical | ||
209 | z = -.77f; | ||
210 | w = .63f; | ||
211 | } else { | ||
212 | assert(false); | ||
213 | return; | ||
214 | } | ||
215 | |||
216 | _memory->WritePanelData<float>(panel, ORIENTATION, {0.0f, 0.0f, z, w}); | ||
217 | } \ No newline at end of file | ||
diff --git a/Source/Randomizer2.h b/Source/Randomizer2.h index 1aeae11..848fd22 100644 --- a/Source/Randomizer2.h +++ b/Source/Randomizer2.h | |||
@@ -6,7 +6,10 @@ class Randomizer2 { | |||
6 | public: | 6 | public: |
7 | Randomizer2(const std::shared_ptr<Memory>& memory); | 7 | Randomizer2(const std::shared_ptr<Memory>& memory); |
8 | void Randomize(); | 8 | void Randomize(); |
9 | void RandomizeKeep(); | ||
9 | 10 | ||
10 | private: | 11 | private: |
12 | void SetGate(int panel, int X, int Y); | ||
13 | |||
11 | std::shared_ptr<Memory> _memory; | 14 | std::shared_ptr<Memory> _memory; |
12 | }; | 15 | }; |
diff --git a/Source/Solver.cpp b/Source/Solver.cpp index 244bfb2..bce1482 100644 --- a/Source/Solver.cpp +++ b/Source/Solver.cpp | |||
@@ -2,6 +2,8 @@ | |||
2 | #include "Puzzle.h" | 2 | #include "Puzzle.h" |
3 | #include "Validator.h" | 3 | #include "Validator.h" |
4 | 4 | ||
5 | int Solver::MAX_SOLUTIONS = 10000; | ||
6 | |||
5 | std::vector<Puzzle> Solver::Solve(Puzzle& p) { | 7 | std::vector<Puzzle> Solver::Solve(Puzzle& p) { |
6 | std::vector<Puzzle> solutions; | 8 | std::vector<Puzzle> solutions; |
7 | // var start = (new Date()).getTime() | 9 | // var start = (new Date()).getTime() |
diff --git a/Source/Solver.h b/Source/Solver.h index 09108c7..455d1eb 100644 --- a/Source/Solver.h +++ b/Source/Solver.h | |||
@@ -1,13 +1,10 @@ | |||
1 | #pragma once | 1 | #pragma once |
2 | #include <vector> | 2 | #include <vector> |
3 | 3 | ||
4 | #ifndef MAX_SOLUTIONS | ||
5 | #define MAX_SOLUTIONS 10000 | ||
6 | #endif | ||
7 | |||
8 | class Puzzle; | 4 | class Puzzle; |
9 | class Solver { | 5 | class Solver { |
10 | public: | 6 | public: |
7 | static int MAX_SOLUTIONS; | ||
11 | static std::vector<Puzzle> Solve(Puzzle& p); | 8 | static std::vector<Puzzle> Solve(Puzzle& p); |
12 | 9 | ||
13 | private: | 10 | private: |