Class DijkstraPathFinder

Namespace

LibGameAI.PathFinding

Assembly

PathFinding.dll

A path finder implemented with the Dijkstra algorithm. Always finds the shortest path.

public class DijkstraPathFinder : IPathFinder

Inheritance

object

DijkstraPathFinder

Implements

IPathFinder

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Remarks

Optimizations to be done (some are code-related with others): TODO Use a heap/priority queue (priority heap) data structure for the open and closed nodes. TODO Either make NodeRecord structs (and update surrounding code appropriately) or use an object pool of NodeRecords. TODO Avoid always getting node record from the dictionary, just pull it once onto a local variable and use that.

Constructors

DijkstraPathFinder()

Create a new Dijkstra shortest path finder.

public DijkstraPathFinder()

Properties

ClosedNodes

public IEnumerable<int> ClosedNodes { get; }

Property Value

IEnumerable<int>

OpenNodes

public IEnumerable<int> OpenNodes { get; }

Property Value

IEnumerable<int>

Methods

FindPath(IGraph, int, int)

Find shortest path between start and goal nodes.

public IEnumerable<IConnection> FindPath(IGraph graph, int start, int goal)

Parameters

graph IGraph

Graph where to perform search.

start int

Start node.

goal int

Goal node.

Returns

IEnumerable<IConnection>

An enumerable containing the connections that constitute the shortest path from start to goal.