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

["Gregory Berkolaiko" <Gregory.Berkolaiko@xxxxxxxxxxxx>]

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

On Tue, 25 Nov 2003, Guest wrote:

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

I don't see how this information can be used in an efficient way.  I 
suspect the time to calculate the nets will outweight any possible gain in 
PF computation.  However, you are welcome to prove me wrong.

G.