A *尋找一個2D Sidescroller

Question

我目前正試圖在我的2D-sidescroller-procedurally generated世界遊戲（想像Terraria般的地形）中使用A *尋路。

我一直在使用這種資源：http://www.redblobgames.com/pathfinding/a-star/introduction.html

並且已經主要利用給出以下僞代碼：

frontier = PriorityQueue() 
frontier.put(start, 0) 
came_from = {} 
cost_so_far = {} 
came_from[start] = None 
cost_so_far[start] = 0 

while not frontier.empty(): 
    current = frontier.get() 

    if current == goal: 
     break 

    for next in graph.neighbors(current): 
     new_cost = cost_so_far[current] + graph.cost(current, next) 
     if next not in cost_so_far or new_cost < cost_so_far[next]: 
     cost_so_far[next] = new_cost 
     priority = new_cost + heuristic(goal, next) 
     frontier.put(next, priority) 
     came_from[next] = current 

我的問題是：在2D-sidescroller的一個大程序上生成的世界，我該如何選擇邊界？通往特定瓦片的路徑可能距離任何距離，並且遍歷整個地圖顯然是不明智的。

我正試圖有效地做到這一點，所以任何援助將不勝感激！

Answer 1

我從來沒有聽說過它被稱爲「前沿」，它一直是「開放列表」，並且你在那裏放置了所有可以前往的鄰居 - 鄰居。

性能方面的事情我已經使用：

1）放入另一個線程的計算：（不協同例程）檢查出這裏的ThreadedJob http://answers.unity3d.com/questions/357033/unity3d-and-c-coroutines-vs-threading.html 這將創建滯後 - 結果將是幾幀在你打電話之後，要麼：a）等待; b）一旦結果準備就緒，開始進入目標的總體方向並改變路線; c）去路徑的第一個節點，即使其餘的還沒有準備好。

2）高速緩存的結果：Dictionary<Vector4, List<Vector2>> pathCache;其中鍵，的Vector4，是startPosX，startPosY，finishPosX，finishPosY，並且值List是A *的結果。 因爲路徑是對稱的，所以當你正在尋找從A到B的路徑時，你還應該檢查B-> A的緩存並且反轉路徑​​。