Почему поиск пути A* иногда идет по прямой, а иногда по диагонали? (Ява)

Если вы ищете простое решение, могу я предложить немного рандомизации?

Я имею в виду следующее: в примере кода cokeandcode есть вложенные циклы for, которые генерируют «состояния преемника» (используя термин AI). Я имею в виду точку, где он зацикливается на квадрате 3x3 вокруг «текущего» состояния, добавляя новые места в кучу для рассмотрения.

Относительно простое исправление будет (должно :)) немного изолировать этот код и, скажем, сгенерировать связанный список узлов до остальной части этапа обработки. Затем Containers.Shuffle (или это Generics.Shuffle?) этого связанного списка и продолжайте обработку там. По сути, есть процедура, скажем, "createNaiveNeighbors(node)", которая возвращает LinkedList = {(node.x-1,node.y), (node.x, node.y-1)... } (пожалуйста, извините за pidgin Java, я пытаюсь (и всегда терплю неудачу) быть кратким.

Однако после того, как вы создадите связанный список, вы сможете просто выполнить «for (Node n : myNewLinkedList)» вместо

for (int x=-1;x<2;x++) {

    for (int y=-1;y<2;y++) {

И по-прежнему используйте тот же самый код тела!

В идеале это должно было бы как бы «встряхнуть» порядок рассматриваемых узлов и создать пути ближе к диагонали, но без изменения эвристики. Пути по-прежнему будут наиболее эффективными, но обычно ближе к диагонали.

Недостатком, конечно, является то, что если вы идете от А к Б несколько раз, вы можете выбрать другой путь. Если это неприемлемо, вам, возможно, придется рассмотреть более радикальное изменение.

Надеюсь это поможет! -Агор

Оба пути имеют одинаковую длину, поэтому алгоритм отлично справляется со своей задачей — находит кратчайший путь. Однако алгоритм A* не указывает, КАКОЙ кратчайший путь он выберет. Реализации обычно выбирают "первый" кратчайший путь. Не видя вашего, невозможно точно знать, почему, но если вы хотите получать одни и те же результаты каждый раз, вам придется добавить какие-то правила приоритета (чтобы желаемый путь был первым в поиске).

Причина этого на самом деле довольно проста: путь всегда будет пытаться иметь наименьшую возможную эвристику, потому что он выполняет поиск жадным образом. Приближение к цели – оптимальный путь.

Если бы вы позволили диагональное движение, этого бы не произошло.

Причина в пути, по которому должен идти алгоритм.
Я не знаю эвристики, которую использует ваш A*, но в первом случае он должен сначала пройти до конца туннеля, а затем проложить путь с конца. тоннеля к цели.

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

Большинство A*, которые я знаю, работают с эвристикой линии прямой видимости или Манхэттенское расстояние в случае блочный мир. Эта эвристика дает вам кратчайший путь, но в случае препятствий, вынуждающих идти по пути, отличному от прямой видимости, пути зависят от вашей начальной точки.
Алгоритм будет идти по линии прямой видимости как можно дольше.

Наиболее вероятным ответом будет то, что если идти прямо на юг, то он сначала приблизится к своей цели; Идя в обратном направлении, это не выбор, поэтому он оптимизирует подпуть кусочно, в результате чего чередующиеся движения вверх / поперек рассматриваются как наилучшие.

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

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

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

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

Если я видел правильно, то сфера движется сначала вправо по прямой, потому что она не может попасть прямо к цели (путь перекрыт). Затем он идет по прямой линии к цели. Это только кажется диагональным.

Ваш поиск смотрит сначала в направлении «вниз»? Это может объяснить алгоритм. Попробуйте изменить его, чтобы сначала искать «вверх», и я уверен, вы увидите противоположное поведение.

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

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

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

Я бы предложил просмотреть мой вопрос, так как он может дать некоторые идеи и решения этой проблемы.