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

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

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

> [guest - Tir. 25. Nov. 2003 15:58:08]:
> 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.

I have experience with this kind of problem. I am writing an agent for 
Asimulator ([http://savannah.nongnu.org/projects/asimulator]). The 
agent is exploring the world an thinks of unexplored areas as groups of 
unexplored tiles. The agent sets a higher priority on smaller groups to 
avoid leaving small unexplored areas behind when wandering off 
exploring a larger area. (That is because it would cost the agent many 
action points to move all the way back just to explore the missing 
tiles.) Each time the agent explored a tile, it had to check whether 
the group of unknown tiles that the tile belonged to became split. Then 
it had to renumber the tiles of the different groups.

One of the complications I had when writing this for the agent was that 
the smallest group should have the highest number and so on. The 2-way 
split was reasonably simple, but the 3-way split was far more complex. 
To achieve this in an efficient way I had to do 2 or 3 recursions 
parallel. Because of that I could not just use a recursive function, I 
had to implement the recursion manually with a loop and 2 or 3 stacks. 
Fortunately your railroad proposal does NOT have this complication. 
(The code in question can be found at [http://savannah.nongnu.org/cgi-
bin/viewcvs/*checkout*/asimulator/asimulator/clients/ada/agents/gunnar.a
db?rev=HEAD&content-type=text/plain].)


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

I think this is wrong. Another player could have built piece of 
railroad next to one of the cities. So the automatic railroads must be 
handled as normal railroad builds, which should not be any problem.


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

Yes, find the shortest way between 2 neighbouring nets and make the
connection there.


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

Which means global recalculation when pillaging. I hope a simpler 
solution could be found. Just stop the move order when the enemy is 
blocking, notify the player, let the player move military unit from 
somewhere on the net and eliminate the problem, then let the user issue 
the move order again.


> 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 would be great.


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

This sounds great too.


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

Interesting.