Improving influence with map flooding

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.

Getting ready

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:

  1. Create the 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;
}
  2. Implement the 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;
}
  3. Implement the required 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);
}

How to do it…

Now, we just need to modify some files and add functionalities:

  1. Include the guild member in the VertexInfluence class:
    public Guild guild;
  2. Include new members in the InfluenceMap class:
    public float dropOffThreshold;
private  Guild[] guildList;
  3. Also, in InfluenceMap, add the following line in the Awake function:
    guildList = gameObject.GetComponents<Guild>();
  4. Create the map-flooding function:
    public List<GuildRecord> ComputeMapFlooding()
{
}
  5. Declare the main necessary variables:
    GPWiki.BinaryHeap<GuildRecord> open;
open = new GPWiki.BinaryHeap<GuildRecord>();
List<GuildRecord> closed;
closed = new List<GuildRecord>();
  6. Add the initial nodes for each guild in the priority queue:
    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);
}
  7. Create the main Dijkstra iteration and return the assignments:
    while (open.Count != 0)
{
    // next steps here
}
return closed;
  8. Take the first node in the queue and get its neighbors:
    GuildRecord current;
current = open.Remove();
GameObject currObj;
currObj = GetVertexObj(current.location);
Vector3 currPos;
currPos = currObj.transform.position;
List<int> neighbours;
neighbours = GetNeighbors(current.location);
  9. Create the loop for computing each neighbor, and put the current node in the closed list:
    foreach (int n in neighbours)
{
    // next steps here
}
closed.Add(current);
  10. Compute the drop off from the current vertex, and check whether it is worth trying to change the guild assigned:
    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;
  11. Create an auxiliary 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;
  12. Check the closed list and validate the time when a new assignment must be avoided:
    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;
}
  13. Check the priority queue for the same reasons:
    else if (open.Contains(neighGR))
{
    bool mustContinue = false;
    foreach (GuildRecord gr in open)
    {
        if (gr.Equals(neighGR))
        {
            mustContinue = true;
            break;
        }
    }
    if (mustContinue)
        continue;
}
  14. Create a new 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;
  15. Add it to the priority queue if necessary:
    open.Add(neighGR);

How it works…

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.

See also

  • The Introducing influence maps recipe
  • Chapter 2, Navigation, the Finding the shortest path with Dijkstra recipe
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.147.47.166