Merge branch 'old-astar' into pathfind-test

diff --combined src/lib/common/path.c
index 04e9ddcc6c31989bf84953172405938075acd7ba,7350e3099f2fdf866e880c4942c29e5b3be18a49..10e1eb0abc9e3da14dea0ffec5626a170330fac3
--- 1/src/lib/common/path.c
--- 2/src/lib/common/path.c
+++ b/src/lib/common/path.c
@@@ -1,11 -1,11 +1,11 @@@
  /*
   *  Empire - A multi-player, client/server Internet based war game.
 - *  Copyright (C) 1986-2010, Dave Pare, Jeff Bailey, Thomas Ruschak,
 - *                           Ken Stevens, Steve McClure
 + *  Copyright (C) 1986-2011, Dave Pare, Jeff Bailey, Thomas Ruschak,
 + *                Ken Stevens, Steve McClure, Markus Armbruster
   *
 - *  This program is free software; you can redistribute it and/or modify
 + *  Empire is free software: you can redistribute it and/or modify
   *  it under the terms of the GNU General Public License as published by
 - *  the Free Software Foundation; either version 2 of the License, or
 + *  the Free Software Foundation, either version 3 of the License, or
   *  (at your option) any later version.
   *
   *  This program is distributed in the hope that it will be useful,
@@@ -14,7 -14,8 +14,7 @@@
   *  GNU General Public License for more details.
   *
   *  You should have received a copy of the GNU General Public License
 - *  along with this program; if not, write to the Free Software
 - *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 + *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
   *
   *  ---
   *
@@@ -25,7 -26,6 +25,6 @@@
   *  ---
   *
   *  path.c: Empire/A* Interface code.
-  *          Define AS_STATS for A* statistics.
   *
   *  Known contributors to this file:
   *     Phil Lapsley, 1991
@@@ -34,6 -34,18 +33,18 @@@
   *     Steve McClure, 1997
   */
  
+ /*
+  * Define AS_STATS for A* statistics on stderr.
+  *
+  * Define AS_NO_PATH_CACHE to disable the path cache.  The path cache
+  * saves a lot of work, but uses lots of memory.  It should be a
+  * significant net win, unless you run out of memory.
+  *
+  * Define AS_NO_NEIGHBOR_CACHE to disable the neighbor cache.  The
+  * neighbor cache trades a modest amount of memory to save a bit of
+  * work.  In its current form, it doesn't really make a difference.
+  */
+ 
  #include <config.h>
  
  #include <stdio.h>
@@@ -50,8 -62,6 +61,6 @@@
  #define BP_NEIGHBORS  6       /* max number of neighbors */
  
  struct bestp {
-     int sctcache_hits;
-     int sctcache_misses;
      int bp_mobtype;
      struct as_data *adp;
  };
@@@ -81,8 -91,10 +90,10 @@@ bp_init(void
      if (bp->adp == NULL)
        return NULL;
  
+ #ifndef AS_NO_NEIGHBOR_CACHE
      if (neighsects == NULL)
        neighsects = calloc(WORLD_SZ() * 6, sizeof(struct sctstr *));
+ #endif
  
      return bp;
  }
@@@ -99,11 -111,16 +110,16 @@@ best_path(struct sctstr *from, struct s
      static struct bestp *mybestpath;
      struct as_data *adp;
      struct as_path *ap;
+     int res;
  
      if (!mybestpath)
        mybestpath = bp_init();
      adp = mybestpath->adp;
+ #ifdef AS_NO_PATH_CACHE
+     ap = NULL;
+ #else
      ap = as_find_cachepath(from->sct_x, from->sct_y, to->sct_x, to->sct_y);
+ #endif
      if (ap == NULL) {
        adp->from.x = from->sct_x;
        adp->from.y = from->sct_y;
@@@ -111,22 -128,21 +127,21 @@@
        adp->to.y = to->sct_y;
        mybestpath->bp_mobtype = mob_type;
  
-       if (as_search(adp) < 0)
+       res = as_search(adp);
+ #ifdef AS_STATS
+       as_stats(adp, stderr);
+ #ifndef AS_NO_NEIGHBOR_CACHE
+       fprintf(stderr, "neighbor cache %zu bytes\n",
+               WORLD_SZ() * 6 * sizeof(struct sctstr *));
+ #endif
+ #endif
+       if (res < 0)
            return -1;
        ap = adp->path;
      }
  
      if (bp_path(ap, path) < 0)
        return -1;
- 
- #ifdef AS_STATS
-     as_stats(adp, stderr);
- #endif /* AS_STATS */
- #ifdef BP_STATS
-     fprintf(stderr, "best path %s\n", path);
-     fprintf(stderr, "cache hits/misses: %d/%d\n",
-           bp->sctcache_hits, bp->sctcache_misses);
- #endif /* BP_STATS */
      return 0;
  }
  
@@@ -211,8 -227,8 +226,8 @@@ bp_neighbors(struct as_coord c, struct 
            *ssp = sp;
        } else {
            sp = *ssp;
-           sx = XNORM(sp->sct_x);
-           sy = YNORM(sp->sct_y);
+           sx = sp->sct_x;
+           sy = sp->sct_y;
        }
        /* No need to calculate cost each time, just make sure we can
           move through it.  We calculate it later. */
@@@ -281,19 -297,25 +296,25 @@@ bp_coord_hash(struct as_coord c
  void
  bp_enable_cachepath(void)
  {
+ #ifndef AS_NO_PATH_CACHE
      as_enable_cachepath();
+ #endif
  }
  
  void
  bp_disable_cachepath(void)
  {
+ #ifndef AS_NO_PATH_CACHE
      as_disable_cachepath();
+ #endif
  }
  
  void
  bp_clear_cachepath(void)
  {
+ #ifndef AS_NO_PATH_CACHE
      as_clear_cachepath();
+ #endif
  }
  
  double