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

[Jason Dorje Short <vze2zq63@xxxxxxxxxxx>]

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.

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

  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.

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

jason