//////////////////////////////////////////////////////////////////////////////////////// // Kara Jensen - mail@karajensen.com - pathfinding.h //////////////////////////////////////////////////////////////////////////////////////// #pragma once #include "global.h" #include <vector> class Player; /** * AStar Pathfinding for placing fences */ class PathFinding { public: typedef std::vector<int> SelectionList; /** * Constructor/Destructor */ PathFinding() = default; ~PathFinding() = default; /** * @return the list of selected indices for the chosen path */ const SelectionList& GetSelectionList() const { return m_selectionList; } /** * Clears the selection list and resets any associated * fences to their appropriate colours */ void ClearSelectionList(); /** * Generates a path from the start pole to the goal pole * @param startPoleID The id of the start node * @param goalPoleID The id of the end node * @param currentPlayer The targeted player */ bool GeneratePath(int startPoleID, int goalPoleID, Player* currentPlayer); private: /** * Prevent copying */ PathFinding& operator=(const PathFinding&) = delete; PathFinding(const PathFinding&) = delete; /** * Connection between each fence pole */ struct Edge { int ID = NO_INDEX; ///< ID of the connecting fence int nodeParentID = NO_INDEX; ///< ID of the parent pole int nodeChildID = NO_INDEX; ///< ID of the child pole }; typedef std::vector<Edge> EdgeList; /** * Fence pole on the grid */ struct Node { int ID = NO_INDEX; ///< ID of the pole Edge edgeFromParent; ///< edge from the parent to the node int costSoFar = 0; ///< cost of the path from start to this node int estimatedTotalCost = 0; ///< estimated total cost to the goal node }; typedef std::vector<Node> PathList; /** * Checks if the goal is possible to reach * @param goalID The id of the goal node * @return whether the goal node is reachable */ bool IsPathPossible(int goalID) const; /** * Adds the given edge to the selection list container * @param edge The edge to add * @param removeOnly Whether to remove the given edge if it exists already */ void AddEdgeToSelectionList(const Edge& edge, bool removeOnly); /** * Generates the outgoing edges given a pole * @param currentNode The node to generate edges from * @param edgesToProcess Container for the edges filled out by the call */ void CreateOutgoingEdges(const Node& currentNode, EdgeList& edgesToProcess); /** * Generates an estimate of the cost to reach the start pole to the end * Heuristic formula used is |Gy-Ny|+|Gx-Nx| * @param nodeID The id of the current node * @param goalID The id of the goal node * @return the cost estimate */ int CreateHeuristic(int nodeID, int goalID); SelectionList m_selectionList; ///< Final list of nodes for the generated path }; //////////////////////////////////////////////////////////////////////////////////////// // Kara Jensen - mail@karajensen.com - pathfinding.cpp //////////////////////////////////////////////////////////////////////////////////////// #include "pathfinding.h" #include "game.h" #include "player.h" #include <algorithm> namespace { const int EDGE_COST = -1; ///< Cost to traverse across an edge between poles const int LIST_RESERVE = 20; ///< Amount of space to reserve for the open/closed lists } int PathFinding::CreateHeuristic(int nodeID, int goalID) { //Heuristic formula used is |Gy-Ny|+|Gx-Nx| const auto& GamePoles = Game::Get()->GetPoles(); return abs(GamePoles[goalID].coordinate.y - GamePoles[nodeID].coordinate.y) + abs(GamePoles[goalID].coordinate.x - GamePoles[nodeID].coordinate.x); } bool PathFinding::GeneratePath(int startPoleID, int goalPoleID, Player* currentPlayer) { PathList openList; PathList closedList; openList.reserve(LIST_RESERVE); closedList.reserve(LIST_RESERVE); int nodeToFind = NO_INDEX; auto findPole = [&](const Node& node) -> bool { return node.ID == nodeToFind; }; auto sortFn = [&](const Node& p1, const Node& p2) -> bool { return p1.estimatedTotalCost < p2.estimatedTotalCost; }; //add start pole to the open list Node node; node.ID = startPoleID; node.estimatedTotalCost = CreateHeuristic(startPoleID, goalPoleID); openList.emplace_back(node); Node currentNode; while(!openList.empty()) { //get pole from the open list with the smallest total estimate cost currentNode = *openList.begin(); //check if pole found is the goal if(currentNode.ID == goalPoleID) { break; } //create a list of edges to process EdgeList edgesToProcess; CreateOutgoingEdges(currentNode, edgesToProcess); //for each valid edge going from the pole PathList::iterator childNode; for(unsigned int i = 0; i < edgesToProcess.size(); ++i) { //get the child/next pole the edge goes to nodeToFind = edgesToProcess[i].nodeChildID; int costUpToChild = currentNode.costSoFar + EDGE_COST; //check the status of the child pole childNode = std::find_if(closedList.begin(), closedList.end(), findPole); if(childNode != closedList.end()) { // In the closed list if(childNode->costSoFar > costUpToChild) { childNode->edgeFromParent = edgesToProcess[i]; childNode->estimatedTotalCost += costUpToChild - childNode->costSoFar; childNode->costSoFar = costUpToChild; openList.push_back(*childNode); closedList.erase(childNode); } } else { // In the open list childNode = std::find_if(openList.begin(), openList.end(), findPole); if(childNode != openList.end()) { if(childNode->costSoFar > costUpToChild) { childNode->edgeFromParent = edgesToProcess[i]; childNode->estimatedTotalCost += costUpToChild - childNode->costSoFar; childNode->costSoFar = costUpToChild; } } else //a new pole { //if the pole hasn't been visited before, fill in a new structure Node newPole; newPole.ID = nodeToFind; newPole.costSoFar = costUpToChild; newPole.estimatedTotalCost = CreateHeuristic(nodeToFind, goalPoleID) + costUpToChild; newPole.edgeFromParent = edgesToProcess[i]; openList.emplace_back(newPole); } } } closedList.push_back(currentNode); openList.erase(openList.begin()); std::sort(openList.begin(), openList.end(), sortFn); } // ensure final pole is the goal if(currentNode.ID == goalPoleID) { // estimate the total cost of the path and whether path is possible unsigned int fencesSelected = m_selectionList.size(); Node gamePole = currentNode; while((gamePole.ID != startPoleID) && (gamePole.edgeFromParent.ID != NO_INDEX)) { ++fencesSelected; nodeToFind = gamePole.edgeFromParent.nodeParentID; gamePole = *std::find_if(closedList.begin(), closedList.end(), findPole); } int totalCost = currentPlayer->GenerateFenceCost(fencesSelected); int totalInvertory = static_cast<int>(currentPlayer->GetTotalLumberInInvertory()); bool removeOnly = (totalInvertory-totalCost < 0); //iterate over chosen fences while((currentNode.ID != startPoleID) && (currentNode.edgeFromParent.ID != NO_INDEX)) { //add/remove the fence in the selection list AddEdgeToSelectionList(currentNode.edgeFromParent, removeOnly); //traverse to parent pole nodeToFind = currentNode.edgeFromParent.nodeParentID; currentNode = *std::find_if(closedList.begin(), closedList.end(), findPole); } //get the final cost for the turn currentPlayer->SetCurrentFenceCost(currentPlayer->GenerateFenceCost(m_selectionList.size())); } return true; } void PathFinding::CreateOutgoingEdges(const Node& currentNode, EdgeList& edgesToProcess) { const auto& fences = Game::Get()->GetFences(); const auto& poles = Game::Get()->GetPoles(); const Pole& pole = poles[currentNode.ID]; auto createEdgeFn = [&](int fenceIndex, int x, int y) { if(fenceIndex != NO_INDEX && fenceIndex != currentNode.edgeFromParent.ID) { const auto& fence = fences[fenceIndex]; if(!fence.active) { //get index of child pole int poleIndex = GetIndex(static_cast<int>(Pole::NumberOfColumns), pole.coordinate.y+y, pole.coordinate.x+x); if(poleIndex >= 0 && poleIndex < static_cast<int>(poles.size())) { //create new edge connecting current node/child Edge newEdge; newEdge.ID = fenceIndex; newEdge.nodeParentID = pole.containerID; newEdge.nodeChildID = poles[poleIndex].containerID; edgesToProcess.emplace_back(newEdge); } } } }; createEdgeFn(pole.backFenceIndex, 0, -1); createEdgeFn(pole.forwardFenceIndex, 0, 1); createEdgeFn(pole.rightFenceIndex, 1, 0); createEdgeFn(pole.leftFenceIndex, -1, 0); } bool PathFinding::IsPathPossible(int goalID) const { const auto& fences = Game::Get()->GetFences(); const auto& poles = Game::Get()->GetPoles(); int surroundCounter = 0; if(poles[goalID].backFenceIndex == NO_INDEX) surroundCounter++; else if(fences[poles[goalID].backFenceIndex].active) surroundCounter++; if(poles[goalID].rightFenceIndex == NO_INDEX) surroundCounter++; else if(fences[poles[goalID].rightFenceIndex].active) surroundCounter++; if(poles[goalID].leftFenceIndex == NO_INDEX) surroundCounter++; else if(fences[poles[goalID].leftFenceIndex].active) surroundCounter++; if(poles[goalID].forwardFenceIndex == NO_INDEX) surroundCounter++; else if(fences[poles[goalID].forwardFenceIndex].active) surroundCounter++; return surroundCounter >= 4; } void PathFinding::AddEdgeToSelectionList(const Edge& edge, bool removeOnly) { auto& fences = Game::Get()->GetFences(); fences[edge.ID].drawSelected = false; //if already added, remove from list auto removeFn = [&](const int id) -> bool { return id == edge.ID; }; m_selectionList.erase(std::remove_if(m_selectionList.begin(), m_selectionList.end(), removeFn), m_selectionList.end()); //not in list, add to list if(!removeOnly) { fences[edge.ID].drawSelected = true; m_selectionList.push_back(edge.ID); } } void PathFinding::ClearSelectionList() { auto& fences = Game::Get()->GetFences(); for(unsigned int i = 0; i < m_selectionList.size(); ++i) { fences[m_selectionList[i]].drawSelected = false; } m_selectionList.clear(); }