Траектория «прямой видимости» через сетку навигации

Я хочу рассчитать линию визирования в сетке навигации.

Рассмотрите изображение ниже, желтая линия - результат только A *, а красная линия - результат алгоритма прямой видимости, который использует желтую линию в качестве входных данных. Теперь юнит может двигаться без «зигзагообразных» действий.

Что такое алгоритм для расчета этой «линии видимости»?

Вы ищете воронкообразный алгоритм.

Вот ты простой

http://digestingduck.blogspot.com.es/2010/03/simple-stupid-funnel-algorithm.html

По сути, алгоритм идентифицирует ребра как порталы и создает воронку, которая проверяется на вершине ребер, чтобы проверить, находятся ли они внутри воронки или нет.

На шаге А воронка строится с начальной позицией, а портал пересекается желтой линией.

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

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

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

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

Статья Gamasutra имеет следующий пример псевдокода:

checkPoint = starting point of path
currentPoint = next point in path
while (currentPoint->next != NULL)
if Walkable(checkPoint, currentPoint->next)
// Make a straight path between those points:
temp = currentPoint
currentPoint = currentPoint->next
delete temp from the path
else
checkPoint = currentPoint
currentPoint = currentPoint->next

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