Influence Maps I

In artificial intelligence one of the biggest problems is how to convert a complex world into a set of data that the AI can actually understand and work on. The real world or even a game world is infinitely complex and different techniques to compress that infinite data set into a usable format is a classic problem in ai research. Thankfully for games we don't have the trouble of having to interpret the image from a camera to create a 3dimensional world to move around in.

We have the advantage of having access to extremely detailed data of everything in the game. But the amount of data we have access to makes any sort of planning by the means of calculations impossible. The world is simply to complex, so in order to be able to work with it we have to employ a series of different algorithms the one we are going to look at today is called influence mapping and it's a way to resolve the actual strength relation ship on a map and helps to base tactical decisions on this. It has nothing to do with purchase planning or high level strategical decisions It's simply a analysis tool to create an accurate and usable view of the world.

Influence maps are based around the concept that objects in the game influences the strength relationships between the players and this influence spreads from their current position outwards throughout the map. If you add in all the influence of all the objects then you would get a view of the relative strength relationships for that part of the map. You should also be able to detect the actual front lines between the different sides with it too. As we will show later on we are able to calculate a lot of different data from the influence maps but for now I think it is time to go back to explaining how this all works. But as a tease in the end of this we will discuss how to create a simple army level opponent behaviour by only using influence maps. There will be limits to it of course but it is still pretty cool.


In artificial intelligence one of the biggest problems is how to convert a complex world into a set of data that the AI can actually understand and work on. The real world or even a game world is infinitely complex and different techniques to compress that infinite data set into a usable format is a classic problem in ai research. Thankfully for games we don't have the trouble of having to interpret the image from a camera to create a 3dimensional world to move around in.

We have the advantage of having access to extremely detailed data of everything in the game. But the amount of data we have access to makes any sort of planning by the means of calculations impossible. The world is simply to complex, so in order to be able to work with it we have to employ a series of different algorithms the one we are going to look at today is called influence mapping and it's a way to resolve the actual strength relation ship on a map and helps to base tactical decisions on this. It has nothing to do with purchase planning or high level strategical decisions It's simply a analysis tool to create an accurate and usable view of the world.

Influence maps are based around the concept that objects in the game influences the strength relationships between the players and this influence spreads from their current position outwards throughout the map. If you add in all the influence of all the objects then you would get a view of the relative strength relationships for that part of the map. You should also be able to detect the actual front lines between the different sides with it too. As we will show later on we are able to calculate a lot of different data from the influence maps but for now I think it is time to go back to explaining how this all works. But as a tease in the end of this we will discuss how to create a simple army level opponent behaviour by only using influence maps. There will be limits to it of course but it is still pretty cool.

So lets start with the default case, to keep everything simple we will for now assume that we are writing the ai for an RTS game where you command different kinds of modern war units with the goal of obliterating your opponent. So you have a unit doesn't matter what type yet just a generic tank or anything, this unit's spreads influence over the play field, the amount of influence he spreads is relative to his strength and how much he can affect the area so it fades away as we get further and further from the unit. As a side not for all the test images here I have been using the ancient game of GO as it allows me to place different colored bricks as unit's and easily measure the influence of them.

Here we have place a single black unit towards the upper corner for the rest of these examples the black units will be yours and you will be fighting towards the horrible evil white player. Your units project a positive influence around them which dissipates based on distance from the unit (we will later go into detail for different methods to decide how the dissipation should work).

We will soon be placing your opponents units too. As your units will project a positive influence your opponent will project a negative influence which means if the value of a position is 0 it is even if it is above 0 you are having more control and below 0 your opponent has more control. We have selected to use yellow to represent the positive values and blue as the negative values, and don't mind the + and 0 signs they are just leftovers because I base the images on GO.



TThis example feels pretty clear on the concept of how influence spreads through the playing field. I hope you can see that the influence actually moves all the way to the edge of the playing field it is just so weak there that it is hard to see it. This is a basis of some of the methods based on influence mapping because else it will be tough to detect where areas of influence meets. But in a real game in a filled world this won't really matter and we can save some performance.


Now however is time to talk about the playing field, since we are translating from an infinite world to simplify it then it makes sense that we should have a fixed resolution on the map we are using to keep our influence data. And this is the important step, the higher resolution you use the more details you have in the map however the more performance it takes to use and the less you can use it. And the smaller it is the more you can use it but the less information you can have. In both Ground Control 2 and World In Conflict  we used a 200x200 influence map on a 512x512 tiles play field. This allowed us to perform a lot of calculations while still maintaining a decent level of detail. However you will have to discover for yourself what resolution is suitable for your game, since all our visual examples are based on go they will have a 19x19 resolution this doesn't mean you should use this resolution, in fact it would probably be a horrible decision unless all you're after is a very very high level view.

Here we have added an opposing unit, notice how the white unit's influence is negating your influence creating a clear conflict zone in the middle between your forces. This image clearly shows that black is in control of the top and white is in control of he lower side. We can also see that there is some sort of conflict in the middle. We could even judge the intensity of the conflict by analyzing the gradients of the influence values. But we will later look at more efficient and reliable ways to calculate the tension of a tile. By now I think the basic concept of the influence map and how it works should feel clear however there should be a lot of question about the details like how far do I influence how does the dissipation of strength works etc. So I will try to cover it right now so you feel you can grasp the complete algorithm and then we will move onto more ways of using it.

First let’s make the dissipation process a bit clearer. Keep in mind while you are reading this that there are many ways of implementing the dissipation and none of them are really incorrect in fact after this paragraph I will discuss how dissipation worked in  Ground Control 2 and World In Conflict which will differ a bit from the base methods for reasons I will discuss later on.

First out is quite an easy dissipation method for every tile you move away from the original influence creator its value is divided with two. This has the advantage of making sure that every unit is somehow influencing the entire play field making sure that you can detect some kind of front line even if the opposing units are really far away from each other. So how does this look in practice?

The tile marked with the black circle is the originator tile where our unit is standing. So the tiles adjacent to it have 0.5 and the tiles adjacent to them have 0.25 and so on, in this case a diagonal tile isn't counted as adjacent. There is nothing that stops you from doing it like that though. In fact a diagonal tiles centre is 1.41 tiles away so it is probably more correct to count diagonal.  This method has some disadvantages though, it is hard to properly represent a unit that has a strong influence within a large area but doesn't really affect much outside of it like a stationary artillery piece. Overall you can’t easily map that the units full influence hits a certain area and then starts dissipating after that. These problems are what lead us to use a different view in World In Conflict.

We instead opted for a version where we could specify a influence strength and a fall off distance for that strength, in fact we had booth an area that was the full strength area of each unit and a fall off area after that. But to keep this image simply I have used only a single unit with an influence of 3 and a fall off distance of 3 as a side note despite me using floating point numbers for these diagrams in the real world I would instead use higher influence values so I could get away with integer numbers instead. One important part of the WIC method is that we calculated the true distance from the unit to the centre of the tiles, This means that you might not get your full influence value on a single tile if you where standing near the edge of a tile, it also meant that diagonal distances etc was taken care of correctly.

 

 Another approach is to take what is referred to as the manhattan distance which basically is how many tiles you will have to pass through to reach that position if diagonal moves are forbidden. Use that as a distance factor instead of the true distance. But no matter how we calculate the distance we still plug it into the formula below.

influence_contribuition(x,y)=UnitInfluence*_max(0,1-(FallOfDistance/(FallOfDistance-DistanceToXY)));

An interesting case that occurs is how should we handle if we have blocked tiles that we can't move too? This all depends on what you are mapping up with your influence but if it’s areas your unit can reach (and not areas it can shoot at) Then you need to find away to not give it influence to tiles that it can't reach. Using the Manhattan distance it is easy to do this as you just calculate the real distance to the tile considering that you can't move through black squares. This way your unit won't give undue influence (if you’re influence consists of two parts where one is where you can shoot and one where you can move you should only do this for the movement part, unless of course you are able to flag areas you cant shoot at too). In the image above we follow what happens in two cases here if we start out with the red arrow nothing changes because the block isn't increasing the path to the target, While the blue arrow has to take a large detour making it travel through 4 tiles instead of 2 negating it's influence.

Applying the same test to the Ground Control 2 & World In Conflict case we will notice that since they calculate the real distance it's quite hard to handle blocks correctly. You could perform a path finding to every tile and use that but that wouldn’t be useable. Since we mostly use influence to map out firing power in these games however it isn't such a big trouble and the influence only dissipates over the distance a unit can travel in a few seconds. This means that any obstacle that is big enough to mean anything would probably be big enough that the influence didn’t reach through it. Of course as time progresses we as programmers should be searching for better and better methods to perform our AI calculations so going with the above method makes sense if your circumstances differs.

Well all of this leads to the question how should we decide on what method to use and more importantly how do we want to cast our influence. Influence is supposed to mark what areas the unit in question can influence so lets start with that, If we for the time assumes a modern warfare game a unit should cast a strong influence everywhere he can shoot. If his accuracy is lower father away the influence should represent this since our goal is to represent the actual power of the unit at that place.

So a  reasonable Assumption is UnitPower*Accruacy(distance). Since we obviously don't want to perform that calculations on the fly it makes sense to make an area based approached. Where we use the full influence for everything within a certain distance and then dissipate it over a falloff distance until we have the power at the end of its firing range. However a unit can move around on the map which would make it influence areas beyond where it currently can fire. How much should be based on how far the unit can move and what type of game you are making. But as a basis this would make sense.

• FullInfluence Area described by two distances from the unit, normally 0 and a number depending on it's accuracy& attacking range.
• AccuracyDissipationArea during this area the influence dissipates from fullstrength to a strength determined by it's accuracy at that distance.
• MovementDissipation during this area the units influence dissipates from the lowest value of the earlier area to 0, The size of the area is depending on how fast the unit can move into a position where it has a firing solution on that position.

This is a good basis for everything  I just want to show a special case of all of this. In the case of an artillery piece he will be helpless vs. a unit that manages to come inside of his firing range and even if it ha some sort of mounted machine gun the influence of this unit in this area would be completely different from in the other areas.

T
This is the reason why the full influence area didn't have to start at 0 distance. For a case like this the dissipation areas needs to go in two direction booth increasing the max distance but also increasing the min distance to compensate for the fact that the unit can move backwards trying to get a firing solution. This will cause a circular band of influence that fades out towards it edges, just like the example we have here to our right. And if we do have units with weapons with radically different ranges we will have to add multiple influences for them but really you should be able to avoid that. Another interesting question is what do you do with a unit that can fire very far but sees very little, This means he influences those areas but only if he knows the enemy is there, The opposite is also true a scouting unit influence a large area by making units there visible but he can't fire in that area.  This is a really interesting problem without a perfect solution, but in many cases you can get away by making a simple approximation by adding together the view range and firing range and then dividing them with 2.

That kind of approximation however breaks down when you are looking at a unit like an artillery piece that can fire over a kilometre away but just spot for 200 meters, In these kind of cases you basically have two available options. One is to simply ignore it and say the artillery gives influence where it can fire and just assumes your spotting units will be doing a good enough work that you don't have to worry about this (The approach chosen in  GC2 and WIC) or you can actually calculate what tiles you have visibility of and add influence to them, this will have some issues however that if the opponent has buildings etc you know the position of your artillery can sill influence them as long as you know they are there, also it will play havoc with the frontline detection, You can avoid this by having  mask giving full strength to visible tiles and half to invisible tiles but this might be a lot of hassle for very little effect but it is always worth trying it and then deciding for yourself.

So what can we use this all for. Well I have talked a bit about front lines it is actually really easy to detect a front line it will be where the influence goes from being positive to being negative because this will be the point where the influences collides. But normally you aren't fighting on the whole area of the front line so we want to be able to pinpoint the part of the frontline where the tensions between the influences are the highest because that will be the strongest area of conflict. Tension can be seen as the difference in influence for the different sides at the point in question. So let’s take a look at what we need to calculate that. First of all we need to calculate the influence for booth sides separately so we can see for each tile how strong the influence of either player is.

To create the basic influence map we have been looking at earlier you just creates a map that contains your Influence - your opponents influence. You can however just add together the two influences to get a count of how high the tension is at a a point in the map(observe that in circumstances when there is no conflict on the map this will give the greatest assembly of troops as the highest tension which in a way is true because where there are many troops there's a big chance of something happening, a way to generate a tension map that avoids this problem is to multiply the 2 influences with each other instead, this will always result in 0 tension where only one side is located, the problem however might bee that very small changes in real world strength can make huge differences in the tension map. You can of course create any combinations of these too, but for the rest of this article we will assume that the tension maps we create are created using the algorithm originally described.).
There are many ways to combine those maps to analyse different stats of the battlefield but for this article we will keep it simple by just working with Influence, Tension and vulnerability.

As a raw strategic decision it's probably a good idea to send your reinforcements to the area that has highest tension, except the one problem with our tension map it will give a high tension even if our forces are superior there are a lot of ways you can calculate tension with all with their advantages and disadvantages. But if you have a frontline and there are battles going on or about to start the area with highest tension is very probable to be the proper area to attack. But the exact heuristics will have to differ from AI to AI the maps are thee just to give you a simple way to look at complex data.

This is a much complex battle than the one we used in our earlier example here black has mapped up area at the top as his while white has taken a solid control of the lower area, but whites third unit has gone deep into blacks sphere of influence partially negating it but it also has very little positive influence around itself, a clear sign that it is in danger especially with the frontline basically turning around it. Black’s front troop is in a slightly better situation because it has some form of backup from the leftmost unit. To a human the area with the most tension should be extremely clear here, but how will our algorithm work? Well the right image shows clearly that the strongest tension on the board is the one between the two central units.

Analyzing these kind of things is where tension maps excels, since everything in the end is just down to where you have high values in a two dimensional array (or one dimensional if you are like me but that’s an implementation detail)  it is extremely easy for the computer to calculate this kind of stuff. But before we jump up and down of happiness lets check how well the technique handles more complex cases. Since the technique scaled well with multiple units lets look at a map with multiple different areas of conflict and different areas of interest.

This time around we clearly have some quite complex conflicts going on we have a huge battle at the top left and a smaller one at the top right and looking at the map it can be considered to be divided into 3-5 areas with as many frontlines while the influence map properly finds and categorises these areas and frontlines for us it sadly can't help us much with what to do. But looking at the tension map we see that the battle in up the upper left is obviously the area of highest tensions with booth of the white groups creating a huge tension with the middle lack group, While there is some potential for conflict in the upper right the left it is dwarfed by the conflict in the left which seems to be of game winning /loosing potential. All of these can be clearly analysed by the computer from the tension map.

However we earlier mentioned a third kind of map vulnerability map, the objective of this map is to calculate which parts of the map that are most vulnerable no matter from which side's point of view you are looking at them. An easy way to calculate vulnerability is tension-abs(InfluenceMap) It will produce a high value where there is high tension but the sides are pretty equal while it will produce a lower value where there is high tension but one side is much superior.

Before we start looking at our vulnerability maps let’s quickly run through the different maps we have right now so there are no misunderstandings. To make it easy for me I will assume that the game is either 2 players or 2 teams competing, it can easily scale higher but it would be a lot of work to make all the text safe for all cases.

• My Influence
• All Influence coming from my units,buildings etc
• Opponent Influence
• All influence coming from opposing units,buildings etc
• Influence map
• Calculated as My Influence-Opponent Influence
• Tension map
• Calculated as My Influence+OpponentInfluence
• Vulnerability Map
• Calculated as Tension map -Abs(Influence map)
  

It turned out to be quite a few maps to calculate everything we want, but the positive side is that only My Influence & Opponent Influence needs to be calculated based on the units in the battle field, the rest are just functions acting on them and can either be quickly calculated or implemented as wrapper functionality above the original maps. So in the end you can keep the calculation costs at a decent level.

The vulnerability map can be used for many things like deciding where it is a good idea to build a new building or tower or to find opponent towers etc that are vulnerable for attack, Observe that after you have move your troops there it won't be vulnerable since it will have become on of your strongholds and it will start to get safer. Also notice that areas with high concentration of troops will get a higher value than areas with no troops since it means there is a larger chance of something happening there. If you are looking at a good position to make your charge versus, look for areas on the frontline with a high vulnerability. As always you have to use these maps with consideration the actual game you are working on.

You can also create a directed vulnerability map that will tell you where your opponent is weak but this will not differ as much from the influence map because you will have strong influence in those areas but if you want to play around try this formula Tension map +Influence map, It will give high values in area of conflict where you are strong and low values in areas of conflict where you are weak. For the rest of this article we will assume the original formula though.

As we can see the area with the great conflict and turmoil in the middle created by these two opposing units are the most vulnerable areas while the rest of the front line is also vulnerable these areas are the extreme parts. While the upper left corner and lower right corners feels like pretty safe areas. So if I want to build s safe base as white here I would place it around my two lower units and if I where black I would place it deep inside my area where it looks safe. And if there are any nice targets like a house in the big yellow area that is a prime area to attack.

In this example booth sides has slowly build up their strength created a very clearly defined front line. Our vulnerability map quickly identifies the battle towards the lower left and the frontline areas around it as the most vulnerable areas of the playing field. And this time around the map is filled with safe areas to create buildings and bases on. By now the vulnerability map is starting to look really good. We will just run it through the last example to be certain.

Even on this our worst case scenario the vulnerability map effectively separates out the uncertain areas and what could be called safe, Not that there is many of them on this battle field. One really nice feature of workings with maps like this is that you can combine them together for even more interesting positions for example if you look at the differences in booth the tension and the vulnerability map it's easy to analyse out where you want to place towers. You just place the tower where you think it should be recalculate the maps and evaluate the difference. To see the real world practical effect of your choice.

To be continued later on :)