[Freeciv-Dev] Re: RFC: alternate topologies

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Tue, Oct 09, 2001 at 03:33:24PM -0400, Jason Dorje Short wrote:
> Here is the proposal, in full (version 1, pretty informal).
> 
> 1.  Mathematical Definition of a Allowable Topology
> 
> Any topology which fits the following informal definition should work
> with the proposed changes.
> 
> - Definitions:
>   - Let Z be the set of all integers.
>   - A "position" is the same as a "coordinate set".

A set isn't ordered.

>   - A "tile" is the same as a "position" but should not be used.
> 
> - S=ZxZ is the set of all possible positions, both real and unreal.
> 
> - R<S is the set of all "real" or "valid" positions.  (< means subset
> here).  Any position that is real has at least the following properties:
> (1) units can move there (2) the client can draw a tile for that
> positions.  An unreal (not real) position does not have these
> properties.

(2) is wrong if we allow the client to only draw a tile one time.

> - Coordinate pairs may be considered equivalent.  This means that if a
> unit on position (x, y) which is equivalent to position (x2, y2) that
> unit could just as easily be considered to be on position (x2, y2). 
> This property is an equivalence relation [1] - it is reflexive,
> transitive, and symmetric.  I'll call this relation "wrapping".
> 
> - N<R is the set of all equivalence classes of the wrapping relation.  N
> is represented as a set of equivalence class representatives [1].  More
> simply put, N is represented as the set of all "normal" positions;
> exactly one position from each equivalency class is in N.  A position in
> N will have at least the following properties: (1) it will have a lot of
> data stored about it, (2) it will be used as an index to map_inx and
> map_get_tile.  A non-normal position will not have these properties.
> 
> 
> 2.  Data Storage
> 
> The current map.xsize x map.ysize array format will be kept; however, it
> will no longer be entirely populated by "on-map" normal tiles.
> 
> The new definition is this: (map.xsize, map.ysize) is the dimensions of
> the smallest possible bounding rectangle for N.  (In general, N should
> be chosen to fit inside as small a rectangle as possible; this also
> makes calculations easier.)  Nice conversion routines will make this
> easy - currently map_inx() does this but I expect it will be expanded to
> map_pos_to_index(), index_to_map_pos(), and map_index_size() or
> something like that so that everyone is happy.
> 
> This storage method has the advantage of easy indexing (i.e. a simple
> map_inx()), but the disadvantage of having wasted space from
> fragmentation.  For most topologies the wasted space should be less than
> half of the total array; however, even so that means as much as a
> doubling of memory consumption in these areas.
> 
> 
> 3.  Operator Functions
> 
> The following functions are necessary to do operations and checks on map
> positions.  All should work under the arbitrary topology discussed
> above.
> 
> - is_real_tile(x, y) returns TRUE iff (x, y) is an element of S.  This
> should be renamed is_real_map_pos for clarity.
> 
> - is_normal_map_pos(x, y) returns TRUE iff (x, y) is an element of N.
> 
> - normalize_map_pos(&x, &y) returns FALSE if (x, y) are unreal (x and y
> become undefined) and TRUE if (x, y) is real (x and y are adjusted so
> that they are the class representative of the (x, y) equivalency class;
> the new (x, y) will be equivalent to the old one and contained in N).
> 
> - nearest_real_pos(&x, &y) adjusts x and y to be one of the nearest
> positions to (x, y) that is contained in N.  (NOTE that it is misnamed,
> it should be nearest_normal_pos.)  Since distance is poorly defined and
> there may be more than one position with equal distance, the new set of
> coordinates is not well-defined.  Thus you should not assume anything
> about this function.  It is definitely needed to keep the same behavior
> in the user interface, unfortunately; in fact right now it is the same
> as x=map_adjust_x(x),y=map_adjust_y(y) which is still used in many
> places (mostly incorrectly).

Grepping through the current source I think that nearest_real_pos
should be removed. In short time. There are currently no valid uses of
this function.
 
> - map_pos_difference(x1, y1, x2, y2, &dx, &dy) will determine the
> minimum difference between (x1, y1) and (x2, y2).  The (dx, dy) are the
> x and y differentials of the two positions; "minimum distance" is
> defined as having a minimum (max(dx, dy)).  If more than one position
> has equal minimum difference, the result may be any of the equivalent
> differences.
> 
> - A few other functions may also be needed.
> 
> 
> 4.  Necessary Changes
> 
> A lot of current code assumes that the topology is flat-rectangular and
> wraps in e-w directions only.  This code must be fixed.

This is a non-isometric cleanup/enhancing.

> In general, it's difficult to tell if you've found all of the applicable
> code.  However, there are a few patterns we can look for:
> 
> - Anything using map_adjust_[xy] is bad.  The fix generally involves
> normalize_map_pos and/or is_real_tile.
> 
> - Anything that loops over tiles and assumes every tile within a
> rectangle is on-map (normal) is bad.  The fix generally involves
> checking for is_normal_map_pos and skipping those which are not proper.

for loops:

$ grep -Irc 'for.*map..size' .|grep -v :0
./client/goto.c:1
./client/gui-mui/overviewclass.c:2
./common/game.c:12
./common/map.h:2
./server/barbarian.c:2
./server/gamelog.c:2
./server/mapgen.c:15
./server/maphand.c:3
./server/savegame.c:88
./server/gotohand.c:4

> - Anything that uses its own data storage methods rather than th one
> described in part #2 with map_inx() may be unsafe.
> 
> - ...?
> 
> 
> [1] http://www.math.csusb.edu/notes/rel/node3.html

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "Life is too short for reboots."