專業尋路方法？

Question

我在（很少）空閒時間工作在roguelike上。每個級別基本上都是通過路徑連接在一起的幾個矩形房間。然而，我希望房間之間的路徑自然，風大。例如，我不會考慮以下自然的：

 B  
     X  
     X  
     X  
     XX  
    XX   
    XX   
    AXX   

我真的希望更多的東西是這樣的：

 B  
     X  
     XXXX  
      X  
      X  
      X  
      X  
    AXXXXXXXX  

這些路徑必須滿足幾個特性：

1. 我必須能夠指定它們所在的區域，
2. 我必須能夠參數化它們多麼有風和長，
3. 線條不應該看起來像他們開始在一個路徑，並在另一個路徑結束。例如，上面的第一個例子看起來好像從A開始到B結束，因爲它基本上反覆地改變了方向，直到它與B對齊，然後直接在那裏直行。

我一直希望能使用A *，但老實說我不知道​​我的啓發是什麼。我也考慮過使用遺傳算法，但我不知道這種方法最終會有多實用。

我的問題是，什麼是獲得我想要的結果的好方法？請不要指定像「A *」或「Dijkstra算法」這樣的方法，因爲我也需要一個很好的啓發式幫助。

Answer 1

在你能弄清楚如何生成路徑之前，你必須找出一種更準確的方式來陳述你想要的東西。一種方法是爲每條路徑分配一個分數，然後搜索高分數路徑。以下是一些需要考慮的問題：

1. 您是否喜歡長直線短跑？你將如何量化這種偏好？ （要使搜索算法收斂，如果您的評分函數是非線性的，將會更容易。）

2. 如果您不想直接前往目的地，可能需要獎勵離主線不遠的步驟。例如，在從A到B的路徑上，考慮每個點，然後分三步計算點之間的方向。現在取這個方向的差值的餘弦和方向從A到B的直線。取消它。線上的步數爲-1，對於你來說，垂直的步數是中性的，並且離行數爲+1。

這裏有一些很好的下一個步驟：

• 的幾個進球的想法思考。
• 手工繪製十幾條路徑，並按您喜歡它們的順序排列它們。
• 對於每個路徑，手動創建幾個小變化。
• 在所有路徑上運行您的評分函數。不停地擺弄，直到你得到一個像那樣的得分函數。

然後您將準備好思考搜索算法。

Answer 2

我想說路徑尋找在這裏是一個錯誤的術語：通常涉及找到從A到B的有效路線，而您的問題不是尋找那條路線，而是創建適合您目的的路線。你故意製造次優道路，其質量難以量化。所以我不認爲具有任何啓發式的搜索算法會是解決這個問題的最佳解決方案。當你有一個強制性標準（工作路徑）和一些模糊的，未定義的標準（自然看起來和纏繞）時，最好先滿足強制性要求並嘗試將其改變爲其他要求。這樣，你總是有一些工作。

我建議，由於您似乎更喜歡水平和垂直路徑以直角轉彎，所以首先使用從A到B的直線2段路徑（帶曼哈頓距離啓發式的A *可以爲您找到它，但它自己一樣容易出手）。然後沿着兩個分段中的一個分段和該分段的兩個端點中的一個端點取一個隨機點，並將該線段的該分段與自身平行移動一定的隨機距離。然後添加2個額外的線段以將該線的新位置連接到舊連接點。你的第二個例子展示了這個算法的一個迭代：如果A是（0,0）並且B是（5,7），那麼你已經隨機選擇了第二條線段（垂直線段），在（0,5 ）和（5,5）的中點，然後將該部分向右推進3個單位，然後再加入。

Answer 3

這裏有一個想法---

，開始以，並在隨機的方向移動 - 向左，向上或向下。每次移動後，滾動一個隨機數，看看你是否轉過身。讓我們說75％的時間你繼續沿同一方向行駛，25％的時間你會轉向。當你轉向時，總是轉向一個更接近於B的方向。這意味着如果你向左或向右移動，就必須轉身向上，如果你向上移動，做出右/左選擇根據您目前距離目標的左側或右側多遠。另外，如果你擊中了世界邊界之一，轉！

這應該不是太難以編碼。我有一種感覺，你只是想讓它變得比它需要更復雜......