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:
VertexInfluence
class, deriving from Vertex
:using UnityEngine; using System.Collections.Generic; public class VertexInfluence : Vertex { public Faction faction; public float value = 0f; }
public bool SetValue(Faction f, float v) { bool isUpdated = false; if (v > value) { value = v; faction = f; isUpdated = true; } return isUpdated; }
InfluenceMap
class deriving from Graph
(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; }
Awake
function for initialization:void Awake() { if (unitList == null) unitList = new List<Unit>(); }
public void AddUnit(Unit u) { if (unitList.Contains(u)) return; unitList.Add(u); }
public void RemoveUnit(Unit u) { unitList.Remove(u); }
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 }
foreach(Unit u in unitList) { Vector3 uPos = u.transform.position; Vertex vert = GetNearestVertex(uPos); pending.Add(vert); // next step }
// 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.