Прямо сейчас я использую линейный алгоритм Брезенхэма для прямой видимости. Проблема в том, что я нашел крайний случай, когда игроки могут смотреть сквозь стены. Происходит, когда игрок смотрит между двумя углами стены с зазором на другой стороне под определенными углами.
В результате я хочу, чтобы плитка между двумя стенами была помечена как недопустимая.
Какой самый быстрый способ изменить линейный алгоритм Брезенхэма, чтобы решить эту проблему? Если нет хорошего решения, есть ли лучший подходящий алгоритм? Любые идеи приветствуются. Обратите внимание, что решение также должно поддерживать 3d.
Редактировать: Моим простым решением было проверить, закрыты ли оба угла при изменении координат x и y линии. Рабочий исходный код и интерактивную демонстрацию готового продукта см. По адресу http://ashblue.github.io/javascript-pathfinding/.
источник
Ответы:
Эрик Липперт написал превосходную серию по созданию прямой видимости в C # с помощью Shadow Casting на прямоугольной плоской сетке.
Среди других вопросов, Эрик имел дело с различными вопросами, на которые необходимо ответить о требованиях к прямой видимости, которые дают разные результаты, и приводит примеры нескольких разных результатов. Одна из статей подробно рассматривает обстоятельства «заглядывания в угол», возникшие в ранней версии его алгоритма.
Я адаптировал алгоритм Эрика к шестиугольной сетке здесь , и успешно использовал его на больших гексагональных сетках (> 400 х 700) с широким радиусом видимости (> 60 гексов). Эта реализация рассчитывает и отображает полное поле обзора так быстро, как я могу моргать, используя один процессор i7. Это, безусловно, достаточно быстро для любых целей, которые я собираюсь использовать.
Обновление - Линия визирования с высотой: реализация
шестигранной сетки, связанная с вышеупомянутой, вычисляет линию визирования с высотой, а не только препятствия. В примечаниях к документации также обсуждается дополнительное решение, которое должно быть принято в отношении расчета высоты: высота цели и высота наблюдателя. Выбор по умолчанию - сделать оба равных, что создает симметричное поле зрения, но можно выбрать и землю, и глаза наблюдателя на землю. (Код с открытым исходным кодом по лицензии MIT)
источник
Что, если для расчета LOS у вас есть отдельная сетка с «более высоким разрешением», которая заполняет угловые промежутки. Я думал что-то вроде этого:
Слева - оригинальный блок из 4 квадратов.
Справа - версия с «высоким разрешением», поскольку вы можете видеть, что каждый исходный квадрат был разделен на четверти, и один из углов был заполнен. Я не уверен, что алгоритм для его генерации был создан вручную, но он может быть предварительно вычислен с текущей карты.
Это означает, что пространство координат увеличено в четыре раза, но я не предполагаю, что это является существенной проблемой производительности.
источник
0.5
для заполненных ячеек с высоким разрешением или нет. Таким образом, использование сетки с высоким разрешением мне кажется довольно хакерским.