Sunday, March 28, 2010

Influence Maps II - Practical Applications

Now it is time to look at how we can use influence mapping in a practical application showing how we can use a simple influence mapping based scheme to create an AI that reacts surprisingly realistic and intelligent as long as it works within certain perimeters and you aren't trying to control it too precisely. This test as I have implemented it will only be using the basic Influence map but we will discuss interesting possibilities of using the other maps too. I am also sure that you by yourself will imagine a ton of ways to use the maps and even create new maps after these two articles. But for now we look at creative ways to use what we have learned so far.

What we are going to be looking on is what we used early on as an experimental Ai for Ground Control 2 it actually become the basis for that AI though heavily modified, partially because it did defeat our project lead 1 on 1 but mostly because the single player team needed a lot more control to create interesting single player missions. But within it's limitations it performed admirably and as I mentioned did become the basis of the AI.


Now it is time to look at how we can use influence mapping in a practical application showing how we can use a simple influence mapping based scheme to create an AI that reacts surprisingly realistic and intelligent as long as it works within certain perimeters and you aren't trying to control it too precisely. This test as I have implemented it will only be using the basic Influence map but we will discuss interesting possibilities of using the other maps too. I am also sure that you by yourself will imagine a ton of ways to use the maps and even create new maps after these two articles. But for now we look at creative ways to use what we have learned so far.

What we are going to be looking on is what we used early on as an experimental Ai for Ground Control 2 it actually become the basis for that AI though heavily modified, partially because it did defeat our project lead 1 on 1 but mostly because the single player team needed a lot more control to create interesting single player missions. But within it's limitations it performed admirably and as I mentioned did become the basis of the AI.

The actual implementation contained a couple of maps some of which will be familiar by now and some that aren't because they where specific to our exact implementation.

  • myInfluenceMap
    • contains all the influence from my troops 
  • EnemyInfluenceMap
    • contains all the influence from enemy troops. This is adjusted for how well I know the area in an attempt to try to make the Ai realize when he's just seeing the tip of an iceberg. It also handles the influence of enemies I am currently not seeing but I know are there, or can make reasonable assumptions that they should still be there.
  • Influence map 
    • The combination of the above maps. myInfluenceMap-enemyInfluenceMap
  • Block map
    • Contains information about whatever the center of a tile in the influence map is blocked.
  • EnemyBlockMap
    • Contains information about whatever the center of a tile in the influence map is blocked by being inside to strong a enemy influence
  • Goal map
    • A map where we can pain in extra influence used to guide our troops to different locations. 
  • Area map
    • A map containing an ID for each tile. Having the same ID means there is a possible path between the tiles. So basically it was created by flood filling all passable areas on the map and increasing the value written with one every time you had filled a complete area.
  • Strength map
    • Contains for each tile  value that tries to represent the important of that tile for fighting and strategic value. All Influence on this tile is multiplied with that value. This allows for hand painting and marking of important areas.
  • Final Influence Map
    • Influence Map+Goal map
First out we will go into some detail about the new maps, especially the goal map and then later on we will explain what we are going to use all of this for. First out is the goal map, the goal map is a way to add or remove influence around an area, and the question might arise why this of any use is for us? That is a good question and the answer is it depends, depends on what you are using your influence map for.

Our basic idea for now is that we will create a simple AI which has as its main goal to eradicate enemy influence in the world. This means that if we put a strong marker of enemy influence somewhere with the goal map our troops would want to go there and smash it. But at the same time since we are using the influence map, the same map that is influence by opponent troopers and buildings etc, they wouldn’t ignore something really obvious just to get to that far away spot with some enemy influence.  They should calmly exterminate influence and our maps are just hints that will be taken in and mixed with the overall position to create a reasonable plan. Following our hints when they make sense, but ignoring them if there are something urgent nearby. This creates an AI that fight reasonable within the limits we have put on him he won't just drive by a huge enemy troop ignoring it to accomplish his goal or any of the other weird behaviours an over controlled AI might exhibit.

So if we work with that as the basic thesis for our AI then using a goal influence map makes perfect sense. Basically we can order our troops around just by writing in a map, we can also give them goals of different importance and they will prioritize base on their distance to the goals and the surrounding circumstances. Without bothering our high level AI with the small details.


This system opened up a number of interesting possibilities, Booth Ground Control 2 and World In conflict are based upon the concept of command points. By dominating these points you win the game in the end, the implementation differs in GC2 multilayer you won by taking all of them, in WIC  by controlling a majority of them for a majority of the time. But the basic idea is the same there are command points and you win by taking them over. So we painted goal influence on the command points. How much we painted however was calculated based on a formula depending on how many the AI controlled and how many the opponent controlled. Generally neutral command points had a higher importance since a battle that can be won without a fight is more important, Then second is the enemies points and third my own. The part of adding opponent influence at my own zones is a way to make sure that some troops are left behind to guard the zones and keep them safe. However the different ratios differed depending on how many zones where captured by either side. For example if I have 4 zones out of 5 defending my current 4 is a lot higher priority than if I have 1 zone the opponent 1 and 3 are neutral. All this was taken care of when evaluating the influence amount used in the goal map.


We also had what we called a desperation factor which basically meant that if the AI was clearly loosing then all bets was off and just try to take something to turn the tide even if it is improbable to succeed since it's loosing anyway playing they way it's currently playing.

This weren't the only use of the goal influence map however. It was also used for allowing mission designers to flag up areas in the map that was important and that the AI should probably want to hold allowing specifications of areas for the AI to fortify in, again without breaking the system, however all if this have an disadvantage too, you loose the amount of control you have over the AI so it is hard to plan exactly what it is going to do. But with this you can mark important choke points or generally spots you want the AI to gather at. This was also combined with the strength map we talked about earlier, together this allowed for a powerful hint system that gave the AI a lot of information while not tying its hands.

We also used this is we had a group of troops that really wanted to go to an area but the enemy in that area was simply to strong so the tiles with the high influence we wanted to reach got blocked. Then we made a strong goal influence map circle around the enemy troops allowing our troops to be drawn there and gather strength until they where strong enough to attack.

Another important map is the scout map, this map contained information for every tile how long it was since one of our players saw it. This is achieving by increasing every tile with 1 each AI frame (the AI isn't evaluating all this stuff every frame that would be senseless so the AI will run on a different frame rate compared to the game). And then for all tiles seen by a unit it is set to 0. Even with a low resolution this gives a surprisingly accurate view of the AI's knowledge of the world. Based on this we could with reasonable probability estimate if the unit we are seeing is really alone or part of a group just behind my line of sight.
Also using a simple algorithm that searched the highest value/distance to the tile proved a very effective scouting algorithm that sweeps the play field booth doubling back to recheck earlier checked tiles and exploring the big unknown. A couple of units doing this made short work of an entire map.

Actually the algorithm described above can be used with great success for every unit in the game if we just check a different map. Obviously we did more stuff above this but with only the following simple algorithm you get a very interesting AI that will detail troops from a larger group to strike down enemies it encounters on the way without necessarily spending all its forces and forget its goal.

int myId=GetTerrainID(myPosition);

// gets the ID from the area map for that position
For(i=0;i
// could be all the tiles in the world or the tiles within a certain distance
{
  if(myBlockedMap[i]==false)
  {
 // well then I cant move there so skip this tile
     if(myEnemyBlockedMap[i]==false)
// the enemy is too strong here currently so I can't move there either.
      {
        if(myAreaMap[i]==myID)
// Make sure there is a path to the position before I continue
         {
               int eval=finalInfluenceMap[i]/distTo(i);
// influence divided by distance gives a good measure for how important that tile is for me right now
               if(eval>bestVal)
               {
// if this is the most promising tile for me to eradicate enemy influence store it.

                   bestVal=eval;
                   bestTile=i;
               }
           }
        }
      }
   }
}
myEnemyBlockedMap[bestTile]=true; 

//  Important step else multiple units might try to move to the same tile
// Give the unit an order to move to that tile.
// Or if you want to be fancy a position that is good for attacking that tile.


This code is deceptively simple but because your units detailed to deal with a force will block the tiles for other units you can't detach too large a force. Also once your units gets closer they will start to negate the influence at that point and troops that we have proved aren't needed anymore can move on to other targets. It all happens quite gracefully, almost like magic sometimes. Of course like all magic sometimes it fails and breaks down, but what can you expect from such a simple algorithm. But it is a good start for an RTS game AI.

While it is a sort of instant AI a lot of it behaviour depends on how you modify the maps governing its behaviour. You could for example put in the influence of a unit on the position it's decided to move towards to make certain that you won't send to many units, but then again only blocking tiles go far and you might get away with it. It might be better for the AI to send to many guys and let the rest move on than to send to few and get hammered. Obviously I wouldn't base an entire game AI on only this but it does look quite incredible in action. Especially considering it's nothing more than individual unit evaluations and some maps.

So how did we do it then? Well the AI was almost entirely influence based on some levels but we had booth higher level mission dynamics and request messages and a lot of stuff that would take way to much detail to cover here, so I will instead cover what we did with the influence mapping based part of the game. All combat was based on influence maps and the attack position data base. The influence map pointed a target and the attack position database found the best position to attack that target from.

We also always had our units grouped in squads this meant the AI never sent a single unit unless it was a squad that had been decimated. So the influence map worked on a slightly higher level allowing the grouping behaviour to seem more cohesive, this did loose some of the power however but it was an important trade-off for singe player.

We also analyzed the entire play field and all units on it and mapped them into groups (Because we had a platoon system we could optimize this a bit and only look at relevant units.) based on their location (and goal but again we will ignore that for now) This created logical combat groupings booth on the AI's side and the opponents side. Then for each group he decided what groups was to strong for him to attack and blocked the tiles those groups could attack so that they AI won't walk into an ambush. If they should be blocked or not was based on a calculation of the AI estimating it's percentage probability to win a battle, these percentages was different for different personalities. The percentages was also affected by the desperation factor if you are desperate you don't have time to be chicken. If we had a clear strong goal that was blocked we painted the earlier described circle around it in the goal map, units would mass there until the group became strong enough to fight the enemy at which time the block would be removed and the goal map reset to pointing to the goal and the AI troops would be storming in from all sides. Obviously any artillery he possessed could happily pound the encircled group while it waited on reaching its full strength.

Of course the opponent could do the same so we had code blocking tiles the opponent were currently targeting with artillery fire so the AI's unit moved out of the way. As you can see this isn't a perfect be all end all solution it still requires tweaking but it is a good start.
So this is what we can discuss about what we did the interesting questions however are what can we do now with all these nice maps we have created? There are endless possibilities but lets explore some of them. An obvious one is weighting the importance of a command point in the goal map based in its vulnerability, more vulnerable command points either needs more defence or are good targets for attack.

We might even change so that the value it calculates in the search isn't influence/distance but (influence+vulnerability) instead. The world is ripe with things to try out and that's probably the most important step to try them out and play around with them and see what you can use them for. I think that especially the higher level goal selecting AI can do a lot of nice stuff with this extra information.

We can also use the group concept we discussed earlier and move it to another level and making sure that the entire group gets a strong goal that is only for that group, this would be easy to achieve with a goal map per group this way we keep the flowing movements of the troops but we also get's focused troops going after specific targets and in this high level analysis the tension and vulnerability maps are essential.

I have given you a basis the rest is playing around with it and see what happens, remember to play around and have fun with your AI that is the key to success with it

2 comments:

  1. Great reading, can't wait to try this out!

    ReplyDelete
  2. Great article - but unless I'm misunderstanding something, wouldn't the basic algorithm you've given just cause the units to bunch up and not move?

    Since, the units tend towards the highest finalInfluenceMap value(= myInfluence - enemyInfluence + goals), wouldn't they always be attracted to each other, and run away from enemy units?

    ReplyDelete