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

我正在制作一个在平铺地图上有坦克战的游戏。如果一个坦克在一个单元格上，那么这个单元格在A *算法中被认为是不可通过的，因此，无论何时单位需要攻击另一个单元格，我需要规划一条将攻击者带入范围的路径（如果range = 1，则next目标）。路径规划接近无法达到的目标

目前，我使用迭代的方法随半径找到附近的一个细胞的路径，并选择其中最小的A-小区-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();

来源

2012-02-04 akarnokd

在您更改算法太多，可以考虑使用更合适的openSet表示（即堆），以及高效decreaseKey。也可以考虑是否可以减少图表的密度 - 改变问题直到它变得更容易解决你可用的时间量。你在做什么听起来很合理 – 2012-02-05 11:08:28

没关系。我通过在闭合集中找到与目标和源的最小距离来解决问题。 – akarnokd 2012-02-06 10:33:57

，似乎工作溶液（将最后返回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给出了两点eucleidian距离。（基本算法使用更简单的函数，对X-X或YY neightbor产生1000，对于XY邻居产生1414）。

来源

2012-03-04 19:37:46 akarnokd

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

回答

相关问题