[Freeciv-Dev] Re: topology RFC (again)

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

At 01:22 AM 01/11/07 -0500, Jason Dorje Short wrote:
>"Ross W. Wetmore" wrote:
>> 
>> Some pseudo code examples to help explain key points once again.
>> i.e. the arithmetic to do isometric (un)normalizations :-?
>> 
>> Cheers,
>> RossW
>> =====
>> 
>> At 04:45 PM 01/11/02 -0500, Jason Dorje Short wrote:
>> >"Ross W. Wetmore" wrote:
[...]
>> >No.  unnormalize_map_pos(&x, &y, 0, 0) is not the same thing as
>> >normalize_map_pos(0, 0).  Normalize map_pos wraps (x, y) into the normal
>> >set, which need not correspond to any particular representative set that
>> >unnormalize_map_pos wraps into.
>> 
>> Jason, THE normal set N(0,0) is something one designates in the manner
>> needed. Once one has defined it, say to reference real memory in some
>> appropriate manner, this is what normalize_map_pos() is written to
>> return. unnormalize_map_pos() given the appropriate offset values will
>> clearly return the offsets in this set if one chooses.
>
>So you are saying normalize_map_pos(&x, &y) is or is not the equivalent
>of unnormalize_map_pos(&x, &y, 0, 0)?  If the latter, I agree.  If the
>former, then you are wrong.  Only in specialized cases (a
>flat-rectangular topology _and_ a flat-rectangular mapview or an
>iso-rectangular topology _and_ an iso-rectangular mapview) will that be
>the case.  When you compare the two, it makes me think you are confusing
>these two concepts (topology and mapview), even though that may not
>actually be the case.

Ok, here's how my interpretation goes ...

You can unnormalize into a variety of N-spaces (N(*,*) or canonical or
whatever - but not representative :-). They can be of different shapes
or at different offsets, though only rectangular ones are really of 
interest to the current stage of development. One of these spaces is 
THE normalized space N(0,0) (or whatever). It is THE one because you 
pick it to be - not for any intrinsic property. If you store your map
coordinates in a rectangular array, you choose it to be this array. If
you decide to store your map coordinates in a related parallelogram
object, then you would define this as THE set. If you pick a rectangle
oriented at pi/4 to store your map data, you would probably want this
to be THE normalized set. Unnormalizing is just normalizing to find the
equivalent position in an arbitrary such set. The unnormalize code is 
just a generalization of normalize_map_pos() to a slightly wider set of 
shapes/offsets. It is by no means a totally general unnormalize, but it
is good enough for now. 

The "un" in unnormalize is really just italics or boldness to highlight 
when I mean this more general form than just the plain normalize that 
unless explicitly clarified keeps its specific semantics.

Unnormalizing into THE set is completely equivalent to our generic
definition of normalizing.

There are no topology limitations of the sort you set above, although
the practical implementation of normalizing operations can be complex
in non-rectangular coordinates. In the most general case, I think you
could probably pick your set as a series of disjoint arbitrary points 
that satisfy the conditions that they are a complete set with no 
equivalent positions. Equivalent positions needs some sort of 
relationship or operation to define it of which linear wrapping is one 
example.

>As an aside, can we please stop calling it N(0, 0)?  There is no "other"
>N, so lets just call it THE normal set N. 

No, it is more useful to think of "normal" in a slightly more generic
way, and understand that when you don't indicate context it applies to
one specific set of points that has been designated special. This is
THE normal set, or N(0,0).

It is actually very helpfull to think of a "normal" set that lies at
the offset of the GUI window origin with a shape that is aligned with
the GUI axes. You (un)normalize map positions into this set to get
offsets that are useful for finding corresponding GUI positions. 

This is not really any more special than going the other way to a
"normal" set that corresponds to the memory allocations which we
have been calling THE normal set. But we do go the other way more
often and the memory tends to be fixed during execution, so this
is as good a place to choose as homebase as any other. Humans tend
to like to have that orientation point :-).

>
>> Note as well, this still defines a very practical unnormalization that
>> is useful for accessing memory or describing the full iso GUI in its
>> standard form or any subset of this (after appropriate transformations).
>> This is what the current rectangular GUI gives, so it is perfectly
>> adequate for isometric play. It also guarantees tiles are only shown
>> once. We'll deal with your odd GUI tastes in a later discussion.
>
>The math you provide is very pretty.  I like it a lot, and will speedily
>use it in the next iteration of the general-topologies patch.  I have
>only a few concerns:

Be careful. It is pseudo-code. I probably didn't get the offset
calculation right, i.e. do you shift to a natural origin then do the
wrapping tests - the result is an offset to which you need to add
the origin vector to recover map coordinates, or do you apply the
wrapping operations in place at the {x0,y0} location - this gives
map coordiantes to which you want to subtract {x0,y0} to get offsets.

For simple rectangles, the former is easiest, but I think the code
actually does the second and thus the offset fix at the end is wrong
or should be a subtraction if you want to return offsets rather than
map coordinates.

It needs to be checked and debugged anyway :-)

>- This math will not cover all topologies, only linearly-wrapping ones. 
>So, although it's a great mathematical system to use for the topology
>backend we should avoid using it outside of there.  This information
>should not be saved in the savegame or sent server->client, but should
>be assembled in topology_init() and used internally by the topology.

I assume all game information should be transmitted or saved in game
coordinates, moreover the coordinates should be normalized, i.e. in THE
normalized set.

You need to save and transmit the map topology type. Anyone who receives
this type index needs to be able to get/understand the characteristics
like the wrap vectors associated with the type. Topology operations are
game operations.

>- How will you account for the width/height limits placed on the
>wrapping by normalize_map_pos_[iso|rect]?  Do you still believe these
>are unnecessary, or are they what you mean by "my odd GUI tastes"?

The candy cane email explains what trouble your odd GUI tastes for
arbitrary target shapes as opposed to arbitrary "normal" sets will get
you into.

If you decide what a full map image means to the GUI, this is the shape
you want to use. It is fixed as part of the map generation, and the
context information can be picked up just like map.xsize, map.ysize.
You don't want to pass this in as a general argument. For one reason
it might not be a simple width/height pair.

On the otherhand, you do want to pass {x0,y0} explictly, as this is
a variable offset or origin association for the specific normalization
instance. The GUI window can float to different offsets.

>- Nit: your numbers for mapiso are off.  map.xsize and map.ysize do not
>correspond directly to the wrapping vectors.  Rather, these should use
>map.topology.usize/map.topology.vsize (or whatever you choose to call
>them).  usize/vsize can also be used to compute xsize/ysize, but are
>definitely distinct from them.

This is another one of those interpretation things. 

The game originally used these values to define the map dimensions, 
and we later understand them as defining the "normal" space. This is
all I need to define the normal map dimensions without changing any of 
the existing concepts or adding any new ones.

Note, the memory you need to store true iso-rectangular maps is a 
square array.

If I find that memory is now a (map.xsize+map.ysize) square to hold
this map, then there will be a need to change the code that deals
with transforming to external memory representations. But I don't see 
any need to change the fundamental game mechanics and definitions just 
to keep some extended memory subset in an older form. Note you will 
still have to deal with memory and external representation changes 
when going to the more general system.

Plus, your change to invent regular and try and preserve some of this 
code results in some incredibly poor algorithmic choices. If you just
leave "normal" definitions alone or in as much of a backwards compatible
state as possible, things will go much smoother and probably more
efficiently.

>- Second nit: struct topo should have fields uwrap and vwrap, not xwrap
>and ywrap.

Maybe. But note they really are rectangular orthogonal wrap vectors, 
even if the rectangle is rotated :-).

It might be fun to see what kind of trouble one gets into by choosing
vectors/axes that were not orthogonal. So far I have carefully tried
not to think about it as a sanity preserving measure.

If the general case is possible, you are right that we should go there
directly in the naming convention.

><snip math>
>
>Here's another idea: can you think of a way to easily extend this math
>to be useful in a "filter" system where we take some of the positions
>within the "normal" set and define them as unreal? 

First, it might be useful to define unreal positions as included in 
the normal set equivalence relations. This means that if you run into 
any equivalent unreal position you can stop. This disallows complications 
like wrapping east to a real tile and west to an unreal one.

For general spotty unreal positions, the filter layer is probably
most easily implemented by is_real_tile() or its renamed successor
as a List lookup where "List" can be implemented as an array, linked
list or hashmap depending on the performance characteristics desired.
Presumably you would do any "quick" algorithmic test first then the
more complex filter ones. For an ellipse, my guess is a normal map
array with a true/false, or real/border/unreal value would be useful.

There is a chicken and egg problem here, in that is_real_tile will
probably need to do this type of lookup realness check in normal 
coordinates. Thus you need _normalize_map_pos() that does the 
algorithm when algorithmic realness is guaranteed, and _is_real_tile0() 
plus _is_real_tile1() that do the algorithmic and filter operations.
The user callable functions would then call these in various orders.
I suspect the user callable is_real_tile() and normalize_map_pos()
become equivalent in all but returning updated coordinates at this
point, as there isn't that much advantage to a fast but incomplete 
algorithmic _is_real_tile0().

If you have several algorithmic or filter operations, then you need
to run down the list of functions in a before or after normalized
state.

There are also some special case flavours that might be useful. For
example, one might define a "realness" map that consisted of a 
multi-map image. Each image would carry some "state" about how
one got there, or what was allowed, i.e. beyond mere position.
Filter algorithms would check/use this state. This would give you
one-way directions.

>  The problem in this
>case is not the wrapping (which works the same), but the problem of
>finding the nearest_normal_map_pos().  nearest_normal_map_pos is very
>easy in the standard linear case (the math will be very similar to what
>you've proposed for wrapping), but if we declare that some positions
>within the "normal" region are unreal then it becomes very difficult
>(see the ellipse topology in the general-topologies patch).  This
>problem would really go away if we dropped the concept of
>nearest_normal_map_pos/nearest_real_tile. 

Yes, by all means do this. Nearest_real_pos() in these cases is pure
hack that should be fixed by correct programming :-).

> The only code that
>legitimately needs it is GUI code that centers the map view (the
>tilespec code could be handled without nearest_normal_map_pos, since
>each unreal position will be guaranteed to be adjacent to a real
>position).  Can you think of any other way to handle this problem?

I don't understand why these cases "need" this. Until this example
is clearer, I still think it falls under the programming error
category.

>Finally, I'm getting really tired of these names:
>unnormalize_map[iso|rect]_pos and normalize_map_pos_[iso|rect] are
>equally misleading and inaccurate IMO.  How about making a single
>function find_representative_map_pos(&x, &y, context), where (x, y) is
>the position to be wrapped and context defines the representative set we
>want to wrap it into (i.e. x0, y0, width, height, iso, etc. as
>necessary)?

I'm being very consistent in using normalize_<coord>_pos, with the "un"
prefix for the generalized flavour mostly to highlight the new use until
it settles into some steady state. Each coord-type has its own special
is_real or normalization operations, wrapping or clipping, and default 
context, so I don't need extra labels for this. I would add them if I 
thought there was a need in teaching people that such implementation
details were different and this need to be stressed. But sofar, map, 
isomap, citymap and gui seem to be understood this way.

>jason

Cheers,
RossW
=====