1 // Copyright (C) 2000, 2001, 2002, 2003 Michael Bartl
2 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 Ulf Lorenz
3 // Copyright (C) 2004, 2005, 2006 Andrea Paternesi
4 // Copyright (C) 2004 John Farrell
5 // Copyright (C) 2006, 2007, 2008, 2009, 2010, 2014, 2015 Ben Asselstine
6 // Copyright (C) 2008 Ole Laursen
7 //
8 // This program is free software; you can redistribute it and/or modify
9 // it under the terms of the GNU General Public License as published by
10 // the Free Software Foundation; either version 3 of the License, or
11 // (at your option) any later version.
12 //
13 // This program is distributed in the hope that it will be useful,
14 // but WITHOUT ANY WARRANTY; without even the implied warranty of
15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 // GNU Library General Public License for more details.
17 //
18 // You should have received a copy of the GNU General Public License
19 // along with this program; if not, write to the Free Software
20 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
21 // 02110-1301, USA.
22
23 #include <assert.h>
24 #include <sstream>
25 #include <queue>
26
27 #include "PathCalculator.h"
28 #include "path.h"
29 #include "army.h"
30 #include "GameMap.h"
31 #include "city.h"
32 #include "stacklist.h"
33 #include "xmlhelper.h"
34 #include "stack.h"
35 #include "player.h"
36
37 Glib::ustring Path::d_tag = "path";
38
39 //#define debug(x) {std::cerr<<__FILE__<<": "<<__LINE__<<": "<<x<<std::endl<<std::flush;}
40 #define debug(x)
41
Path()42 Path::Path()
43 : std::list<Vector<int> > ()
44 {
45 clear();
46 d_moves_exhausted_at_point = 0;
47 }
48
Path(const Path & p)49 Path::Path(const Path& p)
50 : std::list<Vector<int> >(),
51 d_moves_exhausted_at_point(p.d_moves_exhausted_at_point)
52 {
53 for (const_iterator it = p.begin(); it != p.end(); it++)
54 push_back(Vector<int>((*it).x, (*it).y));
55 }
56
Path(XML_Helper * helper)57 Path::Path(XML_Helper* helper)
58 {
59 int i;
60 std::istringstream sx, sy;
61 Glib::ustring s;
62
63 helper->getData(d_moves_exhausted_at_point, "moves_exhausted_at_point");
64 helper->getData(i, "size");
65
66 helper->getData(s, "x");
67 sx.str(s);
68 helper->getData(s, "y");
69 sy.str(s);
70
71 for (; i > 0; i--)
72 {
73 Vector<int> p = Vector<int>(-1,-1);
74
75 sx >> p.x;
76 sy >> p.y;
77 push_back(p);
78 }
79 }
80
~Path()81 Path::~Path()
82 {
83 clear();
84 }
85
save(XML_Helper * helper) const86 bool Path::save(XML_Helper* helper) const
87 {
88 bool retval = true;
89
90 std::stringstream sx, sy;
91 for (const_iterator it = begin(); it != end(); it++)
92 {
93 sx <<(*it).x <<" ";
94 sy <<(*it).y <<" ";
95 }
96
97 retval &= helper->openTag(Path::d_tag);
98 retval &= helper->saveData("size", (guint32) size());
99 retval &= helper->saveData("moves_exhausted_at_point",
100 d_moves_exhausted_at_point);
101 retval &= helper->saveData("x", sx.str());
102 retval &= helper->saveData("y", sy.str());
103 retval &= helper->closeTag();
104
105 return retval;
106 }
107
checkPath(Stack * s,int enemy_city_avoidance,int enemy_stack_avoidance)108 bool Path::checkPath(Stack* s, int enemy_city_avoidance, int enemy_stack_avoidance)
109 {
110 if (empty())
111 return true;
112 bool valid = true;
113 if (size() > 1)
114 {
115 iterator secondlast = end();
116 secondlast--;
117 for (iterator it = begin(); it != secondlast; it++)
118 {
119 if (PathCalculator::isBlocked(s, *it, enemy_city_avoidance,
120 enemy_stack_avoidance) == false)
121 {
122 valid = false;
123 break;
124 }
125 }
126 }
127
128 return valid;
129 }
130
131 //this is used to update the moves_exhausted_at_point variable
recalculate(Stack * s)132 void Path::recalculate (Stack* s)
133 {
134 if (size() == 0)
135 return;
136
137 // be careful to not go into cities that are now owned by the enemy
138 reverse_iterator it = rbegin();
139 for (; it != rend(); it++)
140 {
141 Vector<int> dest = *it;
142 City *c = GameMap::getCity(dest);
143 if (c && c->getOwner() != s->getOwner())
144 continue;
145 else
146 break;
147 }
148 if (it == rend())
149 {
150 //well, it looks like all of our points were in enemy cities
151 setMovesExhaustedAtPoint(0);
152 clear();
153 }
154 else
155 {
156 Vector<int> dest = *it;
157 calculate(s, dest);
158 }
159 return;
160 }
161
calculateToCity(Stack * s,City * c,bool zigzag)162 guint32 Path::calculateToCity (Stack *s, City *c, bool zigzag)
163 {
164 int min_dist = -1;
165 Vector<int> shortest = c->getPos();
166 bool checkJoin = s->getOwner() == c->getOwner();
167
168 for (unsigned int i = 0; i < c->getSize(); i++)
169 for (unsigned int j = 0; j < c->getSize(); j++)
170 {
171 if (checkJoin == true)
172 {
173 Stack *other_stack = GameMap::getStack(c->getPos() + Vector<int>(i,j));
174 if (other_stack && GameMap::canJoin(s,other_stack) == false)
175 continue;
176 }
177 int distance = dist (s->getPos(), c->getPos() + Vector<int>(i, j));
178 if (distance > 0)
179 {
180 if (distance < min_dist || min_dist == -1)
181 {
182 min_dist = distance;
183 shortest = c->getPos() + Vector<int>(i, j);
184 }
185 }
186 }
187 int mp = calculate(s, shortest, zigzag);
188 if (mp <= 0)
189 {
190 //okay.. try really hard
191 min_dist = -1;
192 for (unsigned int i = 0; i < c->getSize(); i++)
193 for (unsigned int j = 0; j < c->getSize(); j++)
194 {
195 if (checkJoin == true)
196 {
197 Stack *other_stack = GameMap::getStack(c->getPos() + Vector<int>(i,j));
198 if (other_stack && GameMap::canJoin(s,other_stack) == false)
199 continue;
200 }
201 int dist = calculate(s, c->getPos() + Vector<int>(i, j), zigzag);
202 if (dist > 0)
203 {
204 if (dist < min_dist || min_dist == -1)
205 {
206 min_dist = dist;
207 shortest = c->getPos() + Vector<int>(i, j);
208 }
209 }
210 }
211 mp = calculate(s, shortest, zigzag);
212 }
213 return mp;
214 }
215
calculate(Stack * s,Vector<int> dest,guint32 & moves,guint32 & turns,guint32 & left,bool zigzag)216 void Path::calculate (Stack* s, Vector<int> dest, guint32 &moves, guint32 &turns, guint32 &left, bool zigzag)
217 {
218 //int mp;
219 //Vector<int> start = s->getPos();
220 debug("path from "<<start.x<<","<<start.y<<" to "<<dest.x<<","<<dest.y)
221
222 clear();
223
224 // Some notes concerning the path finding algorithm. The algorithm
225 // uses two different lists. There is a nodes array, which contains how
226 // many MP one needs to get to the location (x,y), and a process queue that
227 // tells you at what point the number of movement points is calculated next.
228 //
229 // What we basically do is to start at the stack's position and calculate
230 // the distance (i.e. MP needed to get there) in circles around the starting
231 // position with the circles becoming increasingly larger. In detail, we
232 // start by appending the starting position in the queue of positions to be
233 // processed. Then, recursively, we take the first point in the queue and
234 // recalculate the distance for all bordering tiles, assuming that we go
235 // over this point and overwriting their current value if it is larger
236 // than what we find now. Then, we append each modified tile to the queue of
237 // tiles to be processed and continue. We stop when there are no more tiles
238 // to process.
239 //
240 // Finally, all that is left is finding the minimum distance way from start
241 // point to destination.
242
243
244 int enemy_city_avoidance = -1;
245 int enemy_stack_avoidance = -1;
246 if (s->getOwner() && s->getOwner()->isComputer())
247 {
248 //If we're a computer player we don't let enemy stacks and cities
249 //prevent us from reaching our destination. When we encounter them
250 //we'll fight, but we try not to encounter them.
251 enemy_city_avoidance = 10;
252 enemy_stack_avoidance = 10;
253 }
254 PathCalculator pc = PathCalculator(s, zigzag, enemy_city_avoidance,
255 enemy_stack_avoidance);
256
257 Path *calculated_path = pc.calculate(dest, moves, turns, left, zigzag);
258 if (calculated_path->size())
259 {
260 for(Path::iterator it = calculated_path->begin(); it!= calculated_path->end(); it++)
261 push_back(*it);
262 }
263
264 //calculate when the waypoints show no more movement possible
265 guint32 pathcount = 0;
266 guint32 moves_left = s->getMoves();
267 for (iterator it = begin(); it != end(); it++)
268 {
269 guint32 tile_moves = s->calculateTileMovementCost(*it);
270 if (moves_left >= tile_moves)
271 moves_left -= tile_moves;
272 else
273 break;
274 pathcount++;
275 }
276 setMovesExhaustedAtPoint(pathcount);
277 delete calculated_path;
278
279 return;
280 }
281
calculate(Stack * s,Vector<int> dest,guint32 & turns,bool zigzag)282 guint32 Path::calculate (Stack* s, Vector<int> dest, guint32 &turns, bool zigzag)
283 {
284 guint32 moves = 0, left = 0;
285 calculate(s, dest, moves, turns, left, zigzag);
286 return moves;
287 }
288
calculate(Stack * s,Vector<int> dest,bool zigzag)289 guint32 Path::calculate (Stack* s, Vector<int> dest, bool zigzag)
290 {
291 guint32 mp = 0, turns = 0, left = 0;
292 calculate(s, dest, mp, turns, left, zigzag);
293 return mp;
294 }
295
eraseFirstPoint()296 void Path::eraseFirstPoint()
297 {
298 erase(begin());
299
300 if (getMovesExhaustedAtPoint() > 0)
301 setMovesExhaustedAtPoint(getMovesExhaustedAtPoint()-1);
302 }
303
304 // End of file
305