A grid is the most used structure for representing worlds in games because it is easy to implement and visualize. However, we will lay the foundations for advanced graph representations while learning the basis of graph theory and properties.
First, we need to create an abstract class called Graph
, declaring the virtual methods that every graph representation implements. It is done this way because, no matter how the vertices and edges are represented internally, the path-finding algorithms remain high-level, thus avoiding the implementation of the algorithms for each type of graph representation.
This class works as a parent class for the different representations to be learned in the chapter and it's a good starting point if you want to implement graph representations not covered in the book.
The following is the code for the Graph
class:
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 }
public virtual void Start() { Load(); }
public virtual void Load() { }
public virtual int GetSize() { if (ReferenceEquals(vertices, null)) return 0; return vertices.Count; }
public virtual Vertex GetNearestVertex(Vector3 position) { return null; }
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]; }
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, with 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; }
Following, we need to create a class for storing a vertex' neighbours with their costs. This class will be called Edge
, and let's implement it:
Edge
class, deriving from IComparable
:using System; [System.Serializable] public class Edge : IComparable<Edge> { public float cost; public Vertex vertex; // next steps }
public Edge(Vertex vertex = null, float cost = 1f) { this.vertex = vertex; this.cost = cost; }
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; }
public bool Equals(Edge other) { return (other.vertex.id == this.vertex.id); }
public override bool Equals(object obj) { Edge other = (Edge)obj; return (other.vertex.id == this.vertex.id); }
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 concrete about implementing our grid graph. First, we implement all the functions for handling the graph, leaving space for your own text files, and in a following section we'll learn how to read.map
files, which is an open format used by a lot of games:
GraphGrid
class deriving from Graphusing 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 }
GridToId
and IdToGrid
functions for transforming a position in the grid into a vertex index, and vice versa, respectivelyprivate 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; }
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 }
public override void LoadGraph() { LoadMap(mapName); }
GetNearestVertex
function. This is the traditional way, without considering that the resulting vertex is an obstacle. In the next 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]; }
GetNearestVertex
function. It's is based on the Breadth-First Search algorithm that we will learn 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 }
List<Vector2> explored = new List<Vector2>(); Queue<Vector2> queue = new Queue<Vector2>(); queue.Enqueue(p);
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;
if (mapVertices[row, col]) return vertices[id];
if (!explored.Contains(p)) { explored.Add(p); int i, j; // next step }
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)); } }
The algorithm makes use of its private functions in order to adapt itself to the general functions derived from the parent's class, and it relies on simple mathematical functions to convert from a two-dimensional vector position to a one-dimensional vector, or vertex index.
The LoadMap
function is open to your own implementation, but in the next section we we'll learn a way to implement and read certain kinds of text files containing maps based on grids.
We'll learn a way to implement the LoadMap
function by using the .map
file format as an example:
StreamReader
object for reading the fileprivate void LoadMap(string filename) { string path = Application.dataPath + "/" + mapsDir + "/" + filename; try { StreamReader strmRdr = new StreamReader(path); using (strmRdr) { // next steps in here } } catch (Exception e) { Debug.LogException(e); } }
int j = 0; int i = 0; int id = 0; string line; Vector3 position = Vector3.zero; Vector3 scale = Vector3.zero;
line = strmRdr.ReadLine();// non-important line line = strmRdr.ReadLine();// height numRows = int.Parse(line.Split(' ')[1]); line = strmRdr.ReadLine();// width numCols = int.Parse(line.Split(' ')[1]); line = strmRdr.ReadLine();// "map" line in file
vertices = new List<Vertex>(numRows * numCols); neighbours = new List<List<Vertex>>(numRows * numCols); costs = new List<List<float>>(numRows * numCols); vertexObjs = new GameObject[numRows * numCols]; mapVertices = new bool[numRows, numCols];
for (i = 0; i < numRows; i++) { line = strmRdr.ReadLine(); for (j = 0; j < numCols; j++) { // next steps in here } }
bool isGround = true; if (line[j] != '.') isGround = false; mapVertices[i, j] = isGround;
position.x = j * cellSize; position.z = i * cellSize; id = GridToId(j, i); if (isGround) vertexObjs[id] = Instantiate(vertexPrefab, position, Quaternion.identity) as GameObject; else vertexObjs[id] = Instantiate(obstaclePrefab, position, Quaternion.identity) as GameObject;
vertexObjs[id].name = vertexObjs[id].name.Replace("(Clone)", id.ToString()); Vertex v = vertexObjs[id].AddComponent<Vertex>(); v.id = id; vertices.Add(v); neighbours.Add(new List<Vertex>()); costs.Add(new List<float>()); float y = vertexObjs[id].transform.localScale.y; scale = new Vector3(cellSize, y, cellSize); vertexObjs[id].transform.localScale = scale; vertexObjs[id].transform.parent = gameObject.transform;
for (i = 0; i < numRows; i++) { for (j = 0; j < numCols; j++) { SetNeighbours(j, i); } }
protected void SetNeighbours(int x, int y, bool get8 = false) { int col = x; int row = y; int i, j; int vertexId = GridToId(x, y); neighbours[vertexId] = new List<Vertex>(); costs[vertexId] = new List<float>(); Vector2[] pos = new Vector2[0]; // next steps }
if (get8) { pos = new Vector2[8]; int c = 0; for (i = row - 1; i <= row + 1; i++) { for (j = col -1; j <= col; j++) { pos[c] = new Vector2(j, i); c++; } } }
else { pos = new Vector2[4]; pos[0] = new Vector2(col, row - 1); pos[1] = new Vector2(col - 1, row); pos[2] = new Vector2(col + 1, row); pos[3] = new Vector2(col, row + 1); }
foreach (Vector2 p in pos) { i = (int)p.y; j = (int)p.x; if (i < 0 || j < 0) continue; if (i >= numRows || j >= numCols) continue; if (i == row && j == col) continue; if (!mapVertices[i, j]) continue; int id = GridToId(j, i); neighbours[vertexId].Add(vertices[id]); costs[vertexId].Add(defaultCost); }
For further information about the map's format used and getting free maps from several acclaimed titles, please refer to the Moving AI Lab's website, led by Professor Sturtevant, available online at http://movingai.com/benchmarks/