* Pathfinding非常に遅い

Question

私はアンドロイドのための経路探索アルゴリズムを書いた。それは非常にゆっくりと実行されているようだと私は理由を把握することはできません。前にも同様の質問をしましたが、私が探していた答えが得られませんでした。クラスパスを見つけるパスは次のとおりです。

public class Pathfinding { 

    private static Node[][] grid; 

    private static NodeComparator nodeComparator; 

    static{ 
     nodeComparator = new NodeComparator(); 
    } 

    public static class NodeComparator implements Comparator<Node> { 

     @Override 
     public int compare(Node node1, Node node2) { 

      if(node1.F > node2.F){ 
       return 1; 
      } 
      else if(node1.F < node2.F){ 
       return -1; 
      } 
      else{ 
       return 0; 
      } 

     } 
    } 

    public static Array<Node> findPath(Node start, Node finish, Node[][] _grid) { 

     Array<Node> path = new Array<Node>(); 
     Array<Node> openList = new Array<Node>(); 
     Array<Node> closedList = new Array<Node>(); 

     grid = _grid; 

     if(start == null){ 

      return path; 
     } 
     if(finish == null){ 

      return path; 
     } 

     Node currentNode = start; 
     currentNode.G = 0; 
     currentNode.H = getHeuristic(currentNode, finish); 
     currentNode.parent = null; 
     openList.add(currentNode); 

     System.out.println("PATHFINDING STARTED ||| startPos : " + start.position + " finishPos : " + finish.position); 

     while (openList.size > 0) { 

      //Sorts open nodes lowest F value to heighest 
      openList.sort(nodeComparator); 

      currentNode = openList.first(); 

      //If path is found, return 
      if (currentNode == finish) { 
       System.out.println("PATH FOUND...RETURNING -gat5"); 

       return constructPath(currentNode); 
      } 

      openList.removeValue(currentNode, true); 
      closedList.add(currentNode); 

      int counter = 0; 
      for (Node neighbor : getNeighbors(currentNode)) { 
       if (!closedList.contains(neighbor, true)) { //If neighbor not in closed list 
        if(neighbor != null) { //If neighbor not wall 

         if(counter == 4){ 
          counter++; 
         } 

         int movementCost = checkMovementCost(counter); 

         if (openList.contains(neighbor, true)) { 
          if (currentNode.G + movementCost < neighbor.G) { 
           neighbor.parent = currentNode; 
          } 
         } else { 
          openList.add(neighbor); 
          neighbor.parent = currentNode; 
          neighbor.H = getHeuristic(currentNode, finish); 
          neighbor.G = neighbor.parent.G + movementCost; 
         } 
         counter++; 
        } 
       } 
      } 

      System.out.println(counter); 

     } 

     System.out.println("NO FINAL"); 
     System.out.println("NO PATH FOUND RETURNING..."); 
     path.add(start); 
     return path; 

    } 

    private static int checkMovementCost(int neighbor) { 
     int movementCost = 0; 
     switch (neighbor) { 
      //Diagonal 
      case 0: 
      case 2: 
      case 6: 
      case 8: 
       movementCost = 16; 
       break; 
      //Not Diagonal 
      case 1: 
      case 3: 
      case 5: 
      case 7: 
       movementCost = 10; 
       break; 
     } 

     return movementCost; 
    } 

    public static Array<Node> constructPath(Node finish) { 
     Array<Node> pathNodes = new Array<Node>(); 

     Node currentNode = finish; 
     pathNodes.add(currentNode); 

     while (currentNode.parent != null) { 
      currentNode = currentNode.parent; 
      pathNodes.add(currentNode); 
     } 

     return pathNodes; 
    } 

    private static float getHeuristic(Node start, Node finish){ 
     int H = 0; 

     H += Math.abs(start.position.x - finish.position.x); 
     H += Math.abs(start.position.y - finish.position.y); 

     return H; 
    } 

    private static Array<Node> getNeighbors(Node node){ 
     Array<Node> neighbors = new Array<Node>(); 

     int x = (int)node.position.x; 
     int y = (int)node.position.y; 

     if(x - 1 > 0 && x - 1 < grid.length && y + 1 < grid.length && y + 1 > 0){ 
      neighbors.add(grid[x - 1][y + 1]); 
     } 
     else{ 
      neighbors.add(null); 
     } 
     if(x > 0 && x < grid.length && y + 1 < grid.length && y + 1 > 0){ 
      neighbors.add(grid[x][y + 1]); 
     } 
     else{ 
      neighbors.add(null); 
     } 
     if(x + 1 > 0 && x + 1 < grid.length && y + 1 < grid.length && y + 1 > 0){ 
      neighbors.add(grid[x + 1][y + 1]); 
     } 
     else{ 
      neighbors.add(null); 
     } 


     if(x - 1 > 0 && x - 1 < grid.length && y < grid.length && y > 0){ 
      neighbors.add(grid[x - 1][y]); 
     } 
     else{ 
      neighbors.add(null); 
     } 
     if(x > 0 && x < grid.length && y < grid.length && y > 0){ 
      neighbors.add(grid[x][y]); 
     } 
     else{ 
      neighbors.add(null); 
     } 
     if(x + 1 > 0 && x + 1 < grid.length && y < grid.length && y > 0){ 
      neighbors.add(grid[x + 1][y]); 
     } 
     else{ 
      neighbors.add(null); 
     } 


     if(x - 1 > 0 && x - 1 < grid.length && y - 1 < grid.length && y - 1> 0){ 
      neighbors.add(grid[x - 1][y - 1]); 
     } 
     else{ 
      neighbors.add(null); 
     } 
     if(x > 0 && x < grid.length && y - 1 < grid.length && y - 1 > 0){ 
      neighbors.add(grid[x][y - 1]); 
     } 
     else{ 
      neighbors.add(null); 
     } 
     if(x + 1 > 0 && x + 1 < grid.length && y - 1 < grid.length && y - 1 > 0){ 
      neighbors.add(grid[x + 1][y - 1]); 
     } 
     else{ 
      neighbors.add(null); 
     } 

     return neighbors; 

    } 

} 

ありがとうございました！

**さらに詳しい情報：**このアルゴリズムを1回だけ実行すると正常に動作します。しかし、3回以上実行すると、フレームレートが速く失われます。私のグリッドは200x200です。

Answer 1

パスの評価があなたが指摘しているほど簡単な場合、おそらくアルゴリズムの遅さは、アルゴリズムの各反復で行う順序と何か関係があります。

ただ、はるかに効率的な実装では、アルゴリズムの結果によって拡張するノードを注文する PriorityQueueを使用して

 //Sorts open nodes lowest F value to heighest 
     openList.sort(nodeComparator); 

。必要ならば、ライブラリhipster4jに実装された実装の詳細the A* algorithmを見てください。これはAndroidでも動作します。

私の回答が役に立ちます。