From http://aigamedev.com/open/tutorial/influence-map-mechanics/
can i make a few suggestions/corrections?
when you are getting the neighbors you forgot to get two diagonals, you get the diagonals for (x-1,y-1) and (x+1,y+1) but not for (x-1,y+1) and (x+1,y-1).
after doing that it gets a bit better but, i noticed how, if you test using only the mouse, the shape is all weird and fades into the lower left corner… this is because you didn’t put any second buffer for the calculations of influences, so basically you are calculating and changing the values at the same time, which means the values depend on the order of the calculation, this is why the influences fades into that corner. setting up a second vector of values to store the calculations temporarily and only after all is done switch the values of the buffers corrects this
after this all is fine, except now the fade has this square looking shape, which is to be expected since you are considering all neighbors to be at the same distance, which isn’t true since diagonals are a bit further, so adding a third value of distance where diagonals have a value of 14 and axis a value of 10 (you could change it to float and have it 1.4142 and 1.0 respectively) and calculating the exponential value considering the distance gives us this nice sphery/stary looking shape
thx for your initial project :]
Haha, wow, I actually have no idea how to do what you just said. Is it ok if you share your corrections?
xD, ok i’ll try to explain in more detail now
this is what you have right now:
notice how the diffusion of the map is all weird, it’s strong on some diagonals and it seems to fade primarily into the lower left corner
on closer inspection i noticed how you forgot to find the neighbors for two of diagonals
your code:
// diagonals
if (x > 0 y > 0)
{
retVal.Add(new Vector2I(x-1, y-1));
}
if (x < _influences.GetLength(0)-1 y < _influences.GetLength(1)-1)
{
retVal.Add(new Vector2I(x+1, y+1));
}
so the first thing i did was to correct this by adding the missing diagonals
my change:
// diagonals
if (x > 0 y > 0)
{
retVal.Add(new Vector2I(x-1, y-1));
}
if (x < _influences.GetLength(0)-1 y < _influences.GetLength(1)-1)
{
retVal.Add(new Vector2I(x+1, y+1));
}
if (x > 0 y < _influences.GetLength(1)-1)
{
retVal.Add(new Vector2I(x-1, y+1));
}
if (x < _influences.GetLength(0)-1 y > 0)
{
retVal.Add(new Vector2I(x+1, y-1));
}
this is what you get:
now you can see the strength of the diagonals is more even out, BUT it has a weird shape doesn’t it? if you look at the center of the diffusion you can notice it better, the values still look like they are being pushed to the lower left corner… this happens because you are not double buffering the map, what i mean is that you calculate the influence for a certain cell and you change it’s value right away, so the next cell in line will now consider some of its neighbors with old values and some with new values, mixing up everything and giving odd results, influence calculation should not depend on which order do you read and write from the matrix, this is when you need a second matrix (double buffer technique) one to read from and another to write to
so i created a second matrix with the name _influenceCalc and here is the main trick:
public void Propagate()
{
UpdatePropagators();
for (int xIdx = 0; xIdx < _influences.GetLength(0); ++xIdx)
{
for (int yIdx = 0; yIdx < _influences.GetLength(1); ++yIdx)
{
//Debug.Log("at " + xIdx + ", " + yIdx);
float maxInf = 0.0f;
float minInf = 0.0f;
Vector2I[] neighbors = GetNeighbors(xIdx, yIdx);
foreach (Vector2I n in neighbors)
{
//Debug.Log(n.x + " " + n.y);
float inf = _influencesCalc[n.x, n.y] * Mathf.Exp(-Decay); //* Decay;
maxInf = Mathf.Max(inf, maxInf);
minInf = Mathf.Min(inf, minInf);
}
if (Mathf.Abs(minInf) > maxInf)
{
_influences[xIdx, yIdx] = Mathf.Lerp(_influencesCalc[xIdx, yIdx], minInf, Momentum);
}
else
{
_influences[xIdx, yIdx] = Mathf.Lerp(_influencesCalc[xIdx, yIdx], maxInf, Momentum);
}
}
}
for (int xIdx = 0; xIdx < _influences.GetLength(0); ++xIdx)
{
for (int yIdx = 0; yIdx < _influences.GetLength(1); ++yIdx)
{
_influencesCalc[xIdx, yIdx] = _influences[xIdx, yIdx];
}
}
}
see how i save the information on _influence BUT i use _influenceCalc to get the values, and obviously _influenceCalc must be updated at some point, i do it with a new cycle at the end… this technique has it’s costs obviously but look how the map looks now:
much more even on all sides :] now the map is working just fine, there is just one small problem, if you use a map like this to decide how a character should move by looking at the values of adjacent cells you’ll see it preferring walking horizontally or vertically because with this map the higher value cells is ALWAYS at perpendicular position EXCEPT when the character is sitting exactly on the diagonal of the map, where the higher value cell is ALWAYS at the diagonals… so basically the diagonals of the map function like magnets meaning the a character would always walk towards the diagonals first and only then walk to the center of the map diagonally 
this happens because currently the map is considering all neighbors being at the same distance of any given cell, which is not true because diagonal cells are a bit more distant, 1.4142 times more to be more exact (squareroot of 2).
there are two ways of solving this (3 actually), the first one is to completely ignore diagonals altogether, if you comment out the code to get the diagonal neighbors now all neighbors (only 4 of them) do have the same distance and this is what you get:
BUT, this isn’t a really good solution, simply because the only thing it did was shifting the relevance back to the perpendiculars inverting the behavior of the map, this is why now it looks like a 4 point star, or a rotated cube, this is to be expected though, and should be used if you only care about perpendicular movement
another solution would be to diffuse the values instead of interpolating them, which would give us a nice sphere effect on the map (like a soft airbrush from photoshop), but this solution actually has the same problem as the previous solution, because while visually it looks better the values tell us a different story, where the higher value cell is ALWAYS diagonally adjacent to the cell
the solution i prefer is to give each neighbor cell it’s rightful distance value so when you calculate the exponential of the decay it depends on the distance, i did that but introducing a new value of your Vector2I structure that holds either 1 or 1.4142
public struct Vector2I
{
public int x;
public int y;
public float d;
public Vector2I(int nx, int ny, float nd)
{
x = nx;
y = ny;
d = nd;
}
}
float inf = _influencesCalc[n.x, n.y] * Mathf.Exp(-Decay * n.d); //* Decay;
Vector2I[] GetNeighbors(int x, int y)
{
List<Vector2I> retVal = new List<Vector2I>();
if (x > 0)
{
retVal.Add(new Vector2I(x-1, y, 1));
}
if (x < _influences.GetLength(0)-1)
{
retVal.Add(new Vector2I(x+1, y, 1));
}
if (y > 0)
{
retVal.Add(new Vector2I(x, y-1, 1));
}
if (y < _influences.GetLength(1)-1)
{
retVal.Add(new Vector2I(x, y+1, 1));
}
// diagonals
if (x > 0 y > 0)
{
retVal.Add(new Vector2I(x-1, y-1, 1.4142f));
}
if (x < _influences.GetLength(0)-1 y < _influences.GetLength(1)-1)
{
retVal.Add(new Vector2I(x+1, y+1, 1.4142f));
}
if (x > 0 y < _influences.GetLength(1)-1)
{
retVal.Add(new Vector2I(x-1, y+1, 1.4142f));
}
if (x < _influences.GetLength(0)-1 y > 0)
{
retVal.Add(new Vector2I(x+1, y-1, 1.4142f));
}
return retVal.ToArray();
}
and this is how it looks :]
notice how it looks like a 8 point start, which actually share the same problems as previous solutions, BUT since now both the diagonals AND the perpendiculars are “pulling” the values the map works just fine for small to medium size maps like this one, the bigger the map the more you notice the same problems on the outer parts of the map, which is not that bad if you plan on using it for a RTS game for instance
i hope it helped, most of the code is here, but if you wish i can share the package, i still advise you to try doing it yourself though
cheers :]
Awesome, thanks a lot for the explanations! One thing I guessed at was to change both _influences and _influencesCalc when setting influence in InfluenceMap.SetInfluence()
public void SetInfluence(int x, int y, float value)
{
if (x < Width y < Height)
{
_influences[x, y] = value;
_influencesBuffer[x, y] = value;
}
}
public void SetInfluence(Vector2I pos, float value)
{
if (pos.x < Width pos.y < Height)
{
_influences[pos.x, pos.y] = value;
_influencesBuffer[pos.x, pos.y] = value;
}
}
you guessed it right, i didn’t paste all the changes, some minor ones i left out
influence maps are pretty cool, in some cases you can totally replace any pathfinding system with it, being a worthy trade for scenarios with multiple characters, specially if they are cooperating with each other
i’m actually now working of top of these scripts to create a system that dynamically blocks and unblocks some cells, i managed to create walls for now and improved the code by switching buffers instead of copying them (ie: frame 1 you do the calculations with _influenceBuffer and save it on _influence, frame 2 you do the opposite, and so on), it’s for a very custom made scenario but if it turns out good enough for general purposes i’ll gladly share it
This is great! A friend was pushing me to try influence map to do the AI instead of BT and it works really well. For a larger environment it might be necessary to use a shader to compute the map gaussian blur but in the meantime I tweaked it a bit to remove GC spikes and sped it up 2x.
Thanks for writing Unity API free code 
The 4x 100x100 maps I use for testing AI used to spike at 70ms each (their update are staggered) and now that the call to Propagae is threaded they don’t even show up on the profiler - I love you ThreadNinja
/*
Copyright (C) 2012 Anomalous Underdog
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
public struct Vector2I
{
public int x;
public int y;
public float d;
public Vector2I(int nx, int ny)
{
x = nx;
y = ny;
d = 1;
}
public Vector2I(int nx, int ny, float nd)
{
x = nx;
y = ny;
d = nd;
}
}
public class InfluenceMap : GridData
{
List<IPropagator> _propagators = new List<IPropagator>();
float[,] _influences;
float[,] _influencesBuffer;
public float Decay { get; set; }
public float Momentum { get; set; }
public int Width { get{ return _influences.GetLength(0); } }
public int Height { get{ return _influences.GetLength(1); } }
public float GetValue(int x, int y)
{
return _influences[x, y];
}
public InfluenceMap(int size, float decay, float momentum)
{
_influences = new float[size, size];
_influencesBuffer = new float[size, size];
Decay = decay;
Momentum = momentum;
}
public InfluenceMap(int width, int height, float decay, float momentum)
{
_influences = new float[width, height];
_influencesBuffer = new float[width, height];
Decay = decay;
Momentum = momentum;
}
public void SetInfluence(int x, int y, float value)
{
if (x < Width && y < Height)
{
_influences[x, y] = value;
_influencesBuffer[x, y] = value;
}
}
public void SetInfluence(Vector2I pos, float value)
{
if (pos.x < Width && pos.y < Height)
{
_influences[pos.x, pos.y] = value;
_influencesBuffer[pos.x, pos.y] = value;
}
}
public void RegisterPropagator(IPropagator p)
{
_propagators.Add(p);
}
public void Propagate()
{
UpdatePropagators();
UpdatePropagation();
UpdateInfluenceBuffer();
}
void UpdatePropagators()
{
foreach (IPropagator p in _propagators)
{
SetInfluence(p.GridPosition, p.Value);
}
}
void UpdatePropagation()
{
for (int xIdx = 0; xIdx < Width; ++xIdx)
{
for (int yIdx = 0; yIdx < Height; ++yIdx)
{
//Debug.Log("at " + xIdx + ", " + yIdx);
float maxInf = 0.0f;
float minInf = 0.0f;
GetNeighbors(ref retVal, xIdx, yIdx);
for (int i=0;i<8;i++)
{
Vector2I n = retVal [i];
if (n.d!=0) {
//Debug.Log(n.x + " " + n.y);
float inf = _influencesBuffer [n.x, n.y] * Mathf.Exp (-Decay * n.d); //* Decay;
maxInf = Mathf.Max (inf, maxInf);
minInf = Mathf.Min (inf, minInf);
}
}
if (Mathf.Abs(minInf) > maxInf)
{
_influences[xIdx, yIdx] = Mathf.Lerp(_influencesBuffer[xIdx, yIdx], minInf, Momentum);
}
else
{
_influences[xIdx, yIdx] = Mathf.Lerp(_influencesBuffer[xIdx, yIdx], maxInf, Momentum);
}
}
}
}
void UpdateInfluenceBuffer()
{
for (int xIdx = 0; xIdx < _influences.GetLength(0); ++xIdx)
{
for (int yIdx = 0; yIdx < _influences.GetLength(1); ++yIdx)
{
_influencesBuffer[xIdx, yIdx] = _influences[xIdx, yIdx];
}
}
}
Vector2I[] retVal = new Vector2I[8];
void InitVector2IArray(ref Vector2I[] array)
{
for (int i = 0; i < array.Length; i++)
array [i] = new Vector2I (0, 0, 0);
}
void GetNeighbors(ref Vector2I[] array, int x, int y)
{
InitVector2IArray(ref retVal);
if (x > 0) {
retVal [0] = new Vector2I (x - 1, y);
}
if (x < _influences.GetLength (0) - 1) {
retVal [1] = new Vector2I (x + 1, y);
}
if (y > 0) {
retVal [2] = new Vector2I (x, y - 1);
}
if (y < _influences.GetLength (1) - 1) {
retVal [3] = new Vector2I (x, y + 1);
}
// diagonals
// as long as not in bottom-left
if (x > 0 && y > 0)
{
retVal[4] = new Vector2I(x-1, y-1, 1.4142f);
}
if (x < _influences.GetLength(0)-1 && y < _influences.GetLength(1)-1)
{
retVal[5] = new Vector2I(x+1, y+1, 1.4142f);
}
if (x > 0 && y < _influences.GetLength(1)-1)
{
retVal[6] = new Vector2I(x-1, y+1, 1.4142f);
}
if (x < _influences.GetLength(0)-1 && y > 0)
{
retVal[7] = new Vector2I(x+1, y-1, 1.4142f);
}
}
}
This is obviously some pretty old stuff and I sure didn’t have in mind GC at the time, I just wanted something that it would work. Even the images are broken, maybe I can fetch the old ones and fix my post. How did you got here btw? (just curious)
I highly recommend you to do proper diffusion instead of the star shaped one, I ended up using it for some simple mob AI in a square grid but with proper diffusion you can use it with a graph system and place it coarsely in a weird level design. This, in conjunction with other systems like path-finding or raycasting does wonders.
Oldies but goodies, it must have been a time where the “upload file” button of this forum didn’t exist. I found it thought google, only 2 forum thread on the subject.
This diffusion is 8 direction, which is your bit on top of Anomalus’ excellent stub. Seems to behave well without any funky corners unless I crank up one influence way up.
I’d like to see what you made with it, it might not be the proper AI for me. I don’t see need for a graph system, are you using it for a very large level where a giant grid would choke? Pathfinding - do you A* through the vector field? I get good results with following only the local maxima but I haven’t added static obstacles yet.
It was a 4yr old mobile hack and slash game. It ran on almost any device at that time and it used 2D sprites in a 3D gameplay. The maps were very small with a few props and hazards and the AI was competent enough to avoid them and surround the player, I think the max number of enemies was about 15 to 20 in the screen (about 25 draw calls). We scraped all path-finding because the maps were sufficient and only used raycasts for targeting and what not. So it scaled well regardless of the number of baddies. I know for sure most of the systems could handle more than just 20, it was just a design decision.
Influence maps are very situational but I’m not really sure why aren’t they more popular. It scales really well and adds an extra layer of information that you can use for a lot of things, in my case it completely replaced the path-finding.
Did you floodfill the grid using manhattan distance to form a potential field? I see that this present implementation tends to get stuck Pathdfinding with potential field usually get stuck in corners, how did you avoid that without A*?
Also did you end up calculating derived maps such as vulnerability and high level decisions?
I didn’t. Because when the level started had a counter I used that time to have it filled properly. You could pre-bake it or have it update on load.
Because I used heavy time slicing on the diffusion part if something wildly different was happening on one edge of the map it would take a while for the “signal” to reach the other end but that didn’t bother me much, the creepers weren’t super fast and even if they were following the wrong data at one point it made it look like they were searching for their last know position which in my case was a nice side effect, might not suit yours tho. I do remember that the worst case scenario were maze-like levels because the signal would take ages to travel and by the time it reached the end it would cause some weird behaviors like the creepers suddenly going back and forth like they don’t know where to go. But besides this case which could be fixed by have it update faster I didn’t have any path-finding issues at all.
The only problem I remember having was walls. I can’t remember completely what I did for static objects but it was something in the lines of deleting the value in a final buffer so that calculations weren’t affected by the missing values? not sure if it makes sense but basically I had this problem where if not done properly creeps would either be attracted to walls or avoid them but I know I got it fixed completely at the end, just can’t remember exactly how.
It was a simple game so there wasn’t much of high levels decisions to be made, the creeps were avoiding each other and some hazards in the scene (but not completely to make it more natural). Some creeps were supposed to help other and I was going to use some group data to help in the decision making but they never left design so I can’t help you much on that besides giving you my opinion.
Just after I posted those questions, I went ahead and added obstacles, what I did then is zero out a neighbor that’s in the wall and the diffusion gradient takes care of the pathfinding vector flow style, I like it and like you I find the erratic behavior very satisfying, like you say, as if the creature searches for a target while the diffusion reaches them. I just ran into my first thread artifacts, entire regions of the map pulsing, so I’m going to revise the map diffusion code and instead of the very inefficient calculate each map one at a time, do everything in one pass.
On a side note it’s funny how much easier creating fun behavior is, also zero bug which I have been told for a long time is the nice benefit of data oriented programming, makes me want to throw OOP out of the window.
Did you override motion in the vicinity of a target? You mentioned raycast…
For those interested, the code change:
void GetNeighbors(ref Vector2I[] array, int x, int y)
{
InitVector2IArray(ref retVal);
if (x > 0) {
retVal [0] = new Vector2I (x - 1, y);
}
if (x < Width - 1) {
retVal [1] = new Vector2I (x + 1, y);
}
if (y > 0) {
retVal [2] = new Vector2I (x, y - 1);
}
if (y < Height - 1) {
retVal [3] = new Vector2I (x, y + 1);
}
// diagonals
if (x > 0 && y > 0)
{
retVal[4] = new Vector2I(x-1, y-1, 1.4142f);
}
if (x < Width-1 && y < Height-1)
{
retVal[5] = new Vector2I(x+1, y+1, 1.4142f);
}
if (x > 0 && y < Height-1)
{
retVal[6] = new Vector2I(x-1, y+1, 1.4142f);
}
if (x < Width-1 && y > 0)
{
retVal[7] = new Vector2I(x+1, y-1, 1.4142f);
}
// zero out if they're inside an obstacle
for (int i=0; i<8;i++){
if (IsInsideObstacle (retVal [i]))
retVal [i] = new Vector2I (0, 0, 0);
}
}
bool IsInsideObstacle (Vector2I pos){
for (int i=0;i<_obstacles.Count; i++)
if (_obstaclesBounds[i].Contains (pos))
return true;
return false;
}
Is there a place where I can find a complete tutorial for a 3D influence map? I can find a lot of sites that explain the theory but none of them actually get into how to code it.
This is it, download the project on the first post and apply the theory by adding maps.
Yeah, pretty much, it had more conditions but the major factor was how close it was, I used raycasting because my creeps were throwing stuff and I wanted them to “see” the target so I reused ray-casting for both. I would probably do it differently today, it was a waste of resources because I never did anything meaningful with the rays that I couldn’t do without them.
[edit] got the old images restored for future reference
This works with multiple floors in a level?
Seems that a state machine or a bt needs to take over in-range. I was trying to do all the decision making as a flocking mechanic by adding vector direction from multiple maps and, no luck.
It’s a 2D grid, you can have multiple 2D grids but connecting the floors together won’t be as trivial, doable though.
If you implement it as a graph and not a grid you can have any shape you want. But this solution is only a 2D grid
Quick optimization : if you use navmesh agents instead of character controler you get a 5x speedup, plus quasi free collision avoidance so there is one less map lookup you need (maybe, sorta)
using UnityEngine;
using System.Collections;
using UnityEngine.AI;
public class Mover : MonoBehaviour
{
Vector3 direction;
Vector3 velocity;
CharacterController character;
NavMeshAgent agent;
[SerializeField]
float _speed=2f;
public static int pathfindingIterationsPerFrame;
// Use this for initialization
void Start()
{
//navmesh performance and init
pathfindingIterationsPerFrame = pathfindingIterationsPerFrame+10;
NavMesh.pathfindingIterationsPerFrame = pathfindingIterationsPerFrame;
agent = GetComponent<NavMeshAgent> ();
if (agent)
agent.velocity = velocity;
character = GetComponent<CharacterController> ();
delayUpdateDirection += Random.value*delayUpdateDirection;
}
[SerializeField]
float delayUpdateDirection=.1f;
float timer;
void Update()
{
if (Time.time > timer) {
direction = Vector3.zero;
timer = Time.time + delayUpdateDirection;
var directions = GetComponents<IDirection> ();
foreach (var d in directions)
direction += d.GetDirection ();
if (agent && agent.enabled)
agent.SetDestination (transform.position+ velocity);
}
velocity = direction;
velocity.Normalize();
velocity *= _speed;
velocity.y = 0;
// transform.position += _velocity * Time.deltaTime;
if (character&& character.enabled)
character.SimpleMove(velocity);
}
}