00001 /* 00002 $Id: path.h,v 1.7 2003/02/23 23:14:34 ksterker Exp $ 00003 00004 Copyright (C) 2001 Alexandre Courbot 00005 Part of the Adonthell Project http://adonthell.linuxgames.com 00006 00007 This program is free software; you can redistribute it and/or modify 00008 it under the terms of the GNU General Public License. 00009 This program is distributed in the hope that it will be useful, 00010 but WITHOUT ANY WARRANTY. 00011 00012 See the COPYING file for more details. 00013 */ 00014 00015 00016 /** 00017 * @file path.h 00018 * @author Alexandre Courbot <alexandrecourbot@linuxgames.com> 00019 * 00020 * @brief Declares the path class. 00021 * 00022 * 00023 */ 00024 00025 #ifndef PATH_H__ 00026 #define PATH_H__ 00027 00028 #include "mapsquare.h" 00029 00030 #ifndef SWIG 00031 using namespace std; 00032 #endif 00033 00034 class landmap; 00035 00036 /** 00037 * A* pathfinding algorithm implementation class. 00038 * 00039 * This class calculates the shortest way from a begin point 00040 * to a goal point on a landmap using the A* algorithm. It 00041 * stores a list of directions that when followed lead from 00042 * the start to the goal. 00043 * 00044 * This class is particularly well designed for mapcharacters, 00045 * who will often need to walk from one point to another. 00046 * 00047 */ 00048 class path 00049 { 00050 private: 00051 struct compare_squarecost 00052 { 00053 bool operator() (const mapsquare * s1, const mapsquare * s2) 00054 { 00055 return (s1->f > s2->f); 00056 } 00057 }; 00058 00059 public: 00060 #ifndef SWIG 00061 /** 00062 * (x, y) coordinates of a point on a submap. 00063 * 00064 */ 00065 struct area_coord 00066 { 00067 /** 00068 * X position. 00069 * 00070 */ 00071 u_int16 x; 00072 00073 /** 00074 * Y position. 00075 * 00076 */ 00077 u_int16 y; 00078 }; 00079 00080 /** 00081 * Landmap where the pathfinding will occur. 00082 * 00083 */ 00084 landmap * refmap; 00085 00086 /** 00087 * Submap where the pathfinding will occur. 00088 * 00089 */ 00090 u_int16 submap; 00091 00092 /** 00093 * Direction to face once the goal is reached. 00094 * 00095 */ 00096 u_int16 dir; 00097 00098 /** 00099 * Start point. 00100 * 00101 */ 00102 area_coord start; 00103 00104 /** 00105 * Goal point. 00106 * 00107 */ 00108 area_coord goal; 00109 #endif // SWIG 00110 00111 /** 00112 * Totally clears the path. 00113 * 00114 */ 00115 void clear () 00116 { 00117 moves_to_goal.clear (); 00118 } 00119 00120 /** 00121 * Tries to find the shortest path possible between the 00122 * \e start point and the \e goal point. 00123 * 00124 * @return \e true if a path was found, \e false otherwise. 00125 */ 00126 bool calculate (); 00127 00128 /** 00129 * Returns the number of moves between \e start and \e goal. 00130 * 00131 * 00132 * @return Number of moves between \e start and \e goal. 00133 */ 00134 u_int16 nbr_moves () const 00135 { 00136 return moves_to_goal.size (); 00137 } 00138 00139 /** 00140 * Returns the move to perform when at position \e nbr. 00141 * 00142 * @param nbr Index of the move to get. 00143 * 00144 * @return Direction (move) at index \e nbr. 00145 */ 00146 u_int16 get_move (u_int16 nbr) const 00147 { 00148 return moves_to_goal[nbr_moves () - (nbr + 1)]; 00149 } 00150 00151 /** 00152 * Restore the path's state from an opened file. 00153 * 00154 * @param file the opened file from which to load the state. 00155 * 00156 * @return 0 in case of success, error code otherwise. 00157 * 00158 * @bug the landmap this path belongs to must be restored manually! 00159 */ 00160 s_int8 get_state (igzstream & file); 00161 00162 /** 00163 * Saves the path's state into an opened file. 00164 * 00165 * @param file the opened file where to the state. 00166 * 00167 * @return 0 in case of success, error code otherwise. 00168 * 00169 * @bug the landmap this path belongs to can't be saved (as it's a pointer)! 00170 */ 00171 s_int8 put_state (ogzstream & file) const; 00172 00173 private: 00174 vector <u_int16> moves_to_goal; 00175 u_int16 goal_estimate (u_int16 x, u_int16 y); 00176 }; 00177 00178 #endif