Representing the world with grids

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.

Getting ready

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:

  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' neighbours:
    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:

  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.

How to do it...

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:

  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, respectively
    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 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];
   }
  6. Override the 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
}
  7. Define the list of explored positions (vertices) and the queue of position to be explored:
    List<Vector2> explored = new List<Vector2>();
Queue<Vector2> queue = new Queue<Vector2>();
queue.Enqueue(p);
  8. Do it while the queue still have 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're 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));
    }
}

How it works...

How it works...

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.

There's more...

We'll learn a way to implement the LoadMap function by using the .map file format as an example:

  1. Define the function and create a StreamReader object for reading the file
    private 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);
    }
}
  2. Declare and initialize the necessary variables
    int j = 0;
int i = 0;
int id = 0;
string line;
Vector3 position = Vector3.zero;
Vector3 scale = Vector3.zero;
  3. Read the header of the file containing its height and width
    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
  4. Initialize the member variables, allocating memory at the same time:
    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];
  5. Declare the for loop for iterating over the characters in the following lines
    for (i = 0; i < numRows; i++)
{
    line = strmRdr.ReadLine();
    for (j = 0; j < numCols; j++)
    {
        // next steps in here
    }
}
  6. Assign true or false to the logical representation depending on the character read
    bool isGround = true;
if (line[j] != '.')
    isGround = false;
mapVertices[i, j] = isGround;
  7. Instantiate the proper prefab
    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;
  8. Assign the new game object as a child of the graph and clean-up its name
    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;
  9. Create a pair of nested loops right after the previous loop, for setting up the neighbors for each vertex:
    for (i = 0; i < numRows; i++)
{
    for (j = 0; j < numCols; j++)
    {
        SetNeighbours(j, i);
    }
}
  10. Define the SetNeighbours function, called in the previous step:
    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
}
  11. Compute the proper values when we need vicinity of eight (top, bottom, right, left, and corners):
    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++;
        }
    }       
}
  12. Set up everything for vicinity of four (no corners):
    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);   
}
  13. Add the neighbors in the lists. It's the same procedure regarding the type of vicinity:
    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);
}

See also

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/

..................Content has been hidden....................

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