How to do it...

The following code is for the Graph class:

1. Create the backbone with the member values:

using UnityEngine; 
using System.Collections; 
using System.Collections.Generic; 
 
public abstract class Graph : MonoBehaviour 
{ 
    public GameObject vertexPrefab; 
    protected List<Vertex> vertices; 
    protected List<List<Vertex>> neighbours; 
    protected List<List<float>> costs; 
    // next steps 
}

2. Define the Start function:

public virtual void Start() 
{ 
    Load(); 
} 

3. Define the Load function, mentioned previously:

public virtual void Load() { } 

4. Implement the function for getting the graph's size:

public virtual int GetSize() 
{ 
    if (ReferenceEquals(vertices, null)) 
        return 0; 
    return vertices.Count; 
} 

5. Define the function for finding the nearest vertex given a position:

public virtual Vertex GetNearestVertex(Vector3 position) 
{ 
    return null; 
} 

6. Implement the function for getting the vertex given its ID:

public virtual Vertex GetVertexObj(int id) 
{ 
    if (ReferenceEquals(vertices, null) || vertices.Count == 0) 
        return null; 
    if (id < 0 || id >= vertices.Count) 
        return null; 
    return vertices[id]; 
} 

7. Implement the function for retrieving a vertex's neighbors:

public virtual Vertex[] GetNeighbours(Vertex v) 
{ 
    if (ReferenceEquals(neighbours, null) || neighbours.Count == 0) 
        return new Vertex[0]; 
    if (v.id < 0 || v.id >= neighbours.Count) 
        return new Vertex[0]; 
    return neighbours[v.id].ToArray(); 
}

We also need a Vertex class; use the following code:

using UnityEngine; 
using System.Collections.Generic; 
[System.Serializable] 
public class Vertex : MonoBehaviour 
{ 
    public int id; 
    public List<Edge> neighbours; 
    [HideInInspector] 
    public Vertex prev; 
} 

We need to create a class for storing a vertex's neighbors with the costs. This class will be called Edge. Let's implement it:

1. Create the Edge class, deriving from IComparable:

using System; 
 
[System.Serializable] 
public class Edge : IComparable<Edge> 
{ 
    public float cost; 
    public Vertex vertex; 
    // next steps 
} 

2. Implement its constructor:

public Edge(Vertex vertex = null, float cost = 1f) 
{ 
    this.vertex = vertex; 
    this.cost = cost; 
} 

3. Implement the comparison member function:

public int CompareTo(Edge other) 
{ 
    float result = cost - other.cost; 
    int idA = vertex.GetInstanceID(); 
    int idB = other.vertex.GetInstanceID(); 
    if (idA == idB) 
        return 0; 
    return (int)result; 
}

4. Implement the function for comparing two edges:

public bool Equals(Edge other) 
{ 
    return (other.vertex.id == this.vertex.id); 
} 

5. Override the function for comparing two objects:

public override bool Equals(object obj) 
{ 
    Edge other = (Edge)obj; 
    return (other.vertex.id == this.vertex.id); 
} 

6. Override the function for retrieving the hash code. This is necessary when overriding the previous member function:

public override int GetHashCode() 
{ 
    return this.vertex.GetHashCode(); 
} 

Besides creating the previous classes, it's important to define a couple of prefabs based on the cube primitive in order to visualize the ground (maybe a low-height cube) and walls or obstacles. The prefab for the ground is assigned to the vertexPrefab variable and the wall prefab is assigned to the obstaclePrefab variable that is declared in the next section.

Finally, create a directory called Maps to store the text files for defining the maps.

Now, it's time to go in-depth and be specific about implementing our grid graph. First, we implement all the functions for handling the graph, leaving space for your own text files, and, in the following section, we'll learn how to read .map files, which is an open format used by a lot of games:

1. Create the GraphGrid class, deriving from Graph:

using UnityEngine; 
using System; 
using System.Collections.Generic; 
using System.IO; 
 
public class GraphGrid : Graph 
{ 
    public GameObject obstaclePrefab; 
    public string mapName = "arena.map"; 
    public bool get8Vicinity = false; 
    public float cellSize = 1f; 
    [Range(0, Mathf.Infinity)] 
    public float defaultCost = 1f; 
    [Range(0, Mathf.Infinity)] 
    public float maximumCost = Mathf.Infinity; 
    string mapsDir = "Maps"; 
    int numCols; 
    int numRows; 
    GameObject[] vertexObjs; 
    // this is necessary for 
    // the advanced section of reading 
    // from an example test file 
    bool[,] mapVertices; 
    // next steps 
} 

2. Define the GridToId and IdToGrid functions for transforming a position in the grid into a vertex index, and vice versa:

private int GridToId(int x, int y) 
{ 
    return Math.Max(numRows, numCols) * y + x; 
} 
 
private Vector2 IdToGrid(int id) 
{ 
    Vector2 location = Vector2.zero; 
    location.y = Mathf.Floor(id / numCols); 
    location.x = Mathf.Floor(id % numCols); 
    return location; 
} 

3. Define the LoadMap function for reading the text file:

private void LoadMap(string filename) 
{ 
    // TODO 
    // implement your grid-based 
    // file-reading procedure here 
    // using 
    // vertices[i, j] for logical representation and 
    // vertexObjs[i, j] for assigning new prefab instances 
}

4. Override the LoadGraph function:

public override void LoadGraph() 
{ 
    LoadMap(mapName); 
} 

5. Override the GetNearestVertex function. This is the traditional way, without considering that the resulting vertex is an obstacle. In the following steps, we will learn how to do it better:

public override Vertex GetNearestVertex(Vector3 position) 
{ 
    position.x = Mathf.Floor(position.x / cellSize); 
    position.y = Mathf.Floor(position.z / cellSize); 
    int col = (int)position.x; 
    int row = (int)position.z; 
    int id = GridToId(col, row); 
    return vertices[id]; 
   } 

6. Override the GetNearestVertex function. It is based on the Breadth-First Search algorithm that we will learn about in-depth later in the chapter:

public override Vertex GetNearestVertex(Vector3 position) 
{ 
    int col = (int)(position.x / cellSize); 
    int row = (int)(position.z / cellSize); 
    Vector2 p = new Vector2(col, row); 
    // next steps 
} 

7. Define the list of explored positions (vertices) and the queue of the position to be explored:

List<Vector2> explored = new List<Vector2>(); 
Queue<Vector2> queue = new Queue<Vector2>(); 
queue.Enqueue(p); 

8. Keep exploring while the queue still has elements to explore. Otherwise, return null:

do 
{ 
    p = queue.Dequeue(); 
    col = (int)p.x; 
    row = (int)p.y; 
    int id = GridToId(col, row); 
    // next steps 
} while (queue.Count != 0); 
return null; 

9. Retrieve it immediately if it's a valid vertex:

if (mapVertices[row, col]) 
    return vertices[id]; 

10. Add the position to the list of explored, if it's not already there:

if (!explored.Contains(p)) 
{ 
    explored.Add(p); 
    int i, j; 
    // next step 
} 

11. Add all its valid neighbors to the queue, provided they are valid:

for (i = row - 1; i <= row + 1; i++) 
{ 
    for (j = col - 1; j <= col + 1; j++) 
    {  
        if (i < 0 || j < 0) 
            continue; 
        if (j >= numCols || i >= numRows) 
            continue; 
        if (i == row && j == col) 
            continue; 
        queue.Enqueue(new Vector2(j, i)); 
    } 
}