[Freeciv-Dev] Re: Map coordinate cleanups.

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Fri, Aug 17, 2001 at 09:32:01AM -0700, Arien Malec wrote:
> Just to add to this very clear schematization:
> 
> For any grid system:
> 
> Set A (possible points) is the cartesian product N X N
> 
> Set C (normalized points) is the cartesian product  {n | 0 <= n < x} X {n | 0
> <= n < y}
> 
> Set B (real or normalizable points) has the following values:
> 
> For the x & y wrapped world, B = A
> For the unwrapped flat earth, B = C
> For the x-only-wrapped (Freeciv default) world, B = N X {n | 0 <= n < y}
> For the y-only-wrapped world, B = {n | 0 <= n < x} X N
> 
> Yes?

Looks ok.

> BTH, wouldn't a sensible way of implementing normalization be to generate at
> game initalization a suitably big array mapping coordinate positions to
> normalized coordinate positions? E.g., if the map is the maximum of 200x100,
> and sensible moves are < x/2 or y/2 (since if you go more than halfway around
> the map, you might as well go the other way), you would generate a 300X150
> array of ints, each cell of which would contain either the normalized 
> position,
> or NULL (if the position is irreal).

300*150*2*sizeof(short int)=180kb It is possible however I would
expect it would be slower. It depends on memory-bandwith vs computing
speed. AFAIK the computing speed is currently leading.

> That moves the tricky, expensive, and topology-dependent stuff to a one-off
> operation, and should make the implementation of is_real, is_normal, etc. and
> the iterate macros very very simple....

The goal is to have only a few (<10) calls to normalize_position() and
is_real_position(). The rest of the code would test each coordinate
with an "assert(is_normalized_position(x,y));". Most of these calls
however can be removed step after step. If for example the caller
checked the position and didn't change it why should the callee also
have to check it. Profiling of is_normalized_position() will lead to
the hot spots.

        Raimar

> Arien
> 
> --- Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx> wrote:
> > On Fri, Aug 17, 2001 at 05:19:35AM -0700, Trent Piepho wrote:
> > > On Fri, 17 Aug 2001, Raimar Falke wrote:
> > > > I have to admit I haven't learned the difference between proper and
> > > > normal during my coding. Maybe I have used too much copy and paste. I
> > > > think there should be the following sets of positions/tiles:
> > > 
> > > proper is some new thing Gaute came up with.  So you haven't seen it
> > > before.
> > > 
> > > >  A = the base set of all possible positions
> > > >  B = the set of real positions: a real position is a position which have
> > > >  directly or indirectly a tile associated with it
> > > >  C = the set of normalized positions: each tile has exactly one
> > > >  normalized position associated with it
> > > >  D = A minus B = the set of unreal positions
> > > >  E = B minis C = the set of unnormalized positions
> > > > 
> > > > B is a subset of A. C is a subset of B. Depending on the topology
> > > > these are subsets or proper subsets.
> > > > 
> > > > The following methods are declared:
> > > >  - is_real_position(p) tests if p is in B
> > > >  - is_normalized_position(p) tests if p is in C
> > > >  - p'=normalize_position(p) p must be in B, returns the normalized
> > > >  version of p
> > > 
> > > That is what makes the most sense to me too.  It's also what I've
> > understood
> > > to to be the existing code all along now.  The function is_real_tile()
> > already
> > > exists, and is_normal_tile() has been in some patches for quite a while.
> > > 
> > > What Gaute has done is make it so that C is no longer a subset of B, as it
> > > includes non-real positions in the normalized form.  Then he defined a
> > fourth
> > > set, he called proper, that is the same as your set C.  There are still 
> > > the
> > > same two useful subsets of A, now called real and proper, and one new
> > useless
> > > subset called normal.
> > 
> > So for simplicity sake we should stick to the schema above. Except
> > when Gaute comes up with a good reason for his classification.
> > 
> >  Raimar
> > 
> > -- 
> >  email: rf13@xxxxxxxxxxxxxxxxx
> >  Make a software that is foolproof, and only fools will want to use it.
> > 
> 
> __________________________________________________
> Do You Yahoo!?
> Make international calls for as low as $.04/minute with Yahoo! Messenger
> http://phonecard.yahoo.com/
> 

-- 
 email: rf13@xxxxxxxxxxxxxxxxx       phone: +49 351 4415773     icq: 54420251
 pgp 2: id: 0F9D7955 len: 1024 fingerprint: 7760F933D5478009 4FA0C56F1DC2FB8E
 "> Kann man Win 95 remoot booten ueber TCP/IP ?????
  ping -s 65600 win95pc"
    -- Steppke Holger und Rolf Weber in de.alt.sysadmin.recovery