39 else est =
goal.
x - x;
42 else est +=
goal.
y - y;
50 priority_queue <mapsquare *, vector<mapsquare *>, compare_squarecost> sorted_nodes;
52 vector <mapsquare *> opened_nodes;
54 vector <mapsquare *> closed_nodes;
56 moves_to_goal.clear ();
63 n->
h = goal_estimate (n->
x (), n->
y ());
67 sorted_nodes.push (n);
68 opened_nodes.push_back (n);
69 while (!sorted_nodes.empty ())
71 n = sorted_nodes.top ();
73 opened_nodes.erase (find (opened_nodes.begin (), opened_nodes.end (), n));
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 ());
122 if (!((in_opened || in_closed) && np->
g <= newg))
126 np->
h = goal_estimate (np->
x (), np->
y ());
127 np->
f = np->
g + np->
h;
132 closed_nodes.erase (find (closed_nodes.begin (), closed_nodes.end (), np));
137 sorted_nodes.push (np);
138 opened_nodes.push_back (np);
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 ());
161 if (!((in_opened || in_closed) && np->
g <= newg))
165 np->
h = goal_estimate (np->
x (), np->
y ());
166 np->
f = np->
g + np->
h;
171 closed_nodes.erase (find (closed_nodes.begin (), closed_nodes.end (), np));
176 sorted_nodes.push (np);
177 opened_nodes.push_back (np);
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 ());
200 if (!((in_opened || in_closed) && np->
g <= newg))
204 np->
h = goal_estimate (np->
x (), np->
y ());
205 np->
f = np->
g + np->
h;
210 closed_nodes.erase (find (closed_nodes.begin (), closed_nodes.end (), np));
215 sorted_nodes.push (np);
216 opened_nodes.push_back (np);
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 ());
238 if (!((in_opened || in_closed) && np->
g <= newg))
242 np->
h = goal_estimate (np->
x (), np->
y ());
243 np->
f = np->
g + np->
h;
248 closed_nodes.erase (find (closed_nodes.begin (), closed_nodes.end (), np));
253 sorted_nodes.push (np);
254 opened_nodes.push_back (np);
260 closed_nodes.push_back (n);
280 for (
u_int16 i = 0; i < nb_moves; i++)
284 moves_to_goal.push_back (t);
s_int8 get_state(igzstream &file)
Restore the path's state from an opened file.
Class to write data from a Gzip compressed file.
bool is_walkable_west() const
Returns whether a mapsquare is walkable from west.
u_int16 x()
Returns the X position of this mapsquare.
Class to read data from a Gzip compressed file.
area_coord goal
Goal point.
bool is_free()
Returns whether the mapsquare is free for a character to go on or not.
#define u_int16
16 bits long unsigned integer
mapsquare * parent
Parent square for the path.
area_coord start
Start point.
u_int16 submap
Submap where the pathfinding will occur.
mapsquare * get_square(u_int16 x, u_int16 y) const
Returns a pointer to a desired square.
u_int16 area_height() const
Returns the height of the area.
u_int16 dir
Direction to face once the goal is reached.
#define WALK_SOUTH
Walking South.
#define WALK_WEST
Walking West.
bool can_use_for_pathfinding
If == false, then this square will never be considered as walkable by pathfinding functions...
u_int16 area_length() const
Returns the length of the area.
Declares the landmap class.
mapsquare_area * get_submap(u_int16 pos)
Returns a pointer to a submap belonging to this landmap.
bool is_walkable_east() const
Returns whether a mapsquare is walkable from east.
u_int16 g
Distance from the source square.
landmap * refmap
Landmap where the pathfinding will occur.
u_int16 y()
Returns the Y position of this mapsquare.
void clear()
Totally clears the path.
Base unit of a landsubmap, where you can place mapobjects or mapcharacters.
bool is_walkable_north() const
Returns whether a mapsquare is walkable from north.
#define WALK_NORTH
Walking North.
bool is_walkable_south() const
Returns whether a mapsquare is walkable from south.
u_int16 h
Estimated distance to the goal square.
#define WALK_EAST
Walking East.
s_int8 put_state(ogzstream &file) const
Saves the path's state into an opened file.
bool calculate()
Tries to find the shortest path possible between the start point and the goal point.
#define s_int8
8 bits long signed integer
u_int16 get_move(u_int16 nbr) const
Returns the move to perform when at position nbr.
Area of mapsquares, for use with landmap.
u_int16 nbr_moves() const
Returns the number of moves between start and goal.