Упрощённый алгоритм линии взгляда

Материал из Клуб любителей рогаликов
Перейти к: навигация, поиск

LOS (Line of Sight) - линия взгляда

Не обращали ли вы внимание, что большинство ваших подземелий просто связка комнат и коридоров, соединённых между собой дверными проёмами размером в одну ячейку?

Обычно, это что-то вроде этого:

########          
#......#         #########
#......###########.......#
#......'.........'.......#
#......#####'#####.......#
####+###   #.#   ###'#####
 #....#    #.#####.....#
 #....#    #.....+.....#
 #....#    #######.....#
 ######          #######

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

Вы можете использовать для таких уровней некоторые чрезвычайно упрощённые алгоритмы LOS, если Вы сохраняете взаиное расположение комнат и дверей, все ваши комнаты выпуклые, ваши коридоры разделяются на прямые части и все ваши двери шириной в 1 ячейку. Результаты не вполне совершенны, но если Вы используете...

Прежде всего, проверьте расстояние между игроком и объектом. Если оно больше, чем максимальная дальность обзора - цель не видна. Если Вы используете восьмиугольную метрику (показатель), этот расчёт должен быть довольно быстрым.

Теперь, определите, в какой комнате находятся игрок и поле с объектом. Если они в той же комнате, цель видна. Если игрок или монстр стоят во входном проёме, считается, что они стоят в обеих комнатах, разделённых проёмом.

Это то, что надо, если Вам необходимо автозакрывание дверей. Но, кто такого захочет? ^^))

Итак, теперь Вы должны проверить, связаны ли комнаты какими-нибудь проёмами. Если нет, цель не может быть видна (это не очень хорошо, подробнее об этом - позже). Если есть такой проём, Вы должны проверить виден ли объект через этот проём. Возможно, потребуется проверить более чем один проём.

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

1) Игрок, проём и объект на одной высоте.

.....#.....
.....#.....
.@...'...x.
.....#.....
.....#.....

Вычислений не требуется, объект виден всегда.

2) Игрок и объект на одной стороне от проёма.

.@...#.....
.....#..x..
.....'.....
.....#.....
.....#.....

.....#.....
.....#.....
.....'.....
.....#..x..
.@...#.....
.....#.....

Вычислений не требуется, объект не виден никогда.

3) Игрок на одной высоте с проёмом.

.....#.....
.....#.....
.@...'.....
.....#.....
.....#.x...

.....#.....
.....#.....
...@.'.....
.....#....x
.....#.....

Вам нужно вычислить наклон линий, идущих от игрока до сторон проёма, и от сторон проёма до объекта. Выберите правые углы ячеек, особенно если Вы хотите поворачиваться вокруг угла. Сравните наклоны, чтобы определить видимость цели. Если всё сделано правильно, Вы можете сделать это, используя несколько сложений и два перемножения с целыми переменными. Точные формулы оставлены для читателя как упражнение ^^)))

4) Игрок и объект по разные стороны от проёма.

.....#.....
@....#.....
.....'.....
.....#.....
.....#.x...

...@.#.....
.....#.....
.....'.....
.....#....x
.....#.....

...@.#.....
.....#.....
.....'.....
.....#.x...
.....#.....

Здесь Вы всё делаете, в основном, так же как и в предыдущем случае, но Вы должны тщательно выбирать углы в зависимости от того, кто ближе к проёму - объект или игрок. Для некоторых углов линий игрок-проём Вам не нужно вычислять линии объект-проём, потому что игрок не может увидеть что-нибудь через проём.

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

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

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

        ####
####### #.x#
#.....###..#
#.....'.'..#
#.....######
#.@...#
#.....#
#######

Если Вы не можете не отображать всё FOV (поле обзора), никто в действительности не обратит внимания ^^))). И Вы можете исправить этот баг, вспомнив углы наклонов от первого проёма и взяв минимум (максимум).

Вы можете использовать этот алгоритм даже если некоторые из ваших комнат являются пещерами и не обязательно выпуклые - Вам просто нужен флаг IS_COVEX для каждой комнаты, и немного другой алгоритм LOS/FOV для комнат без этого флага. Да, да, это ещё более сложные вещи, но если Вам действительно нужно немного скорости...

Кроме того, любой поиск пути тоже очень прост - Вы используете Dijkstra, или A*, или что-нибудь ещё на графе комнат, а в комнате - прямую линию если у неё установле флаг IS_CONVEX и снова некоторый A* если нет.



Автор: Radomir Dopieralski.
Источник: Extremely fast simplified LOS.
Перевел: Дмитрий О. Бужинский [Bu], 03.10.2005.