From dde56d26837dc52e05207c0672b3c4a1046f6cb2 Mon Sep 17 00:00:00 2001 From: Star Rauchenberger Date: Fri, 27 Oct 2023 13:41:27 -0400 Subject: pulled out generation logic from sigma's rando --- .gitignore | 1 + LICENSE | 21 + README.md | 3 + ext/wittle_generator/.clang-format | 2 + ext/wittle_generator/CMakeLists.txt | 6 + ext/wittle_generator/Generate.cpp | 2056 ++++++++++++++++++++++++++++++++++ ext/wittle_generator/Generate.h | 248 ++++ ext/wittle_generator/Panel.cpp | 116 ++ ext/wittle_generator/Panel.h | 448 ++++++++ ext/wittle_generator/PuzzleSymbols.h | 59 + ext/wittle_generator/Random.cpp | 5 + ext/wittle_generator/Random.h | 16 + ext/wittle_generator/Test.cpp | 10 + lib/keep | 0 14 files changed, 2991 insertions(+) create mode 100644 .gitignore create mode 100644 LICENSE create mode 100644 README.md create mode 100644 ext/wittle_generator/.clang-format create mode 100644 ext/wittle_generator/CMakeLists.txt create mode 100644 ext/wittle_generator/Generate.cpp create mode 100644 ext/wittle_generator/Generate.h create mode 100644 ext/wittle_generator/Panel.cpp create mode 100644 ext/wittle_generator/Panel.h create mode 100644 ext/wittle_generator/PuzzleSymbols.h create mode 100644 ext/wittle_generator/Random.cpp create mode 100644 ext/wittle_generator/Random.h create mode 100644 ext/wittle_generator/Test.cpp create mode 100644 lib/keep diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..caaa972 --- /dev/null +++ b/.gitignore @@ -0,0 +1 @@ +ext/wittle_generator/build diff --git a/LICENSE b/LICENSE new file mode 100644 index 0000000..3e5ac40 --- /dev/null +++ b/LICENSE @@ -0,0 +1,21 @@ +MIT License + +Copyright (c) 2018 jbzdarkid, Sigma144, hatkirby + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. diff --git a/README.md b/README.md new file mode 100644 index 0000000..28d37c6 --- /dev/null +++ b/README.md @@ -0,0 +1,3 @@ +# wittle-generator + +Ruby gem that can generate Witness puzzles. Adapted from [Sigma144's Witness Random Puzzle Generator](https://github.com/sigma144/witness-randomizer), which is itself based on [darkid's Witness Randomizer](https://github.com/darkid/witness-randomizer). diff --git a/ext/wittle_generator/.clang-format b/ext/wittle_generator/.clang-format new file mode 100644 index 0000000..8de7fe6 --- /dev/null +++ b/ext/wittle_generator/.clang-format @@ -0,0 +1,2 @@ +--- + BasedOnStyle: Google diff --git a/ext/wittle_generator/CMakeLists.txt b/ext/wittle_generator/CMakeLists.txt new file mode 100644 index 0000000..236cc83 --- /dev/null +++ b/ext/wittle_generator/CMakeLists.txt @@ -0,0 +1,6 @@ +cmake_minimum_required (VERSION 3.1) +project (wittle_generator) + +add_executable(wittle_generator Generate.cpp Panel.cpp Random.cpp Test.cpp) +set_property(TARGET wittle_generator PROPERTY CXX_STANDARD 17) +set_property(TARGET wittle_generator PROPERTY CXX_STANDARD_REQUIRED ON) diff --git a/ext/wittle_generator/Generate.cpp b/ext/wittle_generator/Generate.cpp new file mode 100644 index 0000000..22c211f --- /dev/null +++ b/ext/wittle_generator/Generate.cpp @@ -0,0 +1,2056 @@ +#include "Generate.h" + +#include + +std::vector Generate::_DIRECTIONS1 = {Point(0, 1), Point(0, -1), + Point(1, 0), Point(-1, 0)}; +std::vector Generate::_8DIRECTIONS1 = { + Point(0, 1), Point(0, -1), Point(1, 0), Point(-1, 0), + Point(1, 1), Point(1, -1), Point(-1, -1), Point(-1, 1)}; +std::vector Generate::_DIRECTIONS2 = {Point(0, 2), Point(0, -2), + Point(2, 0), Point(-2, 0)}; +std::vector Generate::_8DIRECTIONS2 = { + Point(0, 2), Point(0, -2), Point(2, 0), Point(-2, 0), + Point(2, 2), Point(2, -2), Point(-2, -2), Point(-2, 2)}; +std::vector Generate::_DISCONNECT = { + Point(0, 2), Point(0, -2), Point(2, 0), + Point(-2, 0), Point(2, 2), Point(2, -2), + Point(-2, -2), Point(-2, 2), Point(0, 2), + Point(0, -2), Point(2, 0), Point(-2, 0), + Point(2, 2), Point(2, -2), Point(-2, -2), + Point(-2, 2), Point(0, 4), Point(0, -4), + Point(4, 0), Point(-4, 0), // Used to make the discontiguous shapes +}; +std::vector Generate::_SHAPEDIRECTIONS = + {}; // This will eventually be set to one of the above lists + +// Make a maze puzzle. The maze will have one solution. id - id of the puzzle +/*void Generate::generateMaze(int id) { + while (!generate_maze(id, 0, 0)) + ; +} + +// Make a maze puzzle. The maze will have one solution. id - id of the puzzle. +// numStarts - how many starts to add (only one will be valid). numExits - how +// many exits to add. All will work Setting numStarts or numExits to 0 will keep +// the starts/exits where they originally were, otherwise the starts/exits +// originally there will be removed and new ones randomly placed. +void Generate::generateMaze(int id, int numStarts, int numExits) { + while (!generate_maze(id, numStarts, numExits)) + ; +}*/ + +// Read in default panel data, such as dimensions, symmetry, starts/exits, etc. +// id - id of the puzzle +void Generate::initPanel() { + _panel = std::make_unique(); + _panel->Resize(_width, _height); + + // erase_path(); + + //_panelData.resize(_height); + // for (auto& row : _panelData) row.resize(_width); + + if (hasFlag(Config::TreehouseLayout)) { + init_treehouse_layout(); + } + + // Fill gridpos with every available grid block + _gridpos.clear(); + for (int x = 1; x < _panel->width(); x += 2) { + for (int y = 1; y < _panel->height(); y += 2) { + /*if (!(hasFlag(Config::PreserveStructure) && + (get(x, y) & Decoration::Empty) == Decoration::Empty))*/ + _gridpos.emplace(Point(x, y)); + } + } + // Init the open positions available for symbols. Defaults to every grid block + // unless a custom openpos has been specified + if (openPos.size() > 0) + _openpos = openPos; + else + _openpos = _gridpos; + for (Point p : blockPos) + _openpos.erase(p); // Remove the points which the user has defined to not + // place symbols on + for (Point p : _splitPoints) + _openpos.erase(p); // The split points will have erasers and cannot have + // any other symbols placed on them + _fullGaps = hasFlag(Config::FullGaps); + _panel->symmetry = + _symmetry; // Init user-defined puzzle symmetry if not "None". + // 0x00076 (Symmetry Island Fading Lines 7) and 0x01D3F (Keep Blue Pressure + // Plates) are exceptions because they need to have symmetry removed + if (pathWidth != 1) + _panel->pathWidth = pathWidth; // Init path scale. "1" is considered the + // default, and therefore means no change. +} + +// Place a specific symbol into the puzzle at the specified location. The +// generator will add other symbols, but will leave the set ones where they are. +// symbol - the symbol to place. //x, y - the coordinates to put it at. (0, 0) +// is at top left. Lines are at even coordinates and grid blocks at odd +// coordinates +void Generate::setSymbol(Decoration::Shape symbol, int x, int y) { + if (_custom_grid.size() < x + 1) { + _custom_grid.resize(x + 1, std::vector()); + for (auto& row : _custom_grid) { + row.resize(_custom_grid[0].size(), 0); + } + } + for (auto& row : _custom_grid) { + if (row.size() < y + 1) { + row.resize(y + 1, 0); + } + } + + if (symbol == Decoration::Start) + _starts.emplace(Point(x, y)); + else if (symbol == Decoration::Exit) + _exits.emplace(Point(x, y)); + else + _custom_grid[x][y] = symbol; // Starts and exits are not set into the grid +} + +// Set the dimensions of the puzzles. This setting will persist between puzzle +// generation calls. (0, 0) will have the generator use the same dimensions as +// the orignal puzzle. width, height - the dimensions to use, measured in grid +// blocks. +void Generate::setGridSize(int width, int height) { + if (width <= 0 || height <= 0) { + _width = 0; + _height = 0; + } else { + _width = width * 2 + 1; + _height = height * 2 + 1; + } +} + +// Set the type of symmetry to use. This setting will persist between puzzle +// generation calls. Using "None" will make the generator use the existing +// puzzle symmetry. +void Generate::setSymmetry(Panel::Symmetry symmetry) { + _symmetry = symmetry; + if (_symmetry == Panel::Symmetry::ParallelV || + _symmetry == Panel::Symmetry::ParallelVFlip) { + std::vector points; + for (int y = 0; y < _height; y += 2) + points.emplace_back(Point(_width / 2, y)); + setObstructions(points); // This prevents the generator from invalidly + // passing through the center line + } + if (_symmetry == Panel::Symmetry::ParallelH || + _symmetry == Panel::Symmetry::ParallelHFlip) { + std::vector points; + for (int x = 0; x < _width; x += 2) + points.emplace_back(Point(x, _height / 2)); + setObstructions(points); // This prevents the generator from invalidly + // passing through the center line + } +} + +// Write out panel data to the puzzle with the given id +void Generate::write(int id) { + std::vector> backupGrid; + /* if (hasFlag(Config::DisableReset)) + backupGrid = + _panel->_grid; // Allows panel data to be preserved after writing. + // Normally writing erases the panel data.*/ + + erase_path(); + + // TODO: write + + // Undo any one-time config changes + if (_oneTimeAdd) { + _config &= ~_oneTimeAdd; + _oneTimeAdd = 0; + } + if (_oneTimeRemove) { + _config |= _oneTimeRemove; + _oneTimeRemove = 0; + } + // Manually advance seed by 1 each generation to prevent seeds "funneling" + // from repeated fails + Random::seed(_seed); + _seed = Random::rand(); +} + +// Reset all config flags and persistent settings, including width/height and +// symmetry. +void Generate::resetConfig() { + setGridSize(0, 0); + _symmetry = Panel::Symmetry::None; + pathWidth = 1; + if (hasFlag(Config::DisableReset)) { + resetVars(); + } + _config = 0; + _oneTimeAdd = Config::None; + _oneTimeRemove = Config::None; + arrowColor = backgroundColor = successColor = {0, 0, 0, 0}; +} + +//----------------------Private-------------------------- + +// Add the point (pos) to the intended solution path, using symmetry if +// applicable. +void Generate::set_path(Point pos) { + set(pos, PATH); + _path.insert(pos); + if (_panel->symmetry) { + _path1.insert(pos); + Point sp = get_sym_point(pos); + set(sp, PATH); + _path.insert(sp); + _path2.insert(sp); + } +} + +// Remove the path and all symbols from the grid. This does not affect +// starts/exits. If PreserveStructure is active, open gaps will be kept. If a +// custom grid is set, this will reset it back to the custom grid state. +void Generate::clear() { + if (_custom_grid.size() > 0) { + for (int x = 0; x < _panel->width(); x++) { + for (int y = 0; y < _panel->height(); y++) { + set(x, y, _custom_grid[x][y]); + } + } + } else + for (int x = 0; x < _panel->width(); x++) { + for (int y = 0; y < _panel->height(); y++) { + /*if (hasFlag(Config::PreserveStructure) && + (_panel->_grid[x][y] == OPEN || + (_panel->_grid[x][y] & 0x60000f) == NO_POINT || + (_panel->_grid[x][y] & Decoration::Empty) == Decoration::Empty)) + continue;*/ + set(x, y, 0); + } + } + //_panel->_style &= ~0x2ff8; // Remove all element flags + _path.clear(); + _path1.clear(); + _path2.clear(); +} + +// Reset generator variables and lists used when generating puzzles. (not config +// settings) +void Generate::resetVars() { + _panel = NULL; // This is needed for the generator to read in the next panel + _starts.clear(); + _exits.clear(); + _custom_grid.clear(); + hitPoints.clear(); + _obstructions.clear(); + openPos.clear(); + blockPos.clear(); + _splitPoints.clear(); +} + +// Place start and exits in central positions like in the treehouse +void Generate::init_treehouse_layout() { + // bool pivot = _panel->_endpoints.size() > 2; + bool pivot = false; + setSymbol(Decoration::Start, _panel->width() / 2, _panel->height() - 1); + setSymbol(Decoration::Exit, _panel->width() / 2, 0); + if (pivot) { + setSymbol(Decoration::Exit, _panel->width() - 1, _panel->height() / 2); + setSymbol(Decoration::Exit, 0, _panel->height() / 2); + } +} +/* +// Private version of generateMaze. Should be called again if false is returned. +// The algorithm works by generating a correct path, then extending lines off of +// it until the maze is filled. +bool Generate::generate_maze(int id, int numStarts, int numExits) { + initPanel(id); + + if (numStarts > 0) place_start(numStarts); + if (numExits > 0) place_exit(numExits); + + // Prevent start and exit from overlapping, except in one one particular + // puzzle (0x00083). + if (id == 0x00083 && _width == 15 && _height == 15) { + clear(); + _panel->_endpoints.clear(); + _exits.clear(); + Point start = pick_random(_starts); + _panel->SetGridSymbol(start.first, start.second, Decoration::Exit, + Decoration::Color::None); + Point sp = get_sym_point(start); + _panel->SetGridSymbol(sp.first, sp.second, Decoration::Exit, + Decoration::Color::None); + set_path(start); + set_path(sp); + } else { + for (Point p : _starts) + if (_exits.count(p)) return false; + + clear(); + if (hasFlag(Generate::Config::ShortPath)) { + while (!generate_path_length( + (_panel->width() + _panel->height()), + min((_panel->width() + _panel->height()) * 2, + (_panel->width() / 2 + 1) * (_panel->height() / 2 + 1) * 1 / 2))) + clear(); + } + while (!generate_path_length( + (_panel->width() + _panel->height()), + min((_panel->width() + _panel->height()) * 2, + (_panel->width() / 2 + 1) * (_panel->height() / 2 + 1) * 4 / 5))) + clear(); + } + + std::set path = _path; // Backup + + // Extra false starts are tracked in a separate list so that the generator can + // make sure to extend each of them by a higher amount than usual. + std::set extraStarts; + for (Point pos : _starts) { + if (!_path.count(pos)) { + extraStarts.insert(pos); + } + set_path(pos); + } + // Check to see if the correct path runs over any of the false start points. + // If so, start over + if (extraStarts.size() != + (_panel->symmetry ? _starts.size() / 2 - 1 : _starts.size() - 1)) + return false; + + std::set check; + std::vector deadEndH, deadEndV; + for (Point p : _path) { + if (p.first % 2 == 0 && p.second % 2 == 0) + check.insert(p); // Only extend off of the points at grid intersections. + } + while (check.size() > 0) { + // Pick a random extendable point and extend it for some randomly chosen + // amount of units. + Point randomPos = (extraStarts.size() > 0 ? pick_random(extraStarts) + : pick_random(check)); + Point pos = randomPos; + for (int i = (extraStarts.size() > 0 ? 7 : 1); i >= 0; + i--) { // False starts are extended by up to 7 units. Other points are + // extended 1 unit at a time + std::vector validDir; + for (Point dir : _DIRECTIONS2) { + if (!off_edge(pos + dir) && get(pos + dir) == 0) { + validDir.push_back(dir); + } + } + if (validDir.size() < 2) + check.erase(pos); // If there are 0 or 1 open directions, the point + // cannot be extended again. + if (validDir.size() == 0) { + if (extraStarts.size() > 0) { + return false; // Not all the starts were extended successfully. + } + // If full gaps mode is enabled, detect dead ends, so that square tips + // can be put on them + if (_fullGaps && !_exits.count(pos) && !_starts.count(pos)) { + int countOpenRow = 0, countOpenColumn = 0; + for (Point dir2 : _DIRECTIONS1) { + Point added = pos + dir2; + if (!off_edge(added) && _drawnPath[added.second][added.first]) { + if (dir2.first == 0) + countOpenColumn++; + else + countOpenRow++; + } + } + if (countOpenRow + countOpenColumn == 1) { + if (countOpenRow) + deadEndH.push_back(pos); + else + deadEndV.push_back(pos); + } + } + break; // A dead end has been reached, extend a different point + } + Point dir = pick_random(validDir); + Point newPos = pos + dir; + set_path(newPos); + set_path(pos + dir / 2); + check.insert(newPos); + pos = newPos; + } + if (extraStarts.size() > 0) extraStarts.erase(randomPos); + } + // Put openings or gaps in any unused row or column segment + for (int y = 0; y < _panel->height(); y++) { + for (int x = (y + 1) % 2; x < _panel->width(); x += 2) { + if (!_drawnPath[y][x]) { + _panel->SetGridSymbol(x, y, + _fullGaps ? OPEN + : x % 2 == 0 ? Decoration::Gap_Column + : Decoration::Gap_Row); + if (_panel->symmetry) { + Point sp = get_sym_point(Point(x, y)); + if (sp.first == x && sp.second == y || + sp.first == x && x % 2 == 0 && abs(sp.second - y) <= 2 || + sp.second == y && y % 2 == 0 && abs(sp.first - x) <= 2 || + abs(sp.first - x) == 1) { + _drawnPath[y][x] = true; + } else if (Random::rand() % 2 == 0) { + _drawnPath[sp.second][sp.first] = true; + } else { + _drawnPath[y][x] = true; + _panel->SetGridSymbol(sp, _fullGaps ? OPEN + : x % 2 == 0 ? Decoration::Gap_Column + : Decoration::Gap_Row); + } + } + } + } + } + // Put square ends on any dead ends + for (Point p : deadEndH) { + _panel->SetGridSymbol(p, Decoration::Gap_Row); + } + for (Point p : deadEndV) { + _panel->SetGridSymbol(p, Decoration::Gap_Column); + } + _path = path; // Restore backup of the correct solution for testing purposes + std::vector solution; // For debugging only + for (int y = 0; y < _panel->height(); y++) { + std::string row; + for (int x = 0; x < _panel->width(); x++) { + if (_path.count(Point(x, y))) { + row += "xx"; + } else + row += " "; + } + solution.push_back(row); + } + if (!hasFlag(Config::DisableWrite)) write(id); + return true; +}*/ + +void Generate::generate(int width, int height, PuzzleSymbols symbols) { + while (!generateInternal(width, height, symbols)) + ; +} + +// The primary generation function. id - id of the puzzle. symbols - a structure +// representing the amount and types of each symbol to add to the puzzle The +// algorithm works by making a random path and then adding the chosen symbols to +// the grid in such a way that they will be satisfied by the path. if at some +// point the generator fails to add a symbol while still making the solution +// correct, the function returns false and must be called again. +bool Generate::generateInternal(int width, int height, PuzzleSymbols symbols) { + _width = width; + _height = height; + + initPanel(); + + // Multiple erasers are forced to be separate by default. This is because + // combining them causes unpredictable and inconsistent behavior. + if (symbols.getNum(Decoration::Eraser) > 1 && + !hasFlag(Config::CombineErasers)) { + setSymbol(Decoration::Gap_Row, 1, 0); + setSymbol(Decoration::Gap_Row, _panel->width() - 2, _panel->height() - 1); + _splitPoints = {Point(1, 1), + Point(_panel->width() - 2, _panel->height() - 2)}; + // initPanel(id); // Re-initing to account for the newly added information + } + + // Init parity for full dot puzzles + if (symbols.getNum(Decoration::Dot) >= _panel->get_num_grid_points() - 2) + _parity = + (_panel->get_parity() + + (!symbols.any(Decoration::Start) ? get_parity(pick_random(_starts)) + : !symbols.any(Decoration::Exit) ? get_parity(pick_random(_exits)) + : Random::rand() % 2)) % + 2; + else + _parity = -1; //-1 indicates a non-full dot puzzle + + if (symbols.any(Decoration::Start)) + place_start(symbols.getNum(Decoration::Start)); + if (symbols.any(Decoration::Exit)) + place_exit(symbols.getNum(Decoration::Exit)); + + // Make a random path unless a fixed one has been defined + if (customPath.size() == 0) { + int fails = 0; + while (!generate_path(symbols)) { + if (fails++ > 20) + return false; // It gets several chances to make a path so that the + // whole init process doesn't have to be repeated so many + // times + } + } else + _path = customPath; + + std::vector solution; // For debugging only + for (int y = 0; y < _panel->height(); y++) { + std::string row; + for (int x = 0; x < _panel->width(); x++) { + if (get(x, y) == PATH) { + row += "xx"; + } else + row += " "; + } + solution.push_back(row); + } + + // Attempt to add the symbols + if (!place_all_symbols(symbols)) return false; + + for (const auto& row : solution) { + std::cout << row << std::endl; + } + + return true; +} + +// Place the provided symbols onto the puzzle. symbols - a structure describing +// types and amounts of symbols to add. +bool Generate::place_all_symbols(PuzzleSymbols& symbols) { + std::vector eraseSymbols; + std::vector eraserColors; + // If erasers are present, choose symbols to be erased and remove them + // pre-emptively + for (std::pair s : symbols[Decoration::Eraser]) { + for (int i = 0; i < s.second; i++) { + eraserColors.push_back(s.first & 0xf); + eraseSymbols.push_back(hasFlag(Config::FalseParity) + ? Decoration::Dot_Intersection + : symbols.popRandomSymbol()); + } + } + + // Symbols are placed in stages according to their type + // In each of these loops, s.first is the symbol and s.second is the amount of + // it to add + + _SHAPEDIRECTIONS = + (hasFlag(Config::DisconnectShapes) ? _DISCONNECT : _DIRECTIONS2); + int numShapes = 0, numRotate = 0, numNegative = 0; + std::vector colors, negativeColors; + for (std::pair s : symbols[Decoration::Poly]) { + for (int i = 0; i < s.second; i++) { + if (s.first & Decoration::Can_Rotate) numRotate++; + if (s.first & Decoration::Negative) { + numNegative++; + negativeColors.push_back(s.first & 0xf); + } else { + numShapes++; + colors.push_back(s.first & 0xf); + } + } + } + if (numShapes > 0 && !place_shapes(colors, negativeColors, numShapes, + numRotate, numNegative) || + numShapes == 0 && numNegative > 0) + return false; + + _stoneTypes = static_cast(symbols[Decoration::Stone].size()); + _bisect = true; // This flag helps the generator prevent making two adjacent + // regions of stones the same color + for (std::pair s : symbols[Decoration::Stone]) + if (!place_stones(s.first & 0xf, s.second)) return false; + for (std::pair s : symbols[Decoration::Triangle]) + if (!place_triangles(s.first & 0xf, s.second, s.first >> 16)) return false; + for (std::pair s : symbols[Decoration::Arrow]) + if (!place_arrows(s.first & 0xf, s.second, s.first >> 12)) return false; + for (std::pair s : symbols[Decoration::Star]) + if (!place_stars(s.first & 0xf, s.second)) return false; + if (symbols.style == Panel::Style::HAS_STARS && + hasFlag(Generate::Config::TreehouseLayout) && !checkStarZigzag()) + return false; + if (eraserColors.size() > 0 && !place_erasers(eraserColors, eraseSymbols)) + return false; + for (std::pair s : symbols[Decoration::Dot]) + if (!place_dots(s.second, static_cast(s.first & 0xf), + (s.first & ~0xf) == Decoration::Dot_Intersection)) + return false; + for (std::pair s : symbols[Decoration::Gap]) + if (!place_gaps(s.second)) return false; + return true; +} + +// Generate a random path for a puzzle with the provided symbols. +// The path starts at a random start and will not cross through walls or +// symbols. Puzzle symbols are provided because they can influence how long the +// path should be. +bool Generate::generate_path(PuzzleSymbols& symbols) { + clear(); + + if (_obstructions.size() > 0) { + std::vector walls = pick_random(_obstructions); + for (Point p : walls) + if (get(p) == 0) + set(p, p.first % 2 == 0 ? Decoration::Gap_Column : Decoration::Gap_Row); + bool result = + (hasFlag(Config::ShortPath) ? generate_path_length(1) + : _parity != -1 ? generate_longest_path() + : hitPoints.size() > 0 + ? generate_special_path() + : generate_path_length(_panel->get_num_grid_points() * 3 / 4)); + for (Point p : walls) + if (get(p) & Decoration::Gap) set(p, 0); + return result; + } + + if (hitPoints.size() > 0) { + return generate_special_path(); + } + + if (_parity != -1 || hasFlag(Generate::LongestPath)) { + return generate_longest_path(); + } + + if (hasFlag(Config::ShortPath)) return generate_path_length(1); + + // The diagonal symmetry puzzles have a lot of points that can't be hit, so I + // have to reduce the path length + if (_panel->symmetry == Panel::Symmetry::FlipXY || + _panel->symmetry == Panel::Symmetry::FlipNegXY) { + return generate_path_length(_panel->get_num_grid_points() * 3 / 4 - + _panel->width() / 2); + } + + // Dot puzzles have a longer path by default. Vertical/horizontal symmetry + // puzzles are also longer because they tend to be too simple otherwise + if (hasFlag(Config::LongPath) || + symbols.style == Panel::Style::HAS_DOTS && + !hasFlag(Config::PreserveStructure) && + !(_panel->symmetry == Panel::Symmetry::Vertical && + (_panel->width() / 2) % 2 == 0 || + _panel->symmetry == Panel::Symmetry::Horizontal && + (_panel->height() / 2) % 2 == 0)) { + return generate_path_length(_panel->get_num_grid_points() * 7 / 8); + } + + // For stone puzzles, the path must have a certain number of regions + if (symbols.style == Panel::Style::HAS_STONES && _splitPoints.size() == 0) + return generate_path_regions( + std::min(symbols.getNum(Decoration::Stone), + (_panel->width() / 2 + _panel->height() / 2) / 2 + 1)); + + if (symbols.style == Panel::Style::HAS_SHAPERS) { + if (hasFlag(Config::SplitShapes)) { + return generate_path_regions(symbols.getNum(Decoration::Poly) + 1); + } + return generate_path_length(_panel->get_num_grid_points() / 2); + } + + return generate_path_length(_panel->get_num_grid_points() * 3 / 4); +} + +// Generate a random path with the provided minimum length. +bool Generate::generate_path_length(int minLength, int maxLength) { + int fails = 0; + Point pos = adjust_point(pick_random(_starts)); + Point exit = adjust_point(pick_random(_exits)); + if (off_edge(pos) || off_edge(exit)) return false; + set_path(pos); + while (pos != exit) { + if (fails++ > 20) return false; + Point dir = pick_random(_DIRECTIONS2); + Point newPos = pos + dir; + Point directed = pos + dir / 2; + if (off_edge(newPos) || hasSymbolOrPath(newPos) || + hasSymbolOrPath(directed) || + newPos == exit && _path.size() / 2 + 2 < minLength) + continue; + if (_panel->symmetry && + (off_edge(get_sym_point(newPos)) || newPos == get_sym_point(newPos))) + continue; + set_path(newPos); + set_path(pos + dir / 2); + pos = newPos; + fails = 0; + } + return _path.size() / 2 + 1 >= minLength && _path.size() / 2 + 1 <= maxLength; +} + +// Generate a path with the provided number of regions. +bool Generate::generate_path_regions(int minRegions) { + int fails = 0; + int regions = 1; + Point pos = adjust_point(pick_random(_starts)); + Point exit = adjust_point(pick_random(_exits)); + if (off_edge(pos) || off_edge(exit)) return false; + set_path(pos); + while (pos != exit) { + if (fails++ > 20) return false; + Point dir = pick_random(_DIRECTIONS2); + Point newPos = pos + dir; + Point directed = pos + dir / 2; + if (off_edge(newPos) || hasSymbolOrPath(newPos) || + hasSymbolOrPath(directed) || newPos == exit && regions < minRegions) + continue; + if (_panel->symmetry && + (off_edge(get_sym_point(newPos)) || newPos == get_sym_point(newPos))) + continue; + set_path(newPos); + set_path(pos + dir / 2); + if (!on_edge(newPos) && on_edge(pos)) { + regions++; + if (_panel->symmetry) regions++; + } + pos = newPos; + fails = 0; + } + return regions >= minRegions; +} + +// Generate a path that covers the maximum number of points. +bool Generate::generate_longest_path() { + Point pos = adjust_point(pick_random(_starts)); + Point exit = adjust_point(pick_random(_exits)); + if (off_edge(pos) || off_edge(exit)) return false; + Point block(-10, -10); + if (hasFlag(Config::FalseParity)) { // If false parity, one dot must be left + // uncovered + if (get_parity(pos + exit) == _panel->get_parity()) return false; + block = Point(Random::rand() % (_panel->width() / 2 + 1) * 2, + Random::rand() % (_panel->height() / 2 + 1) * 2); + while (pos == block || exit == block) { + block = Point(Random::rand() % (_panel->width() / 2 + 1) * 2, + Random::rand() % (_panel->height() / 2 + 1) * 2); + } + set_path(block); + } else if (get_parity(pos + exit) != _panel->get_parity()) + return false; + int fails = 0; + int reqLength = + _panel->get_num_grid_points() + static_cast(_path.size()) / 2; + bool centerFlag = !on_edge(pos); + set_path(pos); + while (pos != exit && !(_panel->symmetry && get_sym_point(pos) == exit)) { + std::vector solution; // For debugging only + for (int y = 0; y < _panel->height(); y++) { + std::string row; + for (int x = 0; x < _panel->width(); x++) { + if (get(x, y) == PATH) { + row += "xx"; + } else + row += " "; + } + solution.push_back(row); + } + if (fails++ > 20) return false; + Point dir = pick_random(_DIRECTIONS2); + for (Point checkDir : _DIRECTIONS2) { + Point check = pos + checkDir; + if (off_edge(check) || hasSymbolOrPath(check)) continue; + if (check == exit) continue; + int open = 0; + for (Point checkDir2 : _DIRECTIONS2) { + Point added = check + checkDir2; + if (!off_edge(added) && !hasSymbolOrPath(added)) { + if (++open >= 2) break; + } + } + if (open < 2) { + dir = checkDir; + break; + } + } + Point newPos = pos + dir; + Point directed = pos + dir / 2; + // Various checks to see if going this direction will lead to any issues + if (off_edge(newPos) || hasSymbolOrPath(newPos) || + hasSymbolOrPath(directed) || + newPos == exit && _path.size() / 2 + 3 < reqLength || + _panel->symmetry && get_sym_point(newPos) == exit && + _path.size() / 2 + 3 < reqLength) + continue; + if (_panel->symmetry && + (off_edge(get_sym_point(newPos)) || newPos == get_sym_point(newPos))) + continue; + Point added = newPos + dir; + if (on_edge(newPos) && _panel->symmetry != Panel::Symmetry::Horizontal && + added != block && (off_edge(added) || hasSymbolOrPath(added))) { + if (centerFlag && off_edge(added)) { + centerFlag = false; + } else { + int open = 0; + for (Point checkDir : _DIRECTIONS2) { + Point extorted = newPos + checkDir; + if (!off_edge(extorted) && !hasSymbolOrPath(extorted)) { + if (++open >= 2) break; + } + } + if (open >= 2) continue; + } + } + set_path(newPos); + set_path(pos + dir / 2); + pos = newPos; + fails = 0; + } + if (!off_edge(block)) // Uncover the one dot for false parity + set(block, 0); + return _path.size() / 2 + 1 == reqLength; +} + +// Generate path that passes through all of the hitPoints in order +bool Generate::generate_special_path() { + Point pos = adjust_point(pick_random(_starts)); + Point exit = adjust_point(pick_random(_exits)); + if (off_edge(pos) || off_edge(exit)) return false; + set_path(pos); + for (Point p : hitPoints) { + set(p, PATH); + } + int hitIndex = 0; + int minLength = _panel->get_num_grid_points() * 3 / 4; + while (pos != exit) { + std::vector validDir; + for (Point dir : _DIRECTIONS2) { + Point newPos = pos + dir; + if (off_edge(newPos)) continue; + Point connectPos = pos + dir / 2; + // Go through the hit point if passing next to it + if (get(connectPos) == PATH && hitIndex < hitPoints.size() && + connectPos == hitPoints[hitIndex]) { + validDir = {dir}; + hitIndex++; + break; + } + if (hasSymbolOrPath(newPos) || hasSymbolOrPath(connectPos) || + newPos == exit && (hitIndex != hitPoints.size() || + _path.size() / 2 + 2 < minLength)) + continue; + if (_panel->symmetry && newPos == get_sym_point(newPos)) continue; + bool fail = false; + for (Point dir : _DIRECTIONS1) { + Point added = newPos + dir; + if (!off_edge(added) && get(added) == PATH && + newPos + dir != hitPoints[hitIndex]) { + fail = true; + break; + } + } + if (fail) continue; + validDir.push_back(dir); + } + if (validDir.size() == 0) return false; + Point dir = pick_random(validDir); + set_path(pos + dir); + set_path(pos + dir / 2); + pos = pos + dir; + } + return hitIndex == hitPoints.size() && _path.size() >= minLength; +} + +// Eerase the path from the puzzle grid +void Generate::erase_path() { + /*_drawnPath.clear(); + _drawnPath.resize(_height); + for (auto& row : _drawnPath) row.resize(_width);*/ + for (int x = 0; x < _panel->width(); x++) { + for (int y = 0; y < _panel->height(); y++) { + if (get(x, y) == PATH) set(x, y, 0); + } + } +} + +// If a point is on an edge, bump it randomly to an adjacent vertex. Otherwise, +// the point is untouched +Point Generate::adjust_point(Point pos) { + if (pos.first % 2 != 0) { + if (hasSymbolOrPath(pos)) return {-10, -10}; + set_path(pos); + return Point(pos.first - 1 + Random::rand() % 2 * 2, pos.second); + } + if (pos.second % 2 != 0) { + if (hasSymbolOrPath(pos)) return {-10, -10}; + set_path(pos); + return Point(pos.first, pos.second - 1 + Random::rand() % 2 * 2); + } + if (_panel->symmetry && _exits.count(pos) && + !_exits.count(get_sym_point(pos))) + return {-10, -10}; + return pos; +} + +// Get the set of points in region containing the point (pos) +std::set Generate::get_region(Point pos) { + std::set region; + std::vector check; + check.push_back(pos); + region.insert(pos); + while (check.size() > 0) { + Point p = check[check.size() - 1]; + check.pop_back(); + for (Point dir : _DIRECTIONS1) { + Point p1 = p + dir; + if (on_edge(p1)) continue; + if (get(p1) == PATH || get(p1) == OPEN) continue; + Point p2 = p + dir * 2; + if ((get(p2) & Decoration::Empty) == Decoration::Empty) continue; + if (region.insert(p2).second) { + check.push_back(p2); + } + } + } + return region; +} + +// Get all the symbols in the region containing including the point (pos) +std::vector Generate::get_symbols_in_region(Point pos) { + return get_symbols_in_region(get_region(pos)); +} + +// Get all the symbols in the given region +std::vector Generate::get_symbols_in_region( + const std::set& region) { + std::vector symbols; + for (Point p : region) { + if (get(p)) symbols.push_back(get(p)); + } + return symbols; +} + +// Place a start point in a random location +bool Generate::place_start(int amount) { + _starts.clear(); + //_panel->_startpoints.clear(); + while (amount > 0) { + Point pos = Point(Random::rand() % (_panel->width() / 2 + 1) * 2, + Random::rand() % (_panel->height() / 2 + 1) * 2); + if (hasFlag(Config::StartEdgeOnly)) switch (Random::rand() % 4) { + case 0: + pos.first = 0; + break; + case 1: + pos.second = 0; + break; + case 2: + pos.first = _panel->width() - 1; + break; + case 3: + pos.second = _panel->height() - 1; + break; + } + if (_parity != -1 && get_parity(pos) != (amount == 1 ? _parity : !_parity)) + continue; + if (_starts.count(pos) || _exits.count(pos)) continue; + if (_panel->symmetry && pos == get_sym_point(pos)) continue; + // Highly discourage putting start points adjacent + bool adjacent = false; + for (Point dir : _DIRECTIONS2) { + if (!off_edge(pos + dir) && get(pos + dir) == Decoration::Start) { + adjacent = true; + break; + } + } + if (adjacent && Random::rand() % 10 > 0) continue; + _starts.insert(pos); + set(pos.first, pos.second, Decoration::Start | Decoration::Color::None); + amount--; + if (_panel->symmetry) { + Point sp = get_sym_point(pos); + _starts.insert(sp); + set(sp.first, sp.second, Decoration::Start | Decoration::Color::None); + } + } + return true; +} + +// Place an exit point in a random location on the edge of the grid +bool Generate::place_exit(int amount) { + _exits.clear(); + //_panel->_endpoints.clear(); + while (amount > 0) { + Point pos = Point(Random::rand() % (_panel->width() / 2 + 1) * 2, + Random::rand() % (_panel->height() / 2 + 1) * 2); + switch (Random::rand() % 4) { + case 0: + pos.first = 0; + break; + case 1: + pos.second = 0; + break; + case 2: + pos.first = _panel->width() - 1; + break; + case 3: + pos.second = _panel->height() - 1; + break; + } + if (_parity != -1 && (get_parity(pos) + _panel->get_parity()) % 2 != + (amount == 1 ? _parity : !_parity)) + continue; + if (_starts.count(pos) || _exits.count(pos)) continue; + if (_panel->symmetry && pos == get_sym_point(pos)) continue; + if (_panel->symmetry && get_sym_point(pos).first != 0 && + get_sym_point(pos).second != 0) + continue; + // Prevent putting exit points adjacent + bool adjacent = false; + for (Point dir : _8DIRECTIONS2) { + if (!off_edge(pos + dir) && get(pos + dir) == Decoration::Exit) { + adjacent = true; + break; + } + } + if (adjacent) continue; + _exits.insert(pos); + set(pos.first, pos.second, Decoration::Exit | Decoration::Color::None); + amount--; + if (_panel->symmetry) { + Point sp = get_sym_point(pos); + _exits.insert(sp); + set(sp.first, sp.second, Decoration::Exit | Decoration::Color::None); + } + } + return true; +} + +// Check if a gap can be placed at pos. +bool Generate::can_place_gap(Point pos) { + // Prevent putting open gaps at edges of the puzzle + if (pos.first == 0 || pos.second == 0) { + if (hasFlag(Config::FullGaps)) return false; + } else if (Random::rand() % 2 == 0) + return false; // Encourages gaps on outside border + // Prevent putting a gap on top of a start/end point + if (_starts.count(pos) || _exits.count(pos)) return false; + // For symmetry puzzles, prevent putting two gaps symmetrically opposite + if (_panel->symmetry && (get_sym_point(pos) == pos) || + (get(get_sym_point(pos)) & Decoration::Gap)) + return false; + if ((_panel->symmetry == Panel::Symmetry::ParallelH || + _panel->symmetry == Panel::Symmetry::ParallelHFlip) && + pos.second == _panel->height() / 2) + return false; + if ((_panel->symmetry == Panel::Symmetry::ParallelV || + _panel->symmetry == Panel::Symmetry::ParallelVFlip) && + pos.first == _panel->width() / 2) + return false; + if (_panel->symmetry == Panel::Symmetry::FlipNegXY && + (pos.first + pos.second == _width - 1 || + pos.first + pos.second == _width + 1)) + return false; + if (_panel->symmetry == Panel::Symmetry::FlipXY && + (pos.first - pos.second == 1 || pos.first - pos.second == -1)) + return false; + if (hasFlag(Config::FullGaps)) { // Prevent forming dead ends with open gaps + std::vector checkPoints = + (pos.first % 2 == 0 + ? std::vector({Point(pos.first, pos.second - 1), + Point(pos.first, pos.second + 1)}) + : std::vector({Point(pos.first - 1, pos.second), + Point(pos.first + 1, pos.second)})); + for (Point check : checkPoints) { + int valid = 4; + for (Point dir : _DIRECTIONS1) { + Point p = check + dir; + if (off_edge(p) || get(p) & GAP || get(p) == OPEN) { + if (--valid <= 2) { + return false; + } + } + } + } + } + return true; +} + +// Place the given amount of gaps radomly around the puzzle +bool Generate::place_gaps(int amount) { + std::set open; + for (int y = 0; y < _panel->height(); y++) { + for (int x = (y + 1) % 2; x < _panel->width(); x += 2) { + if (get(x, y) == 0 && (!_fullGaps || !on_edge(Point(x, y)))) { + open.emplace(Point(x, y)); + } + } + } + + while (amount > 0) { + if (open.size() == 0) return false; + Point pos = pick_random(open); + if (can_place_gap(pos)) { + set(pos, _fullGaps ? static_cast(OPEN) + : pos.first % 2 == 0 ? Decoration::Gap_Column + : Decoration::Gap_Row); + amount--; + } + open.erase(pos); + } + return true; +} + +// Check if a dot can be placed at pos. +bool Generate::can_place_dot(Point pos, bool intersectionOnly) { + if (get(pos) & DOT) return false; + if (_panel->symmetry) { + // For symmetry puzzles, make sure the current pos and symmetric pos are + // both valid + Point symPos = get_sym_point(pos); + if (symPos == pos) return false; + Panel::Symmetry backupSym = _panel->symmetry; + _panel->symmetry = Panel::Symmetry::None; // To prevent endless recursion + // if (!can_place_dot(get_sym_point(pos))) { + if (!can_place_dot(symPos, intersectionOnly)) { + _panel->symmetry = backupSym; + return false; + } + _panel->symmetry = backupSym; + } + if (_panel->symmetry == Panel::Symmetry::RotateLeft && _path1.count(pos) && + _path2.count(pos)) + return false; // Prevent sharing of dots between symmetry lines + if (hasFlag(Config::DisableDotIntersection)) return true; + for (Point dir : _8DIRECTIONS1) { + Point p = pos + dir; + if (!off_edge(p) && (get(p) & DOT)) { + // Don't allow adjacent dots + if (dir.first == 0 || dir.second == 0) return false; + // Allow diagonally adjacent placement some of the time + if (Random::rand() % 2 > 0) return false; + } + } + // Allow 2-space horizontal/vertical placement some of the time + if (Random::rand() % (intersectionOnly ? 10 : 5) > 0) { + for (Point dir : _DIRECTIONS2) { + Point p = pos + dir; + if (!off_edge(p) && (get(p) & DOT)) { + return false; + } + } + } + return true; +} + +// Place the given amount of dots at random points on the path +bool Generate::place_dots(int amount, Decoration::Color color, + bool intersectionOnly) { + if (_parity != -1) { // For full dot puzzles, don't put dots on the starts + // and exits unless there are multiple + for (int x = 0; x < _panel->width(); x += 2) { + for (int y = 0; y < _panel->height(); y += 2) { + if (_starts.size() == 1 && _starts.count(Point(x, y))) continue; + if (_exits.size() == 1 && _exits.count(Point(x, y))) continue; + if (!hasSymbolOrPath(x, y)) continue; + set(x, y, Decoration::Dot_Intersection); + } + } + amount -= _panel->get_num_grid_points(); + if (amount <= 0) return true; + intersectionOnly = false; + setFlagOnce(Config::DisableDotIntersection); + } + + /*if (color == Decoration::Color::Blue || color == Decoration::Color::Cyan) + color = IntersectionFlags::DOT_IS_BLUE; + else if (color == Decoration::Color::Yellow || + color == Decoration::Color::Orange) + color = IntersectionFlags::DOT_IS_ORANGE; + else + color = 0;*/ + + std::set open = + (color == 0 ? _path + : (color == Decoration::Color::Blue || color == Decoration::Color::Cyan) + ? _path1 + : _path2); + for (Point p : _starts) open.erase(p); + for (Point p : _exits) open.erase(p); + for (Point p : blockPos) open.erase(p); + if (intersectionOnly) { + std::set intersections; + for (Point p : open) { + if (p.first % 2 == 0 && p.second % 2 == 0) intersections.insert(p); + } + open = intersections; + } + if (hasFlag(Config::DisableDotIntersection)) { + std::set intersections; + for (Point p : open) { + if (p.first % 2 != 0 || p.second % 2 != 0) intersections.insert(p); + } + open = intersections; + } + + while (amount > 0) { + if (open.size() == 0) return false; + Point pos = pick_random(open); + open.erase(pos); + if (!can_place_dot(pos, intersectionOnly)) continue; + Decoration::Shape symbol = (pos.first & 1) == 1 ? Decoration::Dot_Row + : (pos.second & 1) == 1 + ? Decoration::Dot_Column + : Decoration::Dot_Intersection; + set(pos, symbol | color); + for (Point dir : _DIRECTIONS1) { + open.erase(pos + dir); + } // If symmetry, set a flag to break the point symmetric to the dot + if (_panel->symmetry) { + Point sp = get_sym_point(pos); + symbol = (sp.first & 1) == 1 ? Decoration::Dot_Row + : (sp.second & 1) == 1 ? Decoration::Dot_Column + : Decoration::Dot_Intersection; + if (symbol != Decoration::Dot_Intersection) + set(sp, symbol & ~Decoration::Dot); + open.erase(sp); + for (Point dir : _DIRECTIONS1) { + open.erase(sp + dir); + } + } + amount--; + } + return true; +} + +// Check if a stone can be placed at pos. +bool Generate::can_place_stone(const std::set& region, int color) { + for (Point p : region) { + int sym = get(p); + if (get_symbol_type(sym) == Decoration::Stone) return (sym & 0xf) == color; + } + return true; +} + +// Place the given amount of stones with the given color +bool Generate::place_stones(int color, int amount) { + std::set open = _openpos; + std::set + open2; // Used to store open points removed from the first pass, to make + // sure a stone is put in every non-adjacent region + int passCount = 0; + int originalAmount = amount; + while (amount > 0) { + if (open.size() == 0) { + // Make sure there is room for the remaining stones and enough partitions + // have been made (based on the grid size) + if (open2.size() < amount || + _bisect && + passCount < std::min(originalAmount, (_panel->width() / 2 + + _panel->height() / 2 + 2) / + 4)) + return false; + // Put remaining stones wherever they will fit + Point pos = pick_random(open2); + set(pos, Decoration::Stone | color); + _openpos.erase(pos); + open2.erase(pos); + amount--; + continue; + } + Point pos = pick_random(open); + std::set region = get_region(pos); + if (!can_place_stone(region, color)) { + for (Point p : region) { + open.erase(p); + } + continue; + } + if (_stoneTypes > 2) { // If more than two colors, group stones together, + // otherwise it takes too long to generate. + open.clear(); + for (Point p : region) { + if (_openpos.count(p)) open.insert(p); + } + } + open.erase(pos); + if (_panel->symmetry) { + open.erase(get_sym_point(pos)); + } + if (_stoneTypes == 2) { + for (Point p : region) { + if (open.erase(p)) open2.insert(p); + } // Remove adjacent regions from the open list + for (Point p : region) { + for (Point dir : _8DIRECTIONS2) { + Point pos2 = p + dir; + if (open.count(pos2) && !region.count(pos2)) { + for (Point P : get_region(pos2)) { + open.erase(P); + } + } + } + } + } + set(pos, Decoration::Stone | color); + _openpos.erase(pos); + amount--; + passCount++; + } + _bisect = false; // After placing one color, adjacent regions are allowed + _stoneTypes--; + return true; +} + +// Generate a random shape. region - the region of points to choose from; points +// chosen will be removed. bufferRegion - points that may be chosen twice due to +// overlapping shapes; points will be removed from here before points in region. +// maxSize - the maximum size of the generated shape. Whether the points can be +// contiguous or not is determined by local variable _SHAPEDIRECTIONS +Shape Generate::generate_shape(std::set& region, + std::set& bufferRegion, Point pos, + int maxSize) { + Shape shape; + shape.insert(pos); + if (!bufferRegion.erase(pos)) region.erase(pos); + while (shape.size() < maxSize && region.size() > 0) { + pos = pick_random(shape); + int i = 0; + for (; i < 10; i++) { + Point dir = pick_random(_SHAPEDIRECTIONS); + Point p = pos + dir; + if (region.count(p) && !shape.count(p)) { + shape.insert(p); + if (!bufferRegion.erase(p)) region.erase(p); + break; + } + } + if (i == 10) return shape; + } + return shape; +} + +// Get the integer representing the shape, accounting for whether it is rotated +// or negative. -1 rotation means a random rotation, depth is for controlling +// recursion and should be set to 0 +int Generate::make_shape_symbol(Shape shape, bool rotated, bool negative, + int rotation, int depth) { + int symbol = static_cast(Decoration::Poly); + if (rotated) { + if (rotation == -1) { + if (make_shape_symbol(shape, rotated, negative, 0, depth + 1) == + make_shape_symbol(shape, rotated, negative, 1, depth + 1)) + return 0; // Check to make sure the shape is not the same when rotated + rotation = Random::rand() % 4; + } + symbol |= Decoration::Can_Rotate; + Shape newShape; // Rotate shape points according to rotation + for (Point p : shape) { + switch (rotation) { + case 0: + newShape.insert(p); + break; + case 1: + newShape.emplace(Point(p.second, -p.first)); + break; + case 2: + newShape.emplace(Point(-p.second, p.first)); + break; + case 3: + newShape.emplace(Point(-p.first, -p.second)); + break; + } + } + shape = newShape; + } + if (negative) symbol |= Decoration::Negative; + int xmin = INT_MAX, xmax = INT_MIN, ymin = INT_MAX, ymax = INT_MIN; + for (Point p : shape) { + if (p.first < xmin) xmin = p.first; + if (p.first > xmax) xmax = p.first; + if (p.second < ymin) ymin = p.second; + if (p.second > ymax) ymax = p.second; + } + if (xmax - xmin > 6 || + ymax - ymin > 6) { // Shapes cannot be more than 4 in width and height + return 0; + } + // Translate to the corner and set bit flags (16 bits, 1 where a shape block + // is present) + for (Point p : shape) { + symbol |= (1 << ((p.first - xmin) / 2 + (ymax - p.second) * 2)) << 16; + } + if (Random::rand() % 4 > + 0) { // The generator makes a certain type of symbol way too often (2x2 + // square with another square attached), this makes it much less + // frequent + int type = symbol >> 16; + if (type == 0x0331 || type == 0x0332 || type == 0x0037 || type == 0x0067 || + type == 0x0133 || type == 0x0233 || type == 0x0073 || type == 0x0076) + return 0; + } + return symbol; +} + +// Place the given amount of shapes with random colors selected from the color +// vectors. colors - colors for regular shapes, negativeColors - colors for +// negative shapes, amount - how many normal shapes numRotated - how many +// rotated shapes, numNegative - how many negative shapes +bool Generate::place_shapes(const std::vector& colors, + const std::vector& negativeColors, int amount, + int numRotated, int numNegative) { + std::set open = _openpos; + int shapeSize = hasFlag(Config::SmallShapes) ? 2 + : hasFlag(Config::BigShapes) ? amount == 1 ? 8 : 6 + : 4; + int targetArea = amount * shapeSize * 7 / + 8; // Average size must be at least 7/8 of the target size + if (amount * shapeSize > _panel->get_num_grid_blocks()) + targetArea = _panel->get_num_grid_blocks(); + int originalAmount = amount; + if (hasFlag(Generate::Config::MountainFloorH) && + _panel->width() == + 9) { // The 4 small puzzles shape size may vary depending on the path + targetArea = 0; + removeFlag(Generate::Config::MountainFloorH); + } + int totalArea = 0; + int minx = _panel->width(), miny = _panel->height(), maxx = 0, maxy = 0; + int colorIndex = Random::rand() % colors.size(); + int colorIndexN = Random::rand() % (negativeColors.size() + 1); + bool shapesCanceled = false, shapesCombined = false, flatShapes = true; + if (amount == 1) shapesCombined = true; + while (amount > 0) { + if (open.size() == 0) return false; + Point pos = pick_random(open); + std::set region = get_region(pos); + std::set bufferRegion; + std::set open2; // Open points for just that region + for (Point p : region) { + if (open.erase(p)) open2.insert(p); + } + if (region.size() + totalArea == _panel->get_num_grid_blocks() && + targetArea != _panel->get_num_grid_blocks()) + continue; // To prevent shapes from filling every grid point + std::vector shapes; + std::vector shapesN; + int numShapesN = std::min( + Random::rand() % (numNegative + 1), + static_cast(region.size()) / + 3); // Negative blocks may be at max 1/3 of the regular blocks + if (amount == 1) numShapesN = numNegative; + if (numShapesN) { + std::set regionN = _gridpos; + int maxSize = static_cast(region.size()) - + numShapesN * 3; // Max size of negative shapes + if (maxSize == 0) maxSize = 1; + for (int i = 0; i < numShapesN; i++) { + pos = pick_random(region); + // Try to pick a random point adjacent to a shape + for (int i = 0; i < 10; i++) { + Point p = pos + pick_random(_SHAPEDIRECTIONS); + if (regionN.count(p) && !region.count(p)) { + pos = p; + break; + } + } + if (!regionN.count(pos)) return false; + Shape shape = generate_shape(regionN, pos, + std::min(Random::rand() % 3 + 1, maxSize)); + shapesN.push_back(shape); + for (Point p : shape) { + if (region.count(p)) + bufferRegion.insert( + p); // Buffer region stores overlap between shapes + else + region.insert(p); + } + } + } + int numShapes = + static_cast(region.size() + bufferRegion.size()) / + (shapeSize + 1) + + 1; // Pick a number of shapes to make. I tried different ones until I + // found something that made a good variety of shapes + if (numShapes == 1 && bufferRegion.size() > 0) + numShapes++; // If there is any overlap, we need at least two shapes + if (numShapes < amount && region.size() > shapeSize && + Random::rand() % 2 == 1) + numShapes++; // Adds more variation to the shape sizes + if (region.size() <= shapeSize + 1 && bufferRegion.size() == 0 && + Random::rand() % 2 == 1) + numShapes = 1; // For more variation, sometimes make a bigger shape than + // the target if the size is close + if (hasFlag(Config::MountainFloorH)) { + if (region.size() < 19) continue; + numShapes = 6; // The big mountain floor puzzle on hard mode needs + // additional shapes since some combine + targetArea = 19; + } + if (hasFlag(Config::SplitShapes) && numShapes != 1) continue; + if (hasFlag(Config::RequireCombineShapes) && numShapes == 1) continue; + bool balance = false; + if (numShapes > + amount // The region is too big for the number of shapes chosen + ) { + if (numNegative < 2 || hasFlag(Config::DisableCancelShapes)) continue; + // Make balancing shapes - Positive and negative will be switched so that + // code can be reused + balance = true; + std::set regionN = _gridpos; + numShapes = std::max( + 2, Random::rand() % numNegative + 1); // Actually the negative shapes + numShapesN = std::min(amount, 1); // Actually the positive shapes + if (numShapesN >= numShapes * 3 || numShapesN * 5 <= numShapes) continue; + shapes.clear(); + shapesN.clear(); + region.clear(); + bufferRegion.clear(); + for (int i = 0; i < numShapesN; i++) { + Shape shape = + generate_shape(regionN, pick_random(regionN), + std::min(shapeSize + 1, numShapes * 2 / numShapesN + + Random::rand() % 3 - 1)); + shapesN.push_back(shape); + for (Point p : shape) { + region.insert(p); + } + } + shapesCanceled = true; + // Let the rest of the algorithm create the cancelling shapes + } + if (_panel->symmetry && numShapes == originalAmount && numShapes >= 3 && + !region.count(Point((_panel->width() / 4) * 2 + 1, + (_panel->height() / 4) * 2 + 1))) + continue; // Prevent it from shoving all shapes to one side of symmetry + if ((_panel->symmetry == Panel::Symmetry::ParallelH || + _panel->symmetry == Panel::Symmetry::ParallelV || + _panel->symmetry == Panel::Symmetry::ParallelHFlip || + _panel->symmetry == Panel::Symmetry::ParallelVFlip) && + region.count(Point((_panel->width() / 4) * 2 + 1, + (_panel->height() / 4) * 2 + 1))) + continue; // Prevent parallel symmetry from making regions through the + // center line (this tends to make the puzzles way too hard) + if (!balance && numShapesN && + (numShapesN > 1 && numRotated > 0 || numShapesN > 2 || + numShapes + numShapesN > 6)) + continue; // Trying to prevent the game's shape calculator from lagging + // too much + if (!(hasFlag(Config::MountainFloorH) && _panel->width() == 11) && + open2.size() < numShapes + numShapesN) + continue; // Not enough space to put the symbols + if (numShapes == 1) { + shapes.push_back(region); + region.clear(); + } else + for (; numShapes > 0; numShapes--) { + if (region.size() == 0) break; + Shape shape = + generate_shape(region, bufferRegion, pick_random(region), + balance ? Random::rand() % 3 + 1 : shapeSize); + if (!balance && numShapesN) + for (Shape s : shapesN) + if (std::equal(shape.begin(), shape.end(), s.begin(), s.end())) + return false; // Prevent unintentional in-group canceling + shapes.push_back(shape); + } + // Take remaining area and try to stick it to existing shapes + multibreak: + while (region.size() > 0) { + pos = pick_random(region); + for (Shape& shape : shapes) { + if (shape.size() > shapeSize || shape.count(pos) > 0) continue; + for (Point p : shape) { + for (Point dir : _DIRECTIONS2) { + if (pos + dir == p) { + shape.insert(pos); + if (!bufferRegion.erase(pos)) region.erase(pos); + goto multibreak; + } + } + } + } + // Failed to cover entire region, need to pick a different region + break; + } + if (region.size() > 0) continue; + if (balance) { // Undo swap for balancing shapes + std::swap(shapes, shapesN); + } + numShapes = static_cast(shapes.size()); + for (Shape& shape : shapesN) { + shapes.push_back(shape); + } + if (hasFlag(Config::DisconnectShapes)) { + // Make sure at least one shape is disconnected + bool disconnect = false; + for (Shape& shape : shapes) { + if (shape.size() == 1) continue; + disconnect = true; + for (Point p : shape) { + for (Point dir : _DIRECTIONS2) { + if (shape.count(p + dir)) { + disconnect = false; + break; + } + } + if (!disconnect) break; + } + if (disconnect) break; + } + if (!disconnect) continue; + } + if (numShapes > 1) shapesCombined = true; + numNegative -= static_cast(shapesN.size()); + if (hasFlag(Generate::Config::MountainFloorH) && + amount == + 6) { // For mountain floor, combine some of the shapes together + if (!combine_shapes(shapes) || + !combine_shapes( + shapes)) // Must call this twice b/c there are two combined areas + return false; + amount -= 2; + } + for (Shape& shape : shapes) { + int symbol = + make_shape_symbol(shape, (numRotated-- > 0), (numShapes-- <= 0)); + if (symbol == 0) return false; + if (!((symbol >> 16) == 0x000F || (symbol >> 16) == 0x1111)) + flatShapes = false; + // Attempt not to put shape symbols adjacent + Point pos; + for (int i = 0; i < 10; i++) { + if (open2.size() == 0) return false; + pos = pick_random(open2); + bool pass = true; + for (Point dir : _8DIRECTIONS2) { + Point p = pos + dir; + if (!off_edge(p) && get(p) & Decoration::Poly) { + pass = false; + break; + } + } + if (pass) break; + } + if (symbol & Decoration::Negative) + set(pos, + symbol | negativeColors[(colorIndexN++) % negativeColors.size()]); + else { + set(pos, symbol | colors[(colorIndex++) % colors.size()]); + totalArea += static_cast(shape.size()); + amount--; + } + open2.erase(pos); + _openpos.erase(pos); + if (_panel->symmetry && originalAmount >= 3) { + for (const Point& p : shape) { + if (p.first < minx) minx = p.first; + if (p.second < miny) miny = p.second; + if (p.first > maxx) maxx = p.first; + if (p.second > maxy) maxy = p.second; + } + } + } + } // Do some final checks - make sure targetArea has been reached, all shapes + // have been placed, and that config requirements have been met + if (totalArea < targetArea || numNegative > 0 || + hasFlag(Config::RequireCancelShapes) && !shapesCanceled || + hasFlag(Config::RequireCombineShapes) && !shapesCombined || + originalAmount > 1 && flatShapes) + return false; + // If symmetry, make sure it didn't shove all the shapes to one side + if (_panel->symmetry && originalAmount >= 3 && + (minx >= _panel->width() / 2 || maxx <= _panel->width() / 2 || + miny >= _panel->height() / 2 || maxy <= _panel->height() / 2)) + return false; + return true; +} + +// Count the occurrence of the given symbol color in the given region (for the +// stars) +int Generate::count_color(const std::set& region, int color) { + int count = 0; + for (Point p : region) { + int sym = get(p); + if (sym && (sym & 0xf) == color) + if (count++ == 2) return count; + } + return count; +} + +// Place the given amount of stars with the given color +bool Generate::place_stars(int color, int amount) { + std::set open = _openpos; + while (amount > 0) { + if (open.size() == 0) return false; + Point pos = pick_random(open); + std::set region = get_region(pos); + std::set open2; // All of the open points in that region + for (Point p : region) { + if (open.erase(p)) open2.insert(p); + } + int count = count_color(region, color); + if (count >= 2) continue; // Too many of that color + if (open2.size() + count < 2) + continue; // Not enough space to get 2 of that color + if (count == 0 && amount == 1) + continue; // If one star is left, it needs a pair + set(pos, Decoration::Star | color); + _openpos.erase(pos); + amount--; + if (count == 0) { // Add a second star of the same color + open2.erase(pos); + if (open2.size() == 0) return false; + pos = pick_random(open2); + set(pos, Decoration::Star | color); + _openpos.erase(pos); + amount--; + } + } + return true; +} + +// Check if there is a star in the given region +bool Generate::has_star(const std::set& region, int color) { + for (Point p : region) { + if (get(p) == (Decoration::Star | color)) return true; + } + return false; +} + +bool Generate::checkStarZigzag() { + if (_panel->width() <= 5 || _panel->height() <= 5) return true; + for (int y = 1; y < _panel->height(); y += 2) { + std::map colorCount; + for (int x = 1; x < _panel->width(); x += 2) { + int color = get(x, y); + if (color == 0) continue; + if (!colorCount.count(color)) colorCount[color] = 0; + colorCount[color] += 1; + } + for (std::pair count : colorCount) + if (count.second % 2 != 0) return true; + } + return false; +} + +// Place the given amount of triangles with the given color. targetCount is how +// many triangles are in the symbol, or 0 for random +bool Generate::place_triangles(int color, int amount, int targetCount) { + /*if (_panel->id == 0x033EA) { // Keep Yellow Pressure Plate + int count = count_sides({1, 3}); + set({1, 3}, Decoration::Triangle | (count << 16) | color); + _openpos.erase({1, 3}); + }*/ + std::set open = _openpos; + int count1 = 0, count2 = 0, count3 = 0; + while (amount > 0) { + if (open.size() == 0) return false; + Point pos = pick_random(open); + int count = count_sides(pos); + open.erase(pos); + if (_panel->symmetry) { + open.erase(get_sym_point(pos)); + } + if (count == 0 || targetCount && count != targetCount) continue; + if (hasFlag(Config::TreehouseLayout) /*|| + _panel->id == 0x289E7*/) { // If the block is adjacent to a start or + // exit, don't place a triangle there + bool found = false; + for (Point dir : _DIRECTIONS1) { + if (_starts.count(pos + dir) || _exits.count(pos + dir)) { + found = true; + break; + } + } + if (found) continue; + } + if (count == 1) { + if (!targetCount && count1 * 2 > count2 + count3 && + Random::rand() % 2 == 0) + continue; + count1++; + } + if (count == 2) { + if (!targetCount && count2 * 2 > count1 + count3 && + Random::rand() % 2 == 0) + continue; + count2++; + } + if (count == 3) { + if (!targetCount && count3 * 2 > count1 + count2 && + Random::rand() % 2 == 0) + continue; + count3++; + } + set(pos, Decoration::Triangle | (count << 16) | color); + _openpos.erase(pos); + amount--; + } + return true; +} + +// Count how many sides are touched by the line (for the triangles) +int Generate::count_sides(Point pos) { + int count = 0; + for (Point dir : _DIRECTIONS1) { + Point p = pos + dir; + if (!off_edge(p) && get(p) == PATH) { + count++; + } + } + return count; +} + +// Place the given amount of arrows with the given color. targetCount is how +// many ticks on the arrows, or 0 for random The color won't actually be +// reflected, ArrowRecolor must be used instead +bool Generate::place_arrows(int color, int amount, int targetCount) { + std::set open = _openpos; + while (amount > 0) { + if (open.size() == 0) return false; + Point pos = pick_random(open); + open.erase(pos); + if (pos.first == _panel->width() / 2) + continue; // Because of a glitch where arrows in the center column won't + // draw right + int fails = 0; + while (fails++ < 20) { // Keep picking random directions until one works + int choice = (_parity == -1 ? Random::rand() % 8 : Random::rand() % 4); + Point dir = _8DIRECTIONS2[choice]; + int count = count_crossings(pos, dir); + if (count == 0 || count > 3 || targetCount && count != targetCount) + continue; + if (dir.first < 0 && count == (pos.first + 1) / 2 || + dir.first > 0 && count == (_panel->width() - pos.first) / 2 || + dir.second < 0 && count == (pos.second + 1) / 2 || + dir.second > 0 && count == (_panel->height() - pos.second) / 2 && + Random::rand() % 10 > 0) + continue; // Make it so that there will be some possible edges that + // aren't passed, in the vast majority of cases + //_panel->SetGridSymbol(pos, Decoration::Arrow | color | (count << 12) | + //(choice << 16)); + _openpos.erase(pos); + amount--; + break; + } + } + return true; +} + +// Count the number of times the given vector is passed through (for the arrows) +int Generate::count_crossings(Point pos, Point dir) { + pos = pos + dir / 2; + int count = 0; + while (!off_edge(pos)) { + if (get(pos) == PATH) count++; + pos = pos + dir; + } + return count; +} + +// Place the given amount of erasers with the given colors. eraseSymbols are the +// symbols that were erased +bool Generate::place_erasers(const std::vector& colors, + const std::vector& eraseSymbols) { + std::set open = _openpos; + /*if (_panel->id == 0x288FC && hasFlag(Generate::Config::DisableWrite)) + open.erase({5, 5}); // For the puzzle in the cave with a pillar in middle*/ + int amount = static_cast(colors.size()); + while (amount > 0) { + if (open.size() == 0) return false; + int toErase = eraseSymbols[amount - 1]; + int color = colors[amount - 1]; + Point pos = pick_random(open); + std::set region = get_region(pos); + std::set open2; + for (Point p : region) { + if (open.erase(p)) open2.insert(p); + } + if (_splitPoints.size() > + 0) { // Make sure this is one of the split point regions + bool found = false; + for (Point p : _splitPoints) { + if (region.count(p)) { + found = true; + break; + } + } + if (!found) continue; + } + /*if (_panel->id == 0x288FC && hasFlag(Generate::Config::DisableWrite) && + !region.count({5, 5})) + continue; // For the puzzle in the cave with a pillar in middle*/ + if (hasFlag(Config::MakeStonesUnsolvable)) { + std::set valid; + for (Point p : open2) { + // Try to make a checkerboard pattern with the stones + if (!off_edge(p + Point(2, 2)) && get(p + Point(2, 2)) == toErase && + get(p + Point(0, 2)) != 0 && get(p + Point(0, 2)) != toErase && + get(p + Point(2, 0)) != 0 && get(p + Point(2, 0)) != toErase || + !off_edge(p + Point(-2, 2)) && get(p + Point(-2, 2)) == toErase && + get(p + Point(0, 2)) != 0 && get(p + Point(0, 2)) != toErase && + get(p + Point(-2, 0)) != 0 && + get(p + Point(-2, 0)) != toErase || + !off_edge(p + Point(2, -2)) && get(p + Point(2, -2)) == toErase && + get(p + Point(0, -2)) != 0 && + get(p + Point(0, -2)) != toErase && get(p + Point(2, 0)) != 0 && + get(p + Point(2, 0)) != toErase || + !off_edge(p + Point(-2, -2)) && get(p + Point(-2, -2)) == toErase && + get(p + Point(0, -2)) != 0 && + get(p + Point(0, -2)) != toErase && + get(p + Point(-2, 0)) != 0 && get(p + Point(-2, 0)) != toErase) + valid.insert(p); + } + open2 = valid; + } + if ((open2.size() == 0 || _splitPoints.size() == 0 && open2.size() == 1) && + !(toErase & Decoration::Dot)) + continue; + bool canPlace = false; + if (get_symbol_type(toErase) == Decoration::Stone) { + canPlace = !can_place_stone(region, (toErase & 0xf)); + } else if (get_symbol_type(toErase) == Decoration::Star) { + canPlace = (count_color(region, (toErase & 0xf)) + + (color == (toErase & 0xf) ? 1 : 0) != + 1); + } else + canPlace = true; + if (!canPlace) continue; + + if (get_symbol_type(toErase) == Decoration::Stone || + get_symbol_type(toErase) == Decoration::Star) { + set(pos, toErase); + } else if (toErase & + Decoration::Dot) { // Find an open edge to put the dot on + std::set openEdge; + for (Point p : region) { + for (Point dir : _8DIRECTIONS1) { + if (toErase == Decoration::Dot_Intersection && + (dir.first == 0 || dir.second == 0)) + continue; + Point p2 = p + dir; + if (!hasSymbolOrPath(p2) && + (hasFlag(Config::FalseParity) || can_place_dot(p2, false))) { + openEdge.insert(p2); + } + } + } + if (openEdge.size() == 0) continue; + pos = pick_random(openEdge); + toErase &= ~IntersectionFlags::INTERSECTION; + if ((toErase & 0xf) == Decoration::Color::Blue || + (toErase & 0xf) == Decoration::Color::Cyan) + toErase |= IntersectionFlags::DOT_IS_BLUE; + if ((toErase & 0xf) == Decoration::Color::Yellow || + (toErase & 0xf) == Decoration::Color::Orange) + toErase |= IntersectionFlags::DOT_IS_ORANGE; + toErase &= ~0x4000f; // Take away extra flags from the symbol + if ((pos.first & 1) == 0 && (pos.second & 1) == 0) + toErase |= Decoration::Dot_Intersection; + else if ((pos.second & 1) == 0) + toErase |= Decoration::Dot_Row; + set(pos, ((pos.first & 1) == 1 ? Decoration::Dot_Row + : (pos.second & 1) == 1 ? Decoration::Dot_Column + : Decoration::Dot_Intersection) | + (toErase & 0xffff)); + } else if (get_symbol_type(toErase) == Decoration::Poly) { + int symbol = 0; // Make a random shape to cancel + while (symbol == 0) { + std::set area = _gridpos; + int shapeSize; + if ((toErase & Decoration::Negative) || hasFlag(Config::SmallShapes)) + shapeSize = Random::rand() % 3 + 1; + else { + shapeSize = Random::rand() % 5 + 1; + if (shapeSize < 3) shapeSize += Random::rand() % 3; + } + Shape shape = generate_shape(area, pick_random(area), shapeSize); + if (shape.size() == region.size()) + continue; // Don't allow the shape to match the region, to guarantee + // it will be wrong + symbol = make_shape_symbol(shape, toErase & Decoration::Can_Rotate, + toErase & Decoration::Negative); + } + set(pos, symbol | (toErase & 0xf)); + } else if (get_symbol_type(toErase) == Decoration::Triangle) { + if (hasFlag(Config::TreehouseLayout) /*|| + _panel->id == 0x289E7*/) { // If the block is adjacent to a start or + // exit, don't place a triangle there + bool found = false; + for (Point dir : _DIRECTIONS1) { + if (_starts.count(pos + dir) || _exits.count(pos + dir)) { + found = true; + break; + } + } + if (found) continue; + } + int count = count_sides(pos); + if (count == 0) + count = Random::rand() % 3 + 1; + else + count = (count + (Random::rand() & 1)) % 3 + 1; + set(pos, toErase | (count << 16)); + } + + if (!(toErase & Decoration::Dot)) { + _openpos.erase(pos); + open2.erase(pos); + } + // Place the eraser at a random open point + if (_splitPoints.size() == 0) + pos = pick_random(open2); + else + for (Point p : _splitPoints) + if (region.count(p)) { + pos = p; + break; + } + /*if (_panel->id == 0x288FC && hasFlag(Generate::Config::DisableWrite)) { + if (hasSymbolOrPath(5, 5)) return false; + pos = {5, 5}; // For the puzzle in the cave with a pillar in middle + }*/ + set(pos, Decoration::Eraser | color); + _openpos.erase(pos); + amount--; + } + return true; +} + +// For the mountain floor puzzle on hard mode. Combine two tetris shapes into +// one +bool Generate::combine_shapes(std::vector& shapes) { + for (int i = 0; i < shapes.size(); i++) { + for (int j = 0; j < shapes.size(); j++) { + if (i == j) continue; + if (shapes[i].size() + shapes[j].size() <= 5) continue; + if (shapes[i].size() > 5 || shapes[j].size() > 5) continue; + // Look for adjacent points + for (Point p1 : shapes[i]) { + for (Point p2 : shapes[j]) { + for (Point dir : _DIRECTIONS2) { + if (p1 + dir == p2) { + // Combine shapes + for (Point p : shapes[i]) shapes[j].insert(p); + // Make sure there are no holes + std::set area = _gridpos; + for (Point p : shapes[j]) area.erase(p); + while (area.size() > 0) { + std::set region; + std::vector check; + check.push_back(*area.begin()); + region.insert(*area.begin()); + while (check.size() > 0) { + Point p = check[check.size() - 1]; + check.pop_back(); + for (Point dir : _DIRECTIONS1) { + Point p2 = p + dir * 2; + if (area.count(p2) && region.insert(p2).second) { + check.push_back(p2); + } + } + } + bool connected = false; + for (Point p : region) { + if (p.first == 1 || p.second == 1 || + p.first == _panel->width() - 2 || + p.second == _panel->height() - 2) { + connected = true; + break; + } + } + if (!connected) return false; + for (Point p : region) area.erase(p); + } + shapes.erase(shapes.begin() + i); + return true; + } + } + } + } + } + } + return false; +} + +bool Generate::hasSymbolOrPath(int x, int y) { return get(x, y) != 0; } diff --git a/ext/wittle_generator/Generate.h b/ext/wittle_generator/Generate.h new file mode 100644 index 0000000..c28a47d --- /dev/null +++ b/ext/wittle_generator/Generate.h @@ -0,0 +1,248 @@ +#ifndef GENERATE_H_0582FCEA +#define GENERATE_H_0582FCEA + +#include +#include + +#include +#include +#include +#include + +#include "Panel.h" +#include "PuzzleSymbols.h" +#include "Random.h" + +typedef std::set Shape; + +// The main class for generating puzzles. +class Generate { + public: + Generate() { + _width = _height = 0; + _areaTotal = _genTotal = _totalPuzzles = _areaPuzzles = _stoneTypes = 0; + _fullGaps = _bisect = _allowNonMatch = false; + _panel = NULL; + _parity = -1; + colorblind = false; + _seed = Random::rand(); + arrowColor = backgroundColor = successColor = {0, 0, 0, 0}; + resetConfig(); + } + enum Config { // See configinfo.txt for explanations of config flags. + None = 0, + FullGaps = 0x1, + StartEdgeOnly = 0x2, + DisableWrite = 0x4, + PreserveStructure = 0x8, + MakeStonesUnsolvable = 0x10, + SmallShapes = 0x20, + DisconnectShapes = 0x40, + ResetColors = 0x80, + DisableCancelShapes = 0x100, + RequireCancelShapes = 0x200, + BigShapes = 0x400, + SplitShapes = 0x800, + RequireCombineShapes = 0x1000, + TreehouseLayout = 0x2000, + TreehouseColors = 0x4000, + AlternateColors = 0x8000, + WriteColors = 0x10000, + Write2Color = 0x20000, + FixBackground = 0x40000, + CombineErasers = 0x80000, + LongPath = 0x100000, + ShortPath = 0x200000, + EnableFlash = 0x400000, + DecorationsOnly = 0x800000, + FalseParity = 0x1000000, + DisableDotIntersection = 0x2000000, + WriteDotColor = 0x4000000, + WriteDotColor2 = 0x8000000, + LongestPath = 0x10000000, + WriteInvisible = 0x20000000, + DisableReset = 0x40000000, + MountainFloorH = 0x80000000 + }; + + void generate(int width, int height, PuzzleSymbols symbols); + + /*void generateMaze(int id); + void generateMaze(int id, int numStarts, int numExits);*/ + void initPanel(); + void setPath(const std::set& path) { + customPath = path; + for (Point p : path) setSymbol(IntersectionFlags::PATH, p.first, p.second); + } + void setObstructions(const std::vector& walls) { + _obstructions = {walls}; + } + void setObstructions(const std::vector>& walls) { + _obstructions = walls; + } + void setSymbol(Decoration::Shape symbol, int x, int y); + void setSymbol(IntersectionFlags symbol, int x, int y) { + setSymbol(static_cast(symbol), x, y); + } + void setGridSize(int width, int height); + void setSymmetry(Panel::Symmetry symmetry); + void write(int id); + void setFlag(Config option) { _config |= option; }; + void setFlagOnce(Config option) { + _config |= option; + _oneTimeAdd |= option; + }; + bool hasFlag(Config option) { return _config & option; }; + void removeFlag(Config option) { _config &= ~option; }; + void removeFlagOnce(Config option) { + _config &= ~option; + _oneTimeRemove |= option; + }; + void resetConfig(); + void seed(long seed) { + Random::seed(seed); + _seed = Random::rand(); + } + + float pathWidth; // Controls how thick the line is on the puzzle + std::vector hitPoints; // The generated path will be forced to hit + // these points in order + std::set + openPos; // Custom set of points that can have symbols placed on + std::set blockPos; // Point that must be left open + std::set customPath; + Color arrowColor, backgroundColor, successColor; // For the arrow puzzles + + private: + int get_symbol_type(int flags) { return flags & 0x700; } + void set_path(Point pos); + Point get_sym_point(Point pos) { return _panel->get_sym_point(pos); } + int get_parity(Point pos) { return (pos.first / 2 + pos.second / 2) % 2; } + void clear(); + void resetVars(); + void init_treehouse_layout(); + template + T pick_random(const std::vector& vec) { + return vec[Random::rand() % vec.size()]; + } + template + T pick_random(const std::set& set) { + auto it = set.begin(); + std::advance(it, Random::rand() % set.size()); + return *it; + } + template + T pop_random(const std::vector& vec) { + int i = Random::rand() % vec.size(); + T item = vec[i]; + vec.erase(vec.begin() + i); + return item; + } + template + T pop_random(const std::set& set) { + T item = pick_random(set); + set.erase(item); + return item; + } + bool on_edge(Point p) { + return (p.first == 0 || p.first + 1 == _panel->width() || p.second == 0 || + p.second + 1 == _panel->height()); + } + bool off_edge(Point p) { + return (p.first < 0 || p.first >= _panel->width() || p.second < 0 || + p.second >= _panel->height()); + } + static std::vector _DIRECTIONS1, _8DIRECTIONS1, _DIRECTIONS2, + _8DIRECTIONS2, _SHAPEDIRECTIONS, _DISCONNECT; + // bool generate_maze(int id, int numStarts, int numExits); + bool generateInternal(int width, int height, PuzzleSymbols symbols); + bool place_all_symbols(PuzzleSymbols& symbols); + bool generate_path(PuzzleSymbols& symbols); + bool generate_path_length(int minLength, int maxLength); + bool generate_path_length(int minLength) { + return generate_path_length(minLength, 10000); + }; + bool generate_path_regions(int minRegions); + bool generate_longest_path(); + bool generate_special_path(); + void erase_path(); + Point adjust_point(Point pos); + std::set get_region(Point pos); + std::vector get_symbols_in_region(Point pos); + std::vector get_symbols_in_region(const std::set& region); + bool place_start(int amount); + bool place_exit(int amount); + bool can_place_gap(Point pos); + bool place_gaps(int amount); + bool can_place_dot(Point pos, bool intersectionOnly); + bool place_dots(int amount, Decoration::Color color, bool intersectionOnly); + bool can_place_stone(const std::set& region, int color); + bool place_stones(int color, int amount); + Shape generate_shape(std::set& region, std::set& bufferRegion, + Point pos, int maxSize); + Shape generate_shape(std::set& region, Point pos, int maxSize) { + std::set buffer; + return generate_shape(region, buffer, pos, maxSize); + } + int make_shape_symbol(Shape shape, bool rotated, bool negative, int rotation, + int depth); + int make_shape_symbol(const Shape& shape, bool rotated, bool negative) { + return make_shape_symbol(shape, rotated, negative, -1, 0); + } + bool place_shapes(const std::vector& colors, + const std::vector& negativeColors, int amount, + int numRotated, int numNegative); + int count_color(const std::set& region, int color); + bool place_stars(int color, int amount); + bool has_star(const std::set& region, int color); + bool checkStarZigzag(); + bool place_triangles(int color, int amount, int targetCount); + int count_sides(Point pos); + bool place_arrows(int color, int amount, int targetCount); + int count_crossings(Point pos, Point dir); + bool place_erasers(const std::vector& colors, + const std::vector& eraseSymbols); + bool combine_shapes(std::vector& shapes); + + bool hasSymbolOrPath(const Point& pos) { + return hasSymbolOrPath(pos.first, pos.second); + } + bool hasSymbolOrPath(int x, int y); + + std::unique_ptr _panel; + std::vector> _custom_grid; + int _width, _height; + Panel::Symmetry _symmetry; + std::set _starts, _exits; + std::set _gridpos, _openpos; + std::set _path, _path1, _path2; + bool _fullGaps, _bisect; + int _stoneTypes; + int _config; + int _oneTimeAdd, _oneTimeRemove; + long _seed; + std::vector _splitPoints; + bool _allowNonMatch; // Used for multi-generator + int _parity; + std::vector> _obstructions; + bool colorblind; + + int _areaTotal, _genTotal, _areaPuzzles, _totalPuzzles; + std::wstring _areaName; + + void set(int x, int y, int val) { _panel->set(x, y, val); } + void set(const Point& pos, int val) { + _panel->set(pos.first, pos.second, val); + } + + int get(int x, int y) { return _panel->get(x, y); } + int get(const Point& pos) { return _panel->get(pos.first, pos.second); } + + // std::vector> _panelData; + // std::vector> _drawnPath; + + friend class PuzzleList; + friend class Special; +}; + +#endif /* end of include guard: GENERATE_H_0582FCEA */ diff --git a/ext/wittle_generator/Panel.cpp b/ext/wittle_generator/Panel.cpp new file mode 100644 index 0000000..a005467 --- /dev/null +++ b/ext/wittle_generator/Panel.cpp @@ -0,0 +1,116 @@ +#include "Panel.h" + +#include +#include + +template +int find(const std::vector& data, T search, size_t startIndex = 0) { + for (size_t i = startIndex; i < data.size(); i++) { + if (data[i] == search) return static_cast(i); + } + return -1; +} + +void Panel::SetSymbol(int x, int y, Decoration::Shape symbol, + Decoration::Color color) { + int gridx = x * 2 + (symbol & IntersectionFlags::COLUMN ? 0 : 1); + int gridy = y * 2 + (symbol & IntersectionFlags::ROW ? 0 : 1); + if (symbol & IntersectionFlags::DOT) { + if (color == Decoration::Color::Blue || color == Decoration::Color::Cyan) + color = static_cast(IntersectionFlags::DOT_IS_BLUE); + else if (color == Decoration::Color::Orange || + color == Decoration::Color::Yellow) + color = static_cast(IntersectionFlags::DOT_IS_ORANGE); + else + color = Decoration::Color::None; + if (symmetry) { + Point sp = get_sym_point(gridx, gridy); + SetGridSymbol(sp.first, sp.second, + static_cast(symbol & ~Decoration::Dot), + Decoration::Color::None); + } + } else if (symbol & IntersectionFlags::ROW || + symbol & IntersectionFlags::COLUMN) + color = Decoration::Color::None; + SetGridSymbol(gridx, gridy, symbol, color); +} + +void Panel::SetShape(int x, int y, int shape, bool rotate, bool negative, + Decoration::Color color) { + if (!shape) return; + int symbol = Decoration::Shape::Poly; + while (!(shape & 0xf)) shape >>= 4; + while (!(shape & 0x1111)) shape >>= 1; + shape <<= 16; + if (rotate) + shape |= Decoration::Shape::Can_Rotate; + else + shape &= ~Decoration::Shape::Can_Rotate; + if (negative) + shape |= Decoration::Shape::Negative; + else + shape &= ~Decoration::Shape::Negative; + _grid[x * 2 + 1][y * 2 + 1] = symbol | shape | color; +} + +void Panel::ClearSymbol(int x, int y) { ClearGridSymbol(x * 2 + 1, y * 2 + 1); } + +void Panel::SetGridSymbol(int x, int y, Decoration::Shape symbol, + Decoration::Color color) { + if (symbol == Decoration::Start) _startpoints.push_back({x, y}); + if (symbol == Decoration::Exit) { + Endpoint::Direction dir; + if (y == 0) + dir = Endpoint::Direction::UP; + else if (y == _height - 1) + dir = Endpoint::Direction::DOWN; + else if (x == 0) + dir = Endpoint::Direction::LEFT; + else + dir = Endpoint::Direction::RIGHT; + /*if (id == 0x033D4 || id == 0x0A3B5) { + if (x == 0) + dir = Endpoint::Direction::LEFT; + else + dir = Endpoint::Direction::RIGHT; + }*/ + if (symmetry == Symmetry::ParallelH || + symmetry == Symmetry::ParallelHFlip) { + if (x == 0) dir = Endpoint::Direction::LEFT; + if (x == _width - 1) dir = Endpoint::Direction::RIGHT; + } + _endpoints.emplace_back(Endpoint( + x, y, dir, + IntersectionFlags::ENDPOINT | + (dir == Endpoint::Direction::UP || dir == Endpoint::Direction::DOWN + ? IntersectionFlags::COLUMN + : IntersectionFlags::ROW))); + } else + _grid[x][y] = symbol | color; +} + +void Panel::ClearGridSymbol(int x, int y) { _grid[x][y] = 0; } + +void Panel::Resize(int width, int height) { + for (Point& s : _startpoints) { + if (s.first == _width - 1) s.first = width - 1; + if (s.second == _height - 1) s.second = height - 1; + } + for (Endpoint& e : _endpoints) { + if (e.GetX() == _width - 1) e.SetX(width - 1); + if (e.GetY() == _height - 1) e.SetY(height - 1); + } + if (_width != _height || width != height) { + float maxDim = std::max(maxx - minx, maxy - miny); + float unitSize = maxDim / std::max(width - 1, height - 1); + minx = 0.5f - unitSize * (width - 1) / 2; + maxx = 0.5f + unitSize * (width - 1) / 2; + miny = 0.5f - unitSize * (height - 1) / 2; + maxy = 0.5f + unitSize * (height - 1) / 2; + } + _width = width; + _height = height; + _grid.resize(width); + for (auto& row : _grid) row.resize(height); + _resized = true; +} diff --git a/ext/wittle_generator/Panel.h b/ext/wittle_generator/Panel.h new file mode 100644 index 0000000..7444a9a --- /dev/null +++ b/ext/wittle_generator/Panel.h @@ -0,0 +1,448 @@ +#ifndef PANEL_H_FC471D68 +#define PANEL_H_FC471D68 + +#include + +#include +#include + +struct Point { + int first; + int second; + Point() { + first = 0; + second = 0; + }; + Point(int x, int y) { + first = x; + second = y; + } + Point operator+(const Point& p) { + return {first + p.first, second + p.second}; + } + Point operator*(int d) { return {first * d, second * d}; } + Point operator/(int d) { return {first / d, second / d}; } + bool operator==(const Point& p) const { + return first == p.first && second == p.second; + }; + bool operator!=(const Point& p) const { + return first != p.first || second != p.second; + }; + friend bool operator<(const Point& p1, const Point& p2) { + if (p1.first == p2.first) return p1.second < p2.second; + return p1.first < p2.first; + }; +}; + +class Decoration { + public: + enum Shape : int { + Exit = 0x600001, + Start = 0x600002, + Stone = 0x100, + Star = 0x200, + Poly = 0x400, + Eraser = 0x500, + Triangle = 0x600, + Triangle1 = 0x10600, + Triangle2 = 0x20600, + Triangle3 = 0x30600, + Triangle4 = 0x40600, + Arrow = 0x700, + Arrow1 = 0x1700, + Arrow2 = 0x2700, + Arrow3 = 0x3700, + Can_Rotate = 0x1000, + Negative = 0x2000, + Gap = 0x100000, + Gap_Row = 0x300000, + Gap_Column = 0x500000, + Dot = 0x20, + Dot_Row = 0x240020, + Dot_Column = 0x440020, + Dot_Intersection = 0x600020, + Empty = 0xA00, + }; + enum Color : int { + None = 0, + Black = 0x1, + White = 0x2, + Red = 0x3, // Doesn't work sadly + Purple = 0x4, + Green = 0x5, + Cyan = 0x6, + Magenta = 0x7, + Yellow = 0x8, + Blue = 0x9, + Orange = 0xA, + X = 0xF, + }; +}; + +enum IntersectionFlags : int { + ROW = 0x200000, + COLUMN = 0x400000, + INTERSECTION = 0x600000, + ENDPOINT = 0x1, + STARTPOINT = 0x2, + OPEN = 0x3, // Puzzle loader flag - not to be written out + PATH = 0x4, // Generator use only + NO_POINT = 0x8, // Points that nothing connects to + GAP = 0x100000, + DOT = 0x20, + DOT_IS_BLUE = 0x100, + DOT_IS_ORANGE = 0x200, + DOT_IS_INVISIBLE = 0x1000, + DOT_SMALL = 0x2000, + DOT_MEDIUM = 0x4000, + DOT_LARGE = 0x8000, +}; + +class Endpoint { + public: + enum Direction { + NONE = 0, + LEFT = 1, + RIGHT = 2, + UP = 4, + DOWN = 8, + UP_LEFT = 5, + UP_RIGHT = 6, + DOWN_LEFT = 9, + DOWN_RIGHT = 10 + }; + + Endpoint(int x, int y, Direction dir, int flags) { + _x = x; + _y = y; + _dir = dir; + _flags = flags; + } + + int GetX() { return _x; } + void SetX(int x) { _x = x; } + int GetY() { return _y; } + void SetY(int y) { _y = y; } + Direction GetDir() { return _dir; } + int GetFlags() { return _flags; } + void SetDir(Direction dir) { _dir = dir; } + + private: + int _x, _y, _flags; + Direction _dir; +}; + +struct Color { + float r; + float g; + float b; + float a; + friend bool operator<(const Color& lhs, const Color& rhs) { + return lhs.r * 8 + lhs.g * 4 + lhs.b * 2 + lhs.a > + rhs.r * 8 + rhs.g * 4 + rhs.b * 2 + rhs.a; + } +}; + +struct SolutionPoint { + int pointA, pointB, pointC, pointD; + float f1x, f1y, f2x, f2y, f3x, f3y, f4x, f4y; + int endnum; +}; + +class Panel { + public: + void SetSymbol(int x, int y, Decoration::Shape symbol, + Decoration::Color color); + void SetShape(int x, int y, int shape, bool rotate, bool negative, + Decoration::Color color); + void ClearSymbol(int x, int y); + void SetGridSymbol(int x, int y, Decoration::Shape symbol, + Decoration::Color color = Decoration::Color::None); + void ClearGridSymbol(int x, int y); + void Resize(int width, int height); + + int width() const { return _width; } + int height() const { return _height; } + + int get(int x, int y) { return _grid[x][y]; } + void set(int x, int y, int val) { _grid[x][y] = val; } + + enum Style { + SYMMETRICAL = 0x2, // Not on the town symmetry puzzles? IDK why. + NO_BLINK = 0x4, + HAS_DOTS = 0x8, + IS_2COLOR = 0x10, + HAS_STARS = 0x40, + HAS_TRIANGLES = 0x80, + HAS_STONES = 0x100, + HAS_ERASERS = 0x1000, + HAS_SHAPERS = 0x2000, + IS_PIVOTABLE = 0x8000, + }; + + enum Symmetry { // NOTE - Not all of these are valid symmetries for certain + // puzzles + None, + Horizontal, + Vertical, + Rotational, + RotateLeft, + RotateRight, + FlipXY, + FlipNegXY, + ParallelH, + ParallelV, + ParallelHFlip, + ParallelVFlip, + PillarParallel, + PillarHorizontal, + PillarVertical, + PillarRotational + }; + Symmetry symmetry; + + float pathWidth; + enum ColorMode { + Default, + Reset, + Alternate, + WriteColors, + Treehouse, + TreehouseAlternate + }; + ColorMode colorMode; + bool decorationsOnly; + bool enableFlash; + + Point get_sym_point(int x, int y, Symmetry symmetry) { + switch (symmetry) { + case None: + return Point(x, y); + case Symmetry::Horizontal: + return Point(x, _height - 1 - y); + case Symmetry::Vertical: + return Point(_width - 1 - x, y); + case Symmetry::Rotational: + return Point(_width - 1 - x, _height - 1 - y); + case Symmetry::RotateLeft: + return Point(y, _width - 1 - x); + case Symmetry::RotateRight: + return Point(_height - 1 - y, x); + case Symmetry::FlipXY: + return Point(y, x); + case Symmetry::FlipNegXY: + return Point(_height - 1 - y, _width - 1 - x); + case Symmetry::ParallelH: + return Point(x, y == _height / 2 + ? _height / 2 + : (y + (_height + 1) / 2) % (_height + 1)); + case Symmetry::ParallelV: + return Point(x == _width / 2 ? _width / 2 + : (x + (_width + 1) / 2) % (_width + 1), + y); + case Symmetry::ParallelHFlip: + return Point(_width - 1 - x, + y == _height / 2 + ? _height / 2 + : (y + (_height + 1) / 2) % (_height + 1)); + case Symmetry::ParallelVFlip: + return Point(x == _width / 2 ? _width / 2 + : (x + (_width + 1) / 2) % (_width + 1), + _height - 1 - y); + case Symmetry::PillarParallel: + return Point(x + _width / 2, y); + case Symmetry::PillarHorizontal: + return Point(x + _width / 2, _height - 1 - y); + case Symmetry::PillarVertical: + return Point(_width / 2 - x, y); + case Symmetry::PillarRotational: + return Point(_width / 2 - x, _height - 1 - y); + } + return Point(x, y); + } + + Point get_sym_point(int x, int y) { return get_sym_point(x, y, symmetry); } + Point get_sym_point(Point p) { + return get_sym_point(p.first, p.second, symmetry); + } + Point get_sym_point(Point p, Symmetry symmetry) { + return get_sym_point(p.first, p.second, symmetry); + } + Endpoint::Direction get_sym_dir(Endpoint::Direction direction, + Symmetry symmetry) { + int dirIndex; + if (direction == Endpoint::Direction::LEFT) dirIndex = 0; + if (direction == Endpoint::Direction::RIGHT) dirIndex = 1; + if (direction == Endpoint::Direction::UP) dirIndex = 2; + if (direction == Endpoint::Direction::DOWN) dirIndex = 3; + std::vector mapping; + switch (symmetry) { + case Symmetry::Horizontal: + mapping = {Endpoint::Direction::LEFT, Endpoint::Direction::RIGHT, + Endpoint::Direction::DOWN, Endpoint::Direction::UP}; + break; + case Symmetry::Vertical: + mapping = {Endpoint::Direction::RIGHT, Endpoint::Direction::LEFT, + Endpoint::Direction::UP, Endpoint::Direction::DOWN}; + break; + case Symmetry::Rotational: + mapping = {Endpoint::Direction::RIGHT, Endpoint::Direction::LEFT, + Endpoint::Direction::DOWN, Endpoint::Direction::UP}; + break; + case Symmetry::RotateLeft: + mapping = {Endpoint::Direction::DOWN, Endpoint::Direction::UP, + Endpoint::Direction::LEFT, Endpoint::Direction::RIGHT}; + break; + case Symmetry::RotateRight: + mapping = {Endpoint::Direction::UP, Endpoint::Direction::DOWN, + Endpoint::Direction::RIGHT, Endpoint::Direction::LEFT}; + break; + case Symmetry::FlipXY: + mapping = {Endpoint::Direction::UP, Endpoint::Direction::DOWN, + Endpoint::Direction::LEFT, Endpoint::Direction::RIGHT}; + break; + case Symmetry::FlipNegXY: + mapping = {Endpoint::Direction::DOWN, Endpoint::Direction::UP, + Endpoint::Direction::RIGHT, Endpoint::Direction::LEFT}; + break; + case Symmetry::ParallelH: + mapping = {Endpoint::Direction::LEFT, Endpoint::Direction::RIGHT, + Endpoint::Direction::UP, Endpoint::Direction::DOWN}; + break; + case Symmetry::ParallelV: + mapping = {Endpoint::Direction::LEFT, Endpoint::Direction::RIGHT, + Endpoint::Direction::UP, Endpoint::Direction::DOWN}; + break; + case Symmetry::ParallelHFlip: + mapping = {Endpoint::Direction::RIGHT, Endpoint::Direction::LEFT, + Endpoint::Direction::UP, Endpoint::Direction::DOWN}; + break; + case Symmetry::ParallelVFlip: + mapping = {Endpoint::Direction::LEFT, Endpoint::Direction::RIGHT, + Endpoint::Direction::DOWN, Endpoint::Direction::UP}; + break; + default: + mapping = {Endpoint::Direction::LEFT, Endpoint::Direction::RIGHT, + Endpoint::Direction::UP, Endpoint::Direction::DOWN}; + break; + } + return mapping[dirIndex]; + } + + int get_num_grid_points() { return ((_width + 1) / 2) * ((_height + 1) / 2); } + int get_num_grid_blocks() { return (_width / 2) * (_height / 2); } + int get_parity() { return (get_num_grid_points() + 1) % 2; } + + private: + std::pair loc_to_xy(int location) { + int height2 = (_height - 1) / 2; + int width2 = (_width + 1) / 2; + + int x = 2 * (location % width2); + int y = 2 * (height2 - location / width2); + return {x, y}; + } + + int xy_to_loc(int x, int y) { + int height2 = (_height - 1) / 2; + int width2 = (_width + 1) / 2; + + int rowsFromBottom = height2 - y / 2; + return rowsFromBottom * width2 + x / 2; + } + + std::pair dloc_to_xy(int location) { + int height2 = (_height - 3) / 2; + int width2 = _width / 2; + + int x = 2 * (location % width2) + 1; + int y = 2 * (height2 - location / width2) + 1; + return {x, y}; + } + + int xy_to_dloc(int x, int y) { + int height2 = (_height - 3) / 2; + int width2 = _width / 2; + + int rowsFromBottom = height2 - (y - 1) / 2; + return rowsFromBottom * width2 + (x - 1) / 2; + } + + int locate_segment(int x, int y, std::vector& connections_a, + std::vector& connections_b) { + for (int i = 0; i < connections_a.size(); i++) { + std::pair coord1 = loc_to_xy(connections_a[i]); + std::pair coord2 = loc_to_xy(connections_b[i]); + int x1 = coord1.first, y1 = coord1.second, x2 = coord2.first, + y2 = coord2.second; + if ((x1 == x - 1 && x2 == x + 1 && y1 == y && y2 == y) || + (y1 == y - 1 && y2 == y + 1 && x1 == x && x2 == x)) { + return i; + } + } + return -1; + } + + bool break_segment(int x, int y, std::vector& connections_a, + std::vector& connections_b, + std::vector& intersections, + std::vector& intersectionFlags) { + int i = locate_segment(x, y, connections_a, connections_b); + if (i == -1) { + return false; + } + int other_connection = connections_b[i]; + connections_b[i] = static_cast(intersectionFlags.size()); + connections_a.push_back(static_cast(intersectionFlags.size())); + connections_b.push_back(other_connection); + intersections.push_back(static_cast(minx + x * unitWidth)); + intersections.push_back( + static_cast(miny + (_height - 1 - y) * unitHeight)); + intersectionFlags.push_back(_grid[x][y]); + return true; + } + + bool break_segment_gap(int x, int y, std::vector& connections_a, + std::vector& connections_b, + std::vector& intersections, + std::vector& intersectionFlags) { + int i = locate_segment(x, y, connections_a, connections_b); + if (i == -1) { + return false; + } + int other_connection = connections_b[i]; + connections_b[i] = static_cast(intersectionFlags.size() + 1); + connections_a.push_back(other_connection); + connections_b.push_back(static_cast(intersectionFlags.size())); + if (!(_grid[x][y] & IntersectionFlags::GAP)) { + _grid[x][y] |= + (x % 2 == 0 ? IntersectionFlags::COLUMN : IntersectionFlags::ROW); + connections_a.push_back(static_cast(intersectionFlags.size())); + connections_b.push_back(static_cast(intersectionFlags.size() + 1)); + } + double xOffset = _grid[x][y] & IntersectionFlags::ROW ? 0.5 : 0; + double yOffset = _grid[x][y] & IntersectionFlags::COLUMN ? 0.5 : 0; + intersections.push_back( + static_cast(minx + (x + xOffset) * unitWidth)); + intersections.push_back( + static_cast(miny + (_height - 1 - y - yOffset) * unitHeight)); + intersections.push_back( + static_cast(minx + (x - xOffset) * unitWidth)); + intersections.push_back( + static_cast(miny + (_height - 1 - y + yOffset) * unitHeight)); + intersectionFlags.push_back(_grid[x][y]); + intersectionFlags.push_back(_grid[x][y]); + return true; + } + + int _width, _height; + + std::vector> _grid; + std::vector _startpoints; + std::vector _endpoints; + float minx, miny, maxx, maxy, unitWidth, unitHeight; + int _style; + bool _resized; +}; + +#endif /* end of include guard: PANEL_H_FC471D68 */ diff --git a/ext/wittle_generator/PuzzleSymbols.h b/ext/wittle_generator/PuzzleSymbols.h new file mode 100644 index 0000000..dedf61a --- /dev/null +++ b/ext/wittle_generator/PuzzleSymbols.h @@ -0,0 +1,59 @@ +#ifndef PUZZLESYMBOLS_H_9DD95900 +#define PUZZLESYMBOLS_H_9DD95900 + +#include +#include + +#include "Panel.h" +#include "Random.h" + +struct PuzzleSymbols { + std::map>> symbols; + std::vector>& operator[](int symbolType) { + return symbols[symbolType]; + } + int style; + int getNum(int symbolType) { + int total = 0; + for (auto& pair : symbols[symbolType]) total += pair.second; + return total; + } + bool any(int symbolType) { return symbols[symbolType].size() > 0; } + int popRandomSymbol() { + std::vector types; + for (auto& pair : symbols) + if (pair.second.size() > 0 && pair.first != Decoration::Start && + pair.first != Decoration::Exit && pair.first != Decoration::Gap && + pair.first != Decoration::Eraser) + types.push_back(pair.first); + int randType = types[Random::rand() % types.size()]; + int randIndex = Random::rand() % symbols[randType].size(); + while (symbols[randType][randIndex].second == 0 || + symbols[randType][randIndex].second >= 25) { + randType = types[Random::rand() % types.size()]; + randIndex = Random::rand() % symbols[randType].size(); + } + symbols[randType][randIndex].second--; + return symbols[randType][randIndex].first; + } + PuzzleSymbols(std::vector> symbolVec) { + for (std::pair s : symbolVec) { + if (s.first == Decoration::Gap || s.first == Decoration::Start || + s.first == Decoration::Exit) + symbols[s.first].push_back(s); + else if (s.first & Decoration::Dot) + symbols[Decoration::Dot].push_back(s); + else + symbols[s.first & 0x700].push_back(s); + } + style = 0; + if (any(Decoration::Dot)) style |= Panel::Style::HAS_DOTS; + if (any(Decoration::Stone)) style |= Panel::Style::HAS_STONES; + if (any(Decoration::Star)) style |= Panel::Style::HAS_STARS; + if (any(Decoration::Poly)) style |= Panel::Style::HAS_SHAPERS; + if (any(Decoration::Triangle)) style |= Panel::Style::HAS_TRIANGLES; + if (any(Decoration::Arrow)) style |= Panel::Style::HAS_TRIANGLES; + } +}; + +#endif /* end of include guard: PUZZLESYMBOLS_H_9DD95900 */ diff --git a/ext/wittle_generator/Random.cpp b/ext/wittle_generator/Random.cpp new file mode 100644 index 0000000..2248947 --- /dev/null +++ b/ext/wittle_generator/Random.cpp @@ -0,0 +1,5 @@ +#include "Random.h" + +#include + +std::mt19937 Random::gen = std::mt19937((int)time(0)); diff --git a/ext/wittle_generator/Random.h b/ext/wittle_generator/Random.h new file mode 100644 index 0000000..115c62d --- /dev/null +++ b/ext/wittle_generator/Random.h @@ -0,0 +1,16 @@ +#ifndef RANDOM_H_F3423EE7 +#define RANDOM_H_F3423EE7 + +#include + +#include + +struct Random { + static std::mt19937 gen; + + static void seed(int val) { gen = std::mt19937(val); } + + static int rand() { return abs((int)gen()); } +}; + +#endif /* end of include guard: RANDOM_H_F3423EE7 */ diff --git a/ext/wittle_generator/Test.cpp b/ext/wittle_generator/Test.cpp new file mode 100644 index 0000000..6139215 --- /dev/null +++ b/ext/wittle_generator/Test.cpp @@ -0,0 +1,10 @@ +#include "Generate.h" + +int main(int, char**) { + Generate generator; + generator.setSymbol(Decoration::Start, 0, 4 * 2); + generator.setSymbol(Decoration::Exit, 4 * 2, 0); + generator.generate(4 * 2 + 1, 4 * 2 + 1, {{{Decoration::Triangle, 6}}}); + + return 0; +} diff --git a/lib/keep b/lib/keep new file mode 100644 index 0000000..e69de29 -- cgit 1.4.1