Influence Maps
Introduction
Influence maps are a well-known tool for handling tactical pathfinding for agents, particularly best in large outdoor environments. These maps are evoked from spatial logic through propagators, who carry a base scalar field of influence, positive or negative. Influence maps provide these components to make the AI make better or believable decisions based on the influence value at the given agent's current world position. Influence values can also drop off, so it is critical to update the influence buffer, which handles influence within the world space to appropriately decay when propagators are no longer in range of a particular area.
The formula for an Influence Map:
Influence Map = Update Propagators + Update Propagation + Update Influence Buffer
This Influence Map displays the influence value for each cell on the grid. Cells with yellow hue text have positive influence values, while cells with a blue hue value have negative influence values. Cells with a black text hue have an influence value of zero.
Propagators
To update propagators, you would first have to obtain your propagators by assigning the base scalar influence values for that propagator. In a war game scenario, you would set allying forces and structures with the same influence value, positive or negative. The enemy force needs to have the opposite signed influence value from the ally team. Any natural agents or forces have an influence value of zero. After assigning the influence value for the propagators, add them to a list so that you can iterate through each propagator and reset the cell that the propagator is currently on (the cell's and the propagator's world position is equivalent) influence and influence buffer variables to of the propagator's base influence value.
foreach (Propagator propagator in mPropagatorList)
{
if (propagator == null)
{
removePropagator(propagator); // remove propagator from the list
Return; // exit iteration because the list size has changed
}
Cell currentCell = getCellFromWorldPosition(propagator.getPosition());
currentCell.mInfluenceValue = propagator.InfluenceValue;
currentCell.mInfluenceBuffer = propagator.InfluenceValue;
}
Propagation
To update propagation, cycle through each cell in your grid; Inside the loop, create a local float min and max influence variable, which initially equals zero. Then create a sub-loop that cycles through the list of neighboring cells of the current cell on the grid. In the neighboring cell, the sub-loop use this formula or one like it to create the influence spread:
influence = currentNeighbor.mInfluenceBuffer * Mathf.Exp (-mDecayRate * decayScalar)
With the influence of that current neighbor cell calculated, you want to set the min and max value of that cell. Then check if the absolute value of the minimum influence is less than the max influence. Lerp that cell's influence value with the new min or max influence value that was just previously calculated.
foreach (Cell currentCell in mGrid)
{
float maxInfluence = 0.0f;
float minInfluence = 0.0f;
List<Cell> currentNeighbors = getNeighborCells(currentCell.mGridIndex, GridDirection.AllDirections);
foreach (Cell currentNeighbor in currentNeighbors)
{
float influence = currentNeighbor.mInfluenceBuffer * Mathf.Exp (-mDecayRate * decayScalar);
maxInfluence = Mathf.Max(influence, maxInfluence);
minInfluence = Mathf.Min(influence, minInfluence);
if (Mathf.Abs(minInfluence) > maxInfluence)
currentCell.mInfluenceValue = Mathf.Lerp(currentCell.mInfluenceBuffer, minInfluence, mMomentum);
else
currentCell.mInfluenceValue = Mathf.Lerp(currentCell.mInfluenceBuffer, maxInfluence, mMomentum);
}
}
InfluenceBuffer
Lastly, to update the influence buffer, iterate through each cell of the grid and set the cell's influence buffer equal to the current cell's influence value.
foreach (Cell currentCell in mGrid)
{
currentCell.mInfluenceBuffer = currentCell.mInfluenceValue;
}
Influence Map
As a result of Update Propagators + Update Propagation + Update Influence Buffer, you now have an influence map. Those three functions are known as propagating, which updates the influence on the grid.
Agents with blue hues have negative influence and those with positive influence have yellow hues.
Influence Map Application
Some interesting things you could do with influence maps allow agents to path find towards opposing forces and set influence towards detection ranges, as shown below with my turrets.
I made my agents choose a random location on the grid and compare that location with other locations’ influence values. If the influence value is of the opposing force’s influence then, that agent will path find towards that location.
// the agent's base influence is positive
if (mPropagatorInfluenceValue > 0)
{
// prioritize another cell that has less influence that was initially wanted
if (currentCell.mInfluenceValue < wantedCell.mInfluenceValue)
wantedCell = currentCell;
// stop the search early if found negative influence (an enemy was spotted)
if (wantedCell.mInfluenceValue < 0)
return wantedCell.mWorldPosition;
}
// the agent's base influence is negative
else if (mPropagatorInfluenceValue < 0)
{
// prioritize another cell that has more influence that was initially wanted
if (currentCell.mInfluenceValue > wantedCell.mInfluenceValue)
wantedCell = currentCell;
// stop the search early if found positive influence (an enemy was spotted)
if (wantedCell.mInfluenceValue > 0)
return wantedCell.mWorldPosition;
}
I applied influence on turret neighboring cells (Cardinal and Intercardinal Directions) that were within its detection radius.
Video Demonstration Link:
References
laurentlavigne. “AI Influence Maps.” uBibliorum, Dec 9, 2016. https://forum.unity.com/threads/ai-influence-maps.145368/