Introduction: What are Influence Maps?

How fun would a strategy game be if the AI sat there or just acted randomly? Probably not that fun. But I would argue that it’s more fun than an AI knowing absolutely everything and acting like a robot. The average AI should be somewhere between being a total rookie and a grandmaster. Part of the answer to making a “human-like” AI is the use of Tactical Analysis (AKA influence maps). The simplest example of an influence map I can conjure up can be seen on the right

In this case, a unit is on the grid (where the influence is highest). From there, its influence decays as it spreads into the neighboring tiles. If more units were present, their influence could combine (if they are friendly) or combat (if they are enemies). What this allows is a representation of the state of a graph/world/combat in a numerical way that an AI can analyze.


While in my initial example I used units, influence maps are not limited to just military units. Alex Champandard’s article on gamedev.net talks about three broad categories that influence maps could fall into: situation summary maps, historical statistics maps, and future prediction maps.
For this project, my tech demo focused on Situation Summary maps
Example Influence Map
Situation Summary:
“Who is in control of what area? Where are the borders between the territories? How much enemy presence is there in each area?” (Champandard). Can also be used to find where the valuable places are.
Historical Statistics:
“Influence maps can also remember what happened for a certain period of time. Was this area being assaulted? How well did my previous attack go?” (Champandard). By storing and comparing influence maps (e.g. to see where the most territory is being lost/gained) historical data can be obtained and acted on.
Future Prediction:
“Using the map of the terrain, you can figure out where an enemy would go and how his influence would extend in the future” (Champandard).
Screenshot of regular map
Screenshot of map with influence overlayed
An example map made in my tech demo. It contains mountains, trees, lakes, fields, and an outpost.
The influence map, specifically for logging, overlaid onto the example map. Orange is where the most logs are. Uses a set radius and sqrt dropoff to calculate influence.

How to Calculate Influence?

Millington writes about three equations to calculate the influence of a square (from a specific source of influence). They are listed on page 513 and examples can be seen on the right.


For my tech demo (the example influence map seen above), I used the sqrt dropoff method. Since it requires a square root, this is the most expensive method. However, because I was working with such a small arena, the loss of efficiency was ignored.


Just doing the base implementation brings about some issues with performance. According to Millington, “execution time is O(nm), and memory is O(m), where m is the number of locations in the level, and n is the number of units” (514). This will pose a big issue if the grid gets large and enough units are placed. However, there are a few ways to improve this.
First off, influence maps do not need to be calculated every frame. For most large-scale decision making, influence can be calculated as needed. Because there can be time between each query, the influence mapping process can be interrupted allowing for the game to still run smoothly (Millington, 524).


There are also ways to alter the speed of processing. Millington also lists three methods for this on pages 514 to 516 . I implemented one of them and the article by Alex Champandard implements a different one. The three methods are:
Examples of the radius and convolution filtering methods can be seen below:
Example showing linear drop off Example showing sqrt drop off Example showing exponential dropoff
Radius influence gif
Convolution filtering influence gif
Switching between different influence maps with influence determined by the radius method
Convolution method (from Champandard's article)

Genres and Platforms

All my sources listed the RTS genre as the starting place of influence maps which makes sense. Influence maps allow for dynamic reevaluation of a game world which is important when trying to do strategy in real time. There are a few cases where influence mapping might not be required. If the map you are implementing is really simple, you don’t really need to map it out (Champandad). For example, if everything takes place on an open plain, just use distance based calculations. Any game where the AI does not have to make complicated decisions probably does not require any kind of influence mapping (e.g. platformer where enemies follow a path or behavior that can be implemented using a behavior tree).


One interesting application I found is a paper about using influence mapping during pathfinding. What it found is that, “Influence map-based pathfinding opens a new possibility in pathfinding. Paths become aware of their surroundings, events or game specific characteristics (e.g., sound, faction location, line of sight, etc.). Game agents are therefore better informed at path planning, and changing the way they navigate through their environments.” (Adaixo, 44). A lot of resources focused on units but as shown in my tech demo, it can also be used for decision making on a higher level (an AI figuring out where to expand). In an FPS, the enemy AI might be able to use influence mapping to make more calculated decisions against a player.


As stated before, the base efficiency of influence maps is pretty bad although it can be improved. For split-second decisions, AI should probably delegate to something faster like a behavior tree. Because most parts of the algorithms can be interrupted, I think it could be adapted to a tile-based or strategy mobile game even though mobile devices do not have fast hardware. Influence maps overall have a lot of flexibility and potential and so should be considered a lot of the time when implementing an AI.

Works Cited:

Champandard, Alex J. “The Core Mechanics of Influence Mapping.” GameDev.net, GameDev.net, 8 June 2011, https://www.gamedev.net/tutorials/programming/artificial-intelligence/the-core-mechanics-of-influence-mapping-r2799/.
This really was a great resource. The article contains a video going through it. Additionally, there is a talk done at GDC by him covering the same topic.

Adaixo, Michael. Influence Map-Based Pathfinding Algorithms in Video Games. 2014. https://ubibliorum.ubi.pt/bitstream/10400.6/5517/1/3443_6881.pdf
Millington, Ian. AI for Games. CRC Press, 2022.