[Freeciv] Re: siege

[Sam Steingold <sds@xxxxxxx>]

> * Jonadab the Unsightly One <wbanqno-IrLFYxOktEFfGaWA9+OTKt@xxxxxxxxxxxxxxxx> 
> [2005-08-12 11:03:09 -0400]:
>
> 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.

not really - the best offensive enemy unit has to be compares to the
best defensive and the best offensive friendly unit.
this is O(n log n)

-- 
Sam Steingold (http://www.podval.org/~sds) running w2k
<http://www.jihadwatch.org/> <http://ffii.org/> <http://www.mideasttruth.com/>
<http://www.savegushkatif.org> <http://www.openvotingconsortium.org/>
If at first you don't suck seed, try and suck another seed.