Influence Maps
What are Influence Maps?
When it comes to games where strategic AI is needed, an AI must see a representation of a game world to make decisions. Influence maps, as the name implies, help influence an AI’s decision on what to do given the circumstances of a game's level. Data about a game’s world is used to construct a map that’ll display information in a readable format for the AI.
Where to use Influence Maps
Influence maps (also known as tactical analysis) can be used to represent various things about a game's world. You can use them to perform terrain analysis and calculate where it is more difficult to travel in a game world. Visibility can also be mapped out using terrain analysis, which can tell AI what it can see, and how well it can see at certain points (Millington, 521). Another common application of influence maps is mapping out enemy territory. Influence maps work great with team tactics as the same map can be used for each enemy's decision on where to go. This is useful in real-time strategy games (RTS) as influence maps can help map out both difficult terrain and weak points in an enemy's territory to decide an attacking point to advance upon. They are also used in squad-based shooters, some of them being first-person shooters, for the same reason.
Techniques
When making an Influence map, we need some way of actually representing influence to the AI. Influence spreads over a distance until it becomes too small to care about. This can be represented as a number, but first, we need a base node/cell to start. Nodes and/or cells represent locations in the game's world. From a base node/cell, we can propagate influence on other nodes/cells it is connected to. One method of doing this is called the limited radius of effect, where each influencer has a radius in which it infects its surrounding nodes with its influence. A drop-off formula is used like this to calculate that influence over distance.
Here is an example (example by Kent):
influence = max_value – (max_value * (distance / max_distance)
There are also other ways to calculate drop-off over a distance (some are more expensive than others). Another method of spreading influence is more commonly found in graphics programming. Gaussian convolution filters can be used as a way to spread influence as well. This is usually done by mapping each cell of a map with a kernel and weighing it depending on what influences are sampled near it. The last method of influencing a map is map flooding. This method is a simplification where any influence made by a target is equal to the largest possible influence that can be made (Millington, 516). This can lead to some dangerous results but is by far the most optimized approach.
Influence maps, no matter how you break them down, can be expensive on the CPU. Especially when it comes to dynamic properties on a map where those influences have to be updated frequently. Map properties that don’t have to be updated constantly, like some terrain elements should have their influence calculated once during a level start-up. Influences that move/spread slowly should be interruptible so that way a game can focus resources into more important things while influence propagates and evolves slowly (Millington, 524).
Different influence maps can also be combined to create a summary of all dangers that are present in a map. This is useful for looking at data as a whole versus looking at each individual map for deciding on a target.
Limited Radius Effect
Gaussian Convolution Filter
Flood Mapping
Tech Demo
For my tech demo, I ended up making some AI with the goal to avoid the player. After developing the game, SNIPERPUNK, for about a year and a half, I got a good feeling about how the game should be played and where disadvantageous spots belong in maps. First, I created my own node-based pathfinding system in Gamemaker in order to have things to propagate influence to. This gave me more control over my path-finding system too.
Node Pathfinding Map
I ended up using the map flooding technique for my influence maps as I found them to work more easily with nodes than grids (I used nodes because they are faster than automatic grid systems). Tight corridors would be marked as having some influence as this would be a slightly disadvantageous spot to stay as bullets can easily overwhelm players with little movement options at their disposal. Two other influence maps I made were based on the player. Danger zones were placed on the node closest to the player and propagated out once to each of the connecting nodes. This was here to prevent the AI from pathfinding through the player since the goal is to avoid them. Last, all nodes visible from the player were influenced all with a single value. Influence is a value that belongs to nodes that maps changed directly.
Terrain Influence Map
Danger Flood Map
Sight Flood Map
Everything Put Together
With the influence maps built, we could make certain decisions based on the influence value of the affected nodes. If the AI was in sight of the player, it would automatically configure a path to an open node not under the player’s influence. After that, it will path to a far away node to try to move away from the player. If the AI opponent sees the player, it will fire as fast as it can to discourage the player from chasing it. If the player decides to not pursue the AI, the AI will shoot phase rounds through the walls in order to get the player to move. When the player moves, the influence map changes, which makes the AI move elsewhere. This should make engagements meaningful.
One optimization I did to my influence maps was to make it so that only one dynamic map was updated per frame. In the future, I will probably also partition these updates over a couple of frames, since sight influence can probably get away with updating less than every other frame. Moving forward, I would also want to organize my decision-making into a behavior tree. This will organize the admittingly messing decision code I wrote for this demo, and it would also open the gates for more modular AI.
Sources
Champandard, Alex. “The Core Mechanics of Influence Mapping.” GameDev.net, 8 June 2011, https://www.gamedev.net/tutorials/programming/artificial-intelligence/the-core-mechanics-of-influence-mapping-r2799/.
Kent, Harry. Harry Kent, https://harrykent.games/game-ai/influence-mapping/.
Millington, Ian. AI for Games. Third ed., CRC Press, Taylor & Francis Group, 2019.