路径规划以接近无法到达的目标

Question

我正在开发一款在平铺地图上有坦克战斗的游戏。如果坦克在一个单元上，那么这个单元在A*算法中被认为是不能通过的，因此，每当一个单元需要攻击另一个单元时，我需要规划一条将攻击者带到范围内的路径(如果是range=1，则紧挨着目标)。

目前，我使用一种递增半径的迭代方法来找到到附近单元的路径，并选择一个最小化A- cell -B距离的单元。不幸的是，这对于一个单元来说是慢的，更不用说对于50个单元了。

有没有办法从常规的A*搜索数据结构中提取部分路径？

仅供参考，以下是我的实现。

Set<T> closedSet = U.newHashSet();
Map<T, T> cameFrom = U.newHashMap();
final Map<T, Integer> gScore = U.newHashMap();
final Map<T, Integer> hScore = U.newHashMap();
final Map<T, Integer> fScore = U.newHashMap();
final Comparator<T> smallestF = new Comparator<T>() {
    @Override
    public int compare(T o1, T o2) {
        int g1 = fScore.get(o1);
        int g2 = fScore.get(o2);
        return g1 < g2 ? -1 : (g1 > g2 ? 1 : 0);
    }
};
Set<T> openSet2 = U.newHashSet();
List<T> openSet = U.newArrayList();
gScore.put(initial, 0);
hScore.put(initial, estimation.invoke(initial, destination));
fScore.put(initial, gScore.get(initial) + hScore.get(initial));
openSet.add(initial);
openSet2.add(initial);
while (!openSet.isEmpty()) {
    T current = openSet.get(0);
    if (current.equals(destination)) {
        return reconstructPath(cameFrom, destination);
    }
    openSet.remove(0);
    openSet2.remove(current);
    closedSet.add(current);
    for (T loc : neighbors.invoke(current)) {
        if (!closedSet.contains(loc)) {
            int tentativeScore = gScore.get(current)
             + distance.invoke(current, loc);
            if (!openSet2.contains(loc)) {
                cameFrom.put(loc, current);
                gScore.put(loc, tentativeScore);
                hScore.put(loc, estimation.invoke(loc, destination));
                fScore.put(loc, gScore.get(loc) + hScore.get(loc));
                openSet.add(loc);
                Collections.sort(openSet, smallestF);
                openSet2.add(loc);
            } else
            if (tentativeScore < gScore.get(loc)) {
                cameFrom.put(loc, current);
                gScore.put(loc, tentativeScore);
                hScore.put(loc, estimation.invoke(loc, destination));
                fScore.put(loc, gScore.get(loc) + hScore.get(loc));
                Collections.sort(openSet, smallestF);
            }
        }
    }
}
return Collections.emptyList();

Answer 1

一个似乎有效的解决方案(替换最后返回的Collections.emptyList();)：

    // if we get here, there was no direct path available
    // find a target location which minimizes initial-L-destination

    if (closedSet.isEmpty()) {
        return Pair.of(false, Collections.<T>emptyList());
    }
    T nearest = Collections.min(closedSet, new Comparator<T>() {
        @Override
        public int compare(T o1, T o2) {
            int d1 = trueDistance.invoke(destination, o1);
            int d2 = trueDistance.invoke(destination, o2);
            int c = U.compare(d1, d2);
            if (c == 0) {
                d1 = trueDistance.invoke(initial, o1);
                d2 = trueDistance.invoke(initial, o2);
                c = U.compare(d1, d2);
            }
            return c;
        }
    });
    return Pair.of(true, reconstructPath(cameFrom, nearest));

其中trueDistance给出了两个点的原子核距离。(基本算法使用一个更简单的函数，对于X-X或YY邻居产生1000，对于XY邻居产生1414 )。