最近通過這篇博文：https://www.cnblogs.com/0zcl/p/6242790.html 學習了a*演算法。
如果以博文中的貓打比方，若專案中只有一只貓，那還好說，當這只貓走到每一個單元格的時候，該單元格都只有一個f值、一個g值和一個h值。
問題來了，如果有多只貓呢，若你需要為多只貓同時來規劃路徑呢，那一個單元格可能需要有多個f\g\h值，這樣不就亂套了么？
一開始我想到一個比較笨的辦法，在python中可以使用deepcopy，為每一只貓都copy一份單獨的地圖（及其單元格），這樣每份地圖的單元格都有自己單獨的f\g\h值，但是如果地圖很大，那python的deepcopy會占用太長時間。這該如何處理呢？請教一下有沒有更好的解決辦法？
uj5u.com熱心網友回復：
在A*演算法中，每個單位是需要獨立的G值的，這個你必須為每個單位單獨存放一個。但是估值H通常是一個估值函式來產生，也就是一個以當前位置和目標位置為輸入引數的函式，這個不需要存放，是即時算出來的，所以并不需要為每個單位單獨拷貝一份地圖資訊。然而實際當中，估值函式太簡單則效果不好，太復雜則運算太大，地圖越大，這種矛盾越突出。
所以實際上游戲其實都會在地圖中預置若干關鍵路徑點資訊，保存這些關鍵路徑點相互之間的最短路徑距離資訊，這樣在尋路時，只需要搜索起點和終點相對于其最近的關鍵點的最短路徑就可以了，計算量大大降低，而只需要付出很少的資訊存放代價。
uj5u.com熱心網友回復：
謝謝回復，請問有沒有更詳細的說明，或者你之前有沒有寫過更詳細的博客之類的？
uj5u.com熱心網友回復：
我沒有寫過這方面的程式和博客，而且也是很多年前想解決一些相似的問題的時候看過一些相關的演算法。不過這個演算法其實就是一個帶啟發的搜索演算法，沒什么難理解的地方。你可以先實作一個單單位的程式，寫完調通了，你自然就有感覺了。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/90831.html
標籤：數據結構與算法
上一篇：家鄉情懷
下一篇：求助大神啊