[Freeciv] Re: siege

["Jonadab the Unsightly One" <jonadab@xxxxxxxxxx>]

Sam Steingold <sds@xxxxxxx> writes:

> >> tile availability is defined as follows:
> >
> > [by an O(n^2) algorithm if I understand it correctly, where n is the
> > number of units that can reach any of the city's tiles in one turn,
> > which with railroads could easily be dozens of units, potentially
> > thousands on a large map]
> >
> > That might have an adverse impact on performance, since it has to be
> > calculated each turn for each city.
> 
> why is it quadratic?
> we apply units one by one.

For each square being considered, each friendly unit that can reach
the square must be compared to each enemy unit that can reach the
square.  Looking at it again, I think the whole algorithm may actually
come out to O(n^3).  Also bear in mind that in some large-map
scenerios, n can go into the tens of thousands, which really makes
anything very much beyond O(n * log n) problematic.

-- 
$;=sub{$/};@;=map{my($a,$b)=($_,$;);$;=sub{$a.$b->()}}
split//,"ten.thgirb\@badanoj$/ --";$\=$ ;-> ();print$/