mass astar尋路

我正在嘗試在Javascript中創建一個塔防遊戲。mass astar尋路

這一切都從尋路順利開..

我使用本網站的愛仕達代碼：http://www.briangrinstead.com/blog/astar-search-algorithm-in-javascript它使用二進制堆（我認爲這是相當最佳）

這個問題我我的意思是我想讓人們阻止「攻擊者」的路徑。這意味着每個「攻擊者」都需要能夠自己找到通往出口的路（因爲有人可能會切斷一個「攻擊者」，並且需要找到自己的出口路徑）。現在5/6攻擊者可以在任何時候查找任何問題。但是說路徑被10個以上的攻擊者阻擋，所有10個攻擊者需要同時射擊它的尋路腳本，這會使FPS下降到每秒1/2左右。

對任何在任何時候都有很多實體尋路的人來說，這肯定是一個常見問題，所以我想必須有比我的方法更好的方法。

所以我的問題是：什麼是以最有效的方式實現質量尋路算法到多個「機器人」的最佳方式。

感謝，

詹姆斯

來源

2012-04-12 james

它看起來像'findGraphNode'在該代碼需要線性時間，而應該採取一定的時間（利用哈希表），因此實施遠非最佳。 – 2012-04-12 10:08:52

我會看看如果我能加快一點點。但我認爲，即使採用更高效的路徑發現方式，如果我嘗試查找漫遊器，我仍會以較慢的幀率結束。我開始認爲我最好的選擇是實際每幀尋路一次，然後設置一個方向在每個可通過的塊上讓機器人遵循。 – james 2012-04-12 10:20:14

@james如果這是類似大多數塔防的東西，大概有一個屏幕價值的地圖和沒有複雜的collisons（即機器人不會彼此碰撞或其他移動的物體，或你分開處理）然後是的我會認爲整個地圖的計算路徑是最好的。事實上，你甚至可能不必每幀重新計算整個地圖。如果您在構建算法時非常小心，則應該能夠確定哪些節點受到用戶更改的影響，並僅從這些節點重新計算「上游」。聽起來不錯！ – Tim 2012-04-12 17:11:14

使用防對象，這是獲得廉價的尋路的唯一途徑，據我所知： http://www.cs.colorado.edu/~ralex/papers/PDF/OOPSLA06antiobjects.pdf

防對象主要是指代替機器人具有個人ai，你將會擁有一個與你的遊戲地圖綁定的「ai」。

P.S：這是一般在尋路另一個鏈接（可能提供最好的在線參考）： http://theory.stanford.edu/~amitp/GameProgramming/index.html

來源

2012-04-12 10:01:55 c69

感謝您的資源，我稍後再看看。儘管從你所說的話來看，它似乎更有意義地尋找整個地圖，並可能爲機器人所遵循的每個「塊」設置一個方向。嗯， – james 2012-04-12 10:23:44

只是緩存結果。

將路徑存儲爲哈希表（對象）中的值，爲每個節點指定UUID，將UUID連接起來以形成唯一的哈希表鍵，並將路徑插入到該表中。

當您檢索路徑背出哈希表，走的路徑，而且，看它是否仍然有效，如果沒有，重新計算並插入新的回。

有很多的優化，你可以做:)

像C69說羣AI或蜂房頭腦浮現在腦海中：P

來源

2013-10-28 03:54:31 Metalstorm

mass astar尋路

回答

相關問題