Что ж, я пытаюсь внедрить A* Pathfinding в простой массив тайловых карт, и у меня есть несколько вопросов.
Для открытого/закрытого списка я должен просто использовать arrayList для хранения всех найденных точек или есть лучший способ их хранения?
Во-вторых, как мне проверить соседей? Нужно ли брать начальную плитку, проверять ту, что сверху, снизу, слева и справа, и сохранять то, что имеет наименьшую стоимость?
Пока вы не реализуете это для игры, то есть видеоигры с высокой частотой кадров, я сомневаюсь, что ваша производительность сильно пострадает при использовании в качестве ArrayList, это должно быть хорошо.
Что касается второй части вашего вопроса, предполагая, что у вас есть только 4 направления подключения для каждого узла, тогда да, простая последовательная проверка каждого соседа будет работать.
Я реализовал это в прошлом с PriorityQueue для открытого списка. Компаратор работает с эвристическим значением A*. Это очень чисто, и вы получите производительность O (log n) на вставку и опрос в худшем случае. Реализации лучше, чем стандартные, могут улучшить опрос до амортизированного O(1). Для списка visited используйте флаги в плитках или отдельный список HashSet. Преимущество последнего заключается в отсутствии затрат на инициализацию и одинаковых асимптотических затратах на вставку и членство. Но постоянные коэффициенты больше для хэша, чем для проверки логических значений карты.
Я не знаю, что такое «массив tilemap», но полагаю, что под «найденными точками» вы подразумеваете узлы в дереве поиска. Структура данных, в которой вы храните узел, который вы еще не исследовали, должна удовлетворять двум важным свойствам, унаследованным от алгоритма Дейкстры:
Первого можно достичь с помощью кучи. Двоичные кучи довольно легко реализовать. Кучи Фибоначчи дают лучшую асимптотическую производительность, но в большинстве приложений не должны быть необходимыми. Большинство куч из библиотек, которые я видел до сих пор, не поддерживают последнее требование, часто называемое клавиша уменьшения. Чтобы реализовать это, ваши узлы должны хранить информацию об их текущей позиции в куче. Таким образом, когда узел меняет свою стоимость, вы можете получить его текущую позицию в O(1) и скорректировать позицию в O(log n). И вы можете использовать эту же переменную, чтобы решить, находится ли элемент в куче или нет.
Теперь о вашем втором вопросе. Обычно вы проверяете стоимость, удаляя минимальный элемент из кучи. Другими словами, для каждого соседа вы либо вставляете его в кучу, либо, если он уже был в куче, вы регулируете его стоимость (и вместе с этим его позицию в куче ), если новая стоимость лучше.
closedобычно хранится как свойство самих узлов. То есть вместо фактического спискаclosedу вас есть логическое свойствоHasBeenVisitedна всех узлах, изначально установленное вfalse. - person BlueRaja - Danny Pflughoeft schedule 03.08.2012