[Freeciv-Dev] Re: Native Coordinates [Was:[PATCH] Map cleanups (PR#1208)
[Top] [All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
Ross W. Wetmore wrote:
I've taken this to a fresh debate forum.
As a quick backgrounder so we can start from a common set of
(mis)understood terms ...
I am using "standard" or "map" or "game" coordinates to mean the
internal coordinate system used in most of the current code. The
standard set is 2-D rectangular (x,y) based, and is typified by
the trident tileset on the usual world map.
I use "native" coordinates to mean a coordinate system which is
generally rectangular in shape, but whose coordinates are not
necessarily spaced or organized in a standard rectangular grid.
An example is a true isometric map which occupies only even or
odd points (i.e. x+y is even or odd) and is thus diagonal in
spacing. Native isometric coordinates can be mapped to standard
coordinates to give a pi/4 rotated rectangular array.
Compressed native isometric recognizes that every other position
is unoccupied in each row and indexes the row value as x' = x/2.
There is also a shift of 1/2 position in a zigzag pattern that
gets lost when doing this, but the even or oddness of the y or
row value can be used to fix this up in any reverse conversion.
For standard maps, standard and native coordinates are equivalent.
A key property of native coordinates is that no real coordinate
position appears more than once.
Another property that must be built in to any native coordinate
system is that wrapping axes are aligned with the rectangular
coordinate axes.
I am of several minds about native coordinates.
1. Native iso coordinates are great to do topological calculations in
if you have an iso-rectangular topology. But this can be done entirely
internally to the topology code (i.e. without "native coordinates" as a
global concept).
2. Native iso coordinates are worthless for most game tasks. This
isn't an argument against using them, of course, just an argument in
favor of keeping standard coordinates as standard. As long as there's a
well-defined interface for conversions, everything should work out cleanly.
3. Native iso coordinates do allow some game tasks, such as
whole_map_iterate, to be done more cleanly _and_ efficiently. This can
also be achieved by index positions just as effectively, though.
4. Native coordinates for anything other than iso-rectangular and
flat-rectangular topologies have not been proposed, or even considered.
Is it possible for a "native coordinate" set meeting the above
specifications to be created for, say, a wrapping hexagonal map? What
about a flat-rectangular map that has unreal positions within the
regular set (for instance, an ellipse)? What about in the general case?
If we introduce native iso coordinates and then have to fall back on
using a "native regular" bounding box for them, then we haven't gained much.
5. Native coordinates are not a necessity but a convenience.
Everything that has been discussed can be accomplished without them. In
many cases, it can be done just as cleanly and efficiently using index
positions.
6. Finally, I see little reason why native coordinates can't be
introduced later (after several different topologies are working), and
used as necessary. Most of their uses are local, and so once issue #4
has been resolved it should just be a matter of introducing the
conversion functions and then using the native coordinates on a
case-by-case basis. The only problem I can think of is that to make
savegames use native coordinates will require some
backwards-compatibility hacking.
For me, point #4 is the overriding concern. While Gaute and Ross have
proposed systems to hack in the 8 "standard" topologies (Ross's recent
corecleanups have taken a somewhat more general approach), most of my
changes have been geared toward first separating all topology code.
This then allows any topology within a rather loose set of restrictions.
Typically, savegames, debug output and general memory storage are
best dealt with in native coordinates, with rows and columns in
the usual standard layout. It is specifically for these uses that
the native system is chosen or designed for any given topology.
Yes.
In fact, almost all global game and topology operations are easiest
to handle in this representational form, is_border_tile() for
instance is only slightly more tricky because of the zizag in
native isometric.
Topology operations certainly.
For game operations, it depends on what you mean by "global".
whole_map_iterate could certainly benefit from using native or index
positions, but I'd call this local rather than global.
Conversely, standard map representations are best used for local
game and directional operations like adjacent iteration.
Making sure one has designed the native representation appropriately
and that there is a reasonably efficient coordinate transformation
process allows one to convert to the representation best suited for
given operations on the fly in local codepaths. It means one does not
have to decide up front which is the one-true-representation that has
to do it all, no matter how cumbersome or complicated things get.
There is a competing term "flat" for standard coordinates. Personally
I think all 2-D coordinates are flat, and "Flat-Earth" is a general
term for a non-wrapping topology, so this is confusing and overloaded.
But we should add "flat" to "standard" or "map" or "game" as an alternate
designation until it's use dies out :-).
Well, my interpretation is like this:
* native: whatever system is most convenient for the current topology
* iso: a native iso-rectangular system
* flat: the opposite of iso, i.e. a native flat-rectangular system
* standard / game / map: whatever the game uses as its main coordinate
system. I much prefer "map" to game or standard, since that's what all
the functions call it.
* index: a single integer identifier in the range [0..n]. This is much
easier to implement if we allow values within this range to be invalid,
i.e. not identified with a unique map position.
I'm willing to give up flat in favor of map, but not in favor of
standard or game. Currently flat == map == native. In the foreseeable
future we will have map == flat, but this will not necessarily always be
the case.
Regular is a term that is used to describe a rectangular bounding box
in standard coordinates that encloses a complete normal set such as a
pi/4 rotated true isometric rectangle.
While we're on the topic, just to rehash:
- normal: a representative set chosen by us. It has no significance
other than what we give it, but using it makes calculations and
debugging much easier.
- real. Duh.
- regular: a convenient bounding box for the normal set.
Currently we talk about "normal map positions" and "regular map
positions", but if we introduce native positions and can't figure out
how to work different topologies we may end up with regular native
positions, and that would IMO suck.
For standard maps, standard and regular coordinates are equivalent.
For a 100 x 2 isometric map, this would be a 102 x 102 square.
Yep. Anyone who wants to use a 100x2 isometric map is doomed to a 98%
waste of memory if we use regular positions for storing map data. This
was deemed acceptable (Tony, Raimar, and I all agreed IIRC), mostly
because nobody would play with a 100x2 map.
Typically one iterates over all values of the regular map and selects
the ones that are normal for global operations (<2% in the above case,
but never better than 50%).
Yes. This leads to an inefficient loop, although in most/all cases it
will be unnoticable..
Unfortunately, in wrapping scenarios, there
may be a lot of equivalent coordinate positions in the regular set that
map into the normal subset (over a 50 in a torus world for the given
example, but never less than 2).
So? Just skip those positions. The fact that they're equivalent is
only a problem if you insist on calling normalize_map_pos instead of
is_normal_map_pos, which unfortunately you (Ross) do.
Storing savegames, debug printing etc. are all typically done in the
regular coordinate system because of the rectangular axes. Typically
"unreal" or "duplicate" markers are stored for the extra positions.
For the above isometric world, one would see a diagonal band or rectangle
on printout of 102 lines of 102 elements, and a 5200% increase in savegame
size.
That's a gross exageration. It will result in a 5200% increase in the
map part of the savegame size. In a savegame I just looked at, the map
data accounted for 12% of the savegame. So we'd end up with a
52*12/100=500% increase in savegame size in this pathological case. In
the median case it will account for about a 15% increase.
Note it is always possible to choose a native or a regular system for
any given 2-D topology, and a coordinate system that maps it to the
standard internal game coordinates and back.
It is certainly always possible to choose a regular system. A native
system has more restrictions and may not always be possible.
Choosing a regular system means identifying the extremum points in the
topology in the axial directions.
Choosing a native system means choosing a regular system in a rotated
coordinate frame that is aligned with the topological wrapping axes, or
in one that minimizes the number of unreal tiles if there is no axial
constraint.
As I understand native coordinates, they have normal==regular. How can
this be guaranteed for unusual topologies?
I suspect that it is a property of wrapping axes in 2-D that they must
be orthogonal. Certainly limiting ones topologies by this constraint will
do much to reduce stress on both game designers and players.
A hexagon does not have orthogonal axes. A hexagon would be a good
shape to play on.
If we limit ourselves to axes of wrapping (which both general-topologies
and corecleanups do, unfortunately, since otherwise we must normalize
vectors just like we normalize map positions), then I can think of only
two shapes that will be playable: a rectangle and a hexagon. With these
two shapes we can do any one of (1) rotate them to make iso or some
other form; (2) take a subset of them, i.e. make certain positions
within them unreal; (3) have them wrap in any valid set of the available
directions.
This makes it relatively easy to guarantee a single normal set in native
coordinates. With no wrap possibility, unreal conditions are detected by a
filter operation, which is also not surprisingly the key test condition
for the regular case.
There is another pre-existing format to which we will give the name
"linear" or "vector". It is typically only used in a one-way transformation
handled by map_inx(), though index_to_map_pos() is its reverse.
In standard maps, "standard", "regular", "native" and "linear" usually
map to the same memory locations, and linear is just the vector form of
the array storage system. Linear coordinates are optimal for storage,
and can always be designed to hold exactly one normal set. Printing,
wrapping and other global topology operations are not usually optimal
in linear coordinates.
Nit: regular isn't a different coordinate system; i.e. opposing native
or standard, it's just a different classification of a position. The
only thing bad about it is that it typically leads to an inefficiency in
storage and execution. For an iso-rectangular map this would be about
60%, for a flat-hexagonal map it would be about 30%. The advantage is
that it required minimal changes from the current code to implement; we
just fixed certain constructs that thought they were operating on normal
positions to instead be operating on regular coordinates.
Finally, the corecleanups use native coordinates extensively where they
simplify life. There is no trace of any interfaces with "regular" in them,
but map_std_xsize() and map_std_ysize() return regular dimensions where
the native and standard coordinate axes are not aligned, and various
standard objects are regular sized. There are a number of places where a
native_to_map_pos() transformation has been inserted into code, usually
where a global iteration is handled in native coordinates, but access is
needed to standard map operations. Otherwise code and data structures
outside of the topology functions are relatively untouched.
The generalized-topology alternative uses regular coordinates extensively
rather than native. There is a key data structure that are added to hold
standard coordinates, and a number of changes in code to switch from the
map dimensions that are now subsumed by regular to the topology ones.
Global operations are typically unchanged apart from the is_normal
condition test for the spin checks.
Yes. The changes from normal->regular are already in CVS, and what
remains is just the tough changes: mapgen, GUI, communication, internals.
There are considerable performance and general game flow differences
between the two because of slightly different ways of traversing the
global coordinate space.
Optimizations aside, I seriously doubt there is a considerable
performance in the general case. This is difficult to measure because
of all the optimizations, of course.
And from what I've seen, there is very little game flow difference. All
of the changes corecleanups introduces with native coordinates are
localized; i.e. one section of code converting to native coordinates,
doing some work, and (if necessary) converting back.
Ok, now for the technical debate on fine points :-).
At 01:18 AM 02/01/07 -0800, jdorje@xxxxxxxxxxxxxxxxxxxxx wrote:
Ross W. Wetmore wrote:
c) is_normal_map_pos() -> normalize_map_pos()
Returned values must be normalized, so just do it and return.
do {
*x = myrand(map.xsize);
*y = myrand(map.ysize);
- } while (!is_normal_map_pos(*x, *y));
+ } while (!normalize_map_pos(x, y));
}
This change is incorrect. Consider an iso-rectangular cylinder. In
this case, all positions will be real, and so will be accepted by
normalize_map_pos. However, it is only normal positions that we are
interested in. Changing the code like this will result in some
positions being picked more often than others.
Consider the iso-rectangular cylinder, it has a map.xsize x map.ysize
native coordinate set where all values are treated exactly the same
as the current standard rectangular cylinder.
But what you are missing is the native coordinate conversion because
that isn't in yet. Look at the prototype/corecleanup version.
do {
*x = myrand(map.xsize);
*y = myrand(map.ysize);
native_to_map_pos()&x,&y);
} while (!normalize_map_pos(x, y));
which typically takes one pass per coordinate requested. Native
coordinates are by definition normal as they are currently in the
standard map. By normal one means no real coordinate appears twice.
For now, there is only standard == native coordinates, so this is correct.
This solution takes the tack of properly defining the random selection
to use the native normal space. Other solutions do things in cruder
more expeensive ways but hopefully not in Freeciv.
Again, no.
The current working definition is that everything is in flat
coordinates; no concept of "native" coordinates has yet been introduced.
In flat coordinates, is_normal_map_pos is definitely what we want. We
don't want to find any non-normal position, since that will imbalance
the probability of finding each position.
Non-normal is ambiguous and thus is is clear why such things are useless
to you.
Non-normal is quite well-defined. It is the opposite of normal.
Unreal are trapped by both cases. Real but unnormalized is the only case
in question.
Yes.
In the current standard == regular == native there are no unnormalized
coordinates. It doesn't matter, there is by definition no problem.
Yes.
In a regular system like the isometric band above, I agree you are
not going to get precisely the ratios you want.
Yes. In an iso-rectangular system it would be slightly off (a few
positions would be under or over-represented by a factor of 50%). In a
hexagonal system, about half of the points would be represented once and
the other half twice within the regular set.
But the current code would have a 2% hit rate on returning any valid
coordinate, and the ratio is going to be off by 4 tiles in 10404 which
is the residual amount after filling with 2x100 duplicates. I'm not sure
the added accuracy for returning a random tile is worth it.
Under the pathological case, there would be a 98% inefficiency. Given
the uses to which rand_map_pos is put (mapgen and occasional random
effects), it is most definitely worthwhile to get it right.
Getting rid of an is_normal_map_pos() in itself is worth it, not
counting the performance benefits.
On the otherhand a native system guarantees, like the current standard
case that elements will only appear once. is_real_tile() would be
sufficient check here, but normalize_map_pos() is equally valid, and
has the warm fuzzy benefit of trashing another is_normal_map_pos() use
before it takes root and spreads :-).
But we don't use a native system. rand_map_pos currently uses map
coordinates, and changing it to act as if it were using a native system
before the native system is implemented is a very bad idea.
Once native or index positions are implemented, it will be easy to
optimize the function. Until then, please don't break it.
In native coordinates each position will be guaranteed to be normal. So
in this case the normalize_map_pos is unnecessary; we might as well
stick with is_normal or leave the check out entirely.
Leaving the check out means that filter-realness is not checked. So it
would not work for elliptical coordinates that filter out some of the
rectangular set.
Ahh, I see. native coordinates are guaranteed to be pseudo-normal (new
term :-( ) but not normal.
Given that neither of these systems have been implemented, we should
stick by the method that will work equally well for either of them;
especially since that's the way the function was originally designed and
written.
The best method is one that is good-enough-but-no-better and efficient
at what it does.
Exactly.
As another side note, "native" coordinates are not guaranteed to be flat
or even to exist, so relying on something like this is unsafe in the
general case. It is better to write something of this form:
Native coordinates are guaranteed to be what you design them to be. In
all cases of interest, rectangular and consisting of a single normal set.
There is only a problem if you choose bad native sets.
int index = myrand(map_index_size());
index_to_map_pos(index, *x, *y);
Yes, this is a valid choice with the normalize_map_pos() to filter out
unreal cases which one may have been inserted to make things "easier"
for transformation or some other reason.
even this assumes that a continuous index_to_map_pos is possible, which
may not be feasible (though it's certainl _possible_) under all
topologies, so it might be best to do
int index;
do {
index = myrand(map_index_size());
} while (!index_to_map_pos(index, *x, *y));
I had thought we were tentatively agreed on this index_to_map_pos system...
One could rely on index_to_map_pos() returning a valid condition, and
make it conform to the general transformation function standard, which
up to now I have not really tried to insure. Or rather have explictly
not done to the native and linear transformations, as they are used a
lot and I think generally in a manner where the normalization is already
guaranteed. But one could do a checked and unchecked version.
This would mean adding a normalize_map_pos() as a final step in the
checked case.
In either case the coordinates returned should be either normal or
non-existent.
I actually like it a lot because, while it doesn't really save a lot
in the normalize part, it is only one myrand() call.
But then I'm sort of backwards to the rest of you in considering tight
clean efficient code generally beneficial, rather than something to try
and eradicate as "ugly" or bury in out of the way nested functions :-).
You're certainly the opposite of me if you consider tight, clean, and
efficient code to be synonymous.
[...]
No, it is perfectly safe. Since in fact is_normal_map_pos() just calls
normalize_map_pos() and throws away the values, using an extra function
call in the process, this change is actually more efficient so it is
worth doing this part now.
It is certainly unsafe in my implementation of general-topologies.
That might be a thought on which to ponder ...
It should go without saying that until native coordinates are
implemented they should not be used. This is true of both
general-topologies and of current CVS.
General-topologies is also 70k instead of 800k, and consequently has a
good (well, better) chance of being realized in the foreseeable future.
I have taken the opposite approach from that of corecleanups; i.e.
making the minimum number of changes necessary to implement a more
general system. My opinion is that once the more general system is in
place, it will be much easier to justify optimizations like native
and/or index positions to make calculations easier. This is why I have
implemented neither of them, although at least index positions are
necessary to make the code cleaner and more efficient.
jason
[Freeciv-Dev] Re: [PATCH] Map cleanups (PR#1208), Raimar Falke, 2002/01/07
[Freeciv-Dev] Native Coordinates [Was:[PATCH] Map cleanups (PR#1208), Ross W. Wetmore, 2002/01/07
[Freeciv-Dev] Re: Native Coordinates [Was:[PATCH] Map cleanups (PR#1208),
Jason Short <=
[Freeciv-Dev] Re: Native Coordinates [Was:[PATCH] Map cleanups (PR#1208), Ross W. Wetmore, 2002/01/10
[Freeciv-Dev] Re: Native Coordinates [Was:[PATCH] Map cleanups (PR#1208), Jason Short, 2002/01/10
[Freeciv-Dev] Re: Native Coordinates [Was:[PATCH] Map cleanups (PR#1208), Ross W. Wetmore, 2002/01/10
[Freeciv-Dev] Re: [PATCH] Map cleanups (PR#1208), jdorje, 2002/01/09
[Freeciv-Dev] Re: [PATCH] Map cleanups (PR#1208), jdorje, 2002/01/14
|
|
