Проблемы с построением алгоритма A *

Question

Я пытаюсь создать приложение, реализующее A *, и у меня возникают проблемы с работой над логикой. Метод здесь принимает 4 ints (startX/Y, goalX/Y), а затем использует алгоритм A *, он будет строить ArrayList и возвращать его, поэтому основной метод может проходить через итерацию и отображать пути A *. Но то, что я получаю, - это сложный путь, который в конечном итоге создает очень толстый путь к узлу цели. Кто-нибудь может определить, где моя ошибка.

Примечание: открытые и закрытые очереди приоритета и инструменты для плитки сопоставимы.

public ArrayList<Tile> findPath(int sX, int sY, int gX, int gY) 
{ 
    ArrayList<Tile> path = new ArrayList<Tile>(); 

    open.offer(gameMap[sX][sY]); 
    Tile currentNode = gameMap[sX][sY]; 
    Tile goalNode = gameMap[gX][gY]; 

    int cX; 
    int cY; 

    while(open.size() > 0){ 
     currentNode = open.poll(); 
     closed.offer(currentNode); 
     path.add(currentNode); 

     cX = currentNode.getX(); 
     cY = currentNode.getY(); 

     if(currentNode == goalNode){ 
      break; 
     } 
     if((cX > 0 && cX < gameMap.length - 1) && (cY > 0 && cY < gameMap.length -1)){ 
      for(int i = -1; i < 2; i++){ 
       for(int j = 1; j > -2; j--){ 
        if(i == 0 && j == 0){} 
        else{ 

         if((gameMap[cX + i][cX + j].type != 1) && !closed.contains(gameMap[cX + i][cX + j])){ 

          if(!open.contains(gameMap[cX + i][cX + j])){ 
           open.offer(gameMap[cX + i][cX + j]); 
           gameMap[cX + i][cX + j].parent = currentNode; 

          } 
         } 
        } 

       } 

      } 

     } 

    } 

    //   while(currentNode != gameMap[sX][sY]){ 
    //    path.push(currentNode); 
    //    currentNode = currentNode.parent; 
    //   } 

    return path; 
} 

Answer 1

Во-первых, я не думаю, что ваш closed набор должен быть приоритетной очереди. Это всего лишь набор узлов, на которые смотрели.

Вам кажется, что отсутствует основная часть работы A *, поэтому я считаю, что этот искатель путей не подходит для вас.

Вот основная идея:

Есть эвристическую функцию, которая угадывает, как далеко назначения. В идеале эта функция будет допустимой, что означает, что она никогда не будет переоценивать расстояние.

Для плиточных сеток это можно сделать, используя расстояние по манхэттену (разность x + y), так как это минимальное расстояние, поэтому оно всегда будет допустимым.

Всякий раз, когда вы берете плитку из открытого списка и добавляете его в закрытый набор, вам необходимо обновить известное значение того, как далеко находятся соседние плитки (сохраняя наименьшее известное значение). Поскольку у вас есть известное значение для плитки, которую вы вкладываете в закрытый набор, вы просто добавляете 1 ко всем известным значениям соседей.

При обновлении этих значений открытый список может сдвинуть порядок (поэтому приоритетная очередь здесь является хорошим выбором). Эвристическое значение, вероятно, останется прежним, но известное значение будет более утонченным.

Как только вы достигнете пункта назначения, у вас будет множество закрытых узлов, все из которых имеют известное расстояние. Затем вы возвращаетесь с места назначения, глядя на каждого соседа, который также находится в закрытом наборе, и выбирая тот, который имеет самое низкое известное расстояние.

С точки зрения реализации этого, вы можете рассмотреть возможность включения класса Tile в другой класс под названием SearchTile или что-то в этом роде. Это может выглядеть следующим образом:

//You may not want to use public variables, depending on your needs 
public class SearchTile implements Comparable<SearchTile> { 
    public final Tile tile; 
    //These need to be updated 
    public int knownDistance = 0; 
    public int heuristicDistance = 0; 

    public SearchTile(final Tile tile) { 
     this.tile = tile; 
    } 

    @Override 
    public int compareTo(final SearchTile other) { 
     if (knownDistance + heuristicDistance > other.knownDistance + other.heuristicDistance) { 
      return 1; 
     } else if (knownDistance + heuristicDistance < other.knownDistance + other.heuristicDistance) { 
      return -1; 
     } else { 
      return 0; 
     } 
    } 
} 

Прохладная вещь A * является то, что в идеальном случае он должен идти прямо к месту назначения. В случаях со стенами это будет наилучшим образом догадываться, и до тех пор, пока эвристика допустима, это придумает оптимальное решение.

Answer 2

Я не полностью вошел в детали вашей реализации, но это приходит в голову, что путь, в котором вы вставляете узлы в ОТКРЫТОГО может быть причиной проблемы:

if(!open.contains(gameMap[cX + i][cX + j])){ 
    open.offer(gameMap[cX + i][cX + j]); 
    gameMap[cX + i][cX + j].parent = currentNode; 
} 

Ваш Цель состоит в том, чтобы избегать повторных элементов в вашем OPEN-списке, но может случиться так, что иногда вам нужно заменить элемент, потому что вы столкнулись с тем, как вы достигаете его с лучшей ценой.В этом случае вам нужно удалить узел, уже вставленный в OPEN, и повторно ввести его с более низкой стоимостью (и, следовательно, с наивысшим приоритетом). Если вы этого не допустите, вы можете генерировать субоптимальные пути, как кажется, в вашем случае.

Дополнительная информация, некоторая логика алгоритма отсутствует. Вы должны сохранить накопленную стоимость с начала, G и приблизительную стоимость цели, H, для каждого создаваемого вами узла. Список OPEN упорядочен по значению G + H, который я не заметил в вашем коде, чтобы сделать это. Во всяком случае, я рекомендую вам взглянуть на некоторые из existing implementation of A*, как один из Hipster4j library, чтобы получить более подробную информацию о том, как это работает.

Надеюсь, мой ответ помог!