A * проблема столкновения препятствий следопыта

Question

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

Проблема заключается в том, что робот иобъект, который должен поднять робот, имеет ширину в один пиксель в поисковике пути.На самом деле они намного больше.Часто следопыт A * выбирает путь вдоль краев препятствий, иногда заставляя его сталкиваться с ними, что нам и не нужно делать.

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

Есть ли у вас какие-либо предложения относительно того, что делать с этой проблемой??

Редактировать:

Итак, я сделал так, как предложил Джастин Л., добавив много затрат вокруг препятствий, что приводит к фоллингу: Сетка без пути http://sogaard.us/uploades/1_grid_no_path.png

Здесь вы можете увидеть стоимость вокруг препятствий, первоначально средние два препятствия должны выглядеть точно так же, как и в углах, но после запуска нашего поискового указателя кажется, что затраты переопределены:

Сетка с путемhttp://sogaard.us/uploades/1_map_grid.png

Изображение, которое показывает вещи, найденные на картинке http://sogaard.us/uploades/2_complete_map.png

Изображение выше показывает, что вещи найдены на картинке.

Путь найден http://sogaard.us/uploades/3_path.png

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

Сетка ранее с путем на http://sogaard.us/uploades/4_mg_path.png

И еще одна картинка с картой стоимостис путем.

Так что я нахожу странным, почему указатель пути A * переопределяет эти затраты на поле, которые ОЧЕНЬ высоки.

Было бы, когда он оценивает узлы внутри открытогосписок с текущим полем, чтобы увидеть, является ли путь к текущему полю короче, чем путь в открытом списке?

А вот код, который я использую для pathfinder:

Pathfinder.cs:http://pastebin.org/343774

Field.cs и Grid.cs: http://pastebin.org/343775

Answer 1

Рассматривали ли вы добавление стоимости градиента к пикселям возле объектов?

Возможно, такой же простой, как линейный градиент:

C = -mx + b

Где x - расстояние до ближайшего объекта, b - стоимость прямо за границей, а m - скорость, с которой стоимость исчезает. Конечно, если C отрицателен, он должен быть установлен в 0.

Возможно, простой гиперболический распад

C = b/x

, где b - желаемая стоимость прямо за границей, опять же. Сделайте отсечение до 0, как только оно достигнет определенной нижней точки.

В качестве альтернативы, вы можете использовать экспоненциальный спад

C = k e^(-hx)

Где k - постоянная масштабирования, а h - скорость затухания. Опять же, умение обрезать - разумно.

---

Второе предложение

Я никогда не применял A * к карте с отображением пикселей; почти всегда, плитка.

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

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

Answer 2

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

Answer 3

Я сделал один такой физический робот. Мое решение состояло в том, чтобы двигаться на один шаг назад, когда есть левый и правый поворот.

альтернативный текст http://www.freeimagehosting.net/uploads/bb41eb3ba5.png

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