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