Complete.Org: Mailing Lists: Archives: freeciv-dev: August 2002:
[Freeciv-Dev] Re: normalize_map_pos and invalid map positions

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

[Top] [All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
To: freeciv-dev@xxxxxxxxxxx
Subject: [Freeciv-Dev] Re: normalize_map_pos and invalid map positions
From: Jason Short <jdorje@xxxxxxxxxxxxxxxxxxxxx>
Date: Thu, 15 Aug 2002 11:43:39 -0500

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


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

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


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


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


[Prev in Thread] Current Thread [Next in Thread]