A1- Grid Lattice

Intro

A grid lattice will be created in Unity to allow for an agent to engage in path planning and obstacle avoidance.

Resources

• A1 Demo
• Ed Discussion

Overview

Set up

• Clone the repository
• Open the folder D:\Unity\Projects\GameAIPathPlanning in Unity
• Select Scenes/GridNavigation to open GridNavigation
• Click play
  • You can click anywhere on the plane to see the Agent attempt to navigate there
  • You can also use the following keyboard controls

Keyboard controls

Keyboard controls

• 0–9 — Choose different scenes
• Tab — Switch between Grid, Path Network, and NavMesh assignment scenes
• Left Click — Path search to location
• Right Click — Incremental path search to location
• Shift + Right Click — Manual incremental search to location (see N below)
• Left Click + Drag — Move obstacles (or waypoints in Path Network scene)
• N — Next manual incremental search step
• T — Toggle obstacle models visibility
• V — Toggle graph adjacency view on the Grid
• . (Period) — Toggle between 4-way (default) and 8-way connectivity

Spacebar - change search algorithm (see HUD top right)

CreateGrid Class Implementation

• Game Grid calls CreateGrid.Create() and CreateGrid.IsTraversable()
• The Create() method generates a 2D Boolean array indicating whether cells in the grid (canvas width × height) are traversable
• The values in game world coordinates/dimensions such as canvasOrigin, canvasWidth, canvasHeight etc can be converted with Convert()
  • need to put width and height into a Vector2 to use it- ex) (canvasWidth, canvasHeight)

CreateGrid.cs

// compile_check
// Remove the line above if you are subitting to GradeScope for a grade. But leave it if you only want to check
// that your code compiles and the autograder can access your public methods.
 
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
 
namespace GameAICourse {
 
    public class CreateGrid
    {
 
        // Please change this string to your name
        //public const string StudentAuthorName = "George P. Burdell ← Not your name, change it!";
 
 
        // Helper method provided to help you implement this file. Leave as is.
        // Returns true if point p is inside (or on edge) the polygon defined by pts (CCW winding). False, otherwise
        static bool IsPointInsidePolygon(Vector2Int[] pts, Vector2Int p)
        {
            return CG.InPoly1(pts, p) != CG.PointPolygonIntersectionType.Outside;
        }
 
 
        // Helper method provided to help you implement this file. Leave as is.
        // Returns float converted to int according to default scaling factor (1000)
        static int Convert(float v)
        {
            return CG.Convert(v);
        }
 
        // Helper method provided to help you implement this file. Leave as is.
        // Returns Vector2 converted to Vector2Int according to default scaling factor (1000)
        static Vector2Int Convert(Vector2 v)
        {
            return CG.Convert(v);
        }
 
        // Helper method provided to help you implement this file. Leave as is.
        // Returns true if segment AB intersects CD properly or improperly
        static bool Intersects(Vector2Int a, Vector2Int b, Vector2Int c, Vector2Int d)
        {
            return CG.Intersect(a, b, c, d);
        }
 
 
        // IsPointInsideAxisAlignedBoundingBox(): Determines whether a point (Vector2Int:p) is On/Inside a bounding box (such as a grid cell) defined by
        // minCellBounds and maxCellBounds (both Vector2Int's).
        // Returns true if the point is ON/INSIDE the cell and false otherwise
        // This method should return true if the point p is on one of the edges of the cell.
        // This is more efficient than PointInsidePolygon(`) for an equivalent dimension poly
        // Preconditions: minCellBounds <= maxCellBounds, per dimension
        static bool IsPointInsideAxisAlignedBoundingBox(Vector2Int minCellBounds, Vector2Int maxCellBounds, Vector2Int p)
        {
            //TODO IMPLEMENT
            //minCellBounds.x = 0;
            //minCellBounds.y = 0;
 
            //maxCellBounds.x = 1;
            //maxCellBounds.y = 1;
 
            if (p.x >= minCellBounds.x && p.x <= maxCellBounds.x || p.y >= minCellBounds.y && p.y <= maxCellBounds.y)
            {
                return true;
            }
                // placeholder logic to be replaced by the student
                return false;
        }
 
 
 
 
        // IsRangeOverlapping(): Determines if the range (inclusive) from min1 to max1 overlaps the range (inclusive) from min2 to max2.
        // The ranges are considered to overlap if one or more values is within the range of both.
        // Returns true if overlap, false otherwise.
        // Preconditions: min1 <= max1 AND min2 <= max2
        static bool IsRangeOverlapping(int min1, int max1, int min2, int max2)
        {
            // TODO IMPLEMENT
            return true;
        }
 
        // IsAxisAlignedBoundingBoxOverlapping(): Determines if the AABBs defined by min1,max1 and min2,max2 overlap or touch
        // Returns true if overlap, false otherwise.
        // Preconditions: min1 <= max1, per dimension. min2 <= max2 per dimension
        static bool IsAxisAlignedBoundingBoxOverlapping(Vector2Int min1, Vector2Int max1, Vector2Int min2, Vector2Int max2)
        {
 
            // TODO IMPLEMENT
            // HINT: Call IsRangeOverlapping()
 
            return true;
        }
 
 
 
 
 
        // IsTraversable(): returns true if the grid is traversable from grid[x,y] in the direction dir, false otherwise.
        // The grid boundaries are not traversable. If the grid position x,y is itself not traversable but the grid cell in direction
        // dir is traversable, the function will return false.
        // returns false if the grid is null, grid rank is not 2 dimensional, or any dimension of grid is zero length
        // returns false if x,y is out of range
        // Note: public methods are autograded
        public static bool IsTraversable(bool[,] grid, int x, int y, TraverseDirection dir)
        {
 
            // TODO IMPLEMENT
 
            //placeholder logic to be replaced by the student
            return true;
        }
 
 
        // Create(): Creates a grid lattice discretized space for navigation.
        // canvasOrigin: bottom left corner of navigable region in world coordinates
        // canvasWidth: width of navigable region in world dimensions
        // canvasHeight: height of navigable region in world dimensions
        // cellWidth: target cell width (of a grid cell) in world dimensions
        // obstacles: a list of collider obstacles
        // grid: an array of bools. A cell is true if navigable, false otherwise
        //    Example: grid[x_pos, y_pos]
 
        public static void Create(Vector2 canvasOrigin, float canvasWidth, float canvasHeight, float cellWidth,
            List<Polygon> obstacles,
            out bool[,] grid
            )
        {
            // ignoring the obstacles for this limited demo; 
            // Marks cells of the grid untraversable if geometry intersects interior!
            // Carefully consider all possible geometry interactions
 
            // also ignoring the world boundary defined by canvasOrigin and canvasWidth and canvasHeight
 
 
            grid = new bool[1, 1];
            grid[0, 0] = true;
 
 
        }
 
    }
 
}
 

Create() implementation

// Create(): Creates a grid lattice discretized space for navigation.
// canvasOrigin: bottom left corner of navigable region in world coordinates
// canvasWidth: width of navigable region in world dimensions
// canvasHeight: height of navigable region in world dimensions
// cellWidth: target cell width (of a grid cell) in world dimensions
// obstacles: a list of collider obstacles
// grid: an array of bools. A cell is true if navigable, false otherwise
//    Example: grid[x_pos, y_pos]
 
public static void Create(Vector2 canvasOrigin, float canvasWidth, float canvasHeight, float cellWidth,
    List<Polygon> obstacles,
    out bool[,] grid
    )
{
    // ignoring the obstacles for this limited demo; 
    // Marks cells of the grid untraversable if geometry intersects interior!
    // Carefully consider all possible geometry interactions
 
    // also ignoring the world boundary defined by canvasOrigin and canvasWidth and canvasHeight
 
    grid = new bool[1, 1];
    grid[0, 0] = true;
}

---

• The IsTraversable() method checks 4-way and 8-way connectivity from grid[x,y] in the direction dir

IsTraversable() implementation

// IsTraversable(): returns true if the grid is traversable from grid[x,y] in the direction dir, false otherwise.
// The grid boundaries are not traversable. If the grid position x,y is itself not traversable but the grid cell in direction
// dir is traversable, the function will return false.
// returns false if the grid is null, grid rank is not 2 dimensional, or any dimension of grid is zero length
// returns false if x,y is out of range
// Note: public methods are autograded
public static bool IsTraversable(bool[,] grid, int x, int y, TraverseDirection dir)
{
    // TODO IMPLEMENT
 
    // placeholder logic to be replaced by the student
    return true;
}

---

Prefigs

• In CustomPresetConfig.cs, can make new SceneConfigs by copying one like SC0, then add to awake
• SCeneConfig()- pass in worldSize, worldOrigin, the ball (agentPos, agentScale)

Helper Methods

• IsPointInsideAxisAlignedBoundingBox() — tests if a point lies within a bounding box

IsPointInsideAxisAlignedBoundingBox()

// IsPointInsideAxisAlignedBoundingBox(): Determines whether a point (Vector2Int:p) is On/Inside a bounding box
// defined by minCellBounds and maxCellBounds.
// Returns true if the point is ON/INSIDE the cell and false otherwise
// This method should return true if the point p is on one of the edges of the cell.
// Preconditions: minCellBounds <= maxCellBounds, per dimension
static bool IsPointInsideAxisAlignedBoundingBox(
    Vector2Int minCellBounds,
    Vector2Int maxCellBounds,
    Vector2Int p)
{
    // TODO IMPLEMENT
    return true;
}

---

• IsRangeOverlapping() — determines if two integer ranges overlap

IsRangeOverlapping()

// IsRangeOverlapping(): Determines if the range (inclusive) from min1 to max1
// overlaps the range (inclusive) from min2 to max2.
// Returns true if overlap, false otherwise.
// Preconditions: min1 <= max1 AND min2 <= max2
static bool IsRangeOverlapping(int min1, int max1, int min2, int max2)
{
    // TODO IMPLEMENT
    return true;
}

---

• IsAxisAlignedBoundingBoxOverlapping() — checks if two AABBs overlap or touch

IsAxisAlignedBoundingBoxOverlapping()

// IsAxisAlignedBoundingBoxOverlapping(): Determines if the AABBs defined by
// min1,max1 and min2,max2 overlap or touch
// Returns true if overlap, false otherwise.
// Preconditions: min1 <= max1, min2 <= max2 per dimension
static bool IsAxisAlignedBoundingBoxOverlapping(
    Vector2Int min1,
    Vector2Int max1,
    Vector2Int min2,
    Vector2Int max2)
{
    // TODO IMPLEMENT
    // HINT: Call IsRangeOverlapping()
    return true;
}

---

GridTest (Unit / Integration Testing)

• Unity tests use the NUnit framework and run via Unity’s Test Runner (Window → General → Test Runner)
• Extend automated testing to cover more scenarios and edge cases

• Shared Unit Tests
  • Castro’s unit tests
  • Muhammad’s unit tests

GridTest example

// You can write parameterized tests for more efficient test coverage!
// This single method can reflect an arbitrary number of test configurations
// via the TestCase(...) syntax.
// TODO You probably want some more test cases here. Maybe a negative origin?
[TestCase(0f, 0f, 1f, 1f, 1f)]
[TestCase(0f, 0f, 1f, 1f, 0.25f)]
[TestCase(0f, 0f, 1f, 1f, 0.26f)]
public void TestEmptyGrid(
    float originx,
    float originy,
    float width,
    float height,
    float cellSize)
{
    var origin = new Vector2(originx, originy);
 
    bool[,] grid;
    List<Polygon> obstPolys = new List<Polygon>();
 
    // Example of testing the code you are working on
    CreateGrid.Create(origin, width, height, cellSize, obstPolys, out grid);
 
    // Helper method usage
    BasicGridCheck(grid, width, height, cellSize);
 
    Assert.That(grid, Has.All.True,
        "There aren't any obstacles to block the grid cells!");
 
    // TODO Extend with more rigorous testing
}

GridTest.cs

using System;
using System.Collections;
using System.Collections.Generic;
using NUnit.Framework;
using UnityEngine;
using UnityEngine.TestTools;
 
using GameAICourse;
 
namespace Tests
{
    public class GridTest
    {
        // You can run the tests in this class in the Unity Editor if you open
        // the Test Runner Window and choose the EditMode tab
 
 
        // Annotate methods with [Test] or [TestCase(...)] to create tests like this one!
        [Test]
        public void TestName()
        {
            // Tests are performed through assertions. You can Google NUnit Assertion
            // documentation to learn about them. Several examples follow.
            Assert.That(CreateGrid.StudentAuthorName, Is.Not.Contains("George P. Burdell"),
                "You forgot to change to your name!");
        }
 
 
        // You can write helper methods that are called by multiple tests!
        // This method is not itself a test because it is not annotated with [Test].
        // But look below for examples of calling it.
        void BasicGridCheck(bool[,] grid, float width, float height, float cellSize)
        {
            Assert.That(grid, Is.Not.Null);
            Assert.That(grid.Rank, Is.EqualTo(2), "grid is not a 2D array!");
 
            var w = grid.GetLength(0);
            var h = grid.GetLength(1);
 
            // Parameterized tests can be dangerous. Especially if you implement
            // an equation to generate the correct values. This may replicate
            // bugs in the code that you are testing and give a false
            // indication of correctness!
            // Be very cautious when doing this...
            Assert.That(w, Is.EqualTo(Mathf.FloorToInt(width / cellSize)));
            Assert.That(h, Is.EqualTo(Mathf.FloorToInt(height / cellSize)));
 
        }
 
 
        // You can write parameterized tests for more efficient test coverage!
        // This single method can reflect an arbitrary number of test configurations
        // via the TestCase(...) syntax.
        // TODO You probably want some more test cases here. Maybe a negative origin?
        [TestCase(0f, 0f, 1f, 1f, 1f)]
        [TestCase(0f, 0f, 1f, 1f, 0.25f)]
        [TestCase(0f, 0f, 1f, 1f, 0.26f)]
        public void TestEmptyGrid(float originx, float originy, float width, float height, float cellSize)
        {
 
            var origin = new Vector2(originx, originy);
 
            bool[,] grid;
 
            List<Polygon> obstPolys = new List<Polygon>();
 
 
            // Here is an example of testing code you are working on by calling it!
            CreateGrid.Create(origin, width, height, cellSize, obstPolys, out grid);
 
 
            // Herer is that helper method in action
            BasicGridCheck(grid, width, height, cellSize);
 
 
            Assert.That(grid, Has.All.True,
                "There aren't any obstacles to block the grid cells!");
 
            // TODO This method can be extended with more rigorous testing...
 
        }
 
 
        [TestCase(0f, 0f, 1f, 1f, 1f)]
        [TestCase(0f, 0f, 1f, 1f, 0.25f)]
        public void TestObstacleThatNearlyFillsCanvas(float originx, float originy,
            float width, float height, float cellSize)
        {
 
            var origin = new Vector2(originx, originy);
 
            bool[,] grid;
 
            List<Polygon> obstPolys = new List<Polygon>();
 
            // Let's make an obstacle in this test...
 
            Polygon poly = new Polygon();
 
            float offset = 0.1f;
 
            // Needs to be counterclockwise!
            Vector2[] pts =
                {
                    origin + Vector2.one * offset,
                    origin + new Vector2(width - offset, offset),
                    origin + new Vector2(width - offset, height - offset),
                    origin + new Vector2(offset, height-offset)
                };
 
            // There are different ways to approach test setup for tests.
            // I generally just assert things that I believe might be problematic.
            // I then add text like "SETUP FAILURE" so I know the problem is separate
            // from what I'm actually testing.
 
            Assert.That(CG.Ccw(pts), Is.True, "SETUP FAILURE: polygon verts not listed CCW");
 
            poly.SetPoints(pts);
 
            obstPolys.Add(poly);
 
 
            // Here is an example of testing code you are working on!
            CreateGrid.Create(origin, width, height, cellSize, obstPolys, out grid);
 
     
            BasicGridCheck(grid, width, height, cellSize);
 
            Assert.That(grid, Has.All.False,
                "There is a big obstacle that should have blocked the entire grid!");
 
            // TODO This method can be extended with more rigorous testing...
 
        }
 
        // This test checks the functionality of your IsTraversable() method.
        // It's very important that this method works correctly. You will
        // need to test it a lot more than just this simple example test.
        [TestCase(true)]
        [TestCase(false)]
        public void TestTraversableWithSingleGridCell(bool gridCellState)
        {
            bool[,] grid = new bool[1, 1];
 
            grid[0, 0] = gridCellState;
 
            // Test all possible directions
            foreach (var dir in (TraverseDirection[])Enum.GetValues(typeof(TraverseDirection)))
            {          
                var res = CreateGrid.IsTraversable(grid, 0, 0, dir);
                Assert.That(res, Is.False, $"Traverability in dir: {dir} expected to be false but wasn't");
            }
        }
 
 
        // TODO I bet there is a lot more you want to write tests for!
 
 
    }
}
 

Debugging

• Use print statments- print() or Debug.Log()/Error()
• Or you can install the Unity plugin for the Visual Studio debugger

Tips

• C-sharp API C# Lists, arrays, tuples
• Unity Scripting API Vector2/Vector2Int class, Floor2Int
• You can obtain obstacle polygon coordinates with poly.getPoints() (floating point in world coordinates or WCS) or poly.getIntegerPoints() (pre-converted to integer-discretized form). You should perform geometric tests using the integer versions.
  • See Computational Geometry regarding floating point inaccuracies and integer discretized coordinates
• The points of a polygon are stored in counterclockwise (CCW) order. Each adjacent pair (and the wraparound) returned by getIntegerPoints()/getPoints() is a line segment. Here is an efficient loop due to no modulus or multiplies while still handling wraparound.

var len = polyVerts.Length;
for (int i = 0, j = len - 1; i < len; j = i++)
{
    var p1 = polyVerts[j];
    var p2 = polyVerts[i];
    
    // Do something with line seg, p1->p2
}

Creating the Grid

Algorithm

• Determine number of grid rows and columns based on canvas width and height and cell width (square)

Grid Size

The returned grid’s dimensions must be as follows: grid_size_x is the largest integer such that grid_size_x * cellWidth is less than or equal to the canvasWidth, and grid_size_y is the largest integer such that grid_size_y * cellWidth is less than or equal to the canvasHeight. If either grid_size_x or grid_size_y would be 0, then a value of 1 will be used instead.

• Create Grid using new bool[rows, columns]- by default all your values will be false
• Loop through each cell (for each column x and an inner loop for each row y) and decide what would make that cell be navigable (i.e. flipped to true).
• If either of the following is true, then grid[x, y] is true:
  • No polygon vertex intersects any edge
    • For each polygon, grab each vertix and determine if it crosses any of the edges on your square
    • Shrink method recommended
      • Rect- 0.001f less all around
      • RectInt (integer, better)- minimums are shrunk by adding 1, the maximums by substracting 1
  • No cell (RectInt) corners are inside a polygon
    • Determine if any shrunk corners is inside said polygon.

Shrink Cells

CreateGrid.cs

        // Create(): Creates a grid lattice discretized space for navigation.
        // canvasOrigin: bottom left corner of navigable region in world coordinates
        // canvasWidth: width of navigable region in world dimensions
        // canvasHeight: height of navigable region in world dimensions
        // cellWidth: target cell width (of a grid cell) in world dimensions
        // obstacles: a list of collider obstacles
        // grid: an array of bools. A cell is true if navigable, false otherwise
        //    Example: grid[x_pos, y_pos]
 
        public static void Create(Vector2 canvasOrigin, float canvasWidth, float canvasHeight, float cellWidth,
            List<Polygon> obstacles,
            out bool[,] grid
            )
        {
            // ignoring the obstacles for this limited demo; 
            // Marks cells of the grid untraversable if geometry intersects interior!
            // Carefully consider all possible geometry interactions
 
            // also ignoring the world boundary defined by canvasOrigin and canvasWidth and canvasHeight
            int n = Mathf.FloorToInt(canvasWidth/cellWidth);
            grid = new bool[n, n]; // default false
 
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    Debug.Log(grid[i, j]);
                    Vector2Int minCellBounds = new Vector2Int(CreateGrid.Convert(canvasOrigin.x + i * cellWidth), CreateGrid.Convert(canvasOrigin.y + j * cellWidth));
                    Vector2Int maxCellBounds = new Vector2Int(minCellBounds.x + CreateGrid.Convert(cellWidth), minCellBounds.y + CreateGrid.Convert(cellWidth));
 
                    bool containsObj = false;
                    // Loop through polygons 
                    for (int k = 0; k < obstacles.Count; k++)
                    {
                        Vector2Int[] vertices = obstacles[k].getIntegerPoints();
                        // Iterate through the vertices
                        for (int l = 0; l < vertices.Length; l++)
                        {
                            Vector2Int p = vertices[l];
                            //Debug.Log(p);
 
                            if (CreateGrid.IsPointInsideAxisAlignedBoundingBox(minCellBounds, maxCellBounds, p))
                            {
                                Debug.Log(vertices[l]); // (600,-600)
                                Debug.Log(minCellBounds); // (4000, 4000)
                                containsObj = true;
                                break;
                            }
                        }
                    }
                    if (!containsObj)
                    {
                        grid[i, j] = true;
                    }
                }
 
            }
        }