仅可获取当前位置邻接节点时Java实现A*搜索的问题咨询

核心逻辑调整 #

你当前的限制是只能获取实际站立的当前节点邻接信息，无法查询任意存储节点的邻接数据，所以标准离线A的预遍历逻辑无法使用，需要改用**实时A（Real-time A*, RTA*）** 逻辑，核心是每次只处理当前所在节点的邻居，选最优步移动后再探索新节点的邻接信息。

具体调整步骤 #

• 删掉原逻辑中弹出开放列表最小f值节点后遍历该节点邻居的逻辑，改为每次仅处理游戏状态s对应的当前位置节点的邻居
• 保留你原有存储结构即可，仅调整执行流程：
  1. 初始化起点数据，存入已探索节点集合
  2. 把当前所在节点加入封闭列表，调用游戏接口获取当前位置的所有邻接节点
  3. 计算邻接节点的g、h、f值，更新路径映射和开放列表
  4. 从开放列表选出f值最小的节点作为下一步移动目标
  5. 调用游戏移动接口走到目标节点，更新游戏状态s的当前位置
  6. 循环执行上面的步骤，直到当前节点h值为0到达终点

调整后核心代码示例 #

final Map<Long, AStarPrimeNode> nodesData= new HashMap<>();
final FibonacciHeap<AStarPrimeNode> openList= new FibonacciHeap<>();
final Map<AStarPrimeNode, FibonacciHeap.Entry<AStarPrimeNode>> entries= new HashMap<>();
final Map<Long, Long> resPath= new HashMap<>();
final Set<AStarPrimeNode> closedList= new HashSet<>();

// 初始化起点
AStarPrimeNode currentNode = new AStarPrimeNode(s.currentLocation(), s.distanceToRing());
currentNode.setG(0);
nodesData.put(currentNode.getID(), currentNode);

while (currentNode.getH() != 0) {
    closedList.add(currentNode);
    // 仅获取当前所在节点的邻接节点，完全符合你的接口限制
    for (NodeStatus neighbor : s.currentNeighbors()) { 
        AStarPrimeNode neighborData;
        if (nodesData.containsKey(neighbor.getId()))
            neighborData = nodesData.get(neighbor.getId());
        else {
            neighborData = new AStarPrimeNode(neighbor);
            nodesData.put(neighborData.getID(), neighborData);
        }
        if (closedList.contains(neighborData)) continue;

        int newG = currentNode.getG() + 1;
        if (newG < neighborData.getG()) {
            neighborData.setG(newG);
            int f = neighborData.getF();
            resPath.put(neighborData.getID(), currentNode.getID());
            if (!entries.containsKey(neighborData))
                entries.put(neighborData, openList.enqueue(neighborData, f));
            else 
                openList.decreaseKey(entries.get(neighborData), f);
        }
    }
    if (openList.isEmpty()) return null; // 无可达路径
    // 选择最优节点移动
    currentNode = openList.dequeueMin().getValue();
    // 调用游戏内置移动接口，更新当前站立位置
    s.moveTo(currentNode.getID());
}
// 到达终点返回构建好的路径
return buildPath(resPath);

可选优化点 #

• 如果游戏场景允许回溯，可以删掉封闭列表的校验逻辑，遇到已访问节点只要新g值更小就更新，适合存在死胡同需要回头的场景
• 保证h值计算符合可采纳性（即不会高估到终点的距离），可以确保最终找到的是最短路径

内容的提问来源于stack exchange，提问作者Kevin Weng Jr.