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

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

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


Jason Short wrote:
> <URL: http://rt.freeciv.org/Ticket/Display.html?id=7350 >
> 
>>[rwetmore@xxxxxxxxxxxx - Thu Apr 01 05:21:01 2004]:
>>
>>If all you want is the order of outwards iteration, then walking it as
>>in the corecleanups spiral macro is trivial O(1) process.
> 
> Um, no.  spiral_outward is over 50 lines long, far from trivial, and
> won't work for hex-tiled maps AFAICT.

I don't think there is any real issue with hex other than the
usual fixes to deal with adjacency constraints. There might
be more sides and directional increments along each side to
consider that means the current implementation needs to be
generalized beyond its simple x,y motions that follow a square
pattern, but this is minor stuff.

No problem if you want to write your own version to reduce the
linecount, optional flexibility and/or add generalizations ...
that the concept is trivial and O(1) is the key point that means
you have an alternate algorithm than nested array order loops.

There are no doubt other algorithms as well ...

>>There is actually a value in doing outwards iteration in unit move
>>searches and such (like with pathfinding) vs array order iterations,
>>in that useful things are usually closer. But that is a very subtle
>>way to effect both performance and game behaviour.
> 
> Shouldn't these cases be using path-finding instead?  That way you
> always find useful things closer; this is far from subtle.
> 
> jason

If you know what you are looking for, pathfinding might be more
effective to optimize the specific checking order. Just a simple
distance flavour is certainly one of the other O(1) algorithmic
ways to do things which may or may not be easier than an outwards
walk, and will certainly be better than your O(5) flavour.


The subtlety in effects of iterating a city map in array vs some
other outwards spiral order in general means a different sequence
of pseudo random numbers in checks for each tile, the possibiity of
order of encountering or listing results in lists changing the
precise sequence of events, etc ... None of these are problems,
but they certainly change the evolution of the game in the sense
that one would not expect two games with different order to result
in the same savegame for testing purposes.

[ASIDE]
The advantage of doing it in general iteration is that usually a
closest tiles first order is going to find the optimum whatever
over an array order iteration. These effects are actually part
of the reason why the corecleanups consistently ran 50% faster
than comparable CVS. The fact that you forced the core DIR_DX
handling to be the same as the GUI, rather than using rotational
order in the core and array order only for GUI tiling is a similar
case to this more limited citymap example.

Thus doing things in the order you argued for and chose by getting
in a partial patch back then, i.e. link the two, then migrate,
rather than keep the core and GUI separate and migrate just the
core leaving the GUI for a proper overhaul, has had signficant
and detrimental results. We are now at the point where the GUI
is being cleaned up with a separate set of coordinates, but the
unnecessary linkages and performance/robustness/simplicity
cleanups are still not done. And you are still fighting them now
with O(5) patches that still handle things from the array order
perspective.
[/ASIDE]


On the otherhand, if you are doing things related to GUI tiling
there are advantages to using an array order for iteration.

Thus having both flavours for iterating a citymap is useful, and
not just in specific cases.


Cheers,
RossW
=====