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.CPP
22 //Description : Object SeekPath
23 //Owner :
24
25 #include <math.h>
26 #include <stdlib.h>
27 #include <ALL.h>
28 #include <OWORLD.h>
29 #include <OSPATH.h>
30 #include <OFIRM.h>
31 #include <OTOWN.h>
32 #include <OUNIT.h>
33 #include <OSYS.h>
34 #include <ONATION.h>
35
36 #ifdef NO_DEBUG_SEARCH
37 #undef err_when
38 #undef err_here
39 #undef err_if
40 #undef err_else
41 #undef err_now
42 #define err_when(cond)
43 #define err_here()
44 #define err_if(cond)
45 #define err_else
46 #define err_now(msg)
47 #undef DEBUG
48 #endif
49
50 #define ZOOM_LOC_HALF_WIDTH ZOOM_LOC_WIDTH/2
51 #define ZOOM_LOC_HALF_HEIGHT ZOOM_LOC_HEIGHT/2
52
53 //----------- Define static variables -----------//
54
55 static Location* world_loc_matrix;
56 static int cur_stack_pos=0;
57 static Node* stack_array[MAX_STACK_NUM];
58 static uint32_t group_id;
59 static short search_mode;
60 static char mobile_type;
61 static char seek_nation_recno;
62 static int attack_range; // used in search_mode = SEARCH_MODE_ATTACK_UNIT_BY_RANGE
63 static short target_recno; // used in search_mode = SEARCH_MODE_TO_ATTACK or SEARCH_MODE_TO_VEHICLE, get from miscNo
64 static uint8_t region_id; // used in search_mode = SEARCH_MODE_TO_LAND_FOR_SHIP
65 static short building_id; // used in search_mode = SEARCH_MODE_TO_FIRM or SEARCH_MODE_TO_TOWN, get from miscNo
66 //======================================================================//
67 // 1) if search_mode = SEARCH_MODE_TO_FIRM or SEARCH_MODE_TO_TOWN
68 // the building top_left to bottom_right positions
69 // 2) if search_mode = SEARCH_MODE_ATTACK_UNIT_BY_RANGE,
70 // the effective attacking region top_left to bottom_right positions
71 //======================================================================//
72 static int building_x1, building_y1, building_x2, building_y2;
73 static FirmInfo *search_firm_info;
74
75 static int max_node_num;
76 static short *reuse_node_matrix_ptr;
77 static Node *reuse_result_node_ptr;
78 static short final_dest_x; // in search_mode SEARCH_MODE_REUSE, dest_x and dest_y may set to a different value.
79 static short final_dest_y; // i.e. the value used finally may not be the real dest_? given.
80
81 //------- aliasing class member vars for fast access ------//
82
83 static SeekPath* cur_seek_path;
84 static short cur_dest_x, cur_dest_y;
85 static short* cur_node_matrix;
86 static Node* cur_node_array;
87 static short cur_border_x1, cur_border_y1, cur_border_x2, cur_border_y2;
88
89 static char nation_passable[MAX_NATION+1] = {0}; // Note: position 0 is not used for faster access
90 static char search_sub_mode;
91
92 //----------- Define static functions -----------//
93
94 static void stack_push(Node *nodePtr);
95 static Node* stack_pop();
96
97 //-***************************************************************************-//
98 //-*************************** for debuging **********************************-//
99 //-***************************************************************************-//
100 #ifdef DEBUG
101 static int is_yielding = 0;
102 static ResultNode *debugNode1, *debugNode2;
103 static int dcount;
104 static int vX, vY; // for debug only
105
106 //---------- function debug_check() ------------//
debug_check(ResultNode * nodeArray,int count)107 void debug_check(ResultNode *nodeArray, int count)
108 {
109 debugNode1 = nodeArray;
110 debugNode2 = nodeArray+1;
111
112 for(dcount=1; dcount<count; dcount++, debugNode1++, debugNode2++)
113 {
114 err_when(debugNode1->node_x<0 || debugNode1->node_x>=MAX_WORLD_X_LOC ||
115 debugNode1->node_y<0 || debugNode1->node_y>=MAX_WORLD_Y_LOC);
116 vX = debugNode2->node_x - debugNode2->node_x;
117 vY = debugNode2->node_y - debugNode2->node_y;
118 err_when(vX!=0 && vY!=0 && (abs(vX)!=abs(vY)));
119 }
120
121 err_when(debugNode1->node_x<0 || debugNode1->node_x>=MAX_WORLD_X_LOC ||
122 debugNode1->node_y<0 || debugNode1->node_y>=MAX_WORLD_Y_LOC);
123 }
124
125 //----------- function debug_check_smode_exclude_hostile() -------------//
debug_check_smode_exclude_hostile(ResultNode * nodeArray,int count)126 void debug_check_smode_exclude_hostile(ResultNode *nodeArray, int count)
127 {
128 ResultNode *curNode = nodeArray;
129 ResultNode *nextNode = nodeArray+1;
130 Location *locPtr;
131 int checkXLoc, checkYLoc, vecX, vecY, magn;
132 for(int ij=1; ij<count; ij++, curNode++, nextNode++)
133 {
134 checkXLoc = curNode->node_x;
135 checkYLoc = curNode->node_y;
136 vecX = nextNode->node_x-curNode->node_x;
137 vecY = nextNode->node_y-curNode->node_y;
138 magn = (abs(vecX)>=abs(vecY)) ? abs(vecX) : abs(vecY);
139 if(vecX) vecX /= abs(vecX);
140 if(vecY) vecY /= abs(vecY);
141 for(int jk=0; jk<magn; jk++)
142 {
143 checkXLoc += vecX;
144 checkYLoc += vecY;
145 locPtr = world.get_loc(checkXLoc, checkYLoc);
146 err_when(locPtr->power_nation_recno && !nation_passable[locPtr->power_nation_recno]);
147 }
148 }
149 }
150
151 //-------------- function debug_check_sailable_path() --------------//
debug_check_sailable_path(ResultNode * nodeArray,int count)152 void debug_check_sailable_path(ResultNode *nodeArray, int count)
153 {
154 ResultNode *debugPtr1 = nodeArray;
155 ResultNode *debugPtr2 = nodeArray+1;
156 int di=1, dj, dvecX, dvecY, magn;
157 while(di<count)
158 {
159 dvecX = debugPtr2->node_x-debugPtr1->node_x;
160 dvecY = debugPtr2->node_y-debugPtr1->node_y;
161 magn = (abs(dvecX) > abs(dvecY)) ? abs(dvecX) : abs(dvecY);
162 dvecX /= magn;
163 dvecY /= magn;
164 for(dj=1; dj<=magn; dj++)
165 err_when(!world.get_loc(debugPtr1->node_x+dvecX*dj, debugPtr1->node_y+dvecY*dj)->sailable());
166
167 di++;
168 debugPtr1++;
169 debugPtr2++;
170 }
171 }
172
173 #endif
174
175 #ifdef DEBUG
176 #define debug_check_path(nodeArray, count) debug_check((nodeArray), (count))
177 #define debug_check_sub_mode(nodeArray, count) debug_check_smode_exclude_hostile((nodeArray), (count))
178 #define debug_check_sea_sailable(nodeArray, count) debug_check_sailable_path((nodeArray), (count))
179 #else
180 #define debug_check_path(nodeArray, count)
181 #define debug_check_sub_mode(nodeArray, count)
182 #define debug_check_sea_sailable(nodeArray, count)
183 #endif
184 //-***************************************************************************-//
185 //-**************************** end debuging *********************************-//
186 //-***************************************************************************-//
187
188 //------- Begin of static function sys_yield ------//
sys_yield()189 static void sys_yield()
190 {
191 #ifdef DEBUG
192 is_yielding++;
193 #endif
194
195 //sys.yield();
196
197 #ifdef DEBUG
198 is_yielding = 0;
199 #endif
200 }
201 //-------- End of static function sys_yield ------//
202
203
204 //------- Begin of static function can_move_to ------//
can_move_to(int xLoc,int yLoc)205 static int can_move_to(int xLoc, int yLoc)
206 {
207 Location *locPtr = world_loc_matrix+yLoc*MAX_WORLD_X_LOC+xLoc;
208 Unit *unitPtr;
209 short recno;
210 char powerNationRecno;
211 uint8_t unitCurAction;
212
213 //------ check terrain id. -------//
214 switch(mobile_type)
215 {
216 case UNIT_LAND:
217 if(search_sub_mode==SEARCH_SUB_MODE_PASSABLE && (powerNationRecno=locPtr->power_nation_recno) &&
218 !nation_passable[powerNationRecno])
219 return 0;
220
221 if(search_mode<SEARCH_MODE_TO_FIRM) //------ be careful for the checking for search_mode>=SEARCH_MODE_TO_FIRM
222 {
223 //------------------------------------------------------------------------//
224 if(!locPtr->walkable())
225 return 0;
226
227 recno = locPtr->cargo_recno;
228 if(!recno)
229 return 1;
230
231 switch(search_mode)
232 {
233 case SEARCH_MODE_IN_A_GROUP: // group move
234 case SEARCH_MODE_REUSE: // path-reuse
235 break;
236
237 case SEARCH_MODE_A_UNIT_IN_GROUP: // a unit in a group
238 unitPtr = unit_array[recno];
239 return unitPtr->cur_action==SPRITE_MOVE && unitPtr->unit_id!=UNIT_CARAVAN;
240
241 case SEARCH_MODE_TO_ATTACK: // to attack target
242 case SEARCH_MODE_TO_VEHICLE: // move to a vehicle
243 if(recno==target_recno)
244 return 1;
245 break;
246
247 case SEARCH_MODE_BLOCKING: // 2x2 unit blocking
248 unitPtr = unit_array[recno];
249 return unitPtr->unit_group_id==group_id && (unitPtr->cur_action==SPRITE_MOVE || unitPtr->cur_action==SPRITE_READY_TO_MOVE);
250
251 default: err_here();
252 break;
253 }
254 }
255 else
256 {
257 //--------------------------------------------------------------------------------//
258 // for the following search_mode, location may be treated as walkable although it is not.
259 //--------------------------------------------------------------------------------//
260 switch(search_mode)
261 {
262 case SEARCH_MODE_TO_FIRM: // move to a firm, (location may be not walkable)
263 case SEARCH_MODE_TO_TOWN: // move to a town zone, (location may be not walkable)
264 if(!locPtr->walkable())
265 return (xLoc>=building_x1 && xLoc<=building_x2 && yLoc>=building_y1 && yLoc<=building_y2);
266 break;
267
268 case SEARCH_MODE_TO_WALL_FOR_GROUP: // move to wall for a group, (location may be not walkable)
269 if(!locPtr->walkable())
270 return (xLoc==final_dest_x && yLoc==final_dest_y);
271 break;
272
273 case SEARCH_MODE_TO_WALL_FOR_UNIT: // move to wall for a unit only, (location may be not walkable)
274 return (locPtr->walkable() && locPtr->cargo_recno==0) || (xLoc==final_dest_x && yLoc==final_dest_y);
275
276 case SEARCH_MODE_ATTACK_UNIT_BY_RANGE: // same as that used in SEARCH_MODE_TO_FIRM
277 case SEARCH_MODE_ATTACK_FIRM_BY_RANGE:
278 case SEARCH_MODE_ATTACK_TOWN_BY_RANGE:
279 case SEARCH_MODE_ATTACK_WALL_BY_RANGE:
280 if(!locPtr->walkable())
281 return (xLoc>=building_x1 && xLoc<=building_x2 && yLoc>=building_y1 && yLoc<=building_y2);
282 break;
283
284 default: err_here();
285 break;
286 }
287
288 recno = (mobile_type!=UNIT_AIR) ? locPtr->cargo_recno : locPtr->air_cargo_recno;
289 if(!recno)
290 return 1;
291 }
292
293 //------- checking for unit's group_id, cur_action, nation_recno and position --------//
294 unitPtr = unit_array[recno];
295 unitCurAction = unitPtr->cur_action;
296 return (unitPtr->unit_group_id==group_id && unitCurAction!=SPRITE_ATTACK) ||
297 (unitCurAction==SPRITE_MOVE && unitPtr->cur_x-unitPtr->next_x<=ZOOM_LOC_HALF_WIDTH &&
298 unitPtr->cur_y-unitPtr->next_y<=ZOOM_LOC_HALF_HEIGHT) ||
299 (unitPtr->nation_recno==seek_nation_recno && unitCurAction==SPRITE_IDLE);
300 break;
301
302 case UNIT_SEA:
303 if(search_mode<SEARCH_MODE_TO_FIRM) //--------- be careful for the search_mode>=SEARCH_MODE_TO_FIRM
304 {
305 if(!locPtr->sailable())
306 return 0;
307
308 recno = locPtr->cargo_recno;
309 if(!recno)
310 return 1;
311
312 switch(search_mode)
313 {
314 case SEARCH_MODE_IN_A_GROUP: // group move
315 case SEARCH_MODE_REUSE: // path-reuse
316 break;
317
318 case SEARCH_MODE_A_UNIT_IN_GROUP: // a unit in a group
319 return unit_array[recno]->cur_action==SPRITE_MOVE;
320
321 case SEARCH_MODE_TO_ATTACK:
322 if(recno==target_recno)
323 return 1;
324 break;
325
326 default: err_here();
327 break;
328 }
329 }
330 else
331 {
332 //--------------------------------------------------------------------------------//
333 // for the following search_mode, location may be treated as sailable although it is not.
334 //--------------------------------------------------------------------------------//
335 switch(search_mode)
336 {
337 case SEARCH_MODE_TO_FIRM: // move to a firm, (location may be not walkable)
338 case SEARCH_MODE_TO_TOWN: // move to a town zone, (location may be not walkable)
339 if(!locPtr->sailable())
340 return (xLoc>=building_x1 && xLoc<=building_x2 && yLoc>=building_y1 && yLoc<=building_y2);
341 break;
342
343 //case SEARCH_MODE_TO_WALL_FOR_GROUP: // move to wall for a group, (location may be not walkable)
344 //case SEARCH_MODE_TO_WALL_FOR_UNIT: // move to wall for a unit only, (location may be not walkable)
345
346 case SEARCH_MODE_ATTACK_UNIT_BY_RANGE: // same as that used in SEARCH_MODE_TO_FIRM
347 case SEARCH_MODE_ATTACK_FIRM_BY_RANGE:
348 case SEARCH_MODE_ATTACK_TOWN_BY_RANGE:
349 case SEARCH_MODE_ATTACK_WALL_BY_RANGE:
350 if(!locPtr->sailable())
351 return (xLoc>=building_x1 && xLoc<=building_x2 && yLoc>=building_y1 && yLoc<=building_y2);
352 break;
353
354 case SEARCH_MODE_TO_LAND_FOR_SHIP:
355 if(locPtr->sailable())
356 {
357 recno = locPtr->cargo_recno;
358 if(!recno)
359 return 1;
360
361 unitPtr = unit_array[recno];
362 unitCurAction = unitPtr->cur_action;
363 return (unitPtr->unit_group_id==group_id && unitCurAction!=SPRITE_ATTACK &&
364 unitPtr->action_mode2!=ACTION_SHIP_TO_BEACH) ||
365 (unitPtr->unit_group_id!=group_id && unitCurAction==SPRITE_MOVE);
366 }
367 else if(locPtr->walkable() && locPtr->region_id==region_id)
368 return 1;
369 else
370 return 0;
371
372 default: err_here();
373 break;
374 }
375 recno = locPtr->cargo_recno;
376 if(!recno)
377 return 1;
378 }
379
380 //------- checking for unit's group_id, cur_action, nation_recno and position --------//
381 unitPtr = unit_array[recno];
382 unitCurAction = unitPtr->cur_action;
383 return (unitPtr->unit_group_id==group_id && unitCurAction!=SPRITE_ATTACK) ||
384 unitCurAction==SPRITE_MOVE ||
385 (unitPtr->nation_recno==seek_nation_recno && unitCurAction==SPRITE_IDLE);
386 break;
387
388 case UNIT_AIR:
389 recno = locPtr->air_cargo_recno;
390 if(!recno)
391 return 1;
392 switch(search_mode)
393 {
394 case SEARCH_MODE_IN_A_GROUP:
395 case SEARCH_MODE_REUSE:
396 case SEARCH_MODE_TO_ATTACK:
397 case SEARCH_MODE_TO_FIRM:
398 case SEARCH_MODE_TO_TOWN:
399 case SEARCH_MODE_TO_WALL_FOR_GROUP:
400 case SEARCH_MODE_TO_WALL_FOR_UNIT:
401 case SEARCH_MODE_ATTACK_UNIT_BY_RANGE:
402 case SEARCH_MODE_ATTACK_FIRM_BY_RANGE:
403 case SEARCH_MODE_ATTACK_TOWN_BY_RANGE:
404 case SEARCH_MODE_ATTACK_WALL_BY_RANGE:
405 unitPtr = unit_array[recno];
406 unitCurAction = unitPtr->cur_action;
407 return (unitPtr->unit_group_id==group_id && unitCurAction!=SPRITE_ATTACK) ||
408 unitCurAction==SPRITE_MOVE ||
409 (unitPtr->nation_recno==seek_nation_recno && unitCurAction==SPRITE_IDLE);
410
411 case SEARCH_MODE_A_UNIT_IN_GROUP: // a unit in a group
412 return unit_array[recno]->cur_action==SPRITE_MOVE;
413
414 default: err_here();
415 break;
416 }
417 break;
418 }
419
420 return 0;
421 }
422 //-------- End of static function can_move_to ------//
423
424
425 //-------- Begin of function SeekPath::bound_check_x ---------//
bound_check_x(short & paraX)426 inline void SeekPath::bound_check_x(short ¶X)
427 {
428 if(paraX<0)
429 paraX = 0;
430 else if(paraX>=MAX_WORLD_X_LOC-1)
431 paraX = MAX_WORLD_X_LOC-1;
432 }
433 //-------- End of static function bound_check_x ------//
434
435
436 //-------- Begin of function SeekPath::bound_check_y ---------//
bound_check_y(short & paraY)437 inline void SeekPath::bound_check_y(short ¶Y)
438 {
439 if(paraY<0)
440 paraY = 0;
441 else if(paraY>=MAX_WORLD_Y_LOC-1)
442 paraY = MAX_WORLD_Y_LOC-1;
443 }
444 //-------- End of static function bound_check_y ------//
445
446
447 //-------- Begin of function SeekPath::result_node_distance ---------//
result_node_distance(ResultNode * node1,ResultNode * node2)448 inline short SeekPath::result_node_distance(ResultNode *node1, ResultNode *node2)
449 {
450 short xDist = abs(node1->node_x - node2->node_y);
451 #ifdef DEBUG
452 short yDist = abs(node1->node_y-node2->node_y);
453 #endif
454
455 if(xDist)
456 {
457 err_when(yDist && xDist!=yDist);
458 return xDist;
459 }
460 else // xDist = 0;
461 {
462 err_when(yDist==0);
463 return abs(node1->node_y-node2->node_y);
464 }
465 }
466 //-------- End of static function result_node_distance ------//
467
468
469 //-------- Begin of function SeekPath::init ---------//
init(int maxNode)470 void SeekPath::init(int maxNode)
471 {
472 max_node = maxNode;
473 node_array = (Node*) mem_add( max_node * sizeof(Node) );
474 node_matrix = (short*) mem_add(sizeof(short)*MAX_WORLD_X_LOC*MAX_WORLD_Y_LOC/4);
475
476 path_status = PATH_WAIT;
477 open_node_list.reset_priority_queue();
478 closed_node_list.reset_priority_queue();
479
480 reset_total_node_avail();
481 }
482 //--------- End of function SeekPath::init ---------//
483
484
485 //-------- Begin of function SeekPath::deinit ---------//
deinit()486 void SeekPath::deinit()
487 {
488 if( node_array )
489 {
490 mem_del(node_array);
491 node_array = NULL;
492 }
493
494 if( node_matrix )
495 {
496 mem_del(node_matrix);
497 node_matrix = NULL;
498 }
499 }
500 //--------- End of function SeekPath::deinit ---------//
501
502
503 //-------- Begin of function SeekPath::set_node_matrix ---------//
set_node_matrix(short reuseNodeMatrix[])504 void SeekPath::set_node_matrix(short reuseNodeMatrix[])
505 {
506 reuse_node_matrix_ptr = reuseNodeMatrix;
507 }
508 //--------- End of function SeekPath::set_node_matrix ---------//
509
510
511 //-------- Begin of function SeekPath::reset ---------//
reset()512 void SeekPath::reset()
513 {
514 path_status=PATH_WAIT;
515 open_node_list.reset_priority_queue();
516 closed_node_list.reset_priority_queue();
517 }
518 //--------- End of function SeekPath::reset ---------//
519
520
521 //-------- Begin of function SeekPath::reset_total_node_used ---------//
reset_total_node_avail()522 void SeekPath::reset_total_node_avail()
523 {
524 total_node_avail = MAX_BACKGROUND_NODE;
525 }
526 //--------- End of function SeekPath::reset_total_node_used ---------//
527
528
529 //-------- Begin of function SeekPath::set_attack_range_para ---------//
set_attack_range_para(int attackRange)530 void SeekPath::set_attack_range_para(int attackRange)
531 {
532 attack_range = attackRange;
533 }
534 //--------- End of function SeekPath::set_attack_range_para ---------//
535
536
537 //-------- Begin of function SeekPath::reset_attack_range_para ---------//
reset_attack_range_para()538 void SeekPath::reset_attack_range_para()
539 {
540 attack_range = 0;
541 }
542 //--------- End of function SeekPath::reset_attack_range_para ---------//
543
544
545 //-------- Begin of function SeekPath::set_nation_recno ---------//
546 // store the nation_recno of the unit calling searching
547 //
set_nation_recno(char nationRecno)548 void SeekPath::set_nation_recno(char nationRecno)
549 {
550 seek_nation_recno = nationRecno;
551 }
552 //--------- End of function SeekPath::set_nation_recno ---------//
553
554
555 //-------- Begin of function SeekPath::set_nation_passable ---------//
set_nation_passable(char nationPassable[])556 void SeekPath::set_nation_passable(char nationPassable[])
557 {
558 memcpy(nation_passable+1, nationPassable, sizeof(char)*MAX_NATION);
559 }
560 //--------- End of function SeekPath::set_nation_passable ---------//
561
562
563 //-------- Begin of function SeekPath::set_sub_mode ---------//
set_sub_mode(char subMode)564 void SeekPath::set_sub_mode(char subMode)
565 {
566 search_sub_mode = subMode;
567 }
568 //--------- End of function SeekPath::set_sub_mode ---------//
569
570
571 //-------- Begin of function SeekPath::add_result_node ---------//
add_result_node(int x,int y,ResultNode ** curPtr,ResultNode ** prePtr,int & count)572 inline void SeekPath::add_result_node(int x, int y, ResultNode** curPtr, ResultNode** prePtr, int& count)
573 {
574 (*curPtr)->node_x = x;
575 (*curPtr)->node_y = y;
576
577 err_when(count>1 && (abs((*curPtr)->node_x-(*prePtr)->node_x)>1 || abs((*curPtr)->node_y-(*prePtr)->node_y)>1));
578 *prePtr = *curPtr;
579 (*curPtr)++;
580 count++;
581 }
582 //--------- End of function SeekPath::add_result_node ---------//
583
584
585 //-------- Begin of function SeekPath::seek ---------//
586 //
587 // <int> sx, sy - the starting world location.
588 // <int> dx, dy - the destination world location.
589 // <DWORD> groupId - unit group id.
590 // <char> mobileType - mobile type, can be UNIT_AIR, UNIT_LAND or UNIT_SEA
591 //
592 // [int] searchMode - 1 SEARCH_MODE_IN_A_GROUP for one group with an unique group id (default)
593 // 2 SEARCH_MODE_A_UNIT_IN_GROUP for one sprite in a group
594 // 3 SERACH_MODE_TO_ATTACK for the searching that one sprite is ordered to attack its target
595 // 4 SEARCH_MODE_REUSE for path-reuse
596 // 5 SEARCH_MODE_BLOCKING for 2x2 unit blocking search
597 // 6 SEARCH_MODE_TO_FIRM for moving to a firm
598 // 7 SEARCH_MODE_TO_TOWN for moving to a town zone
599 // 8 SEARCH_MODE_TO_VEHICLE for moving to a vehicle
600 // 9 SEARCH_MODE_TO_WALL_FOR_GROUP for moving to a wall location
601 // 10 SEARCH_MODE_TO_WALL_FOR_UNIT for moving to a wall location
602 // 11 SEARCH_MODE_ATTACK_UNIT_BY_RANGE for range attacking target
603 // 12 SEARCH_MODE_ATTACK_FIRM_BY_RANGE ditto
604 // 13 SEARCH_MODE_ATTACK_TOWN_BY_RANGE ditto
605 // 14 SEARCH_MODE_ATTACK_WALL_BY_RANGE ditto
606 // 15 SEARCH_MODE_TO_LAND_FOR_SHIP for ships to move to land
607 // (default: 1)
608 //
609 // [int] miscNo - if searchMode = SEARCH_MODE_TO_ATTACK, meaning target_recno
610 // - if searchMode = SEARCH_MODE_TO_FIRM, meaning firm_id
611 // - if searchMode = SEARCH_MODE_TO_LAND_FOR_SHIP, meaning the region_id of the land moving to
612 // (default: 0)
613 //
614 // [int] numOfPath - for group assign, group settle. It is used to generate more set of virtual
615 // destination in the firm/town for searching.
616 //
617 // [int] maxTries - maximum no. of tries in the first seek action.
618 // this refer to the maximum no. of nodes created.
619 // (default : max_node)
620 //
621 // [int] borderX1, borderY1, - borders of the seek area in the world map
622 // borderX2, borderY2 (default: the whole map)
623 //
624 // Note: if maxTries==max_node, incremental seek (PATH_SEEKING) won't happen.
625 //
626 // return : <int> seekStatus - PATH_FOUND, PATH_SEEKING, PATH_NODE_USED_UP, or PATH_IMPOSSIBLE
627 // if PATH_FOUND, or PATH_NODE_USED_UP, can call get_result() to retrieve the result.
628 //
seek(int sx,int sy,int dx,int dy,uint32_t groupId,char mobileType,short searchMode,short miscNo,short numOfPath,int maxTries,int borderX1,int borderY1,int borderX2,int borderY2)629 int SeekPath::seek(int sx,int sy,int dx,int dy, uint32_t groupId, char mobileType,
630 short searchMode, short miscNo, short numOfPath, int maxTries,
631 int borderX1,int borderY1,int borderX2,int borderY2)
632 {
633 err_when(is_yielding);
634
635 if(total_node_avail<=0)
636 return PATH_FOUND; // checking
637
638 border_x1 = short(borderX1/2); // change to 2x2 node format
639 border_y1 = short(borderY1/2);
640 border_x2 = short(borderX2/2);
641 border_y2 = short(borderY2/2);
642
643 //-------- initialize vars --------------//
644 current_search_node_used = 0; // count the number of nodes used in each searching
645 path_status = PATH_SEEKING;
646 world_loc_matrix = world.loc_matrix;
647 open_node_list.reset_priority_queue();
648 closed_node_list.reset_priority_queue();
649
650 search_mode = searchMode;
651 group_id = groupId;
652 mobile_type = mobileType;
653 err_when(search_mode!=searchMode || group_id!=groupId || mobile_type!=mobileType);
654
655 //------------------------------------------------------------------------------//
656 // using another searching for unit sea or unit air
657 //------------------------------------------------------------------------------//
658 if(mobile_type!=UNIT_LAND)
659 return seek2(sx, sy, dx, dy, miscNo, numOfPath, maxTries); // redirect entry of UNIT_SEA or UNIT_AIR
660
661 //------------------------------------------------------------------------------//
662 // extract informaton from the parameter "miscNo"
663 //------------------------------------------------------------------------------//
664 target_recno = building_id = 0;
665 building_x1 = building_y1 = building_x2 = building_y2 = -1;
666
667 switch(search_mode)
668 {
669 case SEARCH_MODE_TO_ATTACK:
670 case SEARCH_MODE_TO_VEHICLE:
671 target_recno = miscNo;
672 break;
673
674 case SEARCH_MODE_TO_FIRM:
675 building_id = miscNo;
676 building_x1 = dx; // upper left corner location
677 building_y1 = dy;
678 search_firm_info = firm_res[building_id];
679 building_x2 = dx+search_firm_info->loc_width-1;
680 building_y2 = dy+search_firm_info->loc_height-1;
681 break;
682
683 case SEARCH_MODE_TO_TOWN:
684 building_id = miscNo;
685 building_x1 = dx; // upper left corner location
686 building_y1 = dy;
687 if(miscNo != -1)
688 {
689 Location* buildPtr = world.get_loc(dx, dy);
690 Town* targetTown = town_array[buildPtr->town_recno()];
691 building_x2 = targetTown->loc_x2;
692 building_y2 = targetTown->loc_y2;
693 }
694 else // searching to settle. Detail explained in function set_move_to_surround()
695 {
696 building_x2 = building_x1+STD_TOWN_LOC_WIDTH-1;
697 building_y2 = building_y1+STD_TOWN_LOC_HEIGHT-1;
698 }
699 break;
700
701 case SEARCH_MODE_ATTACK_UNIT_BY_RANGE:
702 case SEARCH_MODE_ATTACK_WALL_BY_RANGE:
703 building_id = miscNo;
704 building_x1 = MAX(dx-attack_range, 0);
705 building_y1 = MAX(dy-attack_range, 0);
706 building_x2 = MIN(dx+attack_range, MAX_WORLD_X_LOC-1);
707 building_y2 = MIN(dy+attack_range, MAX_WORLD_Y_LOC-1);
708 break;
709
710 case SEARCH_MODE_ATTACK_FIRM_BY_RANGE:
711 building_id = miscNo;
712 building_x1 = MAX(dx-attack_range, 0);
713 building_y1 = MAX(dy-attack_range, 0);
714 search_firm_info = firm_res[building_id];
715 building_x2 = MIN(dx+search_firm_info->loc_width-1+attack_range, MAX_WORLD_X_LOC-1);
716 building_y2 = MIN(dy+search_firm_info->loc_height-1+attack_range, MAX_WORLD_Y_LOC-1);
717 break;
718
719 case SEARCH_MODE_ATTACK_TOWN_BY_RANGE:
720 building_id = miscNo;
721 building_x1 = MAX(dx-attack_range, 0);
722 building_y1 = MAX(dy-attack_range, 0);
723 building_x2 = MIN(dx+STD_TOWN_LOC_WIDTH-1+attack_range, MAX_WORLD_X_LOC-1);
724 building_y2 = MIN(dy+STD_TOWN_LOC_HEIGHT-1+attack_range, MAX_WORLD_Y_LOC-1);
725 break;
726 }
727
728 //------------------------------------------------------------------------------//
729 // set start location and destination location
730 //------------------------------------------------------------------------------//
731 real_sour_x = sx;
732 real_sour_y = sy;
733
734 //---------- adjust destination for some kind of searching ------------//
735 int xShift, yShift, area;
736 short pathNum;
737 switch(search_mode)
738 {
739 case SEARCH_MODE_TO_FIRM:
740 case SEARCH_MODE_TO_TOWN:
741 final_dest_x = (building_x1+building_x2)/2; // the destination is set to be the middle of the building
742 final_dest_y = (building_y1+building_y2)/2;
743
744 //---------------------------------------------------------------------------------//
745 // for group assign/settle, the final destination is adjusted by the value of numOfPath
746 //---------------------------------------------------------------------------------//
747 if(search_mode==SEARCH_MODE_TO_TOWN)
748 area = STD_TOWN_LOC_WIDTH*STD_TOWN_LOC_HEIGHT;
749 else // search_mode == SEARCH_MODE_TO_FIRM
750 area = search_firm_info->loc_width*search_firm_info->loc_height;
751
752 pathNum = (numOfPath>area) ? (numOfPath-1)%area + 1 : numOfPath;
753
754 if(search_mode==SEARCH_MODE_TO_TOWN)
755 misc.cal_move_around_a_point(pathNum, STD_TOWN_LOC_WIDTH, STD_TOWN_LOC_HEIGHT, xShift, yShift);
756 else
757 misc.cal_move_around_a_point(pathNum, search_firm_info->loc_width, search_firm_info->loc_height, xShift, yShift);
758
759 final_dest_x += xShift;
760 final_dest_y += yShift;
761
762 bound_check_x(final_dest_x);
763 bound_check_y(final_dest_y);
764 break;
765
766 case SEARCH_MODE_ATTACK_UNIT_BY_RANGE:
767 case SEARCH_MODE_ATTACK_FIRM_BY_RANGE:
768 case SEARCH_MODE_ATTACK_TOWN_BY_RANGE:
769 case SEARCH_MODE_ATTACK_WALL_BY_RANGE:
770 final_dest_x = (building_x1+building_x2)/2; // the destination is set to be the middle of the building
771 final_dest_y = (building_y1+building_y2)/2;
772 break;
773
774 default:
775 final_dest_x = real_dest_x = dx;
776 final_dest_y = real_dest_y = dy;
777 break;
778 }
779
780 //--------------------------------------------------------------//
781 // change to 2x2 node format
782 //--------------------------------------------------------------//
783 int sourceX = short(sx/2); // the upper left corner is used
784 int sourceY = short(sy/2);
785 dest_x = short(final_dest_x/2);
786 dest_y = short(final_dest_y/2);
787
788 //-----------------------------------------//
789 // reset node_matrix
790 //-----------------------------------------//
791 if(search_mode!=SEARCH_MODE_REUSE)
792 {
793 max_node_num = 0xFFFF;
794 memset(node_matrix, 0, sizeof(short)*MAX_WORLD_X_LOC*MAX_WORLD_Y_LOC/4);
795 }
796 else
797 {
798 max_node_num = max_node;
799 memcpy(node_matrix, reuse_node_matrix_ptr, sizeof(short)*MAX_WORLD_X_LOC*MAX_WORLD_Y_LOC/4);
800 }
801
802 //--------- create the first node ---------//
803 node_count = 0;
804 result_node_ptr = NULL;
805
806 Node *nodePtr = node_array + node_count++;
807 memset(nodePtr, 0, sizeof(Node));
808
809 //-------- store the upper left coordinate of the node ----------//
810 upper_left_x = sourceX<<1;
811 upper_left_y = sourceY<<1;
812
813 //---------- calculate the node type -----------//
814 nodePtr->node_type = 0;
815 nodePtr->node_type = (can_move_to(upper_left_x,upper_left_y))+(can_move_to(upper_left_x+1,upper_left_y)<<1)+
816 (can_move_to(upper_left_x,upper_left_y+1)<<2)+(can_move_to(upper_left_x+1,upper_left_y+1)<<3);
817
818 if(searchMode==SEARCH_MODE_A_UNIT_IN_GROUP || searchMode==SEARCH_MODE_TO_WALL_FOR_UNIT) // plus the self-location
819 nodePtr->node_type += (real_sour_x>upper_left_x)?2+(real_sour_y-upper_left_y)*6:1+(real_sour_y-upper_left_y)*3;
820 else
821 {
822 /*if(searchMode==SEARCH_MODE_TO_FIRM || searchMode==SEARCH_MODE_TO_TOWN) // plus the self-location
823 {
824 if(real_sour_x<building_x1 || real_sour_x>building_x2 ||
825 real_sour_y<building_y1 || real_sour_y>building_y2)
826 nodePtr->node_type += (real_sour_x>upper_left_x)?2+(real_sour_y-upper_left_y)*6:1+(real_sour_y-upper_left_y)*3;
827 }*/
828 }
829
830 err_when(nodePtr->node_type>15 || nodePtr->node_type <0);
831
832 int destUpperLeftX = dest_x<<1;
833 int destUpperLeftY = dest_y<<1;
834 is_dest_blocked = !((can_move_to(destUpperLeftX,destUpperLeftY))+(can_move_to(destUpperLeftX+1,destUpperLeftY)<<1)+
835 (can_move_to(destUpperLeftX,destUpperLeftY+1)<<2)+(can_move_to(destUpperLeftX+1,destUpperLeftY+1)<<3));
836 // whether the destination is blocked, if so, only search till the destination's neighbor locations
837
838 nodePtr->node_g = 0;
839 nodePtr->node_h = (sourceX-dest_x)*(sourceX-dest_x)+(sourceY-dest_y)*(sourceY-dest_y); // should really use sqrt().
840 nodePtr->node_f = nodePtr->node_g + nodePtr->node_h;
841 nodePtr->node_x = sourceX;
842 nodePtr->node_y = sourceY;
843 nodePtr->enter_direction = 0;
844 open_node_list.insert_node(nodePtr); // make Open List point to first node
845
846 //--- if the destination is the current postion or next to it & the dest is occupied ---//
847 if( sourceX==dest_x && sourceY==dest_y )
848 {
849 path_status = PATH_FOUND;
850 result_node_ptr = nodePtr;
851 return path_status;
852 }
853
854 //------------ seek now ------------------//
855 int maxNode = (!maxTries) ? max_node : maxTries;
856 return continue_seek(maxNode, 1); // 1-first seek session of the current seek order
857 }
858 //-------- End of function SeekPath::seek ---------//
859
860
861 //---- Begin of function SeekPath::continue_seek ---------//
862 //
863 // If the last seek operation does not find the whole path,
864 // continue the search.
865 //
866 // <int> maxTries - maximum path seeking tries
867 // [char] firstSeek - whether it's the first seek session of the seek order.
868 // (default: 0)
869 //
870 // return : <int> seekStatus - PATH_FOUND, PATH_SEEKING, PATH_NODE_USED_UP,
871 // or PATH_IMPOSSIBLE
872 //
873 // You can call get_result() to retrieve the result.
874 //
continue_seek(int maxTries,char firstSeek)875 int SeekPath::continue_seek(int maxTries, char firstSeek)
876 {
877 if( path_status != PATH_SEEKING )
878 return path_status;
879
880 //------- aliasing class member vars for fast access ------//
881 cur_seek_path = this;
882 cur_dest_x = dest_x;
883 cur_dest_y = dest_y;
884 cur_node_matrix = node_matrix;
885 cur_node_array = node_array;
886
887 cur_border_x1 = border_x1;
888 cur_border_y1 = border_y1;
889 cur_border_x2 = border_x2;
890 cur_border_y2 = border_y2;
891
892 //------ seek the path using the A star algorithm -----//
893 int maxNode = (total_node_avail<maxTries) ? total_node_avail : maxTries;
894 maxNode -= MAX_CHILD_NODE; // generate_successors() can generate a MAX of MAX_CHILD_NODE new nodes per call
895 Node *bestNodePtr;
896
897 int i;
898 for(i=0; i<maxNode; i++)
899 {
900 bestNodePtr = return_best_node();
901
902 //if(i%20==0)
903 // sys_yield(); // update cursor position
904
905 //---- even if the path is impossible, get the closest path ----//
906 if( !bestNodePtr )
907 {
908 path_status = PATH_IMPOSSIBLE;
909 break;
910 }
911
912 //----- exceed the object's MAX's node limitation, return the closest path ----//
913 if( node_count >= maxNode )
914 {
915 path_status = PATH_NODE_USED_UP;
916 break;
917 }
918
919 //---------------------------------------------------------------//
920 // If the path is found OR If the destination is blocked,
921 // consider it done when we are next to it.
922 //---------------------------------------------------------------//
923 if( (bestNodePtr->node_x==dest_x && bestNodePtr->node_y==dest_y) ||
924 ( is_dest_blocked && abs(bestNodePtr->node_x-dest_x)<=0 && abs(bestNodePtr->node_y-dest_y)<=0 ) )
925 {
926 path_status = PATH_FOUND;
927 result_node_ptr = bestNodePtr;
928 break;
929 }
930
931 //--------- generate successors -------//
932 if(bestNodePtr->generate_successors(bestNodePtr->enter_direction, real_sour_x, real_sour_y))
933 {
934 path_status = PATH_REUSE_FOUND;
935 result_node_ptr = reuse_result_node_ptr;
936 break;
937 }
938 }
939
940 err_when( cur_stack_pos!=0 ); // it should be zero all the times, all pushes should have been poped
941 current_search_node_used = i+1; // store the number of nodes used in this searching
942 return path_status;
943 }
944 //------ End of function SeekPath::continue_seek ---------//
945
946
947 //---- Begin of function SeekPath::get_result ---------//
948 //
949 // Compile the seek result nodes using results processed by
950 // seek() and continue_seek() and store the results in
951 // an array of ResultNode.
952 //
953 // <int&> resultNodeCount - a reference var for returning the no. of result nodes.
954 // <short&> pathDist - a reference var for returning the total distance of the result path
955 //
956 // return : <ResultNode*> an array of ResultNode.
957 // the caller function is responsible for
958 // freeing the memory of the array.
959 //
get_result(int & resultNodeCount,short & pathDist)960 ResultNode* SeekPath::get_result(int& resultNodeCount, short& pathDist)
961 {
962 if(mobile_type!=UNIT_LAND)
963 return get_result2(resultNodeCount, pathDist); // redirect entry point for UNIT_SEA or UNIT_AIR
964
965 resultNodeCount = pathDist = 0;
966 if(total_node_avail<=0)
967 return NULL;
968
969 total_node_avail -= current_search_node_used;
970 short useClosestNode = 0; // indicate whether closest node is returned instead of the actual node
971
972 if(!result_node_ptr) // if PATH_IMPOSSIBLE or PATH_NODE_USED_UP, result_node_ptr is NULL, we need to call get_closest_node() to get the closest node.
973 {
974 result_node_ptr = return_closest_node();
975 useClosestNode = 1;
976
977 if(!result_node_ptr)
978 return NULL;
979 }
980
981 //--------------------------------------------------//
982 // Trace backwards to the starting node, and rationalize
983 // nodes (i.e. group nodes of the same direction into
984 // single nodes.)
985 //--------------------------------------------------//
986 Node* nodePtr = result_node_ptr; // the node current being processed
987 Node* baseNodePtr = result_node_ptr; // the first end node for connecting the other end node for the path in that direction.
988 Node* parentNode = nodePtr->parent_node; // the parent node of nodePtr
989 Node* childNodePtr = nodePtr; // it should point to the children node of nodePtr
990
991 //------------------------------------------------------------------------
992 // there are only one node, source & destination within the same 2x2 node
993 //------------------------------------------------------------------------
994 if(!parentNode) // parentNode==0 when the source location is the desination already
995 {
996 if((real_sour_x!=final_dest_x || real_sour_y!=final_dest_y) && abs(real_sour_x-final_dest_x)<=1 &&
997 abs(real_sour_y-final_dest_y)<=1 && can_move_to(final_dest_x, final_dest_y))
998 {
999 pathDist = 1;
1000
1001 ResultNode* resultNodeArray1 = (ResultNode*) mem_add(sizeof(ResultNode)*2);
1002 ResultNode* resultNodePtr1 = resultNodeArray1;
1003 resultNodeCount=2;
1004 resultNodePtr1->node_x = real_sour_x;
1005 resultNodePtr1->node_y = real_sour_y;
1006 resultNodePtr1++;
1007 resultNodePtr1->node_x = final_dest_x;
1008 resultNodePtr1->node_y = final_dest_y;
1009 return resultNodeArray1;
1010 }
1011 else
1012 return NULL;
1013 }
1014
1015 resultNodeCount=1; // including the current node
1016
1017 //===================================
1018 // count the number of 2x2 node
1019 //===================================
1020 int numOfNode=0;
1021 Node* curPtr = result_node_ptr;
1022
1023 while(curPtr != NULL)
1024 {
1025 curPtr = curPtr->parent_node;
1026 numOfNode++;
1027 }
1028
1029 //sys_yield(); // update cursor position
1030
1031 //---------------------------------
1032 // otherwise, there are more than one node
1033 //---------------------------------
1034 node_count=0;
1035
1036 ResultNode* maxSizeResultNodeArray; // store all the result node in the reverse order, the turning point will be extracted later
1037 int nodeAllocated = (numOfNode+1)<<1;//numOfNode*2+2; // the additional 2 is for the starting node
1038
1039 maxSizeResultNodeArray = (ResultNode*) mem_add(nodeAllocated*sizeof(ResultNode));
1040 max_size_result_node_ptr = maxSizeResultNodeArray;
1041 parent_result_node_ptr = maxSizeResultNodeArray;
1042
1043 //----------------------------------
1044 // start from the destination point
1045 //----------------------------------
1046 memset(max_size_result_node_ptr, 0, sizeof(ResultNode)*nodeAllocated);
1047 int upper_left_x = nodePtr->node_x<<1;
1048 int upper_left_y = nodePtr->node_y<<1;
1049 short xCount, yCount; // for counting
1050
1051 if(!useClosestNode && (search_mode==SEARCH_MODE_TO_ATTACK || search_mode==SEARCH_MODE_TO_VEHICLE ||
1052 can_move_to(final_dest_x, final_dest_y)))
1053 {
1054 max_size_result_node_ptr->node_x = final_dest_x;
1055 max_size_result_node_ptr->node_y = final_dest_y;
1056 }
1057 else
1058 { // use closest node
1059
1060 max_size_result_node_ptr->node_x = MAX_WORLD_X_LOC;
1061 max_size_result_node_ptr->node_y = MAX_WORLD_Y_LOC;
1062
1063 int newValue, xSquare, yDiff;
1064 int compareValue = 0x7FFFFFFF; // should > 199^2 + 199^2
1065
1066 for(xCount=upper_left_x+1; xCount>=upper_left_x; xCount--)
1067 {
1068 xSquare = int(final_dest_x-xCount)*(final_dest_x-xCount);
1069 for(yCount=upper_left_y+1, yDiff=final_dest_y-yCount; yCount>=upper_left_y; yCount--, yDiff++)
1070 {
1071 if(can_move_to(xCount, yCount) && (newValue = xSquare + yDiff*yDiff)<compareValue)
1072 {
1073 max_size_result_node_ptr->node_x = xCount;
1074 max_size_result_node_ptr->node_y = yCount;
1075 compareValue = newValue;
1076 }
1077 }
1078 }
1079
1080 err_when(max_size_result_node_ptr->node_x==MAX_WORLD_X_LOC &&
1081 max_size_result_node_ptr->node_y==MAX_WORLD_Y_LOC);
1082
1083 final_dest_x = max_size_result_node_ptr->node_x;
1084 final_dest_y = max_size_result_node_ptr->node_y;
1085 }
1086 xCount = max_size_result_node_ptr->node_x;
1087 yCount = max_size_result_node_ptr->node_y;
1088 max_size_result_node_ptr++; // note: parent_result_node_ptr don't move for this case
1089 node_count++;
1090
1091 //---------------------------------------------------
1092 // process the end node if passing through two points
1093 //---------------------------------------------------
1094 int xLoc, yLoc;
1095 switch(nodePtr->enter_direction)
1096 {
1097 case 1:
1098 if(upper_left_x < xCount)
1099 {
1100 yLoc = can_move_to(upper_left_x, yCount) ? yCount : ((yCount>upper_left_y)?upper_left_y:upper_left_y+1);
1101 add_result_node(upper_left_x, yLoc, &max_size_result_node_ptr, &parent_result_node_ptr, node_count);
1102 }
1103 break;
1104
1105 case 2: if((upper_left_x!=xCount) || ((upper_left_y+1)!=yCount))
1106 add_result_node(upper_left_x, upper_left_y+1, &max_size_result_node_ptr, &parent_result_node_ptr, node_count);
1107 break;
1108
1109 case 3:
1110 if(upper_left_y == yCount)
1111 {
1112 xLoc = can_move_to(xCount,upper_left_y+1) ? xCount : ((xCount>upper_left_x)?upper_left_x:(upper_left_x+1));
1113 add_result_node(xLoc, upper_left_y+1, &max_size_result_node_ptr, &parent_result_node_ptr, node_count);
1114 }
1115 break;
1116
1117 case 4: if(((upper_left_x+1)!=xCount) || ((upper_left_y+1)!=yCount))
1118 add_result_node(upper_left_x+1, upper_left_y+1, &max_size_result_node_ptr, &parent_result_node_ptr, node_count);
1119 break;
1120
1121 case 5:
1122 if(upper_left_x == final_dest_x)
1123 {
1124 yLoc = can_move_to(upper_left_x+1,yCount) ? yCount : ((yCount>upper_left_y)?upper_left_y:(upper_left_y+1));
1125 add_result_node(upper_left_x+1, yLoc, &max_size_result_node_ptr, &parent_result_node_ptr, node_count);
1126 }
1127 break;
1128
1129 case 6: if(((upper_left_x+1)!=xCount) || (upper_left_y!=yCount))
1130 add_result_node(upper_left_x+1, upper_left_y, &max_size_result_node_ptr, &parent_result_node_ptr, node_count);
1131 break;
1132
1133 case 7:
1134 if(upper_left_y != yCount)
1135 {
1136 xLoc = can_move_to(xCount,upper_left_y) ? xCount : ((xCount>upper_left_x)?upper_left_x:(upper_left_x+1));
1137 add_result_node(xLoc, upper_left_y, &max_size_result_node_ptr, &parent_result_node_ptr, node_count);
1138 }
1139 break;
1140
1141 case 8: if((upper_left_x!=xCount) || (upper_left_y!=yCount))
1142 add_result_node(upper_left_x, upper_left_y, &max_size_result_node_ptr, &parent_result_node_ptr, node_count);
1143 break;
1144
1145 default:
1146 err_now("error in processing the end node");
1147 break;
1148 }
1149 nodePtr = nodePtr->parent_node; // next 2x2 node
1150
1151 //preNodeCount = node_count;
1152 err_when(node_count+nodePtr->node_g+2 > nodeAllocated);
1153
1154 //--------------------------------------------------
1155 // get the actual path, process from the second node
1156 //--------------------------------------------------
1157 //int yieldCount = 0;
1158 while( (parentNode=nodePtr->parent_node) != NULL )
1159 {
1160 upper_left_x = nodePtr->node_x<<1;
1161 upper_left_y = nodePtr->node_y<<1;
1162 get_real_result_node(node_count, nodePtr->enter_direction,(childNodePtr->enter_direction+3)%8+1,
1163 nodePtr->node_type, upper_left_x, upper_left_y);
1164 childNodePtr = nodePtr;
1165 nodePtr = parentNode;
1166
1167 err_when(node_count+nodePtr->node_g+2 > nodeAllocated);
1168 //yieldCount++;
1169 //if(yieldCount%30==0)
1170 // sys_yield();
1171 }
1172
1173 //sys_yield(); // update cursor position
1174
1175 //----------------------------------------------------
1176 // process the starting node
1177 // nodePtr points at the starting node now
1178 //----------------------------------------------------
1179 if(abs(parent_result_node_ptr->node_x-real_sour_x)>1 || abs(parent_result_node_ptr->node_y-real_sour_y)>1)
1180 { // passing through two points
1181 upper_left_x = nodePtr->node_x<<1;
1182 upper_left_y = nodePtr->node_y<<1;
1183 switch(childNodePtr->enter_direction)
1184 {
1185 case 1:
1186 max_size_result_node_ptr->node_x = upper_left_x+1;
1187 if((can_move_to(upper_left_x+1, real_sour_y)&&(real_sour_y==upper_left_y)) ||
1188 (!can_move_to(upper_left_x+1, real_sour_y)&&(real_sour_y>upper_left_y)))
1189 max_size_result_node_ptr->node_y = upper_left_y;
1190 else
1191 max_size_result_node_ptr->node_y = (upper_left_y+1);
1192 break;
1193
1194 case 2:
1195 max_size_result_node_ptr->node_x = upper_left_x+1;
1196 max_size_result_node_ptr->node_y = upper_left_y;
1197 break;
1198
1199 case 3:
1200 max_size_result_node_ptr->node_y = upper_left_y;
1201 if((can_move_to(real_sour_x, upper_left_y)&&(real_sour_x==upper_left_x)) ||
1202 (!can_move_to(real_sour_x, upper_left_y)&&(real_sour_x>upper_left_x)))
1203 max_size_result_node_ptr->node_x = upper_left_x;
1204 else
1205 max_size_result_node_ptr->node_x = upper_left_x+1;
1206 break;
1207
1208 case 4:
1209 max_size_result_node_ptr->node_x = upper_left_x;
1210 max_size_result_node_ptr->node_y = upper_left_y;
1211 break;
1212
1213 case 5:
1214 max_size_result_node_ptr->node_x = upper_left_x;
1215 if((can_move_to(upper_left_x, real_sour_y)&&(real_sour_y==upper_left_y)) ||
1216 (!can_move_to(upper_left_x, real_sour_y)&&(real_sour_y>upper_left_y)))
1217 max_size_result_node_ptr->node_y = upper_left_y;
1218 else
1219 max_size_result_node_ptr->node_y = upper_left_y+1;
1220 break;
1221
1222 case 6:
1223 max_size_result_node_ptr->node_x = upper_left_x;
1224 max_size_result_node_ptr->node_y = upper_left_y+1;
1225 break;
1226
1227 case 7:
1228 max_size_result_node_ptr->node_y = upper_left_y+1;
1229 if((can_move_to(real_sour_x, upper_left_y+1)&&(real_sour_x==upper_left_x)) ||
1230 (!can_move_to(real_sour_x, upper_left_y+1)&&(real_sour_x>upper_left_x)))
1231 max_size_result_node_ptr->node_x = upper_left_x;
1232 else
1233 max_size_result_node_ptr->node_x = upper_left_x+1;
1234 break;
1235
1236 case 8:
1237 max_size_result_node_ptr->node_x = upper_left_x+1;
1238 max_size_result_node_ptr->node_y = upper_left_y+1;
1239 break;
1240
1241 default:
1242 err_now("error in processing the start node");
1243 break;
1244
1245
1246 }
1247
1248 err_when((max_size_result_node_ptr->node_x==real_sour_x) && (max_size_result_node_ptr->node_y==real_sour_y));
1249 parent_result_node_ptr++;
1250 max_size_result_node_ptr++;
1251 node_count++;
1252 }
1253 max_size_result_node_ptr->node_x = real_sour_x;
1254 max_size_result_node_ptr->node_y = real_sour_y;
1255 node_count++;
1256
1257 err_when(nodePtr->node_g || node_count>nodeAllocated);
1258 debug_check_path(maxSizeResultNodeArray, node_count); //*** debug only
1259
1260 ResultNode* result_node_pointer;
1261 maxSizeResultNodeArray = smooth_the_path(maxSizeResultNodeArray, resultNodeCount);
1262
1263 //sys_yield(); // update cursor position
1264 debug_check_path(maxSizeResultNodeArray, resultNodeCount); //*** debug only
1265
1266 //-------------------------------------------------------------------//
1267 // After the above process, here we will have a link of rationalize
1268 // nodes. Retrieve them in the backwards order
1269 //-------------------------------------------------------------------//
1270 ResultNode *resultNodeArray = (ResultNode*) mem_add( sizeof(ResultNode) * resultNodeCount );
1271 ResultNode *resultNodePtr = resultNodeArray+resultNodeCount-1;
1272 int processCount = 1;
1273
1274 ResultNode *preNodePtr = maxSizeResultNodeArray;
1275 *resultNodePtr = *preNodePtr;
1276 resultNodePtr--;
1277
1278 result_node_pointer = maxSizeResultNodeArray+1;
1279 err_when(pathDist!=0);
1280
1281 int xDist, yDist;
1282 //yieldCount = 0;
1283
1284 while(processCount++ < resultNodeCount)
1285 {
1286 err_when(result_node_pointer->node_x<0 || result_node_pointer->node_x>=MAX_WORLD_X_LOC ||
1287 result_node_pointer->node_y<0 || result_node_pointer->node_y>=MAX_WORLD_Y_LOC);
1288
1289 *resultNodePtr = *result_node_pointer;
1290 resultNodePtr--;
1291
1292 xDist = abs(result_node_pointer->node_x-preNodePtr->node_x);
1293 yDist = abs(result_node_pointer->node_y-preNodePtr->node_y);
1294 err_when((!xDist && !yDist) || (xDist && yDist && xDist!=yDist));
1295 pathDist += (xDist) ? xDist : yDist;
1296
1297 preNodePtr++;
1298 result_node_pointer++;
1299
1300 //yieldCount++;
1301 //if(yieldCount%35==0)
1302 // sys_yield();
1303 }
1304
1305 err_when(nodeAllocated<node_count);
1306 mem_del(maxSizeResultNodeArray);
1307
1308 //======================================================================//
1309 #ifdef DEBUG
1310 if(search_sub_mode==SEARCH_SUB_MODE_PASSABLE && resultNodeCount>1)
1311 {
1312 err_when(mobile_type!=UNIT_LAND);
1313 debug_check_sub_mode(resultNodeArray, resultNodeCount);
1314 }
1315 #endif
1316 //======================================================================//
1317
1318 return resultNodeArray;
1319 }
1320 //------ End of function SeekPath::get_result ---------//
1321
1322
1323 //---- Begin of function SeekPath::get_real_result_node ---------//
1324 //
1325 // called by get_result to extract the point in a 2x2 node that is
1326 // used in the shortest path
1327 //
1328 // <int&> count - a reference var for counting number of node in
1329 // max_size_result_node_ptr
1330 //
get_real_result_node(int & count,short enterDirection,short exitDirection,short nodeType,short xCoord,short yCoord)1331 void SeekPath::get_real_result_node( int &count, short enterDirection, short exitDirection,
1332 short nodeType, short xCoord, short yCoord)
1333 {
1334 short ma, mb, mc, md; // | a b | four elements of a 2x2 matrix
1335 // | c d | these values are either 0 or 1
1336 short mTmp; // used in swapping
1337 short atEdge; // at_edge = 1 if exitDirection is at the edge, otherwise 0 for corner
1338 short rotateAngle; // rotate angle clockwisely = its value*90 degree, value ranges from 0 to 3
1339 short furtherCheck; // indicate further checking is needed in finding a path in the node
1340 short rotatedEnterDirection; // reference enter direction after rotation
1341
1342 ma = nodeType&0x1;
1343 mb = (nodeType&0x2)>>1;
1344 mc = (nodeType&0x4)>>2;
1345 md = (nodeType&0x8)>>3;
1346
1347 err_when((ma+(mb<<1)+(mc<<2)+(md<<3)) != nodeType);
1348 atEdge = exitDirection%2;
1349 rotateAngle = short((exitDirection-1)/2);
1350 furtherCheck = 0; // may be used only if enterDirection and exitDirection are opposite to each other
1351
1352 int exitArrowLeft = 0;
1353 int exitArrowRight = 0;
1354 int enterArrowLeft = 0;
1355 int enterArrowRight = 0;
1356 if(atEdge) // exit at the edge
1357 {
1358 //---------------------------------------------------------------------//
1359 // -------
1360 // exitArrowRight |1 |2 |
1361 // <--------|-------|
1362 // exitArrowLeft |3 |4 |
1363 // -------
1364 // There are 2 possible choice for the previous node to select. One is
1365 // the point left of 1, and the other is the point left of 3. Since there
1366 // are four possible edge exiting cases, it call be represented by rotated
1367 // the above figure by 90 degree each.
1368 //
1369 // if the point left of 1 is chosen, exitArrowRight = 1
1370 // if the point left of 3 is chosen, exitArrowLeft = 1
1371 // the flag exitArrowLeft and exitArrowRight is used to generate a better
1372 // result path shape.
1373 //---------------------------------------------------------------------//
1374
1375 switch(exitDirection)
1376 {
1377 case 1: if(parent_result_node_ptr->node_y%2)
1378 exitArrowLeft = 1;
1379 else
1380 exitArrowRight = 1;
1381 break;
1382
1383 case 3: if(parent_result_node_ptr->node_x%2)
1384 exitArrowLeft = 1;
1385 else
1386 exitArrowRight = 1;
1387 break;
1388
1389 case 5: if(parent_result_node_ptr->node_y%2)
1390 exitArrowRight = 1;
1391 else
1392 exitArrowLeft = 1;
1393 break;
1394
1395 case 7: if(parent_result_node_ptr->node_x%2)
1396 exitArrowRight = 1;
1397 else
1398 exitArrowLeft = 1;
1399 break;
1400
1401 default: err_here();
1402 break;
1403 }
1404 }
1405 else // exit at edge
1406 {
1407 if(enterDirection%2) // enter at the edge
1408 {
1409 //---------------------------------------------------------------------//
1410 // -------
1411 // enterArrowLeft |1 |2 |
1412 // -------->|-------|
1413 // enterArrowRight|3 |4 |
1414 // -------
1415 // There are 2 possible choice for the next node to select. One is
1416 // the point left of 1, and the other is the point left of 3. Since there
1417 // are four possible edge entering cases, it call be represented by rotated
1418 // the above figure by 90 degree each time.
1419 //
1420 // if the point left of 1 is chosen, enterArrowLeft = 1
1421 // if the point left of 3 is chosen, enterArrowRight = 1
1422 // the flag enterArrowLeft and enterArrowRight is used to generate a better
1423 // result path shape.
1424 //---------------------------------------------------------------------//
1425
1426 switch(enterDirection)
1427 {
1428 case 1: if(can_move_to(xCoord-1, yCoord))
1429 enterArrowLeft = 1;
1430 if(can_move_to(xCoord-1, yCoord+1))
1431 enterArrowRight = 1;
1432 break;
1433
1434 case 3: if(can_move_to(xCoord, yCoord+2))
1435 enterArrowLeft = 1;
1436 if(can_move_to(xCoord+1, yCoord+2))
1437 enterArrowRight = 1;
1438 break;
1439
1440 case 5: if(can_move_to(xCoord+2, yCoord+1))
1441 enterArrowLeft = 1;
1442 if(can_move_to(xCoord+2, yCoord))
1443 enterArrowRight = 1;
1444 break;
1445
1446 case 7: if(can_move_to(xCoord+1, yCoord-1))
1447 enterArrowLeft = 1;
1448 if(can_move_to(xCoord, yCoord-1))
1449 enterArrowRight = 1;
1450 break;
1451
1452 default: err_here();
1453 break;
1454 }
1455 }
1456 }
1457
1458 //----------------------------------------------------------------
1459 // perform rotation such that the exit direction is either 1 or 2
1460 //----------------------------------------------------------------
1461 switch(exitDirection)
1462 { case 1: case 2:
1463 break;
1464
1465 case 3: case 4: // rotate clockwise 90 degree
1466 //(((mTmp = mb), mb = ma), ma = mc), mc = md;
1467 mTmp = mb;
1468 mb = ma;
1469 ma = mc;
1470 mc = md;
1471 md = mTmp;
1472 break;
1473
1474 case 5: case 6: // rotate clockwise 180 degree
1475 mTmp = md;
1476 md = ma;
1477 ma = mTmp;
1478 mTmp = mb;
1479 mb = mc;
1480 mc = mTmp;
1481 break;
1482
1483 case 7: case 8: // rotate clockwise 270 degree
1484 mTmp = ma;
1485 ma = mb;
1486 mb = md;
1487 md = mc;
1488 mc = mTmp;
1489 break;
1490 default:
1491 err_now("exitDirection error");
1492 break;
1493 }
1494
1495 rotatedEnterDirection = (enterDirection-(rotateAngle<<1)+7)%8+1; // store angle rotated for reverse rotation later
1496 err_when(rotatedEnterDirection>8 || rotatedEnterDirection <1);
1497
1498 //-----------------------------------------
1499 // set the value of the matrix element to
1500 // 1 for the possible answer, the rest is 0
1501 //-----------------------------------------
1502 if(atEdge) // the case for the exit direction at 1
1503 { //------------------- at edge ------------------------//
1504 switch(rotatedEnterDirection)
1505 {
1506 case 1:
1507 err_now("unexpected case at edge");
1508 break;
1509
1510 case 2:
1511 err_when(!mc);
1512 mc = 1; // must be
1513 ma = mb = md = 0;
1514 break;
1515
1516 case 3:
1517 // there are two possible paths
1518 if(mc) // check for the perfered path
1519 ma = mb = md = 0;
1520 else
1521 {
1522 err_when((!ma) || (!md));
1523 mb = 0;
1524 }
1525 // ma, md should be 1
1526 break;
1527
1528 case 4:
1529 err_when(!md); // md should be 1
1530 mb = 0;
1531 err_when((!mc) && (!ma));
1532
1533 if(exitArrowLeft)
1534 ma = 1-mc; // either one is used, prefer mc
1535 else // should be exitArrowRight
1536 mc = 1-ma; // either one is used, prefer ma
1537 break;
1538
1539 case 5:
1540 if(ma&&mb)
1541 { // one path (bar state) exists
1542 if(mc&&md)
1543 furtherCheck = 1;// both paths exist
1544 else
1545 mc = md = 0; // choose ma, mb
1546 }
1547 else if(mc&&md)
1548 ma = mb = 0; // choose mc, md
1549 else
1550 err_when(((!ma)&&(!mc)) && ((!mb)&&(!md)));
1551 // else, only one path exists, do nothing
1552 break;
1553
1554 case 6: // similar to case 4
1555 err_when(!mb); // mb should be 1
1556 md = 0;
1557 err_when((!ma)&&(!mc));
1558
1559 if(exitArrowLeft)
1560 ma = 1-mc; // either one is used, prefer mc
1561 else // should be exitArrowRight
1562 mc = 1-ma; // either one is used, prefer ma
1563 break;
1564
1565 case 7: // similar to case 3
1566 if(ma)
1567 mb = mc = md = 0;
1568 else
1569 {
1570 err_when((!mb)||(!mc));
1571 md = 0; // mb, mc should be 1
1572 }
1573 break;
1574
1575 case 8:
1576 err_when(!ma);
1577 ma = 1; // must be
1578 mb = mc = md = 0;
1579 break;
1580
1581 default:
1582 err_now("at edge error");
1583 break;
1584 }
1585 }
1586 else
1587 { //---------------------------- at corner-------------------------//
1588 // the case for the exit direction at 2
1589 switch(rotatedEnterDirection)
1590 {
1591 case 1: case 3:
1592 err_when(!mc);
1593 mc = 1; // must be
1594 ma = mb = md = 0;
1595 break;
1596
1597 case 2:
1598 err_now("unexpected case at corner");
1599 break;
1600
1601 case 4:
1602 err_when((!mc)||(!md));
1603 mc = md = 1; // must be
1604 ma = mb = 0;
1605 break;
1606
1607 case 5:
1608 err_when(!mc);
1609 mc = 1; // must be
1610 ma = 0;
1611 err_when((!mb)&&(!md));
1612
1613 if(!enterArrowLeft) // the enter arrow left location canot be walked
1614 md = 1-mb; // either one is used, prefer mb
1615 else
1616 mb = 1-md; // either one is used, prefer md
1617 break;
1618
1619 case 6:
1620 err_when((!mb)||(!mc));
1621 mb = mc = 1;
1622 ma = md = 0;
1623 break;
1624
1625 case 7:
1626 err_when(!mc);
1627 mc = 1; // must be
1628 md = 0;
1629 err_when((!ma)&&(!mb));
1630
1631 if(!enterArrowRight)
1632 ma = 1-mb; // either one is used, prefer mb
1633 else
1634 mb = 1-ma; // either one is used, prefer ma
1635 break;
1636
1637 case 8:
1638 err_when((!ma)||(!mc));
1639 ma = mc = 1; // must be
1640 mb = md = 0;
1641 break;
1642
1643 default:
1644 err_now("at corner error");
1645 break;
1646 }
1647
1648 }
1649
1650 //--------------------------- reverse rotation ----------------------------//
1651 switch(exitDirection)
1652 { case 1: case 2:
1653 break;
1654
1655 case 3: case 4: // rotate clockwise 270 degree
1656 mTmp = ma;
1657 ma = mb;
1658 mb = md;
1659 md = mc;
1660 mc = mTmp;
1661 break;
1662
1663 case 5: case 6: // rotate clockwise 180 degree
1664 mTmp = md;
1665 md = ma;
1666 ma = mTmp;
1667 mTmp = mb;
1668 mb = mc;
1669 mc = mTmp;
1670 break;
1671
1672 case 7: case 8: // rotate clockwise 90 degree
1673 mTmp = mb;
1674 mb = ma;
1675 ma = mc;
1676 mc = md;
1677 md = mTmp;
1678 break;
1679
1680 default:
1681 err_now("exitDirection error");
1682 break;
1683 }
1684
1685 //------------------- get the answer ----------------------//
1686 switch(exitDirection)
1687 {
1688 case 1:
1689 if(!furtherCheck)
1690 {
1691 add_result_node(xCoord, yCoord+1-ma, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1692 err_when(mb && md);
1693 if(mb||md) // at most one is 1
1694 add_result_node(xCoord+1, yCoord+1-mb, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1695 }
1696 else
1697 {
1698 if(parent_result_node_ptr->node_y == yCoord)
1699 { // use upper path
1700 add_result_node(xCoord, yCoord, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1701 add_result_node(xCoord+1, yCoord, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1702 }
1703 else
1704 { // use lower path
1705 add_result_node(xCoord, yCoord+1, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1706 add_result_node(xCoord+1, yCoord+1, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1707 }
1708 }
1709 break;
1710
1711 case 2:
1712 err_when(!mc);
1713 if(mc)
1714 add_result_node(xCoord, yCoord+1, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1715 // else, error
1716
1717 err_when(ma+mb+md>1); //(ma&&mb) || (ma&&md) || (mb&&md))
1718 if(ma||mb||md) // at most one is 1
1719 add_result_node(xCoord+1-ma, yCoord+md, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1720 break;
1721
1722 case 3:
1723 if(!furtherCheck)
1724 {
1725 add_result_node(xCoord+1-mc, yCoord+1, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1726
1727 err_when(ma&&mb);
1728 if(ma||mb) // at most one is 1
1729 add_result_node(xCoord+1-ma, yCoord, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1730 }
1731 else
1732 {
1733 if(parent_result_node_ptr->node_x == xCoord)
1734 { // use left path
1735 add_result_node(xCoord, yCoord+1, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1736 add_result_node(xCoord, yCoord, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1737 }
1738 else
1739 { // use right path
1740 add_result_node(xCoord+1, yCoord+1, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1741 add_result_node(xCoord+1, yCoord, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1742 }
1743 }
1744 break;
1745
1746 case 4:
1747 err_when(!md);
1748 if(md)
1749 add_result_node(xCoord+1, yCoord+1, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1750 // else, error
1751
1752 err_when(ma+mb+mc>1); //(ma&&mb) || (ma&&mc) || (mb&&mc))
1753 if(ma||mb||mc) // at most one is 1
1754 add_result_node(xCoord+mb, yCoord+mc, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1755 break;
1756
1757 case 5:
1758 if(!furtherCheck)
1759 {
1760 add_result_node(xCoord+1, yCoord+1-mb, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1761 err_when(ma&&mc);
1762 if(ma||mc) // at most one is 1
1763 add_result_node(xCoord, yCoord+1-ma, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1764 }
1765 else
1766 {
1767 if(parent_result_node_ptr->node_y == yCoord)
1768 { // use upper path
1769 add_result_node(xCoord+1, yCoord, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1770 add_result_node(xCoord, yCoord, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1771 }
1772 else
1773 { // use lower path
1774 add_result_node(xCoord+1, yCoord+1, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1775 add_result_node(xCoord, yCoord+1, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1776 }
1777 }
1778 break;
1779
1780 case 6:
1781 err_when(!mb);
1782 if(mb)
1783 add_result_node(xCoord+1, yCoord, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1784 // else, error
1785
1786 err_when(ma+mc+md>1);//(ma&&mc) || (ma&&md) || (mc&&md))
1787 if(ma||mc||md) // at most one is 1
1788 add_result_node(xCoord+md, yCoord+1-ma, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1789 break;
1790
1791 case 7:
1792 if(!furtherCheck)
1793 {
1794 add_result_node(xCoord+1-ma, yCoord, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1795 err_when(mc&&md);
1796 if(mc||md) // at most one is 1
1797 add_result_node(xCoord+1-mc, yCoord+1, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1798 }
1799 else
1800 {
1801 if(parent_result_node_ptr->node_x == xCoord)
1802 { // use left path
1803 add_result_node(xCoord, yCoord, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1804 add_result_node(xCoord, yCoord+1, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1805 }
1806 else
1807 { // use right path
1808 add_result_node(xCoord+1, yCoord, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1809 add_result_node(xCoord+1, yCoord+1, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1810 }
1811 }
1812 break;
1813
1814 case 8:
1815 err_when(!ma);
1816 if(ma)
1817 add_result_node(xCoord, yCoord, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1818 // else, error
1819
1820 err_when(mb+mc+md>1);//(mb&&mc) || (mb&&md) || (mc&&md))
1821 if(mb||mc||md) // at most one is 1
1822 add_result_node(xCoord+1-mc, yCoord+1-mb, &max_size_result_node_ptr, &parent_result_node_ptr, count);
1823 break;
1824
1825 default:
1826 err_now("error in extracting answer");
1827 break;
1828 }
1829 }
1830 //------ End of function SeekPath::get_real_result_node ---------//
1831
1832
1833 //-------- Begin of function SeekPath::smooth_the_path ---------//
smooth_the_path(ResultNode * nodeArray,int & nodeCount)1834 ResultNode* SeekPath::smooth_the_path(ResultNode* nodeArray, int& nodeCount)
1835 {
1836 //------------------------------------------------------------//
1837 // smoothing the path and get the turning point
1838 //------------------------------------------------------------//
1839 //---------- declare variables ---------------//
1840 int i, j, checkedNodeCount, curNodeCount;
1841 short vectorX, vectorY, newVectorX, newVectorY, newVectorX2, newVectorY2;
1842 short changed, caseNum, processed;
1843 ResultNode *curUsefulNodePtr = nodeArray+1;
1844 ResultNode *preCheckingNodePtr = nodeArray;
1845 ResultNode *ptr1;
1846 ResultNode *ptr2;
1847 ResultNode *ptr3;
1848 ResultNode *ptr4;
1849
1850 parent_result_node_ptr = nodeArray;
1851 max_size_result_node_ptr = nodeArray+1;
1852
1853 //--------------------------------------------------//
1854 // to remove the duplicated or useless node near the
1855 // destination node
1856 //
1857 // note: preCheckingNodePtr points at the previous node of
1858 // max_size_result_node_ptr pointed at
1859 //--------------------------------------------------//
1860 i = 1;
1861 while(abs(parent_result_node_ptr->node_x-max_size_result_node_ptr->node_x)<=1 &&
1862 abs(parent_result_node_ptr->node_y-max_size_result_node_ptr->node_y)<=1)
1863 {
1864 max_size_result_node_ptr++;
1865 preCheckingNodePtr++;
1866 i++;
1867 if(i>=node_count)
1868 break;
1869
1870 //if(i%40==0)
1871 // sys_yield();
1872 }
1873 max_size_result_node_ptr = preCheckingNodePtr;
1874
1875 //--------------------------------------------------//
1876 // to smooth the path
1877 //--------------------------------------------------//
1878 changed = 1;
1879 checkedNodeCount = 1;
1880 curNodeCount = node_count-i+2;
1881 ptr1 = parent_result_node_ptr;
1882 ptr2 = max_size_result_node_ptr;
1883 ptr3 = max_size_result_node_ptr+1;
1884
1885 #ifdef DEBUG
1886 int countEnterWhile = 0;
1887 #endif
1888
1889 //int yieldCount = 0;
1890
1891 while(changed && curNodeCount>=3)
1892 {
1893 #ifdef DEBUG
1894 countEnterWhile++;
1895 #endif
1896
1897 //yieldCount++;
1898 //if(yieldCount%30==0)
1899 // sys_yield();
1900
1901 vectorX = ptr2->node_x - ptr1->node_x;
1902 vectorY = ptr2->node_y - ptr1->node_y;
1903 changed = 0;
1904 curUsefulNodePtr = nodeArray+1;
1905 checkedNodeCount = 1;
1906
1907 for(j=1; j<curNodeCount-1; j++)
1908 {
1909 processed = 0;
1910 newVectorX= ptr3->node_x - ptr2->node_x;
1911 newVectorY= ptr3->node_y - ptr2->node_y;
1912
1913 //------ turning at 90 degree clockwise / anti-clockwise --------//
1914 if((vectorX==0 && vectorY!=0 && newVectorX!=0 && newVectorY==0) || // + case
1915 (vectorX!=0 && vectorY==0 && newVectorX==0 && newVectorY!=0))
1916 {
1917 ptr2++;
1918 err_when(abs(ptr1->node_x-ptr2->node_x)>1 || abs(ptr1->node_y-ptr2->node_y)>1);
1919 ptr3++;
1920 err_when(j<curNodeCount-2 && ptr3->node_x && ptr3->node_y &&
1921 (abs(ptr3->node_x-ptr2->node_x)>1 || abs(ptr3->node_y-ptr2->node_y)>1));
1922 vectorX = ptr2->node_x - ptr1->node_x;
1923 vectorY = ptr2->node_y - ptr1->node_y;
1924 processed = 1;
1925 continue;
1926 }
1927
1928 if((vectorX!=0 && vectorY!=0 && newVectorX!=0 && newVectorY!=0) && // x case
1929 ((vectorX==newVectorX && vectorY==-newVectorY) || (vectorX==-newVectorX && vectorY==newVectorY)) &&
1930 can_move_to((ptr1->node_x+ptr3->node_x)/2, (ptr1->node_y+ptr3->node_y)/2))
1931 {
1932 err_when(ptr1->node_x==ptr3->node_x && ptr1->node_y==ptr3->node_y);
1933 ptr2->node_x = (ptr1->node_x+ptr3->node_x)/2;
1934 ptr2->node_y = (ptr1->node_y+ptr3->node_y)/2;
1935 *curUsefulNodePtr = *ptr2;
1936 err_when(abs(ptr1->node_x-curUsefulNodePtr->node_x)>1 || abs(ptr1->node_y-curUsefulNodePtr->node_y)>1);
1937 curUsefulNodePtr++;
1938 checkedNodeCount++;
1939 ptr1 = ptr2;
1940 ptr2 = ptr3;
1941 err_when(abs(ptr1->node_x-ptr2->node_x)>1 || abs(ptr1->node_y-ptr2->node_y)>1);
1942 ptr3++;
1943 err_when(j<curNodeCount-2 && ptr3->node_x && ptr3->node_y &&
1944 (abs(ptr3->node_x-ptr2->node_x)>1 || abs(ptr3->node_y-ptr2->node_y)>1));
1945 vectorX = ptr2->node_x - ptr1->node_x;
1946 vectorY = ptr2->node_y - ptr1->node_y;
1947 processed = 1;
1948 continue;
1949 }
1950
1951 if(j<curNodeCount-2) // check for the 4-point case
1952 {
1953 ptr4 = ptr3+1;
1954 newVectorX2 = ptr4->node_x - ptr3->node_x;
1955 newVectorY2 = ptr4->node_y - ptr3->node_y;
1956 caseNum = 0;
1957
1958 if(vectorX==-1 && vectorY==0 && newVectorX==-1 && newVectorX2==0)
1959 {
1960 if(newVectorY==1 && newVectorY2==1 && can_move_to(ptr2->node_x, ptr3->node_y))
1961 caseNum = 1; //-------- (0,0), (-1,0), (-2,1), (-2,2) --------//
1962 else if(newVectorY==-1 && newVectorY2==-1 && can_move_to(ptr2->node_x, ptr3->node_y))
1963 caseNum = 5; //-------- (0,0), (-1,0), (-2,-1), (-2,-2) --------//
1964 }
1965 else if(vectorX==1 && vectorY==0 && newVectorX==1 && newVectorX2==0)
1966 {
1967 if(newVectorY==1 && newVectorY2==1 && can_move_to(ptr2->node_x, ptr3->node_y))
1968 caseNum = 3; //-------- (0,0), (1,0), (2,1), (2,2) --------//
1969 else if(newVectorY==-1 && newVectorY2==-1 && can_move_to(ptr2->node_x, ptr3->node_y))
1970 caseNum = 7; //-------- (0,0), (1,0), (2,-1), (2,-2) --------//
1971 }
1972 else if(vectorX==0 && vectorY==-1 && newVectorY==-1 && newVectorY2==0)
1973 {
1974 if(newVectorX==1 && newVectorX2==1 && can_move_to(ptr3->node_x, ptr2->node_y))
1975 caseNum = 2; //-------- (0,0), (0,-1), (1,-2), (2,-2) --------//
1976 else if(newVectorX==-1 && newVectorX2==-1 && can_move_to(ptr3->node_x, ptr2->node_y))
1977 caseNum = 4; //-------- (0,0), (0,-1), (-1,-2), (-2,-2) --------//
1978 }
1979 else if(vectorX==0 && vectorY==1 && newVectorY==1 && newVectorY2==0)
1980 {
1981 if(newVectorX==1 && newVectorX2==1 && can_move_to(ptr3->node_x, ptr2->node_y))
1982 caseNum = 6; //-------- (0,0), (0,1), (1,2), (2,2) --------//
1983 else if(newVectorX==-1 && newVectorX2==-1 && can_move_to(ptr3->node_x, ptr2->node_y))
1984 caseNum = 8; //-------- (0,0), (0,1), (-1,2), (-2,2) --------//
1985 }
1986
1987 if(caseNum)
1988 {
1989 if(caseNum%2) // case 1, 3, 5 7
1990 ptr2->node_y = ptr3->node_y;
1991 else // case 2, 4, 6, 8
1992 ptr2->node_x = ptr3->node_x;
1993
1994 ptr3++; //ptr3 = ptr4;
1995 *curUsefulNodePtr = *ptr2;
1996 err_when(abs(ptr1->node_x-curUsefulNodePtr->node_x)>1 || abs(ptr1->node_y-curUsefulNodePtr->node_y)>1);
1997 curUsefulNodePtr++;
1998 checkedNodeCount++;
1999 ptr1 = ptr2;
2000 ptr2 = ptr3;
2001 err_when(abs(ptr1->node_x-ptr2->node_x)>1 || abs(ptr1->node_y-ptr2->node_y)>1);
2002 ptr3++;
2003 err_when(j<curNodeCount-2 && ptr3->node_x && ptr3->node_y &&
2004 (abs(ptr3->node_x-ptr2->node_x)>1 || abs(ptr3->node_y-ptr2->node_y)>1));
2005 j++;
2006 vectorX = ptr2->node_x - ptr1->node_x;
2007 vectorY = ptr2->node_y - ptr1->node_y;
2008 processed = 1;
2009 continue;
2010 }
2011 }
2012
2013 //------ none of the above case ---------//
2014 if(!processed)
2015 {
2016 *curUsefulNodePtr = *ptr2;
2017 err_when(abs(ptr1->node_x-curUsefulNodePtr->node_x)>1 || abs(ptr1->node_y-curUsefulNodePtr->node_y)>1);
2018 curUsefulNodePtr++;
2019 checkedNodeCount++;
2020 }
2021 else
2022 changed = 1;
2023
2024 ptr1 = ptr2;
2025 ptr2 = ptr3;
2026 err_when(abs(ptr1->node_x-ptr2->node_x)>1 || abs(ptr1->node_y-ptr2->node_y)>1);
2027 ptr3++;
2028 err_when(j<curNodeCount-2 && ptr3->node_x && ptr3->node_y &&
2029 (abs(ptr3->node_x-ptr2->node_x)>1 || abs(ptr3->node_y-ptr2->node_y)>1));
2030 vectorX = ptr2->node_x - ptr1->node_x;
2031 vectorY = ptr2->node_y - ptr1->node_y;
2032 }
2033 //---- end checking and then reset parameters----//
2034
2035 if(processed)
2036 changed = 1;
2037
2038 *curUsefulNodePtr = *ptr2;
2039 err_when(abs(ptr1->node_x-curUsefulNodePtr->node_x)>1 || abs(ptr1->node_y-curUsefulNodePtr->node_y)>1);
2040 curUsefulNodePtr++;
2041 checkedNodeCount++;
2042
2043 curNodeCount = checkedNodeCount;
2044 checkedNodeCount = 1;
2045 ptr1 = parent_result_node_ptr;
2046 ptr2 = ptr1+1;
2047 err_when(abs(ptr1->node_x-ptr2->node_x)>1 || abs(ptr1->node_y-ptr2->node_y)>1);
2048 ptr3 = ptr2+1;
2049 err_when(j<curNodeCount-2 && ptr3->node_x && ptr3->node_y &&
2050 (abs(ptr3->node_x-ptr2->node_x)>1 || abs(ptr3->node_y-ptr2->node_y)>1));
2051
2052 debug_check_path(nodeArray, nodeCount); //*** debug only
2053 }
2054 node_count = curNodeCount;
2055
2056 //--------------------------------------------------//
2057 // to remove the duplicated destination node
2058 //--------------------------------------------------//
2059 parent_result_node_ptr = nodeArray;
2060 max_size_result_node_ptr = nodeArray+1;
2061 ResultNode* result_node_pointer = max_size_result_node_ptr;
2062
2063 //----------------------------------
2064 // get the turning point
2065 //----------------------------------
2066 vectorX = max_size_result_node_ptr->node_x - parent_result_node_ptr->node_x;
2067 vectorY = max_size_result_node_ptr->node_y - parent_result_node_ptr->node_y;
2068
2069 for(i=1; i<node_count-1; i++)
2070 {
2071 parent_result_node_ptr = max_size_result_node_ptr; // don't use parent_result_node_ptr++, if the above code of removing duplication is used.
2072 max_size_result_node_ptr++;
2073 newVectorX=(max_size_result_node_ptr->node_x-parent_result_node_ptr->node_x);
2074 newVectorY=(max_size_result_node_ptr->node_y-parent_result_node_ptr->node_y);
2075 err_when(newVectorY!=0 && newVectorX!=0 && abs(newVectorX)!=abs(newVectorY));
2076
2077 //------ turning to another direction at this point ------//
2078 if(vectorX!=newVectorX || vectorY!=newVectorY)
2079 {
2080 err_when(abs(newVectorX)>1 || abs(newVectorY)>1);// || (newVectorX==0 && newVectorY==0))
2081 if(newVectorX!=0 || newVectorY!=0)
2082 {
2083 *result_node_pointer = *parent_result_node_ptr;
2084 result_node_pointer++;
2085 nodeCount++;
2086
2087 vectorX = newVectorX;
2088 vectorY = newVectorY;
2089 }
2090 }
2091
2092 //if(i%30==0)
2093 // sys_yield();
2094 }
2095
2096 result_node_pointer->node_x = real_sour_x;
2097 result_node_pointer->node_y = real_sour_y;
2098 result_node_pointer++;
2099 nodeCount++;
2100
2101 return nodeArray;
2102 }
2103 //------- End of function SeekPath::smooth_the_path -------//
2104
2105
2106 //-------- Begin of function Node::generate_successors ---------//
2107 // Note: In fact, the cost of the starting node should be 0 or 1
2108 // and the parentEnterDirection is 0. Now the cost in this
2109 // case is set to 2. The difference can be ignored as it will
2110 // not affect the search after generating the second level
2111 // children.
2112 // The advantage to ignore this case is that less comparsion
2113 // effort in checking parentEnterDirection.
2114 //
generate_successors(short parentEnterDirection,short realSourX,short realSourY)2115 short Node::generate_successors(short parentEnterDirection, short realSourX, short realSourY)
2116 {
2117 int hasLeft = node_x > cur_border_x1;
2118 int hasRight = node_x < cur_border_x2;
2119 int hasUp = node_y > cur_border_y1;
2120 int hasDown = node_y < cur_border_y2;
2121 int upperLeftX,upperLeftY;
2122 short cost;
2123
2124 upperLeftX = node_x<<1;
2125 upperLeftY = node_y<<1;
2126
2127 //-------------------------------------------
2128 // enter_direction = (exit_direction+3)%8+1
2129 //-------------------------------------------
2130
2131 if( hasLeft )
2132 {
2133 //--------- Left, exit_direction=1 --------//
2134 if ((node_type&0x05) && (can_move_to(upperLeftX-1,upperLeftY) || can_move_to(upperLeftX-1,upperLeftY+1)))
2135 {
2136 if(parentEnterDirection==2 || parentEnterDirection==8 ||
2137 (node_type&0x1 && parentEnterDirection==7) || (node_type&0x4 && parentEnterDirection==3) ||
2138 (!parentEnterDirection && realSourX == upperLeftX))
2139 cost = 1;
2140 else
2141 cost = 2;
2142
2143 if(generate_succ(node_x-1,node_y,5,cost))
2144 return 1;
2145 }
2146
2147 if( hasUp )
2148 {
2149 //------- Upper-Left, exit_direction=8 ---------//
2150 if ((node_type&0x1) && can_move_to(upperLeftX-1,upperLeftY-1))
2151 {
2152 if(parentEnterDirection==7 || parentEnterDirection==1 ||
2153 (!parentEnterDirection && realSourX==upperLeftX && realSourY==upperLeftY))
2154 cost = 1;
2155 else cost = 2;
2156
2157 if(generate_succ(node_x-1,node_y-1,4,cost))
2158 return 1;
2159 }
2160 }
2161
2162 if( hasDown )
2163 {
2164 //--------- Lower-Left, exit_direction=2 ----------//
2165 if ((node_type&0x4) && can_move_to(upperLeftX-1,upperLeftY+2))
2166 { if(parentEnterDirection==1 || parentEnterDirection==3 ||
2167 (!parentEnterDirection && realSourX==upperLeftX && realSourY==(upperLeftY+1)))
2168 cost = 1;
2169 else cost = 2;
2170
2171 if(generate_succ(node_x-1,node_y+1,6,cost))
2172 return 1;
2173 }
2174 }
2175 }
2176
2177 if( hasRight )
2178 {
2179 //----------- Right, exit_direction=5 -----------//
2180 if ((node_type&0xA) && (can_move_to(upperLeftX+2,upperLeftY) || can_move_to(upperLeftX+2,upperLeftY+1)))
2181 {
2182 if(parentEnterDirection==4 || parentEnterDirection==6 ||
2183 (node_type&0x02 && parentEnterDirection==7) || (node_type&0x08 && parentEnterDirection==3) ||
2184 (!parentEnterDirection && realSourX==(upperLeftX+1)))
2185 cost = 1;
2186 else cost = 2;
2187
2188 if(generate_succ(node_x+1,node_y,1,cost))
2189 return 1;
2190 }
2191
2192 if( hasUp )
2193 {
2194 //-------- Upper-Right, exit_direction=6 ---------//
2195
2196 if ((node_type&0x2)&&can_move_to(upperLeftX+2,upperLeftY-1))
2197 {
2198 if(parentEnterDirection==5 || parentEnterDirection==7 ||
2199 (!parentEnterDirection && realSourX==(upperLeftX+1) && realSourY==upperLeftY))
2200 cost = 1;
2201 else cost = 2;
2202
2203 if(generate_succ(node_x+1,node_y-1,2,cost))
2204 return 1;
2205 }
2206 }
2207
2208 if( hasDown )
2209 {
2210 //--------- Lower-Right, exit_direction=4 ---------//
2211
2212 if ((node_type&0x8)&&can_move_to(upperLeftX+2,upperLeftY+2))
2213 {
2214 if(parentEnterDirection==3 || parentEnterDirection==5 ||
2215 (!parentEnterDirection && realSourX==(upperLeftX+1) && realSourY==(upperLeftY+1)))
2216 cost = 1;
2217 else cost = 2;
2218
2219 if(generate_succ(node_x+1,node_y+1,8,cost))
2220 return 1;
2221 }
2222 }
2223 }
2224
2225 if( hasUp )
2226 {
2227 //---------- Upper, exit_direction=7 -----------//
2228 if ((node_type&0x03) && (can_move_to(upperLeftX,upperLeftY-1) || can_move_to(upperLeftX+1,upperLeftY-1)))
2229 {
2230 if(parentEnterDirection==6 || parentEnterDirection==8 ||
2231 (node_type&0x01 && parentEnterDirection==1) || (node_type&0x02 && parentEnterDirection==5) ||
2232 (!parentEnterDirection && realSourY==upperLeftY))
2233 cost = 1;
2234 else cost = 2;
2235
2236 if(generate_succ(node_x,node_y-1,3,cost))
2237 return 1;
2238 }
2239 }
2240
2241 if( hasDown )
2242 {
2243 //---------- Lower, exit_direction=3 -----------//
2244 if ((node_type&0xC) && ( can_move_to(upperLeftX,upperLeftY+2) || can_move_to(upperLeftX+1,upperLeftY+2) ) )
2245 {
2246 if(parentEnterDirection==2 || parentEnterDirection==4 ||
2247 (node_type&0x4 && parentEnterDirection==1) || (node_type&0x8 && parentEnterDirection==5) ||
2248 (!parentEnterDirection && realSourY==(upperLeftY+1)))
2249 cost = 1;
2250 else cost = 2;
2251
2252 if(generate_succ(node_x,node_y+1,7,cost))
2253 return 1;
2254 }
2255 }
2256 return 0;
2257 }
2258 //------- End of function Node::generate_successors -------//
2259
2260
2261 //-------- Begin of function Node::generate_succ ---------//
generate_succ(short x,short y,short enter_direct,short cost)2262 short Node::generate_succ(short x, short y, short enter_direct,short cost)
2263 {
2264 //----- if it points back to this node's parent ----//
2265 if( parent_node )
2266 {
2267 if( parent_node->node_x==x && parent_node->node_y==y )
2268 return 0;
2269 }
2270
2271 //----- if there is an existing node at the given position ----//
2272 int upperLeftX, upperLeftY;
2273 //int cost;
2274 short c, g = node_g+cost; // g(Successor)=g(BestNode)+cost of getting from BestNode to Successor
2275 short nodeRecno;
2276
2277 if( (nodeRecno=cur_node_matrix[y*MAX_WORLD_X_LOC/2+x]) > 0 &&
2278 nodeRecno<max_node_num)
2279 {
2280 Node* oldNode = cur_node_array+nodeRecno-1;
2281
2282 //------ Add oldNode to the list of BestNode's child_noderen (or Successors).
2283 for(c=0 ; c<MAX_CHILD_NODE && child_node[c] ; c++);
2284 child_node[c]=oldNode;
2285
2286 //---- if our new g value is < oldNode's then reset oldNode's parent to point to BestNode
2287 if(g < oldNode->node_g)
2288 {
2289 oldNode->parent_node = this;
2290 oldNode->node_g = g;
2291 oldNode->node_f = g+oldNode->node_h;
2292 oldNode->enter_direction = (char)enter_direct;
2293
2294 //-------- if it's a closed node ---------//
2295 if(oldNode->child_node[0] )
2296 {
2297 //-------------------------------------------------//
2298 // Since we changed the g value of oldNode, we need
2299 // to propagate this new value downwards, i.e.
2300 // do a Depth-First traversal of the tree!
2301 //-------------------------------------------------//
2302 oldNode->propagate_down();
2303 //sys_yield();
2304 }
2305 }
2306 }
2307 else //------------ add a new node -----------//
2308 {
2309 Node* succNode = cur_node_array + cur_seek_path->node_count++;
2310
2311 memset(succNode, 0, sizeof(Node));
2312
2313 succNode->parent_node = this;
2314 succNode->node_g = g;
2315 succNode->node_h = (x-cur_dest_x)*(x-cur_dest_x)+(y-cur_dest_y)*(y-cur_dest_y); // should do sqrt(), but since we don't really
2316 succNode->node_f = g+succNode->node_h; // care about the distance but just which branch looks
2317 succNode->node_x = x; // better this should suffice. Anyayz it's faster.
2318 succNode->node_y = y;
2319 succNode->enter_direction = (char)enter_direct;
2320 upperLeftX = x<<1;
2321 upperLeftY = y<<1;
2322 succNode->node_type = can_move_to(upperLeftX,upperLeftY)+(can_move_to(upperLeftX+1,upperLeftY)<<1)+
2323 (can_move_to(upperLeftX,upperLeftY+1)<<2)+(can_move_to(upperLeftX+1,upperLeftY+1)<<3);
2324
2325 if(search_mode==SEARCH_MODE_REUSE && nodeRecno>max_node_num) // path-reuse node found, but checking of can_walk(final_dest_?) is requested
2326 {
2327 int destIndex = nodeRecno - max_node_num;
2328 switch(destIndex)
2329 {
2330 case 1: final_dest_x = x<<1;
2331 final_dest_y = y<<1;
2332 break;
2333
2334 case 2: final_dest_x = (x<<1) + 1;
2335 final_dest_y = y<<1;
2336 break;
2337
2338 case 3: final_dest_x = x<<1;
2339 final_dest_y = (y<<1) + 1;
2340 break;
2341
2342 case 4: final_dest_x = (x<<1) + 1;
2343 final_dest_y = (y<<1) + 1;
2344 break;
2345
2346 default: err_here();
2347 break;
2348 }
2349
2350 if(can_move_to(final_dest_x, final_dest_y)) // can_walk the connection point, accept this case
2351 {
2352 reuse_result_node_ptr = succNode;
2353 return 1;
2354 } // else continue until reuse node is found and connection point can be walked
2355 }
2356
2357 cur_node_matrix[y*MAX_WORLD_X_LOC/2+x] = cur_seek_path->node_count;
2358 cur_seek_path->open_node_list.insert_node(succNode);
2359 for(c=0 ; c<MAX_CHILD_NODE && child_node[c] ; c++); // Add oldNode to the list of BestNode's child_noderen (or succNodes).
2360 child_node[c]=succNode;
2361 }
2362
2363 return 0;
2364 }
2365 //------- End of function Node::generate_succ -------//
2366
2367
2368 //-------- Begin of function Node::propagate_down ---------//
propagate_down()2369 void Node::propagate_down()
2370 {
2371 Node *childNode, *fatherNode;
2372 int c, g=node_g; // alias.
2373 short cost;
2374 char xShift, yShift; // the x, y difference between parent and child nodes
2375
2376 char childEnterDirection;
2377 char exitDirection;
2378 char testResult;
2379
2380 for(c=0;c<8;c++)
2381 {
2382 if ((childNode=child_node[c])==NULL) // create alias for faster access.
2383 break;
2384
2385 cost = 2; // in fact, may be 1 or 2
2386 if (g+cost <= childNode->node_g) // first checking
2387 {
2388 xShift = childNode->node_x-node_x;
2389 yShift = childNode->node_y-node_y;
2390 err_when(abs(xShift)>1 || abs(yShift)>1);
2391 //---------- calulate the new enter direction ------------//
2392 switch(yShift)
2393 {
2394 case -1:
2395 childEnterDirection = char(3-xShift);
2396 break;
2397
2398 case 0:
2399 childEnterDirection = char(3-(xShift<<1));
2400 break;
2401
2402 case 1:
2403 childEnterDirection = char(7+xShift);
2404 break;
2405 }
2406
2407 exitDirection = (childEnterDirection+3)%8+1;
2408
2409 if(enter_direction > exitDirection)
2410 {
2411 if((enter_direction==8 && (exitDirection==1 || exitDirection==2)) ||
2412 (enter_direction==7 && exitDirection==1))
2413 testResult = exitDirection + 8 - enter_direction;
2414 else
2415 testResult = enter_direction - exitDirection;
2416 }
2417 else
2418 {
2419 if((exitDirection==8 && (enter_direction==1 || enter_direction==2)) ||
2420 (exitDirection==7 && enter_direction==1))
2421 testResult = enter_direction + 8 - exitDirection;
2422 else
2423 testResult = exitDirection - enter_direction;
2424 }
2425
2426 if(exitDirection%2 && testResult==2)
2427 {
2428 int upperLeftX = 2*node_x;
2429 int upperLeftY = 2*node_y;
2430 // this case only occurs at the edge
2431 switch(childEnterDirection)
2432 {
2433 case 1: if((exitDirection==3 && can_move_to(upperLeftX, upperLeftY+1)) ||
2434 (exitDirection==7 && can_move_to(upperLeftX, upperLeftY)))
2435 cost = 1;
2436 break;
2437
2438 case 3: if((exitDirection==1 && can_move_to(upperLeftX, upperLeftY+1)) ||
2439 (exitDirection==5 && can_move_to(upperLeftX+1, upperLeftY+1)))
2440 cost = 1;
2441 break;
2442
2443 case 5: if((exitDirection==3 && can_move_to(upperLeftX+1, upperLeftY+1)) ||
2444 (exitDirection==7 && can_move_to(upperLeftX+1, upperLeftY)))
2445 cost = 1;
2446 break;
2447
2448 case 7: if((exitDirection==1 && can_move_to(upperLeftX, upperLeftY)) ||
2449 (exitDirection==5 && can_move_to(upperLeftX+1, upperLeftY)))
2450 cost = 1;
2451 break;
2452
2453 default: err_here();
2454 break;
2455 }
2456 }
2457 else
2458 cost = 2 - (testResult <= 1); //if(testResult <= 1) cost = 1;
2459
2460 err_when(cost>2 || cost<1);
2461 if(g+cost < childNode->node_g) // second checking, mainly for cost = 2;
2462 {
2463 childNode->node_g = g+cost;
2464 childNode->node_f = childNode->node_g+childNode->node_h;
2465 childNode->parent_node = this;// reset parent to new path.
2466 childNode->enter_direction = childEnterDirection;
2467 stack_push(childNode); // Now the childNode's branch need to be checked out. Remember the new cost must be propagated down.
2468 }
2469 }
2470 }
2471
2472 while(cur_stack_pos>0)
2473 {
2474 fatherNode=stack_pop();
2475 g = fatherNode->node_g;
2476
2477 for(c=0;c<8;c++)
2478 {
2479 if((childNode=fatherNode->child_node[c])==NULL) // we may stop the propagation 2 ways: either
2480 break;
2481
2482 cost = 2; // in fact, may be 1 or 2
2483 if(g+cost <= childNode->node_g) // first checking
2484 // there are no children, or that the g value of the child is equal or better than the cost we're propagating
2485 {
2486 xShift = childNode->node_x-fatherNode->node_x;
2487 yShift = childNode->node_y-fatherNode->node_y;
2488 err_when(abs(xShift)>1 || abs(yShift)>1);
2489 //---------- calulate the new enter direction ------------//
2490 switch(yShift)
2491 {
2492 case -1:
2493 childEnterDirection = char(3-xShift);
2494 break;
2495
2496 case 0:
2497 childEnterDirection = char(3-(xShift<<1));
2498 break;
2499
2500 case 1:
2501 childEnterDirection = char(7+xShift);
2502 break;
2503 }
2504
2505 exitDirection = (childEnterDirection+3)%8+1;
2506
2507 char fatherEnterDirection = fatherNode->enter_direction;
2508 if(fatherEnterDirection > exitDirection)
2509 {
2510 if((fatherEnterDirection==8 && (exitDirection==1 || exitDirection==2)) ||
2511 (fatherEnterDirection==7 && exitDirection==1))
2512 testResult = exitDirection + 8 - fatherEnterDirection;
2513 else
2514 testResult = fatherEnterDirection - exitDirection;
2515 }
2516 else
2517 {
2518 if((exitDirection==8 && (fatherEnterDirection==1 || fatherEnterDirection==2)) ||
2519 (exitDirection==7 && fatherEnterDirection==1))
2520 testResult = fatherEnterDirection + 8 - exitDirection;
2521 else
2522 testResult = exitDirection - fatherEnterDirection;
2523 }
2524
2525 if(exitDirection%2 && testResult==2)
2526 {
2527 int upperLeftX = 2*fatherNode->node_x;
2528 int upperLeftY = 2*fatherNode->node_y;
2529 // this case only occurs at the edge
2530 switch(childEnterDirection)
2531 {
2532 case 1: if((exitDirection==3 && can_move_to(upperLeftX, upperLeftY+1)) ||
2533 (exitDirection==7 && can_move_to(upperLeftX, upperLeftY)))
2534 cost = 1;
2535 break;
2536
2537 case 3: if((exitDirection==1 && can_move_to(upperLeftX, upperLeftY+1)) ||
2538 (exitDirection==5 && can_move_to(upperLeftX+1, upperLeftY+1)))
2539 cost = 1;
2540 break;
2541
2542 case 5: if((exitDirection==3 && can_move_to(upperLeftX+1, upperLeftY+1)) ||
2543 (exitDirection==7 && can_move_to(upperLeftX+1, upperLeftY)))
2544 cost = 1;
2545 break;
2546
2547 case 7: if((exitDirection==1 && can_move_to(upperLeftX, upperLeftY)) ||
2548 (exitDirection==5 && can_move_to(upperLeftX+1, upperLeftY)))
2549 cost = 1;
2550 break;
2551
2552 default: err_here();
2553 break;
2554 }
2555 }
2556 else
2557 cost = 2 - (testResult <= 1); //if(testResult <= 1) cost = 1;
2558
2559 err_when(cost>2 || cost<1);
2560 if(g+cost < childNode->node_g) // second checking, mainly for cost = 2;
2561 {
2562 childNode->node_g = g+cost;
2563 childNode->node_f = childNode->node_g+childNode->node_h;
2564 childNode->parent_node = fatherNode;
2565 childNode->enter_direction = childEnterDirection;
2566 stack_push(childNode);
2567 }
2568 }
2569 }
2570 }
2571 }
2572 //------- End of function Node::propagate_down -------//
2573
2574
2575 //-------- Begin of static function stack_push ---------//
stack_push(Node * nodePtr)2576 static void stack_push(Node *nodePtr)
2577 {
2578 stack_array[cur_stack_pos++] = nodePtr;
2579
2580 err_when( cur_stack_pos >= MAX_STACK_NUM );
2581 }
2582 //--------- End of static function stack_push ---------//
2583
2584
2585 //-------- Begin of static function stack_pop ---------//
stack_pop()2586 static Node* stack_pop()
2587 {
2588 return stack_array[--cur_stack_pos];
2589 }
2590 //--------- End of static function stack_pop ---------//
2591
2592 //-********************************************************************************-//
2593 // for UNIT_SEA and UNIT_AIR, the scale used is double that of UNIT_LAND
2594 //-********************************************************************************-//
2595
2596 //-------- Begin of static function SeekPath::seek2 ---------//
seek2(int sx,int sy,int dx,int dy,short miscNo,short numOfPath,int maxTries)2597 int SeekPath::seek2(int sx, int sy, int dx, int dy, short miscNo, short numOfPath, int maxTries)
2598 {
2599 err_when(mobile_type==UNIT_LAND);
2600
2601 //---------------------------------------------------------------------------//
2602 // target_recno, building_id is not implemented for this version of seek2()
2603 //---------------------------------------------------------------------------//
2604 target_recno = building_id = 0;
2605 building_x1 = building_y1 = building_x2 = building_y2 = -1;
2606
2607 switch(search_mode)
2608 {
2609 case SEARCH_MODE_TO_FIRM:
2610 building_id = miscNo;
2611 building_x1 = dx; // upper left corner location
2612 building_y1 = dy;
2613 search_firm_info = firm_res[building_id];
2614 building_x2 = dx+search_firm_info->loc_width-1;
2615 building_y2 = dy+search_firm_info->loc_height-1;
2616 break;
2617
2618 case SEARCH_MODE_TO_TOWN:
2619 building_id = miscNo;
2620 building_x1 = dx; // upper left corner location
2621 building_y1 = dy;
2622 if(miscNo != -1)
2623 {
2624 Location* buildPtr = world.get_loc(dx, dy);
2625 Town* targetTown = town_array[buildPtr->town_recno()];
2626 building_x2 = targetTown->loc_x2;
2627 building_y2 = targetTown->loc_y2;
2628 }
2629 else // searching to settle. Detail explained in function set_move_to_surround()
2630 {
2631 building_x2 = building_x1+STD_TOWN_LOC_WIDTH-1;
2632 building_y2 = building_y1+STD_TOWN_LOC_HEIGHT-1;
2633 }
2634 break;
2635
2636 case SEARCH_MODE_ATTACK_UNIT_BY_RANGE:
2637 case SEARCH_MODE_ATTACK_WALL_BY_RANGE:
2638 err_when(attack_range==0);
2639 building_id = miscNo;
2640 building_x1 = MAX(dx-attack_range, 0);
2641 building_y1 = MAX(dy-attack_range, 0);
2642 building_x2 = MIN(dx+attack_range, MAX_WORLD_X_LOC-1);
2643 building_y2 = MIN(dy+attack_range, MAX_WORLD_Y_LOC-1);
2644 break;
2645
2646 case SEARCH_MODE_ATTACK_FIRM_BY_RANGE:
2647 building_id = miscNo;
2648 building_x1 = MAX(dx-attack_range, 0);
2649 building_y1 = MAX(dy-attack_range, 0);
2650 search_firm_info = firm_res[building_id];
2651 building_x2 = MIN(dx+search_firm_info->loc_width-1+attack_range, MAX_WORLD_X_LOC-1);
2652 building_y2 = MIN(dy+search_firm_info->loc_height-1+attack_range, MAX_WORLD_Y_LOC-1);
2653 break;
2654
2655 case SEARCH_MODE_ATTACK_TOWN_BY_RANGE:
2656 building_id = miscNo;
2657 building_x1 = MAX(dx-attack_range, 0);
2658 building_y1 = MAX(dy-attack_range, 0);
2659 building_x2 = MIN(dx+STD_TOWN_LOC_WIDTH-1+attack_range, MAX_WORLD_X_LOC-1);
2660 building_y2 = MIN(dy+STD_TOWN_LOC_HEIGHT-1+attack_range, MAX_WORLD_Y_LOC-1);
2661 break;
2662
2663 case SEARCH_MODE_TO_LAND_FOR_SHIP:
2664 region_id = static_cast<uint8_t>(miscNo);
2665 break;
2666 }
2667
2668 //------------------------------------------------------------------------------//
2669 // set start location and destination location
2670 //------------------------------------------------------------------------------//
2671 real_sour_x = sx;
2672 real_sour_y = sy;
2673 //final_dest_x = real_dest_x = dx;
2674 //final_dest_y = real_dest_y = dy;
2675 real_dest_x = dx;
2676 real_dest_y = dy;
2677
2678 int xShift, yShift, area;
2679 short pathNum;
2680 switch(search_mode)
2681 {
2682 case SEARCH_MODE_TO_FIRM:
2683 case SEARCH_MODE_TO_TOWN:
2684 final_dest_x = (building_x1+building_x2)/2;
2685 final_dest_y = (building_y1+building_y2)/2;
2686
2687 //---------------------------------------------------------------------------------//
2688 // for group assign, the final destination is adjusted by the value of numOfPath
2689 //---------------------------------------------------------------------------------//
2690 if(search_mode==SEARCH_MODE_TO_TOWN)
2691 area = STD_TOWN_LOC_WIDTH*STD_TOWN_LOC_HEIGHT;
2692 else // search_mode == SEARCH_MODE_TO_FIRM
2693 area = search_firm_info->loc_width*search_firm_info->loc_height;
2694
2695 pathNum = (numOfPath>area) ? (numOfPath-1)%area + 1 : numOfPath;
2696 if(search_mode==SEARCH_MODE_TO_TOWN)
2697 misc.cal_move_around_a_point(pathNum, STD_TOWN_LOC_WIDTH, STD_TOWN_LOC_HEIGHT, xShift, yShift);
2698 else
2699 misc.cal_move_around_a_point(pathNum, search_firm_info->loc_width, search_firm_info->loc_height, xShift, yShift);
2700
2701 final_dest_x += xShift;
2702 final_dest_y += yShift;
2703
2704 if(final_dest_x<0)
2705 final_dest_x = 0;
2706 else if(final_dest_x>=MAX_WORLD_X_LOC)
2707 final_dest_x = MAX_WORLD_X_LOC-1;
2708
2709 if(final_dest_y<0)
2710 final_dest_y = 0;
2711 else if(final_dest_y>=MAX_WORLD_Y_LOC)
2712 final_dest_y = MAX_WORLD_Y_LOC-1;
2713 break;
2714
2715 case SEARCH_MODE_ATTACK_UNIT_BY_RANGE:
2716 case SEARCH_MODE_ATTACK_FIRM_BY_RANGE:
2717 case SEARCH_MODE_ATTACK_TOWN_BY_RANGE:
2718 case SEARCH_MODE_ATTACK_WALL_BY_RANGE:
2719 final_dest_x = (building_x1+building_x2)/2;
2720 final_dest_y = (building_y1+building_y2)/2;
2721 break;
2722
2723 default:
2724 final_dest_x = real_dest_x;
2725 final_dest_y = real_dest_y;
2726 break;
2727 }
2728
2729 //--------------------------------------------------------------//
2730 // change to 2x2 node format
2731 //--------------------------------------------------------------//
2732 int sourceX = short(sx/2); // the upper left corner is used
2733 int sourceY = short(sy/2);
2734 dest_x = short(final_dest_x/2);
2735 dest_y = short(final_dest_y/2);
2736
2737 //-----------------------------------------//
2738 // reset node_matrix
2739 //-----------------------------------------//
2740 if(search_mode!=SEARCH_MODE_REUSE)
2741 {
2742 max_node_num = 0xFFFF;
2743 memset(node_matrix, 0, sizeof(short)*MAX_WORLD_X_LOC*MAX_WORLD_Y_LOC/4);
2744 }
2745 else
2746 {
2747 max_node_num = max_node;
2748 memcpy(node_matrix, reuse_node_matrix_ptr, sizeof(short)*MAX_WORLD_X_LOC*MAX_WORLD_Y_LOC/4);
2749 }
2750
2751 //--------- create the first node ---------//
2752 node_count = 0;
2753 result_node_ptr = NULL;
2754
2755 Node *nodePtr = node_array + node_count++;
2756 memset(nodePtr, 0, sizeof(Node));
2757
2758 //-------- store the upper left coordinate of the node ----------//
2759 int destUpperLeftX = dest_x<<1;
2760 int destUpperLeftY = dest_y<<1;
2761 is_dest_blocked = !can_move_to(destUpperLeftX, destUpperLeftY);
2762 // whether the destination is blocked, if so, only search till the destination's neighbor locations
2763
2764 //### begin alex 25/9 ###//
2765 //------------ do some adjustment for ship to beach if destination is blocked ----------------//
2766 if(is_dest_blocked && search_mode==SEARCH_MODE_TO_LAND_FOR_SHIP &&
2767 (final_dest_x%2 || final_dest_y%2)) // either is odd location
2768 {
2769 if(final_dest_x%2 && final_dest_y%2==0)
2770 {
2771 if(destUpperLeftX+2<MAX_WORLD_X_LOC-1 && can_move_to(destUpperLeftX+2, destUpperLeftY))
2772 {
2773 is_dest_blocked = 0;
2774 destUpperLeftX += 2;
2775 dest_x++;
2776 }
2777 }
2778 else if(final_dest_x%2==0 && final_dest_y%2)
2779 {
2780 if(destUpperLeftY+2<MAX_WORLD_Y_LOC-1 && can_move_to(destUpperLeftX, destUpperLeftY+2))
2781 {
2782 is_dest_blocked = 0;
2783 destUpperLeftY += 2;
2784 dest_y++;
2785 }
2786 }
2787 else
2788 {
2789 if(destUpperLeftX+2<MAX_WORLD_X_LOC-1 && can_move_to(destUpperLeftX+2, destUpperLeftY))
2790 {
2791 is_dest_blocked = 0;
2792 destUpperLeftX += 2;
2793 dest_x++;
2794 }
2795 else if(destUpperLeftX+2<MAX_WORLD_X_LOC-1 && destUpperLeftY+2<MAX_WORLD_Y_LOC-1 &&
2796 can_move_to(destUpperLeftX+2, destUpperLeftY+2))
2797 {
2798 is_dest_blocked = 0;
2799 destUpperLeftX += 2;
2800 destUpperLeftY += 2;
2801 dest_x++;
2802 dest_y++;
2803 }
2804 else if(destUpperLeftY+2<MAX_WORLD_Y_LOC-1 && can_move_to(destUpperLeftX, destUpperLeftY+2))
2805 {
2806 is_dest_blocked = 0;
2807 destUpperLeftY += 2;
2808 dest_y++;
2809 }
2810 }
2811 }
2812 //#### end alex 25/9 ####//
2813
2814 nodePtr->node_g = 0;
2815 nodePtr->node_h = (sourceX-dest_x)*(sourceX-dest_x)+(sourceY-dest_y)*(sourceY-dest_y); // should really use sqrt().
2816 nodePtr->node_f = nodePtr->node_g + nodePtr->node_h;
2817 nodePtr->node_x = sourceX;
2818 nodePtr->node_y = sourceY;
2819
2820 open_node_list.insert_node(nodePtr); // make Open List point to first node
2821
2822 //--- if the destination is the current postion or next to it & the dest is occupied ---//
2823 if(sourceX==dest_x && sourceY==dest_y)
2824 {
2825 path_status = PATH_FOUND;
2826 result_node_ptr = NULL;
2827 return path_status;
2828 }
2829
2830 //------------ seek now ------------------//
2831 int maxNode = (!maxTries) ? max_node : maxTries;
2832 return continue_seek2(maxNode, 1); // 1-first seek session of the current seek order
2833 }
2834 //--------- End of static function SeekPath::seek2 ---------//
2835
2836
2837 //-------- Begin of static function SeekPath::continue_seek2 ---------//
continue_seek2(int maxTries,char firstSeek)2838 int SeekPath::continue_seek2(int maxTries, char firstSeek)
2839 {
2840 if( path_status != PATH_SEEKING )
2841 return path_status;
2842
2843 //------- aliasing class member vars for fast access ------//
2844 cur_seek_path = this;
2845 cur_dest_x = dest_x;
2846 cur_dest_y = dest_y;
2847 cur_node_matrix = node_matrix;
2848 cur_node_array = node_array;
2849
2850 cur_border_x1 = border_x1;
2851 cur_border_y1 = border_y1;
2852 cur_border_x2 = border_x2;
2853 cur_border_y2 = border_y2;
2854
2855 //------ seek the path using the A star algorithm -----//
2856 int maxNode = (total_node_avail<maxTries) ? total_node_avail : maxTries;
2857 maxNode -= MAX_CHILD_NODE; // generate_successors() can generate a MAX of MAX_CHILD_NODE new nodes per call
2858 Node *bestNodePtr;
2859
2860 int i;
2861 for(i=0; i<maxNode; i++)
2862 {
2863 bestNodePtr = return_best_node();
2864
2865 //if(i%20==0)
2866 // sys_yield(); // update cursor position
2867
2868 //---- even if the path is impossible, get the closest path ----//
2869 if( !bestNodePtr )
2870 {
2871 path_status = PATH_IMPOSSIBLE;
2872 break;
2873 }
2874
2875 //----- exceed the object's MAX's node limitation, return the closest path ----//
2876 if( node_count >= maxNode )
2877 //if( i >= maxNode )
2878 {
2879 path_status = PATH_NODE_USED_UP;
2880 break;
2881 }
2882
2883 //------------------------------------------//
2884 // If the path is found OR
2885 //
2886 // If the destination is blocked,
2887 // consider it done when we are next to it.
2888 //------------------------------------------//
2889 if( (bestNodePtr->node_x==dest_x && bestNodePtr->node_y==dest_y) ||
2890 ( is_dest_blocked && abs(bestNodePtr->node_x-dest_x)<=1 && abs(bestNodePtr->node_y-dest_y)<=1 ) )
2891 {
2892 path_status = PATH_FOUND;
2893 result_node_ptr = bestNodePtr;
2894 break;
2895 }
2896
2897 //--------- generate successors -------//
2898 if(bestNodePtr->generate_successors2(real_sour_x, real_sour_y))
2899 {
2900 path_status = PATH_REUSE_FOUND;
2901 result_node_ptr = reuse_result_node_ptr;
2902 break;
2903 }
2904 }
2905
2906 err_when( cur_stack_pos!=0 ); // it should be zero all the times, all pushes should have been poped
2907 current_search_node_used = i+1; // store the number of nodes used in this searching
2908 return path_status;
2909 }
2910 //--------- End of static function SeekPath::continue_seek2 ---------//
2911
2912
2913 //---- Begin of function SeekPath::get_result2 ---------//
get_result2(int & resultNodeCount,short & pathDist)2914 ResultNode* SeekPath::get_result2(int& resultNodeCount, short& pathDist)
2915 {
2916 resultNodeCount = pathDist = 0;
2917 if(total_node_avail<=0)
2918 return NULL;
2919
2920 total_node_avail -= current_search_node_used;
2921 short useClosestNode = 0; // indicate whether closest node is returned instead of the actual node
2922
2923 if(!result_node_ptr || !result_node_ptr->parent_node) // if PATH_IMPOSSIBLE or PATH_NODE_USED_UP, result_node_ptr is NULL, we need to call get_closest_node() to get the closest node.
2924 {
2925 if(path_status==PATH_FOUND)
2926 return NULL; // the current location is already the destination
2927
2928 err_when(path_status==PATH_FOUND);
2929 result_node_ptr = return_closest_node();
2930 useClosestNode = 1;
2931
2932 if(!result_node_ptr)
2933 return NULL;
2934 }
2935
2936 //--------------------------------------------------//
2937 // Trace backwards to the starting node, and rationalize
2938 // nodes (i.e. group nodes of the same direction into
2939 // single nodes.)
2940 //--------------------------------------------------//
2941 Node* nodePtr = result_node_ptr; // the node current being processed
2942 Node* baseNodePtr = result_node_ptr; // the first end node for connecting the other end node for the path in that direction.
2943 Node* parentNode = nodePtr->parent_node; // the parent node of nodePtr
2944
2945 if(!parentNode)
2946 return NULL;
2947
2948 resultNodeCount=1; // the current node
2949 err_when( !parentNode ); // the desination node must have a parent node
2950
2951 //--- if the following nodes are going at the same direction, rationalize them ---//
2952 short vectorX = parentNode->node_x - nodePtr->node_x; // the vector at which the sprite is going
2953 short vectorY = parentNode->node_y - nodePtr->node_y;
2954 short newVectorX, newVectorY;
2955 nodePtr = parentNode;
2956 //sys_yield(); // update cursor position
2957
2958 err_when(vectorX && vectorY && abs(vectorX)!=abs(vectorY));
2959 while((parentNode=nodePtr->parent_node) != NULL)
2960 {
2961 err_when(abs(vectorX)>1 || abs(vectorY)>1);
2962
2963 //------ turning to another direction at this point ------//
2964 newVectorX = parentNode->node_x-nodePtr->node_x;
2965 newVectorY = parentNode->node_y-nodePtr->node_y;
2966 if(vectorX != newVectorX || vectorY != newVectorY)
2967 {
2968 err_when(abs(newVectorX)>1 || abs(newVectorY)>1);
2969 err_when(newVectorX && newVectorY && abs(newVectorX)!=abs(newVectorY));
2970 err_when(baseNodePtr->node_x-nodePtr->node_x && baseNodePtr->node_y-nodePtr->node_y &&
2971 abs(baseNodePtr->node_x-nodePtr->node_x)!=abs(baseNodePtr->node_y-nodePtr->node_y));
2972 baseNodePtr->parent_node = nodePtr; // skip the in-between ones which are in the same direction
2973 baseNodePtr = nodePtr; // prepare for the next line.
2974 resultNodeCount++;
2975
2976 vectorX = newVectorX;
2977 vectorY = newVectorY;
2978 }
2979
2980 nodePtr = parentNode;
2981 }
2982
2983 baseNodePtr->parent_node = nodePtr; // finish off the last one
2984 resultNodeCount++;
2985
2986 //----------------------------------------------------------------------------//
2987 // After the above process, here we will have a link of rationalize nodes.
2988 // Retrieve them in the backwards order
2989 //----------------------------------------------------------------------------//
2990 //sys_yield(); // update cursor position
2991 ResultNode *resultNodeArray = (ResultNode*) mem_add( sizeof(ResultNode) * resultNodeCount );
2992 ResultNode *resultNodePtr = resultNodeArray+resultNodeCount-1;
2993 int processCount = 1;
2994
2995 Node *preNodePtr = result_node_ptr;
2996 resultNodePtr->node_x = preNodePtr->node_x;
2997 resultNodePtr->node_y = preNodePtr->node_y;
2998 resultNodePtr--;
2999 Node *curNodePtr = result_node_ptr->parent_node;
3000 err_when(pathDist!=0);
3001
3002 int xDist, yDist;
3003 while(processCount++ < resultNodeCount)
3004 {
3005 err_when(curNodePtr->node_x<0 || curNodePtr->node_x>=MAX_WORLD_X_LOC ||
3006 curNodePtr->node_y<0 || curNodePtr->node_y>=MAX_WORLD_Y_LOC);
3007
3008 resultNodePtr->node_x = curNodePtr->node_x;
3009 resultNodePtr->node_y = curNodePtr->node_y;
3010 resultNodePtr--;
3011
3012 xDist = abs(curNodePtr->node_x-preNodePtr->node_x);
3013 yDist = abs(curNodePtr->node_y-preNodePtr->node_y);
3014 err_when((!xDist && !yDist) || (xDist && yDist && xDist!=yDist));
3015 pathDist += (xDist) ? xDist : yDist;
3016
3017 preNodePtr = curNodePtr;
3018 curNodePtr = curNodePtr->parent_node;
3019 }
3020
3021 //sys_yield(); // update cursor position
3022
3023 //------------------------------------------------//
3024 // multipy all the node by scale 2
3025 //------------------------------------------------//
3026 for(processCount=0, resultNodePtr=resultNodeArray; processCount<resultNodeCount; processCount++, resultNodePtr++)
3027 {
3028 resultNodePtr->node_x <<= 1;
3029 resultNodePtr->node_y <<= 1;
3030
3031 err_when(resultNodePtr->node_x<0 || resultNodePtr->node_x>=MAX_WORLD_X_LOC ||
3032 resultNodePtr->node_y<0 || resultNodePtr->node_y>=MAX_WORLD_Y_LOC);
3033 }
3034 pathDist <<= 1;
3035
3036 #ifdef DEBUG
3037 //------------------------------------------------------------------------//
3038 // used to debug for the path of UNIT_SEA
3039 //------------------------------------------------------------------------//
3040 if(search_mode==SEARCH_MODE_IN_A_GROUP || search_mode==SEARCH_MODE_REUSE || search_mode==SEARCH_MODE_A_UNIT_IN_GROUP)
3041 if(mobile_type==UNIT_SEA && resultNodeCount>1 && search_mode!=SEARCH_MODE_TO_LAND_FOR_SHIP)
3042 debug_check_sea_sailable(resultNodeArray, resultNodeCount);
3043 #endif
3044
3045 return resultNodeArray;
3046 }
3047 //------- End of function SeekPath::get_result2 -------//
3048
3049
3050 //-------- Begin of function Node::generate_successors2 ---------//
generate_successors2(short realSourX,short realSourY)3051 short Node::generate_successors2(short realSourX, short realSourY)
3052 {
3053 int hasLeft = node_x > cur_border_x1;
3054 int hasRight = node_x < cur_border_x2;
3055 int hasUp = node_y > cur_border_y1;
3056 int hasDown = node_y < cur_border_y2;
3057 int upperLeftX, upperLeftY;
3058 short cost = 2;
3059
3060 upperLeftX = node_x<<1;
3061 upperLeftY = node_y<<1;
3062
3063 if(hasLeft)
3064 {
3065 //--------- Left --------//
3066 if(can_move_to(upperLeftX-2, upperLeftY) && can_move_to(upperLeftX-1, upperLeftY))
3067 {
3068 if(generate_succ2(node_x-1, node_y))
3069 return 1;
3070 }
3071
3072 //------- Upper-Left ---------//
3073 if(hasUp)
3074 {
3075 if(can_move_to(upperLeftX-2, upperLeftY-2) && can_move_to(upperLeftX-1, upperLeftY-1)) // can pass through the tile
3076 {
3077 if(generate_succ2(node_x-1, node_y-1))
3078 return 1;
3079 }
3080 }
3081
3082 //--------- Lower-Left ----------//
3083 if(hasDown)
3084 {
3085 if(can_move_to(upperLeftX-2, upperLeftY+2) && can_move_to(upperLeftX-1, upperLeftY+1))
3086 {
3087 if(generate_succ2(node_x-1, node_y+1))
3088 return 1;
3089 }
3090 }
3091 }
3092
3093 if(hasRight)
3094 {
3095 //----------- Right -----------//
3096 if(can_move_to(upperLeftX+2, upperLeftY) && can_move_to(upperLeftX+1, upperLeftY))
3097 {
3098 if(generate_succ2(node_x+1, node_y))
3099 return 1;
3100 }
3101
3102 //-------- Upper-Right ---------//
3103 if(hasUp)
3104 {
3105 if(can_move_to(upperLeftX+2, upperLeftY-2) && can_move_to(upperLeftX+1, upperLeftY-1))
3106 {
3107 if(generate_succ2(node_x+1, node_y-1))
3108 return 1;
3109 }
3110 }
3111
3112 //--------- Lower-Right ---------//
3113 if(hasDown)
3114 {
3115 if(can_move_to(upperLeftX+2, upperLeftY+2) && can_move_to(upperLeftX+1, upperLeftY+1))
3116 {
3117 if(generate_succ2(node_x+1, node_y+1))
3118 return 1;
3119 }
3120 }
3121 }
3122
3123 //---------- Upper -----------//
3124 if(hasUp)
3125 {
3126 if(can_move_to(upperLeftX, upperLeftY-2) && can_move_to(upperLeftX, upperLeftY-1))
3127 {
3128 if(generate_succ2(node_x, node_y-1))
3129 return 1;
3130 }
3131 }
3132
3133 //---------- Lower -----------//
3134 if(hasDown)
3135 {
3136 if(can_move_to(upperLeftX, upperLeftY+2) && can_move_to(upperLeftX, upperLeftY+1))
3137 {
3138 if(generate_succ2(node_x, node_y+1))
3139 return 1;
3140 }
3141 }
3142
3143 return 0;
3144 }
3145 //------- End of function Node::generate_successors2 -------//
3146
3147
3148 //-------- Begin of function Node::generate_succ2 ---------//
generate_succ2(short x,short y,short cost)3149 short Node::generate_succ2(short x, short y, short cost)
3150 {
3151 //----- if it points back to this node's parent ----//
3152 if(parent_node)
3153 {
3154 if(parent_node->node_x==x && parent_node->node_y==y)
3155 return 0;
3156 }
3157
3158 //----- if there is an existing node at the given position ----//
3159 //int upperLeftX, upperLeftY;
3160 short c, g = node_g+1; // g(Successor)=g(BestNode)+cost of getting from BestNode to Successor
3161 short nodeRecno;
3162
3163 if((nodeRecno=cur_node_matrix[y*MAX_WORLD_X_LOC/2+x]) > 0 && nodeRecno<max_node_num)
3164 {
3165 Node* oldNode = cur_node_array+nodeRecno-1;
3166
3167 //------ Add oldNode to the list of BestNode's child_noderen (or Successors).
3168 for(c=0 ; c<MAX_CHILD_NODE && child_node[c] ; c++);
3169 child_node[c]=oldNode;
3170
3171 //---- if our new g value is < oldNode's then reset oldNode's parent to point to BestNode
3172 if(g < oldNode->node_g)
3173 {
3174 oldNode->parent_node = this;
3175 oldNode->node_g = g;
3176 oldNode->node_f = g+oldNode->node_h;
3177
3178 //-------- if it's a closed node ---------//
3179 if(oldNode->child_node[0] )
3180 {
3181 //-------------------------------------------------//
3182 // Since we changed the g value of oldNode, we need
3183 // to propagate this new value downwards, i.e.
3184 // do a Depth-First traversal of the tree!
3185 //-------------------------------------------------//
3186 oldNode->propagate_down();
3187 //sys_yield();
3188 }
3189 }
3190 }
3191 else //------------ add a new node -----------//
3192 {
3193 Node* succNode = cur_node_array + cur_seek_path->node_count++;
3194
3195 memset(succNode, 0, sizeof(Node));
3196
3197 succNode->parent_node = this;
3198 succNode->node_g = g;
3199 succNode->node_h = (x-cur_dest_x)*(x-cur_dest_x)+(y-cur_dest_y)*(y-cur_dest_y); // should do sqrt(), but since we don't really
3200 succNode->node_f = g+succNode->node_h; // care about the distance but just which branch looks
3201 succNode->node_x = x; // better this should suffice. Anyayz it's faster.
3202 succNode->node_y = y;
3203
3204 if(search_mode==SEARCH_MODE_REUSE && nodeRecno>max_node_num) // path-reuse node found, but checking of can_walk(final_dest_?) is requested
3205 {
3206 final_dest_x = x<<1;
3207 final_dest_y = y<<1;
3208
3209 if(can_move_to(final_dest_x, final_dest_y)) // can_walk the connection point, accept this case
3210 {
3211 reuse_result_node_ptr = succNode;
3212 return 1;
3213 } // else continue until reuse node is found and connection point can be walked
3214 }
3215
3216 cur_node_matrix[y*MAX_WORLD_X_LOC/2+x] = cur_seek_path->node_count;
3217 cur_seek_path->open_node_list.insert_node(succNode);
3218 for(c=0 ; c<MAX_CHILD_NODE && child_node[c] ; c++); // Add oldNode to the list of BestNode's child_noderen (or succNodes).
3219 child_node[c]=succNode;
3220 }
3221
3222 return 0;
3223 }
3224 //------- End of function Node::generate_succ2 -------//
3225
3226
3227 //-------- Begin of function Node::propagate_down2 --------//
propagate_down2()3228 void Node::propagate_down2()
3229 {
3230 Node* childNode, *fatherNode;
3231 int c, g=node_g; // alias.
3232 int cost = 1;
3233 #ifdef DEBUG
3234 int middleXLoc, middleYLoc;
3235 #endif
3236
3237 for(c=0;c<8;c++)
3238 {
3239 if((childNode=child_node[c])==NULL) // create alias for faster access.
3240 break;
3241
3242 if(g+cost < childNode->node_g)
3243 {
3244 #ifdef DEBUG
3245 middleXLoc = (node_x + childNode->node_x); // calculate real coordinate
3246 middleYLoc = (node_y + childNode->node_y);
3247 if(can_move_to(middleXLoc, middleYLoc))
3248 #else
3249 if(can_move_to(node_x+childNode->node_x, node_y+childNode->node_y))
3250 #endif
3251 {
3252 childNode->node_g = g+cost;
3253 childNode->node_f = childNode->node_g+childNode->node_h;
3254 childNode->parent_node = this; // reset parent to new path.
3255
3256 stack_push(childNode); // Now the childNode's branch need to be
3257 }
3258 } // checked out. Remember the new cost must be propagated down.
3259 }
3260
3261 while(cur_stack_pos>0)
3262 {
3263 fatherNode=stack_pop();
3264 g = fatherNode->node_g;
3265
3266 for(c=0;c<8;c++)
3267 {
3268 if ((childNode=fatherNode->child_node[c])==NULL) // we may stop the propagation 2 ways: either
3269 break;
3270
3271 if(g+cost < childNode->node_g) // there are no children, or that the g value of
3272 { // the child is equal or better than the cost we're propagating
3273 #ifdef DEBUG
3274 middleXLoc = (node_x + childNode->node_x); // calculate real coordinate
3275 middleYLoc = (node_y + childNode->node_y);
3276 if(can_move_to(middleXLoc, middleYLoc))
3277 #else
3278 if(can_move_to(node_x+childNode->node_x, node_y+childNode->node_y))
3279 #endif
3280 {
3281 childNode->node_g = g+cost;
3282 childNode->node_f = childNode->node_g+childNode->node_h;
3283 childNode->parent_node = fatherNode;
3284 stack_push(childNode);
3285 }
3286 }
3287 }
3288 }
3289 }
3290 //------- End of function Node::propagate_down2 -------//
3291