Worker AI

[Dalcinrafa]

Workers frequently state that there's no work to do, when there are. Better automatic worker settings would be nice too.

[refola]

I think this is because the workers aren't looking far enough away. The same situation happens with exploration.

The workaround for both cases is the same: Move the unit closer to where it's needed.

[yairm210]

This is a tradeoff we need to do between the AI being as useful as possible, and the runtime needed for the AI to check all possible help it can give. We've put a cutoff for technical reasons, so that the game will still run in relatively normal speed of the average Android phone.

[refola]

We've put a cutoff for technical reasons, so that the game will still run in relatively normal speed of the average Android phone.

Mind elaborating on the technical reasons? Because without knowing anything about the code, it seems like even the following naive O(n) algorithm should improve this situation.

1. Make a list of "idle" (by current standards) workers.
2. Iterate thru all tiles, assigning "idle" workers to improvable tiles sequentially (i.e., treating the list like a queue).

If computational resources permit, then you can replace the worker selection method with (a fast approximation of) "choose the closest 'idle' worker". I suspect that ignoring terrain costs to give a simple formulaic distance approximation would make the "closest 'idle' worker" function fast (O(n^2), but n is the number of workers, so n^2 is likely under 10,000) while still being accurate enough to satisfy most players.

[yairm210]

The problem is trying to figure out which workers can go where. Not every worker can actually head towards every tile. The canReach() function uses the getShortestPath() function, which is one of the heaviest functions in the game, and so for tiles that are too far away (I think 20 tiles away?) we don't even try. If you can improve either of those, the canReach() or the getShortestPath(), that will lead to a great performance boost everywhere in the game =D

[bitappend]

A simple and resource cheap solution. Is have the automated workers and explorers. After existing algorithm is exausted. If idle and no workable square in range and and available movement then move 1 tile in a rand() direction . Sure It doesn't give so genus level automation but will make them act like real people and just look around a bit eventually they will find something.

[refola]

@yairm210

Thanks for elaborating! Sounds like some serious graph theory challenges. I or someone else might be able to look up some useful algorithms eventually.…

For reference, judging solely by the names, it looks like canReach() and getShortestPath() are both digraph traversal problems, but the latter requires an efficient solution. I don't know if the "di"* part of "digraph" changes which algorithms are available.

Worst case, I suspect that some crude heuristics and simplifying assumptions could still improve the overall situation. But I'm not making strong claims until I learn enough Kotlin and graph theory to tell if there's a better algorithm than whatever's already being done.

* The graph is directional because you can't always navigate back the way you came. For example, suppose there's a line of three connected hill tiles -- call them A, B, and C -- where tile A is unimproved, tile B has another player's unit, and C has a road. If you have a worker on tile C, then it can move to tile A in one turn. But it can't move from A to C because it would use all its movement points getting to tile B -- an invalid ending tile for that worker, due to the other player's unit -- and will have none left to move onto the road in tile C. (Come to think of it, this would be a really funny way to trap "friendly" units if there's no other way around.)

@bitappend

Technically, that would work eventually if there's a path to somewhere useful. A 2-dimensional random walk will "almost surely" reach a given point. But it would be really inefficient on average.

Graph theory update

Wikipedia's shortest path problem section on directed graphs with nonnegative weights lists "Dijkstra's algorithm with Fibonacci heap" as having O(E + V log V) runtime for E edges and V vertices. For n tiles there are (roughly, ignoring reductions from map edges) 3n edges between them, so this is O(3n + n log n) = O(n log n). It also lists some papers which have O(E log log L) for E edges and L maximum edge "length" / weight (assuming integers; multiply movement costs by 10 to make them integral), which I think would translate to O(3n log log 20) = O(n) for Unciv. In theory, this means it's possible to reach O(n W) performance for n tiles and W workers.

Unfortunately, I don't think any of these algorithms account for how movement cost is quantized. In particular, at the end of a turn, it takes only 0.1 of a movement point to move onto any valid adjacent tile, no matter its movement cost. This means that a quantization-ignoring algorithm would tell a worker to prefer a path through terrain with a repeating rough (R) and open (O) pattern of RROOOO… (4 turns, but 8 movement points) instead of RORORO… (3 turns, but 9 movement points). I have no idea if any of these algorithms can be modified to account for this without becoming inefficient.

(Wikipedia's list of algorithms is a great reference!)