[Freeciv-Dev] Feedback request: Enhanced macro spiral_outward

["Ross W. Wetmore" <rwetmore@xxxxxxxxxxxx>]

Attached and/or appended is a test program and updated set of macros for
spiral_outward and iterate_outward in map.h.

I was experimenting while unravelling the current iterate_outward, and then
got carried away with featurism. But the results might be of interest and
use in a number of areas. 

The resulting code is hopefully documented enough to be marginally more
understandable at least from a first blush conceptual aspect and I believe
should have slight performance gains. It is definitely easier and more
flexible to code to, i.e. single loop allowing break out from user code.

If any of the core developers wants to add this to the code base, feel
free. Or if is there is sufficient feedback, I will package it up and
submit as a patch.

I have also done a fair bit of tweaking to mapgen.c to produce quite
realistic worlds, terrain and river systems (for 1.11.4 - before I saw Eric
and other's 1.11.5 fixes). I can update it to 1.11.5 and share it with
anyone that wants to test it out (i.e. exercise it as opposed to play on it
:-). Let me know if there is interest.

Enjoy,
RossW
======

#include <stdio.h>

/* Test program for spiral_outward and iterate_outward macros. */

/* ---  cut here --- update map.h */

/*                     :
 * +-++-------------+  :  To the left is the pictorial N-ccw walk
 * |6||5  5  5  5  5|  :  of an outward spiral, as in walk -1y, -1x,
 * | |+-++-------++-+  :  +2y, +2x, ... changing the sign of the xy
 * |6||4||3  3  3||5|  :  increment and the length of the walk at
 * | || |+-++-++-+| |  :  the beginning of each y sequence. 
 * |6||4||2||1||3||5|  : 
 * | || || |+-+| || |  :  The walk spins when y runs off map, skips
 * |6||4||2||1||3||5|  :  y-walk when length > map.xsize and exits 
 * | || |+-++-+| || |  :  when there are no map squares untouched.
 * |6||4||2  2||3||5|  :  Step increment below precedes the walk
 * | |+-++----++-+| |  :  sequence reset otherwise everything would
 * |6||4  4  4  4||5|  :  be shifted around by 1 finishing each leg
 * +-++----------++-+  :  1 into the next square.
 *                     : 
 * MACRO Usage:
 *  spiral_outward(x, y, NWSE, USE_00, condition)
 *    <user code at coordinates (x,y)>
 *  spiral_outward_end
 *
 * Where:
 * x,y        - user supplied index variables set to initial coordinates
 * NWSE       - spiral rotation and start direction
 *              N(1),W(2),S(3),E(4), -ve values for clockwise rotation
 * USE_00     - boolean, set TRUE if x,y should be included in the walk
 * condition  - loop termination condition, e.g. (--dist > 0) or (1)
 *
 * Dependencies:
 * map.xsize, map.ysize and map_adjust_x()
*/

#define spiral_outward(x, y, NWSE, USE_00, COND)       \
{                                                      \
  int _new, _ccw, _inc, _len=0, _cnt=0, _dir= (NWSE);  \
  _ccw= (_dir<0)?(_dir=-_dir,0):1;                     \
  _inc= (_dir>2)?1:-1;                                 \
  _new= _dir&= 1;          /* remember starting dir */ \
  _ccw^= _dir;          /* x->y clockwise, y->x ccw */ \
  if(USE_00) {    /* backup for USE_00 special case */ \
    if((_dir^_ccw)==_new) _inc= -_inc;                 \
    if(_dir^=1) y-= _inc; else x-= _inc;               \
    _len--;                                            \
  }                                                    \
  while(COND) {                                        \
    if(_dir)       /* actually the trailing step of */ \
      y+=_inc;     /* last cycle into a new square  */ \
    else                                               \
      x+=_inc, x= map_adjust_x(x);                     \
    if(--_cnt<0) {            /* time for a change? */ \
      if((_dir^=1) == _new )           /* flip _dir */ \
        _len++;                        /* new cycle */ \
      if((_dir^_ccw) == _new )                         \
        _inc= -_inc;    /* ccw is in phase y, out x */ \
      if(_dir==1) {              /* reset: y=1, x=0 */ \
        if(_len>=map.xsize-1+_new) { /* skip ywalk? */ \
          if( (y<0 && y+_len>map.ysize)                \
           || (y>map.ysize && y-_len<0) )              \
            break;     /* all out-of-bounds so exit */ \
          cnt= 0,y+= _len*_inc;                        \
          continue;    /* x out-of-bounds no y-walk */ \
        }                                              \
        _cnt= _len;                                    \
      } else           /* new x, watch for wrapwall */ \
        _cnt= (_len>=map.xsize)?map.xsize-1:_len;      \
    }                                                  \
    if(y<0 || y>=map.ysize)                            \
      continue;              /* spin when y off map */

#define spiral_outward_end                             \
  }                                                    \
}
/* 2001/05/28 -rww */


/* Replacement for the original iterate_outward macro which looped 
 * thru top/bottom/left/right of increasing squares from the start 
 * values outwards to a given distance.
 *
 * Note:
 *   Spiral_outward in addition to providing a more varied walk
 * and set of termination conditions, is also a single while block
 * from which user code can break out. This applies to the
 * replacement macro here as well. The normal iteration step uses
 * fewer active varibles and is probably marginally faster under
 * most compilers.
 *   Usage of iterate_outward should be considered deprecated.
*/

#define iterate_outward(x0,y0,dist,x,y)                \
{                                                      \
  int  _dist;                                          \
  x= (x0), y= (y0), _dist= (dist)*4+1;                 \
  spiral_outward(x, y, 1, 1, (_cnt!=0 || _dist-->0)) 

#define iterate_outward_end                            \
  spiral_outward_end                                   \
}
/* 2001/05/28 -rww */

/* ---  cut here ---  */

/* Test map for x:y and y:x >2, =2, >1, =1 plus even and odd sizes */
struct map {
  int   xsize;
  int   ysize;
} map = {5,9};

#define map_adjust_x(x)  (x<0?(x+map.xsize):(x>=map.xsize?(x-map.xsize):x))

main(int argc, char *argv[], char *argp[])
{
  /* Test conditions - try all starting directions and rotation, 
   * start outside, at corners, on sides, just inside, inside and centered
   */
  int x=2, y=6, nwse=-4, cnt=0, hit=0;

  spiral_outward(x, y, nwse, 1, (++cnt<1024))
    printf("%4d x,y: %3d,%-3d len=%2d inc=%2d dir=%2d\n", 
      cnt, x, y, _len, _inc, _dir);
    hit++;
  spiral_outward_end
  printf("%4d hits=%d \n", cnt, hit);

  hit=0;
  iterate_outward(2, 6, 2, x, y)
    printf("%4d x,y: %3d,%-3d len=%2d inc=%2d dir=%2d\n", 
      _dist, x, y, _len, _inc, _dir);
    hit++;
  iterate_outward_end
  printf("     hits=%d \n", hit);
}

testmacro.c
Description: Text document