* Эвристика для создания линий Брезенхэма

Question

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

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

Вот несколько изображений, иллюстрирующих проблему.

Манхэттенское расстояние:

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

Евклидово расстояние:

Лучше, но все же не идеально.Обратите внимание на прямую линию в конце.Диагональ так же легко могла бы остаться диагональю, чего я и хочу.

Что я хочу:

линии Брезенхэманичья к следующему ходу или цели.

Я нашел хороший ресурс здесь, http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html, который касается того, что я ищу, но только кажется, чторабота для рисования линий Брезенхема от начала до цели.Чего я хочу, так это чтобы линии Брезенхама проходили к следующему повороту и вокруг препятствия.

Есть какие-нибудь идеи для хорошего подхода к этой проблеме?

Answer 1

Можете ли вы изменить функцию стоимости на лету так, чтобы стоимость продвижения вперед увеличивалась с накопленной ошибкой?

Идея состоит в том, чтобы в начале алгоритма вычислять DX и DY, как в стандартном Bresenham., (Предположим, что в остальном примере DX> DY> 0. Измените соответственно для других направлений.)

Затем для каждого посещенного соседнего узла отследите ошибку Бреснахама:

if (neighbor.X > this.X) 
   neighbor.err=this.err+DY 
else if (neighbor.Y > this.Y) 
   neighbor.err=this.err-DX

Затем измените свою функцию стоимости в пользу увеличения X, но добавьте if (err >= DX/2) then cost=cost+FACTOR.На карте, где все остальные затраты равны, это должно отслеживать правильную линию.

Другая вещь, которая может вам понадобиться, - это специальная обработка, когда путь обходит препятствие, в противном случае вы можете получить странные пути, следующие за стеной, похожиек примеру "перекрестный продукт с obatacles" в вашей связанной статье.Вы могли бы справиться с этой ситуацией путем пересчета DX и DY, когда соседний узел не находится в направлении + X или + Y.(К сожалению, это, вероятно, требует отслеживания отдельного DX, DY и ошибки для каждого узла, что может быть слишком большой нагрузкой)

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

Answer 2

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

Answer 3

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

Answer 4

Можете ли вы использовать обнаружение столкновений с помощью алгоритма Брезенхэма, возможно, адаптивного Брезенхэма, например, с кривой заполнения пространства?