Map Database  •  FAQ  •  RSS  •  Register  •  Login

Building AI for RTS

<<

Toxic

Rogue

Posts: 50

Joined: 22 Feb 2017, 19:04

Post 24 Apr 2018, 19:31

Building AI for RTS

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

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):
Image
AI influence "look":
Image

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:
Image

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:
Image
Image
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?
Last edited by Toxic on 25 Apr 2018, 18:17, edited 1 time in total.
<<

Toxic

Rogue

Posts: 50

Joined: 22 Feb 2017, 19:04

Post 24 Apr 2018, 19:31

Re: Building AI for RTS

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.
    Image
    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.
    Image
    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)
    Image
  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).
    Image
  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).
    Image
Last edited by Toxic on 03 Jul 2018, 17:09, edited 5 times in total.
<<

thunder

User avatar

Knight

Posts: 993

Joined: 15 Apr 2012, 12:11

Location: In the Market

KaM Skill Level: Fair

Post 24 Apr 2018, 20:05

Re: Building AI for RTS

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

sado1

User avatar

Moorbach's Guard

Posts: 1385

Joined: 21 May 2012, 19:13

KaM Skill Level: Skilled

Post 24 Apr 2018, 20:48

Re: Building AI for RTS

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

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

Militia

Posts: 42

Joined: 15 Feb 2018, 22:04

KaM Skill Level: Veteran

Post 24 Apr 2018, 20:56

Re: Building AI for RTS

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

sado1

User avatar

Moorbach's Guard

Posts: 1385

Joined: 21 May 2012, 19:13

KaM Skill Level: Skilled

Post 24 Apr 2018, 22:33

Re: Building AI for RTS

Just_Harry wrote: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

User avatar

KaM Remake Developer

Posts: 204

Joined: 12 Oct 2016, 07:41

Location: Moscow

KaM Skill Level: Fair

Post 25 Apr 2018, 06:08

Re: Building AI for RTS

Just_Harry wrote: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

Militia

Posts: 42

Joined: 15 Feb 2018, 22:04

KaM Skill Level: Veteran

Post 25 Apr 2018, 12:02

Re: Building AI for RTS

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

Black

User avatar

Barbarian

Posts: 108

Joined: 20 May 2015, 20:14

Location: Italy

KaM Skill Level: Average

Post 25 Apr 2018, 12:21

Re: Building AI for RTS

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

Rogue

Posts: 50

Joined: 22 Feb 2017, 19:04

Post 25 Apr 2018, 15:36

Re: Building AI for RTS

Black wrote:...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

User avatar

KaM Remake Developer

Posts: 3206

Joined: 09 May 2006, 22:00

Location: Russia

KaM Skill Level: Fair

Post 26 Apr 2018, 07:42

Re: Building AI for RTS

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).
Knights Province at: http://www.knightsprovince.com
KaM Remake at: http://www.kamremake.com
Original MBWR/WR2/AFC/FVR tools at: http://krom.reveur.de
<<

Toxic

Rogue

Posts: 50

Joined: 22 Feb 2017, 19:04

Post 26 Apr 2018, 17:15

Re: Building AI for RTS

Krom wrote:... 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).

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

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

Krom wrote: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.
Last edited by Toxic on 26 Apr 2018, 17:18, edited 1 time in total.
<<

Toxic

Rogue

Posts: 50

Joined: 22 Feb 2017, 19:04

Post 26 Apr 2018, 17:17

Re: Building AI for RTS

{never try to write message on phone ;)}
Last edited by Toxic on 26 Apr 2018, 18:52, edited 1 time in total.
<<

Krom

User avatar

KaM Remake Developer

Posts: 3206

Joined: 09 May 2006, 22:00

Location: Russia

KaM Skill Level: Fair

Post 26 Apr 2018, 18:46

Re: Building AI for RTS

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?)
Knights Province at: http://www.knightsprovince.com
KaM Remake at: http://www.kamremake.com
Original MBWR/WR2/AFC/FVR tools at: http://krom.reveur.de
<<

Toxic

Rogue

Posts: 50

Joined: 22 Feb 2017, 19:04

Post 26 Apr 2018, 19:20

Re: Building AI for RTS

Krom wrote: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?

Return to Ideas / Suggestions

Who is online

Users browsing this forum: No registered users and 4 guests