1 /* 2 * Seven Kingdoms: Ancient Adversaries 3 * 4 * Copyright 1997,1998 Enlight Software Ltd. 5 * 6 * This program is free software: you can redistribute it and/or modify 7 * it under the terms of the GNU General Public License as published by 8 * the Free Software Foundation, either version 2 of the License, or 9 * (at your option) any later version. 10 * 11 * This program is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU General Public License for more details. 15 * 16 * You should have received a copy of the GNU General Public License 17 * along with this program. If not, see <http://www.gnu.org/licenses/>. 18 * 19 */ 20 21 //Filename : OSPATH.H 22 //Description : Header file of Object SeekPath 23 //Owner : Alex 24 25 #ifndef __OSPATH_H 26 #define __OSPATH_H 27 28 #ifndef __ALL_H 29 #include <ALL.h> 30 #endif 31 32 #ifndef __OVGA_H 33 #include <OVGA.h> 34 #endif 35 36 #ifndef __OWORLD_H 37 #include <OWORLD.h> 38 #endif 39 40 //---------- Define constants ------------// 41 42 enum { PATH_WAIT, // Wait for path seeking orders 43 PATH_SEEKING, // Seeking in process 44 PATH_FOUND, // A path is found 45 PATH_NODE_USED_UP, // All nodes have used, but still unable to find the destination 46 PATH_IMPOSSIBLE, // impossible to move, no result at all 47 PATH_REUSE_FOUND, // a reuse path is found 48 }; 49 50 //---------define the search mode------------// 51 enum { SEARCH_MODE_IN_A_GROUP = 1, // general searching for a unit 52 SEARCH_MODE_A_UNIT_IN_GROUP, // general group searching 53 SEARCH_MODE_TO_ATTACK, // general attacking searching 54 SEARCH_MODE_REUSE, // reuse path searching 55 SEARCH_MODE_BLOCKING, // searching when blocking (mainly for 2x2 units) 56 SEARCH_MODE_TO_VEHICLE, // embarking searching 57 58 //=================================================================// 59 // for the following search mode, destination location may be not 60 // walkable, group id together for speeding up chekcing in function 61 // can_move_to() 62 //-----------------------------------------------------------------// 63 SEARCH_MODE_TO_FIRM, 64 SEARCH_MODE_TO_TOWN, 65 SEARCH_MODE_TO_WALL_FOR_GROUP, 66 SEARCH_MODE_TO_WALL_FOR_UNIT, 67 SEARCH_MODE_ATTACK_UNIT_BY_RANGE, // searching to attack by range attack (esp. for attacking target with different mobile_type from this unit) 68 SEARCH_MODE_ATTACK_FIRM_BY_RANGE, 69 SEARCH_MODE_ATTACK_TOWN_BY_RANGE, 70 SEARCH_MODE_ATTACK_WALL_BY_RANGE, 71 //=================================================================// 72 73 SEARCH_MODE_TO_LAND_FOR_SHIP, // for ship only 74 SEARCH_MODE_LAST, //--- set to the last one 75 MAX_SEARCH_MODE_TYPE = SEARCH_MODE_LAST-1, 76 }; 77 78 //--------------------- define sub-mode -----------------// 79 enum { SEARCH_SUB_MODE_NORMAL=0, 80 SEARCH_SUB_MODE_PASSABLE, 81 }; 82 83 //----------- Define constants -----------// 84 85 #define MAX_BACKGROUND_NODE 2400 // the total no. of nodes can be used at a time 86 #define VALID_BACKGROUND_SEARCH_NODE 1600 // the search is considered unsuccessful if the node used > this value 87 #define MIN_BACKGROUND_NODE_USED_UP 400 // don't do any new search if the current available nodes is < this value 88 89 #define MAX_CHILD_NODE 8 // one for each direction 90 //#define MAX_STACK_NUM 2000 // maximum no. of stack entity in stack_aray, which is shared by all SeekPath objects. It is calculated based on: MAX possiblity: 500(MAX node) x 8(MAX child node) = 4000. Practical no. possiblities=2000. Memory occupied: 2000*4 = 8K 91 #define MAX_STACK_NUM MAX_BACKGROUND_NODE // maximum no. of stack entity in stack_aray, which is shared by all SeekPath objects. It is calculated based on: MAX possiblity: 500(MAX node) x 8(MAX child node) = 4000. Practical no. possiblities=2000. Memory occupied: 2000*4 = 8K 92 93 //---------- Define class Node -----------// 94 95 class Node 96 { 97 public: 98 short node_x, node_y; 99 int node_f, node_h;// could be replaced by "unsigned short" to reduce memory, set all member vars to "unsigned short" for consistency 100 short node_g; 101 char node_type;// the type of the node, total 16 different type, 4 points in a 2x2 node, blocked/non-blocked, so there are 2^4 combinations 102 char enter_direction; 103 // enter_direction -- 1-8 for eight directions, 0 for the starting node 104 // 105 // 8 7 6 106 // 1 x 5 where x is the reference point 107 // 2 3 4 108 109 Node* parent_node; 110 Node* child_node[MAX_CHILD_NODE]; 111 Node* next_node; 112 113 public: 114 short generate_successors(short dir, short x , short y); 115 short generate_succ(short x, short y, short direction, short cost); 116 void propagate_down(); 117 118 //------------- for scale 2 --------------// 119 short generate_successors2(short x, short y); 120 short generate_succ2(short x, short y, short cost=1); 121 void propagate_down2(); 122 }; 123 124 //------- Define struct ResultNode --------// 125 126 #pragma pack(1) 127 struct ResultNode 128 { 129 public: 130 short node_x, node_y; 131 }; 132 #pragma pack() 133 134 //---------- Define class Stack ----------// 135 136 struct Stack 137 { 138 Node *node_ptr; 139 Stack *next_stack_ptr; 140 }; 141 142 //---------- define struct NodePriorityQueue --------// 143 144 struct NodePriorityQueue 145 { 146 #define MAX_ARRAY_SIZE MAX_BACKGROUND_NODE+1 147 public: 148 unsigned int size; 149 Node *elements[MAX_ARRAY_SIZE]; 150 151 public: 152 void reset_priority_queue(); 153 void insert_node(Node *insertNode); 154 Node* return_min(); 155 }; 156 157 //--------- Define class SeekPath --------// 158 159 class SeekPath 160 { 161 friend class Node; 162 163 public: 164 char path_status; 165 short real_sour_x, real_sour_y; // the actual coordinate of the starting point 166 short real_dest_x, real_dest_y; // the actual coordinate of the destination point 167 short dest_x, dest_y; // the coordinate of the destination represented in 2x2 node form 168 char is_dest_blocked; 169 short current_search_node_used; // count the number of nodes used in the current searching 170 171 short border_x1, border_y1, border_x2, border_y2; 172 173 static NodePriorityQueue open_node_list; 174 static NodePriorityQueue closed_node_list; 175 176 short* node_matrix; 177 Node* node_array; 178 179 int max_node; 180 int node_count; 181 182 Node* result_node_ptr; 183 184 short total_node_avail; 185 void reset_total_node_avail(); 186 187 private: 188 ResultNode* max_size_result_node_ptr; // point to the temprory result node list 189 ResultNode* parent_result_node_ptr; // the parent node of the currently node pointed by max_size_result_node_ptr 190 int upper_left_x; // x coord. of upper left corner of the 2x2 node 191 int upper_left_y; // y coord. of upper left corner of the 2x2 node 192 193 public: SeekPath()194 SeekPath() { node_array=NULL; node_matrix=NULL; } ~SeekPath()195 ~SeekPath() { deinit(); } 196 197 void init(int maxNode); 198 void deinit(); 199 200 void set_node_matrix(short reuseNodeMatrix[]); set_status(char newStatus)201 void set_status(char newStatus) { path_status = newStatus; } is_valid_searching()202 int is_valid_searching() { return total_node_avail>VALID_BACKGROUND_SEARCH_NODE; } 203 204 void reset(); 205 inline void add_result_node(int x, int y, ResultNode** curPtr, ResultNode** prePtr, int& count); 206 int seek(int sx,int sy,int dx,int dy,uint32_t groupId,char mobileType, short searchMode=SEARCH_MODE_IN_A_GROUP, short miscNo=0, short numOfPath=1, int maxTries=0,int borderX1=0, int borderY1=0, int borderX2=MAX_WORLD_X_LOC-1, int borderY2=MAX_WORLD_Y_LOC-1); 207 int continue_seek(int,char=0); 208 209 ResultNode* get_result(int& resultNodeCount, short& pathDist); 210 Node* return_closest_node(); 211 ResultNode* smooth_the_path(ResultNode* nodeArray, int& nodeCount); // smoothing the path 212 213 //------------ for scale 2 -------------// 214 int seek2(int sx,int sy,int dx,int dy,short miscNo,short numOfPath,int maxTries); 215 int continue_seek2(int,char=0); 216 ResultNode* get_result2(int& resultNodeCount, short& pathDist); 217 218 void set_attack_range_para(int attackRange); 219 void reset_attack_range_para(); 220 void set_nation_recno(char nationRecno); 221 void set_nation_passable(char nationPassable[]); 222 void set_sub_mode(char subMode=SEARCH_SUB_MODE_NORMAL); 223 224 int write_file(File* filePtr); 225 int read_file(File* filePtr); 226 227 private: 228 static Node* return_best_node(); 229 230 void get_real_result_node(int &count, short enterDirection, short exitDirection, short nodeType, short xCoord, short yCoord); 231 // function used to get the actual shortest path out of the 2x2 node path 232 233 inline void bound_check_x(short ¶X); 234 inline void bound_check_y(short ¶Y); 235 inline short result_node_distance(ResultNode *node1, ResultNode *node2); 236 }; 237 238 extern SeekPath seek_path; 239 //### begin alex 29/9 ###// 240 #ifdef DEBUG 241 extern unsigned long seek_path_profile_time; 242 extern unsigned long last_seek_path_profile_time; 243 #endif 244 //#### end alex 29/9 ####// 245 246 //-----------------------------------------// 247 248 #endif 249 250