A *啓發式創建Bresenham行

根據我對A *啓發式以及Bresenham算法如何工作的理解，這可能不可行，因爲只有當前狀態和目標狀態被傳遞給啓發式函數。但也許有人對這個問題有一個聰明的解決方案。A *啓發式創建Bresenham行

我正在使用A *來規劃網格上的路徑，我想要一個啓發式方法，噹噹前狀態和目標之間或下一個回合之間存在空閒空間時，會導致最佳路徑跟隨Bresenham的路線圍繞障礙。

下面是一些圖像來說明問題。

曼哈頓距離：

如果世界上的運動作用就像一個格子一個棋子，這將是完全正常的，但我最終將路徑轉換的A *到動作上連續平面，所以這確實工作得很好。

The shortest path from red to green using the Manhattan distance heuristic

歐氏距離：

更好的，但還不夠完善。注意最後的直線。對角線可以很容易地保持對角線，這正是我想要的。

The shortest path from red to green using the Euclidian distance heuristic

我想：

布氏線畫到下一回合或目標。

The best path I actually want, which uses Bresenham lines to get to the goal

我發現這裏的好資源，http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html說什麼我期待的倒是，但似乎只從起點至終點繪製布氏線工作。我想要的是佈雷森漢姆的線路正在吸引下一個障礙。

任何想法都可以解決這個問題嗎？

來源

2011-04-23 peskal

你有沒有最終實現這個東西？ – AShelly 2011-06-16 19:14:19

@我試着根據先前訪問過的單元格中的直線路徑來加權hueritic，但似乎沒有做到我想要的東西。我想你需要徹底改變A *或者完全使用不同的算法來解決這個問題。 – peskal 2011-06-21 00:38:59

您是否嘗試過使用Brasenham線距如何啓發式？ – 2014-07-28 20:12:15

您是否可以隨時修改成本函數，以便隨着累計誤差增加前進成本？

這個想法是，在算法開始時，按照標準Bresenham計算DX和DY。 （假設爲例子的其餘部分是DX> DY> 0相應修改爲其他的方向。）

然後在每一個參觀鄰居節點跟蹤Bresnaham錯誤：

if (neighbor.X > this.X) 
    neighbor.err=this.err+DY 
else if (neighbor.Y > this.Y) 
    neighbor.err=this.err-DX

然後修改成本函數有利於增加X，但請添加if (err >= DX/2) then cost=cost+FACTOR。在所有其他成本相同的地圖中，這應該追溯到正確的路線。

您可能需要的另一件事是當路徑繞過障礙物行走時的特殊處理，否則您可能會在鏈接的文章中看到類似於「具有obatacles的交叉產品」示例的奇怪的貼牆式路徑。只要鄰居節點不在+ X或+ Y方向，就可以通過重新計算DX和DY來處理這種情況。（不幸的是，這可能需要跟蹤一個單獨的DX，DY，和錯誤的每個節點，這可能是太多的開銷）

聲明，我已經很多年沒有實現的一個 * 或Bresneham算法。這整個想法可能是行不通的

來源

2011-04-24 16:14:55 AShelly

這聽起來很有趣。你可以進入更多的細節？ – 2011-04-24 17:35:38

你可以使用Bresenham算法，也許是一個自適應Bresenham，例如與空間填充曲線碰撞檢測？

來源

2011-04-24 16:40:16 Bytemain

您的所有移動方案都是從當前位置（或目標，如果可見）可見的角落，並且一旦找到最短路徑，在所有站點之間繪製Bresenham線。

來源

2011-04-24 17:29:55

正如您鏈接到的文章的「打破關係」部分所述，也許您可以在啓發式中添加一個因子，即此節點位於其父母和目標之間的界限上有多接近。那樣的話，如果可能的話，它寧願停留在一條直線上。

來源

2011-04-24 21:10:30 BrandonAGr

A *啓發式創建Bresenham行

回答

相關問題