From kde-commits Wed Apr 01 17:42:13 2015 From: Minh Ngo Date: Wed, 01 Apr 2015 17:42:13 +0000 To: kde-commits Subject: [kdots] /: Decision Tree into the separate class. AI is more Message-Id: X-MARC-Message: https://marc.info/?l=kde-commits&m=142791014406517 Git commit 549d14f092274b8116de15a4146b2ae9eb28501b by Minh Ngo. Committed on 01/04/2015 at 17:41. Pushed by minhngo into branch 'master'. Decision Tree into the separate class. AI is more advanced now. M +1 -1 CMakeLists.txt M +2 -0 plugins/simpleai/CMakeLists.txt A +301 -0 plugins/simpleai/decisiontree.cpp [License: BSD] C +54 -22 plugins/simpleai/decisiontree.hpp [from: polygonfinder.hpp -= 050% similarity] M +17 -234 plugins/simpleai/rival.cpp M +0 -18 plugins/simpleai/rival.hpp M +11 -2 polygonfinder.cpp M +3 -3 polygonfinder.hpp http://commits.kde.org/kdots/549d14f092274b8116de15a4146b2ae9eb28501b diff --git a/CMakeLists.txt b/CMakeLists.txt index 0fb03a9..c02d239 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -118,7 +118,7 @@ KDE4_ADD_UI_FILES(SRCS ${FORMS}) KDE4_ADD_KCFG_FILES(SRCS kdots.kcfgc) INSTALL(FILES kdots.kcfg DESTINATION ${KCFG_INSTALL_DIR}) = -SET(KDOTS_VERSION "0.5.2") +SET(KDOTS_VERSION "0.5.3") SET(KDOTS_SOVERSION "1") = CONFIGURE_FILE(config.hpp.in config.hpp) diff --git a/plugins/simpleai/CMakeLists.txt b/plugins/simpleai/CMakeLists.= txt index bf7510d..9ec1125 100644 --- a/plugins/simpleai/CMakeLists.txt +++ b/plugins/simpleai/CMakeLists.txt @@ -18,12 +18,14 @@ SET(SIMPLEAI_HEADERS prioritymap.hpp rival.hpp plugin.hpp + decisiontree.hpp ) = SET(SIMPLEAI_SRCS prioritymap.cpp rival.cpp plugin.cpp + decisiontree.cpp ) = kde4_add_plugin(kdots_simpleai SHARED diff --git a/plugins/simpleai/decisiontree.cpp b/plugins/simpleai/decisiont= ree.cpp new file mode 100644 index 0000000..0164b67 --- /dev/null +++ b/plugins/simpleai/decisiontree.cpp @@ -0,0 +1,301 @@ +/* + * KDots + * Copyright (c) 2011, 2012, 2014, 2015 Minh Ngo + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTI= ES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES(INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF US= E, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +#include "decisiontree.hpp" + +#include +#include +#include + +#include + +#include + +namespace KDots +{ +namespace simpleai +{ + NodeInfo::NodeInfo() + : m_parent(-1) + , m_layer(0) + , m_bestChildGrade(0) + , m_capturedPointsCount(0) + , m_point{-1, -1} + { + } + = + DecisionTree::DecisionTree(const Graph& graph, const QRect& bbox, + int numPointsOnBoard, int depth, Owner ai) + : m_graph(graph) + , m_bbox(bbox) + , m_numPointsOnBoard(numPointsOnBoard) + , m_maxNumPoints(graph.width() * graph.height()) + , m_depth(depth) + , m_ai(ai) + { + kDebug() << "Bounding box:" << bbox.width() << bbox.height(); + } + = + void DecisionTree::calculateDecisions(std::vector& points, Vector= F& grades) + { + m_nodes =3D {NodeInfo()}; + = + // For DFS + std::stack tasks; + tasks.push(0); + = + while (!tasks.empty()) + { + const int parentNodeID =3D tasks.top(); + tasks.pop(); + + TPreviousPoints previousPoints; + + findPreviousPoints(parentNodeID, previousPoints); + + std::vector allowedPoints(m_bbox.width(), VectorB(m_bbox.he= ight(), false)); + buildAllowedPointsMap(previousPoints, allowedPoints); + + const std::size_t layerStart =3D m_nodes.size(); + = + const int parentLayer =3D m_nodes[parentNodeID].m_layer; + const int currentLayer =3D parentLayer + 1; + const bool isHumanLayer =3D parentLayer % 2 =3D=3D 1; + = + const Owner layerOwner =3D isHumanLayer ? StepQueue::other(m_ai) : m= _ai; + = + const std::vector& ownerPrevPoints =3D isHumanLayer + ? previousPoints.m_human + : previousPoints.m_ai; + = + for (int x =3D 0; x < m_bbox.width(); ++x) + { + for (int y =3D 0; y < m_bbox.height(); ++y) + { + if (!allowedPoints[x][y]) + continue; + + m_nodes.emplace_back(); + + NodeInfo& newNode =3D m_nodes[m_nodes.size() - 1]; + newNode.m_layer =3D currentLayer; + newNode.m_parent =3D parentNodeID; + newNode.m_bestChildGrade =3D 0; + + const Point point(x + m_bbox.left(), y + m_bbox.top()); + newNode.m_point =3D point; + + PolygonFinder finder(m_graph, layerOwner, ownerPrevPoints); + + const PolyList& polygons =3D finder(point); + = + newNode.m_capturedPointsCount =3D findCapturedPoints(previousPoi= nts, + layerOwner, + polygons); + + NodeInfo& parentNode =3D m_nodes[parentNodeID]; + // If it's a human layer we choose the worse case + if (parentNode.m_bestChildGrade > newNode.m_capturedPointsCount) + m_nodes.pop_back(); + else + parentNode.m_bestChildGrade =3D newNode.m_capturedPointsCount; + } + } + + // Not found any elements for this layer + if (layerStart =3D=3D m_nodes.size()) + continue; + + // Invert grades for human layers + if (isHumanLayer) + m_nodes[parentNodeID].m_bestChildGrade *=3D -1; + + m_leafs.reserve(m_leafs.size() + m_nodes.size() - layerStart); + = + // Last layer + if (currentLayer =3D=3D m_depth || (m_numPointsOnBoard + currentLaye= r =3D=3D m_maxNumPoints)) + { + for (std::size_t i =3D layerStart; i < m_nodes.size(); ++i) + m_leafs.push_back(i); + = + continue; + } + + for (std::size_t i =3D layerStart; i < m_nodes.size(); ++i) + { + if (m_nodes[i].m_capturedPointsCount =3D=3D 0) + tasks.push(i); + else + m_leafs.push_back(i); + } + } + = + // Update all weights starting from leafs + = + int bestGrade =3D 0; + int prevParentID =3D -1; + for (const int id : m_leafs) + { + const NodeInfo& node =3D m_nodes[id]; + if (node.m_parent !=3D prevParentID) + { + if (prevParentID !=3D -1) + m_nodes[prevParentID].m_bestChildGrade +=3D bestGrade; + + bestGrade =3D node.m_bestChildGrade; + prevParentID =3D node.m_parent; + continue; + } + + if (prevParentID % 2 =3D=3D 0) // Current is max/ai layer + { + if (bestGrade < node.m_bestChildGrade) + bestGrade =3D node.m_bestChildGrade; + } + else // Current is min/human layer + { + if (bestGrade > node.m_bestChildGrade) + bestGrade =3D node.m_bestChildGrade; + } + } + + kDebug() << "Decision Tree Final Size:" << m_nodes.size(); + + // Decisions are positioned in the first layer + // TODO: reserve + for (int i =3D 1; m_nodes[i].m_parent =3D=3D 0; ++i) + { + points.push_back(m_nodes[i].m_point); + grades.push_back(m_nodes[i].m_bestChildGrade); + } + } + = + void DecisionTree::findPreviousPoints(int lastPointID, + TPreviousPoints& previousPoints) c= onst + { + const NodeInfo *lastNode =3D &m_nodes[lastPointID]; + = + while(lastNode->m_point.m_x !=3D -1) + { + if (lastNode->m_layer % 2 =3D=3D 1) + previousPoints.m_ai.push_back(lastNode->m_point); + else + previousPoints.m_human.push_back(lastNode->m_point); + = + lastNode =3D &m_nodes[lastNode->m_parent]; + } + } + = + namespace + { + bool isNotIn(const std::vector& v, const Point& point) + { + for (const Point& p : v) + if (p =3D=3D point) + return false; + = + return true; + } + } + = + int DecisionTree::findCapturedPoints(const TPreviousPoints& previousPoin= ts, + Owner currentOwner, + const PolyList& polygons) const + { + if (polygons.empty()) + return 0; + = + int numPoints =3D 0; + = + const std::vector& opponentPrevPoints =3D currentOwner =3D=3D m= _ai + ? previousPoints.m_human + : previousPoints.m_ai; + + for (int x =3D m_bbox.left(); x <=3D m_bbox.right(); ++x) + { + for (int y =3D m_bbox.top(); y <=3D m_bbox.bottom(); ++y) + { + const Point point(x, y); + = + // We can capture only noncaptured points + if (m_graph[point].isCaptured()) + continue; + = + const Owner pointOwner =3D m_graph[point].owner(); + = + // We can capture only oponent's points + if (pointOwner =3D=3D currentOwner) + continue; + = + if (pointOwner =3D=3D Owner::NONE && isNotIn(opponentPrevPoints, p= oint)) + continue; + = + for (const Polygon_ptr& polygon : polygons) + { + if (polygon->contains(point)) + { + ++numPoints; + break; + } + } + } + } + = + return numPoints; + } + = + namespace + { + bool isNotPreviousPoint(const TPreviousPoints& previousPoints, const P= oint& point) + { + for (const Point& pai : previousPoints.m_ai) + if (pai =3D=3D point) + return false; + = + for (const Point& phuman : previousPoints.m_human) + if (phuman =3D=3D point) + return false; + = + return true; + } + } + = + void DecisionTree::buildAllowedPointsMap(const TPreviousPoints& previous= Points, + std::vector& allowedPo= ints) const + { + for (int x =3D 0; x < m_bbox.width(); ++x) + { + for (int y =3D 0; y < m_bbox.height(); ++y) + { + const Point point(x + m_bbox.left(), y + m_bbox.top()); + = + allowedPoints[x][y] =3D isNotPreviousPoint(previousPoints, point) + && m_graph[point].owner() =3D=3D Owner::NONE + && !m_graph[point].isCaptured(); + } + } + } +} +} \ No newline at end of file diff --git a/polygonfinder.hpp b/plugins/simpleai/decisiontree.hpp similarity index 50% copy from polygonfinder.hpp copy to plugins/simpleai/decisiontree.hpp index 79e67f2..395ba24 100644 --- a/polygonfinder.hpp +++ b/plugins/simpleai/decisiontree.hpp @@ -24,36 +24,68 @@ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #pragma once -#include -#include -#include -#include "polygon.hpp" -#include "constants.hpp" +#include +#include +#include + +class QRect; = namespace KDots { - struct Graph; +class Graph; +namespace simpleai +{ + struct NodeInfo + { + NodeInfo(); + = + int m_parent; // Index from the vector + int m_layer; + int m_bestChildGrade; + int m_capturedPointsCount; = - class KDOTS_EXPORT PolygonFinder final + Point m_point; + }; + = + struct TPreviousPoints + { + std::vector m_ai; + std::vector m_human; + }; + = + typedef std::vector VectorF; + = + class DecisionTree { public: - PolygonFinder(const Graph& graph, Owner owner, - const std::unordered_set& additionalPoints =3D st= d::unordered_set()); - - // O(n) - const PolyList& operator()(const Point& point); - + DecisionTree(const Graph& graph, const QRect& bbox, + int numPointsOnBoard, int depth, Owner ai); + = + void calculateDecisions(std::vector& points, VectorF& grades); + = private: - void findPolygons(const Point& point); - + void findPreviousPoints(int lastPointID, + TPreviousPoints& previousPoints) const; + = + int findCapturedPoints(const TPreviousPoints& previousPoints, + Owner current, + const PolyList& polygons) const; + = + typedef std::vector VectorB; + // Returns allowed points to place (not to capture) + void buildAllowedPointsMap(const TPreviousPoints& previousPoints, + std::vector& allowedPoints) const; + = private: const Graph& m_graph; - Owner m_current; - std::vector> m_stepMap; - const std::unordered_set m_additionalPoints; - - std::vector m_cache; - PolyList m_polygons; - Point m_first; + const QRect& m_bbox; + const int m_numPointsOnBoard; + const int m_maxNumPoints; + const int m_depth; + Owner m_ai; + = + std::vector m_nodes; + std::vector m_leafs; }; +} } \ No newline at end of file diff --git a/plugins/simpleai/rival.cpp b/plugins/simpleai/rival.cpp index 6400204..700ff29 100644 --- a/plugins/simpleai/rival.cpp +++ b/plugins/simpleai/rival.cpp @@ -25,6 +25,7 @@ */ #include "rival.hpp" #include "prioritymap.hpp" +#include "decisiontree.hpp" = #include #include @@ -34,6 +35,7 @@ #include = #include +#include = #include #include @@ -46,8 +48,8 @@ namespace KDots { const std::map DIFFICULTY_TO_= DEPTH =3D { {KgDifficultyLevel::Easy, 2}, - {KgDifficultyLevel::Medium, 4}, - {KgDifficultyLevel::Hard, 6} + {KgDifficultyLevel::Medium, 3}, + {KgDifficultyLevel::Hard, 4} }; } = @@ -153,11 +155,9 @@ namespace KDots return maxPriority; }; = - kDebug() << "BB size:" << bb.width() << bb.height(); std::vector importanceMatrix(bb.width(), VectorF(bb.height(= ))); = const QPoint& offsetPoint =3D bb.topLeft(); - kDebug() << "Offset:" << offsetPoint; for (int x =3D 0; x < bb.width(); ++x) { for (int y =3D 0; y < bb.height(); ++y) @@ -165,12 +165,7 @@ namespace KDots if (graph[x + offsetPoint.x()][y + offsetPoint.y()].owner() !=3D= Owner::NONE) importanceMatrix[x][y] =3D -std::numeric_limits::infini= ty(); else - { importanceMatrix[x][y] =3D cellPriority({offsetPoint.x() + x, = offsetPoint.y() + y}); - kDebug() << "(" << (offsetPoint.x() + x) - << "," << (offsetPoint.y() + y) - << ")" << importanceMatrix[x][y]; - } } } = @@ -216,78 +211,6 @@ namespace KDots return QRect(QPoint(min_x, min_y), QPoint(max_x, max_y)); } = - void Rival::findCapturedPoints(const QRect& bbox, - const std::vector& allowedPoin= ts, - const PolyList& polygons, - std::unordered_set& capturedPoin= ts) const - { - if (polygons.empty()) - return; - - for (int x =3D bbox.left(); x <=3D bbox.right(); ++x) - { - for (int y =3D bbox.top(); y <=3D bbox.bottom(); ++y) - { - if (!allowedPoints[x - bbox.left()][y - bbox.top()]) - continue; - - const Point point(x, y); - for (const Polygon_ptr& polygon : polygons) - { - if (polygon->contains(point)) - { - capturedPoints.insert(point); - break; - } - } - } - } - } - - struct NodeInfo - { - int m_parent; // Index from the vector - int m_layer; - int m_bestChildGrade; - int m_capturedPointsCount; - - Point m_point; - std::unordered_set m_capturedPoints; - }; - - void Rival::findPreviousPoints(const std::vector& decisionTr= ee, - int lastPointID, - std::unordered_set& previousPoin= ts, - std::unordered_set& capturedPoin= ts) const - { - const NodeInfo *lastNode =3D &decisionTree[lastPointID]; - //kDebug() << "Last node: {" << lastNode->m_point.m_x << "," << last= Node->m_point.m_y << "}"; - while (lastNode->m_point.m_x !=3D -1) - { - previousPoints.insert(lastNode->m_point); - const std::unordered_set& lastCapturedPoints =3D lastNode->= m_capturedPoints; - capturedPoints.insert(lastCapturedPoints.begin(), lastCapturedPoin= ts.end()); - lastNode =3D &decisionTree[lastNode->m_parent]; - } - } - - void Rival::buildAllowedPointsMap(const QRect& bbox, - const std::unordered_set& pre= viousPoints, - std::vector& allowedPoints)= const - { - const Graph& graph =3D m_board->graph(); - for (int x =3D 0; x < bbox.width(); ++x) - { - for (int y =3D 0; y < bbox.height(); ++y) - { - const Point point(x + bbox.left(), y + bbox.top()); - allowedPoints[x][y] =3D !previousPoints.count(point) - && graph[point].owner() =3D=3D Owner::NONE - && !graph[point].isCaptured(); - } - } - } - void Rival::addPoint(bool random) { if (random) @@ -298,150 +221,30 @@ namespace KDots = const QRect bbox(getBoundingBox()); = - // For other elements importance is 0 - const auto importanceMatrix(getImportanceMatrix(bbox)); - - std::vector decisionTree(1); - - { - NodeInfo& baseNode =3D decisionTree.back(); - baseNode.m_parent =3D -1; - baseNode.m_bestChildGrade =3D 0; - baseNode.m_layer =3D 0; - - baseNode.m_capturedPointsCount =3D 0; - - baseNode.m_point =3D {-1, -1}; - } - - std::stack tasks; - tasks.push(0); - const Graph& graph =3D m_board->graph(); - - const int begin =3D time(0); - while (!tasks.empty()) - { - const int parentNodeID =3D tasks.top(); - tasks.pop(); - - std::unordered_set previousPoints; - std::unordered_set capturedPoints; - - findPreviousPoints(decisionTree, parentNodeID, - previousPoints, capturedPoints); - - std::vector allowedPoints(bbox.width(), VectorB(bbox.heig= ht(), false)); - buildAllowedPointsMap(bbox, previousPoints, allowedPoints); - - const std::size_t layerStart =3D decisionTree.size(); - - for (int x =3D 0; x < bbox.width(); ++x) - { - for (int y =3D 0; y < bbox.height(); ++y) - { - if (!allowedPoints[x][y]) - continue; - - decisionTree.emplace_back(); - - const int newNodeID =3D decisionTree.size() - 1; - NodeInfo& newNode =3D decisionTree[newNodeID]; - NodeInfo& parentNode =3D decisionTree[parentNodeID]; - - newNode.m_layer =3D parentNode.m_layer + 1; - newNode.m_parent =3D parentNodeID; - newNode.m_bestChildGrade =3D 0; - - const Point point(x + bbox.left(), y + bbox.top()); - newNode.m_point =3D point; - - PolygonFinder finder(graph, - parentNode.m_layer % 2 =3D=3D 0 ? m_ai : = m_human, - previousPoints); - - const PolyList& polygons =3D finder(point); - - findCapturedPoints(bbox, - allowedPoints, - polygons, - newNode.m_capturedPoints); - - newNode.m_capturedPointsCount =3D newNode.m_capturedPoints.siz= e(); - if (parentNode.m_bestChildGrade > newNode.m_capturedPointsCoun= t) - decisionTree.pop_back(); - else - parentNode.m_bestChildGrade =3D newNode.m_capturedPointsCoun= t; - } - } - - if (layerStart =3D=3D decisionTree.size()) - continue; - - NodeInfo& parentNode =3D decisionTree[parentNodeID]; - - if (parentNode.m_layer % 2 =3D=3D 1) // Human layer - // Invert grades for human layers - decisionTree[parentNodeID].m_bestChildGrade *=3D -1; - - // Last layer - if (parentNode.m_layer + 1 =3D=3D m_depth) - continue; - - for (std::size_t i =3D layerStart; i < decisionTree.size(); ++i) - { - if (decisionTree[i].m_capturedPointsCount =3D=3D parentNode.m_be= stChildGrade) - tasks.push(i); - } - } - - int bestGrade =3D 0; - int prevParentID =3D -1; - for (auto it =3D decisionTree.rbegin(), end =3D --decisionTree.rend(= ); it !=3D end; ++it) - { - if (it->m_parent !=3D prevParentID) - { - if (prevParentID !=3D -1) - decisionTree[prevParentID].m_bestChildGrade +=3D bestGrade; - - bestGrade =3D it->m_bestChildGrade; - prevParentID =3D it->m_parent; - continue; - } - - if (prevParentID % 2 =3D=3D 0) // Current is max/ai layer - { - if (bestGrade < it->m_bestChildGrade) - bestGrade =3D it->m_bestChildGrade; - } - else // Current is min/human layer - { - if (bestGrade > it->m_bestChildGrade) - bestGrade =3D it->m_bestChildGrade; - } - } - - kDebug() << "Best grade (Decision tree): " << bestGrade; - kDebug() << "Decision Tree Final Size:" << decisionTree.size(); - + = + const int pointsOnBoard =3D m_board->stepQueue().getAllPoints().size= (); + = + DecisionTree tree(graph, bbox, pointsOnBoard, m_depth, m_ai); + = std::vector decisions; std::vector decisionGrades; - for (int i =3D 1; decisionTree[i].m_parent =3D=3D 0; ++i) + = { - decisions.push_back(decisionTree[i].m_point); - decisionGrades.push_back(decisionTree[i].m_bestChildGrade * m_k2); - kDebug() << decisionTree[i].m_point.m_x << ", " << decisionTree[i]= .m_point.m_y - << ":" << decisionTree[i].m_bestChildGrade * m_k2; + const int begin =3D std::time(0); + tree.calculateDecisions(decisions, decisionGrades); + kDebug() << "Decision making time:" << (std::time(0) - begin); } - + = kDebug() << "Number of decisions founded:" << decisions.size(); = if (!decisions.empty()) { + const auto importanceMatrix(getImportanceMatrix(bbox)); for (std::size_t i =3D 0; i < decisions.size(); ++i) { const Point& p =3D decisions[i]; - + decisionGrades[i] *=3D m_k2; decisionGrades[i] +=3D m_k1 * importanceMatrix[p.m_x - bbox.left= ()][p.m_y - bbox.top()]; } = @@ -449,28 +252,8 @@ namespace KDots std::max_element(decisionGrades.= begin(), decisionGrades.e= nd())); emit needAddPoint(decisions[pointID]); - - kDebug() << "Decision making time:" << (time(0) - begin); - } - else // Last points, doesn't matter a lot so :) - { - kDebug() << "Empty decisions"; - kDebug() << bbox.left() << bbox.right(); - kDebug() << bbox.top() << bbox.bottom(); - for (int x =3D bbox.left(); x <=3D bbox.right(); ++x) - { - for (int y =3D bbox.top(); y <=3D bbox.bottom(); ++y) - { - const Point point(x, y); - if (graph[point].owner() =3D=3D Owner::NONE && !graph[point].i= sCaptured()) - { - kDebug() << "Add point:" << point.m_x << point.m_y; - emit needAddPoint(point); - return; - } - } - } } + // Else -> End of the game } = void Rival::setBoardModel(BoardModel *board) diff --git a/plugins/simpleai/rival.hpp b/plugins/simpleai/rival.hpp index 9fa2d6a..7c85b77 100644 --- a/plugins/simpleai/rival.hpp +++ b/plugins/simpleai/rival.hpp @@ -28,7 +28,6 @@ = #include = -#include #include = namespace KDots @@ -60,26 +59,9 @@ namespace KDots QRect getBoundingBox() const; = typedef std::vector VectorF; - typedef std::vector VectorB; // Complexity O(n) std::vector getImportanceMatrix(const QRect& bb) const; = - void buildAllowedPointsMap(const QRect& bbox, - const std::unordered_set& previous= Points, - std::vector& allowedPoints) cons= t; - - // Complexity O(n) - void findCapturedPoints(const QRect& bbox, - const std::vector& allowerdPoints, - const PolyList& polygons, - std::unordered_set& capturedPoints) c= onst; - - // Complexity O(1) - void findPreviousPoints(const std::vector& decisionTree, - int lastPointID, - std::unordered_set& previousPoints, - std::unordered_set& capturedPoints) c= onst; - signals: void needCreateBoard(const GameConfig& config); void needDestroy(); diff --git a/polygonfinder.cpp b/polygonfinder.cpp index 7ab766c..5a14262 100644 --- a/polygonfinder.cpp +++ b/polygonfinder.cpp @@ -32,7 +32,7 @@ namespace KDots { PolygonFinder::PolygonFinder(const Graph& graph, Owner owner, - const std::unordered_set& additional= Points) + const std::vector& additionalPoints) : m_graph(graph) , m_current(owner) , m_stepMap(graph.width(), std::vector(graph.height(), false)) @@ -72,6 +72,15 @@ namespace KDots = return m_polygons; } + = + bool PolygonFinder::isAdditionalPoint(const Point& point) const + { + for (const Point& pi : m_additionalPoints) + if (pi =3D=3D point) + return true; + = + return false; + } = namespace { @@ -110,7 +119,7 @@ namespace KDots = const GraphPoint& graphPoint =3D m_graph[newPoint]; = - if (!m_additionalPoints.count(newPoint) && newPoint !=3D m_first + if (!isAdditionalPoint(newPoint) && newPoint !=3D m_first && (graphPoint.isCaptured() || graphPoint.owner() !=3D m_current= )) continue; = diff --git a/polygonfinder.hpp b/polygonfinder.hpp index 79e67f2..3af8266 100644 --- a/polygonfinder.hpp +++ b/polygonfinder.hpp @@ -33,24 +33,24 @@ namespace KDots { struct Graph; - class KDOTS_EXPORT PolygonFinder final { public: PolygonFinder(const Graph& graph, Owner owner, - const std::unordered_set& additionalPoints =3D st= d::unordered_set()); + const std::vector& additionalPoints =3D {}); = // O(n) const PolyList& operator()(const Point& point); = private: void findPolygons(const Point& point); + bool isAdditionalPoint(const Point& point) const; = private: const Graph& m_graph; Owner m_current; std::vector> m_stepMap; - const std::unordered_set m_additionalPoints; + const std::vector& m_additionalPoints; = std::vector m_cache; PolyList m_polygons;