home *** CD-ROM | disk | FTP | other *** search
/ Amiga Times / AmigaTimes.iso / spiele / FreeCiv / src / freeciv-1.7.0 / server / gotohand.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-10-06  |  24.2 KB  |  707 lines
  1. /********************************************************************** 
  2.  Freeciv - Copyright (C) 1996 - A Kjeldberg, L Gregersen, P Unold
  3.    This program is free software; you can redistribute it and/or modify
  4.    it under the terms of the GNU General Public License as published by
  5.    the Free Software Foundation; either version 2, or (at your option)
  6.    any later version.
  7.  
  8.    This program is distributed in the hope that it will be useful,
  9.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  10.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11.    GNU General Public License for more details.
  12. ***********************************************************************/
  13. #include <stdio.h>
  14. #include <stdlib.h>
  15. #include <assert.h>
  16. #include <string.h>
  17.  
  18. #include <map.h>
  19. #include <game.h>
  20. #include <unitfunc.h>
  21. #include <unithand.h>
  22. #include <unittools.h>
  23. #include <gotohand.h>
  24. #include <settlers.h>
  25.  
  26. struct move_cost_map warmap;
  27.  
  28. struct stack_element {
  29.   unsigned char x, y;
  30. } warstack[MAP_MAX_WIDTH * MAP_MAX_HEIGHT];
  31.  
  32. /* this wastes ~20K of memory and should really be fixed but I'm lazy  -- Syela */
  33.  
  34. int warstacksize;
  35. int warnodes;
  36.  
  37. void add_to_stack(int x, int y)
  38. {
  39.   warstack[warstacksize].x = x;
  40.   warstack[warstacksize].y = y;
  41.   warstacksize++;
  42. }
  43.  
  44. void init_warmap(int orig_x, int orig_y, enum unit_move_type which)
  45. {
  46.   int x, y, i, j;
  47.   int maxcost = THRESHOLD * 6 + 2; /* should be big enough without being TOO big */
  48.   for (x = 0; x < map.xsize; x++) {
  49.     if (x > orig_x)
  50.       i = MIN(x - orig_x, orig_x + map.xsize - x);
  51.     else
  52.       i = MIN(orig_x - x, x + map.xsize - orig_x);      
  53.     for (y = 0; y < map.ysize; y++) {
  54.       if (y > orig_y)
  55.         j = MAX(y - orig_y, i);
  56.       else
  57.         j = MAX(orig_y - y, i);
  58.       j *= 3;
  59.       if (j < maxcost) j = maxcost;
  60.       if (j > 255) j = 255;
  61.       if (which == LAND_MOVING) warmap.cost[x][y] = j; /* one if by land */
  62.       else warmap.seacost[x][y] = j;
  63.     }
  64.   }
  65.   if (which == LAND_MOVING) warmap.cost[orig_x][orig_y] = 0;
  66.   else warmap.seacost[orig_x][orig_y] = 0;
  67. }  
  68.  
  69. void really_generate_warmap(struct city *pcity, struct unit *punit, enum unit_move_type which)
  70. { /* let generate_warmap interface to this function */
  71.   int x, y, c, i, j, k, xx[3], yy[3], tm;
  72.   int orig_x, orig_y;
  73.   int igter = 0;
  74.   int ii[8] = { 0, 1, 2, 0, 2, 0, 1, 2 };
  75.   int jj[8] = { 0, 0, 0, 1, 1, 2, 2, 2 };
  76.   int maxcost = THRESHOLD * 6 + 2; /* should be big enough without being TOO big */
  77.   struct tile *tile0;
  78.   struct player *pplayer;
  79.  
  80.   if (pcity) {
  81.     orig_x = pcity->x;
  82.     orig_y = pcity->y;
  83.     pplayer = &game.players[pcity->owner];
  84.   } else {
  85.     orig_x = punit->x;
  86.     orig_y = punit->y;
  87.     pplayer = &game.players[punit->owner];
  88.   }
  89.  
  90.   init_warmap(orig_x, orig_y, which);
  91.   warstacksize = 0;
  92.   warnodes = 0;
  93.  
  94.   add_to_stack(orig_x, orig_y);
  95.  
  96.   if (punit && unit_flag(punit->type, F_IGTER)) igter++;
  97.   if (punit && punit->type == U_SETTLERS) maxcost >>= 1;
  98.  
  99.   do {
  100.     x = warstack[warnodes].x;
  101.     y = warstack[warnodes].y;
  102.     warnodes++; /* for debug purposes */
  103.     tile0 = map_get_tile(x, y);
  104.     if((xx[2]=x+1)==map.xsize) xx[2]=0;
  105.     if((xx[0]=x-1)==-1) xx[0]=map.xsize-1;
  106.     xx[1] = x;
  107.     if ((yy[0]=y-1)==-1) yy[0] = 0;
  108.     if ((yy[2]=y+1)==map.ysize) yy[2]=y;
  109.     yy[1] = y;
  110.     for (k = 0; k < 8; k++) {
  111.       i = ii[k]; j = jj[k]; /* saves CPU cycles? */
  112.       if (which == LAND_MOVING) {
  113. /*        if (tile0->move_cost[k] == -3 || tile0->move_cost[k] > 16) c = maxcost;*/
  114.         if (map_get_terrain(xx[i], yy[j]) == T_OCEAN) {
  115.           if (punit && is_transporter_with_free_space(pplayer, xx[i], yy[j])) c = 3;
  116.           else c = maxcost;
  117.         } else if (tile0->terrain == T_OCEAN) c = 3;
  118.         else if (igter) c = 3; /* NOT c = 1 */
  119.         else if (punit) c = MIN(tile0->move_cost[k], unit_types[punit->type].move_rate);
  120. /*        else c = tile0->move_cost[k]; 
  121. This led to a bad bug where a unit in a swamp was considered too far away */
  122.         else {
  123.           tm = map_get_tile(xx[i], yy[j])->move_cost[7-k];
  124.           c = (tile0->move_cost[k] + tm + (tile0->move_cost[k] > tm ? 1 : 0))>>1;
  125.         }
  126.         
  127.         tm = warmap.cost[x][y] + c;
  128.         if (warmap.cost[xx[i]][yy[j]] > tm && tm < maxcost) {
  129.           warmap.cost[xx[i]][yy[j]] = tm;
  130.           add_to_stack(xx[i], yy[j]);
  131.         }
  132.       } else {
  133.         c = 3; /* allow for shore bombardment/transport/etc */
  134.         tm = warmap.seacost[x][y] + c;
  135.         if (warmap.seacost[xx[i]][yy[j]] > tm && tm < maxcost) {
  136.           warmap.seacost[xx[i]][yy[j]] = tm;
  137.           if (tile0->move_cost[k] == -3) add_to_stack(xx[i], yy[j]);
  138.         }
  139.       }
  140.     } /* end for */
  141.   } while (warstacksize > warnodes);
  142.   if (warnodes > 15000) printf("Warning: %d nodes in map #%d for (%d, %d)\n",
  143.      warnodes, which, orig_x, orig_y);
  144. /* printf("Generated warmap for (%d,%d) with %d nodes checked.\n", orig_x, orig_y, warnodes); */
  145. /* warnodes is often as much as 2x the size of the continent -- Syela */
  146. }
  147.  
  148. void generate_warmap(struct city *pcity, struct unit *punit)
  149. {
  150. /*printf("Generating warmap, pcity = %s, punit = %s\n", (pcity ?
  151. pcity->name : "NULL"), (punit ? unit_types[punit->type].name : "NULL"));*/
  152.  
  153.   if (punit) {
  154.     if (pcity && pcity == warmap.warcity) return; /* time-saving shortcut */
  155.     if (warmap.warunit == punit && !warmap.cost[punit->x][punit->y]) return;
  156.     pcity = 0;
  157.   }
  158.  
  159.   warmap.warcity = pcity;
  160.   warmap.warunit = punit;
  161.  
  162.   if (punit) {
  163.     if (is_sailing_unit(punit)) {
  164.       init_warmap(punit->x, punit->y, LAND_MOVING);
  165.       really_generate_warmap(pcity, punit, SEA_MOVING);
  166.     } else {
  167.       init_warmap(punit->x, punit->y, SEA_MOVING);
  168.       really_generate_warmap(pcity, punit, LAND_MOVING);
  169.     }
  170.     warmap.orig_x = punit->x;
  171.     warmap.orig_y = punit->y;
  172.   } else {
  173.     really_generate_warmap(pcity, punit, LAND_MOVING);
  174.     really_generate_warmap(pcity, punit, SEA_MOVING);
  175.     warmap.orig_x = pcity->x;
  176.     warmap.orig_y = pcity->y;
  177.   }
  178. }
  179.  
  180. /* ....... end of old advmilitary.c, beginning of old gotohand.c. ..... */
  181.  
  182. int could_unit_move_to_tile(struct unit *punit, int x0, int y0, int x, int y)
  183. { /* this WAS can_unit_move_to_tile with the notifys removed -- Syela */
  184. /* but is now a little more complicated to allow non-adjacent tiles */
  185.   struct tile *ptile,*ptile2;
  186.   struct city *pcity;
  187.  
  188.   if(punit->activity!=ACTIVITY_IDLE && punit->activity!=ACTIVITY_GOTO)
  189.     return 0;
  190.   
  191.   if(x<0 || x>=map.xsize || y<0 || y>=map.ysize)
  192.     return 0;
  193.   
  194.   if(!is_tiles_adjacent(x0, y0, x, y))
  195.     return 0; 
  196.  
  197.   if(is_enemy_unit_tile(x,y,punit->owner))
  198.     return 0;
  199.  
  200.   ptile=map_get_tile(x, y);
  201.   ptile2=map_get_tile(x0, y0);
  202.   if(is_ground_unit(punit)) {
  203.     /* Check condition 4 */
  204.     if(ptile->terrain==T_OCEAN &&
  205.        !is_transporter_with_free_space(&game.players[punit->owner], x, y))
  206.     return 0;
  207.  
  208.     /* Moving from ocean */
  209.     if(ptile2->terrain==T_OCEAN) {
  210.       /* Can't attack a city from ocean unless marines */
  211.       if(!unit_flag(punit->type, F_MARINES) && is_enemy_city_tile(x,y,punit->owner)) {
  212.     return 0;
  213.       }
  214.     }
  215.   } else if(is_sailing_unit(punit)) {
  216.     if(ptile->terrain!=T_OCEAN && ptile->terrain!=T_UNKNOWN)
  217.       if(!is_friendly_city_tile(x,y,punit->owner))
  218.     return 0;
  219.   } 
  220.  
  221.   if((pcity=map_get_city(x, y))) {
  222.     if ((pcity->owner!=punit->owner && (is_air_unit(punit) || 
  223.                                         !is_military_unit(punit)))) {
  224.         return 0;  
  225.     }
  226.   }
  227.  
  228. /*  zoc = zoc_ok_move(punit, x, y);      can't use this, so reproducing ... */
  229.   /* if you have units there, you can move */
  230.   if (is_friendly_unit_tile(x,y,punit->owner))
  231.     return 1;
  232.   if (!is_ground_unit(punit) || unit_flag(punit->type, F_IGZOC))
  233.     return 1;
  234.   if (map_get_city(x,y) || map_get_city(x0, y0))
  235.     return 1;
  236.   return (is_my_zoc(punit, x0, y0) || is_my_zoc(punit, x, y));
  237. }
  238.  
  239. int goto_tile_cost(struct player *pplayer, struct unit *punit, int x0, int y0, int x1, int y1, int m)
  240. {
  241.   if (!pplayer->ai.control && !map_get_known(x1, y1, pplayer)) {
  242. /*    printf("Venturing into the unknown at (%d, %d).\n", x1, y1);*/
  243. /*    return(3);   People seemed not to like this. -- Syela */
  244.     return(15); /* arbitrary deterrent. */
  245.   }
  246.   if (get_defender(pplayer, punit, x1, y1)) {
  247.      if (same_pos(punit->goto_dest_x, punit->goto_dest_y, x1, y1))
  248.        return(MIN(m, unit_types[punit->type].move_rate));
  249.      if (!can_unit_attack_tile(punit, x1, y1)) return(255);
  250.      return(15);
  251. /* arbitrary deterrent; if we wanted to attack, we wouldn't GOTO */
  252.   } else {
  253.     if (!could_unit_move_to_tile(punit, x0, y0, x1, y1) &&
  254.         !same_pos(x1, y1, punit->goto_dest_x, punit->goto_dest_y)) return(255);
  255. /* in order to allow transports to GOTO shore correctly */
  256.   }
  257.   return(MIN(m, unit_types[punit->type].move_rate));
  258. }
  259.  
  260. void init_gotomap(int orig_x, int orig_y)
  261. {
  262.   int x, y;
  263.   for (x = 0; x < map.xsize; x++) {
  264.     for (y = 0; y < map.ysize; y++) {
  265.       warmap.seacost[x][y] = 255;
  266.       warmap.cost[x][y] = 255;
  267.       warmap.vector[x][y] = 0;
  268.     }
  269.   }
  270.   warmap.cost[orig_x][orig_y] = 0;
  271.   warmap.seacost[orig_x][orig_y] = 0;
  272.   return;
  273. } 
  274.  
  275. int dir_ok(int x0, int y0, int x1, int y1, int k)
  276. { /* The idea of this is to check less nodes in the wrong direction.
  277. These if's might cost some CPU but hopefully less overall. -- Syela */
  278.   int n = 0, s = 0, e = 0, w = 0, dx;
  279.   if (y1 > y0) s = y1 - y0;
  280.   else n = y0 - y1;
  281.   dx = x1 - x0;
  282.   if (dx > map.xsize>>1) w = map.xsize - dx;
  283.   else if (dx > 0) e = dx;
  284.   else if (dx + (map.xsize>>1) > 0) w = 0 - dx;
  285.   else e = map.xsize + dx;
  286.   if (e == map.xsize / 2 || w == map.xsize / 2) { /* thanks, Massimo */
  287.     if (k < 3 && s >= MAX(e, w)) return 0;
  288.     if (k > 4 && n >= MAX(e, w)) return 0;
  289.     return 1;
  290.   }
  291.   switch(k) {
  292.     case 0:
  293.       if (e >= n && s >= w) return 0;
  294.       else return 1;
  295.     case 1:
  296.       if (s && s >= e && s >= w) return 0;
  297.       else return 1;
  298.     case 2:
  299.       if (w >= n && s >= e) return 0;
  300.       else return 1;
  301.     case 3:
  302.       if (e && e >= n && e >= s) return 0;
  303.       else return 1;
  304.     case 4:
  305.       if (w && w >= n && w >= s) return 0;
  306.       else return 1;
  307.     case 5:
  308.       if (e >= s && n >= w) return 0;
  309.       else return 1;
  310.     case 6:
  311.       if (n && n >= w && n >= e) return 0;
  312.       else return 1;
  313.     case 7:
  314.       if (w >= s && n >= e) return 0;
  315.       else return 1;
  316.     default:
  317.       printf("Bad dir_ok call: (%d, %d) -> (%d, %d), %d\n", x0, y0, x1, y1, k);
  318.       return 0;
  319.   }
  320. }
  321.  
  322. int dir_ect(int x0, int y0, int x1, int y1, int k)
  323. {
  324.   int ii[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
  325.   int jj[8] = { -1, -1, -1, 0, 0, 1, 1, 1 };
  326.   int x, y;
  327.   x = map_adjust_x(ii[k] + x0);
  328.   y = jj[k] + y0; /* trusted, since I know who's calling us. -- Syela */
  329.   if (same_pos(x, y, x1, y1)) return 1; /* as direct as it gets! */
  330.   return (1 - dir_ok(x, y, x1, y1, 7-k));
  331. }
  332.  
  333. int find_the_shortest_path(struct player *pplayer, struct unit *punit,
  334.                            int dest_x, int dest_y)
  335. {
  336. /*  char *d[] = { "NW", "N", "NE", "W", "E", "SW", "S", "SE" };*/
  337.   int ii[8] = { 0, 1, 2, 0, 2, 0, 1, 2 };
  338.   int jj[8] = { 0, 0, 0, 1, 1, 2, 2, 2 };
  339.   int igter = 0, xx[3], yy[3], x, y, i, j, k, tm, c;
  340.   int orig_x, orig_y;
  341.   struct tile *tile0;
  342.   enum unit_move_type which = unit_types[punit->type].move_type;
  343.   int maxcost = 255;
  344.   unsigned char local_vector[MAP_MAX_WIDTH][MAP_MAX_HEIGHT];
  345.   struct unit *passenger; /* and I ride and I ride */
  346.   
  347. /* Often we'll already have a working warmap, but I don't want to
  348. deal with merging these functions yet.  Once they work correctly
  349. and independently I can worry about optimizing them. -- Syela */
  350.  
  351.   memset(local_vector, 0, sizeof(local_vector));
  352. /* I think I only need to zero (orig_x, orig_y), but ... */
  353.  
  354.   init_gotomap(punit->x, punit->y);
  355.   warstacksize = 0;
  356.   warnodes = 0;
  357.  
  358.   orig_x = punit->x;
  359.   orig_y = punit->y;
  360.  
  361.   add_to_stack(orig_x, orig_y);
  362.  
  363.   if (punit && unit_flag(punit->type, F_IGTER)) igter++;
  364.   if (which == SEA_MOVING) passenger = other_passengers(punit);
  365.   else passenger = 0;
  366.  
  367.   if (passenger)
  368.     if (map_get_terrain(dest_x, dest_y) == T_OCEAN ||
  369.           is_friendly_unit_tile(dest_x, dest_y, passenger->owner) ||
  370.           is_friendly_city_tile(dest_x, dest_y, passenger->owner) ||
  371.           unit_flag(passenger->type, F_MARINES) ||
  372.           is_my_zoc(passenger, dest_x, dest_y)) passenger = 0;
  373.  
  374. /* if passenger is nonzero, the next-to-last tile had better be zoc-ok! */
  375.  
  376.   do {
  377.     x = warstack[warnodes].x;
  378.     y = warstack[warnodes].y;
  379.     warnodes++; /* for debug purposes */
  380.     tile0 = map_get_tile(x, y);
  381.     if((xx[2]=x+1)==map.xsize) xx[2]=0;
  382.     if((xx[0]=x-1)==-1) xx[0]=map.xsize-1;
  383.     xx[1] = x;
  384.     if ((yy[0]=y-1)==-1) yy[0] = 0;
  385.     if ((yy[2]=y+1)==map.ysize) yy[2]=y;
  386.     yy[1] = y;
  387.     
  388.     for (k = 0; k < 8; k++) {
  389.       i = ii[k]; j = jj[k]; /* saves CPU cycles? */
  390.       if (which != SEA_MOVING) {
  391.         if (which != LAND_MOVING) c = 3;
  392.         else if (tile0->move_cost[k] == -3 || tile0->move_cost[k] > 16) c = maxcost; 
  393.         else if (igter) c = (tile0->move_cost[k] ? 3 : 0); /* Reinier's fix -- Syela */
  394.         else c = tile0->move_cost[k];
  395.         c = goto_tile_cost(pplayer, punit, x, y, xx[i], yy[j], c);
  396.         if (!dir_ok(x, y, dest_x, dest_y, k)) c += c;
  397.         if (!c && !dir_ect(x, y, dest_x, dest_y, k)) c = 1;
  398.         tm = warmap.cost[x][y] + c;
  399. #ifdef ACTUALLYTESTED
  400.         if (warmap.cost[x][y] < punit->moves_left && tm < maxcost &&
  401.             tm >= punit->moves_left - MIN(3, c) && enemies_at(punit, xx[i], yy[j])) {
  402.           tm += unit_types[punit->type].move_rate;
  403. /*printf("%s#%d@(%d,%d) dissuaded from (%d,%d) -> (%d,%d)\n",
  404. unit_types[punit->type].name, punit->id, punit->x, punit->y, xx[i], yy[j],
  405. punit->goto_dest_x, punit->goto_dest_y);*/
  406.         }
  407. #endif
  408.         if (tm < maxcost) {
  409.           if (warmap.cost[xx[i]][yy[j]] > tm) {
  410.             warmap.cost[xx[i]][yy[j]] = tm;
  411.             add_to_stack(xx[i], yy[j]);
  412.             local_vector[xx[i]][yy[j]] = 128>>k;
  413. /*printf("Candidate: %s from (%d, %d) to (%d, %d) +%d to %d\n", d[k], x, y, xx[i], yy[j], c, tm);*/
  414.           } else if (warmap.cost[xx[i]][yy[j]] == tm) {
  415.             local_vector[xx[i]][yy[j]] |= 128>>k;
  416. /*printf("Co-Candidate: %s from (%d, %d) to (%d, %d) +%d to %d\n", d[k], x, y, xx[i], yy[j], c, tm);*/
  417.           }
  418.         }
  419.       } else {
  420.         if (tile0->move_cost[k] != -3) c = maxcost;
  421.         else if (punit->type == U_TRIREME && !is_coastline(xx[i], yy[j])) c = 7;
  422.         else c = 3;
  423. /* I want to disable these totally but for some reason it bugs. -- Syela */
  424.         c = goto_tile_cost(pplayer, punit, x, y, xx[i], yy[j], c);
  425.         if (xx[i] == dest_x && yy[j] == dest_y && passenger && c < 60 &&
  426.             !is_my_zoc(passenger, x, y)) c = 60; /* passenger cannot disembark */
  427.         if (!dir_ok(x, y, dest_x, dest_y, k)) c += c;
  428.         tm = warmap.seacost[x][y] + c;
  429.         if (warmap.seacost[x][y] < punit->moves_left && tm < maxcost &&
  430.             tm >= punit->moves_left - 3 && enemies_at(punit, xx[i], yy[j])) {
  431.           tm += unit_types[punit->type].move_rate;
  432. /*printf("%s#%d@(%d,%d) dissuaded from (%d,%d) -> (%d,%d)\n",
  433. unit_types[punit->type].name, punit->id, punit->x, punit->y, xx[i], yy[j],
  434. punit->goto_dest_x, punit->goto_dest_y);*/
  435.         }
  436.         if (tm < maxcost) {
  437.           if (warmap.seacost[xx[i]][yy[j]] > tm) {
  438.             warmap.seacost[xx[i]][yy[j]] = tm;
  439.             add_to_stack(xx[i], yy[j]);
  440.             local_vector[xx[i]][yy[j]] = 128>>k;
  441.           } else if (warmap.seacost[xx[i]][yy[j]] == tm) {
  442.             local_vector[xx[i]][yy[j]] |= 128>>k;
  443.           }
  444.         }
  445.       }
  446.       if (xx[i] == dest_x && yy[j] == dest_y && maxcost > tm) {
  447. /*printf("Found path, cost = %d\n", tm);*/
  448.         maxcost = tm + 1; /* NOT = tm.  Duh! -- Syela */
  449.       }
  450.     } /* end for */
  451.   } while (warstacksize > warnodes);
  452. /*printf("GOTO: (%d, %d) -> (%d, %d), %d nodes, cost = %d\n", 
  453. orig_x, orig_y, dest_x, dest_y, warnodes, maxcost - 1);*/
  454.   if (maxcost == 255) return(0);
  455. /* succeeded.  the vector at the destination indicates which way we get there */
  456. /* backtracing */
  457.   warnodes = 0;
  458.   warstacksize = 0;
  459.   add_to_stack(dest_x, dest_y);
  460.  
  461.   do {
  462.     x = warstack[warnodes].x;
  463.     y = warstack[warnodes].y;
  464.     warnodes++; /* for debug purposes */
  465.     tile0 = map_get_tile(x, y);
  466.     if((xx[2]=x+1)==map.xsize) xx[2]=0;
  467.     if((xx[0]=x-1)==-1) xx[0]=map.xsize-1;
  468.     xx[1] = x;
  469.     if ((yy[0]=y-1)==-1) yy[0] = 0;
  470.     if ((yy[2]=y+1)==map.ysize) yy[2]=y;
  471.     yy[1] = y;
  472.  
  473.     for (k = 0; k < 8; k++) {
  474.       i = ii[k]; j = jj[k]; /* saves CPU cycles? */
  475.       if (local_vector[x][y] & (1<<k)) {
  476. /* && (local_vector[xx[i]][yy[j]] || !warmap.vector[xx[i]][yy[j]])) {
  477. is not adequate to prevent RR loops.  Bummer. -- Syela */
  478.         add_to_stack(xx[i], yy[j]);
  479.         warmap.vector[xx[i]][yy[j]] |= 128>>k;
  480.         local_vector[x][y] -= 1<<k; /* avoid repetition */
  481. /*printf("PATH-SEGMENT: %s from (%d, %d) to (%d, %d)\n", d[7-k], xx[i], yy[j], x, y);*/
  482.       }
  483.     }
  484.   } while (warstacksize > warnodes);
  485. /*printf("BACKTRACE: %d nodes\n", warnodes);*/
  486.   return(1);
  487. /* DONE! */
  488. }
  489.  
  490. int find_a_direction(struct unit *punit)
  491. {
  492.   int k, d[8], x, y, n, a, best = 0, d0, d1, h0, h1, u, c;
  493.   int ii[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
  494.   int jj[8] = { -1, -1, -1, 0, 0, 1, 1, 1 };
  495.   struct tile *ptile, *adjtile;
  496.   int nearland;
  497.   struct city *pcity;
  498.   struct unit *passenger;
  499.  
  500.   if (map_get_terrain(punit->x, punit->y) == T_OCEAN)
  501.     passenger = other_passengers(punit);
  502.   else passenger = 0;
  503.  
  504.   for (k = 0; k < 8; k++) {
  505.     if (!(warmap.vector[punit->x][punit->y]&(1<<k))) d[k] = 0;
  506.     else {
  507.       if (is_ground_unit(punit))
  508.         c = map_get_tile(punit->x, punit->y)->move_cost[k];
  509.       else c = 3;
  510.       if (unit_flag(punit->type, F_IGTER) && c) c = 1;
  511.       x = map_adjust_x(punit->x + ii[k]); y = map_adjust_y(punit->y + jj[k]);
  512. /*if (passenger) printf("%d@(%d,%d) evaluating (%d,%d)[%d/%d]\n",
  513. punit->id, punit->x, punit->y, x, y, c, punit->moves_left);*/
  514.       ptile = map_get_tile(x, y);
  515.       d0 = get_virtual_defense_power(U_HOWITZER, punit->type, x, y);
  516.       pcity = map_get_city(x, y);
  517.       n = 2;
  518.       if (pcity) { /* this code block inspired by David Pfitzner -- Syela */
  519.         if (city_got_citywalls(pcity)) n += 2;
  520.         if (city_got_building(pcity, B_SDI)) n++;
  521.         if (city_got_building(pcity, B_SAM)) n++;
  522.         if (city_got_building(pcity, B_COASTAL)) n++;
  523.       }
  524.       d0 = (d0 * n) / 2;
  525.       h0 = punit->hp; h1 = 0; d1 = 0; u = 1;
  526.       unit_list_iterate(ptile->units, aunit)
  527.         if (aunit->owner != punit->owner) d1 = -1; /* MINIMUM priority */
  528.         else {
  529.           u++;
  530.           a = get_virtual_defense_power(U_HOWITZER, aunit->type, x, y) * n / 2;
  531.           if (a * aunit->hp > d1 * h1) { d1 = a; h1 = aunit->hp; }
  532.         }
  533.       unit_list_iterate_end;
  534.       if (u == 1) d[k] = d0 * h0;
  535.       else if (pcity || ptile->special&S_FORTRESS)
  536.         d[k] = MAX(d0 * h0, d1 * h1);
  537.       else if ((d0 * h0) <= (d1 * h1)) d[k] = (d1 * h1) * (u - 1) / u;
  538.       else d[k] = MIN(d0 * h0 * u, d0 * h0 * d0 * h0 * (u - 1) / MAX(u, (d1 * h1 * u)));
  539.       if (d0 > d1) d1 = d0;
  540.  
  541.       if (ptile->special&S_ROAD) d[k] += 10; /* in case we change directions */
  542.       if (ptile->special&S_RAILROAD) d[k] += 10; /* next turn, roads are nice */
  543.  
  544.       nearland = 0;
  545.       for (n = 0; n < 8; n++) {
  546.         adjtile = map_get_tile(x + ii[n], y + jj[n]);
  547.         if (adjtile->terrain != T_OCEAN) nearland++;
  548.         if (!((adjtile->known)&(1u<<punit->owner))) {
  549.           if (punit->moves_left <= c) d[k] -= (d[k]>>4); /* Avoid the unknown */
  550.           else d[k]++; /* nice but not important */
  551.         } else { /* NOTE: Not being omniscient here!! -- Syela */
  552.           unit_list_iterate(adjtile->units, aunit) /* lookin for trouble */
  553.             if (aunit->owner != punit->owner && (a = get_attack_power(aunit))) {
  554.               if (punit->moves_left < c + 3) { /* can't fight */
  555.                 if (passenger && !is_ground_unit(aunit)) d[k] = -99;
  556.                 else d[k] -= d1 * (aunit->hp * a * a / (a * a + d1 * d1));
  557.               }
  558.             }
  559.           unit_list_iterate_end;
  560.         } /* end this-tile-is-seen else */
  561.       } /* end tiles-adjacent-to-dest for */
  562.  
  563.       if (punit->type == U_TRIREME && !nearland) {
  564.         if (punit->moves_left < 6) d[k] = 1;
  565.         else if (punit->moves_left == 6) {
  566.           for (n = 0; n < 8; n++) {
  567.             if ((warmap.vector[x][y]&(1<<n))) {
  568.               if (is_coastline(x + ii[n], y + jj[n])) nearland++;
  569.             }
  570.           }
  571.           if (!nearland) d[k] = 1;
  572.         }
  573.       }
  574.  
  575.       if (d[k] < 1 && (!game.players[punit->owner].ai.control ||
  576.          !punit->ai.passenger || punit->moves_left >= 6)) d[k] = 1;
  577.       if (d[k] > best) { 
  578.         best = d[k];
  579. /*printf("New best = %d: (%d, %d) -> (%d, %d)\n", best, punit->x, punit->y, x, y);*/
  580.       }
  581.     } /* end is-a-valid-vector */
  582.   } /* end for */
  583.  
  584.   if (!best) {
  585.     return(-1);
  586.   }
  587.  
  588.   do {
  589.     k = myrand(8);
  590.   } while (d[k] < best);
  591.   return(k);
  592. }
  593.  
  594. int goto_is_sane(struct player *pplayer, struct unit *punit, int x, int y, int omni)
  595. {  
  596.   int ii[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
  597.   int jj[8] = { -1, -1, -1, 0, 0, 1, 1, 1 };
  598.   int k, possible = 0;
  599.   if (same_pos(punit->x, punit->y, x, y)) return 1;
  600.   if (is_ground_unit(punit) && 
  601.           (omni || map_get_known(x, y, pplayer))) {
  602.     if (map_get_terrain(x, y) == T_OCEAN) {
  603.       if (is_transporter_with_free_space(pplayer, x, y)) {
  604.         for (k = 0; k < 8; k++) {
  605.           if (map_get_continent(punit->x, punit->y) ==
  606.               map_get_continent(x + ii[k], y + jj[k]))
  607.             possible++;
  608.         }
  609.       }
  610.     } else { /* going to a land tile */
  611.       if (map_get_continent(punit->x, punit->y) ==
  612.             map_get_continent(x, y))
  613.          possible++;
  614.       else {
  615.         for (k = 0; k < 8; k++) {
  616.           if (map_get_continent(punit->x + ii[k], punit->y + jj[k]) ==
  617.               map_get_continent(x, y))
  618.             possible++;
  619.         }
  620.       }
  621.     }
  622.     return(possible);
  623.   } else if (is_sailing_unit(punit) && (omni || map_get_known(x, y, pplayer)) &&
  624.        map_get_terrain(x, y) != T_OCEAN && !map_get_tile(x, y)->city_id &&
  625.        !is_terrain_near_tile(x, y, T_OCEAN)) {
  626.     return(0);
  627.   } /* end pre-emption subroutine. */
  628.   return(1);
  629. }
  630.  
  631.  
  632. /**************************************************************************
  633. ...
  634. **************************************************************************/
  635. void do_unit_goto(struct player *pplayer, struct unit *punit)
  636. {
  637.   int x, y, k;
  638.   int ii[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
  639.   int jj[8] = { -1, -1, -1, 0, 0, 1, 1, 1 };
  640. /*  char *d[] = { "NW", "N", "NE", "W", "E", "SW", "S", "SE" };*/
  641.  
  642.   int id=punit->id;
  643.  
  644. /* there was a really oogy if here.  Mighty Mouse told me not to axe it
  645. because it would cost oodles of CPU time.  He's right for the most part
  646. but Peter and others have recommended more flexibility, so this is a little
  647. different but should still pre-empt calculation of impossible GOTO's. -- Syela */
  648.  
  649.   if (same_pos(punit->x, punit->y, punit->goto_dest_x, punit->goto_dest_y) ||
  650.       !goto_is_sane(pplayer, punit, punit->goto_dest_x, punit->goto_dest_y, 0)) {
  651.     punit->activity=ACTIVITY_IDLE;
  652.     send_unit_info(0, punit, 0);
  653.     return;
  654.   }
  655.  
  656.   punit->activity = ACTIVITY_GOTO; /* adding this as a failsafe -- Syela */
  657.  
  658.   if(!punit->moves_left) {
  659.     send_unit_info(0, punit, 0);
  660.     return;
  661.   }
  662.  
  663.   if(find_the_shortest_path(pplayer, punit, 
  664.                 punit->goto_dest_x, punit->goto_dest_y)) {
  665.  
  666.     do {
  667.       if(!punit->moves_left) return;
  668.       k = find_a_direction(punit);
  669.       if (k < 0) {
  670. printf("%s#%d@(%d,%d) stalling so it won't be killed.\n",
  671. unit_types[punit->type].name, punit->id, punit->x, punit->y);
  672. /*        punit->activity=ACTIVITY_IDLE;*/
  673.     send_unit_info(0, punit, 0);
  674.     return;
  675.       }
  676. /*printf("Going %s\n", d[k]);*/
  677.       x = map_adjust_x(punit->x + ii[k]);
  678.       y = punit->y + jj[k]; /* no need to adjust this */
  679.  
  680.       if(!punit->moves_left) return;
  681.       if(!handle_unit_move_request(pplayer, punit, x, y)) {
  682. /*printf("Couldn't handle it.\n");*/
  683.     if(punit->moves_left) {
  684.       punit->activity=ACTIVITY_IDLE;
  685.       send_unit_info(0, punit, 0);
  686.       return;
  687.     };
  688.       } /*else printf("Handled.\n");*/
  689.       if(!unit_list_find(&pplayer->units, id))
  690.     return; /* unit died during goto! */
  691.  
  692.       if(punit->x!=x || punit->y!=y) {
  693. /*printf("Aborting, out of movepoints.\n");*/
  694.     send_unit_info(0, punit, 0);
  695.     return; /* out of movepoints */
  696.       }
  697. /*printf("Moving on.\n");*/
  698.     } while(!(x==punit->goto_dest_x && y==punit->goto_dest_y));
  699.   }
  700. else printf("Did not find the shortest path for %s's %s at (%d, %d) -> (%d, %d)\n",
  701. pplayer->name, unit_types[punit->type].name, punit->x, punit->y, 
  702. punit->goto_dest_x, punit->goto_dest_y);
  703.  
  704.   punit->activity=ACTIVITY_IDLE;
  705.   send_unit_info(0, punit, 0);
  706. }
  707.