Representing the world with Dirichlet domains

Also called a Voronoi polygon, a Dirichlet domain is a way of piding space into regions consisting of a set of points closer to a given seed point than to any other. This graph representation helps in distributing the space using Unity's primitives or existing meshes, thus not really adhering to the definition, but using the concept as a means to an end. Dirichlet domains are usually mapped using cones for delimiting the area of a given vertex, but we're adapting that principle to our specific needs and tool.

Example of a Voronoi Diagram or Voronoi Polygon

Getting ready

Before building our new Graph class, it's important to create the VertexReport class, make some modifications to our Graph class, and add the Vertex tag in the project:

1. Prepend the VertexReport class to the Graph class specification, in the same file:

   public class VertexReport
   {
       public int vertex;
       public GameObject obj;
       public VertexReport(int vertexId, GameObject obj)
       {
           vertex = vertexId;
           this.obj = obj;
       }
   }

Note

It's worth noting that the vertex objects in the scene must have a collider component attached to them, as well as the Vertex tag assigned. These objects can be either primitives or meshes, covering the maximum size of the area to be considered that vertex node.

How to do it...

This can be seen as a two-step recipe. First we define the vertex implementation and then the graph implementation, so everything works as intended:

1. First, create the VertexDirichlet class deriving from Vertex:

   using UnityEngine;
   
   public class VertexDirichlet : Vertex
   {
       // next steps
   }

2. Define the OnTriggerEnter function for registering the object in the current vertex:

   public void OnTriggerEnter(Collider col)
   {
       string objName = col.gameObject.name;
       if (objName.Equals("Agent") || objName.Equals("Player"))
       {
           VertexReport report = new VertexReport(id, col.gameObject);
           SendMessageUpwards("AddLocation", report);
       }
   }

3. Define the OnTriggerExit function for the inverse procedure

   public void OnTriggerExit(Collider col)
   {
       string objName = col.gameObject.name;
       if (objName.Equals("Agent") || objName.Equals("Player"))
       {
           VertexReport report = new VertexReport(id, col.gameObject);
           SendMessageUpwards("RemoveLocation", report);
       }
   }

4. Create the GraphDirichlet class deriving from Graph:

   using UnityEngine;
   using System.Collections.Generic;
   
   public class GraphDirichlet : Graph
   {
       Dictionary<int, List<int>> objToVertex;
   }

5. Implement the AddLocation function we called before:

   public void AddLocation(VertexReport report)
   {
       int objId = report.obj.GetInstanceID();
       if (!objToVertex.ContainsKey(objId))
       {
           objToVertex.Add(objId, new List<int>());
       }
       objToVertex[objId].Add(report.vertex);
   }

6. Define the RemoveLocation function as well:

   public void RemoveLocation(VertexReport report)
   {
       int objId = report.obj.GetInstanceID();
       objToVertex[objId].Remove(report.vertex);
   }

7. Override the Start function to initialize the member variables:

   public override void Start()
   {
       base.Start();
       objToVertex = new Dictionary<int, List<int>>();
   }

8. Implement the Load function for connecting everything:

   public override void Load()
   {
       Vertex[] verts = GameObject.FindObjectsOfType<Vertex>();
       vertices = new List<Vertex>(verts);
       for (int i = 0; i < vertices.Count; i++)
       {
           VertexVisibility vv = vertices[i] as VertexVisibility;
           vv.id = i;
           vv.FindNeighbours(vertices);
       }
   }

9. Override the GetNearestVertex function:

   public override Vertex GetNearestVertex(Vector3 position)
   {
       Vertex vertex = null;
       float dist = Mathf.Infinity;
       float distNear = dist;
       Vector3 posVertex = Vector3.zero;
       for (int i = 0; i < vertices.Count; i++)
       {
           posVertex = vertices[i].transform.position;
           dist = Vector3.Distance(position, posVertex);
           if (dist < distNear)
           {
               distNear = dist;
               vertex = vertices[i];
           }
       }
       return vertex;
   }

10. Define the GetNearestVertex function, this time with a GameObject as input:

    public Vertex GetNearestVertex(GameObject obj)
    {
        int objId = obj.GetInstanceID();
        Vector3 objPos = obj.transform.position;
        if (!objToVertex.ContainsKey(objId))
            return null;
        List<int> vertIds = objToVertex[objId];
        Vertex vertex = null;
        float dist = Mathf.Infinity;
        for (int i = 0; i < vertIds.Count; i++)
        {
            int id = vertIds[i];
            Vertex v = vertices[id];
            Vector3 vPos = v.transform.position;
            float d = Vector3.Distance(objPos, vPos);
            if (d < dist)
            {
                vertex = v;
                dist = d;
            }
        }
        return vertex;
    }

11. Implement the GetNeighbors function:

    public override Vertex[] GetNeighbours(Vertex v)
    {
        List<Edge> edges = v.neighbours;
        Vertex[] ns = new Vertex[edges.Count];
        int i;
        for (i = 0; i < edges.Count; i++)
        {
            ns[i] = edges[i].vertex;
        }
        return ns;
    }

12. Finally, define the GetEdges function:

    public override Edge[] GetEdges(Vertex v)
    {
        return vertices[v.id].neighbours.ToArray();
    }

How it works...

When the agents or players enter into the area of a vertex, it sends a message to the graph parent class, and indexes that vertex into the proper dictionary of objects, making the appropriate quantization easier. The same inverse principle applies when the player leaves the area. When the player is mapped into more than one vertex, the function returns the index of the closest one.

Also, we're using a dictionary to facilitate the process of translating object instance IDs to the indices of our vertex array.

There's more...

Take into account that placing the vertices and making the connections between them (edges) must be done manually using the implemented method. You're encouraged to implement a way for getting a vertex's neighbors aimed at your own project if you need a more user-friendly (or automated) technique.

Finally, we'll explore is an automated way to get a vertex's neighbors in the next recipe, using ray casting that will probably serve as a starting point.

See also

• The Representing the world with points of visibility recipe