對於單個單位的尋路可以使用A*算法。但是在實際應用中往往出現多個單位同時移動的場面，而且它們會互相影響，阻礙對方的移動。所以一旦沖突，之前為每個單位計算出的路徑就會失效。
一種流行的解決方法是發現沖突的時候重新計算路徑。還有定期重新計算的等等。這些都是動態調整的方案，最後形成的路徑並非是最優的。雖然這些次優解可以滿足大部分場景的需要，但是有沒有辦法計算出最優解呢？畢竟很多動態調整的算法會有失敗的可能。
我們可以把一個最小時間單位（回合）中每個單位的可能移動的組合列出來作為節點，放入搜索樹中，然後再用A*算法進行搜索。但是在方格地圖中一個單位可以有最多5或者9（帶斜線）種不同的移動方法，其中包括靜止不動。2個單位就有5x5或9x9種組合。隨著要考慮的單位數的增加，組合數會爆炸。這時我們可以把一個回合再分解到一系列單個單位的移動，把單個移動作為節點。這樣一旦發現某些條件不滿足，比如兩個單位有沖突，就可以關閉當前節點，不繼續生成組合，從而實現對搜索樹進行剪枝。由於一個回合中各單位的移動實際並沒有優先次序，而我們現在的處理是一個單位一個單位進行，所以先被處理的單位不需要檢查和後面單位的沖突，只有後面的單位需要檢查和前面單位的沖突。當然為了成功剪枝，優先處理哪些單位也是值得考慮的。可以按某種優先級排序，比如越接近目標的可以優先處理。
舉個例子，假定一個2x2的地圖，有兩個單位A在坐標1，0處，B在坐標0，1處，都想要移動到坐標1，1處。那麼我們按先處理A後處理B的次序生成節點。假定[]表示計劃的移動列表，{}表示未計劃的單位列表。那麼搜索樹可以表示如下：
[]{A10,B01} //初始狀態
/ \ \
[A向下]{B01} [A不動]{B01}未展開 [A向左]{B01}未展開
/ | \
[A向下B向右]{}沖突，剪枝 [A向下B不動]{} [A向下B向上]{} 未展開
|
[]{A11,B01} -> []{B01} 回合1結束，結算位置，A到達目的地，被移走，然後進行下一輪。
/ \ \
[B向右]{} [B不動]{}未展開 [B向上]{}未展開
|
[]{} 回合2結束，結算位置，B到達目的地，被移走。列表為空，達成目標狀態。
另一個優化是，雖然我們可以生成一個單位的所有移動方法，但是我們並不急於把所有的移動都作為節點放入open list中，而只選1~2個最有可能成功的。當前節點並不關閉，並且維護一個列表，記錄有哪些移動已經展開過了。這樣可以有效減少open list中節點的數量。假定<>為未展開的移動，上面的例子可以用如下表示：
[]{A10,B01} //初始狀態 -> []<A不動, A向左>{}
/
[A向下]{B01} -> [A向下]<B向上>{}
/ |
[A向下B向右]{}沖突，剪枝 [A向下B不動]{}
|
[]{A11,B01} -> []{B01} -> []<B不動,B向上> 回合1結束，結算位置，A到達目的地，被移走，然後進行下一輪。
|
[B向右]{}
|
[]{} 回合2結束，結算位置，B到達目的地，被移走。列表為空，達成目標狀態。
關於A*搜索的啟發函數，我們當然可以求出每個單位的manhattan距離、diagonal距離或者duclidean距離，然後求和作為每個節點的啟發值。更好的啟發值可以用RRA*(Reverse Resumable A*)算法來獲得。也就對目標點到當前點執行一次普通A*搜索，來獲得（不計移動單位的障礙）的實際距離。這個距離比前面提到的估算算法要准確得多。RRA*搜索生成的open list是可以重用的，實際上開銷並不大。當然對多個目標點，我們需要維護各自的open list。
具體實現可以參考github.com/silmerusse/fudge_pathfinding中的例子。對於相對簡單的地圖和較少的單位，最優解是可以很快求出的。但是對復雜度高的地圖和較多單位，則需要花費較多時間和內存空間。
