[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:
At 03:43 AM 02/01/09 -0500, Jason Short wrote:
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).
It is always nice to have a concept to guide your programming. It is like
a plan before you build. Understanding before you speak.
It simplifies the internal calculations immensely to switch when this
is beneficial instead of slogging through complex mistake prone standard
calculations, or heuristic algorithms that try to mimic them.
Probably, but it depends on the implementation. But this can be done
entirely within map.c (or map_topology.c), and need not be introduced
until we're ready for a topology that needs it.
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.
No. They do not handle savegames or debug output well. They do not
deal with normalization or border computations. All these are 2-D,
while linear coordinates are just good for listing things efficiently.
I was not speaking of savegames or debug output, although I can see I
was unclear.
Debug output is IMO handled much better in flat coordinates because it
is always drawn flat. savegames are slightly easier with native
positions than with index positions, just because they are more
human-readable.
4. Native coordinates for anything other than iso-rectangular and
flat-rectangular topologies have not been proposed, or even considered.
These are part of the "global concept" that you threw out above. There
is also discussion below of how to handle all wrapping cases, and the
rest are filter cases. This covers, your elliptical, hexagonal, "magic"
and others.
Filter cases I understand. This does not cover the hexagonal case
(unless one considers it as a filter and gives up on having native
coordinates for it, in which case one must loosen the definition of
native coordinates - which is my point).
Is it possible for a "native coordinate" set meeting the above
specifications to be created for, say, a wrapping hexagonal map?
To help you along. Wrapping hexagonal maps in 2-D still have the same
orthogonal wrapping axes as all wrapping topologies. The native set is
thus bounded by the wrapping dimensions (map.xsize,map.ysize) and the
coordinates are stored as in the article referenced previously.
Standard coordinates won't be too useful though, as there are 6 and
not 8 directions with a lot of different local algorithms to fix up.
You are being lead astray by the article, which does not talk about
topologies at all, either isometric or hexagonal. It only talks about
tiles, and does a pretty mediocre job at that.
An isometric map has nothing to do with using isometric tiles, nor does
a hexagonal map mean using hexagonal tiles. The map is shaped
hexagonally, and the vectors of wrapping are most definitely not
orthogonal in any standard coordinate system.
What
about a flat-rectangular map that has unreal positions within the
regular set (for instance, an ellipse)?
Your ellipse example is unwrapped. So it is just bounded by a rectangular
(map.xsize,map.ysize) grid with a filter condition to determine realness.
The native and your regular coordinates would be the same (no need to
rotate the axes unless the ellipse is also rotated).
Yes, the filtered case has been covered. Here we give up on achieving a
native coordinate set for the topology, and instead use a native
coordinate set for the surrounding (unfiltered) topology. We thus have
the concept of "regular" native positions, but (1) the bounding set is a
lot more efficient and (2) we still don't have more than one equivalent
real position within the regular set.
However, I don't see how (2) can be achieved for the hexagonal case,
much less the general case.
What about in the general case?
What about it. Since native coordinates can as a first approximation be
taken as your regular bounding box, except one chosen to minimize the
number of unreal tiles by appropriate rotation of the coordinates axes
(to align with the true-iso rectangle wrap axes for instence), they
should be somewhat more flexible and general than your more limited
case that forces a standard to regular constraint.
Yes, but this is just an increase in efficiency, so there is no need to
add them until later.
To put it another way: you have stated that a big advantage of native
coordinates is that no two regular native positions will ever be
equivalent. If this cannot be guaranteed in the general case (AFAICT it
cannot), then a big advantage of native coordinates has gone away. The
most immediate effect of this is that your
is_normal_map_pos->normalize_map_pos change in rand_map_pos is no longer
correct even if we switch to using native coordinates.
Does this mean native coordinates are bad? No. But it means they are
less of a priority, since they can never be a perfect solution.
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.
Except to eliminate all the inefficiencies from unreal tiles which I
know is the backwards way to think about this. Or the simplification
of all the wrapping operations, the savegame bloat, the debug print
understanability. I know this isn't much ...
We all agree that native coordinates work great for the iso case. But
in the hexagonal case they will gain us nothing.
If you wrap, then the wrap dimension size determines the normal set to
guarantee real coordinates appear only once in the native space. Once
you are guaranteed of this, filtering removes any unreal tiles within
these bounds.
The "regular" part of regular native, is the real+unreal native space
that is left when you reduce to a unique normal set. The real subset
of this is what you actually call normal, but I am happy to leave this
regular set as normal, and just worry about real/unreal. The regular
set is what is defined in memory, printed out, put in save games, etc
with some positions marked as unreal.
You've done all this and we can build on it, but you don't really need
to add any "regular" functions or odd flavours of tests, or inefficiencies
to do all this if you do it right.
Well, I think we both agree that all native positions are "regular",
that is, we don't even consider the positions outside of the regular set.
The question is, is this native regular set more useful than the flat
regular set? In the iso case it is, but the general case still has not
been addressed.
normalize_map_pos() and is_real_tile() are all one needs. No is_normal
condition is required for instance.
The difference between your regular and native results from relaxing
the linkage to standard, and making sure that native has some global
concept like "real" or "normal" that is reflected in the topology
functions.
The problem with "making sure" is that you run into problems when it's
not possible.
A standard-regular set is some random collection of points that have
little global significance. It is just a bounding box hack.
>
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.
For listing or vector operations, yes. For 2-D operations no. Most
topology functions involve 2-D relationships. Generic filters are the
big class that index coordinates are most useful for and we should
probably use them for all of this. But filter algorithms are likely
still best done in native coordinates for special cases.
But the difference is only incremental, and the changes are localized.
6. Finally, I see little reason why native coordinates can't be
introduced later (after several different topologies are working), and
used as necessary.
You mean do all the complicated general operations in regular or map
coordinates, then figure out how to simplify them into native operations?
Why not just use native coordinates now for the things where they are
useful?
Because it requires many more changes to the code, as the regular system
is already in place.
You have split regular == map into two sets when you went to true iso
topologies. But a more efficient (rinse my mouth out) split for this
is standard and a (rotated regular == native).
You're confusing types of coordinate with coordinate sets. A regular
native set is often more useful than a regular flat/map set, but the as
I've explained above the difference is only in efficiency.
normalize_map_pos() doesn't change if you do it in native coordinates
so what you need to add is a map_to_native() at the start and a
native_to_map_pos() as you return to have a standard coordinate
normalize_map_pos().
I'm not saying it's impossible to do with a hexagonal map, but it
certainly hasn't been explained yet. Nor has it been proven that all
vector-preserving maps must be either hexagonal or rectangular (though I
believe it is so). Nor have non-vector-preserving maps even been
considered, for the most part.
whole_map_iterate() doesn't change, except if this is iterating over
native coordinates and they are no longer synonymous with standard or
map then you need to add a native_to_map_pos() transformation.
Note, you could use an index_to_map_pos() and use the linear form of
whole_map_iterate() in the corecleanups.
In fact, if you only access normalized coordinates, then all elements
like map.tiles should be be stored in linear coordinates and you need
to do a map_to_index() transform everytime you access them. But wait,
this is what Freeciv does already, why did it need to convert to
regular :-?.
Freeciv uses map_inx to index into it, but all of the storage structures
are hard-coded. map.tiles is hard-coded as a map.xsize x map.ysize
array, and all local storage is either done that way or uses a double
array. Eventually all of this should be converted to entirely use index
positions, but this is also just a difference in efficiency.
There is nothing magic about native, standard, regular, linear. They
are all just ways of looking at similar things. Some ways have useful
properties when doing some things, so one should take advantage of
this.
The problem is that while standard and linear are well-defined, native
has not yet been. You have incorrectly assumed that all wrapping
vectors must be orthogonal, and narrowly defined native positions to
work with rectangular topologies.
Regular as you have used it just doesn't take the best advantage of
things that others do, and certainly a lot of the original standard
operations didn't take much advantage of anything in the iso case.
These are the places where things are changing.
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.
That is pretty much what I have done. I used native operations where
I figured out they made sense. There may be some places that I've
missed, of others where standard -> linear or some such can also be
done the same way.
OK. Now implement a hexagonal map :-).
It might be nice one day to convert everything to native in a savegame,
rather than just the global parts. This would mean you could save a
game as an isometric world, hack the maptype in the savegame and read
it back in as a standard map. All the tile relationships would be
totally wacky, but everything would be in the right spots and it
would probably play without trouble - sanity_checks of continental
integrity and such tile rearrangements excepted :-).
Yes.
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.
These are the "critical" or must do cases. And fixing up isometric is
I think probably the most important part.
I think that in doing this we have figured out a lot of the complexity
and experimentally verified the resulting changes.
Not if you don't think ahead.
So long as native coordinates are defined in a sufficiently loose
manner, everything should be fine. But if you make the definition too
restricted (as I think you have), then it may make it impossible to
impelement native coordinates at all for certain topologies.
Your separation work keeps us honest, and is very useful in pinpointing
the interfaces and structure that local fixing misses.
The combination of topdown and bottom up can result in more rapid change
and correct change after the initial stages of either are petering out.
So doing things in parallel or differently is not bad.
Hey, we have found another point of agreement.
The trick is to be able to merge and join the two when the time comes.
Yes. In this case, we are largely arguing about the _order_ of
implementation. This is probably not the best use of time. We really
should go back to arguing about
unnormalize_map_pos/find_representative_map_pos.
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.
Global is iterating over the whole map. Local is map_stepping to
adjacent tiles.
Global parameters are border and wrap dimensions, local are directional
tile relationships and distance computations.
OK. These are global in terms of the world, but local in terms of the
code. Most stuff that is global in terms of the code is local in terms
of the world and best done in map positions (although there are exceptions).
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 will resist quibbling here ... basically we agree.
Yes.
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.
map is the internal standard game coordinates, I'm fine with that.
It should be described as the "standard" that all others need to be
able to convert to and from, but we don't need to label it "standard".
This means we have native iso and native map coordinates as the two
core coordinates systems used in most global operations. They have
4 wrapping flavours each to give 8 topologically distinct maps. The
GUI has two views, isometric and (map) to give 16 unique ways to play
the game.
Native generally deals with a particular topology. So we have native
iso-rectangular and native flat-rectangular (==map) positions.
Hopefully we can also have native hexagonal and (of dubious use) native
iso-hexagonal positions. Some day we may come up with native circular
positions, just to make that topology more efficient.
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.
Normal has some concept of uniqueness associated with the set. There
are never two equivalent positions in a normal set.
Yes.
- real. Duh.
Let me help. Real coordinates are the necessary part of the game.
Unreal coordinates are an unrecoverable error condition, except to
void_tile adherents.
Yes. Unreal coordinates are an unrecoverable error condition, except to
those willing to accept a void_tile-ish solution :-).
- 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.
I think (regular == normal) in native coordinates if you are willing
to relax the realness constraint on normal to include filtered unreal
positions. Thus linear coordinates are also always normal even when
they have extra positions to make calculation easier.
OK, although I don't think the semantics on the linear/index positions
are really important.
The only important condition for map coordinates is realness. It is
the native/regular/index ones that need something like normal to
make storage and the like work.
You're still confusing coordinate types with coordinate sets. Regular
is not a "type" of coordinate; there's no map_to_regular_pos function.
It's a set of coordinates, chosen by us just as the normal set is
chosen. When we say "regular" coordinates, we mean "regular map"
coordinates. Of course, this is mostly just quibbling over semantics.
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.
Except those that are trying to argue candycaning is necessary :-)
Hey, good point :-).
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..
All these unnoticeables, especially when they are all in the same
direction, do add up you know :-)
Once they do we can fix them. Fixing them before they are inefficient
seems unnecessary.
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.
Actually, it is the number of times that I FAIL and just spend CPU cycles
spinning that bothers me when I do this.
Usually this is no greater than 50%, which is comparable to the time
waste you'd have in converting to native coordinates and back.
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.
In a Savegame of ~4200 lines, ~700 are the initial map, and all but
100 of 500 for each of the 7 players are map-sized objects. These lines
are always 80 columns or better while the residual is typically 20
characters or less.
So, 16% + 80% * 84% ~= 83% of the save game is of map-sized data in lines
not even data units.
Touche. I had, of course, forgotten the player maps.
I think you underestimate the effect this is going to have on Renier and
Paul's server hardware budget.
Only if people play on 100x2 maps!
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.
I laugh ... native has more restrictions :-).
Restrictions are a good thing - they allow you to do things simply and
cleanly.
At its worst, native == regular.
Yes, but with an extra conversion required.
It must be my backwards English, and genetic heritage again.
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?
Good ... (normal == regular) == agreement
normal==regular is a restriction, and a good one since it allows a lot
of tasks to be done much more easily.
Unfortunately, it's not possible because of filtered cases. Here we
will (in the iso-rectangular case, at least) have a much lower miss
rate, but we won't be able to take advantage of this with simpler code
constructs - we'll still have to check each time. So certainly some
_regular_ native positions will not be _normal_.
Unless we can solve the hexagonal case and are willing to take our
chances in the future, we will also have to abandon the other
restriction: that each real position is represented only once within the
regular native set. Then we will still have an efficiency gain, but
will miss out on some more simpler code constructs. This is what I
think we should do, but I think we should think about it some more.
It is explained above.
For 2-D wrapping topologies which have many equivalent positions,
but two orthogonal rectangular wrap axes with given wrap dimensions, it
is the rectangle formed by these dimensions. If you have no wrapping it
is the smallest bounding box that encloses all the points (note that not
being restricted to alignment with map coordinates means you can often
find a rotated rectangle that is smaller than your regular case). This
set guarantees that no two positions in it are ever equivalent, unless
you are doing really funky warp space stuff (if so it will probably need
to be special cased up the ying-yang anyway). On top of this set you can
apply shape filters to produce ellipses, etc.
Now how about the non-orthogonal case? If you warp it a little bit, you
could perhaps represent the hexagonal case with two coordinates in two
different, non-orthogonal directions. But I haven't given much thought
to the math.
Or, to put it another way: in flat-rectangular coordinates, our u and v
axes are x and y, and our unit vector has distance 1.
In iso-rectangular coordinates, our u and v axes are at pi/4 and 3/4 *
pi, and our unit vector has distance 1/sqrt(2). Some positions are
excluded, according to simple well-defined rules.
In flat-hexagonal coordinates, our u and v axes would have to be at 0
and pi/3, with a third dependent axis at 2/3 pi. I have not worked it
out any further, but this should get you started :-).
X
XXX
XXX
X
Wrapping is possible along any of the three axes, but they are not
independent (any two implies the third). There are therefore 5 possible
choices for wrapping (although the unwrapped and horizontally wrapped
cases are indistinguishable from a filtered flat-rectangular topology).
Then we have the pi/4 rotated hexagon:
XXX
XXXXX
XXX
which we're probably not really interested in. Plus we have isometric
versions of both, which are only of use to make isometric-view clients
_slightly_ better looking.
-------------------------------------------------------------------
After we've considered that, we should consider cases that don't obey
the vector-addition rule. Mobius strips, klein bottles, and wrapped
triangles may be of little interest to most players, but they're
certainly very cool. These don't really have vectors of wrapping at
all, and so native coordinates may not be achievable at all in the
general case.
I tend to think of the unique set as a normal set, and the real coordinates
as those that are both normal and survive filtering.
For me realness is the condition that guarantees game utility, and
normalcy the one that allows utility for topology, storage, etc. or
conversely avoids assert hazards.
Yes.
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.
Well it depends on what axes you want to grind, but a 2-D hexagonal world
has wrapping axes that are. And symmetry operations in these two axial
directions.
For the purposes of doing a Torus world in hex coordinates, you would
choose the appropriate axes, rather than some inappropriate ones.
See above. A hexagonal map is not the same thing as hexagonal tiles.
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.
You can play quite usefully on a number of flat-earth (unwrapped) maps
of arbitrary shape using filtering techniques.
You can use rectangular wrapping with square, iso and hexagonal tilesets
without too much pain on rectangular maps, there are two flavours of
hex, one with E-W and one with N-S primary axis, while the secondary
axis alternately bisects one and separates two tiles.
I don't think there is any useful non-rectangular wrapping shape in 2-D.
I remember someone explicitly requesting the hexagon; it is potentially
a more "fair" world shape than a torus.
It might be interesting to see what you could do by limiting oneself to
a local representation of a hexagonal tiled spherical surface. As one
moves out the 2-D projection gets to be a bit funky, but locally one
would probably be fine.
Yes. Unfortunately, since everything is continuous there is no
distinction between local and global in game coordinates. But it might
be possible to use spherical coordinates or a connected graph of
positions to represent a sphere in terms of game coordinates, and use an
approximation for the GUI part of it.
If one thinks of this as two hemispherical/hexagon grids touching at the
equator or day/night halves it is probably conceivable without requiring
too much therapy. It would be a strain to think about how a centered
view would move tiles around as you stepped along, but it probably
peels off an edge in one of the six directions of motion and adds it
to the otherside of the hexagon across the axis orthogonal to the motion.
The border (along the equator) isn't clean.
Native coordinates would of course be the rectangle bounding two joined
hexagons with a filter to cut out the non-real positions.
There are an infinity of Great Circles or wrapping coordinates on a
sphere, but this is probably limited to the number of hexagons around
the equatorial edge with some interesting paths being traced in the
process. Wrapping operations would be interesting.
Sounds fun, but it's still a long ways off.
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.
Nit on nit ... it really is, but it is heavily constrained so it isn't
really that obvious.
Nit on nit on nit: the same definition can be applied to normal and
real, but isn't. The point here is that we apply a filter rather than a
conversion to determine whether the points are real/regular/normal.
You're right that it's all semantics.
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.
There aren't a lot of changes for either system. Native has close to
zero conceptual change in the basic global elements, and only requires
inserting transformations when you switch coordinates from global to local
operations. This is equivalent to looking for places to linearize array
lookups using map_inx() - not rocket science.
Yes. Once the above issues are addressed, I certainly won't be opposed
to the introduction of native coordinates. I just think other things
have higher priority.
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.
To bad you couldn't have finished the topology work, then switched things
to regular coordinates as you suggested above for native, and which in
fact is pretty much the way the corecleanups went except for the last
push.
The topology changes wouldn't have worked without one of the two. The
regular system is much simpler, and probably required in the native case
as well, so from a code point of view it's a no-brainer. The only issue
is the efficiency, but that's not an issue until the work is completed.
That would mean less of the useless grunge would need to be removed from
CVS now, or the corecleanups when I had to tidy them up.
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.
Yup, when it is not going to improve efficiency there is no need for
numbers or serious analysis. I'm sure the spin loops are almost noise
even at 2% hit rates :-).
Now that you mention it, yes. Without candy-caning the spin loops will
be the least of your worries for such a pathological topology :-).
But to be clear, I mean "average" rather than "general". My bad.
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.
Except for the global loop order though.
Yes. These changes are localized; i.e. within whole_map_iterate or some
other place. Map storage, unfortunately, is not - but I haven't changed
that at all; if I did it would be to use index positions.
[...]
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.
And Raimar always says that until used, they cannot be implemented.
How did regular slip through this catch-22 situation to foul up CVS
so badly :-)
Partly it all goes away in the compilation; i.e.
# define regular_map_pos_is_normal(x, y) (1)
Also because it was put forth as necessary, rather than just an optimization.
General-topologies is also 70k instead of 800k, and consequently has a
good (well, better) chance of being realized in the foreseeable future.
Corecleanups has a lot of stuff besides topology. It has also been
diverging from a lot of the ongoing experimentation hacks.
Yes, I know. This has both advantages as well as problems.
If we remove the ?? K of regular changes from the topology diffs of
the corecleanup stuff you might be surprised to see what the ratios
are.
Probably about the same.
But corecleanups was touted as a mega-patch when it was the current
size of general-topologies.
So is general-topologies. I just don't want it to become any more mega :-).
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.
Once it is in place there will be a lot of breakage and an incredibly
unwieldy system to ever unscramble. The effort required to do core
cleanups of similar grunge tells me this is not a good way to go. This
usually happens with piecemeal development and no concern for global
concepts, and no opportunity for real review of what is being done
or where it is leading.
I think the "it" that you're talking about is already in place, and is
no worse than the code that preceeded it.
If native coordinates had been implemented before the regular system was
developed, things might have gone differently (or maybe not). But since
you implemented native coordinates as a reaction to the "regular"
system, this was impossible :-).
But I agree, it will open the door to lots of fixup patching :-).
Only a little, I think. And it will be easier to justify the fixups
then because they will actually gain something (efficiency).
Ok, I think the squabbling has gone on long enough. Here is what I
propose. As I see it, there are just a few pieces of cleanup necessary
to implement iso-rectangular maps:
1. find_representative_map_pos/unnormalize_map_pos. We have to agree
to something on this.
2. mapgen changes. You had wanted to do this; now is the time IMO. My
only request is that there is at least one map generator that is
topology-independent, and that the code fall back upon this one if
necessary (rather than segfaulting as it will do with no changes).
3. miscellaneous changes. There are just a few of these (like the
vnotify_conn_ex thing), and they should (but generally aren't)
straightforward.
4. the map overview. This depends on #1, and will probably require
extensive discussion.
5. the topology system; i.e. a global topology struct or ID, plus code
to transfer it server->client and store it in the savegame, plus
capabilities and other necessary backwards-compatibility, plus code for
specifying it as pre-game server options. This doesn't depend on any of
the above, although it doesn't make sense to introduce it much before
we're ready for #6.
6. the iso-rectangular topology itself, implemented as changes to the
backend topology functions plus necessary additions to the topology
system (i.e. new values for the topology struct/id). This depends on
all of the above.
Only #4 has any chance of introducing further regular map coordinates,
and I'm sure there will be extensive discussion about that. In the
meantime, we can introduce any other desirable changes as well - as I
said, I will support a patch that (correctly) provides native
coordinates, although there is no use for them yet (it makes more sense
IMO to focus on index/linear positions first).
jason
- [Freeciv-Dev] Re: [PATCH] Map cleanups (PR#1208), (continued)
[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, 2002/01/09
[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 <=
[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
|
|
