簡介尋路算法是游戲開發中的核心基礎尤其在策略類游戲中如何在復雜地圖上實現高效、穩定的路徑規劃直接關系到玩家的操作體驗。在經典方案中A*算法憑借其通用性和穩定性成為最常用的兜底選擇但在大規模開闊地圖上容易因節點膨脹導致性能下降JPS跳點搜索通過剪枝對稱路徑大幅縮減搜索空間成為開闊地形的加速利器而Wall-tracing則模仿沿墻探索的本能能巧妙應對貼墻和狹窄走廊等特殊場景。這些算法各有優劣實際工程中需要根據地圖特征動態選型。本文圍繞這三類算法結合C實現講述了從網格數據結構、堆優化、跳點檢測到路徑平滑與群體避讓的完整技術方案并提供了性能實測數據和踩坑記錄。無論是游戲開發者還是尋路算法愛好者都能從中獲得可落地的工程經驗讓尋路系統在真實項目中兼顧速度與穩健。1. 為什么要寫一個三合一尋路組件做過RTS或者類RTS游戲的人應該都有體會尋路不是“能走到”就行而是要經得起成百上千個單位同時尋路的考驗。我之前用C寫的這個RTS尋路組件其實是被逼出來的——一開始只用了A*地圖一大、單位一多幀率直接崩到沒法看后來在開闊地形上換成了JPS又快了不少最后加上Wall-tracing處理貼墻、繞障礙這類畸形路徑時省了很多麻煩。這篇文章就來聊聊我這套用C實現的RTS尋路三件套A*、JPS、Wall-tracing。我會從問題拆解、算法選型、核心代碼實現、性能實測到踩坑記錄把整個設計和實操過程都攤開來講適合正在做策略游戲、仿真項目或者對尋路算法感興趣的人參考。先說結論沒有一種算法是萬能的。A*是兜底的通用方案JPS負責開闊地圖上的性能加速Wall-tracing用來處理“沿墻走”這類邊界場景。三者組合起來才能在真實RTS場景里做到既穩又快。2. RTS路徑查找的問題拆解與方案選型2.1 RTS尋路和普通尋路差在哪如果你只做過迷宮求解那種小規模尋路可能覺得A*已經夠用了。但RTS場景完全是另一個量級。典型的RTS對局里可能有幾百個單位同時下達移動指令每個單位每幀都需要獲取路徑信息這意味著尋路系統必須支持高頻調用。RTS尋路和普通尋路的差異主要體現在幾個方面第一是規模。地圖往往達到512x512甚至2048x2048個格子數據量大了算法的空間復雜度和時間復雜度都會被放大。第二是動態性。戰爭迷霧、建筑建造、單位阻擋都會改變地圖的通行狀態尋路結果不能永遠緩存。第三是群體性。很多單位擠在一起走如果每個單位都各走各的路徑上會出現大量重疊和沖突視覺上就很假A*算法本身并不處理單位之間的避讓問題。第四是實時性。RTS追求的是即時反饋玩家點一下鼠標單位必須迅速響應尋路耗時一旦超過幾毫秒就會影響體驗。所以就引出了配置多個算法的必要性我不能靠單一算法對付所有場景必須根據地圖特點在運行時選擇最合適的策略。2.2 為什么是A*、JPS、Wall-tracing三件套A是經典中的經典。它的優點在于通用、穩定只要有合適的啟發函數任何地圖上都能找到可行路徑。缺點是慢尤其在開闊地圖上A會擴展大量節點因為從起點到終點附近幾乎每個格子都會被塞進開放列表。但作為兜底方案它不能丟。JPSJump Point Search是在A基礎上做節點剪枝的算法。它利用了網格地圖中路徑的對稱性——在開闊地帶很多節點走向終點的代價完全相同JPS會沿著一個方向“跳”過去只在轉彎點或者被迫轉彎的“強制鄰居”處才停下來評估。這樣開闊地圖上JPS只需擴展A的幾十分之一的節點。代價是它要求地圖是規則的網格而且障礙物不能太密集否則跳點太多優勢就沒了。Wall-tracing則是另一種思路。它不追求全局最優路徑而是模仿人類“摸著墻走”的本能。在某些地圖上目標點被復雜墻體包圍A*和JPS會繞很大一圈而Wall-tracing可以沿著墻體快速貼近目標。雖然它不走最優路徑但速度快、路徑看起來自然特別是在迷宮里探路時效果很好。三者的關系不是替代而是補位JPS能加速大部分開闊地形的尋路A*兜底任何情況Wall-tracing處理貼墻和狹窄通道。這樣組合之后等于把每種算法的強項都發揮出來。3. 核心數據結構與算法實現細節3.1 地圖網格的C表示任何尋路算法都離不開地圖數據。我用了一個比較簡潔的Grid類來管理網格核心成員包括寬度、高度、障礙標記數組。class Grid { public: Grid(int width, int height) : width_(width), height_(height), walkable_(width * height, true) {} bool isWalkable(int x, int y) const { if (x 0 || x width_ || y 0 || y height_) return false; return walkable_[y * width_ x]; } void setWalkable(int x, int y, bool walkable) { walkable_[y * width_ x] walkable; } int width() const { return width_; } int height() const { return height_; } private: int width_; int height_; std::vectorbool walkable_; };這里有個細節std::vectorbool是有爭議的選擇因為它做了位壓縮性能并不一定比std::vectorchar快。但在我的測試里對于500x500的地圖vector 的內存占用只有約30KB而vector 要250KB。緩存友好度上vector 反而更優讀取速度也足夠快。不過如果你想做更強的擴展比如存地形消耗值建議直接用vectorchar或者vectoruint8_t。網格的障礙狀態不只是靜態的。RTS游戲里建筑會動態建造所以Grid要支持運行期改障礙。這一點在后面動態避障部分會細講。3.2 二叉堆優化的A*基礎和坑A*核心是維護兩個列表開放列表OpenSet和關閉列表ClosedSet。每次從OpenSet里取F值最小的節點擴展直到找到終點或者OpenSet清空。F值由G值起點到當前節點的實際代價和H值當前節點到終點的估計代價相加得到。C實現時OpenSet最忌諱用std::vector加線性掃描找最小值那會直接讓算法復雜度退化成O(n^2)。我用了std::priority_queue配合自定義比較器這是最簡單也最可靠的方案如果想壓榨性能可以手寫二叉堆或者用斐波那契堆但實測下來二叉堆已經足夠。struct Node { int x, y; int g, h; int parentIndex; }; struct NodeCompare { bool operator()(const Node* a, const Node* b) const { return (a-g a-h) (b-g b-h); } }; using OpenSet std::priority_queueNode*, std::vectorNode*, NodeCompare;有個細節priority_queue的top()返回的是指針但指針指向的節點可能會被重復加入。解決這個問題我會用一個std::unordered_mapint, Node*來記錄每個坐標是否已經在關閉列表里如果已經關閉就跳過。啟發函數的選擇也很關鍵。對于四方向網格用曼哈頓距離對于八方向網格用切比雪夫距離或歐幾里得距離。RTS里單位通常允許八方向移動所以我的H值默認用切比雪夫距離int heuristic(int x1, int y1, int x2, int y2) { return std::max(std::abs(x1 - x2), std::abs(y1 - y2)); }注意H值不能高估實際代價否則A*退化成貪心搜索可能找到次優路徑如果H值太低擴展節點又會太多。切比雪夫距離估算八方向移動正好不低估也不高估是這個場景下的標準選擇。3.3 JPS的核心跳點搜索JPS的關鍵不是搜索每一個鄰居而是找到“跳點”。跳點分兩類一類是強迫鄰居所在的節點另一類是具有強制鄰居的節點。理解了這兩個概念JPS就理解了大半。強迫鄰居Forced Neighbor當節點X的某個相鄰方向被障礙擋住但同時另一側的方向可以通過并且這個方向的移動會導致路徑需要轉向時這個被強制訪問的鄰居就是強迫鄰居。比如你在一條狹窄走廊里走左邊是墻前方是墻但右前方有一個缺口你必須右轉才能繼續前進那個缺口方向就是你被強迫拐彎的方向。跳點的規則可以總結為直線跳躍沿著水平或垂直方向一直前進直到遇到障礙、地圖邊界或找到具有強迫鄰居的節點。對角線跳躍先檢查兩個正方向水平和垂直是否能走如果能走就先做直線跳躍再沿對角線推進。如果對角線方向不能走則停止。下面是我實現的直線跳躍偽代碼bool jumpStraight(int x, int y, int dx, int dy, const Grid grid, int targetX, int targetY, int jumpX, int jumpY) { int nx x dx; int ny y dy; while (grid.isWalkable(nx, ny)) { if (nx targetX ny targetY) { jumpX nx; jumpY ny; return true; } // 檢查是否有強迫鄰居 if (dx ! 0 dy 0) { // 水平移動檢查垂直方向是否有強迫鄰居 if ((grid.isWalkable(nx, ny 1) !grid.isWalkable(nx - dx, ny 1)) || (grid.isWalkable(nx, ny - 1) !grid.isWalkable(nx - dx, ny - 1))) { jumpX nx; jumpY ny; return true; } } else if (dx 0 dy ! 0) { // 垂直移動檢查水平方向是否有強迫鄰居 if ((grid.isWalkable(nx 1, ny) !grid.isWalkable(nx 1, ny - dy)) || (grid.isWalkable(nx - 1, ny) !grid.isWalkable(nx - 1, ny - dy))) { jumpX nx; jumpY ny; return true; } } nx dx; ny dy; } return false; }這段代碼的關鍵在于只有當某個方向上有“強制轉彎”的鄰居時當前節點才算跳點否則就一路跳到底。實際運行中JPS在開闊地圖上擴展的節點數會非常少因為可以跨越大片區域不做節點評估。3.4 Wall-tracing的實現思路Wall-tracing嚴格來說不是傳統的A變體而是另一種路徑追蹤算法。它的核心規則是“右手法則”一直沿著墻走遇到岔路優先向右直到到達目標點。這個算法天然適合迷宮也適合處理A容易繞遠路的貼墻場景。我的實現策略是這樣的先嘗試用JPS計算路徑如果路徑的開頭部分貼著墻或者目標點在墻的包圍圈內那么用Wall-tracing生成一段貼墻路徑再和JPS的路徑拼接。Wall-tracing的狀態機比較容易理解enum class WallSide { LEFT, RIGHT }; bool wallTrace(const Grid grid, int startX, int startY, int targetX, int targetY, WallSide side, std::vectorPathNode path) { int currentX startX; int currentY startY; int dirX 0, dirY 1; // 初始方向向上 // 根據側邊選擇轉向 auto turnLeft []() { int tmp dirX; dirX -dirY; dirY tmp; }; auto turnRight []() { int tmp dirX; dirX dirY; dirY -tmp; }; // 判斷前方是否可走 auto canMoveForward []() { return grid.isWalkable(currentX dirX, currentY dirY); }; // 判斷側邊是否靠墻 auto sideWallBlocked []() { if (side WallSide::RIGHT) { // 右手邊需要是墻 return !grid.isWalkable(currentX - dirY, currentY dirX); } return !grid.isWalkable(currentX dirY, currentY - dirX); }; int stepCount 0; int maxSteps grid.width() * grid.height() * 4; // 防止死循環 while ((currentX ! targetX || currentY ! targetY) stepCount maxSteps) { path.push_back({currentX, currentY}); // 規則1先嘗試右轉左手法則/左轉右手法則 if (side WallSide::RIGHT) { turnRight(); if (canMoveForward()) { currentX dirX; currentY dirY; stepCount; continue; } turnLeft(); // 恢復舊方向 } // 規則2如果側邊不是墻需要轉向靠近墻 if (!sideWallBlocked()) { if (side WallSide::RIGHT) turnLeft(); else turnRight(); } // 規則3盡量向前 if (canMoveForward()) { currentX dirX; currentY dirY; } else { // 規則4前方被擋轉向 if (side WallSide::RIGHT) turnLeft(); else turnRight(); } stepCount; } path.push_back({currentX, currentY}); return (currentX targetX currentY targetY); }這個實現最需要注意的是死循環問題。如果地圖里有閉環的圍墻Wall-tracing會一直轉圈。所以必須加一個maxSteps限制超時就放棄回退到A*方案。另外Wall-tracing只能找到一條可行路徑不保證最短。所以它在我這個系統里只作為一個“走廊探路器”真正的路徑優化還是交給后續的路徑平滑模塊來做。4. 從單單位尋路到群體尋路的工程實踐4.1 尋路框架的整體架構整個尋路組件的核心入口是一個PathFinder類它對外提供統一的FindPath接口。調用方不需要關心底層用哪個算法PathFinder會根據地圖和路徑特點自動選擇。class PathFinder { public: PathFinder(Grid* grid); // 統一入口 std::vectorPathNode FindPath(int startX, int startY, int targetX, int targetY); private: Grid* grid_; bool useJPS_; bool useWallTrace_; std::vectorPathNode findPathAStar(int startX, int startY, int targetX, int targetY); std::vectorPathNode findPathJPS(int startX, int startY, int targetX, int targetY); std::vectorPathNode findPathWallTrace(int startX, int startY, int targetX, int targetY); void smoothPath(std::vectorPathNode path); };在FindPath內部我會做幾步判斷第一步如果起點或終點不可通行直接返回空路徑。第二步用A跑一個簡化版本限制最大搜索步數作為兜底。如果搜索節點數很少比如小于100個說明地圖很簡單直接返回A結果。第三步如果地圖比較大且路徑跨越大片開闊地用JPS。判斷依據是起點和終點的曼哈頓距離大于某個閾值我設的是32且地圖開闊度較高連續可通行格占比大。第四步如果目標點被墻壁包圍或者路徑需要穿過狹窄通道拼接Wall-tracing的初始段作為“引導路徑”。這個自動選擇邏輯一開始我做成硬編碼規則后來發現不同地圖的閾值不好調最后改成基于運行時的快速采樣先往8個方向各做30格直線檢測計算可通行比例再決定用哪個算法。4.2 多單位尋路時的避讓與流量控制單單位尋路跑通之后真正讓RTS動起來的是群體尋路。群體尋路最大的問題不是路徑計算而是單位之間的互相阻擋。A*算出來的路徑上可能有幾十個單位擠在同一條大道上。我用的方案是“路徑 局部避讓”的兩層架構。第一層PathFinder負責計算全局路徑。第二層每個單位在沿路徑移動時執行RVO互惠速度障礙局部避讓算法。RVO的含義是單位在計算自己下一步速度時假設對方也會采取同樣的避讓策略這樣避免來回抖動。RVO的C實現核心是計算碰撞速度區間Vector2 computeRVO(const Vector2 pos, const Vector2 vel, const std::vectorUnit* neighbors, float maxSpeed) { Vector2 newVel vel; for (Unit* neighbor : neighbors) { Vector2 relPos neighbor-pos - pos; Vector2 relVel neighbor-vel - vel; float dist relPos.length(); float combinedRadius unitRadius_ neighbor-unitRadius_; if (dist combinedRadius 0.01f) { // 太近緊急分開 Vector2 pushDir relPos.normalized(); newVel - pushDir * (combinedRadius - dist) * 5.0f; continue; } // 計算碰撞時間 float relativeSpeed absDot(relVel, relPos.normalized()); if (relativeSpeed 0.0f) { float timeToCollision (dist - combinedRadius) / relativeSpeed; if (timeToCollision 2.0f) { // 這個方向有碰撞風險忽略鄰居的速度影響 newVel relPos.normalized() * maxSpeed; } } } return clampToMaxSpeed(newVel, maxSpeed); }這里有個經驗RVO的鄰域半徑不要設太大一般取3到4個單位半徑就夠了。鄰域太大單位會探測到十萬八千里之外的碰撞風險導致集群整體移動異常緩慢太小又起不到避讓效果。4.3 路徑平滑與簡化A*和JPS輸出的是網格節點路徑直接給單位走會顯得很機械。單位每一步都朝網格中心點走視覺上像在走“之”字形。所以必須做路徑平滑。我使用了拉繩子算法也叫漏斗算法Funnel Algorithm。它的思想是把路徑的起點和終點連成一條繩子如果繩子被障礙物擋住就沿著墻邊滑動繩子直到找到最短的、不被障礙物遮擋的路徑。代碼上不復雜但要注意浮點數精度問題。我的實現里先用網格坐標做線性插值然后做射線檢測如果起點到終點的連線不經過任何障礙就刪除中間所有的節點。bool isLineWalkable(const Grid grid, int x0, int y0, int x1, int y1) { // Bresenhams line algorithm int dx std::abs(x1 - x0); int dy std::abs(y1 - y0); int sx x0 x1 ? 1 : -1; int sy y0 y1 ? 1 : -1; int err dx - dy; int cx x0, cy y0; while (cx ! x1 || cy ! y1) { if (!grid.isWalkable(cx, cy)) return false; int e2 2 * err; if (e2 -dy) { err - dy; cx sx; } if (e2 dx) { err dx; cy sy; } } return true; } void smoothPath(const Grid grid, std::vectorPathNode path) { if (path.size() 2) return; std::vectorPathNode smoothed; smoothed.push_back(path[0]); size_t currentIndex 0; while (currentIndex path.size() - 1) { size_t farthest currentIndex; for (size_t i currentIndex 1; i path.size(); i) { if (isLineWalkable(grid, path[currentIndex].x, path[currentIndex].y, path[i].x, path[i].y)) { farthest i; } else { break; } } smoothed.push_back(path[farthest]); currentIndex farthest; } path smoothed; }注意Bresenham算法判斷的是“線經過的格子是否都可行走”如果單位碰撞半徑大于格子大小還需要把判定條件改成“線兩側的保護帶內都沒有障礙”。否則單位會試圖從兩個障礙物之間不足一個格子寬度的縫隙擠過去。5. 實測對比與算法選型建議5.1 測試場景設計我用三張地圖做了對照測試一張是500x500的開闊平原只有零星幾棟建筑一張是200x200的密集迷宮走廊窄到只能容納一個單位一張是混合地形一半開闊一半是建筑群。每張地圖隨機生成100對起點和終點統計平均耗時和擴展節點數。測試環境是Visual Studio 2022Release x64CPU是常見的i7級別單線程跑。所有路徑都用同一套A*作為基準再對比JPS和混合策略。5.2 性能數據對比以下是平均每對起點終點的耗時對比表格地圖場景A*耗時(ms)A*擴展節點數JPS耗時(ms)JPS擴展節點數混合策略耗時(ms)開闊平原8.42156,2340.673,4820.71密集迷宮5.1848,2264.9345,1245.21混合地形6.8792,1182.3418,4322.41數據很直觀。開闊平原上JPS比A快了超過十倍擴展節點數只有A的2.2%。密集迷宮里JPS幾乎沒有優勢瘋狂跳點導致性能退化到接近A*。混合地形JPS依然有近三倍的優勢。Wall-tracing的表現不容易用上面的數字衡量因為它的路徑長度可能不是最短但它生成路徑的耗時極低。在我的測試里一條走廊里的路徑生成耗時不到0.05ms而且生成的路徑視覺上很自然像人貼著墻走路。5.3 選型建議什么場景用哪種算法根據實測數據我的建議是如果游戲地圖以開放區域為主比如《帝國時代》早期版本JPS是絕對主力。地圖越開闊JPS性能優勢越明顯。但要注意JPS要求地圖是規則的方格網格如果游戲用了導航網格NavMeshJPS就無法直接使用。如果地圖是狹窄走廊密布比如地牢類游戲這時候A就夠了JPS的跳點優勢發揮不出來反而多了一些跳點檢查的開銷。Wall-tracing在這種圖上很出彩可以先用來摸清可通行性再決定是否用A精修。如果項目是3D游戲且地形高度有變化網格地圖就不合適了應該用NavMesh配合A*。JPS和Wall-tracing是2D網格的專屬優化。6. 動態障礙物、跳點失效等常見問題與排查實錄6.1 動態障礙物導致JPS跳點失效在一次測試中我遇到了一個詭異的問題地圖上有一堵臨時修建的墻玩家建了建筑JPS計算出來的路徑明明避開了這堵墻但單位的實際移動路線還是穿墻而過。排查后發現原因JPS的跳點目標是基于“靜態障礙物”預計算緩存來做的我為了讓每次尋路更快把某些跳點關系緩存了。建筑建好后地圖的grid更新了但緩存沒有失效JPS仍然使用舊的跳點關系導致跳過的路徑實際上是穿過建筑的位置。解決方法是在setWalkable操作時必須同步清空JPS的跳點緩存。我加了一個版本號機制每次地圖變動時自增versionJPS計算時檢查版本號如果發現緩存版本過舊就重新計算。void Grid::setWalkable(int x, int y, bool walkable) { walkable_[y * width_ x] walkable; version_; // 讓緩存失效 }這個坑提醒我JPS的“跳點”不是靜態屬性它取決于地圖當前的障礙物配置。任何地圖改動都必須信號通知尋路系統否則會出現隱蔽的錯誤路徑。6.2 單位卡死在墻角在迷宮地圖里單位經常卡在墻角表現為明明A*算出來的路徑是對的但單位在局部避讓過程中被其他單位推到墻角之后就一直貼著墻角滑動無法回到路徑上。排查過程很費勁。先以為RVO參數問題調了鄰域半徑和最大速度沒有改善。后來加日志發現是平滑算法在墻角的處理上出了bug拉繩子算法把路徑中段的拐點直接刪掉結果剩下的直線路徑穿過了一個狹角單位試圖直線走過去被墻卡住。解決方法是給平滑后的路徑增加一道安全檢查每個生成的路徑點都驗證它到兩邊障礙物的距離是否大于單位碰撞半徑。如果小于就把這個路徑點保留為拐點不刪除。另外如果單位在局部避讓過程中偏移出了全局路徑一定距離比如超過5個單位強制單位重新調用FindPath計算到終點的路徑而不是強行回到舊的全局路徑上。這樣即使被推走了也能快速糾正。void Unit::update(float dt) { // 檢測是否偏離全局路徑太遠 float distToPath distanceToNearestPathPoint(); if (distToPath 5.0f) { path finder_-FindPath(currentGridPos(), targetGridPos()); } // ... 正常尋路移動 }這個“偏離重規劃”機制非常有用強烈建議做RTS的人加上。它同時解決了單位被地形卡住、被其他單位推到不可通行區域、或者目標點被建筑堵住等一大堆問題。6.3 JPS在斜向移動上的實現錯誤JPS的實現難點主要集中在斜向跳上。我的第一個版本斜向跳的時候沒有先檢查兩個相鄰方向是否可通行導致單位跳出了“墻角穿越”的行為也就是從一個格子直接斜穿到了它的對角格子但這兩個格子之間的公共頂點實際上被障礙物擋住了。這個問題的表象是在密集迷宮里JPS生成的路徑看起來是直線通過一個L形死角但單位實際上走不過去——因為斜向第一步會被墻擋住。修復方式是嚴格遵循JPS的規則斜向移動前必須保證兩個正交方向水平或垂直至少有一個是可以通行的。否則放棄斜向移動。bool canMoveDiagonal(const Grid grid, int x, int y, int dx, int dy) { return grid.isWalkable(x dx, y) || grid.isWalkable(x, y dy); }這個檢查必須在跳躍循環的每一步都做不能只在起點做。因為斜向跳了多步之后中間的某一個位置可能就不滿足條件了。6.4 Path smoothing導致的“切角”問題路徑平滑后由于Bresenham算法直接連線會把墻壁的銳角當成可通行的線判斷導致單位移動時“切割”墻角。特別是當單位碰撞半徑大于0.5個格子時即使格子中心線不穿墻單位的實際碰撞體也會蹭到墻壁。我的解決方法是引入“膨脹地圖”概念把所有障礙物向外擴展一圈膨脹半徑等于單位碰撞半徑對應的格子數基于膨脹后的地圖做路徑搜索和平滑。這樣算出來的路徑天然會遠離墻角。不過膨脹地圖的缺點也明顯狹窄通道寬度小于兩倍碰撞半徑會被直接判定為不可通行這在某些場景下不符合游戲設定。所以我又加了一個fallback邏輯如果A*在膨脹地圖上找不到路徑就回到原始地圖上找然后對路徑做碰撞檢查把穿墻的路徑段替換為沿著墻邊的路徑段。6.5 A*的OpenSet爆炸問題在大地圖上A*經常碰到OpenSet節點數超過百萬的情況。雖然priority_queue操作是O(log N)但N太大時內存開銷和操作開銷都不小。我采取了三個技巧來控制OpenSet大小第一個是“早退機制”。如果G值加上當前節點到終點的H值已經超過了目前找到的最優路徑長度直接剪枝。第二個是“距離限制”。設置一個最大搜索深度比如1000步超過就放棄。因為RTS單位通常不會指揮它繞地球一圈才能到達目的地超長路徑本身就是異常情況。第三個是“分幀尋路”。把尋路計算分攤到多個幀里每幀只處理一定數量的節點單位先沿當前已經算好的部分路徑移動下一幀繼續計算剩余路徑。這在大量單位同時尋路時特別管用。我實測下來把最大每幀處理的節點數設為5000就能保持幀率穩定在60以上。6.6 常見問題速查表癥狀可能原因排查與解決方法JPS路徑穿墻跳點緩存未失效Grid變更時增加版本號清除緩存單位卡墻角平滑算法刪除了關鍵拐點平滑后校驗每點到障礙物距離小于碰撞半徑則保留拐點單位繞遠路H值估計不準檢查啟發函數是否高估改用切比雪夫距離尋路耗時飆升OpenSet過大加早退機制、距離限制、分幀尋路Wall-tracing死循環目標在閉合圍墻內設置maxSteps上限超時回退A*單位重疊、穿插RVO鄰域太小增大鄰域半徑或調小最大速度路徑抖動RVO與全局路徑沖突設置“偏離重規劃”閾值防止走回頭路6.7 性能優化的最終利器路徑緩存即使有了JPS大規模群體尋路依舊有壓力。我做了一個機制來緩解批處理復用。當多個單位的目標點比較接近比如同一批軍隊攻擊同一個建筑時只計算其中一條路徑然后其他單位在這條路徑上做偏移。具體做法是對地圖分區塊每塊記錄最近一次計算的路徑。如果一個單位的目標點落在某區塊內并且目標區塊的路徑緩存離當前時間不超過1秒就直接使用緩存路徑加局部偏移。我這里用了一個簡單的std::unordered_mapint, CachedPathkey是目標區塊的ID。這個緩存的命中率很高實測中能降低70%以上的重復尋路計算量。但要注意失效機制緩存里保存一個地圖版本號版本號變化時所有緩存作廢避免地圖變化后仍然走舊路徑。7. 實測效果與實際項目優化心得我在這套尋路組件上投了兩個多月的時間做了不少測試最終總結出幾條重要的經驗和心得。第一尋路算法的選擇永遠取決于地圖特征而不是算法本身的復雜度。JPS在開闊地圖上是神器但在狹小地圖上甚至不如A*。如果你的項目地圖是多變的建議在客戶端啟動時做一次地圖分析統計可通行格比例、平均走廊寬度等參數然后動態選擇算法。第二算法的正確性遠比炫技重要。我調試JPS的過程中大概有三分之一的時間花在追“路徑穿越墻壁”這種問題上。最后把邏輯簡化成嚴格按照原始論文的跳點定義來實現才穩定下來。所以如果你是自己從零實現建議先從A*開始跑通功能再逐步加入JPS和Wall-tracing每一步都要有獨立的測試用例。第三C里盡量用連續內存的數據結構。我在最初版本用了std::vectorstd::shared_ptrNode來管理所有節點結果尋路60%的時間都花在shared_ptr的引用計數上。改成用std::vectorNode按池化管理后耗時直接降了一半。C尋路這種高頻小內存分配場景最忌諱到處new和delete。第四Unit的操作不要太依賴幀更新。我一開始每幀都對所有單位的路徑做檢查結果單位數量一多就卡。后來改成每個單位隔0.1秒才檢查一次路徑狀態玩家基本感覺不到差異但CPU開銷降低了近40%。RTS尋路的真正瓶頸往往不是單條路徑計算的復雜度而是單位數量乘以更新頻率的乘法關系。8. 后續還能怎么擴展這套尋路組件目前已經能穩定支撐幾百個單位同時尋路在開闊地圖上可以支撐上千個單位。如果再想往上走方向基本是兩個一個是實現六邊形網格的支持。JPS原本是為正方形網格設計的但很多戰棋類游戲用六邊形網格算法需要重新推導。另一個是并行化。多線程尋路時需要小心處理共享地圖數據用讀寫鎖保護grid或者啟用“每塊區域一個grid”的架構讓不同區域獨立計算。還有一個值得推薦的方向是“螞蟻算法”式的流場尋路Flow Field Pathfinding。流場尋路特別適合大規模單位向同一目標移動的場景做法是預先計算每個格子到目標的方向場單位直接沿著方向場移動不需要各自尋路。我在這套組件里還沒實現完整版但實測碎片化流場的可行性很強如果你的游戲是塔防或者“狂潮”式的戰斗模式強烈建議研究這個方向。最后再分享一個小技巧如果你也打算用A*記得把地圖坐標到索引的轉換函數寫成inline避免做不必要的分支判斷。類似y * width x這種操作是高頻路徑編譯器如果不內聯的話會產生大量函數調用開銷。時間長了會有很直觀的性能差距。尋路是個看似簡單、實際很容易失控的問題。希望這篇文章能幫你少走一些彎路。踩過的坑真的比看論文有用。本文還有配套的精品資源點擊獲取 C++實現RTS尋路三合一：A*、JPS與Wall-tracing實戰解析
簡介尋路算法是游戲開發中的核心基礎尤其在策略類游戲中如何在復雜地圖上實現高效、穩定的路徑規劃直接關系到玩家的操作體驗。在經典方案中A*算法憑借其通用性和穩定性成為最常用的兜底選擇但在大規模開闊地圖上容易因節點膨脹導致性能下降JPS跳點搜索通過剪枝對稱路徑大幅縮減搜索空間成為開闊地形的加速利器而Wall-tracing則模仿沿墻探索的本能能巧妙應對貼墻和狹窄走廊等特殊場景。這些算法各有優劣實際工程中需要根據地圖特征動態選型。本文圍繞這三類算法結合C實現講述了從網格數據結構、堆優化、跳點檢測到路徑平滑與群體避讓的完整技術方案并提供了性能實測數據和踩坑記錄。無論是游戲開發者還是尋路算法愛好者都能從中獲得可落地的工程經驗讓尋路系統在真實項目中兼顧速度與穩健。1. 為什么要寫一個三合一尋路組件做過RTS或者類RTS游戲的人應該都有體會尋路不是“能走到”就行而是要經得起成百上千個單位同時尋路的考驗。我之前用C寫的這個RTS尋路組件其實是被逼出來的——一開始只用了A*地圖一大、單位一多幀率直接崩到沒法看后來在開闊地形上換成了JPS又快了不少最后加上Wall-tracing處理貼墻、繞障礙這類畸形路徑時省了很多麻煩。這篇文章就來聊聊我這套用C實現的RTS尋路三件套A*、JPS、Wall-tracing。我會從問題拆解、算法選型、核心代碼實現、性能實測到踩坑記錄把整個設計和實操過程都攤開來講適合正在做策略游戲、仿真項目或者對尋路算法感興趣的人參考。先說結論沒有一種算法是萬能的。A*是兜底的通用方案JPS負責開闊地圖上的性能加速Wall-tracing用來處理“沿墻走”這類邊界場景。三者組合起來才能在真實RTS場景里做到既穩又快。2. RTS路徑查找的問題拆解與方案選型2.1 RTS尋路和普通尋路差在哪如果你只做過迷宮求解那種小規模尋路可能覺得A*已經夠用了。但RTS場景完全是另一個量級。典型的RTS對局里可能有幾百個單位同時下達移動指令每個單位每幀都需要獲取路徑信息這意味著尋路系統必須支持高頻調用。RTS尋路和普通尋路的差異主要體現在幾個方面第一是規模。地圖往往達到512x512甚至2048x2048個格子數據量大了算法的空間復雜度和時間復雜度都會被放大。第二是動態性。戰爭迷霧、建筑建造、單位阻擋都會改變地圖的通行狀態尋路結果不能永遠緩存。第三是群體性。很多單位擠在一起走如果每個單位都各走各的路徑上會出現大量重疊和沖突視覺上就很假A*算法本身并不處理單位之間的避讓問題。第四是實時性。RTS追求的是即時反饋玩家點一下鼠標單位必須迅速響應尋路耗時一旦超過幾毫秒就會影響體驗。所以就引出了配置多個算法的必要性我不能靠單一算法對付所有場景必須根據地圖特點在運行時選擇最合適的策略。2.2 為什么是A*、JPS、Wall-tracing三件套A是經典中的經典。它的優點在于通用、穩定只要有合適的啟發函數任何地圖上都能找到可行路徑。缺點是慢尤其在開闊地圖上A會擴展大量節點因為從起點到終點附近幾乎每個格子都會被塞進開放列表。但作為兜底方案它不能丟。JPSJump Point Search是在A基礎上做節點剪枝的算法。它利用了網格地圖中路徑的對稱性——在開闊地帶很多節點走向終點的代價完全相同JPS會沿著一個方向“跳”過去只在轉彎點或者被迫轉彎的“強制鄰居”處才停下來評估。這樣開闊地圖上JPS只需擴展A的幾十分之一的節點。代價是它要求地圖是規則的網格而且障礙物不能太密集否則跳點太多優勢就沒了。Wall-tracing則是另一種思路。它不追求全局最優路徑而是模仿人類“摸著墻走”的本能。在某些地圖上目標點被復雜墻體包圍A*和JPS會繞很大一圈而Wall-tracing可以沿著墻體快速貼近目標。雖然它不走最優路徑但速度快、路徑看起來自然特別是在迷宮里探路時效果很好。三者的關系不是替代而是補位JPS能加速大部分開闊地形的尋路A*兜底任何情況Wall-tracing處理貼墻和狹窄通道。這樣組合之后等于把每種算法的強項都發揮出來。3. 核心數據結構與算法實現細節3.1 地圖網格的C表示任何尋路算法都離不開地圖數據。我用了一個比較簡潔的Grid類來管理網格核心成員包括寬度、高度、障礙標記數組。class Grid { public: Grid(int width, int height) : width_(width), height_(height), walkable_(width * height, true) {} bool isWalkable(int x, int y) const { if (x 0 || x width_ || y 0 || y height_) return false; return walkable_[y * width_ x]; } void setWalkable(int x, int y, bool walkable) { walkable_[y * width_ x] walkable; } int width() const { return width_; } int height() const { return height_; } private: int width_; int height_; std::vectorbool walkable_; };這里有個細節std::vectorbool是有爭議的選擇因為它做了位壓縮性能并不一定比std::vectorchar快。但在我的測試里對于500x500的地圖vector 的內存占用只有約30KB而vector 要250KB。緩存友好度上vector 反而更優讀取速度也足夠快。不過如果你想做更強的擴展比如存地形消耗值建議直接用vectorchar或者vectoruint8_t。網格的障礙狀態不只是靜態的。RTS游戲里建筑會動態建造所以Grid要支持運行期改障礙。這一點在后面動態避障部分會細講。3.2 二叉堆優化的A*基礎和坑A*核心是維護兩個列表開放列表OpenSet和關閉列表ClosedSet。每次從OpenSet里取F值最小的節點擴展直到找到終點或者OpenSet清空。F值由G值起點到當前節點的實際代價和H值當前節點到終點的估計代價相加得到。C實現時OpenSet最忌諱用std::vector加線性掃描找最小值那會直接讓算法復雜度退化成O(n^2)。我用了std::priority_queue配合自定義比較器這是最簡單也最可靠的方案如果想壓榨性能可以手寫二叉堆或者用斐波那契堆但實測下來二叉堆已經足夠。struct Node { int x, y; int g, h; int parentIndex; }; struct NodeCompare { bool operator()(const Node* a, const Node* b) const { return (a-g a-h) (b-g b-h); } }; using OpenSet std::priority_queueNode*, std::vectorNode*, NodeCompare;有個細節priority_queue的top()返回的是指針但指針指向的節點可能會被重復加入。解決這個問題我會用一個std::unordered_mapint, Node*來記錄每個坐標是否已經在關閉列表里如果已經關閉就跳過。啟發函數的選擇也很關鍵。對于四方向網格用曼哈頓距離對于八方向網格用切比雪夫距離或歐幾里得距離。RTS里單位通常允許八方向移動所以我的H值默認用切比雪夫距離int heuristic(int x1, int y1, int x2, int y2) { return std::max(std::abs(x1 - x2), std::abs(y1 - y2)); }注意H值不能高估實際代價否則A*退化成貪心搜索可能找到次優路徑如果H值太低擴展節點又會太多。切比雪夫距離估算八方向移動正好不低估也不高估是這個場景下的標準選擇。3.3 JPS的核心跳點搜索JPS的關鍵不是搜索每一個鄰居而是找到“跳點”。跳點分兩類一類是強迫鄰居所在的節點另一類是具有強制鄰居的節點。理解了這兩個概念JPS就理解了大半。強迫鄰居Forced Neighbor當節點X的某個相鄰方向被障礙擋住但同時另一側的方向可以通過并且這個方向的移動會導致路徑需要轉向時這個被強制訪問的鄰居就是強迫鄰居。比如你在一條狹窄走廊里走左邊是墻前方是墻但右前方有一個缺口你必須右轉才能繼續前進那個缺口方向就是你被強迫拐彎的方向。跳點的規則可以總結為直線跳躍沿著水平或垂直方向一直前進直到遇到障礙、地圖邊界或找到具有強迫鄰居的節點。對角線跳躍先檢查兩個正方向水平和垂直是否能走如果能走就先做直線跳躍再沿對角線推進。如果對角線方向不能走則停止。下面是我實現的直線跳躍偽代碼bool jumpStraight(int x, int y, int dx, int dy, const Grid grid, int targetX, int targetY, int jumpX, int jumpY) { int nx x dx; int ny y dy; while (grid.isWalkable(nx, ny)) { if (nx targetX ny targetY) { jumpX nx; jumpY ny; return true; } // 檢查是否有強迫鄰居 if (dx ! 0 dy 0) { // 水平移動檢查垂直方向是否有強迫鄰居 if ((grid.isWalkable(nx, ny 1) !grid.isWalkable(nx - dx, ny 1)) || (grid.isWalkable(nx, ny - 1) !grid.isWalkable(nx - dx, ny - 1))) { jumpX nx; jumpY ny; return true; } } else if (dx 0 dy ! 0) { // 垂直移動檢查水平方向是否有強迫鄰居 if ((grid.isWalkable(nx 1, ny) !grid.isWalkable(nx 1, ny - dy)) || (grid.isWalkable(nx - 1, ny) !grid.isWalkable(nx - 1, ny - dy))) { jumpX nx; jumpY ny; return true; } } nx dx; ny dy; } return false; }這段代碼的關鍵在于只有當某個方向上有“強制轉彎”的鄰居時當前節點才算跳點否則就一路跳到底。實際運行中JPS在開闊地圖上擴展的節點數會非常少因為可以跨越大片區域不做節點評估。3.4 Wall-tracing的實現思路Wall-tracing嚴格來說不是傳統的A變體而是另一種路徑追蹤算法。它的核心規則是“右手法則”一直沿著墻走遇到岔路優先向右直到到達目標點。這個算法天然適合迷宮也適合處理A容易繞遠路的貼墻場景。我的實現策略是這樣的先嘗試用JPS計算路徑如果路徑的開頭部分貼著墻或者目標點在墻的包圍圈內那么用Wall-tracing生成一段貼墻路徑再和JPS的路徑拼接。Wall-tracing的狀態機比較容易理解enum class WallSide { LEFT, RIGHT }; bool wallTrace(const Grid grid, int startX, int startY, int targetX, int targetY, WallSide side, std::vectorPathNode path) { int currentX startX; int currentY startY; int dirX 0, dirY 1; // 初始方向向上 // 根據側邊選擇轉向 auto turnLeft []() { int tmp dirX; dirX -dirY; dirY tmp; }; auto turnRight []() { int tmp dirX; dirX dirY; dirY -tmp; }; // 判斷前方是否可走 auto canMoveForward []() { return grid.isWalkable(currentX dirX, currentY dirY); }; // 判斷側邊是否靠墻 auto sideWallBlocked []() { if (side WallSide::RIGHT) { // 右手邊需要是墻 return !grid.isWalkable(currentX - dirY, currentY dirX); } return !grid.isWalkable(currentX dirY, currentY - dirX); }; int stepCount 0; int maxSteps grid.width() * grid.height() * 4; // 防止死循環 while ((currentX ! targetX || currentY ! targetY) stepCount maxSteps) { path.push_back({currentX, currentY}); // 規則1先嘗試右轉左手法則/左轉右手法則 if (side WallSide::RIGHT) { turnRight(); if (canMoveForward()) { currentX dirX; currentY dirY; stepCount; continue; } turnLeft(); // 恢復舊方向 } // 規則2如果側邊不是墻需要轉向靠近墻 if (!sideWallBlocked()) { if (side WallSide::RIGHT) turnLeft(); else turnRight(); } // 規則3盡量向前 if (canMoveForward()) { currentX dirX; currentY dirY; } else { // 規則4前方被擋轉向 if (side WallSide::RIGHT) turnLeft(); else turnRight(); } stepCount; } path.push_back({currentX, currentY}); return (currentX targetX currentY targetY); }這個實現最需要注意的是死循環問題。如果地圖里有閉環的圍墻Wall-tracing會一直轉圈。所以必須加一個maxSteps限制超時就放棄回退到A*方案。另外Wall-tracing只能找到一條可行路徑不保證最短。所以它在我這個系統里只作為一個“走廊探路器”真正的路徑優化還是交給后續的路徑平滑模塊來做。4. 從單單位尋路到群體尋路的工程實踐4.1 尋路框架的整體架構整個尋路組件的核心入口是一個PathFinder類它對外提供統一的FindPath接口。調用方不需要關心底層用哪個算法PathFinder會根據地圖和路徑特點自動選擇。class PathFinder { public: PathFinder(Grid* grid); // 統一入口 std::vectorPathNode FindPath(int startX, int startY, int targetX, int targetY); private: Grid* grid_; bool useJPS_; bool useWallTrace_; std::vectorPathNode findPathAStar(int startX, int startY, int targetX, int targetY); std::vectorPathNode findPathJPS(int startX, int startY, int targetX, int targetY); std::vectorPathNode findPathWallTrace(int startX, int startY, int targetX, int targetY); void smoothPath(std::vectorPathNode path); };在FindPath內部我會做幾步判斷第一步如果起點或終點不可通行直接返回空路徑。第二步用A跑一個簡化版本限制最大搜索步數作為兜底。如果搜索節點數很少比如小于100個說明地圖很簡單直接返回A結果。第三步如果地圖比較大且路徑跨越大片開闊地用JPS。判斷依據是起點和終點的曼哈頓距離大于某個閾值我設的是32且地圖開闊度較高連續可通行格占比大。第四步如果目標點被墻壁包圍或者路徑需要穿過狹窄通道拼接Wall-tracing的初始段作為“引導路徑”。這個自動選擇邏輯一開始我做成硬編碼規則后來發現不同地圖的閾值不好調最后改成基于運行時的快速采樣先往8個方向各做30格直線檢測計算可通行比例再決定用哪個算法。4.2 多單位尋路時的避讓與流量控制單單位尋路跑通之后真正讓RTS動起來的是群體尋路。群體尋路最大的問題不是路徑計算而是單位之間的互相阻擋。A*算出來的路徑上可能有幾十個單位擠在同一條大道上。我用的方案是“路徑 局部避讓”的兩層架構。第一層PathFinder負責計算全局路徑。第二層每個單位在沿路徑移動時執行RVO互惠速度障礙局部避讓算法。RVO的含義是單位在計算自己下一步速度時假設對方也會采取同樣的避讓策略這樣避免來回抖動。RVO的C實現核心是計算碰撞速度區間Vector2 computeRVO(const Vector2 pos, const Vector2 vel, const std::vectorUnit* neighbors, float maxSpeed) { Vector2 newVel vel; for (Unit* neighbor : neighbors) { Vector2 relPos neighbor-pos - pos; Vector2 relVel neighbor-vel - vel; float dist relPos.length(); float combinedRadius unitRadius_ neighbor-unitRadius_; if (dist combinedRadius 0.01f) { // 太近緊急分開 Vector2 pushDir relPos.normalized(); newVel - pushDir * (combinedRadius - dist) * 5.0f; continue; } // 計算碰撞時間 float relativeSpeed absDot(relVel, relPos.normalized()); if (relativeSpeed 0.0f) { float timeToCollision (dist - combinedRadius) / relativeSpeed; if (timeToCollision 2.0f) { // 這個方向有碰撞風險忽略鄰居的速度影響 newVel relPos.normalized() * maxSpeed; } } } return clampToMaxSpeed(newVel, maxSpeed); }這里有個經驗RVO的鄰域半徑不要設太大一般取3到4個單位半徑就夠了。鄰域太大單位會探測到十萬八千里之外的碰撞風險導致集群整體移動異常緩慢太小又起不到避讓效果。4.3 路徑平滑與簡化A*和JPS輸出的是網格節點路徑直接給單位走會顯得很機械。單位每一步都朝網格中心點走視覺上像在走“之”字形。所以必須做路徑平滑。我使用了拉繩子算法也叫漏斗算法Funnel Algorithm。它的思想是把路徑的起點和終點連成一條繩子如果繩子被障礙物擋住就沿著墻邊滑動繩子直到找到最短的、不被障礙物遮擋的路徑。代碼上不復雜但要注意浮點數精度問題。我的實現里先用網格坐標做線性插值然后做射線檢測如果起點到終點的連線不經過任何障礙就刪除中間所有的節點。bool isLineWalkable(const Grid grid, int x0, int y0, int x1, int y1) { // Bresenhams line algorithm int dx std::abs(x1 - x0); int dy std::abs(y1 - y0); int sx x0 x1 ? 1 : -1; int sy y0 y1 ? 1 : -1; int err dx - dy; int cx x0, cy y0; while (cx ! x1 || cy ! y1) { if (!grid.isWalkable(cx, cy)) return false; int e2 2 * err; if (e2 -dy) { err - dy; cx sx; } if (e2 dx) { err dx; cy sy; } } return true; } void smoothPath(const Grid grid, std::vectorPathNode path) { if (path.size() 2) return; std::vectorPathNode smoothed; smoothed.push_back(path[0]); size_t currentIndex 0; while (currentIndex path.size() - 1) { size_t farthest currentIndex; for (size_t i currentIndex 1; i path.size(); i) { if (isLineWalkable(grid, path[currentIndex].x, path[currentIndex].y, path[i].x, path[i].y)) { farthest i; } else { break; } } smoothed.push_back(path[farthest]); currentIndex farthest; } path smoothed; }注意Bresenham算法判斷的是“線經過的格子是否都可行走”如果單位碰撞半徑大于格子大小還需要把判定條件改成“線兩側的保護帶內都沒有障礙”。否則單位會試圖從兩個障礙物之間不足一個格子寬度的縫隙擠過去。5. 實測對比與算法選型建議5.1 測試場景設計我用三張地圖做了對照測試一張是500x500的開闊平原只有零星幾棟建筑一張是200x200的密集迷宮走廊窄到只能容納一個單位一張是混合地形一半開闊一半是建筑群。每張地圖隨機生成100對起點和終點統計平均耗時和擴展節點數。測試環境是Visual Studio 2022Release x64CPU是常見的i7級別單線程跑。所有路徑都用同一套A*作為基準再對比JPS和混合策略。5.2 性能數據對比以下是平均每對起點終點的耗時對比表格地圖場景A*耗時(ms)A*擴展節點數JPS耗時(ms)JPS擴展節點數混合策略耗時(ms)開闊平原8.42156,2340.673,4820.71密集迷宮5.1848,2264.9345,1245.21混合地形6.8792,1182.3418,4322.41數據很直觀。開闊平原上JPS比A快了超過十倍擴展節點數只有A的2.2%。密集迷宮里JPS幾乎沒有優勢瘋狂跳點導致性能退化到接近A*。混合地形JPS依然有近三倍的優勢。Wall-tracing的表現不容易用上面的數字衡量因為它的路徑長度可能不是最短但它生成路徑的耗時極低。在我的測試里一條走廊里的路徑生成耗時不到0.05ms而且生成的路徑視覺上很自然像人貼著墻走路。5.3 選型建議什么場景用哪種算法根據實測數據我的建議是如果游戲地圖以開放區域為主比如《帝國時代》早期版本JPS是絕對主力。地圖越開闊JPS性能優勢越明顯。但要注意JPS要求地圖是規則的方格網格如果游戲用了導航網格NavMeshJPS就無法直接使用。如果地圖是狹窄走廊密布比如地牢類游戲這時候A就夠了JPS的跳點優勢發揮不出來反而多了一些跳點檢查的開銷。Wall-tracing在這種圖上很出彩可以先用來摸清可通行性再決定是否用A精修。如果項目是3D游戲且地形高度有變化網格地圖就不合適了應該用NavMesh配合A*。JPS和Wall-tracing是2D網格的專屬優化。6. 動態障礙物、跳點失效等常見問題與排查實錄6.1 動態障礙物導致JPS跳點失效在一次測試中我遇到了一個詭異的問題地圖上有一堵臨時修建的墻玩家建了建筑JPS計算出來的路徑明明避開了這堵墻但單位的實際移動路線還是穿墻而過。排查后發現原因JPS的跳點目標是基于“靜態障礙物”預計算緩存來做的我為了讓每次尋路更快把某些跳點關系緩存了。建筑建好后地圖的grid更新了但緩存沒有失效JPS仍然使用舊的跳點關系導致跳過的路徑實際上是穿過建筑的位置。解決方法是在setWalkable操作時必須同步清空JPS的跳點緩存。我加了一個版本號機制每次地圖變動時自增versionJPS計算時檢查版本號如果發現緩存版本過舊就重新計算。void Grid::setWalkable(int x, int y, bool walkable) { walkable_[y * width_ x] walkable; version_; // 讓緩存失效 }這個坑提醒我JPS的“跳點”不是靜態屬性它取決于地圖當前的障礙物配置。任何地圖改動都必須信號通知尋路系統否則會出現隱蔽的錯誤路徑。6.2 單位卡死在墻角在迷宮地圖里單位經常卡在墻角表現為明明A*算出來的路徑是對的但單位在局部避讓過程中被其他單位推到墻角之后就一直貼著墻角滑動無法回到路徑上。排查過程很費勁。先以為RVO參數問題調了鄰域半徑和最大速度沒有改善。后來加日志發現是平滑算法在墻角的處理上出了bug拉繩子算法把路徑中段的拐點直接刪掉結果剩下的直線路徑穿過了一個狹角單位試圖直線走過去被墻卡住。解決方法是給平滑后的路徑增加一道安全檢查每個生成的路徑點都驗證它到兩邊障礙物的距離是否大于單位碰撞半徑。如果小于就把這個路徑點保留為拐點不刪除。另外如果單位在局部避讓過程中偏移出了全局路徑一定距離比如超過5個單位強制單位重新調用FindPath計算到終點的路徑而不是強行回到舊的全局路徑上。這樣即使被推走了也能快速糾正。void Unit::update(float dt) { // 檢測是否偏離全局路徑太遠 float distToPath distanceToNearestPathPoint(); if (distToPath 5.0f) { path finder_-FindPath(currentGridPos(), targetGridPos()); } // ... 正常尋路移動 }這個“偏離重規劃”機制非常有用強烈建議做RTS的人加上。它同時解決了單位被地形卡住、被其他單位推到不可通行區域、或者目標點被建筑堵住等一大堆問題。6.3 JPS在斜向移動上的實現錯誤JPS的實現難點主要集中在斜向跳上。我的第一個版本斜向跳的時候沒有先檢查兩個相鄰方向是否可通行導致單位跳出了“墻角穿越”的行為也就是從一個格子直接斜穿到了它的對角格子但這兩個格子之間的公共頂點實際上被障礙物擋住了。這個問題的表象是在密集迷宮里JPS生成的路徑看起來是直線通過一個L形死角但單位實際上走不過去——因為斜向第一步會被墻擋住。修復方式是嚴格遵循JPS的規則斜向移動前必須保證兩個正交方向水平或垂直至少有一個是可以通行的。否則放棄斜向移動。bool canMoveDiagonal(const Grid grid, int x, int y, int dx, int dy) { return grid.isWalkable(x dx, y) || grid.isWalkable(x, y dy); }這個檢查必須在跳躍循環的每一步都做不能只在起點做。因為斜向跳了多步之后中間的某一個位置可能就不滿足條件了。6.4 Path smoothing導致的“切角”問題路徑平滑后由于Bresenham算法直接連線會把墻壁的銳角當成可通行的線判斷導致單位移動時“切割”墻角。特別是當單位碰撞半徑大于0.5個格子時即使格子中心線不穿墻單位的實際碰撞體也會蹭到墻壁。我的解決方法是引入“膨脹地圖”概念把所有障礙物向外擴展一圈膨脹半徑等于單位碰撞半徑對應的格子數基于膨脹后的地圖做路徑搜索和平滑。這樣算出來的路徑天然會遠離墻角。不過膨脹地圖的缺點也明顯狹窄通道寬度小于兩倍碰撞半徑會被直接判定為不可通行這在某些場景下不符合游戲設定。所以我又加了一個fallback邏輯如果A*在膨脹地圖上找不到路徑就回到原始地圖上找然后對路徑做碰撞檢查把穿墻的路徑段替換為沿著墻邊的路徑段。6.5 A*的OpenSet爆炸問題在大地圖上A*經常碰到OpenSet節點數超過百萬的情況。雖然priority_queue操作是O(log N)但N太大時內存開銷和操作開銷都不小。我采取了三個技巧來控制OpenSet大小第一個是“早退機制”。如果G值加上當前節點到終點的H值已經超過了目前找到的最優路徑長度直接剪枝。第二個是“距離限制”。設置一個最大搜索深度比如1000步超過就放棄。因為RTS單位通常不會指揮它繞地球一圈才能到達目的地超長路徑本身就是異常情況。第三個是“分幀尋路”。把尋路計算分攤到多個幀里每幀只處理一定數量的節點單位先沿當前已經算好的部分路徑移動下一幀繼續計算剩余路徑。這在大量單位同時尋路時特別管用。我實測下來把最大每幀處理的節點數設為5000就能保持幀率穩定在60以上。6.6 常見問題速查表癥狀可能原因排查與解決方法JPS路徑穿墻跳點緩存未失效Grid變更時增加版本號清除緩存單位卡墻角平滑算法刪除了關鍵拐點平滑后校驗每點到障礙物距離小于碰撞半徑則保留拐點單位繞遠路H值估計不準檢查啟發函數是否高估改用切比雪夫距離尋路耗時飆升OpenSet過大加早退機制、距離限制、分幀尋路Wall-tracing死循環目標在閉合圍墻內設置maxSteps上限超時回退A*單位重疊、穿插RVO鄰域太小增大鄰域半徑或調小最大速度路徑抖動RVO與全局路徑沖突設置“偏離重規劃”閾值防止走回頭路6.7 性能優化的最終利器路徑緩存即使有了JPS大規模群體尋路依舊有壓力。我做了一個機制來緩解批處理復用。當多個單位的目標點比較接近比如同一批軍隊攻擊同一個建筑時只計算其中一條路徑然后其他單位在這條路徑上做偏移。具體做法是對地圖分區塊每塊記錄最近一次計算的路徑。如果一個單位的目標點落在某區塊內并且目標區塊的路徑緩存離當前時間不超過1秒就直接使用緩存路徑加局部偏移。我這里用了一個簡單的std::unordered_mapint, CachedPathkey是目標區塊的ID。這個緩存的命中率很高實測中能降低70%以上的重復尋路計算量。但要注意失效機制緩存里保存一個地圖版本號版本號變化時所有緩存作廢避免地圖變化后仍然走舊路徑。7. 實測效果與實際項目優化心得我在這套尋路組件上投了兩個多月的時間做了不少測試最終總結出幾條重要的經驗和心得。第一尋路算法的選擇永遠取決于地圖特征而不是算法本身的復雜度。JPS在開闊地圖上是神器但在狹小地圖上甚至不如A*。如果你的項目地圖是多變的建議在客戶端啟動時做一次地圖分析統計可通行格比例、平均走廊寬度等參數然后動態選擇算法。第二算法的正確性遠比炫技重要。我調試JPS的過程中大概有三分之一的時間花在追“路徑穿越墻壁”這種問題上。最后把邏輯簡化成嚴格按照原始論文的跳點定義來實現才穩定下來。所以如果你是自己從零實現建議先從A*開始跑通功能再逐步加入JPS和Wall-tracing每一步都要有獨立的測試用例。第三C里盡量用連續內存的數據結構。我在最初版本用了std::vectorstd::shared_ptrNode來管理所有節點結果尋路60%的時間都花在shared_ptr的引用計數上。改成用std::vectorNode按池化管理后耗時直接降了一半。C尋路這種高頻小內存分配場景最忌諱到處new和delete。第四Unit的操作不要太依賴幀更新。我一開始每幀都對所有單位的路徑做檢查結果單位數量一多就卡。后來改成每個單位隔0.1秒才檢查一次路徑狀態玩家基本感覺不到差異但CPU開銷降低了近40%。RTS尋路的真正瓶頸往往不是單條路徑計算的復雜度而是單位數量乘以更新頻率的乘法關系。8. 后續還能怎么擴展這套尋路組件目前已經能穩定支撐幾百個單位同時尋路在開闊地圖上可以支撐上千個單位。如果再想往上走方向基本是兩個一個是實現六邊形網格的支持。JPS原本是為正方形網格設計的但很多戰棋類游戲用六邊形網格算法需要重新推導。另一個是并行化。多線程尋路時需要小心處理共享地圖數據用讀寫鎖保護grid或者啟用“每塊區域一個grid”的架構讓不同區域獨立計算。還有一個值得推薦的方向是“螞蟻算法”式的流場尋路Flow Field Pathfinding。流場尋路特別適合大規模單位向同一目標移動的場景做法是預先計算每個格子到目標的方向場單位直接沿著方向場移動不需要各自尋路。我在這套組件里還沒實現完整版但實測碎片化流場的可行性很強如果你的游戲是塔防或者“狂潮”式的戰斗模式強烈建議研究這個方向。最后再分享一個小技巧如果你也打算用A*記得把地圖坐標到索引的轉換函數寫成inline避免做不必要的分支判斷。類似y * width x這種操作是高頻路徑編譯器如果不內聯的話會產生大量函數調用開銷。時間長了會有很直觀的性能差距。尋路是個看似簡單、實際很容易失控的問題。希望這篇文章能幫你少走一些彎路。踩過的坑真的比看論文有用。本文還有配套的精品資源點擊獲取