Influence Maps
Influence Maps are a key component to tactical AI and can be used in many different ways. “An influence map allows the AI to see which areas of the game are safe (those that are very secure), which areas to avoid, and where the border between the teams is weakest (i.e., where there is little difference between the influence of the two sides)”.1 In essence, this data then allows AI algorithms to make smarter choices.
The sources we used are “Modular Tactical Influence Maps” written by programmer Dave Mark,1 “The Mechanics of Influence Mapping: Representation, Algorithm & Parameters” by Alex Champandard,2 and excerpts from “Artificial Intelligence For Games Second Edition” by Ian Millington and John Funge.3
From Champandard, we learned a small history of Influence maps, when and when not to use them, as well as a variety of uses that an influence map can give. The uses given were: 1, a quick summary of smaller details to describe who is in control of what area, where are the borders, how many enemies are in an area, 2, historical statistics such as how long ago an area was attacked, which can lead AI to create countermeasures or act more safely, and 3, future prediction such as the current trend of an influence letting the AI know where influence will most likely spread in the future. The article also breaks down the creation of an Influence Map and simple propagation of influence.2
From Millington, Influence Maps are discussed in tandem with tactical analyses. The book taught us how we can connect Influence Maps with other tactical analysis algorithms to produce even better results. For example, using a Frag-Map, a level can be tested offline to find the riskiest and safest locations on a map and can then be fixed into the level itself, eliminating runtime costs. The book also gives a more detailed explanation of map-flooding, which is used to propagate the influence of units with different parameters (such as a city having more influence than a village, etc).3
Dave Mark goes into a bit more depth into the creation and combination influence maps. Mark discusses working maps, which are “temporary, small map centered on an agent used to assemble and process information from multiple maps in the local area”.1pp. 353 Mark also explained the combination of multiple working maps using weights in order to get a more effective result. An example of a use for this is targeting. If a unit wants to cast an area of effect heal on allies, we would take the highest point on the casters working map which has taken into account the location of the allies. This will allow the healer to locate the center-of-mass of all of the allies and place the healing spell accordingly.1
A specific use could be that you want an agent to path-find a through an area that is riddled with enemy strongholds, influence maps can supply the nodes & connection on the graph with the relevant info to allow the agent to traverse the environment. Another example is wanting an agent to place a turret at the border of its territory. An Influence Map easily allows for that information to be presented to the unit.
This technique was most prevalent in RTS games like StarCraft. They allowed for more challenging and more believable AI battles. In recent years, however, it has been adapted to many different genres that involve faction based battles. Overall, it is not a terribly expensive algorithm, as it has to act on the map itself when units move and it does not visibly suffer from a 1 update/second run time.2 “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”.3pp. 520
If your game map has complex features such as obstacles or chokepoints, Influence Maps can be an outstanding addition in order to help your AI make smarter choices and to help deliver challenging fights to players. The uses of Influence Maps can span many game genres. Any games with faction based combat will benefit greatly from influence maps. Depending on the complexity, you can go from baking influence into a level with testing, or combine multiple working maps to help your ai make complex choices. The uses are innumerable.
Demo
-
D. Mark, “Modular Tactical Influence Maps” in Game AI Pro 2. Boca Raton, FL: CRC Press, 2015, pp. 343–364.
↩ -
A. J. Champandard, “The Mechanics of Influence Mapping: Representation, Algorithm & Parameters”, 2011. [Online]. Available: https://aigamedev.com/open/tutorial/influence-map-mechanics. May 19, 2011 [Dec. 12, 2018].
↩ -
I. Millington and J. Funge, Artificial Intelligence For Games, 2nd ed. London: CRC Press, 2016.
↩