開發ing經驗關于遊戲中尋路

任何的遊戲幾乎都需要尋路吸，最常用的則是A星尋路，這個算法在網絡上可以找到很多的版本，然而，今天則是一起探讨尋路算法的問題。

在我們目前的正在開發的項目中，使用的就是A*算法，在正常的尋路中表現非常好，速度很快，但是實際過程中，使用者則有可能點選一個不可能到達的點，那麼這個時候有趣的問題就發生了，整個邏輯則會“頓”一下，當然了，這取決于運算方法和主要邏輯是不是在一起，這得另說。隻說“頓”的情況，它的發生是因為這個點不可能到達，則我們強大的A*尋路把所有的點全部找個遍，實際情況則是這樣的：在4000x3000的地圖上，尋路循環進行了30萬次，才隻是找到一個近似路徑而已，我們将這個部分做了修改，将尋路縮小到指定範圍，如果超過這個範圍則不在進行尋路，圖例表示如下：

<a target="_blank" href="http://blog.51cto.com/attachment/201111/162118718.jpg"></a>

隻對設定的範圍内進行搜尋，這也是比限定搜尋長度要容易的方式，我嘗試使用限定搜尋的總長度，但是不怎麼好，對于A*的算法代碼改動太大，而使用設定範圍，隻需要在超出範圍時候控制好即可。

關于直接尋路，我們會得到一個很不自然的路徑，那麼為什麼不先進行直線行走，走到特定位置然後再按按照尋路點走呢，我們的項目中是這樣的解決的，先使用向量計算，然後判定按照步長上的每個點是否在不可達點上，當出現這種情況，則調用尋路，雖然不能達到100%的平滑尋路，但是對于普通的行走已經足夠應付，會走一個相對很爽的路徑。

可能上述寫的很雜亂，表述的問題其實很簡單，有的時候我們研究和優化很多的代碼，都是存在于實驗室——一個完美的環境，而在真實環境将面臨着使用者亂點一通，或者提出為什麼不是很平滑的移動的問題，這些問題有可能讓我們需要将路重走一遍，而本篇則是我們項目當中的一篇更新郵件子内容。

//在限定範圍内進行處理，是以我們在處理之前就看是否是超出了範圍。

off_x += father.x;

off_y += father.y;

if ((off_x &lt; 0) || (off_x &gt;= this.mapW) || (off_x &lt; _rangeMinX) || (off_x &gt;= _rangeMaxX))

{

return false;

}

if ((off_y &lt; 0) || (off_y &gt;= this.mapH) || (off_y &lt; _rangeMinY) || (off_y &gt;= _rangeMaxY))

if (this.map[off_x, off_y].block)

//下面的代碼屬于另外一個部分，類的成員，作為判定的限定參數

private static int maxFinderW = 50;

private static int maxFinderH = 40;

private int _rangeMinX = 0;

private int _rangeMinY = 0;

private int _rangeMaxX = 1;

private int _rangeMaxY = 1;

private int _sx

set { _rangeMinX = value - maxFinderW; _rangeMaxX = value + maxFinderW; }

private int _sy

set { _rangeMinY = value - maxFinderH; _rangeMaxY = value + maxFinderH; }

本文轉自nowpaper 51CTO部落格，原文連結:http://blog.51cto.com/nowpaper/712586