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

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Fri, Oct 05, 2001 at 04:18:18AM -0400, Jason Dorje Short wrote:
> Raimar Falke wrote:
> > 
> > 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.
> 
> Correct, but they may not be the same as map.xsize/map.ysize.
> 
> I think if we put restrictions on the form of the isometric graph
> (always wrappable in both dimensions, etc) then we can use
> map.xsize/map.ysize as the options to set the map size.  The problem is
> most users won't think of the graph like this:
> 
>   a
>  bcd
> efghi
>  jkln
>   mo
> 
> but instead like this
> 
> a d i
>  c h n
> b g l
>  f k o
> e j m
> 
> So it would be easier to have the interface treat this as a 6x5 map, and
> make the conversion internal.  This is a difficult interface question.

The above map has 15 tiles. This is a 3x5 map to me.

> > > > > 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?
> 
> What I've been doing was using an IS_ARCTIC macro so a check can be done
> within a whole_map_iterate.  How to implement IS_ARCTIC is another
> question - I'm not sure.
> 
> > > > > 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.
> 
> Some of the same places, but the core code should remain the same.  For
> instance
> 
> #define IS_ARCTIC(x, y) (y<map.ysize/10)
> 
>   whole_map_iterate(x, y) {
>     if (!IS_ARCTIC(x, y)) continue;
>     ...
>   whole_map_iterate_end;
> 
> It will be necessary later to fix IS_ARCTIC, but the rest of the code
> should remain the same.  The same is true of code that uses
> normalize_map_pos, is_normal, is_real, nearest_real, whole_map_iterate,
> etc.  My goal is to get the core code right the first time, while
> leaving code in map.[ch] that deals with the topology itself until later
> (when we actually implement new topologies).
> 
> > > > > > 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);
> > > }
> 
> Note the use of is_normal_map_pos within the iteration.

I overlook it.

> In the case of
> an isometric map, it will iterate over the entire surrounding rectangle,
> but only real positions within that rectangle are treated regularly; the
> others are given dummy values.  This makes the savegame format remain

So this means that y_map_iterate and x_map_iterate won't change under
an isometric map? IMHO you have NOW to define what the semantic of
map.[xy]size are. Either 

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

will always (under all possible topologies) catch all tiles or not. If
it does that the is_normal_map_pos check is necessary and the
[xy]_map_iterate is decoration/cleanup.

>   a
>  bcd
> efghi
>  jkln
>   mo
> 
> Rather than
> 
> a
> bcd
> efghi
> jkln
> mo
> 
> Which is easier to read and also makes indexing into the array easier
> (since we can just use X values).  Upon loading, the exact check is used
> to skip over the unreal values (there we can use a modified macro that
> does this automatically as you suggest).  Sorry if this sounds
> complicated; to me it's perfectly clear.  There are several different
> ways the game can be saved (#1, #2, and #3 from your previous list), and
> I don't really care which one is used - but I think this one is easiest.
> 
> > > > How complex would the transformation methods [be]?
> > >
> > > 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?!
> 
> Kind of...except the transformation does not, and can not, result in
> integer values.  Also this transformation *still* assumes that the map
> is rectangular or rotated-rectangular, which is a BAD thing.
> 
> > > > 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 would be slower than the current method.  I have no idea how much. 
> Nobody's forcing you to use it, though.
> 
> > > 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.
> 
> I disagree.  Doing transformations to integer values is not possible,
> and tracking calculations with floats is highly undesired.  Restricting
> ourselves to rectangular or rotated-rectangular maps is undesired (IMO)
> and unnecessary.  Don't be overly concerned by the speed difference;
> that is not the most important thing here.
> 
> Finally, the concepts of "north" and "polar" are themselves
> topology-dependent.  In a taurus world we may have no polar regions; in
> a mobius strip world the concept of "north" versus "south" has no
> meaning (the two are synonymous or interchangable; this presents
> problems but is not impossible).  I would MUCH rather do this by having
> functions/macros like IS_POLAR and such; ignoring the idea of north
> entirely.

Lets forget the very weird other types out and concentrate on "simple"
isometric maps. IMHO you can define a "distance from the
north-wrapping border". This can return an integer. Depending on the
definition of map.ysize the value range of this method may be
0..map.ysize or 0..2*map.ysize.

> > > > 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#
> 
> Right.  Actually I think (3) is not only the most human-readable but
> also the easiest to do (since we can use the X value directly as the
> index into the array).  But I either (3) or (4 [what you call 3#]) will
> work as far as I'm concerned.
> 
> > > > 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?
> 
> Because I recently played Alpha Centauri, and I *really* liked the
> isometric tileset.  In part because it was much prettier, but also
> because on an isometric map it looks really good.  There's not much I
> can do about the first, but oddly enough I had already started embarking
> down fixing the second :-).
> 
> > > 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.
> 
> Yes, that is a desirable intermediate step.  However, my goal is to do
> the cleanups first; then we should be able to add new topologies at
> will.  At some point a simple patch that allows multiple wrap methods
> may become desirable (Ross's patch already does this, but it does so in
> the completely wrong way).
> 
> 
> One other thing I thought of (I hope I didn't say this before, with all
> the conversation I'm not sure how many times I've repeated each bit of
> explanation :-): none of these changes are directly leading toward
> having isometric maps; there are other possible goals/intermediate
> steps.  Again the example of a regular rectangular map:
> 
> X X X X X
> X X X   X
> X X X X X
> X X X X X
> 

> This map has a "hole" in it.  This hole is an invalid/unreal coordinate
> pair; the intent is to represent impassable mountains or something like
> that (I'm not too keen on the idea, but some people thought it was
> nifty).  However, something as simple as this is pretty much impossible
> under our current system.  map_adjust_[xy] will not work with this
> system since they assume regular wrapping (you can only tell when you're
> on the empty tile by considering both X and Y values), and
> whole_map_iterate (along with any manual iterations) will blithely
> iterate straight over the empty tile.  The corrections I'm proposing
> will fix things so that these assumptions are not made.

This is a lame excuse. There are solutions possible which require less
work. I'm just waiting for somebody proposing a worm hole.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "We've all heard that a million monkeys banging on a million typewriters
  will eventually reproduce the entire works of Shakespeare.
  Now, thanks to the Internet, we know this is not true."