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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Аватара пользователя
Максим Кич
Администратор
Сообщения: 1613
Зарегистрирован: 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]

Ответить

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

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