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-2007, 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  *     Markus Armbruster, 2006
  33  */
  34
  35 /*
  36  * IMPORTANT: These routines are very selectively used in the server.
  37  *
  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 <config.h>
  47
  48 #include "file.h"
  49 #include "misc.h"
  50 #include "nat.h"
  51 #include "optlist.h"
  52 #include "path.h"
  53 #include "prototypes.h"
  54 #include "sect.h"
  55 #include "xy.h"
  56
  57 static int owned_and_navigable(char *, int, int, int);
  58
  59 #define MAXROUTE        100
  60 #define valid(x,y)      ((((x) ^ (y)) & 1) == 0)
  61
  62 /*
  63  * Ok, note that here we malloc some buffers.  BUT, we never
  64  * free them.  Why, you may ask?  Because we want to allocate
  65  * them based on world size which is now (or soon to be) dynamic,
  66  * but we don't want to allocate each and every time, since that
  67  * would be slow.  And, since world size only changes at init
  68  * time, we can do this safely.
  69  */
  70 static unsigned short *mapbuf;
  71 static unsigned short **mapindex;
  72
  73 /*
  74  * Find passable path from X, Y to EX, EY for nation OWN.
  75  * BPATH is a buffer capable of holding at least MAXROUTE characters.
  76  * If BIGMAP is null, all sectors are passable (useful for flying).
  77  * Else it is taken to be a bmap.
  78  * Sectors owned by or allied to OWN are then passable according to
  79  * the usual rules.
  80  * Other sectors are assumed to be passable when BIGMAP shows '.' or
  81  * nothing.
  82  * Return a path if found, else a null pointer.
  83  * Wart: the path isn't terminated with 'h', except when if X,Y equals
  84  * EX,EY.
  85  */
  86 char *
  87 bestownedpath(char *bpath, char *bigmap,
  88               int x, int y, int ex, int ey, int own)
  89 {
  90     int i, j, tx, ty, markedsectors;
  91     int minx, maxx, miny, maxy, scanx, scany;
  92     unsigned routelen;
  93
  94     if (!mapbuf)
  95         mapbuf = malloc(WORLD_X * WORLD_Y * sizeof(*mapbuf));
  96     if (!mapbuf)
  97         return NULL;
  98     if (!mapindex) {
  99         mapindex = malloc(WORLD_X * sizeof(*mapindex));
 100         if (mapindex) {
 101             /* Setup the map pointers */
 102             for (i = 0; i < WORLD_X; i++)
 103                 mapindex[i] = &mapbuf[WORLD_Y * i];
 104         }
 105     }
 106     if (!mapindex)
 107         return NULL;
 108
 109     x = XNORM(x);
 110     y = YNORM(y);
 111     ex = XNORM(ex);
 112     ey = YNORM(ey);
 113
 114     if (x == ex && y == ey)
 115         return "h";
 116
 117     if (!valid(x, y) || !valid(ex, ey))
 118         return NULL;
 119     if (!owned_and_navigable(bigmap, ex, ey, own))
 120         return NULL;
 121
 122     for (i = 0; i < WORLD_X; i++)
 123         for (j = 0; j < WORLD_Y; j++)
 124             mapindex[i][j] = 0xFFFF;    /* clear the workspace  */
 125
 126     routelen = 0;               /* path length is now 0 */
 127     mapindex[x][y] = 0;         /* mark starting spot   */
 128     markedsectors = 1;          /* source sector marked */
 129     minx = x - 2;               /* set X scan bounds    */
 130     maxx = x + 2;
 131     miny = y - 1;               /* set Y scan bounds    */
 132     maxy = y + 1;
 133
 134     do {
 135         if (++routelen == MAXROUTE)
 136             return NULL;
 137         markedsectors = 0;
 138         for (scanx = minx; scanx <= maxx; scanx++) {
 139             x = XNORM(scanx);
 140             for (scany = miny; scany <= maxy; scany++) {
 141                 y = YNORM(scany);
 142                 if (!valid(x, y))
 143                     continue;
 144                 if (((mapindex[x][y] & 0x1FFF) == routelen - 1)) {
 145                     for (i = DIR_FIRST; i <= DIR_LAST; i++) {
 146                         tx = x + diroff[i][0];
 147                         ty = y + diroff[i][1];
 148                         tx = XNORM(tx);
 149                         ty = YNORM(ty);
 150                         if (mapindex[tx][ty] == 0xFFFF) {
 151                             if (owned_and_navigable(bigmap, tx, ty, own)) {
 152                                 if (CANT_HAPPEN(i < DIR_FIRST || i > DIR_LAST))
 153                                     i = DIR_STOP;
 154                                 mapindex[tx][ty] =
 155                                     ((i - DIR_FIRST + 1) << 13) + routelen;
 156                                 markedsectors++;
 157                             }
 158                         }
 159                         if (tx == ex && ty == ey) {
 160                             bpath[routelen] = 0;
 161                             while (routelen--) {
 162                                 i = (mapindex[tx][ty] >> 13)
 163                                     - 1 + DIR_FIRST;
 164                                 bpath[routelen] = dirch[i];
 165                                 tx = tx - diroff[i][0];
 166                                 ty = ty - diroff[i][1];
 167                                 tx = XNORM(tx);
 168                                 ty = YNORM(ty);
 169                             }
 170                             return bpath;
 171                         }
 172                     }
 173                 }
 174             }
 175         }
 176         miny--;
 177         maxy++;
 178         minx -= 2;
 179         maxx += 2;
 180     } while (markedsectors);
 181
 182     return NULL;                /* no route possible    */
 183 }
 184
 185 /*
 186  * Return non-zero if sector X, Y is passable.
 187  * If BIGMAP is null, all sectors are passable (useful for flying).
 188  * Else it is taken to be a bmap.
 189  * Sectors owned by or allied to OWN are checked according to the
 190  * usual rules, and the result is correct.
 191  * Other sectors are assumed to be passable when BIGMAP shows '.' or
 192  * nothing.
 193  */
 194 static int
 195 owned_and_navigable(char *bigmap, int x, int y, int own)
 196 {
 197     char mapspot;
 198     struct sctstr sect;
 199
 200     if (!bigmap)
 201         return 1;
 202
 203     /* Owned or allied sector?  Check the real sector.  */
 204     getsect(x, y, &sect);
 205     if (sect.sct_own == own
 206         || (sect.sct_own && getrel(getnatp(sect.sct_own), own) == ALLIED)) {
 207         /* FIXME duplicates shp_check_nav() logic */
 208         switch (dchr[sect.sct_type].d_nav) {
 209         case NAVOK:
 210             return 1;
 211         case NAV_CANAL:
 212             /* FIXME return 1 when all ships have M_CANAL */
 213             return 0;
 214         case NAV_02:
 215             return sect.sct_effic >= 2;
 216         case NAV_60:
 217             return sect.sct_effic >= 60;
 218         default:
 219             return 0;
 220         }
 221     }
 222
 223     /* Can only check bigmap */
 224     mapspot = bigmap[sctoff(x, y)];
 225     return mapspot == '.' || mapspot == ' ' || mapspot == 0;
 226 }