Skip to content

Instantly share code, notes, and snippets.

@fuqunaga
Created December 11, 2017 06:34
Show Gist options
  • Save fuqunaga/37f52d076c60a852646bd38714e8a4f1 to your computer and use it in GitHub Desktop.
Save fuqunaga/37f52d076c60a852646bd38714e8a4f1 to your computer and use it in GitHub Desktop.
Route search as a Dijkstra whose cost between nodes is always 1
public struct DijkstraData
{
public float cost;
public Node parent;
}
// Route search as a Dijkstra whose cost between nodes is always 1
protected List<Node> CalcRoute(Node from, Node to)
{
List<Node> ret = null;
Dictionary<Node, DijkstraData> finished = new Dictionary<Node, DijkstraData>();
Dictionary<Node, DijkstraData> temporaries = new Dictionary<Node, DijkstraData>();
temporaries[from] = new DijkstraData()
{
cost = 0f,
parent = null
};
while (temporaries.Any())
{
var minCost = temporaries.Values.Select(d => d.cost).Min();
var currentPair = temporaries.First(pair => pair.Value.cost == minCost);
finished.Add(currentPair.Key, currentPair.Value);
temporaries.Remove(currentPair.Key);
var current = currentPair.Key;
var nextCost = currentPair.Value.cost + 1;
var nexts = current.connectedNode.Except(finished.Keys).ToList();
if (nexts.Any())
{
// find route!
if (nexts.Contains(to))
{
ret = new List<Node>();
ret.Add(to);
var parent = current;
while(parent != null)
{
ret.Add(parent);
parent = finished[parent].parent;
}
ret.Reverse();
break;
}
nexts.ForEach(n =>
{
DijkstraData data;
var keep = temporaries.TryGetValue(n, out data) && (data.cost <= nextCost);
if (!keep) {
temporaries[n] = new DijkstraData()
{
cost = nextCost,
parent = current
};
}
});
}
}
return ret;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment