diff options
author | Kelly Rauchenberger <fefferburbia@gmail.com> | 2018-07-13 17:06:48 -0400 |
---|---|---|
committer | Kelly Rauchenberger <fefferburbia@gmail.com> | 2018-07-13 17:06:48 -0400 |
commit | 4e8f554286593ec8aca6c61fa0fb9c4934bd640c (patch) | |
tree | 438b87e7003f2ca38b9973543bda8509ff2e9efa /util.cpp | |
parent | b64ada0dfec5895d14bd0d41cb83779d093970fe (diff) | |
download | mazeoflife-4e8f554286593ec8aca6c61fa0fb9c4934bd640c.tar.gz mazeoflife-4e8f554286593ec8aca6c61fa0fb9c4934bd640c.tar.bz2 mazeoflife-4e8f554286593ec8aca6c61fa0fb9c4934bd640c.zip |
Redesigned the solver algorithm
The new solver algorithm decreases the size of the search space by combining states. A flood fill is used to find all of the positions accessible by the player without changing the board state, and that flood is considered a node in the search graph, rather than there being a node for every position on every board state. Other optimizations are implemented too, like checking for changes locally instead of using tick, and using unordered_map/unordered_set because bitsets are hashable. Also changed wrap to use references, finally. refs #1
Diffstat (limited to 'util.cpp')
-rw-r--r-- | util.cpp | 18 |
1 files changed, 9 insertions, 9 deletions
diff --git a/util.cpp b/util.cpp index 5ccfe51..9fcdbbd 100644 --- a/util.cpp +++ b/util.cpp | |||
@@ -2,22 +2,22 @@ | |||
2 | #include "mazeoflife.h" | 2 | #include "mazeoflife.h" |
3 | #include <iostream> | 3 | #include <iostream> |
4 | 4 | ||
5 | void wrap(int* x, int* y) | 5 | void wrap(int& x, int& y) |
6 | { | 6 | { |
7 | if (*x < 0) | 7 | if (x < 0) |
8 | { | 8 | { |
9 | *x = WIDTH-(0-*x); | 9 | x = WIDTH+x; |
10 | } else if (*x >= WIDTH) | 10 | } else if (x >= WIDTH) |
11 | { | 11 | { |
12 | *x = *x-WIDTH; | 12 | x = x-WIDTH; |
13 | } | 13 | } |
14 | 14 | ||
15 | if (*y < 0) | 15 | if (y < 0) |
16 | { | 16 | { |
17 | *y = HEIGHT-(0-*y); | 17 | y = HEIGHT+y; |
18 | } else if (*y >= HEIGHT) | 18 | } else if (y >= HEIGHT) |
19 | { | 19 | { |
20 | *y = *y-HEIGHT; | 20 | y = y-HEIGHT; |
21 | } | 21 | } |
22 | } | 22 | } |
23 | 23 | ||