[Freeciv-Dev] Re: (PR#8773) rewrite city_map_iterate

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

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


Gregory Berkolaiko wrote:

> <URL: http://rt.freeciv.org/Ticket/Display.html?id=8773 >
> 
> On Sat, 22 May 2004, Jason Short wrote:
[...]
>>Using an array solution is fine with me, but someone has to code it. 
>>And the method used in the corecleanups (a compile-time-generated array) 
>>is no good since these iterators may (in future) vary by topology, 
>>CITY_MAP_RADIUS, or even per-city.  This is not easy to deal with in an 
>>array solution. 

Actually it is rather trivial, and the ability to build or swap in a
different array to get different behaviours is a very powerful tool
for doing lots of things.

Adding a check variable, and calling an init_array() function that does
Jason's piggy iteration to fill it in the first time is a one-liner addition
that resolves his future issues. This is just a standard cache pattern in
software development so should not require any mental strain.

>>Finally the claim that it is substantially faster than 
>>a (possibly inline) mathematical calculation has not actually been 
>>demonstrated.

That is ok. We understand how hard it must always be made to demonstrate
performance value when the target motives are always to degrade it for the
as yet unspecified reasons. But it is clear that once the value of the
performance increase is shown, one has been secure in choosing the weaker
alternatives virtually 100% of the time. I'm sure past practice will still
prevail.

> For easy handling of CITY_MAP_RADIUS (whether city-dependent or not), you 
> need to iterate outward with a stop index depending on CITY_MAP_RADIUS.  
> Different topology would require either different arrays or iteration in 
> some common coordinates.  The former is preferable for speed and will 
> hopefully deter proliferation of new topologies ;)

Actually, the core iteration code will probably never change. What will
change is the init routines.  Moreover, if the core map iterators are
also changed to use the array form, then the init_array() step there
means that one has just two localized spots to adjust for any new case.

> As for the speed issue, we should have some trials.  Note that changing 
> iteration order will likely cause AI games to diverge.

One can easily fillin the array in different ways and experiment. I have
found that iterate outwards vs array-ordered patterns are often efficient
for finding and choosing alternatives, since typically attacking a nearby
opponent, rather than one at the NW grid corner is often a preferable
choice. It is subtleties like this that can be quite intriguing.

But computing and caching any values for indexed lookup, rather than
recomputing something that never changes for the duration of the game
should really not be that difficult a concept to understand. Even the
single loop and minimal tests that form the residual iterator code
reduce the complexity that current and topological future cases might
need to give a constant time across all future iterations.

> G.

Cheers,
RossW
=====