1 /* 2 * This file is part of Dune Legacy. 3 * 4 * Dune Legacy is free software: you can redistribute it and/or modify 5 * it under the terms of the GNU General Public License as published by 6 * the Free Software Foundation, either version 2 of the License, or 7 * (at your option) any later version. 8 * 9 * Dune Legacy is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * GNU General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public License 15 * along with Dune Legacy. If not, see <http://www.gnu.org/licenses/>. 16 */ 17 18 #ifndef ASTARSEARCH_H 19 #define ASTARSEARCH_H 20 21 #include <DataTypes.h> 22 #include <fixmath/FixPoint.h> 23 24 #include <list> 25 #include <vector> 26 27 class UnitBase; 28 class Map; 29 30 class AStarSearch { 31 public: 32 AStarSearch(Map* pMap, UnitBase* pUnit, Coord start, Coord destination); 33 ~AStarSearch(); 34 getFoundPath()35 std::list<Coord> getFoundPath() { 36 std::list<Coord> path; 37 38 if(bestCoord.isInvalid()) { 39 return path; 40 } 41 42 Coord currentCoord = bestCoord; 43 while(true) { 44 Coord nextCoord = getMapData(currentCoord).parentCoord; 45 46 if(nextCoord.isInvalid()) { 47 break; 48 } 49 50 path.push_front(currentCoord); 51 currentCoord = nextCoord; 52 } 53 54 return path; 55 }; 56 57 private: 58 struct TileData { 59 Coord parentCoord; 60 size_t openListIndex; 61 FixPoint g; 62 FixPoint h; 63 FixPoint f; 64 bool bInOpenList; 65 bool bClosed; 66 }; 67 68 getMapData(const Coord & coord)69 inline TileData& getMapData(const Coord& coord) const { return mapData[coord.y * sizeX + coord.x]; }; 70 trickleUp(size_t openListIndex)71 void trickleUp(size_t openListIndex) { 72 Coord bottom = openList[openListIndex]; 73 FixPoint newf = getMapData(bottom).f; 74 75 size_t current = openListIndex; 76 size_t parent = (openListIndex - 1)/2; 77 while (current > 0 && getMapData(openList[parent]).f > newf) { 78 79 // copy parent to position of current 80 openList[current] = openList[parent]; 81 getMapData(openList[current]).openListIndex = current; 82 83 // go up one level in the tree 84 current = parent; 85 parent = (parent - 1)/2; 86 } 87 88 openList[current] = bottom; 89 getMapData(openList[current]).openListIndex = current; 90 }; 91 putOnOpenListIfBetter(const Coord & coord,const Coord & parentCoord,FixPoint g,FixPoint h)92 void putOnOpenListIfBetter(const Coord& coord, const Coord& parentCoord, FixPoint g, FixPoint h) { 93 FixPoint f = g + h; 94 95 if(getMapData(coord).bInOpenList == false) { 96 // not yet in openlist => add at the end of the open list 97 getMapData(coord).g = g; 98 getMapData(coord).h = h; 99 getMapData(coord).f = f; 100 getMapData(coord).parentCoord = parentCoord; 101 getMapData(coord).bInOpenList = true; 102 openList.push_back(coord); 103 getMapData(coord).openListIndex = openList.size() - 1; 104 105 trickleUp(openList.size() - 1); 106 } else { 107 // already on openlist 108 if(f >= getMapData(coord).f) { 109 // new item is worse => don't change anything 110 return; 111 } else { 112 // new item is better => replace 113 getMapData(coord).g = g; 114 getMapData(coord).h = h; 115 getMapData(coord).f = f; 116 getMapData(coord).parentCoord = parentCoord; 117 trickleUp(getMapData(coord).openListIndex); 118 } 119 } 120 }; 121 extractMin()122 Coord extractMin() { 123 Coord ret = openList[0]; 124 getMapData(ret).bInOpenList = false; 125 126 openList[0] = openList.back(); 127 getMapData(openList[0]).openListIndex = 0; 128 openList.pop_back(); 129 130 size_t current = 0; 131 Coord top = openList[current]; // save root 132 FixPoint topf = getMapData(top).f; 133 while(current < openList.size()/2) { 134 135 size_t leftChild = 2*current+1; 136 size_t rightChild = leftChild+1; 137 138 // find smaller child 139 size_t smallerChild; 140 FixPoint smallerChildf; 141 if(rightChild < openList.size()) { 142 FixPoint leftf = getMapData(openList[leftChild]).f; 143 FixPoint rightf = getMapData(openList[rightChild]).f; 144 145 if(leftf < rightf) { 146 smallerChild = leftChild; 147 smallerChildf = leftf; 148 } else { 149 smallerChild = rightChild; 150 smallerChildf = rightf; 151 } 152 } else { 153 // there is only a left child 154 smallerChild = leftChild; 155 smallerChildf = getMapData(openList[leftChild]).f; 156 } 157 158 // top >= largerChild? 159 if(topf <= smallerChildf) 160 break; 161 162 // shift child up 163 openList[current] = openList[smallerChild]; 164 getMapData(openList[current]).openListIndex = current; 165 166 // go down one level in the tree 167 current = smallerChild; 168 } 169 170 openList[current] = top; 171 getMapData(openList[current]).openListIndex = current; 172 173 return ret; 174 }; 175 176 int sizeX; 177 int sizeY; 178 Coord bestCoord; 179 TileData* mapData; 180 std::vector<Coord> openList; 181 }; 182 183 #endif //ASTARSEARCH_H 184