fairland: Nicer & much faster replacement for next_vector()

next_vector() is kind of cute, but it is also unobvious, cumbersome to
use, and slow for arguments greater than one.

Replace it by hexagon_first(), hexagon_next().  The new code takes
O(1) time, whereas the old code takes O(n).  Iterating over a hexagon
changes from

       for (i = 0; i < n; ++i)
           vector[i] = 0;
       do {
           x = x0;
           y = y0;
           for (i = 0; i < n; ++i) {
               x = new_x(x + dirx[vector[i]]);
               y = new_y(y + diry[vector[i]]);
           }
	   do stuff with @x, @y...
       } while (next_vector(n));

to

       hexagon_first(&hexit, x0, y0, n, &x, &y);
       do {
	   do stuff with @x, @y...
       } while (hexagon_next(&hexit, &x, &y));

In my measurements, it's ~8% slower for n == 1, 25% faster for n == 2,
and more than three times faster for n == 6.

fairland's performance is dominated by it.  Creating worlds for the
Common Fever blitz (distance arguments 3 and 2) and the Hvy Fever
Blitz (distance arguments 6 and 3) on my machine speeds up by a factor
of 1.6 and 2.1, respectively.

Of course, fairland performance is hardly an issue on today's
machines: it takes fairly impractical setups to push run time over a
second.

Signed-off-by: Markus Armbruster <armbru@pond.sub.org>

diff --git a/src/util/fairland.c b/src/util/fairland.c
index c42fbbb3d3ddd928bdae3c3955373e5275387e07..a4c0c06a74e7f2f32dc2e265327d2ae110aef758 100644 (file)
--- a/src/util/fairland.c
+++ b/src/util/fairland.c
@@ -104,6 +104,7 @@
 #include <unistd.h>
 #include "chance.h"
 #include "optlist.h"
+#include "path.h"
 #include "prototypes.h"
 #include "sect.h"
 #include "version.h"
@@ -188,7 +189,6 @@ static int **own;           /* owner of the sector.  -1 means water */
 static int **elev;             /* elevation of the sectors */
 static int **sectx, **secty;   /* the sectors for each continent */
 static int **sectc;            /* which sectors are on the coast? */
-static int *vector;            /* used for measuring distances */
 static int *weight;            /* used for placing mountains */
 static int *dsea, *dmoun;      /* the dist to the ocean and mountain */
 
@@ -476,7 +476,6 @@ allocate_memory(void)
 
     capx = calloc(nc, sizeof(int));
     capy = calloc(nc, sizeof(int));
-    vector = calloc(WORLD_X + WORLD_Y, sizeof(int));
     own = calloc(WORLD_X, sizeof(int *));
     elev = calloc(WORLD_X, sizeof(int *));
     for (i = 0; i < WORLD_X; ++i) {
@@ -637,22 +636,42 @@ find_coast(int c)
     }
 }
 
-/* Used for measuring distances
-*/
-static int
-next_vector(int n)
+struct hexagon_iter {
+    int dir, i, n;
+};
+
+/*
+ * Start iterating around @x0,@y0 at distance @d.
+ * Set *x,*y to coordinates of the first sector.
+ */
+static inline void
+hexagon_first(struct hexagon_iter *iter, int x0, int y0, int n,
+             int *x, int *y)
 {
-    int i;
+    *x = new_x(x0 - 2 * n);
+    *y = y0;
+    iter->dir = DIR_FIRST;
+    iter->i = 0;
+    iter->n = n;
+}
 
-    if (n == 1) {
-       vector[0] += 1;
-       vector[0] %= 6;
-       return vector[0];
+/*
+ * Continue iteration started with hexagon_first().
+ * Set *x,*y to coordinates of the next sector.
+ * Return whether we're back at the first sector, i.e. iteration is
+ * complete.
+ */
+static inline int
+hexagon_next(struct hexagon_iter *iter, int *x, int *y)
+{
+    *x = new_x(*x + diroff[iter->dir][0]);
+    *y = new_y(*y + diroff[iter->dir][1]);
+    iter->i++;
+    if (iter->i == iter->n) {
+       iter->i = 0;
+       iter->dir++;
     }
-    for (i = 1; i < n && vector[i] == vector[i - 1]; ++i) ;
-    vector[i - 1] += 1;
-    vector[i - 1] %= 6;
-    return i > 1 || vector[0] > 0;
+    return iter->dir <= DIR_LAST;
 }
 
 /* Test to see if we're allowed to grow there: the arguments di and id
@@ -660,26 +679,20 @@ next_vector(int n)
 static int
 try_to_grow(int c, int newx, int newy, int d)
 {
-    int i, j, px, py;
+    int i, px, py;
+    struct hexagon_iter hexit;
 
     if (own[newx][newy] != -1)
        return 0;
 
     for (i = 1; i <= d; ++i) {
-       for (j = 0; j < i; ++j)
-           vector[j] = 0;
+       hexagon_first(&hexit, newx, newy, i, &px, &py);
        do {
-           px = newx;
-           py = newy;
-           for (j = 0; j < i; ++j) {
-               px = new_x(px + dirx[vector[j]]);
-               py = new_y(py + diry[vector[j]]);
-           }
            if (own[px][py] != -1 &&
                own[px][py] != c &&
                (DISTINCT_ISLANDS || own[px][py] < nc))
                return 0;
-       } while (next_vector(i));
+       } while (hexagon_next(&hexit, &px, &py));
     }
     sectx[c][isecs[c]] = newx;
     secty[c][isecs[c]] = newy;
@@ -911,18 +924,12 @@ create_elevations(void)
 static int
 distance_to_what(int x, int y, int flag)
 {
-    int j, d, px, py;
+    int d, px, py;
+    struct hexagon_iter hexit;
 
     for (d = 1; d < 5; ++d) {
-       for (j = 0; j < d; ++j)
-           vector[j] = 0;
+       hexagon_first(&hexit, x, y, d, &px, &py);
        do {
-           px = x;
-           py = y;
-           for (j = 0; j < d; ++j) {
-               px = new_x(px + dirx[vector[j]]);
-               py = new_y(py + diry[vector[j]]);
-           }
            switch (flag) {
            case 0:             /* distance to sea */
                if (own[px][py] == -1)
@@ -937,7 +944,7 @@ distance_to_what(int x, int y, int flag)
                    return d;
                break;
            }
-       } while (next_vector(d));
+       } while (hexagon_next(&hexit, &px, &py));
     }
     return d;
 }