Update copyright notice

[empserver] / src / lib / common / bestpath.c

diff --git a/src/lib/common/bestpath.c b/src/lib/common/bestpath.c
index 67b4e05d3864119266dec11e1e6bfd4994589df1..5003082aa589ae1a45f6df290742022f47fda804 100644 (file)
--- a/src/lib/common/bestpath.c
+++ b/src/lib/common/bestpath.c
@@ -1,6 +1,6 @@
 /*
  *  Empire - A multi-player, client/server Internet based war game.
- *  Copyright (C) 1986-2006, Dave Pare, Jeff Bailey, Thomas Ruschak,
+ *  Copyright (C) 1986-2008, Dave Pare, Jeff Bailey, Thomas Ruschak,
  *                           Ken Stevens, Steve McClure
  *
  *  This program is free software; you can redistribute it and/or modify
@@ -29,6 +29,7 @@
  * 
  *  Known contributors to this file:
  *     Steve McClure, 1998-2000
+ *     Markus Armbruster, 2006
  */
 
 /* 
@@ -44,22 +45,19 @@
 
 #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(char *, int, int, int);
 
 #define MAXROUTE       100
-#define valid(x,y)     (((x^y)&1)==0)
-
-static char *dirchar = "juygbn";
-int dx[6] = { 2, 1, -1, -2, -1, 1 };
-int dy[6] = { 0, -1, -1, 0, 1, 1 };
+#define valid(x,y)     ((((x) ^ (y)) & 1) == 0)
 
 /*
  * Ok, note that here we malloc some buffers.  BUT, we never
@@ -69,19 +67,21 @@ int dy[6] = { 0, -1, -1, 0, 1, 1 };
  * 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;
 
 /*
  * 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 checked according to the
- * usual rules, and the result is correct.
+ * 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 path or a null pointer.
+ * 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,
@@ -89,14 +89,14 @@ bestownedpath(char *bpath, char *bigmap,
 {
     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++)
@@ -116,6 +116,8 @@ bestownedpath(char *bpath, char *bigmap,
 
     if (!valid(x, y) || !valid(ex, ey))
        return NULL;
+    if (!owned_and_navigable(bigmap, ex, ey, own))
+       return NULL;
 
     for (i = 0; i < WORLD_X; i++)
        for (j = 0; j < WORLD_Y; j++)
@@ -130,7 +132,7 @@ bestownedpath(char *bpath, char *bigmap,
     maxy = y + 1;
 
     do {
-       if (++routelen == MAXROUTE - 1)
+       if (++routelen == MAXROUTE)
            return NULL;
        markedsectors = 0;
        for (scanx = minx; scanx <= maxx; scanx++) {
@@ -140,26 +142,28 @@ bestownedpath(char *bpath, char *bigmap,
                if (!valid(x, y))
                    continue;
                if (((mapindex[x][y] & 0x1FFF) == routelen - 1)) {
-                   for (i = 0; i < 6; i++) {
-                       tx = x + dx[i];
-                       ty = y + dy[i];
+                   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 + 1) << 13) + routelen;
+                                   ((i - DIR_FIRST + 1) << 13) + routelen;
                                markedsectors++;
                            }
                        }
                        if (tx == ex && ty == ey) {
-                           bpath[routelen] = 'h';
-                           bpath[routelen + 1] = 0;
+                           bpath[routelen] = 0;
                            while (routelen--) {
-                               i = (mapindex[tx][ty] >> 13) - 1;
-                               bpath[routelen] = dirchar[i];
-                               tx = tx - dx[i];
-                               ty = ty - dy[i];
+                               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);
                            }