[Freeciv-Dev] Re: (PR#7350) Map radius change with city size

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

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

rwetmore@xxxxxxxxxxxx wrote:

> It will be unbounded as soon as the patch for arbitrary city sizes goes
> in. Since you are aware of this, the above comment is rather strange or
> desperate.

Um, no.  Arbitrary city sizes does not mean unbounded city sizes.  They 
will always be less than 255, for instance.  Most likely they will 
always be less than 10.

> Attached is some cut and paste elements from existing code that hopefully
> illustrates some points you seem to have so much trouble with when you
> make your various unsupported assertions or repudiations of efficiencies
> and degree of difficulty of code required. These are generalized with
> clear points where additional optimizations could be added with little
> effort. The verbose commentary will hopefully make both the algorithms
> and other issues clearer.


[counter-example 1]

> A counter example ... still based on array order, but precomputing
> the array order loop data in a single pass.

This is a nearly identical algorithm with an extra sorting step to make 
the code O(R^2) instead of O(R^4).  This may or may not be worth the 
extra code required.


[counter-example 2]

> This is an optimized spiral outward loop that could be used to replace array
> order loops.
> 
> There should be enough commentary to understand the algorithm, which is
> relatively trivial and *very* efficient (all loop logic takes place at the
> end of a side walk, with the exception of a test for x or y increment and
> loop end. This test is minimal for reducing a doubly indexed loop to a
> single index.
> 
> The loop is also singly nested, i.e. conforms to the desired standard of
> making all loops "break"-able.

This loop works for iterate_outward but not city_map_iterate.

It would be easy enough to encode city_iterate_outward as a wrapper for 
iterate_outward.  However it wouldn't work, because 
city_map_iterate_outward works in pythagorean distance while 
iterate_outward works in real-map distance.

A better iterate_outward is something that we'll need to get working for 
hex-tiled maps.  Unfortunately this example doesn't work for hex-tile 
maps, and it's not immediately obvious how to change it to work.

It's also fairly convoluted, and likely to become more so when it does 
support hex tiles.  A final drawback is that it doesn't handle wrapping 
well for large spirals (but then neither does the current 
iterate_outward, despite its claim to the contrary).

It's not feasible to use an O(R^4) or even O(R^2) algorithm for a 
spiral_iterate macro, since it must be run many times.  However I wonder 
if it is possible to use a precomputed list of offsets for 
spiral_iterate.  This could probably be precomputed in O(n log n) time 
[n is number of tiles], and would of course take up O(n) memory.  This 
would have the advantage of working well with wrap (for linear 
topologies anyway).

jason