[Freeciv-Dev] Re: normalize_map_pos and invalid map positions

[Jason Short <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

Per I. Mathisen wrote:
> On Tue, 13 Aug 2002, Ross W. Wetmore wrote:
>
> > Normalize_map_pos() is the swiss army knife for coordinate testing.
> >
> > It returns false if the coordinate is unreal - generally terminal error.
> >
> > It returns true and a valid normalized coordinate pair otherwise. This
> > may involve normalizing the coordinates in the process but that is always
> > possible if they are real.
>
> > This should be used at all portal points, i.e. places where you should
> > check for unreal coordinates. This includes source creation, network
> > input points or any place where one might want to check for corruption
> > of any sort, or even just a change in the definition of "normalized".
> >
> > In some cases it is better to use unnormalized or differently normalized
> > coordinates for a given operation. In this case one would normalize before
> > handing off such coordinates to more picky code outside of this module,
> > or do it on input to any module that might receive such coordinates.
>
> > This should always be the case. It doesn't hurt to fix things up and
> > continue in any situation, and a few judiciously placed checks like
> > this will be useful to catch the unreal cases which are terminal.
>
> > So even the big reason for normalizing everywhere is not really that
> > sensible with truly generalized topologies.
>
> So what you are suggesting is that normalize_map_pos() is used at the
> lowest level where coordinates are generated, changed or received from the
> client, and that the the higher level functions receive properly
> normalized map positions which are checked with is_normal_map_pos().
>
> Right?
That is certainly not what Ross is saying.

What you describe is what Raimar and I have been doing, and Ross is 
opposed to it.  Currently coordinates are normalized on creation, and so 
only normal coordinates should be passed around.  Here and there 
throughout the code CHECK_MAP_POS(x,y) is called, which is basically 
assert(is_normal_map_pos(x,y)).
This has the advantage that it is substantially faster when FreeCiv is 
compiled without debugging (normalize_map_pos and is_normal_map_pos have 
a high overhead), while it helps to catch problem cases where non-normal 
positions are passed around (because the assertion is there, err, except 
that now it's only active in DEBUG, which nobody uses...a problem). 
Ross's point is that when you compile with NDEBUG, although the code is 
faster it is less safe - if there *is* an error, it will not be dealt 
with and will result in a bad memory access or some other problem.  This 
could easily be handled if we just called normalize_map_pos on the 
coordinates again...but then we would give up the speed advantage (which 
Raimar is a big fan of).
So what it comes down to is three different concerns: speed, safety, and 
error-catching.  And it seems everyone values each concern differently 
(I put the most emphasis on error-catching).
> Obviously we should not use normalize_map_pos() in high level code that
> should receive normalized coordinates, since it could receive real,
> non-normalized but completely wrong coordinates, and passing
> normalize_map_pos() over them would make them even more wrong by
> normalizing them, and it would return TRUE, suggesting that coordinates
> are okay.
Usually these coordinates *are* okay - they just missed the 
normalization step.  This is an error in the calling code, but need not 
be fatal.
I once proposed changing CHECK_MAP_POS along these lines:

  #define CHECK_MAP_POS(x,y)                     \
  do {                                           \
    bool is_real = normalize_map_pos(&(x),&(y)); \
    assert(is_real);                             \
  } while(0)

which addresses the problem nicely, IMO.  In this case we give up speed, 
but get both error checking and safe behavior in NDEBUG mode.  (Note 
there's a problem in that not all CHECK_MAP_POS calls currently pass 
valid targets for the & operator.)
> > > example: a unit at (0,0) is ordered to move "northwest" by:
> > > a) the server (by proxy of the ai)
> > > b) a remote client.
> > >
> > > What should ideally happen in a general topological framework?
> > If you normalize the position before handing it off and it comes back
> > something other than (-1,-1) you don't need to worry. Since you can
> > choose the soft condition of normalization in any way you like, this
> > should almost always work - I can't think of a case where it wouldn't.
>
> Uhm, shouldn't the dir function that returns the coordinate for northwest
> from (0, 0) return a _normalized_ map position? Then both coordinates
> should be >= 0, no?
In theory the set of "normal" positions could include (-1,-1).  I think 
we all agree that it should not, though.
> > If your topology wants to define the value (-1,-1) as both real and
> > normal
>
> Now you lost me again. I thought a normalized map position by definition
> would be "unwrapped" and always refer to a square map (x1 >= 0, y1 >= 0)
> to (x2 > x1, y2 > y1) in size.
>
> But a negative map value can be normal?
Currently the "normal set" (note the misleading term) is all values in 
[0..map.xsize)x[0..map.ysize).  If we were to make a map that wrapped in 
different directions, this would still be the normal set.
But if we make an isometric map (like what SMAC, CivIII, and maybe CivII 
use), then things get more complicated.  From the point of view of an 
isometric-view client, this map will look like
 X X X X X
  X X X X
 X X X X X
  X X X X
 X X X X X

but if you think about it in standard coordinates, the shape is actually

     X
    XXX
   XXXXX
  XXXXX
 XXXXX
  XXX
   X

which does not match the [0..X)x[0..Y) paradigm.  In fact, dealing with 
things in this way is incredibly unwieldy - for instance if the map 
wraps direction we get weird vectors of wrapping.
Note that we can convert easily between the two forms - it's just a 
matter of a pi/4 or -pi/4 rotation and a scaling.  The first form 
("isometric" coordinates; I call them "native") is much easier to deal 
with; wrapping is done easily along the axes, etc.
Ross came up with yet another representation.  If you scale the 
isometric coordinates down, you can get what he calls "native" 
coordinates (I call them "compressed").  So the set then becomes
 XXXXX
 XXXX
 XXXXX
 XXXX
 XXXXX

which is just as easy to work with for most things, and also makes data 
accesses easier (i.e. the X and Y values can be used as indices into an 
array of tiles).
Most of this can be seen in action in Ross's corecleanups.  He has a 
clean system of converting from one type of coordinate to another - 
map_to_native_pos, native_to_map_pos, etc.  But when these things try to 
make their way into CVS, we always run into minor stumbling blocks that 
hold things up indefinitely (like the speed vs safety vs error-catching 
issue above).
jason