[Freeciv-Dev] Re: example patch: [xy]_map_iterate

[Jason Dorje Short <vze2zq63@xxxxxxxxxxx>]

Raimar Falke wrote:
> 
> On Thu, Oct 04, 2001 at 09:47:19AM -0400, Jason Dorje Short wrote:
> > [Note: this explanation is long and repetitious.  I'm trying to be as
> > clear as possible.]
> >
> > Raimar Falke wrote:

> > It is an isometric map, but not a correct one if you desire wrapping.
> > It can't wrap properly.  A correction would be:
> >
> >   a     <- y==0
> >  bcd    <- y==1
> > efghi      ...
> >  jkln      ...
> >   mo    <- y==4
> >
> > ^   ^
> > |   |
> > |   x==4
> > |
> > x==0
> >
> > With the addition of n and o it will now successfully wrap in one
> > direction.  y==0 for just tile a.
> 
> This means that wrapping need a odd number in this axis?

There are different ways to measure, but...no.  Refer back to my
previous post if you're still in doubt.

Remember, measuring by x and y sizes won't work.  The two extra tiles I
added did not change x or y dimensions.

> > Putting these directions onto the cartesian representation of the map,
> > we see that "north" is up-left, "south" is down-right, "east" is
> > up-right, and "west" is down-left.  Everything's just rotated 45
> > degrees.  (Note: you can really rotate it 45 degrees in either
> > direction, but you need to take care that its the same direction every
> > time.  I don't remember which way the client rotates things, but we
> > should consider that before choosing.)
> 
> If this paragraph is about an isometric *map*: This means that a is
> the only tile with y==0. But a,d and i are in the north?! Ohh my.

Correct.  North is on the diagonal.  This can be likened to isometric
view, where currently north is no longer up but is on the diagonal.  Put
them together and you've got the correct (from the user's point of view)
north, but with just one or the other (isometric map with cartesian
tileset or cartesian map with isometric tileset) and things won't look
right.

> > All of the changes now come because the current code assumes the
> > topology is rectangular and wraps in one direction.  This code must be
> > replaced by code that does not make these assumptions, but instead uses
> > the correct macros and function calls: is_normal_map_pos instead of
> > map_adjust_[xy], whole_map_iterate instead of for(x...) for(y...),
> > is_real_tile instead of (y>=0 && y<map.ysize), etc.
> 
> You give a precise list of what has to be changed (not the cleanup but
> the actual things). You can also formulate this in mathematical
> ways. I still haven't got all difference between the map now and an
> isometric map.

OK.

Remember, though, that my goal isn't specifically to be able to allow
isometric maps.  It's to be able to allow *arbitrary* maps.  I haven't
figured out the isometric aspects (math) to it yet (although I've seen
Thue's calculations).

> > > Summary: before I don't understand this issue and especially the end
> > > result fully there will be no changes by me.
> >
> > A wise plan in general, but with most of these changes I think it'll be
> > clear that they are cleanups to the code that make things better and
> > remove the assumptions above.
> 
> I agree. But for the changes to savegame I have to know the end result.

True.  Note, though, that the end result will not change at all for the
current topology.  Here's an example.
static void map_rivers_overlay_save(struct section_file *file)
{
  char *pbuf = fc_malloc(map.xsize+1);

  /* put "next" 4 bits of special flags */
  y_map_iterate(y) {
    x_map_iterate(x) {
      pbuf[x] = is_normal_map_pos(x, y) ?
                dec2hex[(map_get_tile(x, y)->special&0xf00)>>8]
                : ' ';
    } x_map_iterate_end;
    pbuf[map.xsize]='\0';
    secfile_insert_str(file, pbuf, "map.n%03d", y);
  } y_map_iterate_end;
  free(pbuf);
}

I've converted manual loops to [xy]_map_iterate loops and added in the
check for is_normal.  The first just removes dependencies on
map.[xy]size; the second skips over invalid map positions (padding the
buffer so that 'x' can still be used as an index into it).  The
corresponding load code is

static void map_rivers_overlay_load(struct section_file *file)
{
  /* get "next" 4 bits of special flags;
     extract the rivers overlay from them */
  y_map_iterate(y) {
    char *terline=secfile_lookup_str_default(file, NULL, "map.n%03d",
y);

    if (terline) {
      x_map_iterate(x) {
        char ch=terline[x];

        if (!is_normal_map_pos(x, y)) /* can safely be skipped */
          continue;

        if(isxdigit(ch)) {
          map_get_tile(x, y)->special |=
            ((ch-(isdigit(ch) ? '0' : 'a'-10))<<8) & S_RIVER;
        } else if(ch!=' ') {
          freelog(LOG_FATAL, "unknown rivers overlay flag (map.n) in map "
                  "at position(%d,%d): %d '%c'", x, y, ch, ch);
          exit(1);
        }
      } x_map_iterate_end;
    }
  } y_map_iterate_end;
  map.have_rivers_overlay = 1;
}

I've done almost the exact same thing, except that now the invalid
positions (spaces) are just skipped over in the string.

> > The most likely way it'll store the data is in a 5x5 array, although
> > this wastes space.  A more general method would be in a single-index
> > array using map_pos_to_index to index into it (it's more general because
> > it can easily be extended to more extreme topologies).
> 
> How complex would the transformation methods?

Short but dense.

Each of the four borders is a diagonal line.  Determining
normalcy/realness involves finding a point's distance from that line. 
The actual line may vary, but for a line of x==y the equations would be:

diff = (x-y);

And 'diff' can then be compared to 0 to see which side of the line the
point (x, y) is on.

Like I said, I haven't worked out the final math.  If you want to see it
I'll do so.

> > Almost all calculations can be done exactly the same way on this
> > isometric map as on the current map.  The neighbor property remains
> > exactly the same.  The only real differences are with border tiles,
> > wrapping/normalcy, and realness.
> 
> > is_real_tile and normalize_map_pos will contain some rather
> > complicated code that will take some time to understand
> 
> You know that normalize_map_pos is used A LOT of times?! You will get
> a real slowdown.

Perhaps.  It's impossible to profile the use of map_adjust_[xy], though,
and most current uses of normalize_map_pos happen in
really_generate_warmap, so it's difficult to tell whether this will be a
"real" slowdown or not.  Remember, normalize_map_pos can always be made
a macro or inline function.

To make it a macro, consider:

#define normalize_map_pos(x, y) (topology_type==rectangle ?
rect_normalize_map_pos(x, y) : iso_normalize_map_pos(x, y))

Where rect_normalize_map_pos may also be a macro and
iso_normalize_map_pos a real function.  If all such changes were made
the code should be faster than current code for rectangular maps (since
current code does require the function call); the only extra overhead is
the one extra check for topology.  (In the case of an isometric map a
function call will still have to be made.)

It'd be much prettier inline:

inline int normalize_map_pos(int *x, int *y)
{
  switch (topology) {
    case rectangle:
      ...
    case isometric:
      ...
    ...
  }
}

This would be much prettier (and possibly faster) as more types are
added.  Note the problems with inlines, though: unless you declare it a
static inline within map.h itself, most compilers (including possibly
gcc right now) can't inline it at all.

> > (if you don't believe me, look at the transformations Thue does to
> > get an isometric view).
> 
> Where?

http://www.freeciv.org/lxr/search?string=is_isometric
http://www.freeciv.org/lxr/source/client/gui-gtk/mapview.c#L269

Our code should be simpler since we're abstracting more of the
complexity away behind the 3 functions (is_normal, is_real, normalize).

> > We are a very long way off from having an actual isometric map.
> 
> *puh* Long email.

Yes...here's another one :-).  Although not a long I think.

> Ok next question: how should an isometric savegame look like?
> 
> 1)
>  a d i
>   c h n
>  b g l
>   f k o
>  e j m
> 
> 2)
>  adi
>  chn
>  bgl
>  fko
>  ejm
> 
> 3)
>    a
>   bcd
>  efghi
>   jkln
>    mo

#3.  Alternately it could be

a
bcd
efghi
jkln
mo

depending on whether you skip over invalid positions or pad them with
empty values for easy indexing.  The latter is what I did (the same as
your #3) in the example above, and I think makes for a good standard
(although slight redundancy in the save file).  Note that the current
topology's savegame won't change any (except extra data will have to be
added to record the kind of topology).

> I still have problems with the fact that less y doesn't mean more
> north.

You probably don't like the isometric tileset, do you?

Neither do I.  I'd rather have the server take care of it so that north
will be up on the screen.  This is what Alpha Centauri and (I believe)
Civ II do.

jason