Как быстро рассчитать площадь прицела в 2D плиточной игре?

У меня есть матрица плиток, на некоторых из которых есть объекты. Я хочу рассчитать, какие плитки видны игроку, а какие нет, и мне нужно сделать это достаточно эффективно (чтобы они вычислялись достаточно быстро, даже когда у меня большие матрицы (100x100) и много объектов).

Я пытался сделать это с помощью алгоритма линии Брезенхэма , но это было медленно. Кроме того, это дало мне некоторые ошибки:

----XXX-        ----X**-     ----XXX-
-@------        -@------     -@------
----XXX-        ----X**-     ----XXX-
(raw version)   (Besenham)   (correct, since tunnel walls are 
                              still visible at distance)

(@ is the player, X is obstacle, * is invisible, - is visible)

Я уверен, что это можно сделать - в конце концов, у нас есть NetHack, Zangband, и все они как-то справились с этой проблемой :)

Какой алгоритм вы можете порекомендовать для этого?

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

Ваше определение видимого следующее:

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

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

1. Укажите уровень точности, который вы хотите придать алгоритму. Это будет количество лучей, которые вы будете отслеживать.
2. Разделите полный круг на 360 градусов на выбранную точность, чтобы узнать, сколько градусов повернуть между каждым лучом.
3. Начиная с 0 градусов и увеличивая на величину, определенную на шаге 2, создайте луч с началом координат в центре плитки игрока и направлением, определенным текущим углом.
4. Для каждого луча, начиная с плитки игрока, идите вдоль направления луча, пока не столкнетесь с плиткой препятствия. Добавьте эту плитку в список видимых плиток и перейдите к следующему лучу. Вы также можете добавить максимальное расстояние, чтобы «сдаться», если столкновение не найдено.

Вот изображение, показывающее 3 примера лучей. Темные цветные плитки являются «результатом» каждого луча, то есть там, где произошло столкновение. Вы должны будете повторить это по всему кругу, хотя:

Настроить максимальное расстояние и количество лучей для производительности. Слишком мало, и вы будете скучать по плиткам, слишком много, и ваша производительность пострадает. Кроме того, чем дальше будут проходить лучи, тем больше будет «ошибка» и тем больше точности вам потребуется.

редактировать

Обратитесь к следующему руководству по лучевому вещанию, в частности к шагу 3 и шагу 4, чтобы помочь вам реализовать бит пересечения алгоритма:

http://www.permadi.com/tutorial/raycast/rayc7.html

Я бы предпочел отбрасывать теневые лучи вместо лучей прямой видимости.

Допустим, это ваша область обзора (потенциально видимая область)

######################
#####.............####
###................###
##..................##
#....................#
#....................#
#..........@.........#
#....................#
#....................#
##..................##
###................###
#####.............####
######################

Блоки # не видны, пока. видны

Давайте поставим некоторое препятствие X:

######################
#####.............####
###................###
##.....X.....XXX....##
#......X.......X.....#
#...X.XX.............#
#...X......@.........#
#...X..........X.....#
#...XXXXXX...........#
##..................##
###....X...........###
#####.............####
######################

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

######################
#####.............####
###................###
##.....X.....XXX....##
#......X.......X.....#
#...X.XX.............#
#...X......@.........#
#...X..........X.....#
#...XXXXX*...........#
##......##..........##
###....*#..........###
#####.###.........####
######################

В приведенном выше примере вы можете видеть тень, отбрасываемую самой правой нижней стенкой, и то, как эта тень удаляет скрытое препятствие из списка препятствий, которые вы должны проверить (X должен проверить; * проверен).

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

Вы можете использовать своего рода алгоритм «Naval Battles» для одновременной проверки блока X (в основном, ищите вспомогательный X, который находится в направлении, которое может сделать конус тени шире)

[РЕДАКТИРОВАТЬ]

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

Координаты луча могут быть вычислены с помощью простого разделения пространства вокруг плитки препятствий:

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

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

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

Если желтая плитка является препятствием, эта плитка становится новой красной плиткой.

Теперь давайте рассмотрим верхний край конуса:

Синие плитки - все возможные кандидаты, чтобы позволить теневому конусу шире: если хотя бы одно из них является препятствием, луч можно перемещать, используя пространство, разделяющее эту плитку, как показано ранее.

Зеленая плитка является кандидатом, только если наблюдатель находится над оранжевой линией, которая следует за:

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

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

Проблема, которую вы пытаетесь решить, иногда называется Field of View, FOV для краткости. Как вы упомянули roguelikes в качестве примеров, вы должны взглянуть на то, что вики RogueBasin говорит о предмете (есть даже ссылки на реализации): http://www.roguebasin.com/index.php?title=Field_of_Vision

Существует довольно много разных алгоритмов с разными плюсами и минусами - очень удобное сравнение доступно также на RogueBasin: http://www.roguebasin.com/index.php?title=Comparative_study_of_field_of_view_algorithms_for_2D_grid_based_worlds

Я также нашел это, у которого есть рабочая демонстрация:

http://www.redblobgames.com/articles/visibility/

Вы можете найти http://blogs.msdn.com/b/ericlippert/archive/2011/12/12/shadowcasting-in-c-part-one.aspx полезными вместе с остальной частью серии .