複雜的路徑路線

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