复杂的路径路线

Question

     L->| 
    A -> B   ^| 
    |__> C -> D-> G->X--| | 
     K |_> T | |_>Z 
     |___________| 

我希望这个小小的绘图能够帮助传达我想要做的事情。

我有一个7000个位置的列表，每个位置都有一个不确定但少量的门。每扇门都是两个地点之间的桥梁。

参考上面的图表，我将如何去寻找通过门从A到Z的最快路线？

我不需要完整的源代码，只需psuedo代码就可以。

显然你可以采取A→B→C→D→G→X→L→Z， ，但最短路径是A→B→C→K→X - > Z.

Answer 1

将您的位置表示为节点，将门表示为图中的边。然后应用一些相当标准的shortest path algorithm(s)，就完成了。

Answer 2

在维基百科上查找Pathfinding算法。你基本上在它们之间建立了一系列的节点和连接，并且算法通过它们找到从开始到目标的一种方式。

Answer 3

你可以假设每个房间都是一个节点，每个门是一个节点，这个问题将成为寻找在图表，你可以用Dijkstra's algorithm找到例如

Answer 4

最短路径。如果你有一个启发式可对接下来尝试的最佳节点做出合理的猜测，然后可以使用A *算法。我的博客上有一个C＃实现;随意使用代码。给定一个正确的启发式，A *可以比其他路径寻找算法更高效。

http://blogs.msdn.com/ericlippert/archive/tags/AStar/default.aspx