From 0baa521ba34d2cd4e0f732f83d23b807605786a2 Mon Sep 17 00:00:00 2001 From: jbzdarkid Date: Sat, 16 Nov 2019 10:27:06 -0800 Subject: More and more progress. Split out functions in serializer Figured out how to allocate memory (for sequences) --- App/Main.cpp | 1 + Source/Memory.cpp | 25 +++- Source/Memory.h | 27 +++- Source/Puzzle.cpp | 11 +- Source/Puzzle.h | 20 +-- Source/PuzzlerSerializer.cpp | 285 ++++++++++++++++++++++++------------------- Source/PuzzlerSerializer.h | 24 +++- Source/Randomizer2.cpp | 207 +++++++++++++++++++++++++------ Source/Randomizer2.h | 1 + Source/Solver.cpp | 2 + 10 files changed, 413 insertions(+), 190 deletions(-) diff --git a/App/Main.cpp b/App/Main.cpp index a96c34d..a815746 100644 --- a/App/Main.cpp +++ b/App/Main.cpp @@ -24,6 +24,7 @@ #include "Puzzle.h" #include "Solver.h" #include "Randomizer2.h" +#include "PuzzlerSerializer.h" #include #define TMP1 0x501 diff --git a/Source/Memory.cpp b/Source/Memory.cpp index 98b06f9..bc0725b 100644 --- a/Source/Memory.cpp +++ b/Source/Memory.cpp @@ -70,7 +70,6 @@ void Memory::Heartbeat(HWND window) { PostMessage(window, WM_COMMAND, HEARTBEAT, (LPARAM)ProcStatus::Running); } - [[nodiscard]] bool Memory::Initialize() { // First, get the handle of the process @@ -106,6 +105,7 @@ bool Memory::Initialize() { std::cerr << "Couldn't locate base address" << std::endl; return false; } + return true; } @@ -161,7 +161,7 @@ void Memory::ThrowError() { } void* Memory::ComputeOffset(std::vector offsets) { - // Leave off the last offset, since it will be either read/write, and may not be of type unitptr_t. + // Leave off the last offset, since it will be either read/write, and may not be of type uintptr_t. int final_offset = offsets.back(); offsets.pop_back(); @@ -176,6 +176,9 @@ void* Memory::ComputeOffset(std::vector offsets) { if (bool result = !ReadProcessMemory(_handle, reinterpret_cast(cumulativeAddress), &computedAddress, sizeof(uintptr_t), NULL)) { ThrowError(); } + if (computedAddress == 0) { // Attempting to dereference a nullptr + ThrowError(); + } _computedAddresses[cumulativeAddress] = computedAddress; } @@ -183,3 +186,21 @@ void* Memory::ComputeOffset(std::vector offsets) { } return reinterpret_cast(cumulativeAddress + final_offset); } + +uintptr_t Memory::Allocate(size_t bytes) { + uintptr_t current = _freeMem; + _freeMem += bytes; + + if (_freeMem > _freeMemEnd) { + // If we don't have enough space at our current location, go allocate some more space. + // Note that the remaining space in our current page is unused. Oh well. + _freeMem = reinterpret_cast(::VirtualAllocEx(_handle, NULL, 0x1000, MEM_RESERVE | MEM_COMMIT, PAGE_READWRITE)); + _freeMemEnd = _freeMem + 0x1000; + + current = _freeMem; + _freeMem += bytes; + assert(_freeMem <= _freeMemEnd); // Don't allocate data > 0x1000 at a time. Duh. + } + + return current; +} diff --git a/Source/Memory.h b/Source/Memory.h index 6b8403f..af4f0ae 100644 --- a/Source/Memory.h +++ b/Source/Memory.h @@ -35,7 +35,14 @@ public: template void WriteArray(int panel, int offset, const std::vector& data) { - WriteData({GLOBALS, 0x18, panel*8, offset, 0}, data); + WriteData({GLOBALS, 0x18, panel*8, offset, 0}, data); + } + + template + void WriteNewArray(int panel, int offset, const std::vector& data) { + std::vector newAddr = {Allocate(data.size() * sizeof(T))}; + WritePanelData(panel, offset, newAddr); + WriteArray(panel, offset, data); } template @@ -45,7 +52,7 @@ public: template void WritePanelData(int panel, int offset, const std::vector& data) { - WriteData({GLOBALS, 0x18, panel*8, offset}, data); + WriteData({GLOBALS, 0x18, panel*8, offset}, data); } void AddSigScan(const std::vector& scanBytes, const std::function& scanFunc); @@ -57,9 +64,12 @@ private: if (numItems == 0) return {}; std::vector data; data.resize(numItems); + void* computedOffset = ComputeOffset(offsets); for (int i=0; i<5; i++) { - if (ReadProcessMemory(_handle, ComputeOffset(offsets), &data[0], sizeof(T) * numItems, nullptr)) - { + if (ReadProcessMemory(_handle, computedOffset, &data[0], sizeof(T) * numItems, nullptr)) { + if (i != 0) { + int k = 0; + } return data; } } @@ -70,8 +80,12 @@ private: template void WriteData(const std::vector& offsets, const std::vector& data) { if (data.empty()) return; + void* computedOffset = ComputeOffset(offsets); for (int i=0; i<5; i++) { - if (WriteProcessMemory(_handle, ComputeOffset(offsets), &data[0], sizeof(T) * data.size(), nullptr)) { + if (WriteProcessMemory(_handle, computedOffset, &data[0], sizeof(T) * data.size(), nullptr)) { + if (i != 0) { + int k = 0; + } return; } } @@ -82,6 +96,7 @@ private: bool Initialize(); void ThrowError(); void* ComputeOffset(std::vector offsets); + uintptr_t Allocate(size_t bytes); int _previousFrame = 0; bool _threadActive = false; @@ -90,6 +105,8 @@ private: std::map _computedAddresses; uintptr_t _baseAddress = 0; HANDLE _handle = nullptr; + uintptr_t _freeMem = 0; + uintptr_t _freeMemEnd = 0; struct SigScan { std::function scanFunc; bool found; diff --git a/Source/Puzzle.cpp b/Source/Puzzle.cpp index 72af129..d0ede27 100644 --- a/Source/Puzzle.cpp +++ b/Source/Puzzle.cpp @@ -2,18 +2,17 @@ #include "Memory.h" #include - -inline Cell Puzzle::GetCell(int x, int y) const { +Cell Puzzle::GetCell(int x, int y) const { x = Mod(x); if (!SafeCell(x, y)) return Cell::Undefined(); return grid[x][y]; } -inline Cell::Color Puzzle::GetLine(int x, int y) const { +Cell::Color Puzzle::GetLine(int x, int y) const { return grid[x][y].color; } -inline void Puzzle::NewGrid(int newWidth, int newHeight) { +void Puzzle::NewGrid(int newWidth, int newHeight) { if (newWidth == 0) { assert(false); newWidth = width; @@ -28,12 +27,12 @@ inline void Puzzle::NewGrid(int newWidth, int newHeight) { for (int x=0; x= width) return false; if (y < 0 || y >= height) return false; return true; diff --git a/Source/Puzzle.h b/Source/Puzzle.h index 3a8e73b..fdf51be 100644 --- a/Source/Puzzle.h +++ b/Source/Puzzle.h @@ -64,21 +64,23 @@ struct Pos {int x; int y;}; class Puzzle { public: - int16_t height; - int16_t width; + int16_t height = 0; + int16_t width = 0; bool hasDecorations = false; enum class Symmetry {NONE, X, Y, XY}; Symmetry sym = Symmetry::NONE; bool pillar = false; - bool valid; + bool valid = false; std::vector negations; std::vector invalidElements; - inline Cell GetCell(int x, int y) const; - inline Cell::Color GetLine(int x, int y) const; - inline void NewGrid(int newWidth, int newHeight); + std::vector sequence; + + Cell GetCell(int x, int y) const; + Cell::Color GetLine(int x, int y) const; + void NewGrid(int newWidth, int newHeight); // @TODO: Pos GetSymmetricalPos(int x, int y); @@ -86,7 +88,7 @@ public: // private: std::vector> grid; -private: - inline int Mod(int x) const; - inline bool SafeCell(int x, int y) const; +// private: + int Mod(int x) const; + bool SafeCell(int x, int y) const; }; diff --git a/Source/PuzzlerSerializer.cpp b/Source/PuzzlerSerializer.cpp index 779336d..86f59e7 100644 --- a/Source/PuzzlerSerializer.cpp +++ b/Source/PuzzlerSerializer.cpp @@ -11,21 +11,52 @@ Puzzle PuzzleSerializer::ReadPuzzle(int id) { int height = 2 * _memory->ReadPanelData(id, GRID_SIZE_Y, 1)[0] - 1; if (width < 0 || height < 0) return Puzzle(); // @Error: Grid size should be always positive? Looks like the starting panels break this rule, though. + int numIntersections = _memory->ReadPanelData(id, NUM_DOTS, 1)[0]; + _intersectionFlags = _memory->ReadArray(id, DOT_FLAGS, numIntersections); + int numConnections = _memory->ReadPanelData(id, NUM_CONNECTIONS, 1)[0]; + _connectionsA = _memory->ReadArray(id, DOT_CONNECTION_A, numConnections); + _connectionsB = _memory->ReadArray(id, DOT_CONNECTION_B, numConnections); + _intersectionLocations = _memory->ReadArray(id, DOT_POSITIONS, numIntersections*2); + Puzzle p; p.NewGrid(width, height); - ReadIntersections(p, id); + ReadIntersections(p); + ReadExtras(p); ReadDecorations(p, id); + ReadSequence(p, id); return p; } -void PuzzleSerializer::ReadIntersections(Puzzle& p, int id) { - int numIntersections = _memory->ReadPanelData(id, NUM_DOTS, 1)[0]; - std::vector intersectionFlags = _memory->ReadArray(id, DOT_FLAGS, numIntersections); - int numConnections = _memory->ReadPanelData(id, NUM_CONNECTIONS, 1)[0]; - std::vector connections_a = _memory->ReadArray(id, DOT_CONNECTION_A, numConnections); - std::vector connections_b = _memory->ReadArray(id, DOT_CONNECTION_B, numConnections); - std::vector intersectionLocations = _memory->ReadArray(id, DOT_POSITIONS, numIntersections*2); +void PuzzleSerializer::WritePuzzle(const Puzzle& p, int id) { + _intersectionFlags.clear(); + _connectionsA.clear(); + _connectionsB.clear(); + _intersectionLocations.clear(); + + MIN = 0.1f; + MAX = 0.9f; + WIDTH_INTERVAL = (MAX - MIN) / (p.width/2); + HEIGHT_INTERVAL = (MAX - MIN) / (p.height/2); + HORIZ_GAP_SIZE = WIDTH_INTERVAL / 2; + VERTI_GAP_SIZE = HEIGHT_INTERVAL / 2; + + WriteIntersections(p); + WriteEndpoints(p); + WriteDecorations(p, id); + WriteSequence(p, id); + + _memory->WritePanelData(id, GRID_SIZE_X, {(p.width + 1)/2}); + _memory->WritePanelData(id, GRID_SIZE_Y, {(p.height + 1)/2}); + _memory->WritePanelData(id, NUM_DOTS, {static_cast(_intersectionFlags.size())}); + _memory->WriteArray(id, DOT_POSITIONS, _intersectionLocations); + _memory->WriteArray(id, DOT_FLAGS, _intersectionFlags); + _memory->WritePanelData(id, NUM_CONNECTIONS, {static_cast(_connectionsA.size())}); + _memory->WriteArray(id, DOT_CONNECTION_A, _connectionsA); + _memory->WriteArray(id, DOT_CONNECTION_B, _connectionsB); + _memory->WritePanelData(id, NEEDS_REDRAW, {1}); +} +void PuzzleSerializer::ReadIntersections(Puzzle& p) { // @Cleanup: Change defaults? for (int x=0; x x2) x--; @@ -49,13 +80,15 @@ void PuzzleSerializer::ReadIntersections(Puzzle& p, int id) { else if (y1 > y2) y++; p.grid[x][y].gap = Cell::Gap::NONE; } +} +void PuzzleSerializer::ReadExtras(Puzzle& p) { // This iterates bottom-top, left-right int i = 0; - for (;; i++) { - int flags = intersectionFlags[i]; + for (; i < _intersectionFlags.size(); i++) { + int flags = _intersectionFlags[i]; auto [x, y] = loc_to_xy(p, i); - if (y < 0) break; + if (y < 0) break; // This is the expected exit point if (flags & Flags::IS_STARTPOINT) { p.grid[x][y].start = true; } @@ -66,31 +99,31 @@ void PuzzleSerializer::ReadIntersections(Puzzle& p, int id) { } // Iterate the remaining intersections (endpoints, dots, gaps) - for (; i < numIntersections; i++) { - int location = FindConnection(i, connections_a, connections_b); + for (; i < _intersectionFlags.size(); i++) { + int location = FindConnection(i); if (location == -1) continue; // @Error: Unable to find connection point // (x1, y1) location of this intersection // (x2, y2) location of the connected intersection - float x1 = intersectionLocations[2*i]; - float y1 = intersectionLocations[2*i+1]; - float x2 = intersectionLocations[2*location]; - float y2 = intersectionLocations[2*location+1]; + float x1 = _intersectionLocations[2*i]; + float y1 = _intersectionLocations[2*i+1]; + float x2 = _intersectionLocations[2*location]; + float y2 = _intersectionLocations[2*location+1]; auto [x, y] = loc_to_xy(p, location); - if (intersectionFlags[i] & Flags::IS_ENDPOINT) { + if (_intersectionFlags[i] & Flags::IS_ENDPOINT) { // Our x coordinate is less than the target's if (x1 < x2) p.grid[x][y].end = Cell::Dir::LEFT; else if (x1 > x2) p.grid[x][y].end = Cell::Dir::RIGHT; // Note that Y coordinates are reversed: 0.0 (bottom) 1.0 (top) else if (y1 < y2) p.grid[x][y].end = Cell::Dir::DOWN; else if (y1 > y2) p.grid[x][y].end = Cell::Dir::UP; - } else if (intersectionFlags[i] & Flags::HAS_DOT) { + } else if (_intersectionFlags[i] & Flags::HAS_DOT) { if (x1 < x2) x--; else if (x1 > x2) x++; else if (y1 < y2) y++; else if (y1 > y2) y--; - p.grid[x][y].dot = FlagsToDot(intersectionFlags[i]); - } else if (intersectionFlags[i] & Flags::HAS_ONE_CONN) { + p.grid[x][y].dot = FlagsToDot(_intersectionFlags[i]); + } else if (_intersectionFlags[i] & Flags::HAS_ONE_CONN) { if (x1 < x2) x--; else if (x1 > x2) x++; else if (y1 < y2) y++; @@ -124,36 +157,24 @@ void PuzzleSerializer::ReadDecorations(Puzzle& p, int id) { } } -void PuzzleSerializer::WritePuzzle(const Puzzle& p, int id) { - _memory->WritePanelData(id, GRID_SIZE_X, {(p.width + 1)/2}); - _memory->WritePanelData(id, GRID_SIZE_Y, {(p.height + 1)/2}); - - WriteIntersections(p, id); - if (p.hasDecorations) WriteDecorations(p, id); +void PuzzleSerializer::ReadSequence(Puzzle& p, int id) { + int sequenceLength = _memory->ReadPanelData(id, SEQUENCE_LEN, 1)[0]; + std::vector sequence = _memory->ReadArray(id, SEQUENCE, sequenceLength); - _memory->WritePanelData(id, NEEDS_REDRAW, {1}); + for (int location : sequence) { + auto [x, y] = loc_to_xy(p, location); + p.sequence.emplace_back(Pos{x, y}); + } } -void PuzzleSerializer::WriteIntersections(const Puzzle& p, int id) { - std::vector intersectionLocations; - std::vector intersectionFlags; - std::vector connections_a; - std::vector connections_b; - - float min = 0.1f; - float max = 0.9f; - float width_interval = (max - min) / (p.width/2); - float height_interval = (max - min) / (p.height/2); - float horiz_gap_size = width_interval / 2; - float verti_gap_size = height_interval / 2; - +void PuzzleSerializer::WriteIntersections(const Puzzle& p) { // @Cleanup: If I write directly to locations, then I can simplify this gross loop iterator. // int numIntersections = (p.width / 2 + 1) * (p.height / 2 + 1); // Grided intersections for (int y=p.height-1; y>=0; y-=2) { for (int x=0; x 0 && p.grid[x][y-1].gap == Cell::Gap::NONE) { - connections_a.push_back(xy_to_loc(p, x, y-2)); - connections_b.push_back(xy_to_loc(p, x, y)); + if (y > 0 && p.grid[x][y-1].gap != Cell::Gap::FULL) { + _connectionsA.push_back(xy_to_loc(p, x, y-2)); + _connectionsB.push_back(xy_to_loc(p, x, y)); flags |= Flags::HAS_VERTI_CONN; numConnections++; } // Top connection - if (y < p.height - 1 && p.grid[x][y+1].gap == Cell::Gap::NONE) { + if (y < p.height - 1 && p.grid[x][y+1].gap != Cell::Gap::FULL) { flags |= Flags::HAS_VERTI_CONN; numConnections++; } // Left connection - if (x > 0 && p.grid[x-1][y].gap == Cell::Gap::NONE) { - connections_a.push_back(xy_to_loc(p, x-2, y)); - connections_b.push_back(xy_to_loc(p, x, y)); + if (x > 0 && p.grid[x-1][y].gap != Cell::Gap::FULL) { + _connectionsA.push_back(xy_to_loc(p, x-2, y)); + _connectionsB.push_back(xy_to_loc(p, x, y)); flags |= Flags::HAS_HORIZ_CONN; numConnections++; } // Right connection - if (x < p.width - 1 && p.grid[x+1][y].gap == Cell::Gap::NONE) { + if (x < p.width - 1 && p.grid[x+1][y].gap != Cell::Gap::FULL) { flags |= Flags::HAS_HORIZ_CONN; numConnections++; } if (numConnections == 1) flags |= HAS_ONE_CONN; - intersectionFlags.push_back(flags); + _intersectionFlags.push_back(flags); } } +} - // Endpoints +void PuzzleSerializer::WriteEndpoints(const Puzzle& p) { for (int x=0; x(intersectionFlags.size())); // This endpoint + _connectionsA.push_back(xy_to_loc(p, x, y)); // Target to connect to + _connectionsB.push_back(static_cast(_intersectionFlags.size())); // This endpoint - float xPos = min + (x/2) * width_interval; - float yPos = max - (y/2) * height_interval; + auto [xPos, yPos] = xy_to_pos(p, x, y); switch (p.grid[x][y].end) { case Cell::Dir::LEFT: xPos -= .05f; @@ -231,13 +252,14 @@ void PuzzleSerializer::WriteIntersections(const Puzzle& p, int id) { yPos -= .05f; break; } - intersectionLocations.push_back(xPos); - intersectionLocations.push_back(yPos); - intersectionFlags.push_back(Flags::IS_ENDPOINT); + _intersectionLocations.push_back(xPos); + _intersectionLocations.push_back(yPos); + _intersectionFlags.push_back(Flags::IS_ENDPOINT); } } +} - // Dots +void PuzzleSerializer::WriteDots(const Puzzle& p) { for (int x=0; x(intersectionFlags.size()); // This endpoint + int other_connection = _connectionsB[i]; + _connectionsB[i] = static_cast(_intersectionFlags.size()); // This endpoint - connections_a.push_back(other_connection); - connections_b.push_back(static_cast(intersectionFlags.size())); // This endpoint + _connectionsA.push_back(other_connection); + _connectionsB.push_back(static_cast(_intersectionFlags.size())); // This endpoint break; } } // Add this dot to the end - float xPos = min + (x/2.0f) * width_interval; - float yPos = max - (y/2.0f) * height_interval; - intersectionLocations.push_back(xPos); - intersectionLocations.push_back(yPos); + auto [xPos, yPos] = xy_to_pos(p, x, y); + _intersectionLocations.push_back(xPos); + _intersectionLocations.push_back(yPos); int flags = Flags::HAS_DOT; switch (p.grid[x][y].dot) { @@ -278,56 +299,51 @@ void PuzzleSerializer::WriteIntersections(const Puzzle& p, int id) { flags |= DOT_IS_INVISIBLE; break; } - intersectionFlags.push_back(flags); + _intersectionFlags.push_back(flags); } } +} - // Gaps +void PuzzleSerializer::WriteGaps(const Puzzle& p) { for (int x=0; x(intersectionFlags.size())); // This endpoint - intersectionLocations.push_back(xPos); - intersectionLocations.push_back(yPos + verti_gap_size / 2); - intersectionFlags.push_back(Flags::HAS_ONE_CONN | Flags::HAS_VERTI_CONN); - - connections_a.push_back(xy_to_loc(p, x, y+1)); - connections_b.push_back(static_cast(intersectionFlags.size())); // This endpoint - intersectionLocations.push_back(xPos); - intersectionLocations.push_back(yPos - verti_gap_size / 2); - intersectionFlags.push_back(Flags::HAS_ONE_CONN | Flags::HAS_VERTI_CONN); + _connectionsA.push_back(xy_to_loc(p, x, y-1)); + _connectionsB.push_back(static_cast(_intersectionFlags.size())); // This endpoint + _intersectionLocations.push_back(xPos); + _intersectionLocations.push_back(yPos + VERTI_GAP_SIZE / 2); + _intersectionFlags.push_back(Flags::HAS_ONE_CONN | Flags::HAS_VERTI_CONN); + + _connectionsA.push_back(xy_to_loc(p, x, y+1)); + _connectionsB.push_back(static_cast(_intersectionFlags.size())); // This endpoint + _intersectionLocations.push_back(xPos); + _intersectionLocations.push_back(yPos - VERTI_GAP_SIZE / 2); + _intersectionFlags.push_back(Flags::HAS_ONE_CONN | Flags::HAS_VERTI_CONN); } else if (y%2 == 0) { // Horizontal gap - connections_a.push_back(xy_to_loc(p, x-1, y)); - connections_b.push_back(static_cast(intersectionFlags.size())); // This endpoint - intersectionLocations.push_back(xPos - horiz_gap_size / 2); - intersectionLocations.push_back(yPos); - intersectionFlags.push_back(Flags::HAS_ONE_CONN | Flags::HAS_HORIZ_CONN); - - connections_a.push_back(xy_to_loc(p, x+1, y)); - connections_b.push_back(static_cast(intersectionFlags.size())); // This endpoint - intersectionLocations.push_back(xPos + horiz_gap_size / 2); - intersectionLocations.push_back(yPos); - intersectionFlags.push_back(Flags::HAS_ONE_CONN | Flags::HAS_HORIZ_CONN); + _connectionsA.push_back(xy_to_loc(p, x-1, y)); + _connectionsB.push_back(static_cast(_intersectionFlags.size())); // This endpoint + _intersectionLocations.push_back(xPos - HORIZ_GAP_SIZE / 2); + _intersectionLocations.push_back(yPos); + _intersectionFlags.push_back(Flags::HAS_ONE_CONN | Flags::HAS_HORIZ_CONN); + + _connectionsA.push_back(xy_to_loc(p, x+1, y)); + _connectionsB.push_back(static_cast(_intersectionFlags.size())); // This endpoint + _intersectionLocations.push_back(xPos + HORIZ_GAP_SIZE / 2); + _intersectionLocations.push_back(yPos); + _intersectionFlags.push_back(Flags::HAS_ONE_CONN | Flags::HAS_HORIZ_CONN); } } } - - _memory->WritePanelData(id, NUM_DOTS, {static_cast(intersectionFlags.size())}); - _memory->WriteArray(id, DOT_POSITIONS, intersectionLocations); - _memory->WriteArray(id, DOT_FLAGS, intersectionFlags); - _memory->WritePanelData(id, NUM_CONNECTIONS, {static_cast(connections_a.size())}); - _memory->WriteArray(id, DOT_CONNECTION_A, connections_a); - _memory->WriteArray(id, DOT_CONNECTION_B, connections_b); } void PuzzleSerializer::WriteDecorations(const Puzzle& p, int id) { + if (!p.hasDecorations) return; + std::vector decorations; for (int y=p.height-2; y>0; y-=2) { for (int x=1; xWriteArray(id, DECORATIONS, decorations); } +void PuzzleSerializer::WriteSequence(const Puzzle& p, int id) { + if (p.sequence.size() == 0) return; + + std::vector sequence; + for (Pos pos : p.sequence) { + // Only include intersections, the game does not treat segments as real objects + if (pos.x%2 == 0 && pos.y%2 == 0) { + sequence.emplace_back(xy_to_loc(p, pos.x, pos.y)); + } + } + + _memory->WritePanelData(id, SEQUENCE_LEN, {static_cast(sequence.size())}); + _memory->WriteNewArray(id, SEQUENCE, sequence); +} + std::tuple PuzzleSerializer::loc_to_xy(const Puzzle& p, int location) const { int height2 = (p.height - 1) / 2; int width2 = (p.width + 1) / 2; @@ -378,23 +409,25 @@ int PuzzleSerializer::xy_to_dloc(const Puzzle& p, int x, int y) const { return rowsFromBottom * width2 + (x - 1)/2; } +std::tuple PuzzleSerializer::xy_to_pos(const Puzzle& p, int x, int y) const { + return { + MIN + (x/2) * WIDTH_INTERVAL, + MAX - (y/2) * HEIGHT_INTERVAL + }; +} + Cell::Dot PuzzleSerializer::FlagsToDot(int flags) const { if (!(flags & Flags::HAS_DOT)) return Cell::Dot::NONE; - if (flags & Flags::DOT_IS_BLUE) { - return Cell::Dot::BLUE; - } else if (flags & Flags::DOT_IS_ORANGE) { - return Cell::Dot::YELLOW; - } else if (flags & Flags::DOT_IS_INVISIBLE) { - return Cell::Dot::INVISIBLE; - } else { - return Cell::Dot::BLACK; - } + if (flags & Flags::DOT_IS_BLUE) return Cell::Dot::BLUE; + else if (flags & Flags::DOT_IS_ORANGE) return Cell::Dot::YELLOW; + else if (flags & Flags::DOT_IS_INVISIBLE) return Cell::Dot::INVISIBLE; + else return Cell::Dot::BLACK; } -int PuzzleSerializer::FindConnection(int i, const std::vector& connections_a, const std::vector& connections_b) const { - for (int j=0; j loc_to_xy(const Puzzle& p, int location) const; int xy_to_loc(const Puzzle& p, int x, int y) const; // Decoration location std::tuple dloc_to_xy(const Puzzle& p, int location) const; int xy_to_dloc(const Puzzle& p, int x, int y) const; + // Grid coordinates + std::tuple xy_to_pos(const Puzzle& p, int x, int y) const; Cell::Dot FlagsToDot(int flags) const; // Iterate connection lists for another location which is connected to us; return that other location. - int FindConnection(int i, const std::vector& connections_a, const std::vector& connections_b) const; + int FindConnection(int location) const; std::shared_ptr _memory; + + std::vector _intersectionLocations; + std::vector _intersectionFlags; + std::vector _connectionsA; + std::vector _connectionsB; + + float MIN, MAX, WIDTH_INTERVAL, HEIGHT_INTERVAL, HORIZ_GAP_SIZE, VERTI_GAP_SIZE; }; diff --git a/Source/Randomizer2.cpp b/Source/Randomizer2.cpp index 537c30b..b5218bf 100644 --- a/Source/Randomizer2.cpp +++ b/Source/Randomizer2.cpp @@ -3,6 +3,9 @@ #include "Random.h" #include "Solver.h" #include "Memory.h" +#include "PuzzlerSerializer.h" +#include +#include void FloodFillInternal(const Puzzle& p, std::vector>& reached, int x, int y) { if (x%2 == 1 && y%2 == 1) return; @@ -62,10 +65,10 @@ void Randomizer2::Randomize() { for (int j=0; j(edges.size() - 1)); Pos pos = edges[edge]; - p.grid[pos.x][pos.y].gap = Cell::Gap::FULL; edges.erase(edges.begin() + edge); if (FloodFill(p)) { + p.grid[pos.x][pos.y].gap = Cell::Gap::FULL; break; } else { p.grid[pos.x][pos.y].gap = Cell::Gap::NONE; @@ -108,10 +111,10 @@ void Randomizer2::Randomize() { int edge = Random::RandInt(0, static_cast(edges.size() - 1)); Pos pos = edges[edge]; - p.grid[pos.x][pos.y].gap = Cell::Gap::FULL; edges.erase(edges.begin() + edge); if (FloodFill(p)) { + p.grid[pos.x][pos.y].gap = Cell::Gap::FULL; break; } else { p.grid[pos.x][pos.y].gap = Cell::Gap::NONE; @@ -152,19 +155,100 @@ void Randomizer2::Randomize() { } +void DebugColorGrid(const std::vector>& colorGrid) { + for (int y=0; y>& colorGrid, int color, int x, int y) { + if (!p.SafeCell(x, y)) return; + if (colorGrid[x][y] != 0) return; // Already processed. + colorGrid[x][y] = color; + + FloodFill(p, colorGrid, color, x, y+1); + FloodFill(p, colorGrid, color, x, y-1); + FloodFill(p, colorGrid, color, x+1, y); + FloodFill(p, colorGrid, color, x-1, y); +} + +void FloodFillOutside(const Puzzle&p, std::vector>& colorGrid, int x, int y) { + if (!p.SafeCell(x, y)) return; + if (colorGrid[x][y] != 0) return; // Already processed. + if (x%2 != y%2 && p.grid[x][y].gap != Cell::Gap::FULL) return; // Only flood-fill through full gaps + colorGrid[x][y] = 1; // Outside color + + FloodFillOutside(p, colorGrid, x, y+1); + FloodFillOutside(p, colorGrid, x, y-1); + FloodFillOutside(p, colorGrid, x+1, y); + FloodFillOutside(p, colorGrid, x-1, y); +} + +/* + undefined -> 1 (color of outside) or * (any colored cell) or -1 (edge/intersection not part of any region) + + 0 -> {} (this is a special edge case, which I don't need right now) + 1 -> 0 (uncolored / ready to color) + 2 -> +*/ +std::vector> CreateColorGrid(const Puzzle& p) { + std::vector> colorGrid; + colorGrid.resize(p.width); + + for (int x=0; x edges; + for (int x=0; x gates = {0x00344, 0x00488, 0x00489, 0x00495, 0x00496}; + for (int i=0; i<5; i++) { + for (int j=0; j(edges.size() - 1)); + Pos pos = edges[edge]; + edges.erase(edges.begin() + edge); + + int color1 = 0; + int color2 = 0; + if (pos.x%2 == 0 && pos.y%2 == 1) { // Vertical + if (pos.x > 0) color1 = colorGrid[pos.x-1][pos.y]; + else color1 = 1; + + if (pos.x < p.width - 1) color2 = colorGrid[pos.x+1][pos.y]; + else color2 = 1; + } else { // Horizontal + assert(pos.x%2 == 1 && pos.y%2 == 0); + if (pos.y > 0) color1 = colorGrid[pos.x][pos.y-1]; + else color1 = 1; + + if (pos.y < p.height - 1) color2 = colorGrid[pos.x][pos.y+1]; + else color2 = 1; + } + // Enforce color1 < color2 + if (color1 > color2) std::swap(color1, color2); + + // Colors mismatch, valid cut + if (color1 != color2) { + // @Performance... have a lookup table instead? + for (int x=0; xWritePanelData(panel, POSITION, {x, y, 19.1f}); + auto solutions = Solver::Solve(copy); + assert(solutions.size() == 1); + p.sequence = solutions[0].sequence; + PuzzleSerializer(_memory).WritePuzzle(solutions[0], 0x139); +} - float z, w; +void Randomizer2::SetGate(int panel, int X, int Y) { + float x, y, z, w; if (X%2 == 0 && Y%2 == 1) { // Horizontal - z = -0.1f; - w = 1.0f; - } else if (X%2 == 1 && Y%2 == 0) { // Vertical + x = -1.49f * X + 0.22f * Y + 66.58f; + y = 0.275f * X + 1.6f * Y + 108.4f; z = -.77f; w = .63f; - } else { - assert(false); - return; + } else { // Vertical + assert(X%2 == 1 && Y%2 == 0); + x = -1.6f * X + 0.35f * Y + 66.5f; + y = 0.25f * X + 1.6f * Y + 108.55f; + z = -0.1f; + w = 1.0f; } + SetPos(panel, x, y, 19.2f); _memory->WritePanelData(panel, ORIENTATION, {0.0f, 0.0f, z, w}); +} + +void Randomizer2::SetPos(int panel, float x, float y, float z) { + _memory->WritePanelData(panel, POSITION, {x, y, z}); } \ No newline at end of file diff --git a/Source/Randomizer2.h b/Source/Randomizer2.h index 848fd22..359e357 100644 --- a/Source/Randomizer2.h +++ b/Source/Randomizer2.h @@ -10,6 +10,7 @@ public: private: void SetGate(int panel, int X, int Y); + void SetPos(int panel, float x, float y, float z); std::shared_ptr _memory; }; diff --git a/Source/Solver.cpp b/Source/Solver.cpp index bce1482..a8710a2 100644 --- a/Source/Solver.cpp +++ b/Source/Solver.cpp @@ -30,6 +30,7 @@ void Solver::SolveLoop(Puzzle& p, int x, int y, std::vector& solutions) if (p.sym == Puzzle::Symmetry::NONE) { if (cell.color != Cell::Color::NONE) return; // Collided with ourselves p.grid[x][y].color = Cell::Color::BLACK; // Otherwise, mark this cell as visited + p.sequence.emplace_back(Pos{x, y}); } else { /* // Get the symmetrical position, and try coloring it @@ -69,6 +70,7 @@ void Solver::SolveLoop(Puzzle& p, int x, int y, std::vector& solutions) // Tail recursion: Back out of this cell p.grid[x][y].color = Cell::Color::NONE; + p.sequence.pop_back(); if (p.sym != Puzzle::Symmetry::NONE) { /* auto sym = p.GetSymmetricalPos(x, y); -- cgit 1.4.1