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

簡體傳統

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

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

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

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

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

public List<Point> GetPath(double sx, double sy, double ex, double ey) { double vx = ex - sx; double vy = ey - sy; double mm = Math.Sqrt(vx * vx + vy * vy); vx = (vx / mm) * CGRoot.MapGridSize; vy = (vy / mm) * CGRoot.MapGridSize; List<Point> bufft = new List<Point>(); while (true) { if (Math.Sqrt((ex - sx) * (ex - sx) + (ey - sy) * (ey - sy)) < CGRoot.MapGridSize) { return bufft; } int x = (int)(sx / CGRoot.MapGridSize + vx); int y = (int)(sy / CGRoot.MapGridSize + vy); if (x >= m_MapData_Rank_Width) x = m_MapData_Rank_Width - 1; else if (x < 0) x = 0; if (y >= m_MapData_Rank_Height) y = m_MapData_Rank_Height - 1; else if (y < 0) y = 0; if (m_MapObstruct[y, x] == 0) { sx += vx; sy += vy; bufft.Add(new Point(sx, sy)); } else { break; } } //到此為止找到了一條通向目標點的直線，如果是直線，那么下面的不會進行

//如果不是，則會在停止的障礙點上開始尋路，直到目標 List<Point> buff = base.GetPath((int)sx / CGRoot.MapGridSize, (int)sy / CGRoot.MapGridSize, (int)ex / CGRoot.MapGridSize, (int)ey / CGRoot.MapGridSize); for (int i = 0; i < buff.Count; i++) { bufft.Add(new Point(buff[i].X * CGRoot.MapGridSize, buff[i].Y * CGRoot.MapGridSize)); } return bufft; }

關于限定范圍中的部分寫在尋路算法當中，由于代碼過長，只能節選一部分

//在限定范圍內進行處理，所以我們在處理之前就看是否是超出了范圍。
        off_x += father.x;
            off_y += father.y;
            if ((off_x < 0) || (off_x >= this.mapW) || (off_x < _rangeMinX) || (off_x >= _rangeMaxX))
            {
                return false;
            }
            if ((off_y < 0) || (off_y >= this.mapH) || (off_y < _rangeMinY) || (off_y >= _rangeMaxY))
            {
                return false;
            }
            if (this.map[off_x, off_y].block)
            {
                return false;
            }
//下面的代碼屬于另外一個部分，類的成員，作為判定的限定參數
     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; }
        }