Created
December 11, 2017 06:34
-
-
Save fuqunaga/37f52d076c60a852646bd38714e8a4f1 to your computer and use it in GitHub Desktop.
Route search as a Dijkstra whose cost between nodes is always 1
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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