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 #include <OSPREUSE.h>
22 #include <OUNIT.h>
23 #include <OWORLD.h>
24 #include <OMISC.h>
25
26 #ifdef NO_DEBUG_SEARCH
27 #undef err_when
28 #undef err_here
29 #undef err_if
30 #undef err_else
31 #undef err_now
32 #define err_when(cond)
33 #define err_here()
34 #define err_if(cond)
35 #define err_else
36 #define err_now(msg)
37 #undef debug_reuse_check_path
38 #define debug_reuse_check_path()
39 #undef DEBUG
40 #endif
41
42 #ifdef DEBUG
43 #include <OSYS.h>
44 #endif
45
46 //------------------- static function --------------------//
47 // check whether a location can be walked. This function is
48 // similar to that in SeekPath. However, only several search
49 // mode is useful here. i.e. search mode 1 and 2.
50 //
can_walk(int xLoc,int yLoc)51 int SeekPathReuse::can_walk(int xLoc, int yLoc)
52 {
53 if(xLoc>=MAX_WORLD_X_LOC || yLoc>=MAX_WORLD_Y_LOC)
54 return 0;
55
56 Location *locPtr = world.get_loc(xLoc, yLoc);
57 short recno = (mobile_type!=UNIT_AIR) ? locPtr->cargo_recno : locPtr->air_cargo_recno;
58 Unit *unitPtr;
59 uint8_t unitCurAction;
60
61 //------ check terrain id. -------//
62
63 switch(mobile_type)
64 {
65 case UNIT_LAND:
66 if(reuse_search_sub_mode==SEARCH_SUB_MODE_PASSABLE && locPtr->power_nation_recno &&
67 !reuse_nation_passable[locPtr->power_nation_recno])
68 return 0;
69
70 if(!locPtr->walkable())
71 return 0;
72
73 if(!recno)
74 return 1;
75
76 unitPtr = unit_array[recno];
77 if(search_mode==SEARCH_MODE_A_UNIT_IN_GROUP)
78 return unitPtr->cur_action==SPRITE_MOVE;
79 else
80 {
81 unitCurAction = unitPtr->cur_action;
82 return (unitPtr->unit_group_id==cur_group_id && unitCurAction!=SPRITE_ATTACK) ||
83 (unitCurAction==SPRITE_MOVE && unitPtr->cur_x-unitPtr->next_x<=ZOOM_LOC_WIDTH/2 &&
84 unitPtr->cur_y-unitPtr->next_y<=ZOOM_LOC_HEIGHT/2) ||
85 (unitPtr->nation_recno==unit_nation_recno && unitCurAction==SPRITE_IDLE);
86 }
87
88 break;
89
90 case UNIT_SEA:
91 if(!locPtr->sailable())
92 return 0;
93
94 if(!recno)
95 return 1;
96
97 unitPtr = unit_array[recno];
98 if(search_mode==SEARCH_MODE_A_UNIT_IN_GROUP)
99 return unitPtr->cur_action==SPRITE_MOVE;
100 else
101 {
102 unitCurAction = unitPtr->cur_action;
103 return (unitPtr->unit_group_id==cur_group_id && unitCurAction!=SPRITE_ATTACK) ||
104 unitCurAction==SPRITE_MOVE ||
105 (unitPtr->nation_recno==unit_nation_recno && unitCurAction==SPRITE_IDLE);
106 }
107
108 break;
109
110 case UNIT_AIR:
111 if(!recno)
112 return 1;
113
114 unitPtr = unit_array[recno];
115 if(search_mode==SEARCH_MODE_A_UNIT_IN_GROUP)
116 return unitPtr->cur_action==SPRITE_MOVE;
117 else
118 {
119 unitCurAction = unitPtr->cur_action;
120 return (unitPtr->unit_group_id==cur_group_id && unitCurAction!=SPRITE_ATTACK) ||
121 unitCurAction==SPRITE_MOVE ||
122 (unitPtr->nation_recno==unit_nation_recno && unitCurAction==SPRITE_IDLE);
123 }
124 break;
125 }
126 return 0;
127 }
128 //------------ End of static function ----------------//
129
130
131 //------------------- static function --------------------//
can_walk_s2(int xLoc,int yLoc)132 int SeekPathReuse::can_walk_s2(int xLoc, int yLoc)
133 {
134 if(xLoc>=MAX_WORLD_X_LOC-1 || yLoc>=MAX_WORLD_Y_LOC-1)
135 return 0;
136
137 if(can_walk(xLoc, yLoc) && can_walk(xLoc+1,yLoc) && can_walk(xLoc,yLoc+1) && can_walk(xLoc+1,yLoc+1))
138 return 1;
139 else
140 return 0;
141 }
142 //------------ End of static function ----------------//
143
144
145 //------------------- static function --------------------//
sys_yield()146 void SeekPathReuse::sys_yield()
147 {
148 //sys.yield();
149 }
150 //------------ End of static function ----------------//
151
152
153 //-------- Begin of function SeekPathReuse::seek_path_offset ---------//
seek_path_offset()154 void SeekPathReuse::seek_path_offset()
155 {
156 if(!is_leader_path_valid())
157 return;
158
159 if(is_node_avail_empty())
160 {
161 copy_leader_path_offset();
162 return;
163 }
164
165 //------------ construct data structure to store result node ----------------//
166 result_node_array_def_size += result_node_array_reset_amount;
167 path_reuse_result_node_ptr = (ResultNode*) mem_add(sizeof(ResultNode)* result_node_array_def_size);
168 memset(path_reuse_result_node_ptr, 0, sizeof(ResultNode)* result_node_array_def_size);
169 cur_result_node_ptr = path_reuse_result_node_ptr;
170 num_of_result_node = 0;
171
172 //---------------- set starting point ----------------------//
173 add_result(start_x, start_y);
174
175 //-----------------initialize offset path reuse ------------//
176 cur_leader_node_ptr = reuse_leader_path_backup+1;
177 cur_leader_node_num = 2;
178 use_offset_method(reuse_leader_path_backup[0].node_x, reuse_leader_path_backup[0].node_y); // using offset path method directly
179
180 //----------------------------------------------------------------------//
181 // checking for incomplete searching
182 //----------------------------------------------------------------------//
183 ResultNode *lastNode = path_reuse_result_node_ptr + num_of_result_node - 1;
184 if((lastNode->node_x!=vir_dest_x || lastNode->node_y!=vir_dest_y) && is_node_avail_empty())
185 {
186 incomplete_search++;
187 reuse_path_status = REUSE_PATH_INCOMPLETE_SEARCH;
188 }
189 }
190 //--------- End of function SeekPathReuse::seek_path_offset ---------//
191
192
193 //-------- Begin of function SeekPathReuse::seek_path_join_offset ---------//
194 // The join-offset-path method.
195 //
seek_path_join_offset()196 void SeekPathReuse::seek_path_join_offset()
197 {
198 if(!is_leader_path_valid())
199 return;
200
201 //----------------------------------------------------------------------//
202 // checking for incomplete searching
203 //----------------------------------------------------------------------//
204 if(is_node_avail_empty())
205 {
206 incomplete_search++;
207 reuse_path_status = REUSE_PATH_INCOMPLETE_SEARCH;
208 return;
209 }
210
211 err_when(unit_size!=1);
212 memset(reuse_node_matrix, 0, sizeof(short)*MAX_WORLD_X_LOC*MAX_WORLD_Y_LOC/4);
213 path_reuse_result_node_ptr = NULL;
214
215 //--------------------------------------------------------------//
216 // initialization and declaring variables
217 //--------------------------------------------------------------//
218 int connectResultNodeNum;
219 ResultNode* connectResultNodePtr=NULL;
220
221 cur_leader_node_ptr = reuse_leader_path_backup;
222 cur_leader_node_num = 1;
223
224 int leaderNodeXLoc = cur_leader_node_ptr->node_x;
225 int leaderNodeYLoc = cur_leader_node_ptr->node_y;
226
227 #ifdef DEBUG
228 int debugLoopCount = 0;
229 #endif
230
231 do
232 {
233 err_when(++debugLoopCount>10000);
234 set_index_in_node_matrix(leaderNodeXLoc+x_offset, leaderNodeYLoc+y_offset);
235 }while(get_next_offset_loc(leaderNodeXLoc, leaderNodeYLoc));
236
237 //--------------------------------------------------------------//
238 // copy the node_matrix to that node_matrix used in class SeekPath
239 //--------------------------------------------------------------//
240 err_when(unit_size!=1);
241 seek_path.set_node_matrix(reuse_node_matrix);
242
243 //--------------------------------------------------------------//
244 // process shortest path searching to find a walkable point in
245 // the offset path for connection
246 //--------------------------------------------------------------//
247 //--- if the starting location is already in the offset path, process it immediately ---//
248 err_when(unit_size!=1);
249 short *locNode = reuse_node_matrix + MAX_WORLD_X_LOC/2*(start_y/2) + (start_x/2);
250
251 if(*locNode > max_node && mobile_type==UNIT_LAND) // starting point on the reuse offset path
252 {
253 connectResultNodePtr = (ResultNode*) mem_add(sizeof(ResultNode)*2);
254 ResultNode* curNode = connectResultNodePtr;
255 curNode->node_x = start_x;
256 curNode->node_y = start_y;
257 connectResultNodeNum = 1;
258 curNode++;
259
260 switch(*locNode-max_node)
261 {
262 case 1: if(start_x%2 || start_y%2)
263 {
264 curNode->node_x = (start_x%2) ? start_x-1 : start_x;
265 curNode->node_y = (start_y%2) ? start_y-1 : start_y;
266 connectResultNodeNum++;
267 }
268 break;
269
270 case 2: if(!(start_x%2 && start_y%2==0))
271 {
272 curNode->node_x = (start_x%2) ? start_x : start_x+1;
273 curNode->node_y = (start_y%2) ? start_y-1 : start_y;
274 connectResultNodeNum++;
275 }
276 break;
277
278 case 3: if(!(start_x%2==0 && start_y%2))
279 {
280 curNode->node_x = (start_x%2) ? start_x-1 : start_x;
281 curNode->node_y = (start_y%2) ? start_y : start_y+1;
282 connectResultNodeNum++;
283 }
284 break;
285
286 case 4: if(start_x%2==0 || start_y%2==0)
287 {
288 curNode->node_x = (start_x%2) ? start_x : start_x+1;
289 curNode->node_y = (start_y%2) ? start_y : start_y+1;
290 connectResultNodeNum++;
291 }
292 break;
293 }
294
295 //********BUGHERE
296 // unable to handle this blocked case now, abort path-reuse and seeking instead
297 if(connectResultNodeNum>1 && !can_walk(curNode->node_x, curNode->node_y))
298 {
299 path_reuse_result_node_ptr = call_seek(start_x, start_y, vir_dest_x, vir_dest_y, cur_group_id, mobile_type, SEARCH_MODE_IN_A_GROUP, num_of_result_node);
300 mem_del(connectResultNodePtr);
301 return;
302 }
303 }
304 else
305 {
306 //------------- seek for connection point ------------//
307 connectResultNodePtr = call_seek(start_x, start_y, vir_dest_x, vir_dest_y, cur_group_id, mobile_type,
308 SEARCH_MODE_REUSE, connectResultNodeNum);
309 err_when(connectResultNodePtr!=NULL && connectResultNodeNum<2);
310
311 if(connectResultNodePtr==NULL || connectResultNodeNum==0) // cannot reach the destination
312 {
313 if(connectResultNodePtr!=NULL)
314 mem_del(connectResultNodePtr);
315
316 return;
317 }
318 }
319
320 //--------------------------------------------------------------//
321 // constructing data structure
322 //--------------------------------------------------------------//
323 result_node_array_def_size += result_node_array_reset_amount;
324 path_reuse_result_node_ptr = (ResultNode*) mem_add(sizeof(ResultNode)* result_node_array_def_size);
325 memset(path_reuse_result_node_ptr, 0, sizeof(ResultNode)* result_node_array_def_size);
326 cur_result_node_ptr = path_reuse_result_node_ptr;
327 num_of_result_node = 0;
328
329 //--------------------------------------------------------------//
330 // add the result path
331 //--------------------------------------------------------------//
332 ResultNode* curResultNode = connectResultNodePtr;
333 for(int i=0; i<connectResultNodeNum; i++)
334 {
335 add_result(curResultNode->node_x, curResultNode->node_y);
336 curResultNode++;
337 }
338
339 //--------------------------------------------------------------//
340 // determine the joining point in the offset path
341 //--------------------------------------------------------------//
342 cur_leader_node_ptr = reuse_leader_path_backup;
343 cur_leader_node_num = 1;
344
345 ResultNode *endNode = connectResultNodePtr + connectResultNodeNum - 1;
346 short findConnectionPoint = 0;
347
348 if(endNode->node_x==vir_dest_x && endNode->node_y==vir_dest_y)
349 {
350 if(connectResultNodePtr!=NULL)
351 mem_del(connectResultNodePtr);
352 return; // already the destination location
353 }
354
355 //------------------------------------------------------------------------------------//
356 // find a offset-reference point in leader path
357 //------------------------------------------------------------------------------------//
358 leaderNodeXLoc = cur_leader_node_ptr->node_x;
359 leaderNodeYLoc = cur_leader_node_ptr->node_y;
360 short notEnd = 1;
361 sys_yield(); // update cursor position
362
363 int unitDestX, unitDestY; // for the current searching unit, using the leader path
364 do
365 {
366 //---------- boundary checking -----------//
367 bound_check_x((unitDestX = leaderNodeXLoc+x_offset));
368 bound_check_y((unitDestY = leaderNodeYLoc+y_offset));
369
370 if(endNode->node_x==unitDestX && endNode->node_y==unitDestY)
371 findConnectionPoint = 1; // ok, connected
372 else
373 notEnd = get_next_offset_loc(leaderNodeXLoc, leaderNodeYLoc);
374
375 if(!notEnd)
376 break;
377 }while(!findConnectionPoint);
378
379 sys_yield(); // update cursor position
380
381 //-------------- clear the temporary path ------------//
382 if(connectResultNodePtr!=NULL)
383 mem_del(connectResultNodePtr);
384
385 //-----------------------------------------------------------------------------//
386 // return since cannot find a connection point
387 //-----------------------------------------------------------------------------//
388 if(!findConnectionPoint)
389 {
390 //----------------------------------------------------------------------//
391 // checking for incomplete searching
392 //----------------------------------------------------------------------//
393 if(is_node_avail_empty())
394 {
395 incomplete_search++;
396 reuse_path_status = REUSE_PATH_INCOMPLETE_SEARCH;
397 }
398
399 if(num_of_result_node==1)
400 {
401 mem_del(path_reuse_result_node_ptr);
402 path_reuse_result_node_ptr = NULL;
403 num_of_result_node = 0;
404 }
405 return;
406 }
407
408 //-----------------------------------------------------------------------------//
409 // update pointer cur_leader_node_ptr if necessary
410 //-----------------------------------------------------------------------------//
411 if(leaderNodeXLoc==cur_leader_node_ptr->node_x && leaderNodeYLoc==cur_leader_node_ptr->node_y) // at the turning point
412 {
413 if(cur_leader_node_num < reuse_leader_path_node_num)
414 {
415 cur_leader_node_num++;
416 cur_leader_node_ptr++;
417 }
418 else // join at the end of the offset path, search finished
419 return;
420 }
421
422 //----------------------------------------------------------------------------------------//
423 // at this moment, the searching unit has a offset path to the leader path.
424 // There are not processed leader nodes. These nodes are pointed by cur_leader_node_ptr.
425 //----------------------------------------------------------------------------------------//
426 use_offset_method(leaderNodeXLoc, leaderNodeYLoc); // changed to offset method for the rest
427
428 //----------------------------------------------------------------------//
429 // checking for incomplete searching
430 //----------------------------------------------------------------------//
431 ResultNode *lastNode = path_reuse_result_node_ptr + num_of_result_node - 1;
432 if((lastNode->node_x!=vir_dest_x || lastNode->node_y!=vir_dest_y) && is_node_avail_empty())
433 {
434 incomplete_search++;
435 reuse_path_status = REUSE_PATH_INCOMPLETE_SEARCH;
436 }
437 }
438 //--------- End of function SeekPathReuse::seek_path_join_offset ---------//
439
440
441 //-------- Begin of function SeekPathReuse::use_offset_method ---------//
use_offset_method(int xLoc,int yLoc)442 void SeekPathReuse::use_offset_method(int xLoc, int yLoc)
443 {
444 //----------------------------------------------------------------------//
445 // checking for incomplete searching
446 //----------------------------------------------------------------------//
447 if(is_node_avail_empty())
448 {
449 incomplete_search++;
450 reuse_path_status = REUSE_PATH_INCOMPLETE_SEARCH;
451 return;
452 }
453
454 //-----------------------------------------------------//
455 int leaderNodeXLoc = xLoc; // hold the currently referred leader node
456 int leaderNodeYLoc = yLoc;
457
458 leader_vec_x = cur_leader_node_ptr->node_x - leaderNodeXLoc;
459 leader_vec_y = cur_leader_node_ptr->node_y - leaderNodeYLoc;
460 if(leader_vec_x!=0)
461 leader_vec_x /= abs(leader_vec_x);
462 if(leader_vec_y!=0)
463 leader_vec_y /= abs(leader_vec_y);
464
465 ResultNode *partOfResultNodePtr, *curNodePtr;
466 int partOfResultNodeNum, restNode;
467
468 partOfResultNodePtr = NULL;
469 partOfResultNodeNum = 0;
470
471 //-----------------------------------------------------//
472 int unitNodeXLoc, unitNodeYLoc;
473 int preNonblockedXLoc, preNonblockedYLoc;
474 int nextNonblockedLeaderXLoc, nextNonblockedLeaderYLoc;
475 int preLeaderVecX, preLeaderVecY;
476 int virDestX, virDestY;
477 int pathSeekResult, canReach;
478
479 //-----------------------------------------------------//
480 // start walking along the leader path
481 //-----------------------------------------------------//
482 #ifdef DEBUG
483 int debugPreLeaderNodeXLoc, debugPreLeaderNodeYLoc;
484 while(debugPreLeaderNodeXLoc=leaderNodeXLoc, debugPreLeaderNodeYLoc=leaderNodeYLoc,
485 get_next_offset_loc(leaderNodeXLoc, leaderNodeYLoc)) // get next location in the leader path
486 #else
487 while(get_next_offset_loc(leaderNodeXLoc, leaderNodeYLoc)) // get next location in the leader path
488 #endif
489 {
490 err_when(leaderNodeXLoc<0 || leaderNodeXLoc>=MAX_WORLD_X_LOC);
491 err_when(leaderNodeYLoc<0 || leaderNodeYLoc>=MAX_WORLD_Y_LOC);
492
493 err_when(partOfResultNodePtr!=NULL);
494 sys_yield(); // update cursor position
495
496 unitNodeXLoc = leaderNodeXLoc+x_offset; // calculate the corresponding location in the offset path.
497 unitNodeYLoc = leaderNodeYLoc+y_offset;
498
499 if(unitNodeXLoc>=0 && unitNodeXLoc<MAX_WORLD_X_LOC && unitNodeYLoc>=0 && unitNodeYLoc<MAX_WORLD_Y_LOC &&
500 ((move_scale==1 && can_walk(unitNodeXLoc, unitNodeYLoc)) ||
501 (move_scale==2 && can_walk(unitNodeXLoc, unitNodeYLoc) &&
502 can_walk(unitNodeXLoc-leader_vec_x, unitNodeYLoc-leader_vec_y)) ))
503 {
504 //----------------------------------------------------------------------------//
505 // offset node exists, so add it to the result path
506 //----------------------------------------------------------------------------//
507 add_result(unitNodeXLoc, unitNodeYLoc); // add result if location can be reached
508 if(unitNodeXLoc==vir_dest_x && unitNodeYLoc==vir_dest_y)
509 break;
510 }
511 else
512 {
513 //----------------------------------------------------------------------------//
514 // get the next non-blocked location calculated by offset
515 //----------------------------------------------------------------------------//
516 nextNonblockedLeaderXLoc = leaderNodeXLoc; // used as reference
517 nextNonblockedLeaderYLoc = leaderNodeYLoc;
518 preLeaderVecX = leader_vec_x;
519 preLeaderVecY = leader_vec_y;
520
521 //========================================================================//
522 //========================================================================//
523 if(get_next_nonblocked_offset_loc(nextNonblockedLeaderXLoc, nextNonblockedLeaderYLoc)) // get the next nonblocked location for joining
524 {
525 if(is_node_avail_empty())
526 {
527 incomplete_search++;
528 reuse_path_status = REUSE_PATH_INCOMPLETE_SEARCH;
529 return;
530 }
531
532 //--- seek from the current location to the next non-blocked location ---//
533 err_when(num_of_result_node<1);
534 preNonblockedXLoc = (cur_result_node_ptr-1)->node_x;
535 preNonblockedYLoc = (cur_result_node_ptr-1)->node_y;
536 //bound_check_x((preNonblockedXLoc = unitNodeXLoc-preLeaderVecX*move_scale));
537 //bound_check_y((preNonblockedYLoc = unitNodeYLoc-preLeaderVecY*move_scale));
538 err_when(preNonblockedXLoc<0 || preNonblockedXLoc>=MAX_WORLD_X_LOC);
539 err_when(preNonblockedYLoc<0 || preNonblockedYLoc>=MAX_WORLD_Y_LOC);
540
541 //-------- find a path to the next non-blocked location ----------//
542 bound_check_x((virDestX = nextNonblockedLeaderXLoc+x_offset));
543 bound_check_y((virDestY = nextNonblockedLeaderYLoc+y_offset));
544 err_when(partOfResultNodePtr!=NULL);
545
546 err_when(unit_size!=1);
547 pathSeekResult = seek_path.seek(preNonblockedXLoc, preNonblockedYLoc, virDestX, virDestY,
548 cur_group_id, mobile_type, SEARCH_MODE_IN_A_GROUP);
549 partOfResultNodePtr = seek_path.get_result(partOfResultNodeNum, reuse_path_dist);
550
551 //--------------------------------------------------------------------------//
552 // go to destination directly if cannot reach the next nonblocked lcoation
553 //--------------------------------------------------------------------------//
554 if(partOfResultNodePtr==NULL || partOfResultNodeNum==0)
555 canReach = 0;
556 else
557 {
558 #ifdef DEBUG
559 int ddX = abs((cur_result_node_ptr-1)->node_x-partOfResultNodePtr[0].node_x);
560 int ddY = abs((cur_result_node_ptr-1)->node_y-partOfResultNodePtr[0].node_y);
561 err_when(ddX && ddY && ddX!=ddY);
562 #endif
563
564 ResultNode *curNode = partOfResultNodePtr + partOfResultNodeNum-1;
565 if(curNode->node_x==virDestX && curNode->node_y==virDestY)
566 canReach = 1;
567 else
568 {
569 canReach = 0;
570 mem_del(partOfResultNodePtr);
571 partOfResultNodePtr = NULL;
572 }
573 }
574
575 if(canReach==0) // unable to reach the location specified
576 {
577 if(is_node_avail_empty())
578 {
579 incomplete_search++;
580 reuse_path_status = REUSE_PATH_INCOMPLETE_SEARCH;
581 return;
582 }
583
584 bound_check_x((virDestX = dest_x));
585 bound_check_y((virDestY = dest_y));
586 err_when(partOfResultNodePtr!=NULL);
587
588 err_when(unit_size!=1);
589 int pathSeekResult= seek_path.seek(preNonblockedXLoc, preNonblockedYLoc, virDestX, virDestY, cur_group_id, mobile_type, SEARCH_MODE_IN_A_GROUP);
590 partOfResultNodePtr = seek_path.get_result(partOfResultNodeNum, reuse_path_dist);
591
592 #ifdef DEBUG
593 if(partOfResultNodePtr!=NULL)
594 {
595 int ddX = abs((cur_result_node_ptr-1)->node_x-partOfResultNodePtr[0].node_x);
596 int ddY = abs((cur_result_node_ptr-1)->node_y-partOfResultNodePtr[0].node_y);
597 err_when(ddX && ddY && ddX!=ddY);
598 }
599 #endif
600 }
601
602 //---------------------- connect the two paths ----------------------//
603 if(partOfResultNodePtr!=NULL)
604 {
605 restNode = partOfResultNodeNum;
606 curNodePtr = partOfResultNodePtr;
607
608 err_when(preNonblockedXLoc!=partOfResultNodePtr->node_x || preNonblockedYLoc!=partOfResultNodePtr->node_y);
609
610 restNode--;
611 curNodePtr++;
612 while(restNode)
613 {
614 add_result(curNodePtr->node_x, curNodePtr->node_y);
615 curNodePtr++;
616 restNode--;
617 }
618
619 debug_reuse_check_path(); //-************** debug checking
620
621 mem_del(partOfResultNodePtr);
622 partOfResultNodePtr = NULL;
623 }
624
625 err_when(partOfResultNodePtr!=NULL);
626
627 if(canReach)
628 {
629 leaderNodeXLoc = nextNonblockedLeaderXLoc;
630 leaderNodeYLoc = nextNonblockedLeaderYLoc;
631 }
632 else
633 {
634 //------------------------------------------------//
635 // incomplete search
636 //------------------------------------------------//
637 if(is_node_avail_empty())
638 {
639 incomplete_search++;
640 reuse_path_status = REUSE_PATH_INCOMPLETE_SEARCH;
641 return;
642 }
643 break;
644 }
645
646 if(pathSeekResult!=PATH_FOUND && pathSeekResult!=PATH_REUSE_FOUND)
647 break;
648 }
649 //========================================================================//
650 //========================================================================//
651 else // no next non-blocked offset location, searching directly to the destinaton
652 {
653 //-------------------------------------------------------------//
654 // move directly to the destination from the current location
655 //
656 // This case occurs when the destination cannot be reached.
657 //-------------------------------------------------------------//
658
659 //--- seek from the current location to the destination ---//
660 //bound_check_x((preNonblockedXLoc = unitNodeXLoc-preLeaderVecX*move_scale));
661 //bound_check_y((preNonblockedYLoc = unitNodeYLoc-preLeaderVecY*move_scale));
662 err_when(num_of_result_node<1);
663 preNonblockedXLoc = (cur_result_node_ptr-1)->node_x;
664 preNonblockedYLoc = (cur_result_node_ptr-1)->node_y;
665 err_when(preNonblockedXLoc<0 || preNonblockedXLoc>=MAX_WORLD_X_LOC);
666 err_when(preNonblockedYLoc<0 || preNonblockedYLoc>=MAX_WORLD_Y_LOC);
667
668 bound_check_x((virDestX = nextNonblockedLeaderXLoc+x_offset));
669 bound_check_y((virDestY = nextNonblockedLeaderYLoc+y_offset));
670 err_when(partOfResultNodePtr!=NULL);
671
672 //------------------------------------------------//
673 // set to incomplete_search for later searching
674 //------------------------------------------------//
675 incomplete_search++;
676 reuse_path_status = REUSE_PATH_INCOMPLETE_SEARCH;
677
678 #ifdef DEBUG
679 int ddX1 = abs((cur_result_node_ptr-1)->node_x-preNonblockedXLoc);
680 int ddY1 = abs((cur_result_node_ptr-1)->node_y-preNonblockedYLoc);
681 err_when(ddX1 && ddY1 && ddX1!=ddY1);
682 #endif
683
684 err_when(unit_size!=1);
685 seek_path.seek(preNonblockedXLoc, preNonblockedYLoc, virDestX, virDestY, cur_group_id, mobile_type, 1);
686 partOfResultNodePtr = seek_path.get_result(partOfResultNodeNum, reuse_path_dist);
687
688 //---------------- connect the two paths together ----------------//
689 if(partOfResultNodePtr!=NULL)
690 {
691 #ifdef DEBUG
692 int ddX = abs((cur_result_node_ptr-1)->node_x-partOfResultNodePtr[0].node_x);
693 int ddY = abs((cur_result_node_ptr-1)->node_y-partOfResultNodePtr[0].node_y);
694 err_when(ddX && ddY && ddX!=ddY);
695 #endif
696
697 err_when(preNonblockedXLoc!=partOfResultNodePtr->node_x || preNonblockedYLoc!=partOfResultNodePtr->node_y);
698
699 restNode = partOfResultNodeNum-1;
700 curNodePtr = partOfResultNodePtr+1;
701
702 while(restNode)
703 {
704 add_result(curNodePtr->node_x, curNodePtr->node_y);
705 curNodePtr++;
706 restNode--;
707 }
708
709 debug_reuse_check_path(); //-************** debug checking
710
711 mem_del(partOfResultNodePtr);
712 partOfResultNodePtr = NULL;
713 }
714 }//end if get_next_nonblocked_offset_loc()
715
716 //-------------------------------------------------------------------------------------------------//
717 // update leaderNode?Loc since it may be changed after calling get_next_nonblocked_offset_loc()
718 //-------------------------------------------------------------------------------------------------//
719 leaderNodeXLoc = nextNonblockedLeaderXLoc;
720 leaderNodeYLoc = nextNonblockedLeaderYLoc;
721 }
722
723 debug_reuse_check_path(); //-************** debug checking
724 err_when(partOfResultNodePtr!=NULL);
725 } // end while
726
727 err_when(partOfResultNodePtr!=NULL);
728 debug_reuse_check_path(); //-************** debug checking
729 }
730 //--------- End of function SeekPathReuse::use_offset_method ---------//
731
732
733 //-------- Begin of function SeekPathReuse::get_next_nonblocked_offset_loc ---------//
734 // find the next nonblocked offset location if the inputed location is blocked
735 // return 1 if found, 0 for none
736 //
get_next_nonblocked_offset_loc(int & nextXLoc,int & nextYLoc)737 int SeekPathReuse::get_next_nonblocked_offset_loc(int& nextXLoc, int&nextYLoc)
738 {
739 int found = 0;
740 int unitDestX, unitDestY;
741
742 /*#ifdef DEBUG
743 int debugLoopCount = 0;
744 #endif
745
746 while(!found)
747 {
748 err_when(++debugLoopCount>10000);
749 if(!get_next_offset_loc(nextXLoc, nextYLoc))
750 break; // all nodes visited
751
752 unitDestX = nextXLoc+x_offset;
753 unitDestY = nextYLoc+y_offset;
754
755 err_when(unit_size!=1);
756 if(unitDestX>=0 && unitDestX<MAX_WORLD_X_LOC && unitDestY>=0 && unitDestY<MAX_WORLD_Y_LOC &&
757 can_walk(unitDestX, unitDestY))
758 found = 1;
759 }
760
761 return found;*/
762 while(!found)
763 {
764 if(nextXLoc != cur_leader_node_ptr->node_x || nextYLoc != cur_leader_node_ptr->node_y)
765 {
766 nextXLoc += leader_vec_x;
767 nextYLoc += leader_vec_y;
768
769 unitDestX = nextXLoc+x_offset;
770 unitDestY = nextYLoc+y_offset;
771
772 err_when(unit_size!=1);
773 if(unitDestX>=0 && unitDestX<MAX_WORLD_X_LOC && unitDestY>=0 && unitDestY<MAX_WORLD_Y_LOC &&
774 can_walk(unitDestX, unitDestY))
775 found = 1;
776 }
777 else
778 {
779 if(cur_leader_node_num < reuse_leader_path_node_num)
780 {
781 cur_leader_node_num++;
782 cur_leader_node_ptr++;
783 leader_vec_x = cur_leader_node_ptr->node_x - nextXLoc;
784 leader_vec_y = cur_leader_node_ptr->node_y - nextYLoc;
785 if(leader_vec_x!=0)
786 {
787 leader_vec_x /= abs(leader_vec_x);
788 nextXLoc += leader_vec_x;
789 }
790 if(leader_vec_y!=0)
791 {
792 leader_vec_y /= abs(leader_vec_y);
793 nextYLoc += leader_vec_y;
794 }
795
796 unitDestX = nextXLoc+x_offset;
797 unitDestY = nextYLoc+y_offset;
798
799 err_when(unit_size!=1);
800 if(unitDestX>=0 && unitDestX<MAX_WORLD_X_LOC && unitDestY>=0 && unitDestY<MAX_WORLD_Y_LOC &&
801 can_walk(unitDestX, unitDestY))
802 found = 1;
803 }
804 else
805 break; // or return 0;
806 }
807
808 sys_yield(); // update cursor position
809 }
810
811 return found;
812 }
813 //--------- End of function SeekPathReuse::get_next_nonblocked_offset_loc ---------//
814
815
816 //-------- Begin of function SeekPathReuse::get_next_offset_loc ---------//
817 // get the next location along the main path (reuse reference path)
818 // return 1 if found, 0 for end of the path
819 //
get_next_offset_loc(int & nextXLoc,int & nextYLoc)820 int SeekPathReuse::get_next_offset_loc(int& nextXLoc, int& nextYLoc)
821 {
822 if(nextXLoc != cur_leader_node_ptr->node_x || nextYLoc != cur_leader_node_ptr->node_y)
823 {
824 //--------- point in a the middle of two nodes ----------//
825 nextXLoc += leader_vec_x*move_scale;
826 nextYLoc += leader_vec_y*move_scale;
827 return 1;
828 }
829 else if(cur_leader_node_num < reuse_leader_path_node_num)
830 {
831 //------------- the end of a node ----------//
832 cur_leader_node_num++;
833 cur_leader_node_ptr++;
834 leader_vec_x = cur_leader_node_ptr->node_x - nextXLoc;
835 leader_vec_y = cur_leader_node_ptr->node_y - nextYLoc;
836 err_when(leader_vec_x!=0 && leader_vec_y!=0 && abs(leader_vec_x)!=abs(leader_vec_y));
837
838 if(leader_vec_x!=0)
839 {
840 leader_vec_x /= abs(leader_vec_x);
841 nextXLoc += leader_vec_x*move_scale;
842 }
843 if(leader_vec_y!=0)
844 {
845 leader_vec_y /= abs(leader_vec_y);
846 nextYLoc += leader_vec_y*move_scale;
847 }
848
849 err_when(nextXLoc<0 || nextXLoc>=MAX_WORLD_X_LOC);
850 err_when(nextYLoc<0 || nextYLoc>=MAX_WORLD_Y_LOC);
851 return 1;
852 }
853 else
854 return 0;
855 }
856 //--------- End of function SeekPathReuse::get_next_offset_loc ---------//
857
858
859 //-------- Begin of function SeekPathReuse::copy_leader_path_offset ---------//
copy_leader_path_offset()860 void SeekPathReuse::copy_leader_path_offset()
861 {
862 if(!is_leader_path_valid())
863 {
864 incomplete_search++;
865 reuse_path_status = REUSE_PATH_INCOMPLETE_SEARCH;
866 return;
867 }
868
869 err_when(leader_path_num<0 || leader_path_num>total_num_of_path);
870 cur_leader_node_ptr = reuse_leader_path_backup;
871 cur_leader_node_num = 1;
872
873 ResultNode *curNodePtr = cur_leader_node_ptr;
874 err_when(curNodePtr->node_x+x_offset<0 || curNodePtr->node_x+x_offset>=MAX_WORLD_X_LOC ||
875 curNodePtr->node_y+y_offset<0 || curNodePtr->node_y+y_offset>=MAX_WORLD_Y_LOC);
876
877 int preXLoc = curNodePtr->node_x+x_offset;
878 int preYLoc = curNodePtr->node_y+y_offset;
879 add_result(preXLoc, preYLoc);
880
881 int curXLoc, curYLoc;
882 curNodePtr++;
883
884 int status = 0; // 0 for current position inside map, 1 for outside map
885 int checkXLoc, checkYLoc;
886 int vecX, vecY, magnX, magnY, magn;
887 int i, quitLoop;
888 Location *locPtr;
889
890 while(cur_leader_node_num++<reuse_leader_path_node_num)
891 {
892 curXLoc = curNodePtr->node_x+x_offset;
893 curYLoc = curNodePtr->node_y+y_offset;
894
895 //----------------------------------------------------------------------//
896 // offset method is terminated when the path leaves the map region for
897 // this version.
898 //----------------------------------------------------------------------//
899 if(curXLoc>=0 && curXLoc<MAX_WORLD_X_LOC && curYLoc>=0 && curYLoc<MAX_WORLD_Y_LOC) // inside map
900 {
901 //----------------------------------------------------------------------//
902 // checking passable condition
903 //----------------------------------------------------------------------//
904 if(reuse_search_sub_mode==SEARCH_SUB_MODE_PASSABLE)
905 {
906 vecX = curXLoc-preXLoc;
907 vecY = curYLoc-preYLoc;
908 magn = ((magnX=abs(vecX)) > (magnY=abs(vecY))) ? magnX : magnY;
909 if(magnX) vecX /= magnX;
910 if(magnY) vecY /= magnY;
911 checkXLoc = preXLoc;
912 checkYLoc = preYLoc;
913 quitLoop = 0;
914
915 for(i=0; i<magn; ++i)
916 {
917 checkXLoc += vecX;
918 checkYLoc += vecY;
919 locPtr = world.get_loc(checkXLoc, checkYLoc);
920 if(locPtr->power_nation_recno && !reuse_nation_passable[locPtr->power_nation_recno])
921 {
922 quitLoop = 1;
923 break; // can't handle this case: not passable and copying leader path
924 }
925 }
926
927 if(quitLoop)
928 break;
929 }
930
931 status = 0;
932 if(!status) // inside
933 move_within_map(preXLoc, preYLoc, curXLoc, curYLoc);
934 else // outside
935 //move_inside_map(preXLoc, preYLoc, curXLoc, curYLoc);
936 break;
937 }
938 else // outside
939 {
940 //----------------------------------------------------------------------//
941 // checking passable condition
942 //----------------------------------------------------------------------//
943 if(reuse_search_sub_mode==SEARCH_SUB_MODE_PASSABLE)
944 break;
945
946 status = 1;
947 if(!status) // inside
948 {
949 move_outside_map(preXLoc, preYLoc, curXLoc, curYLoc);
950 break;
951 }
952 else // outside
953 //move_beyond_map(preXLoc, preYLoc, curXLoc, curYLoc);
954 break;
955 }
956
957 debug_reuse_check_path(); //-************** debug checking
958 preXLoc = curXLoc;
959 preYLoc = curYLoc;
960 curNodePtr++;
961 }
962
963 debug_reuse_check_path(); //-************** debug checking
964 }
965 //--------- End of function SeekPathReuse::copy_leader_path_offset ---------//
966