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-2006, 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 files README, COPYING and CREDITS in the root of the source
  23  *  tree for related information and legal notices.  It is expected
  24  *  that future 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  * "bestownedpath" is only used to determine paths for ships and planes.
  38  *
  39  * Callers should not be calling these directly anymore. They should use
  40  * the "BestShipPath", "BestAirPath", "BestLandPath" and "BestDistPath"
  41  * functions.  Note that those last two use the A* algorithms to find
  42  * information.
  43  */
  44
  45 #include <config.h>
  46
  47 #include "misc.h"
  48 #include "xy.h"
  49 #include "sect.h"
  50 #include "file.h"
  51 #include "nat.h"
  52 #include "common.h"
  53 #include "optlist.h"
  54
  55 static int owned_and_navigable(char *, int, int, char *, int);
  56
  57 #define MAXROUTE        100     /* return '?' if path longer than this */
  58 #define valid(x,y)      (((x^y)&1)==0)
  59
  60 /* ________________________________________________________________
  61 **
  62 **  bestpath(x1,y1,x2,y2,(s_char *)terrain);
  63 **
  64 **  Calculate routing string to get from sector [x1,y1] to sector [x2,y2]
  65 **  via a specified type of terrain.
  66 **
  67 **  Specify:
  68 **
  69 **      x1,y1        starting coordinates
  70 **
  71 **      x2,y2        destination coordinates
  72 **
  73 **      terrain      ptr to string showing the types of sectors that
  74 **                   we're allowed to pass through:
  75 **
  76 **                   A null string enables routing through any kind of
  77 **                   sector (useful for airplanes).
  78 **
  79 **                   A string that begins with an 'R' ensures that
  80 **                   the source and destination sectors also match
  81 **                   the specified type of terrain.
  82 **
  83 **                   A string that begins with a '~' (after the 'R',
  84 **                   if necessary) specifies that we can pass through
  85 **                   any kind of sector EXCEPT those in the remainder
  86 **                   of the string.
  87 **
  88 **                   Examples:
  89 **
  90 **                      "R~.^"  all sectors along route must be
  91 **                              non-ocean, non-mountain
  92 **
  93 **                      "+"     all sectors between start and end
  94 **                              must be highway
  95 **
  96 **                      "h. "   all sectors along route must be
  97 **                              harbor, water, or unmapped
  98 **
  99 **  'bestpath' returns a pointer to a route string containing either:
 100 **
 101 **     yugjbn - string of normal routing characters if route possible
 102 **     ?      - if route is longer than MAXROUTE characters
 103 **     \0     - (null string) if no route possible
 104 **     h      - if start and end points are the same sector
 105 ** ________________________________________________________________
 106 */
 107
 108 static char *dirchar = "juygbn";
 109 int dx[6] = { 2, 1, -1, -2, -1, 1 };
 110 int dy[6] = { 0, -1, -1, 0, 1, 1 };
 111
 112 /*
 113  * Ok, note that here we malloc some buffers.  BUT, we never
 114  * free them.  Why, you may ask?  Because we want to allocate
 115  * them based on world size which is now (or soon to be) dynamic,
 116  * but we don't want to allocate each and every time, since that
 117  * would be slow.  And, since world size only changes at init
 118  * time, we can do this safely.
 119  */
 120 static unsigned int *mapbuf;
 121 static unsigned int **mapindex;
 122
 123 s_char *
 124 bestownedpath(s_char *bpath,
 125               s_char *bigmap,
 126               int x, int y, int ex, int ey, s_char *terrain, int own)
 127 {
 128     int i, j, tx, ty, markedsectors, restr2;
 129     int minx, maxx, miny, maxy, scanx, scany;
 130     unsigned int routelen;
 131
 132     if (!mapbuf)
 133         mapbuf = malloc((WORLD_X * WORLD_Y) *
 134                                         sizeof(unsigned int));
 135     if (!mapbuf)
 136         return NULL;
 137     if (!mapindex) {
 138         mapindex = malloc(WORLD_X * sizeof(unsigned int *));
 139         if (mapindex) {
 140             /* Setup the map pointers */
 141             for (i = 0; i < WORLD_X; i++)
 142                 mapindex[i] = &mapbuf[WORLD_Y * i];
 143         }
 144     }
 145     if (!mapindex)
 146         return NULL;
 147
 148     if (0 != (restr2 = (*terrain == 'R')))
 149         terrain++;
 150
 151     x = XNORM(x);
 152     y = YNORM(y);
 153     ex = XNORM(ex);
 154     ey = YNORM(ey);
 155
 156     if (x == ex && y == ey)
 157         return "h";
 158
 159     if (!valid(x, y) || !valid(ex, ey))
 160         return NULL;
 161
 162     if (restr2 && (!owned_and_navigable(bigmap, x, y, terrain, own) ||
 163                    !owned_and_navigable(bigmap, ex, ey, terrain, own)))
 164         return NULL;
 165
 166     for (i = 0; i < WORLD_X; i++)
 167         for (j = 0; j < WORLD_Y; j++)
 168             mapindex[i][j] = 0xFFFF;    /* clear the workspace  */
 169
 170     routelen = 0;               /* path length is now 0 */
 171     mapindex[x][y] = 0;         /* mark starting spot   */
 172     markedsectors = 1;          /* source sector marked */
 173     minx = x - 2;               /* set X scan bounds    */
 174     maxx = x + 2;
 175     miny = y - 1;               /* set Y scan bounds    */
 176     maxy = y + 1;
 177
 178     do {
 179         if (++routelen == MAXROUTE - 1)
 180             return NULL;
 181         markedsectors = 0;
 182         for (scanx = minx; scanx <= maxx; scanx++) {
 183             x = XNORM(scanx);
 184             for (scany = miny; scany <= maxy; scany++) {
 185                 y = YNORM(scany);
 186                 if (valid(x, y)) {
 187                     if ((((mapindex[x][y]) & 0x1FFF) == (routelen - 1))) {
 188                         for (i = 0; i < 6; i++) {
 189                             tx = x + dx[i];
 190                             ty = y + dy[i];
 191                             tx = XNORM(tx);
 192                             ty = YNORM(ty);
 193                             if (mapindex[tx][ty] == 0xFFFF) {
 194                                 if (owned_and_navigable(bigmap, tx, ty,
 195                                                         terrain, own)
 196                                     || (tx == ex && ty == ey && !restr2)) {
 197                                     mapindex[tx][ty] =
 198                                         ((i + 1) << 13) + routelen;
 199                                     markedsectors++;
 200                                 }
 201                             }
 202                             if (tx == ex && ty == ey) {
 203                                 bpath[routelen] = 'h';
 204                                 bpath[routelen + 1] = 0;
 205                                 while (routelen--) {
 206                                     i = ((mapindex[tx][ty]) >> 13) - 1;
 207                                     bpath[routelen] = dirchar[i];
 208                                     tx = tx - dx[i];
 209                                     ty = ty - dy[i];
 210                                     tx = XNORM(tx);
 211                                     ty = YNORM(ty);
 212                                 }
 213                                 return bpath;
 214                             }
 215                         }
 216                     }
 217                 }
 218             }
 219         }
 220         miny--;
 221         maxy++;
 222         minx -= 2;
 223         maxx += 2;
 224     } while (markedsectors);
 225
 226     return NULL;                /* no route possible    */
 227 }
 228
 229 /* return TRUE if sector is passable */
 230 static int
 231 owned_and_navigable(char *bigmap, int x, int y, char *terrain, int own)
 232 {
 233     char *t;
 234     char mapspot;               /* What this spot on the bmap is */
 235     struct sctstr sect;
 236     int negate;
 237
 238     /* No terrain to check?  Everything is navigable! (this
 239        probably means we are flying) */
 240     if (!*terrain)
 241         return 1;
 242
 243     /* Owned or allied sector?  Check the real sector.  */
 244     getsect(x, y, &sect);
 245     if (sect.sct_own == own
 246         || (sect.sct_own && getrel(getnatp(sect.sct_own), own) == ALLIED)) {
 247         /* FIXME duplicates shp_check_nav() logic */
 248         switch (dchr[sect.sct_type].d_nav) {
 249         case NAVOK:
 250             return 1;
 251         case NAV_CANAL:
 252             /* FIXME return 1 when all ships have M_CANAL */
 253             return 0;
 254         case NAV_02:
 255             return sect.sct_effic >= 2;
 256         case NAV_60:
 257             return sect.sct_effic >= 60;
 258         default:
 259             return 0;
 260         }
 261     }
 262
 263     /* Can only check bigmap */
 264     if (bigmap) {
 265         /* Do we know what this sector is?  If not, we assume it's ok,
 266            since otherwise we'll never venture anywhere */
 267         mapspot = bigmap[sctoff(x, y)];
 268         if (mapspot == ' ' || mapspot == 0)
 269             return 1;
 270
 271         /* Now, is it marked with a 'x' or 'X'? If so, avoid it! */
 272         if (mapspot == 'x' || mapspot == 'X')
 273             return 0;
 274     } else {
 275         /* We don't know what it is since we have no map, so return ok! */
 276         return 1;
 277     }
 278
 279     /* Now, check this bmap entry to see if it is one of the
 280        terrain types. */
 281     t = terrain;
 282     if (*t == '~') {
 283         negate = 1;
 284         t++;
 285     } else
 286         negate = 0;
 287
 288     while (*t) {
 289         if (*t == mapspot)
 290             break;
 291         t++;
 292     }
 293     if (negate && *t) {
 294         /* We found it, so we say it's bad since we are negating */
 295         return 0;
 296     } else if (!negate && !*t) {
 297         /* We didn't find it, so we say it's bad since we aren't negating */
 298         return 0;
 299     }
 300
 301     /* According to our bmap, this sector is ok. */
 302     return 1;
 303 }