[Freeciv] Re: siege

[kilobug@xxxxxxxxxxx (Gaël Le Mignot)]

Hello Sam!

Fri, 12 Aug 2005 12:58:54 -0400, you wrote: 

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

More O(N n log n) where N  is the number of titles reachable by a city
and n the number of units. If we consider that big maps tend to have
more unit, it's basically O(n²log n).

I think we could ignore  roads/rails for such computation; it makes no
sense to have a unit at the  other side of the world able to prevent a
production just because  it could move there. The  workers of the city
probably don't even know the units does exist.

-- 
Gael Le Mignot "Kilobug" - kilobug@xxxxxxxxx - http://kilobug.free.fr
GSM         : 06.71.47.18.22 (in France)   ICQ UIN   : 7299959
Fingerprint : 1F2C 9804 7505 79DF 95E6 7323 B66B F67B 7103 C5DA

Member of HurdFr: http://hurdfr.org - The GNU Hurd: http://hurd.gnu.org