The previous influence computation is good when dealing with a simple influence that is based on individual units helping a faction. However, this could lead to holes in the map instead of covering a whole section. One technique to resolve that problem is flooding, based on the Dijkstra algorithm.
In this case, we will blend the faction capability for tagging a vertex, with the unit's logic for having a drop-off function, into a class called Guild
. This is a component to include in the game object; one for each desired guild:
using UnityEngine; using System; using System.Collections; public class Guild : MonoBehaviour { public string guildName; public int maxStrength; public GameObject baseObject; [HideInInspector] public int strenghth public virtual void Awake() { strength = maxStrength; } }
It also needs a drop-off function. However, this time we wanted to create an example using Euclidean distance:
public virtual float GetDropOff(float distance) { float d = Mathf.Pow(1 + distance, 2f); return strength / d; }
Finally, we will need a GuildRecord
data type for the Dijkstra algorithm representation of a node:
GuildRecord
struct, deriving from the IComparable
interface:using UnityEngine; using System.Collections; using System; public struct GuildRecord : IComparable<GuildRecord> { public Vertex location; public float strength; public Guild guild; }
Equal
functions:public override bool Equals(object obj) { GuildRecord other = (GuildRecord)obj; return location == other.location; } public bool Equals(GuildRecord o) { return location == o.location; }
IComparable
functions:public override int GetHashCode() { return base.GetHashCode(); } public int CompareTo(GuildRecord other) { if (location == other.location) return 0; // the substraction is inverse for // having a descending binary heap return (int)(other.strength - strength); }
Now, we just need to modify some files and add functionalities:
guild
member in the VertexInfluence
class:public Guild guild;
InfluenceMap
class:public float dropOffThreshold; private Guild[] guildList;
InfluenceMap
, add the following line in the Awake
function:guildList = gameObject.GetComponents<Guild>();
public List<GuildRecord> ComputeMapFlooding() { }
GPWiki.BinaryHeap<GuildRecord> open; open = new GPWiki.BinaryHeap<GuildRecord>(); List<GuildRecord> closed; closed = new List<GuildRecord>();
foreach (Guild g in guildList) { GuildRecord gr = new GuildRecord(); gr.location = GetNearestVertex(g.baseObject); gr.guild = g; gr.strength = g.GetDropOff(0f); open.Add(gr); }
while (open.Count != 0) { // next steps here } return closed;
GuildRecord current; current = open.Remove(); GameObject currObj; currObj = GetVertexObj(current.location); Vector3 currPos; currPos = currObj.transform.position; List<int> neighbours; neighbours = GetNeighbors(current.location);
foreach (int n in neighbours) { // next steps here } closed.Add(current);
GameObject nObj = GetVertexObj(n); Vector3 nPos = nObj.transform.position; float dist = Vector3.Distance(currPos, nPos); float strength = current.guild.GetDropOff(dist); if (strength < dropOffThreshold) continue;
GuildRecord
node with the current vertex's data:GuildRecord neighGR = new GuildRecord(); neighGR.location = n; neighGR.strength = strength; VertexInfluence vi; vi = nObj.GetComponent<VertexInfluence>(); neighGR.guild = vi.guild;
if (closed.Contains(neighGR)) { int location = neighGR.location; int index = closed.FindIndex(x => x.location == location); GuildRecord gr = closed[index]; if (gr.guild.name != current.guild.name && gr.strength < strength) continue; }
else if (open.Contains(neighGR)) { bool mustContinue = false; foreach (GuildRecord gr in open) { if (gr.Equals(neighGR)) { mustContinue = true; break; } } if (mustContinue) continue; }
GuildRecord
assignment and add it to the priority queue when everything else fails:else { neighGR = new GuildRecord(); neighGR.location = n; } neighGR.guild = current.guild; neighGR.strength = strength;
open.Add(neighGR);
The algorithm returns the guild's assignment for every vertex. It traverses the whole graph starting from the guilds' bases and computes.
The algorithm traverses the whole graph starting from the guilds' positions. Given our previous inverse subtraction, the priority queue always starts from the strongest node and computes the assignment until it reaches a value below dropOffThreshold
. It also checks for ways to avoid a new assignment if the conditions are not met: if the vertex value is greater than the current strength, or if the guild assignment is the same.