A2- Path Networks

Intro

In A2, a path network will be generated by creating valid edges (PathEdges) connecting nodes (PathNodes), such that the AI agent can navigate between any path node without colliding with an obstacle or canvas/world boundary.

Resources

• A2 Demo
• Lectures
  • Computational Geometry
    • Line Segment Intersection
    • Point to line segement distance
  • Path Network

Tips

• Scene 7 is most useful for debugging

Overview

Set up

• Select Scenes/PathNetwork to open the scene

• Click play

  • Clicking will highlight the nearest node that has a line of sight with the mouse click

• The objective is to figure out how to connect the nodes, ensuring that none of the edges are too close to anything that would prevent the agent from traversing along the edge

Reference Implmentation

Scenes

Scene 1

Scene 1

---

Scene 2

Scene 2

---

Scene 3

Scene 3

---

Scene 4

Scene 4

---

Scene 5

Scene 5

---

Scene 6

Scene 6

---

Scene 7

Scene 7

Unit/Integration Testing

PathNetworkTest.cs

using System.Collections;
using System.Collections.Generic;
using NUnit.Framework;
using UnityEngine;
using UnityEngine.TestTools;
 
using System.Linq;
 
using GameAICourse;
using System.Text;
 
namespace Tests
{
    public class PathNetworkTest
    {
        // 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(CreatePathNetwork.StudentAuthorName, Is.Not.Contains("George P. Burdell"),
                "You forgot to change to your name!");
        }
 
 
        [Test]
        public void ExampleTest()
        {
            // Set up some parameters for testing
 
            Vector2 origin = new Vector2(-5f, -5f);
            Vector2 size = new Vector2(10f, 10f);
            List<Polygon> obstacles = new List<Polygon>();
            float agentRadius = 1f;
            List<Vector2> pathNodes = new List<Vector2>()
            {
                new Vector2(0f, 0f), //<-- In the middle of the canvas
                new Vector2(4.5f, 0f) //<-- Close to the middle of the right edge of the canvas boundary
            };
 
            // output param
 
            List<List<int>> pathEdges;
 
 
            //Execute your code!
 
            CreatePathNetwork.Create(origin, size.x, size.y, obstacles, agentRadius, agentRadius+0.01f, agentRadius*2.5f, ref pathNodes, out pathEdges, PathNetworkMode.Predefined);
 
            //Various assertions to validate your returned result
 
            Assert.That(pathEdges, Is.Not.Null);
            Assert.That(pathEdges, Has.Count.EqualTo(pathNodes.Count));
            Assert.That(pathEdges, Is.All.Not.Null);
 
            for (int i = 0; i < pathEdges.Count; ++i)
            {
                var edges = pathEdges[i];
 
                Debug.Log($"[{i}]:{string.Join(",", edges)}");
 
                //TODO check for self edges, dupe edges, out of range edge ends, etc...
 
            }
 
            // Nodes are not expected to connect because right node is too close to canvas boundary
 
            Assert.That(pathEdges, Is.All.Empty);
 
 
            // TODO add more asserts for things not tested in this example
        }
 
        // TODO write more tests!
 
 
    }
}
 

Shared Tests

castro

PathNetwork

PathNetwork class:

• Collects path nodes and builds edges between them
• Calls CreatePathNetwork.Create()
• Stores the graph and it in Unity
• Modified version also displays nodes indices

Display indices over nodes

PathNetwork.cs

//#define SAVE_CASES
 
using GameAICourse;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using UnityEngine;
using UnityEngine.UI;
 
/*
 * Class that holds all information about the path network
 *
 */
public class PathNetwork : DiscretizedSpaceMonoBehavior
{
 
    private string PathNodeMarkersGroupName = "PathNodeMarkersGroup";
 
    //public GameObject PathNodeMarkersGroup;
    public MoveBall moveBall;
    //material for drawing the path network line
    //public Material LineMaterial;
    public Color LineColor = Color.green;
 
    public GameObject pathNodePrefab;
    public GameObject pathNodeOutlinePrefab;
 
    List<GameObject> pathNodeObjects = new List<GameObject>();
 
 
    public PathNetworkMode pathNetworkMode = PathNetworkMode.Predefined;
 
    public override void Awake()
    {
        base.Awake();
 
        Obstacles = this.GetComponent<Obstacles>();
    }
 
 
    public override void Start()
    {
        base.Start();
 
        // Following commented out because presets will immediately override...
 
        //Obstacles.Init();
 
        //Bake();
 
        if (UseHardCodedCases)
            Utils.DisplayName("CreatePathNetwork", "HARD CODED CASES");
        else
            Utils.DisplayName("CreatePathNetwork", CreatePathNetwork.StudentAuthorName);
 
    }
 
    public void ResetPathNodeMarkers()
    {
        PathNodeMarkers = null;
        PurgeOutdatedPathNodeMarkers();
    }
 
 
    //private void Update()
    //{
    //    Utils.DisplayName("CreatePathNetwork", CreatePathNetwork.StudentAuthorName);
    //}
 
    //Get all child node cubes and create their corresponding path node vectors
    void Init()
    {
 
        var PathNodeMarkersGroup = GameObject.Find(PathNodeMarkersGroupName);
 
        if (PathNodeMarkersGroup != null)
        {
 
            if (PathNodeMarkersGroup.transform.childCount > 0)
            {
 
                PathNodeMarkers = new List<GameObject>(PathNodeMarkersGroup.transform.childCount);
 
                for (int i = 0; i < PathNodeMarkersGroup.transform.childCount; ++i)
                {
                    PathNodeMarkers.Add(PathNodeMarkersGroup.transform.GetChild(i).gameObject);
                }
 
 
                PathNodes = new List<Vector2>(PathNodeMarkers.Count);
 
                for (int i = 0; i < PathNodeMarkers.Count; i++)
                {
                    PathNodes.Add(new Vector2(PathNodeMarkers[i].transform.position.x, PathNodeMarkers[i].transform.position.z));
                }
 
            }
 
        }
 
    }
 
 
    void PurgeOutdatedLineViz()
    {
 
        var linegroup = this.transform.Find(Utils.LineGroupName);
 
        if (linegroup != null)
        {
            linegroup.name = "MARKED_FOR_DELETION";
            linegroup.gameObject.SetActive(false);
            Destroy(linegroup.gameObject);
        }
    }
 
 
 
    //void CreateNetworkLines()
    //{
    //    PurgeOutdatedLineViz();
 
    //    var parent = Utils.FindOrCreateGameObjectByName(this.gameObject, Utils.LineGroupName);
 
 
    //    HashSet<System.Tuple<int, int>> hs = new HashSet<System.Tuple<int, int>>();
 
 
    //    if (PathEdges != null)
    //    {
    //        for (int i = 0; i < PathEdges.Count; ++i)
    //        {
    //            var pts = PathEdges[i];
    //            if (pts != null)
    //            {
    //                for (int j = 0; j < pts.Count; ++j)
    //                {
    //                    var smaller = i;
    //                    var bigger = pts[j];
 
    //                    if (bigger < smaller)
    //                    {
    //                        var tmp = bigger;
    //                        bigger = smaller;
    //                        smaller = tmp;
    //                    }
 
    //                    var tup = new System.Tuple<int, int>(smaller, bigger);
    //                    if (!hs.Contains(tup))
    //                    {
    //                        hs.Add(tup);
    //                        Utils.DrawLine(PathNodes[i], PathNodes[pts[j]], Utils.ZOffset, parent, Color.green, LineMaterial);
    //                    }
 
    //                }
    //            }
    //        }
    //    }
    //}
 
 
 
#if SAVE_CASES
    int caseCount = 0;
#endif
 
    public bool UseHardCodedCases = false;
 
 
    public override void Bake()
    {
        base.Bake();
 
        Init();
 
        //PathNodes = new List<Vector2>(PathNodeMarkers.Count);
 
        //for (int i = 0; i < PathNodeMarkers.Count; i++)
        //{
        //    PathNodes.Add(new Vector2(PathNodeMarkers[i].transform.position.x, PathNodeMarkers[i].transform.position.z));
        //}
 
        var obst = Obstacles.getObstacles();
 
        var polys = new List<Polygon>(obst.Count);
 
        for (int i = 0; i < obst.Count; ++i)
        {
            polys.Add(obst[i].GetPolygon());
        }
 
 
 
        List<List<int>> pathEdges;
 
 
 
        PathNetworkCase overrideCase = null;
 
        if (UseHardCodedCases)
        {
            var pnt = new PathNetworkCase(0, BottomLeftCornerWCS, Boundary.size.x, Boundary.size.z, polys, moveBall.Radius, PathNodes);
 
            overrideCase = HardCodedPathNetworkCases.FindCase(pnt);
        }
 
        if (overrideCase != null)
        {
            PathEdges = overrideCase.pathEdges;
        }
        else
        {
 
            //pathEdges = new List<List<int>>(PathNodes.Count);
 
            //for (int i = 0; i < PathNodes.Count; ++i)
            //{
            //    pathEdges.Add(new List<int>());
            //}
            //PathEdges = pathEdges;
 
            //Debug.Log("PathNetwork: calling student code!");
 
            // clone because we might refuse changes passed back from Create()
            List<Vector2> pathNodes = null;
 
            if (pathNetworkMode == PathNetworkMode.PointsOfVisibility)
            {
                pathNodes = new List<Vector2>();
            }
            else 
            {
                pathNodes = new List<Vector2>(PathNodes);
            }
 
            CreatePathNetwork.Create(BottomLeftCornerWCS, Boundary.size.x, Boundary.size.z,
polys, moveBall.Radius, moveBall.Radius+0.001f, moveBall.Radius*2.5f, ref pathNodes, out pathEdges, pathNetworkMode);
 
            if (pathNetworkMode == PathNetworkMode.PointsOfVisibility)
            {
                //accept overwrite
                PathNodes = pathNodes;
            }
 
            PathEdges = pathEdges;
 
        }
 
 
#if SAVE_CASES
 
PathNetworkCase gc = new PathNetworkCase(caseCount++, BottomLeftCornerWCS, Boundary.size.x, Boundary.size.z, polys, moveBall.Radius, PathNodes, PathEdges);
 
        using (var OutFile = new StreamWriter("cases.txt", true))
        {
 
            OutFile.WriteLine(gc);
        }
 
#endif
 
 
 
        PurgeOutdatedLineViz();
        CreateNetworkLines(Utils.ZOffset);
 
        CreatePathNodeMarkerObjects(PathNodes);
 
 
    }
 
 
 
 
 
    void PurgeGroup(string gname)
    {
        var group = this.transform.Find(gname);
 
        if (group != null)
        {
            group.name = "MARKED_FOR_DELETION";
            group.gameObject.SetActive(false);
            Destroy(group.gameObject);
        }
    }
 
    void PurgeOutdatedPathNodeMarkers()
    {
        PurgeGroup(PathNodeMarkersGroupName);
    }
 
 
    void CreatePathNodeMarkerObjects(List<Vector2> pathNodes)
    {
 
        // Debug.Log($"CreatePathNodeMarkerObjects(): num: {pathNodes.Count}");
 
 
 
        PurgeOutdatedPathNodeMarkers();
 
        var parent = Utils.FindOrCreateGameObjectByName(this.gameObject, PathNodeMarkersGroupName);
 
 
        GameObject prefab = pathNodePrefab;
 
        if (HideBlockingDetails)
        {
            prefab = pathNodeOutlinePrefab;
        }
 
        int i = 0;
        Camera cam = Camera.main;
 
        // Load the Arial font from the Unity Resources folder.
        Text text;
        Font font = (Font)Resources.GetBuiltinResource(typeof(Font), "LegacyRuntime.ttf");
 
        foreach (Vector2 pn in pathNodes)
        {
            GameObject pno = Instantiate(prefab, new Vector3(pn.x, Utils.ZOffset + 0.01f, pn.y), Quaternion.identity, parent.transform);
            pno.transform.localScale = Vector3.one * 2f * moveBall.Radius;
            pathNodeObjects.Add(pno);
 
 
            // Create Canvas GameObject.
            GameObject canvasGO = new GameObject();
            canvasGO.name = "Canvas";
            canvasGO.AddComponent<Canvas>();
            canvasGO.AddComponent<CanvasScaler>();
            canvasGO.AddComponent<GraphicRaycaster>();
            canvasGO.transform.parent = GameObject.Find(PathNodeMarkersGroupName).transform;
 
            // Get canvas from the GameObject.
            Canvas canvas;
            canvas = canvasGO.GetComponent<Canvas>();
            canvas.renderMode = RenderMode.ScreenSpaceOverlay;
 
            // Create the Text GameObject.
            GameObject textGO = new GameObject();
            textGO.transform.parent = canvasGO.transform;
            textGO.AddComponent<Text>();
 
 
            // Set Text component properties.
            text = textGO.GetComponent<Text>();
            text.font = font;
            text.text = i.ToString();
            text.fontSize = 48;
            text.alignment = TextAnchor.MiddleCenter;
 
            // Provide Text position and size using RectTransform.
            RectTransform rectTransform;
            rectTransform = text.GetComponent<RectTransform>();
            var newPos = cam.WorldToScreenPoint(new Vector3(pno.transform.position.x, 0, pno.transform.position.z));
            rectTransform.position = new Vector2(newPos.x, newPos.y);
 
            RectTransform objectRectTransform = canvasGO.GetComponent<RectTransform>();
            i++;
        }
    }
 
    }

CreatePathNetwork

• In CreatePathNetwork.cs, implement CreatePathNetwork.Create() in order to generate a path network from pathNodes.

CreatePathNetwork.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.
//test
using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
 
namespace GameAICourse
{
 
    public class CreatePathNetwork
    {
 
        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 Vector2 converted to Vector2Int according to default scaling factor (1000)
        public static Vector2Int ConvertToInt(Vector2 v)
        {
            return CG.Convert(v);
        }
 
        // Helper method provided to help you implement this file. Leave as is.
        // Returns float converted to int according to default scaling factor (1000)
        public static int ConvertToInt(float v)
        {
            return CG.Convert(v);
        }
 
        // Helper method provided to help you implement this file. Leave as is.
        // Returns Vector2Int converted to Vector2 according to default scaling factor (1000)
        public static Vector2 ConvertToFloat(Vector2Int v)
        {
            float f = 1f / (float)CG.FloatToIntFactor;
            return new Vector2(v.x * f, v.y * f);
        }
 
        // Helper method provided to help you implement this file. Leave as is.
        // Returns int converted to float according to default scaling factor (1000)
        public static float ConvertToFloat(int v)
        {
            float f = 1f / (float)CG.FloatToIntFactor;
            return v * f;
        }
 
 
        // Helper method provided to help you implement this file. Leave as is.
        // Returns true is segment AB intersects CD properly or improperly
        static public bool Intersects(Vector2Int a, Vector2Int b, Vector2Int c, Vector2Int d)
        {
            return CG.Intersect(a, b, c, d);
        }
 
 
        //Get the shortest distance from a point to a line
        //Line is defined by the lineStart and lineEnd points
        public static float DistanceToLineSegment(Vector2Int point, Vector2Int lineStart, Vector2Int lineEnd)
        {
            return CG.DistanceToLineSegment(point, lineStart, lineEnd);
        }
 
 
        //Get the shortest distance from a point to a line
        //Line is defined by the lineStart and lineEnd points
        public static float DistanceToLineSegment(Vector2 point, Vector2 lineStart, Vector2 lineEnd)
        {
            return CG.DistanceToLineSegment(point, lineStart, lineEnd);
        }
 
 
        // Helper method provided to help you implement this file. Leave as is.
        // Determines if a point is inside/on a CCW polygon and if so returns true. False otherwise.
        public static bool IsPointInPolygon(Vector2Int[] polyPts, Vector2Int point)
        {
            return CG.PointPolygonIntersectionType.Outside != CG.InPoly1(polyPts, point);
        }
 
        // Returns true iff p is strictly to the left of the directed
        // line through a to b.
        // You can use this method to determine if 3 adjacent CCW-ordered
        // vertices of a polygon form a convex or concave angle
 
        public static bool Left(Vector2Int a, Vector2Int b, Vector2Int p)
        {
            return CG.Left(a, b, p);
        }
 
        // Vector2 version of above
        public static bool Left(Vector2 a, Vector2 b, Vector2 p)
        {
            return CG.Left(CG.Convert(a), CG.Convert(b), CG.Convert(p));
        }
 
 
 
 
 
 
        //Student code to build the path network from the given pathNodes and Obstacles
        //Obstacles - List of obstacles on the plane
        //agentRadius - the radius of the traversing agent
        //minPoVDist AND maxPoVDist - used for Points of Visibility (see assignment doc)
        //pathNodes - ref parameter that contains the pathNodes to connect (or return if pathNetworkMode is set to PointsOfVisibility)
        //pathEdges - out parameter that will contain the edges you build.
        //  Edges cannot intersect with obstacles or boundaries. Edges must be at least agentRadius distance
        //  from all obstacle/boundary line segments. No self edges, duplicate edges. No null lists (but can be empty)
        //pathNetworkMode - enum that specifies PathNetwork type (see assignment doc)
 
        public static void Create(Vector2 canvasOrigin, float canvasWidth, float canvasHeight,
            List<Polygon> obstacles, float agentRadius, float minPoVDist, float maxPoVDist, ref List<Vector2> pathNodes, out List<List<int>> pathEdges,
            PathNetworkMode pathNetworkMode)
        {
 
            //STUDENT CODE HERE
 
            pathEdges = new List<List<int>>(pathNodes.Count);
 
            for (int i = 0; i < pathNodes.Count; ++i)
            {
                pathEdges.Add(new List<int>());
            }
 
 
            // END STUDENT CODE
 
        }
 
 
    }
 
}

Fully connected network

public static void Create(Vector2 canvasOrigin, float canvasWidth, float canvasHeight,
    List<Polygon> obstacles, float agentRadius, float minPoVDist, float maxPoVDist, ref List<Vector2> pathNodes, out List<List<int>> pathEdges,
    PathNetworkMode pathNetworkMode)
{
    Debug.Log($"{pathNodes.Count} nodes");
    pathEdges = new List<List<int>>(pathNodes.Count);
    Debug.Log($"Capacity: {pathEdges.Capacity}");
 
    for (int i = 0; i < pathNodes.Count; ++i)
    {
        pathEdges.Add(new List<int>());
        Debug.Log("PathNode " + i + ": " + pathNodes[i]);
    }
 
    for (int y = 0; y < pathEdges.Count; y++) {
        for (int z = 0; z < pathNodes.Count; z++)
        {
            if (y != z)
            {
                pathEdges[y].Add(z);
            }  
        }
        Debug.Log("PathEdge " + y + ": " + string.Join(", ", pathEdges[y]));
    }
}
 

Boundary Conditions

Make sure any edge in the path network is traversable by an agent that has physical size. That is, edges in the path network should never come too close to any Obstacle such that an agent blindly following the path edge collides with an Obstacle (or the edges of the map).

TODO

• No self edges
• No duplicate edges
• Minimum distance between nodes of an edge and canvas edge > agentRadius
• Minimum distance between nodes of an edge and obstacle edges > agentRadius
• Minimum distance from path edge to obstacle vertices > agentRadius

Helper Methods

Tip

In terms of Computational Geometry, the DistanceToLineSegment() works best with floats. You can use the poly.getPoints(), which are unscaled floats. The poly.getIntegerPoints() are the equivalent vectors in scaled integer form (by 1000)

Helper Methods

public static Vector2Int ConvertToInt(Vector2 v)
{
    return CG.Convert(v);
}
 
// Helper method provided to help you implement this file. Leave as is.
// Returns float converted to int according to default scaling factor (1000)
public static int ConvertToInt(float v)
{
    return CG.Convert(v);
}
 
// Helper method provided to help you implement this file. Leave as is.
// Returns Vector2Int converted to Vector2 according to default scaling factor (1000)
public static Vector2 ConvertToFloat(Vector2Int v)
{
    float f = 1f / (float)CG.FloatToIntFactor;
    return new Vector2(v.x * f, v.y * f);
}
 
// Helper method provided to help you implement this file. Leave as is.
// Returns int converted to float according to default scaling factor (1000)
public static float ConvertToFloat(int v)
{
    float f = 1f / (float)CG.FloatToIntFactor;
    return v * f;
}
 
 
// Helper method provided to help you implement this file. Leave as is.
// Returns true is segment AB intersects CD properly or improperly
static public bool Intersects(Vector2Int a, Vector2Int b, Vector2Int c, Vector2Int d)
{
    return CG.Intersect(a, b, c, d);
}
 
 
//Get the shortest distance from a point to a line
//Line is defined by the lineStart and lineEnd points
public static float DistanceToLineSegment(Vector2Int point, Vector2Int lineStart, Vector2Int lineEnd)
{
    return CG.DistanceToLineSegment(point, lineStart, lineEnd);
}
 
 
//Get the shortest distance from a point to a line
//Line is defined by the lineStart and lineEnd points
public static float DistanceToLineSegment(Vector2 point, Vector2 lineStart, Vector2 lineEnd)
{
    return CG.DistanceToLineSegment(point, lineStart, lineEnd);
}
 
 
// Helper method provided to help you implement this file. Leave as is.
// Determines if a point is inside/on a CCW polygon and if so returns true. False otherwise.
public static bool IsPointInPolygon(Vector2Int[] polyPts, Vector2Int point)
{
    return CG.PointPolygonIntersectionType.Outside != CG.InPoly1(polyPts, point);
}
 
// Returns true iff p is strictly to the left of the directed
// line through a to b.
// You can use this method to determine if 3 adjacent CCW-ordered
// vertices of a polygon form a convex or concave angle
 
public static bool Left(Vector2Int a, Vector2Int b, Vector2Int p)
{
    return CG.Left(a, b, p);
}
 
// Vector2 version of above
public static bool Left(Vector2 a, Vector2 b, Vector2 p)
{
    return CG.Left(CG.Convert(a), CG.Convert(b), CG.Convert(p));
}