Another way to use graphs is to represent how much reach or influence an agent, or in this case a unit, has over an area of the world. In this context, influence is represented as the total area of a map an agent, or a group of agents of the same party, covers.
This is a key element for creating good AI decision mechanisms based on the military presence in real-time simulation games, or games where it is important to know how much of the world is taken by a group of agents, each representing a given faction.
This is a recipe that requires the experience of graph building, so it is based on the general Graph class. However, we will need to derive it from a specific graph definition, or define our own methods to handle vertices and the neighbors retrieval logic, as learned in Chapter 2, Navigation.
We will learn how to implement the specific algorithms for this recipe, based on the Graph class general functions and the Vertex class.
Finally, we will need a base Unity component for our agent and Faction enum.
The following is the code for the Faction enum and Unit classes. They can be written in the same file, called Unit.cs:
using UnityEngine;
using System.Collections;
public enum Faction
{
// example values
BLUE, RED
}
public class Unit : MonoBehaviour
{
public Faction faction;
public int radius = 1;
public float influence = 1f;
public virtual float GetDropOff(int locationDistance)
{
return influence;
}
}We will build the VertexInfluence and InfluenceMap classes, used for handle vertices and the graph, respectively:
- Create the
VertexInfluenceclass, deriving fromVertex:using UnityEngine; using System.Collections.Generic; public class VertexInfluence : Vertex { public Faction faction; public float value = 0f; } - Implement the function for setting up values and notifying success:
public bool SetValue(Faction f, float v) { bool isUpdated = false; if (v > value) { value = v; faction = f; isUpdated = true; } return isUpdated; } - Create the
InfluenceMapclass deriving fromGraph(or a more specific graph implementation):using UnityEngine; using System.Collections; using System.Collections.Generic; public class InfluenceMap : Graph { public List<Unit> unitList; // works as vertices in regular graph GameObject[] locations; } - Define the
Awakefunction for initialization:void Awake() { if (unitList == null) unitList = new List<Unit>(); } - Implement the function for adding a unit on the map:
public void AddUnit(Unit u) { if (unitList.Contains(u)) return; unitList.Add(u); } - Implement the function for removing a unit from the map:
public void RemoveUnit(Unit u) { unitList.Remove(u); } - Start building the function for computing the influence:
public void ComputeInfluenceSimple() { int vId; GameObject vObj; VertexInfluence v; float dropOff; List<Vertex> pending = new List<Vertex>(); List<Vertex> visited = new List<Vertex>(); List<Vertex> frontier; Vertex[] neighbours; // next steps } - Continue by creating a loop for iterating over the list of units:
foreach(Unit u in unitList) { Vector3 uPos = u.transform.position; Vertex vert = GetNearestVertex(uPos); pending.Add(vert); // next step } - Finally, apply a BFS-based code for spreading influence given the radius reach:
// BFS for assigning influence for (int i = 1; i <= u.radius; i++) { frontier = new List<Vertex>(); foreach (Vertex p in pending) { if (visited.Contains(p)) continue; visited.Add(p); v = p as VertexInfluence; dropOff = u.GetDropOff(i); v.SetValue(u.faction, dropOff); neighbours = GetNeighbours(vert); frontier.AddRange(neighbours); } pending = new List<Vertex>(frontier); }
The influence-map graph works exactly as a general graph as well as the influence-based vertex because there's just a couple of extra parameters for mapping the influence across the graph. The most relevant part relies on the computation of the influence, and it is based on the BFS algorithm.
For each unit on the map, we spread its influence given the radius. When the computed influence (drop off) is greater than the vertex original faction, the vertex faction is changed.
The drop-off function should be tuned according to your specific game needs. We can define a smarter function with the following example code, using the distance parameter:
public virtual float GetDropOff(int locationDistance)
{
float d = influence / radius * locationDistance;
return influence - d;
}It is important to note that the distance parameter is an integer indicating the distance measured in vertices.
Finally, we could avoid using factions and instead use a reference to the unit itself. That way, we could map the influence based on individual units, but we think it makes the most sense to think in terms of factions or teams.
- Chapter 2, Navigation, the Representing the world with grids and Finding the shortest path in a grid with BFS recipes