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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Thu, Aug 15, 2002 at 11:43:39AM -0500, Jason Short wrote:
> 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).

We didn't catch a single error with CHECK_MAP_POS. So it was
disabled. However I have no problem to reenabling it if we work heavy
on the map.

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

Yes. Any normal position is a regular position (see
common/map.h:regular_map_pos_is_normal). So we have

real positions are a (proper) subset of all map positions
  are equal if wrapping in both axises is enabled
regualr positions are a (proper) subset of real positions
  are equal if no wrapping is enabled
normal positions are a (proper) subset of regualr positions
  are equal in "classic" (non-iso) maps

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

And this is the part where I lost Jason and Ross the last time. In
addition to the three sets of map positions we now get at least two
representations.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "How about the new language C&? No, that's not 'c ampersand', 'c reference', 
  'reference to c' or 'c and'. It's pronounced 'campersand', to confuse the 
  hell out of people who are unfamiliar with it, and it will, of course, 
  have no pointers."
    -- Xazziri in comp.lang.c++ about C#