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

["Ross W. Wetmore" <rwetmore@xxxxxxxxxxxx>]

At 01:25 PM 02/08/09 -0500, Mike Kaufman wrote:
>On Fri, Aug 09, 2002 at 06:04:36PM +0000, Per I. Mathisen wrote:
>> Ok, this is probably a stupid question, but anyway.
>> 
>> I take it the point of normalize_map_pos is to ensure the given map
>> positions don't point to an illegal point on the map that would case an
>> error.

What ...

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.

If coded properly, there is no additional performance penalty to do all
this rather than just check for some part of the condition.

Why ...

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.

Also, older clients may legitimately send unnormalized coordinates.
Since they can be normalized in passing and the server continue
merrily on its way, there is no need for any further action such as
crashing the game.

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.

Forward compatibility ...

Also, there is no guarantee that a given module or client will use the 
same normal definition as the server. This is especially true when there
are generalized topologies, and code or clients may wish to view the 
map from a more convenient perspective from their standpoint. Thus any
time you cross such logical boundaries you should renormalize for the
local module environment. Jason and Raimar are still in the "one size
fits all" mode and determined their religious choice should be "THE ONE".
It would be a grave mistake to let these constraints be built into the
code base as absolute restrictions - and moreso as no constraint is even
needed.

Why normalized ...

Note the only reason for insisting on "normalized" coordinates is so
memory accesses do not generate memory faults. But if you are storing
topological data in different ways for different topologies, then 
having the standard in memory working coordinates normalized doesn't
really help that much as they still need to be transformed to native
coordinates to do the memory access. It is the case that almost all 
in memory algorithms are indelibly based on a rectangular cartesian
coordinate system, but the storage of data need not be done this way
and need not be constrained by the limitations of cartesian coordinates.
Jason's generalized topologies has not progressed this far, but the
corecleanups version is not dependent on internal coordinates for 
storage.

So even the big reason for normalizing everywhere is not really that
sensible with truly generalized topologies.

>> However, sometimes, as with goto_dest_?, I believe the correct thing to do
>> is to make the positions illegal, so that they don't get used and if they
>> get used, an error is generated so that the problem can be fixed.
>> 
>> So what would be an illegal map position? (-1, -1)?

This is used as both an illegal position, and a marker or fill value
in places that don't use coordinates but need to pad the space. As in
vnotify_conn_ex, you don't know if this is a coordinate or not except
in context. That is why Jason's fix is a bug - he is first assuming
the values always represent coordinates, then applying an unnecessary
constraint condition and crashing the server when it doesn't live up
to his expectations. Sometimes they are just fill bits - some day he 
will hopefully come to accept this fact of life.

(-1,-1) must always be dealt with in context by code that understands
whether this is a coordinate or not. Backwards compatibility with older
clients and existing code means you cannot change this value yet. Yet
generally means two or more releases, and a complete (not partial) fix.

Your question is correct, in that you need to define a new marker value
and change the code everywhere or use (-1,-1). You also need to build in
any backwards compatible checks for (-1,-1) and deal with it in context
if you opt for a new value, which may have the same constraints.
Since you are going to do the latter anyway, just make sure any code that
uses coordinates (-1,-1) flags or tests the value as real within its
contextual understanding ... somehow.

So far, code handles this correctly. The fix to restore the original
behaviour to vnotify_conn_ex() will retain this characteristic. It
traps and passes (-1,-1) through to code that can deal with it in
proper context. It also checks for unreal coordinates and flags them 
as such. Finally it normalizes any real coordinates to the working
server definition of normal which it used to do several routines
lower, but doesn't now that code has been "fixed" in the earlier
purges.

>urk, -1,-1 is (will be) a valid position. (at least that's my
>understanding of the whole thing...)
>The solution should be to add an illegal position bit?

If you define it as valid in some future context, then it needs to be 
flagged in some way, or you need to be sure that it will be passed 
through without triggering any error conditions along its particular 
codepaths. This is the work Jason is trying to avoid, but as usual 
avoiding it involves more work in the end.

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

If your topology wants to define the value (-1,-1) as both real and
normal, then you need to make sure that error checks for this value
understand this and do the correct thing. This is a hard problem, so
the best solution is to define your topology otherwise as above.

Note, if you are going to reserve one point in the standard cartesian
coordinate space (-1,-1) has a lot going for it. Avoiding this one
point is not that big a deal.

>Jason, Ross, could we have a consensus on this particular point, devoid of
>any other considerations? If other considerations, what do they need to be?

1) Normalization is a "soft" condition that can be defined locally
   within a module. Different modules can have different concepts of
   normalization. Normalize_map_pos() should be used at portal points
   between such logical regimes to trap errors and do any conversions.

2) (-1,-1) is a "special" value in the code. It *cannot* be assumed to 
   be a coordinate except in context. Changing this is both hard and
   probably not worthwhile given 1). Finding a replacement is equally
   dubious.

>-mike
>
>> 
>> Yeah, I guess this question shows just how well I've been following the
>> gen topology discussion...
>> 
>> Yours
>> Per

Cheers,
RossW
=====