A*路径搜索器（Java）在使用1024维多维数组时效率低下。

huangapple
go评论101阅读模式
英文:

A* Path Finder (Java) is inefficient using a 1024 multidimentional array

问题

  1. import java.util.List;
  2. import java.util.ArrayList;
  4. class AStarTwo {
  5.     private final List<Node> openList;
  6.     private final List<Node> closedList;
  7.     private final List<Node> calcPath;
  8.     private final int[][] collisionMap;
  9.     private Node currentNode;
  10.     private final int xstart;
  11.     private final int ystart;
  12.     private int xEnd, yEnd;
  14.     static class Node implements Comparable {
  15.         public Node parent;
  16.         public int x, y;
  17.         public double g;
  18.         public double h;
  19.         Node(Node parent, int xpos, int ypos, double g, double h) {
  20.             this.parent = parent;
  21.             this.x = xpos;
  22.             this.y = ypos;
  23.             this.g = g;
  24.             this.h = h;
  25.         }
  26.         
  27.         @Override
  28.         public int compareTo(Object o) {
  29.             Node that = (Node) o;
  30.             return (int)((this.g + this.h) - (that.g + that.h));
  31.         }
  32.     }
  34.     public AStarTwo(int[][] collisionMap, int xstart, int ystart) {
  35.         this.openList = new ArrayList<>();
  36.         this.closedList = new ArrayList<>();
  37.         this.calcPath = new ArrayList<>();
  38.         this.collisionMap = collisionMap;
  39.         this.currentNode = new Node(null, xstart, ystart, 0, 0);
  40.         this.xstart = xstart;
  41.         this.ystart = ystart;
  42.     }
  44.     public List<Node> findPathTo(int xTo, int yTo) {
  45.         this.xEnd = xTo;
  46.         this.yEnd = yTo;
  47.         this.closedList.add(this.currentNode);
  48.         addNeigborsToOpenList();
  49.         while (this.currentNode.x != this.xEnd || this.currentNode.y != this.yEnd) {
  50.             if (this.openList.isEmpty()) {
  51.                 return null;
  52.             }
  53.             this.currentNode = this.openList.get(0);
  54.             this.openList.remove(0); 
  55.             this.closedList.add(this.currentNode); 
  56.             addNeigborsToOpenList();
  57.         }
  58.         this.calcPath.add(0, this.currentNode);
  59.         while (this.currentNode.x != this.xstart || this.currentNode.y != this.ystart) {
  60.             this.currentNode = this.currentNode.parent;
  61.             this.calcPath.add(0, this.currentNode);
  62.         }
  63.         return this.calcPath;
  64.     }
  66.     private static boolean checkNeighbourHasBeenSearched(List<Node> array, Node node) {
  67.         return array.stream().anyMatch((n) -> (n.x == node.x && n.y == node.y));
  68.     }
  70.     private double distance(int dx, int dy) {
  71.         return Math.hypot(this.currentNode.x + dx - this.xEnd, this.currentNode.y + dy - this.yEnd);
  72.     }
  73.     
  74.     private void addNeigborsToOpenList() {
  75.         Node node;
  76.         for (int x = -1; x <= 1; x++) {
  77.             for (int y = -1; y <= 1; y++) {
  78.                 node = new Node(this.currentNode, this.currentNode.x + x, this.currentNode.y + y, this.currentNode.g, this.distance(x, y));
  79.                 if ((x != 0 || y != 0) 
  80.                     && this.currentNode.x + x >= 0 && this.currentNode.x + x < this.collisionMap[0].length
  81.                     && this.currentNode.y + y >= 0 && this.currentNode.y + y < this.collisionMap.length
  82.                     && this.collisionMap[this.currentNode.y + y][this.currentNode.x + x] != -1) {
  83.                     if (!checkNeighbourHasBeenSearched(this.openList, node) && !checkNeighbourHasBeenSearched(this.closedList, node)) {
  84.                         node.g = node.parent.g + 1.0;
  85.                         node.g += collisionMap[this.currentNode.y + y][this.currentNode.x + x];
  86.                         if (x != 0 && y != 0) {
  87.                             node.g += .4;
  88.                         }
  89.                         this.openList.add(node);
  90.                     }
  91.                 }
  92.             }
  93.         }
  94.     }
  95.     
  96.     public static void main(String[] args) {
  97.         int [][] maze = {
  98.             // maze data here
  99.         };
  100.         
  101.         final int sizeOf = 20;
  102.         int[][] collisionMap = new int[sizeOf][sizeOf];
  103.         
  104.         // Set collision map values here
  105.         
  106.         AStarTwo as = new AStarTwo(maze, 9, 9);
  107.         List<Node> path = as.findPathTo(0,0);
  108.         
  109.         if (path == null) {
  110.             System.out.println("Unable to reach target");
  111.         }
  112.         
  113.         // Output image generation
  114.         
  115.         BufferedImage img = new BufferedImage(sizeOf, sizeOf, BufferedImage.TYPE_INT_RGB);
  116.         
  117.         // Set colors and fill image
  118.         
  119.         File f = new File("aStarPath.png");
  120.         // Save image to file
  121.     }
  122. }
英文:

I have the below code for a A* pathfinder, however it is taking upwards of 10 minutes to find a solution using a simple 1024 x 1024 array.

I had to comment out //Collections.sort(this.openList); as it was throwing a comparison method violates its general contract! error when running.

Is the algorithm correct and any idea why the bottleneck? Some people using C++ are getting a response time of 40ms, not 10+ mins!

When using the maze array it does it in the blink of an eye, but thats using something like a 14x10 array, rather than 1024 from the collisionMap.

Is the method flawed in some way? Or using the wrong data structures?

  1. import java.util.List;
  2. import javax.imageio.ImageIO;
  3. import java.awt.Canvas;
  4. import java.awt.Color;
  5. import java.awt.GraphicsConfiguration;
  6. import java.awt.Paint;
  7. import java.awt.image.BufferedImage;
  8. import java.io.Console;
  9. import java.io.File;
  10. import java.io.IOException;
  11. import java.util.ArrayList;
  12. import java.util.Collection;
  13. import java.util.Collections;
  14. import java.util.Comparator;
  15. class AStarTwo {
  16. // Closed list, open list and calculatedPath lists
  17. private final List&lt;Node&gt; openList;
  18. private final List&lt;Node&gt; closedList;
  19. private final List&lt;Node&gt; calcPath;
  20. // Collision Map to store tha map in
  21. private final int[][] collisionMap;
  22. // Current node the  program is executing
  23. private Node currentNode;
  24. // Define the start and end coords
  25. private final int xstart;
  26. private final int ystart;
  27. private int xEnd, yEnd;
  28. // Node class 
  29. static class Node implements Comparable {
  30. public Node parent;
  31. public int x, y;
  32. public double g;
  33. public double h;
  34. Node(Node parent, int xpos, int ypos, double g, double h) {
  35. this.parent = parent;
  36. this.x = xpos;
  37. this.y = ypos;
  38. this.g = g;
  39. this.h = h;
  40. }
  41. // Compare f value (g + h)
  42. @Override
  43. public int compareTo(Object o) {
  44. Node that = (Node) o;
  45. return (int)((this.g + this.h) - (that.g + that.h));
  46. }
  47. }
  48. // construct and initialise 
  49. public AStarTwo(int[][] collisionMap, int xstart, int ystart) {
  50. this.openList = new ArrayList&lt;&gt;();
  51. this.closedList = new ArrayList&lt;&gt;();
  52. this.calcPath = new ArrayList&lt;&gt;();
  53. this.collisionMap = collisionMap;
  54. this.currentNode = new Node(null, xstart, ystart, 0, 0);
  55. this.xstart = xstart;
  56. this.ystart = ystart;
  57. }
  58. // returns a List&lt;&gt; of nodes to target
  59. public List&lt;Node&gt; findPathTo(int xTo, int yTo) {
  60. this.xEnd = xTo;
  61. this.yEnd = yTo;
  62. // Add this to the closed list
  63. this.closedList.add(this.currentNode);
  64. // Add neighbours to openList for iteration
  65. addNeigborsToOpenList();
  66. // Whilst not at our target
  67. while (this.currentNode.x != this.xEnd || this.currentNode.y != this.yEnd) {
  68. // If nothing in the open list then return with null - handled in error message in main calling func
  69. if (this.openList.isEmpty()) {
  70. return null;
  71. }
  72. // get the lowest f value and add it to the closed list, f calculated when neighbours are sorted
  73. this.currentNode = this.openList.get(0);
  74. this.openList.remove(0); 
  75. this.closedList.add(this.currentNode); 
  76. addNeigborsToOpenList();
  77. }
  78. // add this node to the calculated path
  79. this.calcPath.add(0, this.currentNode);
  80. while (this.currentNode.x != this.xstart || this.currentNode.y != this.ystart) {
  81. this.currentNode = this.currentNode.parent;
  82. this.calcPath.add(0, this.currentNode);
  83. }
  84. return this.calcPath;
  85. }
  86. // Searches the current list for neighbouring nodes returns bool
  87. private static boolean checkNeighbourHasBeenSearched(List&lt;Node&gt; array, Node node) {
  88. return array.stream().anyMatch((n) -&gt; (n.x == node.x &amp;&amp; n.y == node.y));
  89. }
  90. // Calculate distance from current node to the target
  91. private double distance(int dx, int dy) {
  92. return Math.hypot(this.currentNode.x + dx - this.xEnd, this.currentNode.y + dy - this.yEnd); // return hypothenuse
  93. }
  94. // Add neighbouring nodes to the open list to iterate through next
  95. @SuppressWarnings(&quot;unchecked&quot;)
  96. private void addNeigborsToOpenList() {
  97. Node node;
  98. for (int x = -1; x &lt;= 1; x++) {
  99. for (int y = -1; y &lt;= 1; y++) {
  100. node = new Node(this.currentNode, this.currentNode.x + x, this.currentNode.y + y, this.currentNode.g, this.distance(x, y));
  101. // if we are not on the current node
  102. if ((x != 0 || y != 0) 
  103. &amp;&amp; this.currentNode.x + x &gt;= 0 &amp;&amp; this.currentNode.x + x &lt; this.collisionMap[0].length // check collision map boundaries
  104. &amp;&amp; this.currentNode.y + y &gt;= 0 &amp;&amp; this.currentNode.y + y &lt; this.collisionMap.length
  105. &amp;&amp; this.collisionMap[this.currentNode.y + y][this.currentNode.x + x] != -1) { // check if tile is walkable (-1)
  106. // and finally check we haven&#39;t already searched the nodes
  107. if(!checkNeighbourHasBeenSearched(this.openList, node) &amp;&amp; !checkNeighbourHasBeenSearched(this.closedList, node)){
  108. node.g = node.parent.g + 1.; // Horizontal/vertical cost = 1.0
  109. node.g += collisionMap[this.currentNode.y + y][this.currentNode.x + x]; // add movement cost for this square
  110. // Add diagonal movement cost sqrt(hor_cost&#178; + vert_cost&#178;) + 0.4
  111. if (x != 0 &amp;&amp; y != 0) {
  112. node.g += .4;	
  113. }
  114. // Add the node to the List&lt;&gt;
  115. this.openList.add(node);
  116. }
  117. }
  118. }
  119. }
  120. // sort in ascending order
  121. //Collections.sort(this.openList);
  122. }
  123. public static void main(String[] args) {
  124. int [][] maze = 
  125. { {1,1,1,1,1,1,1,1,1,1,1,1,1},
  126. {1,0,-1,0,-1,0,1,0,0,0,0,0,1},
  127. {1,0,-1,0,0,0,1,0,1,1,1,0,1},
  128. {1,0,0,0,-1,-1,-1,0,0,0,0,0,1},
  129. {1,0,1,0,0,0,0,0,1,1,1,0,1},
  130. {1,0,1,0,-1,-1,-1,0,1,0,0,0,-1},
  131. {1,0,-1,0,-1,0,0,0,-1,-1,-1,0,-1},
  132. {1,0,1,0,-1,-1,-1,0,1,0,-1,0,-1},
  133. {1,0,0,0,0,0,0,0,0,0,1,0,1},
  134. {1,1,1,1,1,1,1,1,1,1,1,1,1}
  135. };
  136. // Define the size of the grid
  137. final int sizeOf = 20;
  138. int[][] collisionMap = new int[sizeOf][];
  139. for(int i=0;i &lt; sizeOf; i++) {
  140. // -1 = blocked
  141. // 0+ = cost
  142. collisionMap[i] = new int[sizeOf];
  143. }
  144. // set the value of the nodes
  145. for (int k = 0; k &lt; sizeOf; k++) {
  146. for (int j = 0; j &lt; sizeOf; j++) {
  147. if(j == 30 &amp;&amp; k &lt; 100) {
  148. collisionMap[k][j] = -1;
  149. } else if (j == 50 &amp;&amp; k &gt; 230) {
  150. collisionMap[k][j] = -1;
  151. }else {
  152. collisionMap[k][j] = 0;
  153. }
  154. }
  155. }        
  156. AStarTwo as = new AStarTwo(maze, 9, 9);
  157. List&lt;Node&gt; path = as.findPathTo(0,0);
  158. if(path == null) {
  159. System.out.println(&quot;Unable to reach target&quot;);
  160. }
  161. // create image buffer to write output to
  162. BufferedImage img = new BufferedImage(sizeOf, sizeOf, BufferedImage.TYPE_INT_RGB);
  163. // Set colours
  164. int r = 255;
  165. int g = 0;
  166. int b = 0; 
  167. int colRed = (r &lt;&lt; 16) | (g &lt;&lt; 8) | b;
  168. r = 0;
  169. g = 255;
  170. b = 0; 
  171. int colGreen = (r &lt;&lt; 16) | (g &lt;&lt; 8) | b;
  172. r = 0;
  173. g = 0;
  174. b = 255; 
  175. int colBlue = (r &lt;&lt; 16) | (g &lt;&lt; 8) | b;
  176. r = 255;
  177. g = 255;
  178. b = 255; 
  179. int colWhite = (r &lt;&lt; 16) | (g &lt;&lt; 8) | b;
  180. int i = 0;
  181. int j = 0;
  182. if (path != null) {
  183. path.forEach((n) -&gt; {
  184. System.out.print(&quot;[&quot; + n.x + &quot;, &quot; + n.y + &quot;] &quot;);
  185. maze[n.y][n.x] = 2;
  186. });
  187. for (int[] maze_row : maze) {
  188. for (int maze_entry : maze_row) {
  189. switch (maze_entry) {
  190. // normal tile
  191. case 0:
  192. img.setRGB(j, i, colWhite);
  193. break;
  194. // final path
  195. case 2:
  196. img.setRGB(j, i, colBlue);
  197. break;
  198. // Object to avoid
  199. case -1:
  200. img.setRGB(j, i, colRed);
  201. break;
  202. // Any other value
  203. default:
  204. img.setRGB(j, i, colWhite);
  205. }
  206. j++;
  207. }
  208. // count j - reset as if it were a for loop
  209. if(i != 12) {
  210. j=0;
  211. }
  212. i++;
  213. System.out.println();
  214. }
  215. }
  216. // output file
  217. File f = new File(&quot;aStarPath.png&quot;);
  218. try {
  219. ImageIO.write(img, &quot;PNG&quot;, f);
  220. } catch (IOException e) {
  221. // TODO Auto-generated catch block
  222. e.printStackTrace();
  223. }
  224. System.out.println(&quot;i: &quot; + i + &quot;, j: &quot; + j);
  225. }
  226. }

答案1

得分: 0

我怀疑你的问题出在这一行：

  1. return array.stream().anyMatch((n) -> (n.x == node.x && n.y == node.y));

这一行被调用大约O(n^2)次，并且将花费与数组大小成正比的时间（在最坏情况下，对于一个n乘n的迷宫，数组大小也将是O(n^2)）。

你希望有一个更快的方法来执行这个测试。

例如：

  1. 使用一个集合来保存开放和关闭列表，而不是列表。
  2. 或者在节点结构中使用一个额外的字段来指示它是否在开放或关闭列表中。
英文:

I suspect your problem is this line:

  1. return array.stream().anyMatch((n) -&gt; (n.x == node.x &amp;&amp; n.y == node.y));

which is called around O(n^2) times and will take time proportional to the size of the array (which will also be O(n^2) in the worst case for a n by n maze).

You want a faster method of performing this test.

For example:

  1. Use a set to hold the open and closed lists instead of list
  2. Or use an extra field in the node structure to indicate if it is in the open or closed list

huangapple
  • 本文由 发表于 2020年5月30日 01:10:44
  • 转载请务必保留本文链接：https://go.coder-hub.com/62091245.html
  • a-star
  • algorithm
  • java
  • performance
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定