This tutorial will solve graph-based pathfinding using C# in Unity by applying a generic pathfinder.
This tutorial is Part 4 of my tutorial series on Pathfinding Using C# in Unity.
In our last tutorial, Implement a Generic Pathfinder in Unity using C#, we implemented a generic pathfinder in Unity using C#. In this tutorial, we will use that generic pathfinder and apply it to a graph. We will then visualise this graph in Unity and see pathfinding in action.
Pathfinding Playground
The prerequisite for this tutorial is Part 1 – Implement a Generic Pathfinder in Unity using C#.
In Part 1, we implemented a Generic Pathfinder (Prerequisite).
In Part 2, we solved the 8-puzzle problem by applying our Generic Pathfinder (Not a prerequisite but another example use-case of the generic pathfinder).
In Part 3, we solved the 2D grid-based pathfinding using C# and demonstrated the application in Unity (Not a prerequisite but another example use-case of the generic pathfinder).
Contact me
Find the GitHub repository of this tutorial at https://github.com/shamim-akhtar/tutorial-pathfinding/tree/part-4-graph.
Click to try the WebGL version below. NOTE: The WebGL version might not work for mobile devices.
Solution Approach
We will approach the solution by first modelling the graph as a network of vertices, connecting the graph with our generic pathfinder, and visualising the graph-based pathfinding in Unity.
What is a Graph
A graph is an abstract data structure that comprises a set of vertices (also called nodes) and the connectivity between these vertices (edges).
A graph is a directed graph if the edges have a one-way direction; that is to say, we can traverse each edge in only a single direction. This figure shows a simple directed graph with five vertices and four edges.
A graph is an undirected graph if the vertices are connected, where all the edges are bidirectional (or there is no direction). The figure below shows a graph with five vertices and four edges, with two edges (double arrows) as undirected and two edges (single arrows) as directed.
For a detailed understanding of graphs, please refer to Mathworks on Directed and Undirected Graphs. You can also see it in my references section below.
Implementing a Graph Data Structure in C#
Create a C# file and call it Graph.cs. In Implement a Generic Pathfinder in Unity using C#, we implemented an abstract Node class. We will now create a new class called Vertex that will extend this abstract Node.
The original abstract Node class is in the PathFinder.cs file.
The Vertex Class.
The Vertex class is straightforward. It inherits the abstract Node from the PathFinder and adds two lists to hold the cost and the neighbour vertices.
We will put the Vertex class within the main Graph class. However, if you want, then you can also keep this class separate from Graph.
using System.Collections;
using System.Collections.Generic;
using GameAI.PathFinding;
public class Graph<T>
{
public class Vertex : Node<T>
{
// The list to store the cost associated
// with the traversal of each edge.
private List<float> mCosts = new List<float>();
// The list to store all the neighbours for this vertex.
private List<Node<T>> mNeighbours = new List<Node<T>>();
public Vertex(T value)
: base(value)
{ }
public Vertex(T value, List<Node<T>> neighbours)
: base(value)
{
mNeighbours = neighbours;
}
public List<Node<T>> Neighbours
{
get
{
return mNeighbours;
}
}
public List<float> Costs
{
get
{
return mCosts;
}
}
public override List<Node<T>> GetNeighbours()
{
return mNeighbours;
}
}
}Code language: C# (cs)The Graph Class
We will now implement the graph-related functionalities.
Constructors
The default constructor inits the list of Vertex to a null value.
public Graph()
: this(null)
{
}Code language: C# (cs)The following constructor takes in a list of Vertex and sets it to the internal private member variable mVertices.
public Graph(List<Vertex> mVertices)
{
if (mVertices == null)
this.mVertices = new List<Vertex>();
else
this.mVertices = mVertices;
}Code language: C# (cs)Add Vertex Function
Next, we will have the AddVertex functions that allow adding a new Vertex into the Vertex list. We shall enable two different methods for AddVertex, one that takes in a Vertex and one that takes in the value-type of the generic graph.
// Add a vertex to the graph.
public void AddVertex(Vertex node)
{
mVertices.Add(node);
mOnAddNode?.Invoke(node);
}
// Add a vertex by taking in the value
// type of the graph. In this case, we
// create a new Vertex internally and
// add to the graph.
public void AddVertex(T value)
{
AddVertex(new Vertex(value));
}
Code language: C# (cs)In the highlighted line above, you may see that I have invoked a delegate with the added Vertex. This invocation allows the flexibility to the caller to take some action when we add a Vertex. For example, show the newly added Vertex in a different colour.
The Delegates for Flexibility
So, let’s go and define these delegates.
#region Delegates
public delegate void DelegateGraphNode(Vertex n);
public delegate void DelegateOnAddEdge(Vertex a, Vertex b);
public DelegateGraphNode mOnAddNode;
public DelegateGraphNode mOnRemoveNode;
public DelegateOnAddEdge mOnAddDirectedEdge;
#endregion
Code language: C# (cs)Add Directed and Undirected Edge
// Add a directed edge with the associated cost.
public void AddDirectedEdge(
Vertex from,
Vertex to,
float cost)
{
from.Neighbours.Add(to);
from.Costs.Add(cost);
mOnAddDirectedEdge?.Invoke(from, to);
}
// Add an undirected edge with the associated cost
// as same for both directions.
public void AddUndirectedEdge(
Vertex a,
Vertex b,
float cost)
{
AddUndirectedEdge(a, b, cost, cost);
}
// Add an undirected edge with different
// associated costs for each direction.
public void AddUndirectedEdge(
Vertex a,
Vertex b,
float cost1,
float cost2)
{
AddDirectedEdge(a, b, cost1);
AddDirectedEdge(b, a, cost2);
}Code language: C# (cs)You can see that adding an undirected edge is similar to adding two directed edges.
Next, we add a few utility functions.
Remove a Vertex
public bool Remove(T value)
{
// first remove the node from the mVertices
Vertex nodeToRemove = FindByValue(mVertices, value);
if (nodeToRemove == null)
// node wasn't found
return false;
mOnRemoveNode(nodeToRemove);
// otherwise, the node was found
mVertices.Remove(nodeToRemove);
// enumerate through each node in the mVertices,
// removing edges to this node
foreach (Vertex gnode in mVertices)
{
int index = gnode.Neighbours.IndexOf(nodeToRemove);
if (index != -1)
{
// remove the reference to the node
// and associated cost
gnode.Neighbours.RemoveAt(index);
gnode.Costs.RemoveAt(index);
}
}
return true;
}
Code language: C# (cs)Finding Vertex
// Find a vertex that has a T of value.
public static Vertex FindByValue(
List<Vertex> nodes,
T value)
{
// search the list for the value
foreach (Vertex node in nodes)
if (node.Value.Equals(value))
return node;
// if we reached here, we didn't find a matching node
return null;
}
public bool Contains(T value)
{
return FindByValue(mVertices, value) != null;
}
Code language: C# (cs)Properties
We expose the Vexter list and the number of vertices as get only properties.
#region Properties
public List<Vertex> Vertices
{
get
{
return mVertices;
}
}
public float Count
{
get { return mVertices.Count; }
}
#endregion
Code language: C# (cs)We have completed our implementation of the Graph data structure.
Graph Visualisation and The Unity Project
Next, we will create our visualisation in Unity to show the vertices and the edges of the graph.
If you are starting fresh, you can grab the Unity project from my GitHub repository for the tutorial, Part 3. Open up the project in Unity and create a new Scene. Name it Demo_GraphPathFinding.
In our previous section, we implemented the Graph data structure. However, that data structure is generic. To test our pathfinding, we will need to create a concrete implementation of the graph.
Our premise will be a bus ride from one stop to another stop within a network of bus stops.
The Bus Stop Class
Let’s create a new class called the BusStop. We will inherit this class from System.IEquatable<BusStop>. We do so because we will need a comparison operator to compare one bus stop with another.
We will have only two variables for our BusStop. One will be the location, and the other will be the name of the BusStop. Note that these two variables are only for demonstration of our bus stops. If you require other variables, then you can add them as you wish.
Our location variable can be latitude and longitude or plain simple cartesian coordinates.
public class BusStop : System.IEquatable<BusStop>
{
/// <summary>
/// We will have only two variables for our BusStop.
/// One will be the location, and the other will be
/// the name of the BusStop. Note that these two variables
/// are only for demonstration of our bus stops.
///
/// If you require other variables, then you can add
/// them as you wish. Our location variable can be
/// latitude and longitude or plain simple cartesian coordinates.
/// </summary>
public string Name { get; set; }
public Vector2 Point { get; set; }
}Code language: C# (cs)We add a few constructors besides the default constructor for our convenience.
#region Constructors
public BusStop()
{
}
public BusStop(string names, Vector2 point)
{
Name = names;
Point = point;
}
public BusStop(string name, float x, float y)
{
Name = name;
Point = new Vector2(x, y);
}
#endregion
Code language: C# (cs)Next, we implement the functions associated with Equals and the hash function for comparisons.
#region Functions related to Equal to hashcode
public override bool Equals(object obj) =>
this.Equals(obj as BusStop);
public bool Equals(BusStop p)
{
if (p is null)
{
return false;
}
// Optimization for a common success case.
if (System.Object.ReferenceEquals(this, p))
{
return true;
}
// If run-time types are not exactly the same,
// return false.
if (this.GetType() != p.GetType())
{
return false;
}
// Return true if the fields match.
// Note that the base class is not invoked
// because it is System.Object, which defines
// Equals as reference equality.
return (Name == p.Name);
}
public override int GetHashCode() =>
(Name, Point).GetHashCode();
#endregion
Code language: C# (cs)Finally, we implement methods that the pathfinder will use. These functions are related to cost functions.
#region The cost functions and other utility functions
public static float Distance(BusStop a, BusStop b)
{
return (a.Point - b.Point).magnitude;
}
public static float GetManhattanCost(
BusStop a,
BusStop b)
{
return Mathf.Abs(a.Point.x - b.Point.x) +
Mathf.Abs(a.Point.y - b.Point.y);
}
public static float GetEuclideanCost(
BusStop a,
BusStop b)
{
return GetCostBetweenTwoStops(a, b);
}
public static float GetCostBetweenTwoStops(
BusStop a,
BusStop b)
{
return (a.Point - b.Point).magnitude;
}
public static float GetAngleBetweenTwoStops(
BusStop a,
BusStop b)
{
float delta_x = b.Point.x - a.Point.x;
float delta_y = b.Point.y - a.Point.y;
float theta_radians = Mathf.Atan2(delta_y, delta_x);
return theta_radians;
}
#endregion
Code language: C# (cs)The Vertex Visualization
In this section, we will create a simple visualisation for a vertex (or node) in the graph. Our objective is to show the vertex as a circle and the edges as line arrows.
- Create an empty game object and name it Vertex_Viz. Reset the transform to make it at 0, 0, 0.
- Add two circle sprites to this empty game object and name them Inner and Outer.
- Make the Outer sprite’s scale values as 0.65, 0.65 and 0.65 and the Inner sprite’s scale value as 0.55, 0.55, 0.55. You can also try other values. These are the values that I found to suit the visualisation for our demo.
- Add a Circle collider (for raycast picking) to Vertex_Viz.
We will use this game object to represent our vertices in the graph. However, as our ortho camera size increases, it will look smaller and smaller. We want our vertex to be of the same size all the time. Below is a script that will make a sprite constant in length no matter how big or small our ortho camera size is.
Create a new C# script named ConstantScreenSizeForSprite. Add the following code to it.
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class ConstantScreenSizeForSprite : MonoBehaviour
{
public float mOriginalCameraSize = 10.0f;
public Vector3 OrigScale = Vector3.one;
void LateUpdate()
{
if (Camera.main.orthographicSize > 0.1f)
{
transform.localScale =
Camera.main.orthographicSize /
mOriginalCameraSize * OrigScale;
}
}
}Code language: C# (cs)- Attach the above script to our Vertex_Viz game object.
- Drag and drop this game object to the Prefabs folder to make it a prefab.
The Edge Visualisation
In the above section, we visualised a vertex as a constant size of two concentric circles with different colours. In this section, we will implement the edges visualisation.
- Create a new script and call it Vertex_Viz.
- Add a private variable of type Graph<BusStop>.Vertex.
- Allow a property to access the value of mVertex as readonly.
public Graph<BusStop>.Vertex Vertex
{
get
{
return mVertex;
}
}
private Graph<BusStop>.Vertex mVertex;
Code language: C# (cs)- We will use LineRenderer to create an arrow to represent an edge. Add a variable to hold a list of game objects for our LineRenderers.
List<GameObject> mLines = new List<GameObject>();Code language: PHP (php)- Next, add a method to get or create a LineRenderer.
private LineRenderer GetOrCreateLine(int index)
{
if (index >= mLines.Count)
{
GameObject obj = new GameObject();
obj.name = "line_" + index.ToString();
obj.transform.SetParent(transform);
obj.transform.position = new Vector3(0.0f, 0.0f, -1.0f);
LineRenderer lr = obj.AddComponent<LineRenderer>();
ConstantScreenLineWidth clw =
obj.AddComponent<ConstantScreenLineWidth>();
mLines.Add(obj);
lr.material = new Material(Shader.Find("Sprites/Default"));
lr.startColor = Color.green;
lr.endColor = Color.green;
}
return mLines[index].GetComponent<LineRenderer>();
}
Code language: C# (cs)Like our ConstantScreenSizeForSprite we create a new script called ConstantScreenLineWidth and attach it to our game object with the LineRenderer component. You can see this in the highlighted line. This script will ensure that our LineRenderer remains the same width with changes in the screen and ortho size.
- Finally, implement the SetVertex method.
public void SetVertex(Graph<BusStop>.Vertex vertex)
{
mVertex = vertex;
for (int i = 0; i < mVertex.Neighbours.Count; ++i)
{
Graph<BusStop>.Vertex n =
mVertex.Neighbours[i] as Graph<BusStop>.Vertex;
Vector3 a = new Vector3(
mVertex.Value.Point.x,
mVertex.Value.Point.y,
-1.0f);
Vector3 b = new Vector3(
n.Value.Point.x,
n.Value.Point.y,
-1.0f);
// find the direction.
Vector3 dir = (b - a);
float distance = dir.magnitude;
dir.Normalize();
// instead of percentage use fixed lengths
// and arrow heads so that they dont scale.
Vector3 c = a + dir * 0.22f;
Vector3 d = b - dir * 0.2f;
Vector3 e = b - dir * 0.31f;
Vector3 f = b - dir * 0.3f;
float p1 = (e - c).magnitude / (d - c).magnitude;
float p2 = (f - c).magnitude / (d - c).magnitude;
LineRenderer lr = GetOrCreateLine(i);
lr.widthCurve = new AnimationCurve(
new Keyframe(0, 0.05f),
new Keyframe(p1, 0.05f), // neck of arrow
new Keyframe(p2, 0.25f), // max width of arrow head
new Keyframe(1, 0f)); // tip of arrow
lr.positionCount = 4;
lr.SetPositions(
new Vector3[]
{
c,
e,
f,
d
});
}
}
Code language: C# (cs)The SetVertex method is the method that creates the edges for a vertex by iterating through its neighbours. We are using AnimationCurve to make the arrow. I will write a separate tutorial on How to Create an Arrow in Unity using LineRenderer.
For now, copy the code and use it. To make it proper, I will need to refactor the above code as well. There are a lot of hardcoded values within the code. I will leave it for another day.
In short, the AnimationCurve associated with the LineRenderer will make the line an arrow. The AnimationCurve is as shown below.
We will connect this script at runtime in our code. Right now, we leave the Vertex_Viz.cs as is.
The Bus Stop Graph
In the previous section, we implemented the BusStop. We will now implement the bus stop network, alternately called the BusStopGraph. We could have imported this information from some readily available sources.
However, for the sake of this tutorial, we will challenge ourselves and create a random network of bus stops and convert them into a graph. I thought this would be an interesting exercise to attempt at this.
We can create a random graph in many ways, but those graphs don’t look suitable for a proper bus stop network.
After a few experiments, I created a random bus stop network. I will explain my process below. Of course, you can use your method to generate a random network of bus stops.
- Create an empty game object and name it BusStopGraph.
- Select this game object and add a new script component. Call it BusStopGraph. Double click the BusStopGraph script file and open it in Visual Studio.
- Add the following variables.
public class BusStopGraph : MonoBehaviour
{
Graph<BusStop> mBusStopGraph = new Graph<BusStop>();
private Rect mExtent = new Rect();
[SerializeField]
GameObject VertexPrefab;
[SerializeField]
NPC Npc;
[SerializeField]
Transform Destination;
// Our generic pathfinder.
// I have used here AStarPathFinder. You can also
// use the DijkstraPathFinder or the GreedyPathFinder
AStarPathFinder<BusStop> mPathFinder =
new AStarPathFinder<BusStop>();
// The goal vertex
Graph<BusStop>.Vertex mGoal;
// The start vertex.
Graph<BusStop>.Vertex mStart;
LineRenderer mPathViz;
Code language: C# (cs)In the above code, the first highlighted line uses a script component NPC. You can find the NPC script from GitHub. It is a simple script that allows moving a sprite from one waypoint to another smoothly. I find this script very useful for quick prototyping and demo.
The second highlighted line uses a transform that represents the destination visually. You can create a circle sprite with a different colour and set it to this serializable field through the Unity editor.
Create Random Graph Function
In this section, we will create a random graph that represents the network of bus stops.
void CreateRandomGraph()
{
//Random.InitState(10);
int rows_cols =10;
for (int i = 0; i < rows_cols; ++i)
{
for (int j = 0; j < rows_cols; ++j)
{
float toss = Random.Range(0.0f, 1.0f);
if (toss >= 0.70f)
{
mBusStopGraph.AddVertex(
new BusStop("stop_" + i + "_" + j, i, j));
}
}
}
// find the cost between all the vertices.
List<List<float>> distances =
new List<List<float>>(mBusStopGraph.Count);
List<List<float>> angles =
new List<List<float>>(mBusStopGraph.Count);
for (int i = 0; i < mBusStopGraph.Count; ++i)
{
distances.Add(new List<float>());
angles.Add(new List<float>());
for (int j = 0; j < mBusStopGraph.Count; ++j)
{
distances[i].Add(BusStop.Distance(
mBusStopGraph.Vertices[i].Value,
mBusStopGraph.Vertices[j].Value));
angles[i].Add(BusStop.GetAngleBetweenTwoStops(
mBusStopGraph.Vertices[i].Value,
mBusStopGraph.Vertices[j].Value));
}
var sorted = distances[i]
.Select((x, k) => new KeyValuePair<float, int>(x, k))
.OrderBy(x => x.Key)
.ToList();
List<float> B = sorted.Select(x => x.Key).ToList();
List<int> idx = sorted.Select(x => x.Value).ToList();
// connect the nearest 2 to 6 vertices.
int index = Random.Range(2, 6);
int id = 0;
Dictionary<float, bool> angleFilled =
new Dictionary<float, bool>();
for (int j = 1; j < B.Count-1; ++j)
{
// we do not want to add collinear vertices.
if (!angleFilled.ContainsKey(angles[i][idx[j]]))
{
angleFilled[angles[i][idx[j]]] = true;
mBusStopGraph.AddDirectedEdge(
mBusStopGraph.Vertices[i],
mBusStopGraph.Vertices[idx[j]],
B[j]);
id++;
}
if (id == index)
break;
}
}
}
Code language: C# (cs)My idea is simple. Let’s break down the code and analyse it.
From lines 6 to 17, we create a lattice of points 10 by 10, but we only add a point as a vertex if the random number generated between 0 to 1 is greater than 0.7. You can play around with these numbers and see how your generated graph turns out.
Ideally, you want these numbers to be configurable.
Between lines 20 to 39, we iterate through each vertex and calculate the distances and angles between each pair of vertices. We store these values in the variables List<List<float>> distances and List<List<float>> angles.
Between lines 41 to 47, we sort the distances for each of the vertices.
In line 50, we generate a random number between 2 and 6. This number will determine the number of neighbours for the current vertex. Note that we only want to make an outgoing connection, i.e., we create a directed edge.
Between lines 56 to 71, we add the required number of nearest vertices as neighbours by calling AddDirectedEdge, only if there are no prior vertices at the same angle. We do not want to add collinearly vertices.
Initializing the Graph and Camera Parameters
We will now implement the Start method. This method will create the random graph by calling the above function, creating the visual by instantiating the vertex prefab and setting vertex to Vertex_Viz.
We will also reset our ortho camera parameters so that our camera is placed correctly.
void Start()
{
CreateRandomGraph();
for (int i = 0; i < mBusStopGraph.Vertices.Count; ++i)
{
Vector3 pos = Vector3.zero;
pos.x = mBusStopGraph.Vertices[i].Value.Point.x;
pos.y = mBusStopGraph.Vertices[i].Value.Point.y;
pos.z = 0.0f;
GameObject obj = Instantiate(
VertexPrefab,
pos,
Quaternion.identity);
obj.name = mBusStopGraph.Vertices[i].Value.Name;
Vertex_Viz vertexViz = obj.AddComponent<Vertex_Viz>();
vertexViz.SetVertex(mBusStopGraph.Vertices[i]);
//mVerticesMap[mBusStopGraph.Vertices[i].Value.Name] = obj;
}
CalculateExtent();
Camera.main.orthographicSize = mExtent.width / 1.5f;
Vector3 center = mExtent.center;
center.z = -100.0f;
Camera.main.transform.position = center;
// randomly place our NPC to one of the vertices.
int randIndex = Random.Range(0, mBusStopGraph.Count);
Npc.transform.position = new Vector3(
mBusStopGraph.Vertices[randIndex].Value.Point.x,
mBusStopGraph.Vertices[randIndex].Value.Point.y,
-1.0f);
mStart = mBusStopGraph.Vertices[randIndex];
mPathFinder.HeuristicCost = BusStop.GetManhattanCost;
mPathFinder.NodeTraversalCost = BusStop.GetEuclideanCost;
mPathFinder.onSuccess = OnPathFound;
mPathFinder.onFailure = OnPathNotFound;
// We create a line renderer to show the path.
mPathViz = transform.gameObject.AddComponent<LineRenderer>();
mPathViz.startWidth = 0.2f;
mPathViz.endWidth = 0.2f;
mPathViz.startColor = Color.magenta;
mPathViz.endColor = Color.magenta;
}
Code language: C# (cs)In line 26, we calculate the extent of our graph. The function to calculate this is given below.
Between lines 33 to 37, we randomly select one vertex as set our NPC’s default position. We also make the same vertex as the start vertex.
From lines 41 to 44, we set up our pathfinder properties by setting the delegates for cost calculation, onSuccess and onFailure. Please refer to my part 1 tutorial Implement a Generic Pathfinder in Unity using C#.
Finally, from lines 47 to 51, we create a LineRenderer to highlight the path found by the pathfinder.
The Remaining Methods
We now implement the remaining methods. These are simple to understand. So, for now, I won’t explain. The codes provided below should be sufficient.
We use the right-click to select a destination. If a path exists, then our pathfinder will find the path. The path gets highlighted, and our NPC starts moving from its current location to the destination. If a path doesn’t exist, then we print out a message in the Debug console.
void Update()
{
if (Input.GetMouseButtonDown(1))
{
RayCastAndSetDestination();
}
}
void RayCastAndSetDestination()
{
Vector2 rayPos = new Vector2(
Camera.main.ScreenToWorldPoint(Input.mousePosition).x,
Camera.main.ScreenToWorldPoint(Input.mousePosition).y);
RaycastHit2D hit = Physics2D.Raycast(rayPos, Vector2.zero, 0f);
if (hit)
{
GameObject obj = hit.transform.gameObject;
Vertex_Viz sc = obj.GetComponent<Vertex_Viz>();
if (sc == null) return;
Vector3 pos = Destination.position;
pos.x = sc.Vertex.Value.Point.x;
pos.y = sc.Vertex.Value.Point.y;
Destination.position = pos;
mGoal = sc.Vertex;
mPathFinder.Initialize(mStart, mGoal);
StartCoroutine(Coroutine_FindPathSteps());
}
}
IEnumerator Coroutine_FindPathSteps()
{
while (mPathFinder.Status == PathFinderStatus.RUNNING)
{
mPathFinder.Step();
yield return null;
}
}
public void OnPathFound()
{
PathFinder<BusStop>.PathFinderNode node =
mPathFinder.CurrentNode;
List<BusStop> reverse_indices = new List<BusStop>();
while (node != null)
{
reverse_indices.Add(node.Location.Value);
node = node.Parent;
}
mPathViz.positionCount = reverse_indices.Count;
for (int i = reverse_indices.Count - 1; i >= 0; i--)
{
Npc.AddWayPoint(new Vector2(
reverse_indices[i].Point.x,
reverse_indices[i].Point.y));
mPathViz.SetPosition(i, new Vector3(
reverse_indices[i].Point.x,
reverse_indices[i].Point.y,
0.0f));
}
// We set the goal to be the start for next pathfinding
mStart = mGoal;
}
void OnPathNotFound()
{
Debug.Log("Cannot find path to destination");
}Code language: C# (cs)Calculate Bound
This is a simple method that iterates through each node in the graph and calculates the bound of the graph. This function is useful to determine the ortho camera size.
public void CalculateExtent()
{
float minX = Mathf.Infinity;
float minY = Mathf.Infinity;
float maxX = -Mathf.Infinity;
float maxY = -Mathf.Infinity;
for (int i = 0; i < mBusStopGraph.Vertices.Count; ++i)
{
BusStop d = mBusStopGraph.Vertices[i].Value;
Vector2 p = d.Point;
if (minX > p.x) minX = p.x;
if (minY > p.y) minY = p.y;
if (maxX <= p.x) maxX = p.x;
if (maxY <= p.y) maxY = p.y;
}
mExtent.xMin = minX;
mExtent.xMax = maxX;
mExtent.yMin = minY;
mExtent.yMax = maxY;
}
Code language: C# (cs)This concludes our implementation. I rushed through the previous few sections, probably to get the tutorial completed. If you require any clarification, then please write in the comments.
The Final Product
Click play to run our pathfinding in a graph network.
Read My Other Tutorials
- 2D Grid-Based Pathfinding Using C# and Unity
- 8-Puzzle Problem Using A* in C# and Unity
- Create a Jigsaw Puzzle Game in Unity
- Implement a Generic Pathfinder in Unity using C#
- Create a Jigsaw Puzzle Game in Unity
- Generic Finite State Machine Using C#
- Implement Bezier Curve using C# in Unity
- Create a Jigsaw Tile from an Existing Image
- Create a Jigsaw Board from an Existing Image
- Solving 8 puzzle problem using A* star search
- A Configurable Third-Person Camera in Unity
- Player Controls With Finite State Machine Using C# in Unity
- Finite State Machine Using C# Delegates in Unity
- Enemy Behaviour With Finite State Machine Using C# Delegates in Unity
- Augmented Reality – Fire Effect using Vuforia and Unity
- Implementing a Finite State Machine Using C# in Unity
- Solving 8 puzzle problem using A* star search in C++
- What Are C# Delegates And How To Use Them
- How to Generate Mazes Using Depth-First Algorithm
A committed and optimistic professional who brings passion and enthusiasm to help motivate, guide and mentor young students into their transition to the Industry and reshape their careers for a fulfilling future. The past is something that you cannot undo. The future is something that you can build.
I enjoy coding, developing games and writing tutorials. Visit my GitHub to see the projects I am working on right now.
Educator | Developer | Mentor