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