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

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Thu, Oct 04, 2001 at 03:44:43PM -0400, Jason Dorje Short wrote:
> 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.

But there need to be map sizes. The user want the set them.

> > > 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.

IMHO you will need methods (for example in mapgen) to transform this
coordinates into a "sane" space. How would code like

  for (y=0;y<map.ysize/10;y++) {
    for (x=0;x<map.xsize;x++) {

change? Would you introduce a distance_from_north(x,y) or a similar
thing?

> > > 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).

It looks to me that if I apply your patch now that another patch (the
final one) is needed which touches the same places.

> > > > 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) {

IMHO this macro has to get the current y coordinate.

>       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.

So you just transform the (x,y) position to a "normal" system (where
y==0 is the northmost position, the position where things wrap) and
check this "normal" position?!

> > > 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.)

Ok so there is minimal slowdown for the non-isometric case. What about
the iso_normalize_map_pos method?

> 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).

Mhh this convinces me that we need transformation methods between the
core position space to a "sane/normal" one (where y==0 is north). The
latter can be used in mapgen and in normalize_map_pos.

> > > 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).

The current savegames are human readable. Do we want to continue this? 
This will rule out 2) and 3#

> > 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?

No.

> Neither do I.

Quick question: why do we do this then?

> 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.

Another point: before isometric maps are included it would be nice to
first get arbitrary wrapping of the current system. You may can
include this in your reflectings.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "Make it idiot-proof and someone will make a better idiot."