Make sure you first watch the Path Network lecture before attempting this assignment.

One of the main uses of artificial intelligence in games is to perform path planning, the search for a sequence of movements through the virtual environment that gets an agent from one location to another without running into any obstacles. For now, we will assume static obstacles. In order for an agent to engage in path planning, there must be a topography for the agent to traverse that is represented in a form that can be efficiently reasoned about.

Grid topologies discretize the environment and usually assumes an agent can be in one discrete cell or another. However, for many games such as $1$st$-$person shooters, a more continuous model of space is beneficial. Depending on the granularity of the grid, a lot of space around obstacles becomes inaccessible in grid$-$based approaches. Finally, grids result in unnecessarily large number of cell transitions. path network discretizes a continuous space into a small number of points and edges that allow transitions between points. However, unlike a grid topology, a path network does not require the agent to be at one of the path nodes at all times. The agent can be at any point in the terrain. When the agent needs to move to a different location and an obstacle is in the way, the agent can move to the nearest path node accessible by straight$-$line movement and then find a path through the edges of the path network to another path node near to the desired destination. In this assignment, you will be provided with different terrains with obstacles and hard$-$coded

path nodes. You must write the code to generate the path network, as a set of edges

between path nodes. An edge between path nodes exists when $($a$)$ there is no obstacle or

boundary wall between the two path nodes, $($b$)$ there is sufficient space on either side of the

edge so that an agent can follow the line without colliding with any obstacles or boundary

wall and $($c$)$ a path node that is inside the boundary but outside of any obstacles. Nodes that

are outside of the boundary or inside of obstacles, should not connect.

Furthermore, there should be edges in both directions. If there is an edge from Node $A$ to

Node B$,$ then there should be an edge from Node B to Node A$.$ Also, if there should be an

edge from Node A to Node B$,$ it should appear exactly once in the edge list for Node A $($no

duplicates$).$ Also, no nodes should link to self.

If two nodes are arbitrarily close together, including possibly located at exactly the same

location, they should still be connected.

What you need to know

Please consult homework $1$ for background on the Unity Project. In addition to the

information about the game engine provided there, the following applies.

Also, make sure you first watch the Path Network lecture before attempting this assignment.

CreatePathNetwork

This is the only file you will be modifying and submitting for this homework. It provided

functionality to create a path network from provided pathNodes.

String StudentAuthorName $-$ Please change to your name

Create$()$

This is the method you will be finishing. You can create helper methods in the same source

code file if you like.

Parameters:

Vector$2$ canvasOrigin $-$ Bottom left corner of navigable space

float canvasWidth $-$ Width of navigable space

float canvasHeight $-$ Height of navigable space

List float minPoVDist $-$ The minimum distance a single point of visibility can be from the

vertex or lines of angle that is bisected. Only used when

generating PoVs

float maxPoVDist $-$ The maximum distance a single create a path planning alogrithm in c# for a unity game that avoids obstacles implement it into the function below code :

$//$

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

$($

Vector

$2$

$$canvasOrigin$,$ float canvasWidth, float canvasHeight,

$$ List obstacles, float agentRadius, float minPoVDist, float maxPoVDist, ref List pathNodes, out List

$>$

$$pathEdges$,$

$$ PathNetworkMode pathNetworkMode

$)$

$$

$\{$

$$

$//$

STUDENT CODE HERE

$$ pathEdges

$=$

$$new List

$>$

$($

pathNodes

$.$

Count

$)$

;

$$ for

$($

int i

$=$

$0$

; i

$$

$$pathNodes$.$Count;

$+$

$+$

i

$)$

$$

$\{$

$$ pathEges.Add

$($

new List

$())$

;

$$

$\}$

$$

$//$

$$END STUDENT CODE

$$