FOV и карта на графах

Темы, связанные с проектированием и программированием roguelike-игр

Модераторы: Sanja, Максим Кич

Ответить
Аватара пользователя
Максим Кич
Администратор
Сообщения: 1642
Зарегистрирован: 03 дек 2006, 20:17
Откуда: Витебск, Беларусь
Контактная информация:

FOV и карта на графах

Сообщение Максим Кич » 10 ноя 2019, 18:41

Итак, я это сделал, на уровне «proof-of-concept».

Изначальная идея:

FOV: Мы строим граф из всех путей, которые проходят линии видимости от центра к периметру поля зрения. Каждая вершина графа соответствует некоей целочисленной клетке в поле зрения, а рёбра графа прокладываются по исходя из того, как проходила бы линия по алгоритму Брезенхема. В итоге, получается дерево, с центральной вершиной, соответствующей началу координат.

Для поля глубиной 1, граф будет выглядеть следующим образом:
tree1.png
tree1.png (1.45 КБ) 2820 просмотров
Для поля глубиной 2:
tree2.png
tree2.png (1.9 КБ) 2820 просмотров
Для поля глубиной 10:
tree3.png
tree3.png (11.08 КБ) 2820 просмотров
Здесь можно заметить, что в одну клетку входит более одной линии видимости. По факту, в таких случаях создаются новые вершины, соответствующие тем же координатам. В противном случае, видимость будет «расползаться» далеко за пределы ожидаемых границ.

Карта:
Мы строим карту из элементов, связанных с восемью соседними элементами.
tree1.png
tree1.png (1.45 КБ) 2820 просмотров
Тогда прямоугольная карта 4×6 будет представлять собой следующий граф:
map.png
map.png (2.81 КБ) 2820 просмотров
Отрисовка карты осуществляется следующим образом: мы выбираем некоторый центральный элемент и начиная от него начинаем обход графа видимости, проверяя прозрачность клеток карты, соответствующих вершинам графа видимости. Прозрачные клетки мы отрисовываем с соответствующим смещением и продолжаем обход. Непрозрачная клетка также отрисовывается и на ней обход данной ветки завершается.

Недостатки метода:
1. Излишняя жадность. Игрок может видеть, что находится за одинарными колоннами.
2. Не до конца просматриваемые стены вертикальных и горизонтальных коридоров. Это можно решить отрисовкой всех смежных непрозрачных клеток по пути следования линии видимости.
3. Сложность генерации карты, по сравнению с классическим представлением. Решается разработкой соответствующих вспомогательных процедур.
4. Граф занимает определённое место в памяти (глубина в 150 радостно отожрала 2Гб оперативной памяти. Но на практике достаточно глубины в 15-20, что не требует значительного объёма)

Достоинства метода:
1. Дешёвый расчёт FOV с т.з. процессора. Поскольку все вычисления проделываются на стадии предрасчёта, затраты в худшем случае сравнимы с обходом массива размером с поле видимости.
2. Дружелюбное к алгоритмам нахождение пути представление карты. Не то, чтобы представить массив в виде графа было большой проблемой, но тут у нас уже есть готовый граф.
3. Возможность хранить в клетках графа видимости дополнительную предрасчитанную информацию: расстояние до центра, азимут и т.д.
4. И, самое главное, возможность соединять клетки как душе угодно. Я давно хотел использовать эту фишку для геймплея и вот сбылась мечта идиота.

В приложении — простейшая технодемка, в которой два прямоугольных помещения соединены с особым цинизмом.
Вложения
StencilTest.zip
(5.32 МБ) 111 скачиваний
Dump the screen? [y/n]

Аватара пользователя
thefish
Сообщения: 31
Зарегистрирован: 18 июн 2012, 22:37

Re: FOV и карта на графах

Сообщение thefish » 11 ноя 2019, 19:26

Фишка с незаметными переходами между комнатами - просто офигенно крутая! Я ее обязательно украду творчески позаимствую.
А вот FOV действительно жадный =(
StencilTest2.jpg
StencilTest2.jpg (135.04 КБ) 2783 просмотра

Аватара пользователя
Максим Кич
Администратор
Сообщения: 1642
Зарегистрирован: 03 дек 2006, 20:17
Откуда: Витебск, Беларусь
Контактная информация:

Re: FOV и карта на графах

Сообщение Максим Кич » 12 ноя 2019, 13:05

thefish писал(а):
11 ноя 2019, 19:26
Фишка с незаметными переходами между комнатами - просто офигенно крутая! Я ее обязательно украду творчески позаимствую.
Удачи! Но по сравнению с классическим представлением карты это — боль!
thefish писал(а):
11 ноя 2019, 19:26
А вот FOV действительно жадный =(
У меня появилась идея на тему того, что можно с этим сделать. Если моя гипотеза верна, у меня получится достаточно безболезненно умерить его аппетиты.
Dump the screen? [y/n]

Аватара пользователя
Максим Кич
Администратор
Сообщения: 1642
Зарегистрирован: 03 дек 2006, 20:17
Откуда: Витебск, Беларусь
Контактная информация:

Re: FOV и карта на графах

Сообщение Максим Кич » 26 янв 2020, 15:59

«Жадность» предыдущего алгоритма оказалась крайне тяжёлой, и его пришлось подвергнуть суровой модификации. Кстати, всё изобретено до меня, и алгоритм с предрасчётом дерева видимости (PCVT) описан на RogueBasin (и имеет те же проблемы с тенями)

В принципе, если бы у меня была обычная карта-матрица, я бы взял, например, рекурсивный shadow-casting и не мучился. К сожалению, для того, чтобы реализовать идею с анизотропной картой на графах — а я планирую строить вокруг неё изрядную часть геймплея и лора — алгоритм LOS должен рассматривать клетки карты в строго определённом порядке: от источника к периферии. Иначе из-за того, что клетки могут соединяться по-разному, картина не будет соответствовать тому, что «видит» персонаж.

В итоге, я пришёл к чему-то, похожему на смесь PCVT и Precomputed Shade (PS).

1. Я всё ещё использую предрасчитанное дерево лучей, исходящих из центра к периметру квадрата видимости (круг из него делается элементарно на любой стадии, но работать проще с квадратом).
2. Каждая клетка на периметре квадрата получает свой уникальный номер.
3. Каждая клетка внутри квадрата хранит список тех номеров клеток периметра, к которым через эту клетку проходят лучи.

Фактически, мы индексируем тени, которые клетка отбрасывает на периметр квадрата. Только вместо углов из PS мы имеем меру, масштабирующуюся с размером области обсчёта.

Далее, при использовании дерево видимости обходится в ширину (это принципиально). Мы заводим пустое множество (я использую SortedSet в C#) индексов текущей тени. На каждом шаге, мы добавляем в очередь клетки нижнего уровня, если клетка текущего уровня прозрачна и множество теней которой не пересекается с множеством текущей тени. Если клетка непрозрачна — множество текущей тени пополняется её индексами теней.

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

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

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

UPD: оно тормозит на радиусах от 12 (а на более слабых, надо полагать, и раньше) и имеет артефактные тени там, где их быть не должно... Буду думать дальше.
Dump the screen? [y/n]

Ответить

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 5 гостей