Adonthell  0.4
path.cc
Go to the documentation of this file.
1 /*
2  Copyright (C) 2001 Alexandre Courbot
3  Part of the Adonthell Project <http://adonthell.nongnu.org>
4 
5  Adonthell is free software; you can redistribute it and/or modify
6  it under the terms of the GNU General Public License as published by
7  the Free Software Foundation; either version 2 of the License, or
8  (at your option) any later version.
9 
10  Adonthell is distributed in the hope that it will be useful,
11  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  GNU General Public License for more details.
14 
15  You should have received a copy of the GNU General Public License
16  along with Adonthell. If not, see <http://www.gnu.org/licenses/>.
17 */
18 
19 
20 /**
21  * @file path.cc
22  * @author Alexandre Courbot <alexandrecourbot@linuxgames.com>
23  *
24  * @brief Defines the path class.
25  *
26  *
27  */
28 
29 #include "path.h"
30 #include "landmap.h"
31 #include <queue>
32 #include <algorithm>
33 
34 
35 u_int16 path::goal_estimate (u_int16 x, u_int16 y)
36 {
37  u_int16 est;
38  if (x > goal.x) est = x - goal.x;
39  else est = goal.x - x;
40 
41  if (y > goal.y) est += y - goal.y;
42  else est += goal.y - y;
43 
44  return est;
45 }
46 
48 {
49  // Sorted Open nodes.
50  priority_queue <mapsquare *, vector<mapsquare *>, compare_squarecost> sorted_nodes;
51  // Open nodes.
52  vector <mapsquare *> opened_nodes;
53  // Closed nodes.
54  vector <mapsquare *> closed_nodes;
55 
56  moves_to_goal.clear ();
57 
59 
60  mapsquare * n = smap->get_square (start.x, start.y);
61  // Origin node
62  n->g = 0;
63  n->h = goal_estimate (n->x (), n->y ());
64  n->f = n->g + n->h;
65  n->parent = NULL;
66 
67  sorted_nodes.push (n);
68  opened_nodes.push_back (n);
69  while (!sorted_nodes.empty ())
70  {
71  n = sorted_nodes.top ();
72  sorted_nodes.pop ();
73  opened_nodes.erase (find (opened_nodes.begin (), opened_nodes.end (), n));
74 
75  // Have we reached the goal?
76  if (n->x () == goal.x && n->y () == goal.y)
77  {
78  while (n->parent != NULL)
79  {
80  // Vertical move
81  if (n->x () == n->parent->x ())
82  {
83  // Go to north
84  if (n->y () - n->parent->y () < 0)
85  moves_to_goal.push_back (WALK_NORTH);
86  // Go to south
87  else moves_to_goal.push_back (WALK_SOUTH);
88  }
89  // Horizontal move
90  else
91  {
92  // Go to west
93  if (n->x () - n->parent->x () < 0)
94  moves_to_goal.push_back (WALK_WEST);
95  // Go to east
96  else moves_to_goal.push_back (WALK_EAST);
97  }
98  n = n->parent;
99  }
100  return true;
101  }
102 
103  // Now proceeding with the successors of n
104  mapsquare * np;
105 
106  // East square
107  // Make sure that the square is not at the edge of the submap
108  // and is directly reachable.
109  // If so, add it to the opened nodes list.
110  if (n->x () + 1 < smap->area_length ())
111  {
112  np = smap->get_square (n->x () + 1, n->y ());
113  if (n->is_walkable_east () && np->is_walkable_west () && np->is_free () &&
114  (np->can_use_for_pathfinding || (np->x () == goal.x && np->y () == goal.y)))
115  {
116  u_int16 newg = n->g + 1;
117  bool in_opened, in_closed;
118  in_opened = (find (opened_nodes.begin (), opened_nodes.end (), np) != opened_nodes.end ());
119  in_closed = (find (closed_nodes.begin (), closed_nodes.end (), np) != closed_nodes.end ());
120 
121  // If np is in opened_nodes or closed_nodes and np->g <= newg, don't do anything.
122  if (!((in_opened || in_closed) && np->g <= newg))
123  // else add the node to the opened nodes list (if necessary)
124  {
125  np->g = newg;
126  np->h = goal_estimate (np->x (), np->y ());
127  np->f = np->g + np->h;
128  np->parent = n;
129 
130  // if np is in closed_nodes, remove it
131  if (in_closed)
132  closed_nodes.erase (find (closed_nodes.begin (), closed_nodes.end (), np));
133 
134  // if np is not in opened_nodes yet, add it
135  if (!in_opened)
136  {
137  sorted_nodes.push (np);
138  opened_nodes.push_back (np);
139  }
140  }
141  }
142  }
143 
144 
145  // West square
146  // Make sure that the square is not at the edge of the submap
147  // and is directly reachable.
148  // If so, add it to the opened nodes list.
149  if (n->x () > 0)
150  {
151  np = smap->get_square (n->x () - 1, n->y ());
152  if (n->is_walkable_west () && np->is_walkable_east () && np->is_free () &&
153  (np->can_use_for_pathfinding || (np->x () == goal.x && np->y () == goal.y)))
154  {
155  u_int16 newg = n->g + 1;
156  bool in_opened, in_closed;
157  in_opened = (find (opened_nodes.begin (), opened_nodes.end (), np) != opened_nodes.end ());
158  in_closed = (find (closed_nodes.begin (), closed_nodes.end (), np) != closed_nodes.end ());
159 
160  // If np is in opened_nodes or closed_nodes and np->g <= newg, don't do anything.
161  if (!((in_opened || in_closed) && np->g <= newg))
162  // else add the node to the opened nodes list (if necessary)
163  {
164  np->g = newg;
165  np->h = goal_estimate (np->x (), np->y ());
166  np->f = np->g + np->h;
167  np->parent = n;
168 
169  // if np is in closed_nodes, remove it
170  if (in_closed)
171  closed_nodes.erase (find (closed_nodes.begin (), closed_nodes.end (), np));
172 
173  // if np is not in opened_nodes yet, add it
174  if (!in_opened)
175  {
176  sorted_nodes.push (np);
177  opened_nodes.push_back (np);
178  }
179  }
180  }
181  }
182 
183 
184  // North square
185  // Make sure that the square is not at the edge of the submap
186  // and is directly reachable.
187  // If so, add it to the opened nodes list.
188  if (n->y () > 0)
189  {
190  np = smap->get_square (n->x (), n->y () - 1);
191  if (n->is_walkable_north () && np->is_walkable_south () && np->is_free () &&
192  (np->can_use_for_pathfinding || (np->x () == goal.x && np->y () == goal.y)))
193  {
194  u_int16 newg = n->g + 1;
195  bool in_opened, in_closed;
196  in_opened = (find (opened_nodes.begin (), opened_nodes.end (), np) != opened_nodes.end ());
197  in_closed = (find (closed_nodes.begin (), closed_nodes.end (), np) != closed_nodes.end ());
198 
199  // If np is in opened_nodes or closed_nodes and np->g <= newg, don't do anything.
200  if (!((in_opened || in_closed) && np->g <= newg))
201  // else add the node to the opened nodes list (if necessary)
202  {
203  np->g = newg;
204  np->h = goal_estimate (np->x (), np->y ());
205  np->f = np->g + np->h;
206  np->parent = n;
207 
208  // if np is in closed_nodes, remove it
209  if (in_closed)
210  closed_nodes.erase (find (closed_nodes.begin (), closed_nodes.end (), np));
211 
212  // if np is not in opened_nodes yet, add it
213  if (!in_opened)
214  {
215  sorted_nodes.push (np);
216  opened_nodes.push_back (np);
217  }
218  }
219  }
220  }
221 
222  // South square
223  // Make sure that the square is not at the edge of the submap
224  // and is directly reachable.
225  // If so, add it to the opened nodes list.
226  if (n->y () + 1 < smap->area_height ())
227  {
228  np = smap->get_square (n->x (), n->y () + 1);
229  if (n->is_walkable_south () && np->is_walkable_north () && np->is_free () &&
230  (np->can_use_for_pathfinding || (np->x () == goal.x && np->y () == goal.y)))
231  {
232  u_int16 newg = n->g + 1;
233  bool in_opened, in_closed;
234  in_opened = (find (opened_nodes.begin (), opened_nodes.end (), np) != opened_nodes.end ());
235  in_closed = (find (closed_nodes.begin (), closed_nodes.end (), np) != closed_nodes.end ());
236 
237  // If np is in opened_nodes or closed_nodes and np->g <= newg, don't do anything.
238  if (!((in_opened || in_closed) && np->g <= newg))
239  // else add the node to the opened nodes list (if necessary)
240  {
241  np->g = newg;
242  np->h = goal_estimate (np->x (), np->y ());
243  np->f = np->g + np->h;
244  np->parent = n;
245 
246  // if np is in closed_nodes, remove it
247  if (in_closed)
248  closed_nodes.erase (find (closed_nodes.begin (), closed_nodes.end (), np));
249 
250  // if np is not in opened_nodes yet, add it
251  if (!in_opened)
252  {
253  sorted_nodes.push (np);
254  opened_nodes.push_back (np);
255  }
256  }
257  }
258  }
259 
260  closed_nodes.push_back (n);
261  }
262  return false;
263 }
264 
266 {
267  u_int16 nb_moves;
268 
269  clear ();
270 
271  submap << file;
272  dir << file;
273  start.x << file;
274  start.y << file;
275  goal.x << file;
276  goal.y << file;
277 
278  nb_moves << file;
279 
280  for (u_int16 i = 0; i < nb_moves; i++)
281  {
282  u_int16 t;
283  t << file;
284  moves_to_goal.push_back (t);
285  }
286  return 0;
287 }
288 
290 {
291  submap >> file;
292  dir >> file;
293  start.x >> file;
294  start.y >> file;
295  goal.x >> file;
296  goal.y >> file;
297 
298  nbr_moves () >> file;
299 
300  for (u_int16 i = 0; i < nbr_moves (); i++)
301  {
302  get_move (i) >> file;
303  }
304  return 0;
305 }
WALK_SOUTH
#define WALK_SOUTH
Walking South.
Definition: mapcharacter.h:88
mapsquare_area::area_height
u_int16 area_height() const
Returns the height of the area.
Definition: mapsquare.h:416
path.h
Declares the path class.
mapsquare::parent
mapsquare * parent
Parent square for the path.
Definition: mapsquare.h:329
path::area_coord::x
u_int16 x
X position.
Definition: path.h:75
mapsquare_walkable::is_walkable_south
bool is_walkable_south() const
Returns whether a mapsquare is walkable from south.
Definition: mapsquare_walkable.h:153
WALK_EAST
#define WALK_EAST
Walking East.
Definition: mapcharacter.h:100
mapsquare::is_free
bool is_free()
Returns whether the mapsquare is free for a character to go on or not.
Definition: mapsquare.cc:77
igzstream
Class to read data from a Gzip compressed file.
Definition: fileops.h:135
mapsquare_area::area_length
u_int16 area_length() const
Returns the length of the area.
Definition: mapsquare.h:405
path::get_state
s_int8 get_state(igzstream &file)
Restore the path's state from an opened file.
Definition: path.cc:265
path::refmap
landmap * refmap
Landmap where the pathfinding will occur.
Definition: path.h:88
path::nbr_moves
u_int16 nbr_moves() const
Returns the number of moves between start and goal.
Definition: path.h:138
landmap.h
path::calculate
bool calculate()
Tries to find the shortest path possible between the start point and the goal point.
Definition: path.cc:47
mapsquare::g
u_int16 g
Distance from the source square.
Definition: mapsquare.h:311
mapsquare::h
u_int16 h
Estimated distance to the goal square.
Definition: mapsquare.h:317
ogzstream
Class to write data from a Gzip compressed file.
Definition: fileops.h:227
mapsquare::f
u_int16 f
Sum of g + h.
Definition: mapsquare.h:323
path::put_state
s_int8 put_state(ogzstream &file) const
Saves the path's state into an opened file.
Definition: path.cc:289
mapsquare_walkable::is_walkable_north
bool is_walkable_north() const
Returns whether a mapsquare is walkable from north.
Definition: mapsquare_walkable.h:142
mapsquare_walkable::is_walkable_east
bool is_walkable_east() const
Returns whether a mapsquare is walkable from east.
Definition: mapsquare_walkable.h:131
s_int8
#define s_int8
8 bits long signed integer
Definition: types.h:44
mapsquare::can_use_for_pathfinding
bool can_use_for_pathfinding
If == false, then this square will never be considered as walkable by pathfinding functions.
Definition: mapsquare.h:336
mapsquare_walkable::is_walkable_west
bool is_walkable_west() const
Returns whether a mapsquare is walkable from west.
Definition: mapsquare_walkable.h:120
mapsquare_area
Area of mapsquares, for use with landmap.
Definition: mapsquare.h:372
path::submap
u_int16 submap
Submap where the pathfinding will occur.
Definition: path.h:94
path::dir
u_int16 dir
Direction to face once the goal is reached.
Definition: path.h:100
path::start
area_coord start
Start point.
Definition: path.h:106
mapsquare::x
u_int16 x()
Returns the X position of this mapsquare.
Definition: mapsquare.h:263
u_int16
#define u_int16
16 bits long unsigned integer
Definition: types.h:38
WALK_NORTH
#define WALK_NORTH
Walking North.
Definition: mapcharacter.h:82
landmap::get_submap
mapsquare_area * get_submap(u_int16 pos)
Returns a pointer to a submap belonging to this landmap.
Definition: landmap.h:167
WALK_WEST
#define WALK_WEST
Walking West.
Definition: mapcharacter.h:94
path::area_coord::y
u_int16 y
Y position.
Definition: path.h:81
mapsquare_area::get_square
mapsquare * get_square(u_int16 x, u_int16 y) const
Returns a pointer to a desired square.
Definition: mapsquare.h:430
mapsquare::y
u_int16 y()
Returns the Y position of this mapsquare.
Definition: mapsquare.h:274
mapsquare
Base unit of a landsubmap, where you can place mapobjects or mapcharacters.
Definition: mapsquare.h:234
path::goal
area_coord goal
Goal point.
Definition: path.h:112
path::clear
void clear()
Totally clears the path.
Definition: path.h:119
path::get_move
u_int16 get_move(u_int16 nbr) const
Returns the move to perform when at position nbr.
Definition: path.h:150