スターの経路探索|六角形のグリップ

Question

私は初心者です。私はそのような厄介な問題に直面しています。

です。

アルゴリズムが余分な16進数を飲み込んだようです。 誰かが私の間違いを指摘できますか？

だからここでは、コードです：

1.Pathfinding funcを（1に表示され、2 '障害' が設定されている 'OB'）：

private static Node pathFinding(Vector2i startHex, Vector2i goalHex, HashSet<Vector2i> ob, int movesLeft) { 
    start = new Node(startHex); 
    goal = new Node(goalHex); 

    if (distance(start, goal) > movesLeft) return null; 

    TreeSet<Node> openSet = new TreeSet<>(new NodeComparator()); 
    HashSet<Node> closedSet = new HashSet<>(); 

    start.cameFrom = null; 
    start.g = 0; 
    start.h = distance(start, goal); 
    start.f = start.g + start.h; 
    openSet.add(start); 

    float tentativeScore; 

    while (!openSet.isEmpty()) { 
     current = openSet.pollFirst(); 
     if (current.coords.equals(goal.coords)) { 
      return current; 
     } 
     closedSet.add(current); 
     for (Node node : getNeighbors(current, ob)) { 
      node.g = distance(start, node); 
      tentativeScore = current.g + distance(current, node); 

      if (!closedSet.contains(node) || tentativeScore < node.g) { 
       node.g = tentativeScore; 
       node.h = distance(node, goal); 
       node.f = node.g + node.h; 
       node.cameFrom = current; 
       openSet.add(node); 
      } 
     } 
    } 
    return null; 
} 

2.Neighbors ：

private static final Vector2i[] directions2i = { 
     new Vector2i(0,-1), new Vector2i(1,-1), new Vector2i(1,0), 
     new Vector2i(0,1), new Vector2i(-1,1), new Vector2i(-1,0) 
}; 

private static List<Node> getNeighbors(Node origin, HashSet<Vector2i> ob) { 
    List<Node> list = new ArrayList<>(); 
    for (int i = 0; i < 6; i++) { 
     Vector2i dir = new Vector2i(origin.coords.x + directions2i[i].x, origin.coords.y + directions2i[i].y); 
     if (!ob.contains(dir)) 
      list.add(new Node(dir)); 
    } 
    return list; 
} 

3.Heuristic：

static float distance(Node a, Node b) { 
    return (Math.abs(a.coords.x - b.coords.x) + Math.abs(a.coords.y - b.coords.y) + Math.abs(a.coords.x +a.coords.y -b.coords.x -b.coords.y))/2; 
} 

4.And念のために、ここでノードと比較するクラスです：

public class Node { 
public Node cameFrom; 
public Vector2i coords; 
float g, h, f; 

@Override 
public int hashCode() { 
    return coords.x * 100000 + coords.y; 
} 

@Override 
public boolean equals(Object o) { 
    if (this == o) return true; 
    if (getClass() != o.getClass()) return false; 
    Node oth = (Node) o; 
    return this.coords.equals(oth.coords); 
} 

Node(Vector2i coords) { 
    this.coords = new Vector2i(coords); 
} 
} 

private static class NodeComparator implements Comparator<Node> { 
    @Override 
    public int compare(Node o1, Node o2) { 
     return Float.compare(o1.f, o2.f); 
    } 
} 

Answer 1

TreeSetは、この使用には適していません。これはコンパレータ（equalsの実装を無視）の観点から定義されていますが、Openセットで同じFスコアを持つ複数のノード（実際にそこにある必要があります）を持つことは可能です。これは、そこにあったはずのノードの喪失と重複の無意味な存在の両方を引き起こす。

ノードを挿入する前にそれを削除するのは実際の解決策ではありません。ちょっと速くハックすると、（明らかに）時間がかかることがあります。その提案を許容可能な解決策と見なすべきではなく、基本的な変更を適用する必要があります。

一般的に言及されているアプローチは、リンクされた優先順位キューとハッシュマップを維持することです。優先順位キューは、指定された座標を持つノードがキュー内で発生する場所を追跡するためにハッシュマップを更新します。これにより、オープンセットを「contains」にすばやく照会（ハッシュマップ）し、指定された座標のノードをすぐにキューから削除し（ハッシュマップし、キューに指定したインデックスのノードを削除するよう指示します） （通常通り）Fスコアが最も低いノードに送信する。

この配列は、キューがハッシュマップについて知り、それを更新する必要があるため、組み込みの順序付きコンテナでは実行できません。幸運なことに、バイナリヒープはそれを実装するのが難しくありませんし、すでに実行されているので、既存の実装を借りることができるかもしれません。