[Freeciv-Dev] Re: (PR#8959) remove CAR_DIR_D[XY]

["rwetmore@xxxxxxxxxxxx" <rwetmore@xxxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=8959 >


Gregory Berkolaiko wrote:
> <URL: http://rt.freeciv.org/Ticket/Display.html?id=8959 >
> 
> On Mon, 21 Jun 2004, Jason Short wrote:
> 
>><URL: http://rt.freeciv.org/Ticket/Display.html?id=8959 >
>>
>>>If the ordering of the directions is changed to rotational, the test for
>>>cardinal-ness is just a test for even-ness (or odd-ness).
>>
>>Except on a hex map.

The mask for hex takes out the 0 and 4 directions rather than even/odd
which is a rather trivial change in the simplest form (length and incr
only) of implementation.

> On a fake hex map you mean.  Because on a real one every valid direction
> is cardinal (edge-joined with the center tile).

And of course there is no mask needed in this implementation case in the
secondary wrapper function - just possibly a different order of loop that
postpones the N/S directions to the end of the combined std/iso/hex list,
or uses separate lists for each?

>>We have a similar problem for adjc_dir_iterate in that in hex maps not
>>all directions are "valid".  So either we need a call to is_valid_dir
>>here or we need something else clever.  adjc_dir_iterate actually is
>>used a lot (unlike cart_iterate which is almost never used) so there
>>actually is a speed issue here.  However the alternatives have drawbacks
>>as well:
> 
> I am not quite sure whether the below are disjoint alternatives or
> combinable parts.  So here is a proposal based on some of them:

I think you are finally getting to the point of the more sophisticated
versions of this sort of implementation (see the standalone mapgen code).

One thing that would be really worthwhile is to learn to abstract key
concepts (aka filter/mask) and implement them in an efficient manner
which in this case is a single lookup test to an array defined at compile
or possibly init_topo()/init_terrain() time (i.e. cached on setup of the
current topology or even first use).

Build the mask as a complex set of tests that include cartesian vs other
onetime setup masking elements and that are combined into the single lookup
during the init stage as opposed to having a number of lookups at runtime.

This means "filter" is the concept that is subdivided into sub-concepts
like is_valid_<for_whatever_reason{1,2,...}>() in an O-O fashion rather
than exposing all the filtering possibilities at the top level without
really understanding or codifying the basic filter concept one wants to
abstract. The top key requirement is that implementation lookups are
definable at init(). The next abstraction level down can include other
concepts like whether this is for cartesian vs full iteration (and hence
the loop lengths and increments are different or not (for added performance)
or whatever implementation details one wants to add in over time. Some 
techniques used in pathfinding to consolidate tests into basic types with
options for more complex things pushed down a level might be useful in more
sophisticated topology actions in the future based on this sort of
implementation.

The combination of ordering of the basic list of tiles that one iterates
over with total length and increment to cut down on wasted checks, the
transform array to reorder the list by changing the initial hardcoded
order, or by using different ordered lists for different purposes
(rotational vs tiling vs city vs ... and reorder helps because it gives a
set of trivial functions for interconversion outside of a loop or that
are useful for keeping loop and iterator variables in sync), and the filter
lookup are the basic elements of current prototype implementations.

Interestingly, one can change this implementation in the one header at will
and there is no need to touch the rest of the code - once you get things
right and undo all the monolithic hacks that exist in CVS and not the
corecleanups or other prototype examples/patches that have been around
for years.

> Part (a)
> 
>>Make new arrays VALID_DIRS[] and CARINDAL_DIRS[].  These arrays
>>contain the list of valid (for adjc_dir_iterate) and cardinal (for
>>cart_iterate) directions.  Of course these arrays must be initialized,
>>and that means extra code (in init_topology).
> 
> 
> Part (b)
> Make two variables NUM_VALID_DIRS and NUM_CARD_DIRS which give sizes of
> the arrays from part (a).
> 
> Part (c)
> Make a macro
>   dir_array_iterate(...., dir_array, num_dirs)
> 
> Part (d)
>    #define adjc_dir_iterate(...) \
>      dir_array_iterate(..., VALID_DIRS, NUM_VALID_DIRS)
> 
>    #define cart_iterate(...) \
>      dir_array_iterate(..., CARD_DIRS, NUM_CARD_DIRS)
> 
> This, I feel, will have the best features of Ross' model and be more
> extensible because the subset of dirs over which you want to iterate next
> doesn't have to form an arithmetic progression in the total set of all
> directions.
> 
> G.
> 
> P.S. I still remain very sceptical about new topologies such as hex or
> quincical.  I think there are more worthy issues to be dealt with.

Yup. Quincuntial is nowhere close to being viable as it still breaks a
number of longstanding rules (like showing duplicate tiles) associated
with dealing with concepts like singularities it hasn't properly worked
out yet.

But once you get the core code cleaned of topology specific hacks
everywhere, and the core iterators are one of the long overdue areas to
complete, then it becomes easier to spot problems (they require new
local hacks :-) and introduce fixes into the few places like a
consolidated iterator implementation.

I have also noticed "my_iterator()" hacks in various submitted patches
which means people are doing bad things (if left as hacks) that need to
be caught and done right or updates folded into the proper places.

Cheers
RossW
=====