[Freeciv-Dev] (PR#6721) A Quincuncial topology

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

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

I'm not happy with the use of is_reversed everywhere.  I think this is a
hack that isn't mathematically clean.  It causes problems when we try to
do things like have mobius-strip maps.

Instead track an orientation of the tile: a direction8 value.  I think
this will give more understandable code and also allow more future
topologies.

Background:

is_reversed is a boolean value that applies to a particular position. 
If it is true, then the particular invocation of the position that we're
dealing with is reversed as compared to the normalized version of that
position.  So when we normalize the position we determine whether or not
it is reversed.

It probably makes more sense with an example.  There is an
adjc_dir_iterate_isreversed macro.  It's just like adjc_dir_iterate
except it also gives an is_reversed flag for each position returned
(determined via a specialized normalize operation).  So the code in path
finding to iterate around a particular position goes like:

  adjc_dir_iterate_isreversed(x0, y0, x1, y1, dir, is_reversed) {
    node1 = get_node(x1, y1);
    /* ... */
    node1->path_to_here = normalize_dir(dir, is_reversed);
  } adjc_dir_iterate_isreversed_end;

normalize_dir, of course, just reverses the direction if the is_reversed
flag is set.

This is a prime example of (current) code that won't work without
changes when the map is not well-oriented, so some type of change is
needed here.  But I think the is_reversed method is not a good one.

Mathematically, I think it's not a clean solution.  In the above case,
the is_reversed flag applies to the pre-normalized (x1,y1) position - a
value that doesn't even exist.  We're passing around a flag that doesn't
have meaning outside of its direct context.  The result is that the code
is not very intuitive.  It also prevents any future topology from having
orientation other than standard or reversed.

In general, I think we have to do normalization of directions along with
their original position.  For instance instead of keeping around the
is_reversed value we should take the pre-normalized position and call

  dir = normalize_dir(x1, y1, dir);

on the direction, or better yet

  normalize_vector(&x1, &y1, &dir);

Now in the above case I think all the work should be done by the macro.
 So the code should read


  adjc_dir_iterate_full(0, y0, x1, y1, dir0, dir1) {
    node1 = get_node(x1, y1);
    /* ... */
    node1->path_to_here = dir1;
  } adjc_dir_iterate_full_end;

where dir1 is the version of dir0, with respect to (x1, y1).  (Better,
we could return the direction needed to get from (x1,y1) back to
(x0,y0).  Thus (x0,y0,dir0) is the inverse vector of (x1,y1,dir1).  The
important point is that dir0 is relative to (x0,y0) while dir1 is
relative to (x1,y1).  And dir1 has a concrete meaning that programmers
can wrap their minds around.

In general, rather than tracking an is_reversed value we should track
the orientation of the tile in terms of a direction (a direction8).  And
instead of tracking directions and orientations separately, we should
track _vectors_ wherever possible.

jason