[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:

>>>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.
> 
> 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.

I assume by O(5) you mean O(n^4)?  And by O(1) you mean O(n)?

I still don't see why you're concerned about a one-time running of an 
O(n^4) algorithm when n is almost always 2.  In fact I practically 
guarantee that the algorithm I suggested (O(n^4) generation time, O(n) 
execution time) will give a faster runtime than your spiral_outward 
method (O generation time, O(n) execution time) - though the difference 
will be incredibly small.  (Obviously this isn't true if N is unbounded. 
  But it's not.)

jason