/*
* Empire - A multi-player, client/server Internet based war game.
- * Copyright (C) 1986-2006, Dave Pare, Jeff Bailey, Thomas Ruschak,
+ * Copyright (C) 1986-2010, Dave Pare, Jeff Bailey, Thomas Ruschak,
* Ken Stevens, Steve McClure
*
* This program is free software; you can redistribute it and/or modify
* ---
*
* bestpath.c: Find the best path between sectors
- *
+ *
* Known contributors to this file:
* Steve McClure, 1998-2000
+ * Markus Armbruster, 2006
*/
-/*
+/*
* IMPORTANT: These routines are very selectively used in the server.
*
* "bestownedpath" is only used to determine paths for ships and planes.
- *
+ *
* Callers should not be calling these directly anymore. They should use
* the "BestShipPath", "BestAirPath", "BestLandPath" and "BestDistPath"
* functions. Note that those last two use the A* algorithms to find
#include <config.h>
-#include "misc.h"
-#include "xy.h"
-#include "sect.h"
#include "file.h"
+#include "misc.h"
#include "nat.h"
-#include "common.h"
#include "optlist.h"
+#include "path.h"
+#include "prototypes.h"
+#include "sect.h"
+#include "xy.h"
-static int owned_and_navigable(s_char *, int, int, s_char *, int);
-
-#define MAXROUTE 100 /* return '?' if path longer than this */
-#define valid(x,y) (((x^y)&1)==0)
-
-/* ________________________________________________________________
-**
-** bestpath(x1,y1,x2,y2,(s_char *)terrain);
-**
-** Calculate routing string to get from sector [x1,y1] to sector [x2,y2]
-** via a specified type of terrain.
-**
-** Specify:
-**
-** x1,y1 starting coordinates
-**
-** x2,y2 destination coordinates
-**
-** terrain ptr to string showing the types of sectors that
-** we're allowed to pass through:
-**
-** A null string enables routing through any kind of
-** sector (useful for airplanes).
-**
-** A string that begins with an 'R' ensures that
-** the source and destination sectors also match
-** the specified type of terrain.
-**
-** A string that begins with a '~' (after the 'R',
-** if necessary) specifies that we can pass through
-** any kind of sector EXCEPT those in the remainder
-** of the string.
-**
-** Examples:
-**
-** "R~.^" all sectors along route must be
-** non-ocean, non-mountain
-**
-** "+" all sectors between start and end
-** must be highway
-**
-** "h. " all sectors along route must be
-** harbor, water, or unmapped
-**
-** 'bestpath' returns a pointer to a route string containing either:
-**
-** yugjbn - string of normal routing characters if route possible
-** ? - if route is longer than MAXROUTE characters
-** \0 - (null string) if no route possible
-** h - if start and end points are the same sector
-** ________________________________________________________________
-*/
+static int owned_and_navigable(char *, int, int, int);
-static char *dirchar = "juygbn";
-int dx[6] = { 2, 1, -1, -2, -1, 1 };
-int dy[6] = { 0, -1, -1, 0, 1, 1 };
+#define MAXROUTE 100
+#define valid(x,y) ((((x) ^ (y)) & 1) == 0)
/*
* Ok, note that here we malloc some buffers. BUT, we never
* would be slow. And, since world size only changes at init
* time, we can do this safely.
*/
-static unsigned int *mapbuf;
-static unsigned int **mapindex;
+static unsigned short *mapbuf;
+static unsigned short **mapindex;
-s_char *
-bestownedpath(s_char *bpath,
- s_char *bigmap,
- int x, int y, int ex, int ey, s_char *terrain, int own)
+/*
+ * Find passable path from X, Y to EX, EY for nation OWN.
+ * BPATH is a buffer capable of holding at least MAXROUTE characters.
+ * If BIGMAP is null, all sectors are passable (useful for flying).
+ * Else it is taken to be a bmap.
+ * Sectors owned by or allied to OWN are then passable according to
+ * the usual rules.
+ * Other sectors are assumed to be passable when BIGMAP shows '.' or
+ * nothing.
+ * Return a path if found, else a null pointer.
+ * Wart: the path isn't terminated with 'h', except when if X,Y equals
+ * EX,EY.
+ */
+char *
+bestownedpath(char *bpath, char *bigmap,
+ int x, int y, int ex, int ey, int own)
{
- int i, j, tx, ty, markedsectors, restr2;
+ int i, j, tx, ty, markedsectors;
int minx, maxx, miny, maxy, scanx, scany;
- unsigned int routelen;
+ unsigned routelen;
if (!mapbuf)
- mapbuf = malloc((WORLD_X * WORLD_Y) *
- sizeof(unsigned int));
+ mapbuf = malloc(WORLD_X * WORLD_Y * sizeof(*mapbuf));
if (!mapbuf)
return NULL;
if (!mapindex) {
- mapindex = malloc(WORLD_X * sizeof(unsigned int *));
+ mapindex = malloc(WORLD_X * sizeof(*mapindex));
if (mapindex) {
/* Setup the map pointers */
for (i = 0; i < WORLD_X; i++)
if (!mapindex)
return NULL;
- bpath[0] = 0;
- if (0 != (restr2 = (*terrain == 'R')))
- terrain++;
-
x = XNORM(x);
y = YNORM(y);
ex = XNORM(ex);
ey = YNORM(ey);
- if (x == ex && y == ey) {
- bpath[0] = 'h';
- bpath[1] = 0;
- return bpath;
- }
+ if (x == ex && y == ey)
+ return "h";
if (!valid(x, y) || !valid(ex, ey))
return NULL;
-
- if (restr2 && (!owned_and_navigable(bigmap, x, y, terrain, own) ||
- !owned_and_navigable(bigmap, x, y, terrain, own)))
+ if (!owned_and_navigable(bigmap, ex, ey, own))
return NULL;
for (i = 0; i < WORLD_X; i++)
maxy = y + 1;
do {
- if (++routelen == MAXROUTE) {
- bpath[0] = '?';
- bpath[1] = 0;
- return bpath;
- }
+ if (++routelen == MAXROUTE)
+ return NULL;
markedsectors = 0;
for (scanx = minx; scanx <= maxx; scanx++) {
x = XNORM(scanx);
for (scany = miny; scany <= maxy; scany++) {
y = YNORM(scany);
- if (valid(x, y)) {
- if ((((mapindex[x][y]) & 0x1FFF) == (routelen - 1))) {
- for (i = 0; i < 6; i++) {
- tx = x + dx[i];
- ty = y + dy[i];
- tx = XNORM(tx);
- ty = YNORM(ty);
- if (mapindex[tx][ty] == 0xFFFF) {
- if (owned_and_navigable(bigmap, tx, ty,
- terrain, own)
- || (tx == ex && ty == ey && !restr2)) {
- mapindex[tx][ty] =
- ((i + 1) << 13) + routelen;
- markedsectors++;
- }
+ if (!valid(x, y))
+ continue;
+ if (((mapindex[x][y] & 0x1FFF) == routelen - 1)) {
+ for (i = DIR_FIRST; i <= DIR_LAST; i++) {
+ tx = x + diroff[i][0];
+ ty = y + diroff[i][1];
+ tx = XNORM(tx);
+ ty = YNORM(ty);
+ if (mapindex[tx][ty] == 0xFFFF) {
+ if (owned_and_navigable(bigmap, tx, ty, own)) {
+ if (CANT_HAPPEN(i < DIR_FIRST || i > DIR_LAST))
+ i = DIR_STOP;
+ mapindex[tx][ty] =
+ ((i - DIR_FIRST + 1) << 13) + routelen;
+ markedsectors++;
}
- if (tx == ex && ty == ey) {
- bpath[routelen] = 0;
- while (routelen--) {
- i = ((mapindex[tx][ty]) >> 13) - 1;
- bpath[routelen] = dirchar[i];
- tx = tx - dx[i];
- ty = ty - dy[i];
- tx = XNORM(tx);
- ty = YNORM(ty);
- }
- return bpath;
+ }
+ if (tx == ex && ty == ey) {
+ bpath[routelen] = 0;
+ while (routelen--) {
+ i = (mapindex[tx][ty] >> 13)
+ - 1 + DIR_FIRST;
+ bpath[routelen] = dirch[i];
+ tx = tx - diroff[i][0];
+ ty = ty - diroff[i][1];
+ tx = XNORM(tx);
+ ty = YNORM(ty);
}
+ return bpath;
}
}
}
maxx += 2;
} while (markedsectors);
- bpath[0] = 0;
return NULL; /* no route possible */
}
-/* return TRUE if sector is passable */
+/*
+ * Return non-zero if sector X, Y is passable.
+ * If BIGMAP is null, all sectors are passable (useful for flying).
+ * Else it is taken to be a bmap.
+ * Sectors owned by or allied to OWN are checked according to the
+ * usual rules, and the result is correct.
+ * Other sectors are assumed to be passable when BIGMAP shows '.' or
+ * nothing.
+ */
static int
-owned_and_navigable(s_char *map, int x, int y, s_char *terrain, int own)
+owned_and_navigable(char *bigmap, int x, int y, int own)
{
- s_char c;
- s_char *t;
- s_char mapspot; /* What this spot on the bmap is */
- int negate;
- struct sctstr *sect;
- int rel;
+ char mapspot;
+ struct sctstr sect;
- /* No terrain to check? Everything is navigable! (this
- probably means we are flying) */
- if (!*terrain)
+ if (!bigmap)
return 1;
- /* Are we checking this map? */
- if (map) {
- /* Do we know what this sector is? If not, we assume it's ok,
- since otherwise we'll never venture anywhere */
- mapspot = map[sctoff(x, y)];
- if (mapspot == ' ' || mapspot == 0)
+ /* Owned or allied sector? Check the real sector. */
+ getsect(x, y, §);
+ if (sect.sct_own == own
+ || (sect.sct_own && getrel(getnatp(sect.sct_own), own) == ALLIED)) {
+ /* FIXME duplicates shp_check_nav() logic */
+ switch (dchr[sect.sct_type].d_nav) {
+ case NAVOK:
return 1;
-
- /* Now, is it marked with a 'x' or 'X'? If so, avoid it! */
- if (mapspot == 'x' || mapspot == 'X')
+ case NAV_CANAL:
+ /* FIXME return 1 when all ships have M_CANAL */
+ return 0;
+ case NAV_02:
+ return sect.sct_effic >= 2;
+ case NAV_60:
+ return sect.sct_effic >= 60;
+ default:
return 0;
- } else {
- /* We don't know what it is since we have no map, so return ok! */
- return 1;
- }
-
- /* Now, check this bmap entry to see if it is one of the
- terrain types. */
- t = terrain;
- if (*t == '~') {
- negate = 1;
- t++;
- } else
- negate = 0;
-
- while (*t) {
- if (*t == mapspot)
- break;
- t++;
- }
- if (negate && *t) {
- /* We found it, so we say it's bad since we are negating */
- return 0;
- } else if (!negate && !*t) {
- /* We didn't find it, so we say it's bad since we aren't negating */
- return 0;
- }
-
- /* According to our bmap, this sector is ok so far. */
-
- /* Ok, we made it this far. Now get the sector */
- sect = getsectp(x, y);
- c = dchr[sect->sct_type].d_mnem;
- /* Ok, now, check the owner if needed */
- if (own >= 0) {
- if (sect->sct_own != own) {
- rel = getrel(getnatp(sect->sct_own), own);
- /* We can't sail through deity sectors, but we can sail
- through any ocean */
- if (rel < FRIENDLY && sect->sct_type != SCT_WATER)
- return 0;
}
}
- /* Ok, now, check these two sector types */
- /* check for bad harbors. */
- if (c == 'h' && sect->sct_effic < 2)
- return 0;
- /* check for bad bridges */
- if (c == '=' && sect->sct_effic < 60)
- return 0;
- /* Woo-hoo, it's ok! */
- return 1;
+
+ /* Can only check bigmap */
+ mapspot = bigmap[sect.sct_uid];
+ return mapspot == '.' || mapspot == ' ' || mapspot == 0;
}