8方向尋路算法

我在尋找正在尋找的正確尋路算法時遇到了麻煩。8方向尋路算法

我有間距的球員，自由行動（不堅持一個網格），但它們僅限於在8個方向（N NEË等）移動

我正在使用A *，和這個圖表。但是我意識到，圖上的每個節點都相距很遠，並且所有邊都具有相同的權重 - 因爲節距是矩形的。節點的數量是巨大的（是一個很大的瀝青，他們能夠在1個像素和另一個之間移動）

我覺得必須有另一種算法，爲這種事情進行了優化？

來源

2010-04-06 Richard Taylor

我會將節距分解爲10x10像素網格。您的路由不必像系統的其他部分一樣精細，並且使算法佔用的內存少得多。

正如克里斯在上面所說的那樣，選擇正確的啓發式是讓算法適合您的關鍵。

來源

2010-04-06 22:47:13

這似乎是一個好主意，使用A *網格來移動，當它們接近目標時可能使用更小的網格。無論如何他們會每隔一秒左右重新評估一次路徑 - 目標可能每次都會改變，所以不需要太詳細。找到路徑並不是唯一的問題，我不希望玩家在明顯看起來像網格的地方亂跑，這是不現實的，它是這樣做的 - 但堅持8個方向，這就證明了問題 – 2010-04-07 20:34:22

您可以根據另一種啓發式方法來衡量方向。因此，與根據實際距離加權路徑相反，您可以根據另一個因素（例如「接近其他玩家」）來加權或縮放，這意味着玩家將偏愛不會與其他玩家相撞的路線。

A *算法應該像這樣工作。

來源

2010-04-06 22:41:22 Chris

謝謝，這是一個好主意，但正如我剛纔所說：找到路徑並不是唯一的問題，但我不希望玩家在顯然看起來像網格的地方亂跑，這是不現實的，它是這樣做的 - 但堅持8個方向，這就證明了問題 – 2010-04-07 20:34:45

如果玩家在網格上的點之間以直線移動，則實際上不需要使用A *。 Bresenham's line algorithm將很快提供一條直線路徑。

來源

2010-04-07 13:47:24 andand

謝謝，但他們固定在8個方向，如果他們遵循這一點，它有點太完美了（例如，將在每幀的北/東之間切換） – 2010-04-07 20:30:04

我認爲你應該嘗試跳轉點搜索。這是一個非常快速的8-dire尋路算法。

這裏是blog短暫描述跳轉點搜索。

而且，這是它的學術文章< Online Graph Pruning for Pathfinding on Grid Maps>

此外，YouTube上有一些有趣的視頻。

我希望這會有所幫助。

來源

2012-06-16 08:54:23 Eric

8方向尋路算法

回答

相關問題