[Freeciv-Dev] Settler AI optimization.

["Claus Leth Gregersen" <leth@xxxxxxxxxxx>]

Hi, i got a few ideas for optimizing settler AI and improving settlers in
general.

First of all, my theory is that there is no real big perfomance problems
before the invention of railroads. (there is not many settlers working yet)

Now when railroad has been invented we have this interesting situation that
moving along them is for free, so if you're on a connected railroad net,
then moving from one point on this net to another is free (aslong you're
certain there is no enemy blocking *sigh*). So identically to the initial
continental numbering it might be a good idea to number the railroad nets.

I) A naive approach would be to recalculate this numbering every turn.

II) A more clever implementation will only recalculate it for continents
where there has been placed a railroad in the previous turn.

III) An even smarter implementation will every time there is made a new
piece of railroad look at it's neighbour tiles, there is 3 situations:
1) It's adjacent to no railroad nets, we assign it an unused "railnet
number"

2) It touches 1 and just 1 net, we will assign this tile the "railnet
number" of the net it touches.

3) it is adjacent to more than 1 net, give this tile the lowest of the
different "railnet numbers" that it's is attached to, and change the number
of the adjacent nets to the number of the lowest of the adjacent nets. (this
can be done with a simply floodfilling exactly as the continent
calculations)

Unfortunately when game is saved/restored you'll need to perform I) or II)
to restore the railnets.

Similary when pillage happends, you'll have to check if it potentially
"breaks up" the railnet into 2 seperate nets, i haven't thought it through,
but an idea is if can't decide if it's "broken" by looking at the adjacent
tiles, you can floodfill one of the tiles with a new "railnet number" repeat
this until all adjacent tiles have a railnet number != the original number.

(when you discover railroads, your cities will automatically get a railroad,
and each city tile should be assigned a unique railnet number automatically
if it calls the same function which normally place the railroad)

So after this exercise you'll have different railroad nets on which settlers
can move without penalty.

1 settler strategy could be to connect these nets as soon as possible, so
the cities would be more easily defended.

Now i would suggest that all moves inside a net was just going to be done
without doing any sorts of goto, but potentially blocking enemies makes this
a problem. I got  2 ideas for this

1) ignore it, allthough it might give some strange situations.
2) When there is no enemies on the net.

This later option could be done by doing reference counting on "number of
units of a given race on a given net".

I know it's not  trivial, but i think if you did this you would reduce alot
of waste of cycles, and if you ditched moving the settlers along these
obvious path.
You would gain alot of performance both with CPU usage on the server and
reduce network traffic.

This could ofcourse also be extended to normal units on goto, where you in
O(1) can decide if it can move from a give tile to another.

Finding work for settlers could incorporate these facts as a better distance
weight.

Another possible extension of this net idea would be to calculate the move
cost between nets, this way you could build a graph for extremely fast
shortest path calculations (assuming your start and destination is inside
nets, or adjacent to nets)

Heh, i know who's going to code it is the good question ;)

But i think the idea is pretty neat, and it would be quite funny to code.

Keep up the good work, freeciv is looking really good.

/Claus Leth Gregersen