[Freeciv-Dev] (PR#6946) Settler AI optimization

["Guest" <rt-guest@xxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=6946 >

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.