在游戲世界的尋路中，通常會有這樣一種情況：在小地圖上點擊目標(biāo)點時，點擊到了障礙物或者建筑上，然后游戲會提示我們目標(biāo)地點無法到達。玩家必須非常小心的在小地圖上點擊目標(biāo)區(qū)域的空白部分，才能移動到目標(biāo)地點。那么，有沒有辦法來改進一下這種不友好的體驗?zāi)?#xff1f;

下面給出兩種方法：

最近可達點替代：當(dāng)目標(biāo)點S不可達時，在S點周圍尋找一個最近的可達點R，讓R替代S作為目標(biāo)點尋路。

最近點檢測法：設(shè)置一個最小距離，尋路過程中，不斷檢測每個加入openList的點，如果該點到目標(biāo)點S的距離小于最小距離，保存當(dāng)前點為N，并修改最小距離。在尋路結(jié)束時，如果目標(biāo)點S無法到達，那么將最接近點N作為尋路的終點。

1.最近可達點替代

最近可達點替代方法是在尋路之前的一個預(yù)處理，首先需要檢測目標(biāo)點是否可達，如果不可達則需檢測最近的一個可達的點作為目標(biāo)點。其情形如下：

??

從A點到S的尋路中，發(fā)現(xiàn)S點不可達時，在S點周圍一圈的點中搜尋到R，使用R點作為替代目標(biāo)點。如果A點需要移動到S2點呢？我們在檢測附近可達點的時候，引入一個變量depth，表示不可達點的深度，意為從S到最近的可達點需要搜尋的圈數(shù)。

代碼延續(xù)前一篇文章A*尋路算法之解決路徑多拐點問題中的A*尋路算法，搜索替換點方法實現(xiàn)如下：

public Node getNearestReachableNode(Node node, int maxDepth) {if (maxDepth <= 0 || map.canReach(node.x, node.y)) {return node;}for (int depth = 1; depth < maxDepth ; depth++) {for (int i = node.x - depth; i <= node.x + depth; i++) {// 左if (map.canReach(i, node.y - depth)) {return new Node(i, node.y - depth);}// 右if (map.canReach(i, node.y + depth)) {return new Node(i, node.y + depth);}}for (int i = node.y - depth + 1; i < node.y + depth; i++) {// 上if (map.canReach(node.x - depth, i)) {return new Node(node.x - depth, i);}// 下if (map.canReach(node.x + depth, i)) {return new Node(node.x + depth, i);}}}return node;}

2.最近點檢測法

最近點檢測，基本的想法就是在尋路過程中不斷檢測加入到openList中的點與目標(biāo)點的距離。當(dāng)無法尋路到目標(biāo)點時，可以移動到這個最近點上。下面直接上代碼：

public List<Node> findPath(Node startNode, Node endNode) {int minDistance = Integer.MAX_VALUE;Node nearestNode = startNode;newOpenList.add(startNode);Node currNode = null;while ((currNode = newOpenList.poll()) != null) {removeKey(openSet, currNode.x, currNode.y);addKey(closeSet, currNode.x, currNode.y);ArrayList<Node> neighborNodes = findNeighborNodes(currNode);for (Node nextNode : neighborNodes) {// G + H + Eint gCost = 10 * calcNodeCost(currNode, nextNode) + currNode.gCost + calcNodeExtraCost(currNode, nextNode, endNode);if (contains(openSet, nextNode.x, nextNode.y)) {if (gCost < nextNode.gCost) {nextNode.parent = currNode;nextNode.gCost = gCost;nextNode.fCost = nextNode.gCost + nextNode.hCost;}} else {nextNode.parent = currNode;nextNode.gCost = gCost;nextNode.hCost = 10 * calcNodeCost(nextNode, endNode);nextNode.fCost = nextNode.gCost + nextNode.hCost;newOpenList.add(nextNode);addKey(openSet, nextNode.x, nextNode.y);// 檢測是否是當(dāng)前最近點int distance = Math.abs(nextNode.x - endNode.x) + Math.abs(nextNode.y - endNode.y);if (distance < minDistance) {minDistance = distance;nearestNode = nextNode;}}}if (contains(openSet, endNode.x, endNode.y)) {Node node = findOpenList(newOpenList, endNode);return getPathList(node != null ? node : nearestNode);}}Node node = findOpenList(newOpenList, endNode);return getPathList(node != null ? node : nearestNode);}

大概修改10行左右的代碼，就可以在尋路的過程中解決目標(biāo)點不可達的問題。

3.兩種方法對比

1.目標(biāo)點替代法無法解決尋路到封閉地形的問題，而最近點檢測方法可以移動到附近的點R（?如左圖）。因此，最近點檢測方法一定會生成一條路徑，而目標(biāo)點替代法不一定會有。

2.一般情況下，當(dāng)目標(biāo)點無法移動過去時，最近點檢測方法往往會搜索地圖上的所有點，而目標(biāo)點替代法通過找最近可達點可以解決這個問題。不過在如左圖所示回字形地圖上，標(biāo)點替代法同樣會搜索地圖上的所有點。

3.目標(biāo)點替代法搜索到的可達點，可能不是在起點和中間之間，可能使最終生成路徑變得稍微有點怪異。而最近點檢測方法生成的路徑則很自然。如右圖所示，由于目標(biāo)點替代法查找周圍的可達點時，是按照一定的順序去搜索的。那么就可能出現(xiàn)目標(biāo)點是S,卻走到R1上去了，而很自然的路徑應(yīng)該是走到R點上。這一點在格子大小很小的地圖中表現(xiàn)不是非常明顯，但是在格子很大的地圖上表現(xiàn)的差異感就很強烈了，甚至不能接受了。不過，我們可以通過額外的方法消除這個問題-- 在搜索每一圈的可達點的時候，計算該圈上每一點到起始點的距離大小，選擇距離最小的可達點作為替代點。

? ? ? ??

?

總結(jié)

以上是生活随笔為你收集整理的A*寻路算法之解决目标点不可达问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。