git.pond.sub.org Git - empserver/blob - src/lib/common/bestpath.c

   1 /*
   2  *  Empire - A multi-player, client/server Internet based war game.
   3  *  Copyright (C) 1986-2000, Dave Pare, Jeff Bailey, Thomas Ruschak,
   4  *                           Ken Stevens, Steve McClure
   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, write to the Free Software
  18  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19  *
  20  *  ---
  21  *
  22  *  See the "LEGAL", "LICENSE", "CREDITS" and "README" files for all the
  23  *  related information and legal notices. It is expected that any future
  24  *  projects/authors will amend these files as needed.
  25  *
  26  *  ---
  27  *
  28  *  bestpath.c: Find the best path between sectors
  29  *
  30  *  Known contributors to this file:
  31  *     Steve McClure, 1998-2000
  32  */
  33
  34 /*
  35  * IMPORTANT: These routines are very selectively used in the server.
  36  *
  37  * "bestpath" is now obsolete (and removed)
  38  * "bestownedpath" is only used to determine paths for ships and planes.
  39  *
  40  * Callers should not be calling these directly anymore. They should use
  41  * the "BestShipPath", "BestAirPath", "BestLandPath" and "BestDistPath"
  42  * functions.  Note that those last two use the A* algorithms to find
  43  * information.
  44  */
  45
  46 #include "gamesdef.h"
  47 #include "misc.h"
  48 #include "xy.h"
  49 #include "var.h"
  50 #include "sect.h"
  51 #include "file.h"
  52 #include "nat.h"
  53 #include "common.h"
  54 #include "optlist.h"
  55
  56 static int owned_and_navigable(s_char *  , int  , int  , s_char *  , int );
  57
  58 #define MAXROUTE        100        /* return '?' if path longer than this */
  59 #define valid(x,y)      (((x^y)&1)==0)
  60
  61 /* ________________________________________________________________
  62 **
  63 **  bestpath(x1,y1,x2,y2,(s_char *)terrain);
  64 **
  65 **  Calculate routing string to get from sector [x1,y1] to sector [x2,y2]
  66 **  via a specified type of terrain.
  67 **
  68 **  Specify:
  69 **
  70 **      x1,y1        starting coordinates
  71 **
  72 **      x2,y2        destination coordinates
  73 **
  74 **      terrain      ptr to string showing the types of sectors that
  75 **                   we're allowed to pass through:
  76 **
  77 **                   A null string enables routing through any kind of
  78 **                   sector (useful for airplanes).
  79 **
  80 **                   A string that begins with an 'R' ensures that
  81 **                   the source and destination sectors also match
  82 **                   the specified type of terrain.
  83 **
  84 **                   A string that begins with a '~' (after the 'R',
  85 **                   if necessary) specifies that we can pass through
  86 **                   any kind of sector EXCEPT those in the remainder
  87 **                   of the string.
  88 **
  89 **                   Examples:
  90 **
  91 **                      "R~.^"  all sectors along route must be
  92 **                              non-ocean, non-mountain
  93 **
  94 **                      "+"     all sectors between start and end
  95 **                              must be highway
  96 **
  97 **                      "h. "   all sectors along route must be
  98 **                              harbor, water, or unmapped
  99 **
 100 **  'bestpath' returns a pointer to a route string containing either:
 101 **
 102 **     yugjbn - string of normal routing characters if route possible
 103 **     ?      - if route is longer than MAXROUTE characters
 104 **     \0     - (null string) if no route possible
 105 **     h      - if start and end points are the same sector
 106 ** ________________________________________________________________
 107 */
 108
 109 s_char *dirchar = "juygbn";
 110 int dx[6]       = { 2, 1,-1,-2,-1, 1 };
 111 int dy[6]       = { 0,-1,-1, 0, 1, 1 };
 112 int tmp;
 113
 114 /*
 115  * Ok, note that here we malloc some buffers.  BUT, we never
 116  * free them.  Why, you may ask?  Because we want to allocate
 117  * them based on world size which is now (or soon to be) dynamic,
 118  * but we don't want to allocate each and every time, since that
 119  * would be slow.  And, since world size only changes at init
 120  * time, we can do this safely.
 121  * We also share these buffers between "bestpath" and "bestownedpath"
 122  * since you can never be in both functions at the same time.  If that
 123  * did happen, we'd already be so broken that it won't matter.
 124  */
 125 static unsigned int *mapbuf = (unsigned int *)0;
 126 static unsigned int **mapindex = (unsigned int **)0;
 127
 128 s_char *bestownedpath(s_char *bpath,
 129                       s_char *bigmap,
 130                       int x,
 131                       int y,
 132                       int ex,
 133                       int ey,
 134                       s_char *terrain,
 135                       int own)
 136 {
 137   int i, j, tx, ty, markedsectors, restr2;
 138   int minx, maxx, miny, maxy, scanx, scany;
 139   unsigned int routelen;
 140
 141   if (!mapbuf)
 142       mapbuf = (unsigned int *)malloc((WORLD_X * WORLD_Y) *
 143                                       sizeof(unsigned int));
 144   if (!mapbuf)
 145       return ((s_char *)0);
 146   if (!mapindex) {
 147       mapindex = (unsigned int **)malloc(WORLD_X * sizeof(unsigned int *));
 148       if (mapindex) {
 149           /* Setup the map pointers */
 150           for (i = 0; i < WORLD_X; i++)
 151               mapindex[i] = &mapbuf[WORLD_Y * i];
 152       }
 153   }
 154   if (!mapindex)
 155       return ((s_char *)0);
 156
 157   bpath[0] = 0;
 158   if (0 != (restr2 = (*terrain == 'R')))
 159     terrain++;
 160
 161   x  = XNORM(x);
 162   y  = YNORM(y);
 163   ex = XNORM(ex);
 164   ey = YNORM(ey);
 165
 166   if (x == ex && y == ey) {
 167     bpath[0] = 'h';
 168     bpath[1] = 0;
 169     return ((s_char *)bpath);
 170   }
 171
 172   if (!valid(x,y) || !valid(ex,ey))
 173     return((s_char *)0);
 174
 175   if (restr2 && (!owned_and_navigable(bigmap, x, y, terrain, own) ||
 176                  !owned_and_navigable(bigmap, x, y, terrain, own)))
 177     return ((s_char *)0);
 178
 179   for (i = 0; i < WORLD_X; i++)
 180     for (j = 0; j < WORLD_Y; j++)
 181       mapindex[i][j] = 0xFFFF;  /* clear the workspace  */
 182
 183   routelen = 0;                 /* path length is now 0 */
 184   mapindex[x][y] = 0;           /* mark starting spot   */
 185   markedsectors = 1;            /* source sector marked */
 186   minx = x - 2;                 /* set X scan bounds    */
 187   maxx = x + 2;
 188   miny = y - 1;                 /* set Y scan bounds    */
 189   maxy = y + 1;
 190
 191   do {
 192     if (++routelen == MAXROUTE) {
 193       bpath[0] = '?';
 194       bpath[1] = 0;
 195       return ((s_char *)bpath);
 196     }
 197     markedsectors = 0;
 198     for (scanx = minx; scanx <= maxx; scanx++) {
 199       x = XNORM(scanx);
 200       for (scany = miny; scany <= maxy; scany++) {
 201         y = YNORM(scany);
 202         if (valid(x,y)) {
 203           if ((((mapindex[x][y]) & 0x1FFF) == (routelen - 1))) {
 204             for (i = 0; i < 6; i++) {
 205               tx = x + dx[i];
 206               ty = y + dy[i];
 207               tx = XNORM(tx);
 208               ty = YNORM(ty);
 209               if (mapindex[tx][ty] == 0xFFFF) {
 210                 if (owned_and_navigable(bigmap, tx, ty, terrain, own) ||
 211                     (tx == ex && ty == ey && !restr2) ) {
 212                   mapindex[tx][ty] = ((i + 1) << 13) + routelen;
 213                   markedsectors++;
 214                 }
 215               }
 216               if (tx == ex && ty == ey) {
 217                 bpath[routelen] = 0;
 218                 while (routelen--) {
 219                   i = ((mapindex[tx][ty]) >> 13) - 1;
 220                   bpath[routelen] = dirchar[i];
 221                   tx = tx - dx[i];
 222                   ty = ty - dy[i];
 223                   tx = XNORM(tx);
 224                   ty = YNORM(ty);
 225                 }
 226                 return((s_char *)bpath);
 227               }
 228             }
 229           }
 230         }
 231       }
 232     }
 233     miny--;
 234     maxy++;
 235     minx -= 2;
 236     maxx += 2;
 237   } while (markedsectors);
 238
 239   bpath[0] = 0;
 240   return((s_char *)0);          /* no route possible    */
 241 }
 242
 243 /* return TRUE if sector is passable */
 244 static int
 245 owned_and_navigable(s_char *map, int x, int y, s_char *terrain, int own)
 246 {
 247         s_char c;
 248         s_char *t;
 249         s_char mapspot; /* What this spot on the bmap is */
 250         int negate;
 251         struct sctstr *sect;
 252         int rel;
 253
 254         /* No terrain to check?  Everything is navigable! (this
 255            probably means we are flying) */
 256         if (!(*terrain))
 257           return (1);
 258
 259         /* Are we checking this map? */
 260         if (map) {
 261           /* Do we know what this sector is?  If not, we assume it's ok,
 262              since otherwise we'll never venture anywhere */
 263           mapspot = map[sctoff(x, y)];
 264           if (mapspot == ' ' || mapspot == 0)
 265             return (1);
 266
 267           /* Now, is it marked with a 'x' or 'X'? If so, avoid it! */
 268           if (mapspot == 'x' || mapspot == 'X')
 269             return (0);
 270         } else {
 271           /* We don't know what it is since we have no map, so return ok! */
 272           return (1);
 273         }
 274
 275         /* Now, check this bmap entry to see if it is one of the
 276            terrain types. */
 277         t = terrain;
 278         if (*t == '~') {
 279           negate = 1;
 280           t++;
 281         } else
 282           negate = 0;
 283
 284         while (*t) {
 285           if (*t == mapspot)
 286             break;
 287           t++;
 288         }
 289         if (negate && *t) {
 290           /* We found it, so we say it's bad since we are negating */
 291           return (0);
 292         } else if (!negate && !*t) {
 293           /* We didn't find it, so we say it's bad since we aren't negating */
 294           return (0);
 295         }
 296
 297         /* According to our bmap, this sector is ok so far. */
 298
 299         /* Ok, we made it this far.  Now get the sector */
 300         sect = getsectp(x, y);
 301         c = dchr[sect->sct_type].d_mnem;
 302         /* Ok, now, check the owner if needed */
 303         if (own >= 0) {
 304           if (sect->sct_own != own) {
 305             rel = getrel(getnatp(sect->sct_own), own);
 306             /* We can't sail through deity sectors, but we can sail
 307                through any ocean */
 308             if (rel < FRIENDLY && sect->sct_type != SCT_WATER)
 309               return (0);
 310           }
 311         }
 312         /* Ok, now, check these two sector types */
 313         /* check for bad harbors. */
 314         if (c == 'h' && sect->sct_effic < 2)
 315           return (0);
 316         /* check for bad bridges  */
 317         if (c == '=' && sect->sct_effic < 60)
 318           return (0);
 319         /* Woo-hoo, it's ok! */
 320         return (1);
 321 }
 322