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>
#include <unistd.h>
#include "chance.h"
#include "optlist.h"
#include <unistd.h>
#include "chance.h"
#include "optlist.h"
#include "prototypes.h"
#include "sect.h"
#include "version.h"
#include "prototypes.h"
#include "sect.h"
#include "version.h"
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 **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 */
static int *weight; /* used for placing mountains */
static int *dsea, *dmoun; /* the dist to the ocean and mountain */
capx = calloc(nc, sizeof(int));
capy = calloc(nc, sizeof(int));
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) {
own = calloc(WORLD_X, sizeof(int *));
elev = calloc(WORLD_X, sizeof(int *));
for (i = 0; i < WORLD_X; ++i) {
-/* 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)
+ *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
}
/* Test to see if we're allowed to grow there: the arguments di and id
static int
try_to_grow(int c, int newx, int newy, int d)
{
static int
try_to_grow(int c, int newx, int newy, int d)
{
+ int i, px, py;
+ struct hexagon_iter hexit;
if (own[newx][newy] != -1)
return 0;
for (i = 1; i <= d; ++i) {
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);
- 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;
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;
}
sectx[c][isecs[c]] = newx;
secty[c][isecs[c]] = newy;
static int
distance_to_what(int x, int y, int flag)
{
static int
distance_to_what(int x, int y, int flag)
{
+ int d, px, py;
+ struct hexagon_iter hexit;
for (d = 1; d < 5; ++d) {
for (d = 1; d < 5; ++d) {
- for (j = 0; j < d; ++j)
- vector[j] = 0;
+ hexagon_first(&hexit, x, y, d, &px, &py);
- 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)
switch (flag) {
case 0: /* distance to sea */
if (own[px][py] == -1)
- } while (next_vector(d));
+ } while (hexagon_next(&hexit, &px, &py));