[Freeciv-Dev] Re: (PR#3936) introducing native coordinates

[Ross Wetmore <rwetmore@xxxxxxxxxxxx>]

Raimar Falke wrote:
> On Thu, Apr 24, 2003 at 09:00:59AM -0400, Ross Wetmore wrote:
> > Raimar Falke wrote:
> > > On Wed, Apr 23, 2003 at 05:50:43PM -0500, Jason Dorje Short wrote:
> > > > Raimar Falke wrote:
> > [...]
> > > > Using "map coordinates" rather than "native coordinates" as standard is 
> > > > fastest, since the vast, vast, vast majority of operations are done on 
> > > > map coordinates.
> > > I disagree here. Every tile access needs the compact form. The same is
> > > true for normalize_map_pos and is_normal_map_pos. But without testing
> > > we won't find out.
> > Wrong on aeveral counts.
> > Tile accesses are done in indexed coordinates - memory is linear.
> Yes. But the indexed form can easily (and is derived in the Jason's
> gen_topo patch) derived from the compact form:
>
> +int map_pos_to_index(int map_x, int map_y)
> +{
> +  int nat_x, nat_y;
> +
> +  CHECK_MAP_POS(map_x, map_y);
> +  map_to_native_pos(&nat_x, &nat_y, map_x, map_y);
> +  return nat_x + nat_y * map.xsize;
> +}
This is an implementation detail that may or may not be changed in the
future with no impact to the API.

The fact that something is hidden in the implementation does not make
it a requirement at the interface level. Good programmers always maintain
an appropriate separation between the two.

It is demonstrably *not* true that tile access *needs* the compact form
and so keeping this out of the interface and conceptual description is
the only smart thing to do.

> > All game logic is handled in standard/internal coordinates including
> > things like the local iterators. The Freeciv foundations are based on
> > a standard map grid and changing this is a lot of work to make things
> > less efficient and much more complex in a number of cases.
> Most of the freeciv code only copies coordinates around. Some code
> create new coordinates (iterators, MAPSTEP) and some code access
> tiles. The question is which part of the code has a bigger impact on
> the runtime.
You still don't appear to appreciate the underlying reality in Freeciv.

The standard map coordinate grid is *fundamental* to Freeciv at this
time. It is not just the system or protocol for exchanging coordinates.

Most operations, especially in inner loop code, are local, and the
coordinate system best suited for local operations is the one that is
fundamental to the operations. DIR_DX/Y in native coordinates is a
mess, for instance which means MAPSTEP is a mess.

[...]
> I have abandoned the idea to write my own implementation since it
> would similar to Jason gen_topo patch. However this patch has some
> problems:
>  - missing reasons for certain decisions
>  - missing documentation (I wrote this now)
These are certainly valid areas for review comment. Is there a list of
such problem areas, or have you an appropriately commented review that
outlines them?

I also think that different points of view can be very useful in catching
issues, with the caveat that the seriousness or validity of the issue
raised may not always be understood by the person raising it. Sometimes
changes are not warranted just because they are suggested ...

>  - some slightly wrong code (native_to_map_pos doesn't return y=0)
The current patch uses an identity transformation, no? What is the problem
referred to here?

>  - code (unnormalize_map_pos) that hard to understand. I would say too
>  hard.
It may be hard for some, but lots of the freeciv code is hard to understand
especially on first read and some elements are intrinsically difficult which
is not to say they should not be there.

As a primer ...

In this case the algorithm goes through a number of very simple and easy to
understand steps that are well commented. One could write a treatise on all
aspects and implicaitions of every line, but this is probably less useful
than the current highlights and guidelines.

There is only one step that is conceptually difficult, but if you look closely
at the code, you will see that it is not much more than a vector implementation
of the normalize_map_pos() while loops that have been in Freeciv for a dogs age.

These only occur when the native and standard wrap axes are not aligned, and
thus the normalized set mappings are not simple one-to-one rectangles.

If you understood the scalar form for wrapping, then you should be able to
follow the vector one here.

Personally, I found it instructive to understand the process here visually, and
thus drawing graphs and doing a geometric mapping operation on paper helped me
to verify all the subtleties of the code conditions. The comments tell you how
to do this and the result to look for in the simple 1-D wrapping case (the
normal set rectangle gets mapped to a parallelogram to remain within the 
positive
region of the target axes) as well as the full 2-D one.

Geometrically, every point (above/)below a diagonal line through the origin is
wrapped to the other end of the rectangle to create a parellelogram in the 
simple
case. Points below that diagonal line would be negative in the output coordinate
system. This is a vector operation (bounded by a diagonal line) rather than a
simple single coordinate "+ map.xsize" operation because the transformation is
a linear combination of coordinates rather than an independent function of each
coordinate separately as in the parellel wrap axes case.

For the 2-D case you just need to juggle more mental balls because you wrap in
two diagonal/vector steps, but the logic is the same.

As a final point to note, in the unaligned wrap axes case, either the wrapping
operation or the target conditions will need to be expressed in a vector form.
The current code uses native coordinates to keep wrapping operations simple,
and expresses the loop/target conditions in vector form. This might be done
differently, but almost certainly no more simply.

> If these are addressed I'm for appling this patch.
[...]
>         Raimar
Cheers,
RossW
=====