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

["Raimar Falke" <i-freeciv-lists@xxxxxxxxxxxxx>]

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

On Tue, Nov 25, 2003 at 07:58:08AM -0800, Guest wrote:
> 
> <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. 

You are proposing two things here.

1) optimize the path-finding (used by the settlers but also by other
units) by specially considering railroads (nets)

2) change how settlers build railroads so that settlers build an
interconnected railroad net.

The first is possible but I don't think that the cost/benefit ratio is
very good.

The second is more for the AI guys. There were a similar proposal
(PR#1065 with the thread not in RT but with subject "AI can build
railway-system" in Nov 2001). It got rejected since the AI also has to
learn to defend this network. Otherwise the enemy would have an easy
task.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "Using only the operating-system that came with your computer is just
  like only playing the demo-disc that came with your CD-player."