Building AI for RTS

[Toxic]

City-building Artificial Intelligence

At the request of developers I created short documentation of my AI. This topic is focused on city building, planning and management. More examples of my work: Combat AI, Random Map Generator.

AI Fields
The AI is not able to see game by human's eyes. In fact the AI is just an algorithm which can work with numbers and thus it is necessary to transform game data through special interface into data fields with exact meaning (AI field). Minimal unit in the KaM game is 1 tile (= 1 texture in game map). On the tile can be placed for example object, resource, obstacle or warrior. The AI does not know anything about any tile until it check the tile - for example the AI ask a question whether there is unit then save the information and keep asking another tiles. Decision-making process based on such questions is not too effective because it must handle each game tick around 255*255 tiles + not all tiles are walkable / reachable. Therefore, in computer games is created higher structure (often called Navigation Mesh) which merge multiple useful tiles into one unit (polygon). For KaM are needed only 2-dimensional polygons which can be obtained for example by Delaunay triangulation.

The map is then divided into polygons (you can see that polygons are NOT created in mountains):


Every polygon can contain multiple informations - for the city building AI is the most important information player's influence = detection whether are player's buildings in surrounding tiles (or the whole base). My AI also creates polygon routes between mines and decrease chance that in those polygons will be build forest (it is expected that there will be other houses).

Standard game (what the player sees):

AI influence "look":


Another example of the AI field can be array which corresponds with game map and allow or denny building of houses in specific areas (coal mines, forests, protected areas etc.)

City-building AI
Core of city-building AI is divided into 4 main classes:

1. TKMCityManagement = main class which controls city interface = unit training (in schools), weapons ordering, ware distribution, blocking wares in storehouse, house repairing, demolishing of exhausted houses and trading (+ simple trading algorithm = secure wood and gold production so AI does not get stuck).
2. TKMCityPredictor = this class computes city production, predicts derivation of ware flow and tries to create list of needed houses in dependence on peace time, count of mines, available free space and actual game tick.
3. TKMCityBuilder = selection of optimal houses which should be build + organization of roads / fields / shortcuts construction. AI should be able to build city quite fast because it also check free workers and give them work immediately after notification.
4. TKMCityPlanner = planning of new houses position: at the input is house type and at the output the "best" possible loc for the house. The "best" position is selected by weighted function which considers surrounding houses, terrain, player's influences etc. This class keeps list of all reserved / placed / destroyed houses and by requirements it sends them to city builder (AI can plan houses without placing house plan, destroyed houses are constructed at the same loc). It is one of more complicated classes which uses Eye class.

Support TKMEye class
This class provides map informations to the AI - gold / coal / iron / stone mine locs + list of forests, procedures which will check whether is possible to place house at specific location etc. It is universal for all AI players and it is located in AI fields.

Example of Eye view:


Genetic algorithm
Not every calculation is straightforward. Sometimes is required approximation or parameter which will change weight of certain element in equation. For example when the AI wants to decide if it place gold mine in loc 1 or loc 2 there is following function:

  Code:

PriceOfMine := {Available resources} * P0 - {Distance from city} * P1 - {Distance from coal mines} * P2 - {Influence of other allies} * P3 - {Influence of all other players} * P4;

where P0,...,P4 are parameters which must be choosen. Method for choosing optimal (in meaning of fitness function) parameters provides Genetic algorithm (GA).


Actual problems
The AI is now able to produce quite good city. There is still quite large potential to improve but it is question whether it is worth it - as an example I will show you the impact of Random Seed in two games with identical AI, initial conditions, resources and time for production / construction:


You can see that difference between weapons production is almost 60% (I simulated just 10 simulations with identical conditions and pick the best / worst). Producing of an aditional code which could suppress the influence of random noise is too much time consuming. It will also make actual code even more unclear and add another computation requirements.

Do you have any ideas? Do you need to explain something more detailed?

[Toxic]

Generation of Navigation Mesh (NavMesh)
Here is my algorithm for generation of the NavMesh. Basically it is modification of polygon triangulation with holes and inner points. Here can be found an old algorithm for NavMesh which is more universal but also slower and in current implementation is not possible to use it for generation of the NavMesh in real time.

Generator have 3 parts:

1. Extraction of polygons
   First, the map is separated into walkable and non-walkable tiles.
   
   Next, algorithm starts at first non-walkable tile which follows walkable tile and marks all tiles which are part of the same shape. Tiles are marked with using point which moves on the edge of the shape and use relative coordinate system:

     Code:

   X := aStartPoint.X; Y := aStartPoint.Y; v := aInitDir; // Init vector //Dir := ifthen(aRightHanded, -1, 1); // Determine direction of rotation repeat // Find next CanBeVisited tile and rotate vector if (Tiles[ Y-v.X{*Dir}, X+v.Y{*Dir} ] > 0) then // Left {Right} v := KMPoint(+v.Y,-v.X) else if (Tiles[ Y+v.Y, X+v.X ] > 0) then // Forward //v := KMPoint(+v.X,+v.Y) else if (Tiles[ Y+v.X{*Dir}, X-v.Y{*Dir} ] > 0) then // Right {Left} v := KMPoint(-v.Y,+v.X) else if (Tiles[ Y-v.Y, X-v.X ] > 0) then // Backward v := KMPoint(-v.X,-v.Y) else break; // Mark point // Move into new point X := X + v.X; Y := Y + v.Y; until KMSamePoint( KMPoint(X,Y), aEndPoint )

   This method allows to use information from previous tile and easily detect tile's position in shape (corner / edge). In parallel with this process are also calculated potential border-points of NavMesh (it is possible to use standard selection of each X. tile OR evaluation of tiles [border tiles can have higher price] OR Ramer–Douglas–Peucker algorithm ...).
   The points in grid are referenced to the right down corner of a tile. With using direction of rotation (vector v in code) is possible to determine position of point in the shape (top / left / right / down). This information is sufficient to determine point's relocation to secure that border lines will be as accurate as possible.
   
   After that, it is possible to connect the points and create borders of each obstacle (border = point + pointer to previous and next border). Moreover, there are added points in large walkable areas (fastest way is grid of points + detection of distance between new point and existing points but I prefer flood fill from border points and detection of unvisited area - it is slower but provides better results)
   
2. Polygon triangulation
   Finally, with sorted points by Y (they are sorted automatically in creation of borders), it is possible to assemble NavMesh with using Polygon triangulation. The algorithm will gradually select all points by Y coord and create triangles with 2 following border points and 1 closest point on the left side of line which is given by border points (direction depends on initial direction in item 1.) - see first image. The extension to the inner points just assume that each already existing triangle have all sides made by border points. In process of creation new triangle are also stored ID's of surrounding triangles from which is new triangle assembled (so triangles in NavMesh are automatically interconnected).
   
3. Pretty-Poly
   This algorithm does not provide "perfect" triangles. On the other hand the information about surrounding triangles of each triangle is available so it is easily to compare 2 nearby triangles and switch 2 points between them to create triangles with lower sum of circumference (on the picture blue lines are equal to improved triangles and red lines are old triangulation).
   

[thunder]

I won't lie... I lost after the first sentence. let's try it again.

[sado1]

I won't lie... I lost after the first sentence. let's try it again.

This must be the first time thunder lost against a wall of text on these forums, after a very long spree of wins.

Thanks for the post, I enjoyed it

[Just_Harry]

Yea very intersting to see how it kinda works. Nice work Rey keep it up!

[sado1]

Yea very intersting to see how it kinda works. Nice work Rey keep it up!

Just to be precise, from what I know, these two big features - new AI and random map generator - were done by Toxic, while Rey works on most of the other changes to the game.

[Rey]

Yea very intersting to see how it kinda works. Nice work Rey keep it up!

Thx, but new AI was made by Toxic, not me. So all of the honor and thanks please address to him.

Its quite interesting indeed. Sad thing is that seed is so important, so its hard to improve AI.
Any ideas how can we avoid so huge seed-dependance ?

[Just_Harry]

Omg idk why i wrote "Rey" xDD I must have confused the names. Anyways I mean Toxic of course

[Black]

Really good work Toxic, impressive how much work there is behind a simple AI action. What i don't understand really well, is how the random seeds effectively work, and how this influences AI 'performance' during all the game.

[Toxic]

...What i don't understand really well, is how the random seeds effectively work...

Seed is a number (for example 0.566813514354). Like I wrote in RMG topic we use Seed for generating random numbers. The algorithm is not important, you just need to know that random number generator needs the Seed as an input and then it returns pseudo-random numbers. Pseudo-random numbers among other things means that when you generate set of random numbers with 1 Seed and then you will use this Seed again for generating another set of random numbers the sets will be identical (so you can watch replay and the game will be exactly same with the live game).

Units in KaM makes unsynchronized actions. For example each warrior in group of archers shoots randomly and does not "wait" at other archers. This is done via random delay between shoots. In fact every unit in KaM have random delays between tasks / actions and random delay is given by generated random number. My question was about tricks, how to easily remove this "noise" to secure constant city production.

[Krom]

I doubt this is achievable. See the https://en.wikipedia.org/wiki/Butterfly_effect Even the smallest change (serf pausing for 2 ticks instead of 3, or archer killing an enemy in 1 shot instead of missing, or player commanding attack 200ms later) causes a huge change in whole game 20min later.

Ways to fight with that include reduction of Random() function usage. Let AI always plan the city without relying on any "random" factors (incl. wares reserve, unit counts, etc). Although I doubt that will work out well.

Other RTS can handle this much better because they are inherently less complicated systems (dozen of houses, no roads and no serfs).

[Toxic]

... See the https://en.wikipedia.org/wiki/Butterfly_effect Even the smallest change causes a huge change in whole game 20min later.

I understand you point but real Butterfly effect (weather) is definitely uncontrollable and probably even unobservable system. The AI build city with using reference data (predictor) and feedback (game data). It is true that it can hardly prevent initial inaccuracies but at least it control system to avoid critical states. In control theory you can compute derivation of regulation error and apply preventive steps. However, in KaM I was unable to construct such decision process based on ware flow because the game is too discrete (in first minute you will produce nothing, in second tons of wares, then will serfs get stuck and you are again at 0 even thought that you have all houses you need).

Ways to fight with that include reduction of Random() function usage.

Yep, I don't use random element in AI at all.

Other RTS can handle this much better because they are inherently less complicated systems (dozen of houses, no roads and no serfs).

Exactly - even though I knew that KaM is more complicated than most of new RTS I am still surprised when I see how many ideas to improve city will fail because of complexity.

[Toxic]

{never try to write message on phone }

[Krom]

How do you smooth results of "noisy" function - either take more samples (not possible in a single run), or average out on larger "window" (maybe that could do?)

[Toxic]

How do you smooth results of "noisy" function - either take more samples (not possible in a single run), or average out on larger "window" (maybe that could do?)

Yes this is technically possible. I already failed with this solution because similary to FIR and IIR filters it brings delay (production of 1 ware takes around 1 minute and sometimes you dont have resources for production so minimal step is around 2-4 min * order of your filter => not enough for stones) or you are unable to say how much time it takes before you will be able to produce this ware with using your intervention. For example when you detect shortage of wood, which is completely critical material, you can compute the time which it takes to build specific forest in specific distance (so delay of woodcutter production + delay of construction) and it will not correspond with real situation (maybe there are not enought building materials or this material is too far away so construction time is not accurate, maybe there is traffic, maybe you will be out of gold so you cannot afford to train woodcutter etc.).

I give up this idea for all houses except woodcutters where I added chop-only mode when it is critical. Instead of using variables I am using just parameters which are tuned by GA.

Probably best and exact solution is to compute ware flow by every piece but where to find resources for this tasks? And again there are exceptions ... what if serf which is bringing your ware die? What if he decides to bring this material in different place?