Permit disabling of A* path cache at compile-time
authorMarkus Armbruster <armbru@pond.sub.org>
Sat, 19 Feb 2011 14:00:03 +0000 (15:00 +0100)
committerMarkus Armbruster <armbru@pond.sub.org>
Tue, 12 Apr 2011 19:40:08 +0000 (21:40 +0200)
Mostly to measure its effectiveness.  Compile with AS_NO_PATH_CACHE
defined to disable it.

Turns out the path cache is quite effective.  For my continental test
case (Hvy Metal 2 updates), it reduces the number of searches by a
factor of 18.5, speeding up distribution path assembly by a factor of
7.  The price is memory: it uses 135 times more memory than the A*
library.  For my island test case (Hvy Plastic 2 updates), I get 4
times search reduction, 3.5 times faster distribution path assembly,
36 times more memory.

src/lib/common/path.c

index 9cdf959ec389380e0db58aed13805b0bbaead32b..f36d48289645b0885664a4c90033678cf2b2d698 100644 (file)
@@ -26,7 +26,6 @@
  *  ---
  *
  *  path.c: Empire/A* Interface code.
- *          Define AS_STATS for A* statistics.
  *
  *  Known contributors to this file:
  *     Phil Lapsley, 1991
  *     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.
+ */
+
 #include <config.h>
 
 #include <stdio.h>
@@ -103,7 +110,11 @@ best_path(struct sctstr *from, struct sctstr *to, char *path, int mob_type)
     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;
@@ -278,19 +289,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