This is another widely-used technique for world representation based on points located throughout the valid area of navigation, whether manually placed or automated via scripting. We'll be using manually-placed points connected automatically via scripting.
Just like the previous representation, it's important to have several things in order before continuing:
Edge
class prepended to the Graph
class in the same fileGetEdges
function in the Graph
classVertex
classWe'll be creating the graph representation class as well as a custom Vertex
class:
VertexVisibility
class deriving from Vertex
:using UnityEngine; using System.Collections.Generic; public class VertexVisibility : Vertex { void Awake() { neighbours = new List<Edge>(); } }
FindNeighbours
function for automating the process of connecting vertices among them:public void FindNeighbours(List<Vertex> vertices) { Collider c = gameObject.GetComponent<Collider>(); c.enabled = false; Vector3 direction = Vector3.zero; Vector3 origin = transform.position; Vector3 target = Vector3.zero; RaycastHit[] hits; Ray ray; float distance = 0f; // next step }
for (int i = 0; i < vertices.Count; i++) { if (vertices[i] == this) continue; target = vertices[i].transform.position; direction = target - origin; distance = direction.magnitude; ray = new Ray(origin, direction); hits = Physics.RaycastAll(ray, distance); if (hits.Length == 1) { if (hits[0].collider.gameObject.tag.Equals("Vertex")) { Edge e = new Edge(); e.cost = distance; GameObject go = hits[0].collider.gameObject; Vertex v = go.GetComponent<Vertex>(); if (v != vertices[i]) continue; e.vertex = v; neighbours.Add(e); } } } c.enabled = true;
GraphVisibility
class:using UnityEngine; using System.Collections.Generic; public class GraphVisibility : Graph { // next steps }
Load
function for making the connections between vertices: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); } }
GetNearesteVertex
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; }
GetNeighbours
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; }
GetEdges
function:public override Edge[] GetEdges(Vertex v) { return vertices[v.id].neighbours.ToArray(); }
The parent class
GraphVisibility
indexes every vertex on the scene and makes use of the FindNeighbours
function on each one. This is in order to build the graph and make the connections without total user supervision, beyond placing the visibility points where the user sees fit. Also, the distance between two points is used to assign the cost to that corresponding edge.
It's important to make a point visible to one another for the graph to be connected. This approach is also suitable for building intelligent graphs considering stairs and cliffs, it just requires moving the Load
function to an editor-friendly class in order to call it in edit mode, and then modify or delete the corresponding edges to make it work as intended.
Take a look at the previous recipe's Getting ready section so you can better understand the starting point in case you feel you're missing something.
For further information about custom editors, editor scripting, and how to execute code in edit mode, please refer to the Unity documentation, available online at: