[Freeciv-Dev] Re: (PR#7350) Map radius change with city size

["rwetmore@xxxxxxxxxxxx" <rwetmore@xxxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=7350 >


Jason Short wrote:
> <URL: http://rt.freeciv.org/Ticket/Display.html?id=7350 >
> 
> rwetmore@xxxxxxxxxxxx wrote:
> 
>>>> There is actually a value in doing outwards iteration in unit move 
>>>> searches and such (like with pathfinding) vs array order
>>>> iterations, in that useful things are usually closer. But that is a
>>>> very subtle way to effect both performance and game behaviour.
[...]
> I still don't see why you're concerned about a one-time running of an 
> O(n^4) algorithm when n is almost always 2.  In fact I practically

I think the real point, is why are you arguing so hard for an algorithm
which is clearly not only inefficient but will result in incredibly
worse dependencies down the road. As a maintainer, why spend such effort
to include sub-optimal code and fight any attempt to make this code
robust and efficient, or conform to goals like breakable singly nested
loops?

> guarantee that the algorithm I suggested (O(n^4) generation time, O(n) 
> execution time) will give a faster runtime than your spiral_outward 
> method (O generation time, O(n) execution time) - though the difference 
> will be incredibly small.  (Obviously this isn't true if N is unbounded.
>  But it's not.)

It will be unbounded as soon as the patch for arbitrary city sizes goes
in. Since you are aware of this, the above comment is rather strange or
desperate.

You have given no justification for your choice other than excuses for
why being bad is ok. Perhaps you could provide even one positive reason
in support of the bad code choice.

> jason

Anyway ...

Attached is some cut and paste elements from existing code that hopefully
illustrates some points you seem to have so much trouble with when you
make your various unsupported assertions or repudiations of efficiencies
and degree of difficulty of code required. These are generalized with
clear points where additional optimizations could be added with little
effort. The verbose commentary will hopefully make both the algorithms
and other issues clearer.

Note, these are just quick samples, and one could probably do better with
a smidgen more brainpower.  Brainpower expended up front is always far
more effective than warty fixups down the road :-).

Cheers,
RossW
=====

/*
  *  Previous bad code based on array order looping.
  *  Inner doubly nested loop picks up only a part of a circle of
  *  points and possibly none each pass. The algorithm is O(R^4)
  *  where future extensions (now in patch review stage) could see
  *  R unbounded (R ~ CITYMAP_RADIUS).
  *
  *  Issues:
  *  0)  Inefficient inner loop algorithm
  *  1)  Inefficient nesting of loops, or lack of precomputed inner
  *      loop values.
  *  2)  where does the R^2+2 come from, should it not be just R^2
  *      or (R+1)^2 depending on the definition of R being inclusive.
  *  3)  assumption of symmetries from computing only one quadrant may
  *      impose undue limitations on future evolution to irregularly
  *      shaped city regions.
  *
{ int dist, count = 0;

   for (dist = 0; dist <= CITYMAP_RADIUS * CITYMAP_RADIUS + 2; dist++) {
     for (x = 0; x < CITYMAP_SIZE; x++) {
       for (y = 0; y < CITYMAP_SIZE; y++) {
         int dx = (x - CITYMAP_RADIUS);
         int dy = (y - CITYMAP_RADIUS);

         if (dx * dx + dy * dy == dist) {
           indices[count].x = x;
           indices[count].y = y;
           count++;
         }
       }
     }
   }
}
*/
=====

A counter example ... still based on array order, but precomputing
the array order loop data in a single pass.

{ /*
    * Loop over the citymap in array order computing and ordering the
    * points by the square distance from its centre point.
    *
    * Notes:
    * - citymaps need not be of fixed rectangular shape, and thus using
    *   a linear list of citymap coordinates, besides the advantage of
    *   it being a linear loop that is "breakable", would automatically
    *   optimize the size of the iteration in cases of future extension
    *   to irregular regions. In essence this code generates an *ordered*
    *   list by outwards Pythagorean distance (which has dubious value
    *   since a Freeciv circle or constant distance from a centre point
    *   is actually a square path on the map).
    * - the real value of "circular" cities is to introduce weakness
    *   points around the border where one is "closer" to the city centre
    *   while still being outside the city. In the case of irregular
    *   city regions this is no longer needed. Also, Pythagorean distance
    *   assumes map points are geometrically associated vs connected by
    *   adjacency rules with stepping distances. The latter are needed
    *   for portals and other future extensions.
    *
    * - if one used a linear (as in the corecleanup citymap iterators) vs
    *   array order list of citymap coordinates, then the ordering step is
    *   *much* more efficient, as the distances are almost Pythagorean ordered
    *   to begin with and the O(R^2) sort reduces to O(R/2) or less, i.e. only
    *   a few points on a side are out of order.
    * - this means a spiral outward walk would make a better outer loop
    *   than the array order loops here.
    *
    * - making quadrant symmetry assumptions as above means changing the two
    *   CITYMAP_SIZE ranges to CITYMAP_RADIUS.
    */
   int dist, count = 0;
   int distsq[CITYMAP_SIZE*CITYMAP_SIZE][2];

   /* Precompute the coordinates/index and value in ascending order by value. */
   for (x = 0; x < CITYMAP_SIZE; x++) {
     for (y = 0; y < CITYMAP_SIZE; y++) {
       int dx = (x - CITYMAP_RADIUS);
       int dy = (y - CITYMAP_RADIUS);
       int nn;

       /* count = xy = CITYMAP_SIZE * x + y; */
       count++;
       dist = dx * dx + dy * dy;
       for (nn = count; nn-- > 0; ) {
         /*
          * sort into ascending order by dist
          * Note:  the sort loop is usually only a few iterations deep
          *        and could average something like 1/8th of loop size
          *        if properly tuned to the input loop order.
         */
         if ( distsq[nn][1] > dist ) {
           distsq[nn+1][0] = distsq[nn][0];
           distsq[nn+1][1] = distsq[nn][1];
           break;
         }
       }

       distsq[nn+1][0] = count;
       distsq[nn+1][1] = dist;
     }
   }

   /*
    * Convert the index to and save as coordinate indices.
    * Notes:    This step could be omitted by splitting distsq into 2 arrays,
    *         one of which was the desired output coord indices (vs index).
    *         This loop corresponds to the above code after the work has been
    *         done by a single pass over the inner loops. Alternatively, the
    *         sort step could be moved into this loop to more closely match
    *         the above steps, and possibly organize the data computation and
    *         output ordering steps into more closely related code blocks.
    *           Since count reflects the actual upper bound, it may be much
    *         less than O(CITYMAP_RADIUS^2) or O(CITYMAP_RADIUS^2)*O(sort) if
    *         sort moved down vs O(R^4) of the original.
    */
   while (count-- > 0) {
     indices[count].x = distsq[count][0] % CITYMAP_SIZE;
     indices[count].y = distsq[count][0] / CITYMAP_SIZE;
   }
}
=====

This is an optimized spiral outward loop that could be used to replace array
order loops.

There should be enough commentary to understand the algorithm, which is
relatively trivial and *very* efficient (all loop logic takes place at the
end of a side walk, with the exception of a test for x or y increment and
loop end. This test is minimal for reducing a doubly indexed loop to a
single index.

The loop is also singly nested, i.e. conforms to the desired standard of
making all loops "break"-able.

{
   /*
    * Iterate outwards in a clockwise direction, first step N,
    * until dist == CITYMAP_RADIUS.
    *                     :
    * +-++-------------+  :  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|  :  This walks counterclockwise, first step
    * | || || |+-+| || |  :  North, for a 6x6 grid.
    * |6||4||2||*||3||5|  :
    * | || |+-++-+| || |  :  Step increment below precedes the walk
    * |6||4||2  2||3||5|  :  sequence reset otherwise everything would
    * | |+-++----++-+| |  :  be shifted around by 1 finishing each leg
    * |6||4  4  4  4||5|  :  1 into the next square. This also keeps all
    * +-++----------++-+  :  index logic in the loop start block, making
    *                     :  the spiral_iterate_end block simply "}".
    */

   /*
    * Optimized/hardcoded for a 2n+1 spiral outwards walk for a fixed
    * starting direction and rotational direction (N-clockwise).
    *
    * Init loop control parameters to include the centre/initial point
    * (i.e. for(<init>;;).
    * Where:
    *   ccw   - walk runs counterclockwise (1) or clockwise (0)
    *   dir   - first step is in this direction (NESW = 0123)
    *   new   - marks start of cycle as x (0) or y (1) direction.
    *   inc   - current x or y step increment
    *   len   - length of the current side walk
    *   cnt   - current counter/index for side walk
    *   xx,yy - current coordinate position in the walk. This could
    *           be passed in with addition of first point adjustment,
    *           or as here treated as a relative offset from {x0, y0}.
    */
   int  ccw = 0;
   int  dir = 0;
   int  new = 1;
   int  inc = -1;
   int  len = 0;
   int  cnt = 0;
   int  xx = 1;
   int  yy = 0;
   int  nn;


   /*
    * Failsafe (paranoia) test (i.e. used for 2n+2 even sized squares) ...
    * Could be `while(TRUE)` as loop logic should break/exit on len check
    * in the current optimized case.
    */
   nn = 0;
   while (cnt <= CITYMAP_SIZE)
   {
     /*
      * make the trailing step of the last cycle into a new square to
      * initialize the current walk point (i.e. for(;; <incr step>)
      */
     if (dir) {
       yy += inc;
     } else {
       xx += inc;
     }

     /*
      * main looping logic (i.e. for(; <loop test>; )
      * - handle all stepping changes at end of side.
      */
     if (--cnt < 0) {
       /* Reset dir len inc cnt after walking a side */

       if ((dir ^= 1) == new) {
         /* increment side every other walk, i.e. on 2nd pass */
         len++;
       } else {
         /* Check for 2n+1 odd square exit every other walk, i.e. 1st pass */
         if (len >= CITYMAP_SIZE) {
           /* len++ completes a 2n square, break/exit on 2n+1 or 1st pass */
           break;
         }
       }

       /* Update direction:  ccw is in phase y, out x */
       if ((dir ^ ccw) != new) {
         inc = -inc;
       }

       /* Finally, count down the new side */
       cnt = len-1;

       /*
        * Optional:
        *   Skip sides if doing only a quadrant or partial loop. Detect the
        * sides to skip, set cnt to 0 updating {xx,yy} appropriately to
        * reflect skipped operations, and continue. There may be a need to set
        * cnt to cnt/2 in sides to be executed, and/or other adjustments
        * to control parms or {xx,yy} to reflect missing steps (though a
        * simple continue or current loop fixups is probably the simplest way
        * to handle most cases).
        */
     }
     /* DEBUG:  printf("spiral_outward[%3d] %3.3d,%-3.3d \n", nn, xx, yy); */
     nn++;

     /* User code, aka inner loop, goes here */

   } /* spiral_outward_end */
}
=====

/*
  * spiralOutwardTest.c:  A quick program to test/illustrate the algorithm.
*/
#include "stdio.h"
#include "stdlib.h"

int     CITYMAP_SIZE = 5;
int     CITYMAP_RADIUS = 5 / 2;

int main(int argc, char* argv[])
{
   /*
    * Iterate outwards in a clockwise direction, first step N,
    * until dist == CITYMAP_RADIUS.
    *                     :
    * +-++-------------+  :  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|  :  This walks counterclockwise, first step
    * | || || |+-+| || |  :  North, for a 6x6 grid.
    * |6||4||2||*||3||5|  :
    * | || |+-++-+| || |  :  Step increment below precedes the walk
    * |6||4||2  2||3||5|  :  sequence reset otherwise everything would
    * | |+-++----++-+| |  :  be shifted around by 1 finishing each leg
    * |6||4  4  4  4||5|  :  1 into the next square. This also keeps all
    * +-++----------++-+  :  index logic in the loop start block, making
    *                     :  the spiral_iterate_end block simply "}".
    */

   /*
    * Optimized/hardcoded for a 2n+1 spiral outwards walk for a fixed
    * starting direction and rotational direction (N-clockwise).
    *
    * Init loop control parameters to include the centre/initial point
    * (i.e. for(<init>;;).
    * Where:
    *   ccw   - walk runs counterclockwise (1) or clockwise (0)
    *   dir   - first step is in this direction (NESW = 0123)
    *   new   - marks start of cycle as x (0) or y (1) direction.
    *   inc   - current x or y step increment
    *   len   - length of the current side walk
    *   cnt   - current counter/index for side walk
    *   xx,yy - current coordinate position in the walk. This could
    *           be passed in with addition of first point adjustment,
    *           or as here treated as a relative offset from {x0, y0}.
    */
   int  ccw = 0;
   int  dir = 0;
   int  new = 1;
   int  inc = -1;
   int  len = 0;
   int  cnt = 0;
   int  xx = 1;
   int  yy = 0;
   int nn;

   if (argc > 1) {
     int  nn = atoi(argv[1]);
     if ( nn > 0 ) {
       CITYMAP_SIZE = nn;
       CITYMAP_RADIUS = nn / 2;
     }
   }

   /*
    * Failsafe (paranoia) test (i.e. used for 2n+2 even sized squares) ...
    * Could be `while(TRUE)` as loop logic should break/exit on len check
    * in the current optimized case.
    */
   nn = 0;
   while (cnt <= CITYMAP_SIZE)
   {
     /*
      * make the trailing step of the last cycle into a new square to
      * initialize the current walk point (i.e. for(;; <incr step>)
      */
     if (dir) {
       yy += inc;
     } else {
       xx += inc;
     }

     /*
      * main looping logic (i.e. for(; <loop test>; )
      * - handle all stepping changes at end of side.
      */
     if (--cnt < 0) {
       /* Reset dir len inc cnt after walking a side */

       if ((dir ^= 1) == new) {
         /* increment side every other walk, i.e. on 2nd pass */
         len++;
       } else {
         /* Check for 2n+1 odd square exit every other walk, i.e. 1st pass */
         if (len >= CITYMAP_SIZE) {
           /* len++ completes a 2n square, break/exit on 2n+1 or 1st pass */
           break;
         }
       }

       /* Update direction:  ccw is in phase y, out x */
       if ((dir ^ ccw) != new) {
         inc = -inc;
       }

       /* Finally, count down the new side */
       cnt = len-1;

       /*
        * Optional:
        *   Skip sides if doing only a quadrant or partial loop. Detect the
        * sides to skip, set cnt to 0 updating {xx,yy} appropriately to
        * reflect skipped operations, and continue. There may be a need to set
        * cnt to cnt/2 in sides to be executed, and/or other adjustments
        * to control parms or {xx,yy} to reflect missing steps (though a
        * simple continue or current loop fixups is probably the simplest way
        * to handle most cases).
        */
     }
     printf("spiral_outward[%3d]= %3.3d,%-3.3d \n", nn, xx, yy);  /* DEBUG: */
     nn++;

     /* User code, aka inner loop, goes here */

   } /* spiral_outward_end */

   printf("Done \n");
   exit(0);
}
=====