Как сделать естественно выглядящие пути с A * на сетке?

Я читал это: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

Но есть некоторые вещи, которые я не понимаю, например, в статье сказано использовать что-то вроде этого для поиска пути с диагональным движением:

function heuristic(node) =
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    return D * max(dx, dy)

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

Это моя эвристическая функция и функция перемещения:

def heuristic(self, node, goal):
    D = 5
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    return D * max(dx, dy)

def move_cost(self, current, node):
   cross = abs(current.x - node.x) == 1 and abs(current.y - node.y) == 1
   return 7 if cross else 5

Результат:

Плавный путь плавания, который мы хотим осуществить:

Остальная часть моего кода: http://pastebin.com/TL2cEkeX

Обновить

Это лучшее решение, которое я нашел до сих пор:

def heuristic(node, start, goal):
    dx1 = node.x - goal.x
    dy1 = node.y - goal.y
    dx2 = start.x - goal.x
    dy2 = start.y - goal.y
    cross = abs(dx1*dy2 - dx2*dy1)

    dx3 = abs(dx1)
    dy3 = abs(dy1)

    return 5 + (cross*0.01) * (dx3+dy3) + (sqrt(2)-2) * min(dx3, dy3)

def move_cost(current, node):
    cross = abs(current.x - node.x) == 1 and abs(current.y - node.y) == 1
    return 7 if cross else 5

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

Какие уловки и оптимизации я могу применить, чтобы улучшить его?

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

Я думаю, что вы хотите, либо:

1. Вам нужно двигаться по сетке, но вы хотите смешать осевые и диагональные шаги, чтобы она выглядела лучше. Один из подходов состоит в том, чтобы выбрать один из других одинаково коротких путей; продолжайте читать эту страницу эвристики, чтобы найти «разрыв связи». Другой подход заключается в том, что, когда вы оцениваете соседей, выбирайте случайным образом, какой из них оценивать первым, чтобы он не всегда выбирал один перед другим. Я не рекомендую использовать евклидово-декартово расстояние, если вы хотите двигаться по сетке; это несоответствие, которое заставляет A * работать медленнее.
2. Вам не нужно двигаться по сетке, и вы хотите двигаться по прямой линии. Один из подходов состоит в том, чтобы выправить пути, используя «натяжение струн». Вы ищете места, где путь поворачивает, и рисуете прямые линии между этими точками. Другой подход заключается в применении этого к самому основному графу. Вместо поиска пути в сетке, найдите путь в ключевых точках на карте, а затем двигайтесь вдоль прямых линий между этими ключевыми точками. Вы можете увидеть пример здесь . Еще один подход - алгоритм Тета * .

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

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

Хорошая формула может быть:

cost = normal_cost * (1.1 - 0.1 / num_of_steps_in_the_same_direction)

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

Адаптация *

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

Кажется, легко адаптировать A * для вычисления «всех» оптимальных путей (с наименьшей длиной), а затем выбрать один из них с помощью другой эвристики. Но существует проблема. Если у вас длинный путь, может быть много решений с оптимальной длиной. Это приводит к тому, что алгоритму A * требуется гораздо больше времени для вычисления всех этих других решений. Это потому что сетка. Вы не можете пройти 80 градусов вместо 90 градусов, что приводит к нескольким субоптимальным решениям вместо одного оптимального решения. Для воображения представьте карту без препятствий. Расстояние по x равно 2, расстояние по y равно 3. Это означает, что все кратчайшие пути имеют 2 диагональных хода и 1 прямой ход. Для этого простого пути есть 3 допустимые комбинации: SDD, DSD, DDS (где D = диагональ, S = прямая). Настоящее «веселье» начинается уже тогда, когда у вас есть пути, например, с 3 прямых и 2 диагональных хода: SSSDD, SSDSD, SSDDS, SDSSD, SDSDS, SDDSS, DSSSD, DSSDS, DSDSS, DDSSS (10 вариантов кратчайшего пути, если я не пропустил ни одного). Я думаю, у тебя должна была быть идея ...

Таким образом, мы должны исправить это путем адаптации функции стоимости таким образом, чтобы меньшее количество решений (или даже только одно решение) было «оптимальным».

Адаптация функции стоимости

Выполнение адаптации, как предлагает Филипп в своей формуле примера, даст вам гораздо лучшие результаты, но все еще имеет некоторые проблемы. Он не будет равномерно распределять более короткие / более длинные «части» вдоль пути, что означает: изменение направления будет происходить чаще в начале пути или наоборот.

Кроме того, путь с бесконечным побуждением актера к «повороту» кажется неоптимальным, когда его наблюдает человек. Поскольку на это требуется время (чтобы показать анимацию поворота) и, следовательно, оно должно быть медленнее.

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