Jump to content

  • Log In with Google      Sign In   
  • Create Account

Like
8Likes
Dislike

The Core Mechanics of Influence Mapping

By Alex J. Champandard of AIGamedev.com | Published Jun 07 2011 10:00 PM in Artificial Intelligence

influence maps map you' algorithm game grid information
If you find this article contains errors or problems rendering it unreadable (missing images or files, mangled code, improper text formatting, etc) please contact the editor so corrections can be made. Thank you for helping us improve this resource

[This tutorial and its accompanying video (on the last page) were produced by Alex J. Champandard, Technical Director at AiGameDev.com. If you'd like to find out more about game AI, don't miss his free interviews and masterclasses (almost) every weekend!].

Influence maps have been around since the very early days of game AI, tracing their history back to real-time strategy games over a decade ago. Since then, influence maps have become a cornerstone technique for game developers, and are even starting to become prevalent in first-person shooters as well (e.g. KILLZONE 2/3).

In this tutorial, you'll learn about some of the motivation for influence maps and why they are so appealing. You'll also find out when to use influence maps, and what representation fits best with your game. Then, you'll see the algorithm in action as well as its most important parameters that you'll need to tune when using influence maps in your game.

Motivation

Influence maps ultimately help your AI make better decisions by providing useful information about the world. In particular, influence maps provide three different types of information that are particularly useful for decision making:
  • Situation Summary — Influence maps do a great job of summarizing all the little details in the world and making them easy to understand at a glance. Who's in control of what area? Where are the borders between the territories? How much enemy presence is there in each area?
  • Historical Statistics — Beyond just storing information about the current situation, 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?
  • Future Predictions — An often ignored aspect of influence maps, they can also help predict the future. Using the map of the terrain, you can figure out where an enemy would go and how his influence would extend in the future.
As you can imagine, each of these different properties of influence maps helps the AI perform its threat analysis calculations in a much more intelligent way. Since these are factors that we take into account as human players, it should also help the AI!

Attached Image: IM_Motivation.huge.png

Why Not Influence Maps?

If you're already convinced about the benefits of influence maps, you should probably take a second to pause before implementing them. There's one reason that you wouldn't really need them in your game; if the world is too simple you just don't need a "map" for it. This is the case for large open terrains with the occasional tree, for example.

In general, you need an influence map in the following cases:
  • If your graph has varying connectivity, and not just a 2D grid with all its connections traversable.
  • If your world has interesting features like choke-points, large open areas, large obstacles.
Otherwise, you can use simple distance-based equations in your AI decision making to reason about the world. There's no need for the overhead of an influence map in memory, nor its computational cost.

Attached Image: IM_Terrain.huge.png

Representation

High-precision grids, rough area graphs, waypoint networks, or a coarse grid in space; all are sensible options for representing an influence map. There are more options too! Generally there are two things you need from your influence map representation:
  • Spatial Partition — A way to easily and efficiently partition space and store information (i.e. influence) for each partition. This allows the influence map to store information about the past, gathering statistics about what happened.
  • Connectivity (optional) — An indication of connectivity between these spatial partitions in space. The connections allow the influence mapping algorithm to predict how influence could spread through the level, predicting what could happen in the future.
Obviously, the important question is which is the best choice for your game? Generally, the more precise representations will be useful for low-level decision making, and larger partitions will be better suited to high-level decision making.

a) 2D Grids

Attached Image: IM_2DGrid.huge.png

This is a great default representation if you can map your world to a mostly 2D environment. It's a very fast representation to process and very simple to implement. The downsides, however, are that you may waste memory if you have sparse environments.

b) Area Graphs

Attached Image: IM_AreaGraph.huge.png

If you have a navigation hierarchy in place already, then you can use that as the basic representation for the influence map. The advantage of this approach is that it's not a very intrusive change and can easily be incorporated into most game engines. The disadvantages are the lack of precision in cases where details are required for the decision making.

c) Waypoint Network

Attached Image: IM_WaypointNetwork.huge.png

Using a full waypoint network in 3D resolves some of the problems with 2D grids, as you can easily wrap a waypoint network over multiple levels of a building or upstairs. However, the downside is that it's much less efficient to process than both a grid or an area graph.

d) Coarse Grid

Attached Image: IM_CoarseGrid.huge.png

One last option is to decrease the resolution of the grid. Unfortunately, this causes certain grid cells to span over obstacles, which can cause problems when updating the influence. The alternative is to remove those split cells from the representation, but certain connectivity may be lost because of it. Using these cells as disconnected buckets in space to store influence is also an option, though it rules out predicting the spread of the influence in the future.

The Algorithm

Fundamentally, the algorithm is similar to a blurring process that you can find in photo editing software like Photoshop. You start by setting the influence values in your map, and then repeatedly blur the map to spread the influence from the source towards neighboring nodes.

The influence mapping algorithm is actually pretty flexible. It's made up of two different steps, but you can run those steps in any order you see fit and customize them quite extensively.

1) Setting Influence

Attached Image: IM_SettingInfluence.huge.png

Typically, the first step is to set the influence sources inside the representation you chose. It's as easy as storing or updating a floating point number in an array of influence values. The only challenge is figuring out the influence sources for your game. Often these sources can be:
  • Entities, both friendly and enemy soldiers, semi-permanent turrets, etc.
  • Events like grenade explosions, bullet fire, taking damage.
You'll also need to figure out which of these influence sources are additive (layered on top of the existing influence) and which are reference (set as the base influence value). That depends on your game, but temporary events like bullet fire are well suited to additive influence.

2) Propagation

The propagation algorithm itself is very simple, and fits in less than a page of code. There are many different ways you can implement this, and many variations would also work fine... but this is a good place to start:

void InfluenceMap::propagateInfluence()
{
  for (size_t i = 0; i < m_pAreaGraph->getSize(); ++i)
  {
	float maxInf = 0.0f;
	Connections& connections = m_pAreaGraph->getEdgeIndices(i);
	for (Connections::const_iterator it = connections.begin();
		it != connections.end(); ++it)
	{
	  const AreaConnection& c = m_pAreaGraph->getEdge(*it);
	  float inf = m_Influences[c.neighbor] * expf(-c.dist * m_fDecay);
	  maxInf = std::max(inf, maxInf);
	}

	m_Influences[i] = lerp(m_Influences[i], maxInf, m_fMomentum);
  }
}
Attached Image: IM_Propagation.medium.jpg

A few things to note:
  • You need double buffering if you want your influences to be calculated correctly. You can do that by setting the new influence values in a local store, then copying it back into the m_Influences array. If you do an extra propagation step each frame, then you can avoid the copy (at the cost of some extra processing).
  • Without double buffering, the influence may propagate differently depending on the order of your graph nodes and how you process them. This makes the influence on a grid look a bit more irregular, but nothing fatal! If you're looking for some extra performance this may help a bit in practice.
  • Here the code uses exponential decay for the influence, which has some nice properties. However, it's a bit slower than linear decay for instance, which only requires a division and not an exponential function.
  • The code above only handles positive influences and their propagation. If you need to handle negative influences also, then you could also accumulate the minimum influence and combine them together.
Parameters

The only challenge left is figuring out the parameters for the code snippet above. Here's a breakdown of the most important ones you need to keep in mind.

a) Momentum

Attached Image: IM_Momentum.huge.png

When you update the influence value, how much do you bias the update towards the existing value compared to the new value? The code above uses linear interpolation to blend from the current value to the new value, and then relies on the momentum parameter to control the result.

If you set the momentum to high (closer to 1.0) then the algorithm will bias towards the historical values of the influence, which is particularly well suited to storing statistics about previous attacks. Use this for things like high-level strategic maps. Conversely, if you set the momentum parameter to low (closer to 0.0) then the algorithm biases towards the currently calculated influence, so the propagation happens quicker and the prediction is more accurate. Use this for low-level influence maps for individual positioning for example.

b) Decay

How quickly should the influence decay with distance? In the code snippet above, this is controlled by a multiplier to the distance before it's passed to the exponential function, so you can control how quickly the influence fades.

Typically, you'll use different decay values based on the size of your influence map. Lower decay for larger strategic maps, and higher decay when the map is localized and used for tactical purposes. If you'd like influence to spread differently per-unit then most likely you'll need different influence maps for that, or a customized algorithm that stores additional information per cell.

c) Update Frequency

The parameter you'll have the least control over, is the update frequency. This will depend on how many resources you have at your disposal for updating the AI. Luckily, influence maps can scale down relatively well, but there's a base amount of computation that needs to be done to get good quality information.

Most often, you'll update high-level strategic maps less often, for example at 0.5Hz to 1Hz. Then, at the low-level for the tactical maps that individuals use, consider doing that at 2Hz to 5Hz. No influence maps really need to be updated at 30 FPS!

Attached Image: IM_UpdateFrequency.huge.png

Tutorial Video

http://vimeo.com/23913640

Conclusion
  • Influence maps are particularly easy to get up-and-running! It's less than a page of code.
  • You'll most likely end up with a variety of different influence maps to provide better information to your AI.
  • Pick your map representations wisely, though a 2D grid and your existing area graph are the safest bets.
  • Expect a lot of iteration along with the AI decision making as you tweak the parameters of your influence map.
If you have any questions on the topic of influence maps and their use for spatial decision making, don't hesitate to ask here or via Twitter!





Comments
This is really awesome! I wouldn't even have thought about using it as an implementation of "history" either.
This a tremendous tutorial thanks for that, I still got a doubt, what tool did you use to make the representation of the Influence Maps concept you are explaing? Looks pretty neat and upper class ;) Also what language did you use to code? Or that just a pseudocode?

Well hope you answer my doubts :)

fr33
fr33,
The videos and screenshots are taken from The AI Sandbox, which we've been developing at AiGameDev.com over the past few years. The algorithm in itself for creating the grid representation of various sizes is extremely simple (a page of code) and the code for creating the areas and waypoint graph is based on some stuff I did in KILLZONE 2, and that William van der Sterren came up with himself before. It's an incremental area clustering algorithm:

http://aigamedev.com/open/articles/terrain-area-generation/

The algorithm for creating areas isn't that complex, and there are multiple ways of doing that successfully. You could also use a similar approach that navigation mesh generation tools use, for example Recast.

I hope that helps!

Alex
fr33,

Also what language did you use to code? Or that just a pseudocode?


I think it's plain c++.

2016-3-22 leilei

gucci borse stephen curry shoes ralph lauren cartier glasses christian louboutin shoes canada goose uk converse sale coach outlet online coach factory outlet coach factory outlet coach factory outlet online ed hardy uk true religion jeans michael kors bags coach outlet ray ban sunglasses skechers outlet louis vuitton borse lacoste shoes ralph lauren outlet ray ban sunglasses jimmy choo outlet store christian louboutin uk polo ralph lauren outlet ugg outlet online instyler max timberland boots michael kors handbags polo ralph lauren polo ralph lauren outlet toms outlet louis vuitton pas cher ray ban sunglasses mont blanc pens prada uk longchamp levis 511 toms shoes ugg sale ray ban sunglasses nike blazer louis vuitton handbags rolex watches nike store uk toms shoes fitflops clearance nike air max 95 ray ban outlet cheap basketball shoes fitflop uk christian louboutin outlet converse uk louis vuitton handbags michael kors outlet ray bans under armour outlet michael kors handbags michael kors supra for sale true religion jeans michael kors handbags true religion michael kors outlet reebok classic michael kors outlet micahel kors adidas gazelle pandora jewelry adidas trainers omega speedmaster supra shoes kate spade outlet ralph lauren pas cher oakley outlet ray bans louis vuitton handbags michael kors watches discount oakley sunglasses coach purses on sale nike huarache ray ban outlet ghd hair straighteners oakley sunglasses nike roshe run michael kors bags coach outlet online cheap jordan shoes michael kors bags toms outlet air max 90 michael kors handbags reebok shoes michael kors louboutin calvin klein dresses coach outlet hollister uk prada handbags michael kors outlet online ghd flat iron omega watches white converse lacoste polo shirts lululemon sale coach outlet online lululemon outlet babyliss pro canada goose sale coach outlet online adidas superstars nike cortez shoes canada goose jackets canada goose sale hermes outlet burberry outlet coach factory outlet rolex daytona salvatore ferragamo sac longchamp michael kors outlet babyliss flat iron louboutin pas cher prada handbags mcm handbags fitflops outlet ray ban sunglasses asics gel kayano cheap oakley sunglasses prada outlet louboutin outlet adidas shoes mizuno running shoes converse shoes michael kors outlet coach outlet michael kors outlet coach outlet store online toms outlet store nike running shoes ralph lauren outlet longchamp outlet oakley store kate spade outlet burberry uk polo outlet kate spade outlet online michael kors outlet online ralph lauren uk fitflop shoes fitflops shoes true religion jeans ralph lauren hermes belt valentino store christian louboutin uk michael kors watches armani jeans louis vuitton bags michael kors handbags versace jimmy choo shoes asics shoes converse shoes nike free runs kate spade outlet michael kors outlet burberry outlet online burberry outlet cheap ray bans michael kors bags levis jeans gucci outlet online ray ban sunglasses outlet michael kors outlet clearance calvin klein outlet michael kors handbags sac longchamp pliage christian louboutin polo ralph lauren outlet ferragamo shoes longchamp bag nike air max 90 nike tn pas cher air max 90 michael kors outlet hollister clothing coach factory outlet air jordan shoes oakley sunglasses wholesale reebok outlet cheap oakley sunglasses cheap jordans timberland uk coach outlet online toms outlet pandora charms michael kors handbags ecco shoes coach outlet online ray ban outlet michael kors outlet online puma shoes louis vuitton kate spade handbags burberry outlet handbags coach factory outlet online coach outlet online ed hardy jordan pas cher armani exchange nike trainers reebok shoes designer handbags outlet coach outlet store online burberry michael kors coach outlet ugg outlet michael kors handbags oakley sunglasses sale coach outlet store online michael kors outlet michael kors outlet under armour shoes bottega veneta fitflops outlet burberry outlet valentino shoes coach factory outlet online new balance shoes kate spade outlet vans outlet rolex replica watches abercrombie & fitch coach outlet store canada goose uk converse sale vans shoes ralph lauren outlet coach factory online prada handbags on sale polo ralph lauren marc jacobs handbags jordan shoes coach outlet fitflops sale air max chaussure louboutin coach factory outlet ture religion outlet michael kors outlet hollister clothing store cartier watches chi flat iron nike force 1 true religion outlet

عمل جيد وممتاز مرحبا بكم جميعا في العاب بنات

http://bit.ly/1W9i4Xx
http://bit.ly/1WIiSlZ
http://bit.ly/1TOtSbq
http://bit.ly/258USdF
http://bit.ly/1s1RJ0U
http://bit.ly/1qBWahB
http://bit.ly/1VeFRUB
http://bit.ly/22jSQFF
http://bit.ly/1YNc3h2
http://bit.ly/1ORt8pN
http://bit.ly/1NEqV0y
http://bit.ly/1OGrW37
http://bit.ly/242rjIa
http://bit.ly/1XIPXxM
http://bit.ly/258V6kZ
http://bit.ly/1TrA9Ky
http://bit.ly/1U6wC3J
http://bit.ly/1WJDvPh
http://bit.ly/1TOu1eN
http://bit.ly/1XpgmAb
http://bit.ly/1WIiYtP
http://bit.ly/1Tv9r5W
http://bit.ly/27Mmfwk
http://bit.ly/25fAR8E
http://bit.ly/1XIQ9gz
http://bit.ly/1U6wktv
http://bit.ly/258VnEt
http://bit.ly/1XpgAqU
http://bit.ly/1TmTXnI
http://bit.ly/1ORt0Xi
http://bit.ly/1TmUA0q
http://bit.ly/1U6wykp
http://bit.ly/1OGs6HL
http://bit.ly/1TrAtJb
http://bit.ly/1U6zv7m
http://bit.ly/1s1S1ow
http://bit.ly/242s83y
http://bit.ly/242rzqC
http://bit.ly/25fANFT
http://bit.ly/1ORtkoN
http://bit.ly/258Vpfw
http://bit.ly/1qBWg8R
http://bit.ly/1OGrVfC
http://bit.ly/1TmUiXy
http://bit.ly/27MmszA
http://bit.ly/1ORtEUN
http://bit.ly/258Vr78
http://bit.ly/1XIQArg
http://bit.ly/1TrAEUY
http://bit.ly/1s1RJxT
http://bit.ly/1ORtlcs
http://bit.ly/1WIj4BM
http://bit.ly/1YNcR5s
http://bit.ly/1RgEHRu
http://bit.ly/1TA56zG
http://bit.ly/1Tv9y1u
http://bit.ly/1TOuk9E
http://bit.ly/20laBTo
http://bit.ly/20lbbkb
http://bit.ly/1OGrTV4
http://bit.ly/1TrAL2T
http://bit.ly/22jTe7b
http://bit.ly/25fB2kh
http://bit.ly/25fBbEo
http://bit.ly/1RgEhur
http://bit.ly/1U6zVdW
http://bit.ly/1XpgmQJ
http://bit.ly/1ORtqgm
http://bit.ly/242rUcU
http://bit.ly/1XpgZcX
http://bit.ly/27MnHPc
http://bit.ly/1WJDX00
http://bit.ly/1s1SqY3
http://bit.ly/1U6zCA0
http://bit.ly/1TOuM7O
http://bit.ly/1TA4Qkk
http://bit.ly/1OGshmg
http://bit.ly/1NEryqY
http://bit.ly/1U6wvoO
http://bit.ly/1XIR806
http://bit.ly/1OGsnKI
http://bit.ly/20laPdf
http://bit.ly/1NErzv7
http://bit.ly/1RgF4LU
http://bit.ly/1NErh7l
http://bit.ly/25fBFu5
http://bit.ly/1WIjHew
http://bit.ly/1ORtywm
http://bit.ly/1ORtFIc
http://bit.ly/1WIjp7y
http://bit.ly/1W9j79O
http://bit.ly/20lb7Rj
http://bit.ly/1NErGqv
http://bit.ly/1U6wHV5
http://bit.ly/1TA5Ch5
http://bit.ly/1sMlyTW
http://bit.ly/1Tvapz6
 


Note: Please offer only positive, constructive comments - we are looking to promote a positive atmosphere where collaboration is valued above all else.




PARTNERS