unity-path-finding
Shortest path finding with Dijkstra's algorithm for Unity.
Usage (2D grid nodes example)
var nodes = new List<Node>();
var edges = new List<Edge>();
// grid size
int width = 10, height = 10;
// create nodes on grid
for(int y = 0; y < height; y++)
{
for(int x = 0; x < width; x++)
{
var node = new Node(new Vector3(x, 0, y));
nodes.Add(node);
}
}
// connect edges between neighbor nodes on grid
for(int y = 0; y < height; y++)
{
var yoff = y * width;
for(int x = 0; x < width; x++)
{
var idx = yoff + x;
var node = nodes[idx];
// connect horizontally
if(x < width - 1)
{
var to = nodes[idx + 1];
var e = node.Connect(to, Vector3.Distance(node.Position, to.Position));
edges.Add(e);
}
// connect vertically
if(y < height - 1)
{
var to = nodes[idx + width];
var e = node.Connect(to, Vector3.Distance(node.Position, to.Position));
edges.Add(e);
}
}
}
// create graph
var graph = new Graph(nodes, edges);
// build a Path with shortest path finding from source
int source = 0; // source node index
Path route = graph.Find(source);
// traverse a route from source to destination
int destination = 84; // destination node index
// traverse nodes from destination to source
List<Node> nodes;
// Traverse function returns if traversable or not
bool traversable = nodes = route.Traverse(graph, destination, out nodes);
for(int i = 0, n = nodes.Count - 1; i < n; i++)
{
var from = nodes[i];
var to = nodes[i + 1];
// draw line between from and to nodes
Gizmos.DrawLine(from.Position, to.Position);
}
PathRenderer
Sources
- Dijkstra's algorithm - Wikipedia - https://en.wikipedia.org/wiki/Dijkstra's_algorithm
- Priority Queue implementation from Microsoft/MixedRealityToolkit-Unity - https://github.com/Microsoft/MixedRealityToolkit-Unity