Поиск пути (волновой)

java
  1. // class Pathfinder
  2. import java.util.Vector;
  3.  
  4. /**
  5.  * @author dzanis
  6.  * @version 1.0
  7.  */
  8. public class Pathfinder {
  9.  
  10.     /**
  11.      * Волновой метод для поиска кратчайшего пути от одной точки к другой, учитывая препятствия на пути
  12.      * @version 1.0
  13.      * @param startX  x стартовой точки
  14.      * @param startY  y стартовой точки
  15.      * @param endX  x конечной точки
  16.      * @param endY  y конечной точки
  17.      * @param map карта,двухмерный массив в котором 0 считается свободной клеткой
  18.      * @return Vector path рассчитанный путь
  19.      */
  20.     public Vector getPath (int startX, int startY, int endX, int endY, int[][] map ) {
  21.         Vector openList = new Vector();
  22.         Vector closeList = new Vector();
  23.         Node startNode = new Node(endX, endY);
  24.         openList.add(startNode);
  25.         while (openList.size() > 0) {
  26.             Node n = (Node) openList.elementAt(0);
  27.             openList.removeElementAt(0);
  28.             closeList.add(n);
  29.             if(n.x == startX && n.y == startY) {
  30.                 Node curr = n;
  31.                 Vector path = new Vector();
  32.                 while(curr != null) {
  33.                     path.add(curr);
  34.                     curr = curr.parent;
  35.                 }
  36.                 return path;
  37.             }
  38.  
  39.             for (int x = n.x - 1; x <= n.x + 1; x++) {
  40.                 for (int y = n.y - 1; y <= n.y + 1; y++) {
  41.                     if (x >= 0 && y >= 0 && x < map[0].length && y < map.length) {
  42.                         if (map[y][x] == 0 && !contains(closeList, x, y) ) {
  43.                             if ( !contains(openList, x, y) ) {
  44.                                 Node neighbor = new Node(x, y);
  45.                                 neighbor.parent = n;
  46.                                 openList.add(neighbor);
  47.                             }
  48.                         }
  49.                     }
  50.                 }
  51.             }
  52.  
  53.         }
  54.         return null;
  55.     }
  56.  
  57.  
  58.     /** Метод проверяет находится ли уже узел с координатами x и y в списке
  59.      * @param list  список
  60.      * @param x
  61.      * @param y
  62.      * @return boolean возвращает true если есть
  63.      */
  64.     boolean contains(Vector list, int x, int y) {
  65.         for (int i = 0; i < list.size(); i++) {
  66.             Node n = (Node) list.get(i);
  67.             if (n.x == x && n.y == y) return true;
  68.         }
  69.         return false;
  70.     }
  71. }
  72.  
  73. // class Node
  74. /**
  75.  * @author dzanis
  76.  * @version 1.0
  77.  * Класс для узла. Каждый узел имеет координаты x и y и его родителя Node parent
  78.  */
  79. public class Node {
  80.     public int x;
  81.     public int y;
  82.     Node parent = null;
  83.  
  84.     Node(int x, int y) {
  85.         this.x = x;
  86.         this.y = y;
  87.     }
  88. }
Пример использования:
  1. Pathfinder pf = new Pathfinder();
  2. Vector path = pf.getPath(0, 0, 10, 10, map);
  3. for (int i = 0; i < path.size(); i++) {
  4.     Node n =  (Node) path.elementAt(i);
  5.     g.drawRect(n.x * 4, n.y * 4, 4, 4);//рисую найденный путь
  6. }

Недостатки:
ищет дольше чем AStar, местами ищет по диагонали, требует больше памяти чем AstarРаботает и на JavaSE, на ней и тестирую. Потом из него буду делать Astar поиск.
Пример и исходник: https://www.dropbox.com/s/y26ttahdoro4u9b/pathfinder-test.jar
Назад

Реклама

Мы в соцсетях

tw tg yt gt