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

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

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

Gregory Berkolaiko wrote:

> 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 ;)

It's easy to generate arrays for the iteration order - in fact this is 
pretty clearly the best way to do an outwards iterate (just look at 
outwards_iterate in map.h).  This can be done easily using an 
inefficient algorithm or with more trouble using an efficient algorithm. 
  There's no great need for efficiency here; however see below.

It is also easy to generate arrays to check for realness.  For instance 
is_valid_city_coords could do an array lookup.  This is harder since 
(under Remi's patch, anyway) the validity may depend on the city and 
thus you'd need separate arrays.  I had thought Ross was suggesting 
doing this, but maybe not.

It should be pretty obvious that city_map_iterate_outwards is closely 
related to iterate_outwards.  However while the former (very simply) 
uses an array implementation the latter uses a (very complicated) 
mathematical implementation.  It would be better to use an array 
implementation for both, I think.  However there are some issues here:

- An array implementation for iterate_outwards won't work well for 
non-linear topologies (like a quincuncial topology).

- While the city's iterate_outwards uses pythagorean order (from 
map_distance_sq) the map's iterate_outwards uses tile order (from 
real_map_distance).  Both of these requirements are absolute AFAICT.

jason