Unity/C# - Grids - Definition and Graph


Since grids are a common data structure used for games I'm gonna talk a little about them.
Technically, grids are just n-dimensional discrete spaces (as opposed to a continuous space). For instance, let's talk about square grids since they are one of the most found in all types of games (electronic and analogical).

Square Grids

Using our previous definition for grids, a square grid is just one of the many cases for a 2-dimensional discrete space. As all spaces, they are infinite and functional. When I say they are functional, it means that necessarily you need a data structure or an instance of something to represent a grid, it can be entirely represented through functions. Since most games use a 3D-continuous space, let's convert it to 2D-discrete.


public static class Grid
{
    public const float DISCRETE_SIZE = 1.0f;
  
    public static Vector2Int Convert(Vector3 worldPosition)
    {
        var coordX = Mathf.RoundToInt(worldPosition.x / DISCRETE_SIZE);
        var coordY = Mathf.RoundToInt(worldPosition.y / DISCRETE_SIZE);
        return new Vector2Int(coordX,coordY);
    }
}


The Grid class above basically just provides a function that converts a world coordinate do a grid coordinate. If the world coordinate ranges from [-0.5, 0.5] it will result in 0, so all continuous coordinates from that range belong to the same grid cell. The DISCRETE_SIZE constant is the size for each cell of the grid (higher cell size results in a greater range of values being converted to the same cell).

Now that we a have a simple discrete space to work on, let segment it. While a grid is infinite, a grid segment is finite. It is akin to how lines are infinite and line segment are finite (a line is a 1D space), so we just have the 2 dimensions of the grid being finite. The same way that a rectangle is a continuous plane segment, a grid segment is just a rectangle with int values.

In order to iterate through all coordinates of a grid segment (RectInt), I will declare an extension method for it:

    public static IEnumerable<Vector2Int> Enumerate(this RectInt rect)
    {
        for (int i = rect.xMin; i < rect.xMax; i++)
            for (int j = rect.yMin; j < rect.yMax; j++)
                yield return new Vector2Int(i, j);
    }

Grid Graph (also know as Lattice)

For games and many other applications, when dealing with grid segments we usually have to treat them as graphs. Now we are going to create some classes to allow us to treat the grid segment as a graph.
We will build our graph based on a grid segment and a neighbourhood function.


public abstract class Graph<TVertex> : IGraph<TVertex, Graph<TVertex>.Edge>
{
    public delegate IEnumerable<TVertex> NeighborhoodFunction(TVertex vertex);

    public struct Edge : IGraphEdge<TVertex>
    {
        public TVertex VertexA { get; private set; }
        public TVertex VertexB { get; private set; }
        public Edge(TVertex a, TVertex b)
        {
            VertexA = a;
            VertexB = b;
        }
    }
    private NeighborhoodFunction GetNeighbors { get; set; }

    public Graph(NeighborhoodFunction neighborhoodFunction)
    {
        GetNeighbors = neighborhoodFunction;
    }
    public IEnumerable<Edge> Neighbors(TVertex vertex)
    {
        var neighbors = GetNeighbors(vertex);
        foreach (var neighbor in neighbors)
            if (Contains(neighbor))
                yield return new Edge(vertex, neighbor);
    }
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    public abstract bool Contains(TVertex vertex);
    public abstract IEnumerator<TVertex> GetEnumerator();
}




This is a simple abstract graph class that has a delegate that returns a list of neighbours for a certain vertex and is itself a collection of vertices. Our concrete grid segment class will be:




public class GridSegmentGraph : Graph<Vector2Int>
{
    public RectInt gridSegment;

    public GridSegmentGraph(RectInt segmentRect, NeighborhoodFunction getNeighbors) : base(getNeighbors)
    {
        this.gridSegment = segmentRect;
    }

    public override bool Contains(Vector2Int vertex) => gridSegment.Contains(vertex);

    public override IEnumerator<Vector2Int> GetEnumerator() => gridSegment.Enumerate().GetEnumerator();
}




Then you can ask me: "Why a neighbourhood function?". Well, since the grid has many uses, I'm going to present the 2 most common neighbourhood functions: Von Neumann and Moore.







Von Neumann neighbourhood.


Moore neighbourhood.




I could go about how each of this neighbourhoods is defined by a distance function, but for simplicity sake, let's just hard-code the functions as extension methods of the Vector2Int struct (note that the Moore neighbourhood is just the Von Neumann plus the diagonals).




Obs: I could easily remove the delegate neighbourhood function in the graph and implement 2 separated classes, one for Moore neighbourhood grid segments and one for Von Neumann, or an enumeration to choose the type of neighbourhood. But since the neighbourhood of a coordinate is independent of the graph, I'd rather make them extension methods for Vector2Int and use delegates for the graph. This also allows the graph class to be generic and usable in the future for other types of graphs.

    public static IEnumerable<Vector2Int> VonNeumannNeighborhood(this Vector2Int coord)
    {
        yield return coord + new Vector2Int(1, 0);
        yield return coord + new Vector2Int(0, 1);
        yield return coord + new Vector2Int(-1, 0);
        yield return coord + new Vector2Int(0, -1);
    }
    public static IEnumerable<Vector2Int> MooreNeighborhood(this Vector2Int coord)
    {
        foreach(var neighbor in VonNeumannNeighborhood(coord))
            yield return neighbor;

        yield return coord + new Vector2Int(1, 1);
        yield return coord + new Vector2Int(-1, 1);
        yield return coord + new Vector2Int(-1, -1);
        yield return coord + new Vector2Int(1, -1);
    }


Now we can easily create a 10x10 grid segment graph by declaring:


var gridSegment = new RectInt(0, 0, 10, 10);
var gridSegmentGraph = new GridSegmentGraph(gridSegment, VonNeumannNeighborhood);


The formulas for neighbourhood also work for global positions, the grid segment just checks for neighbours that are contained within that segment.

Comments

Popular posts from this blog

Unity3D/C# - Asynchronous Programming - Coroutines vs await/async

C# - Simple Graph Interfaces and a MeshGraph

Unity/C# - Grids - Simple Grid Segment struct