開發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; }
        }
復制代碼

 


Nowpaper 十五英寸的世界 2013-08-31 22:02:10

[新一篇] 3D游戲之父---John Carmark

[舊一篇] 關于WindowsPhone7的內存問題,90MB
回頂部
寫評論


評論集


暫無評論。

稱謂:

内容:

驗證:


返回列表