Precomputed Shade - FOV алгоритм, Golang

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

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

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

Precomputed Shade - FOV алгоритм, Golang

Сообщение thefish » 31 окт 2019, 21:32

Набрел на reddit по ссылкам на интересный гибрид shadowcasting и precomputed tree.
Если бы не подсветка стен (которую вменяемо реализовать тут затруднительно) то работал бы он по предрасчитанному дереву вообще в один проход.

Логика работы примерно следующая:

Код: Выделить всё

Предрасчет:

	- Составляем список тайлов в наибольшем возможном радиусе видимости, сохраняем X и Y относительно центра
	- Сохраняем расстояние до центра для каждого тайла, и сортируем список по возрастанию дистанции
	- Сохраняем для каждого тайла список углов occludedAngles, которые он закрывает. По часовой стрелке, 
		абсолютные значения в виде int
	- Создаем массив EmptyShade []uint8 из 360 элементов, заполненный нулями. И такой же из единичек под 
		названием FullShade

Работа:
	- Создаем два массива из 360 uint8 - CurrentShade и NextShade
	- Для начала CurrentShade := EmptyShade
	- До тех пор пока CurrentShade не равно FullSHade: итерируемся по заранее отсортированнму списку тайлов
		- Если дистанция от центра до текущего тайла не равна предыдущей проверенной дистанции - заменяем 
			содержимое CurrentShade на NextShade.
		- Если проверяемый тайл непрозрачный: для каждого угла в списке occludedAngles этого тайла - ставим 
			единичку в соответствующей углу ячейке массива NextShade[angle] = 1.
		- Для каждого угла в списке occludedAngles этого тайла добавляем единичку к степени освещенности этого 
			тайла за каждый 0 в соответствующей ячейке массива CurrentShade.
Кому объяснение не зашло - вот реализация на Go, с примером использования.

Как вам такой алгоритм? Или может быть видели что-то подобное по изяществу?
Последний раз редактировалось thefish 01 ноя 2019, 12:22, всего редактировалось 1 раз.

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

Re: Precomputed Shade - FOV алгоритм, Golang

Сообщение Максим Кич » 01 ноя 2019, 09:39

Я всё никак не проверю на практике достаточно близкую схему:

Предрасчёт:
1. Пусть N — максимальный радиус FOV, пусть текущая итерация будет i = 0
2. Создаём нуль-граф из вершин, соответствующих клеткам квадрата со стороной 2*N + 1
3. Обходим клетки по периметру квадрата со стороной 2*N - i + 1 и центром в координатах 0:0
4. Для каждой такой клетки просчитываем первую итерацию алгоритма Брезенхема и получаем координаты следующей клетки на пути к центру. Соединяем ребром эти две клетки.
5. i = i + 1. Если i = N + 1 — предрасчёт окончен. Иначе — повторяем с пункта 3.

В итоге мы должны получить граф, в котором вершины — это координаты клеток относительно центра, а рёбра — пути распространения лучей от центра к каждой клетке. Вполне возможно, что придётся модифицировать алгоритм с точки зрения порядка обхода вершин.

Работа: получившийся граф является деревом, корень которого приходится на центр FOV. Построение FOV сводится к обходу дерева до вершин, соответствующих непрозначным клеткам. Одна из неочевидных фишек такого подхода заключается в том, что уровень тоже может описываться графом, открывая возможности делать порталы, анизотропные коридоры и всякие комнаты, которые внутри больше, чем снаружи.
Dump the screen? [y/n]

Аватара пользователя
Anfeir
Сообщения: 696
Зарегистрирован: 14 дек 2007, 09:29
Контактная информация:

Re: Precomputed Shade - FOV алгоритм, Golang

Сообщение Anfeir » 02 ноя 2019, 07:54

- Составляем список тайлов в наибольшем возможном радиусе видимости, сохраняем X и Y относительно центра
- Сохраняем расстояние до центра для каждого тайла, и сортируем список по возрастанию дистанции
Сильно не вчитывался, поэтому может замечание мимо, но.
Каждый раз строить отсортированный список тайлов от центра может оказаться излишним, ведь можно составить такой список не привязанный к конкретным координатам. Т.е. всегда использовать один и тот же предзаданный маршрут обхода, просто накладывать его на конкретные координаты. Я что-то подобное использовал.

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

Re: Precomputed Shade - FOV алгоритм, Golang

Сообщение thefish » 02 ноя 2019, 12:45

Anfeir писал(а):Каждый раз строить отсортированный список тайлов от центра может оказаться излишним, ведь можно составить такой список не привязанный к конкретным координатам. Т.е. всегда использовать один и тот же предзаданный маршрут обхода, просто накладывать его на конкретные координаты.
Ну так и есть, потому пункт и называется "предрасчет".
Максим Кич писал(а):
01 ноя 2019, 09:39
Я всё никак не проверю на практике достаточно близкую схему:
...
Идея кажется благодатной, попробую набросать реализацию.

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

Re: Precomputed Shade - FOV алгоритм, Golang

Сообщение thefish » 05 ноя 2019, 20:40

Вот, в рамках изучения кросс-компиляции даже собрал демо precomputed shade под win64.

Пишите об обнаруженных багах. Вскоре постараюсь запилить и алгоритм М. Кича.
Последний раз редактировалось thefish 07 ноя 2019, 10:35, всего редактировалось 1 раз.

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

Re: Precomputed Shade - FOV алгоритм, Golang

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

thefish писал(а):
05 ноя 2019, 20:40
Вскоре постараюсь запилить и алгоритм М. Кича.
Алгоритм М.Кича, похоже, нуждается в серьёзной обработке напильником. Я сделал прикидку по графу, получается что-то вот такое:

stencil.jpg
stencil.jpg (670.44 КБ) 278 просмотров

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

Ну и дело немного медленно идёт, потому что движок и язык для меня почти незнакомые.
Dump the screen? [y/n]

Аватара пользователя
Xecutor
Мастер
Сообщения: 739
Зарегистрирован: 25 мар 2008, 08:32

Re: Precomputed Shade - FOV алгоритм, Golang

Сообщение Xecutor » 06 ноя 2019, 12:34

Я 6 лет назад что-то подобное сделал.
Детали тут https://forums.roguetemple.com/index.php?topic=3346.0 правда на аглицком, и картинки теперь не встраиваются, кликать надо.
Пример и код на С++ тут: https://sites.google.com/site/tetrogue/downloads/cfov

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

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

Аватара пользователя
karagy
Сообщения: 1099
Зарегистрирован: 10 янв 2007, 14:13

Re: Precomputed Shade - FOV алгоритм, Golang

Сообщение karagy » 06 ноя 2019, 17:33

А там не маячит какой-нибудь precomputed pathfinding заодно с фовом?

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

Re: Precomputed Shade - FOV алгоритм, Golang

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

thefish писал(а):
05 ноя 2019, 20:40
Пишите об обнаруженных багах.
А не слишком ли этот алгоритм за углы заглядывает? По идее, отмеченных стенок не должно быть видно.
corners.jpg
corners.jpg (50.32 КБ) 255 просмотров
Dump the screen? [y/n]

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

Re: Precomputed Shade - FOV алгоритм, Golang

Сообщение thefish » 07 ноя 2019, 08:33

Максим Кич писал(а):
06 ноя 2019, 18:18
А не слишком ли этот алгоритм за углы заглядывает? По идее, отмеченных стенок не должно быть видно.
Оригинальный алгоритм тут ни при чем, это уже лично моя реализация подсветки стенок. Не самая удачная, признаю, но как это адекватно (в плане сложности алгоритма) поправить - я пока не придумал.

Понял, на что ты намекаешь. Подкрутил константы, чтобы освещенным считался пол, на который попало более 2 лучей, и стенка, на которую попало более 5. Новый билд в аттаче.

PS Сейчас подумал, что надо бы сделать эти константы переменными и вывести ручечки (+) (-) в интерфейс.

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

Re: Precomputed Shade - FOV алгоритм, Golang

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

thefish писал(а):
07 ноя 2019, 08:33
Понял, на что ты намекаешь. Подкрутил константы, чтобы освещенным считался пол, на который попало более 2 лучей, и стенка, на которую попало более 5. Новый билд в аттаче.

PS Сейчас подумал, что надо бы сделать эти константы переменными и вывести ручечки (+) (-) в интерфейс.
Возможно, но это, кажется, фундаментальное свойство алгоритма. Или я криво объяснил, что я имею в виду, в прошлый раз.
corners2.jpg
corners2.jpg (38.09 КБ) 233 просмотра
Смотри: две освещённые клетки, которые «А» — эта стена для игрока находится за углом. Он их в принципе видеть не может, никак.
С другой стороны, есть неосвещённые клетки на линии взгляда «Б».
Dump the screen? [y/n]

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

Re: Precomputed Shade - FOV алгоритм, Golang

Сообщение thefish » 08 ноя 2019, 15:15

Максим Кич писал(а):
08 ноя 2019, 11:10
Возможно, но это, кажется, фундаментальное свойство алгоритма. Или я криво объяснил, что я имею в виду, в прошлый раз.
Нет, это моя реализация засветки стенок. Проблема в том, что расходящееся "кольцо" света на большом удалении становится достаточно дырявым .Тупо не хватает разрешения в 360 разных углов с шагом по градусу, чтобы охватить _все_ [частично попадающие под падающий по касательной свет] тайлы на удалении в 12 клеток.
Я попытался посчитать отраженный соседями свет, что и привело к показанному тобой артефакту:
Максим Кич писал(а):
08 ноя 2019, 11:10
Смотри: две освещённые клетки, которые «А» — эта стена для игрока находится за углом. Он их в принципе видеть не может, никак.
С другой стороны, есть неосвещённые клетки на линии взгляда «Б».
Ну раз мозгов мне сегодня не завезли, будем побеждать мощщой процессора. Я уменьшил шаг расчета углов до 1/2 градуса, и убрал костыли с отраженным светом. Зато теперь видимость считается в один проход по дереву, хоть само дерево и стало больше (но не в два раза!).

PS Естественно, на больших радиусах FOV проблема возникнет снова. Но кмк текущее значение в 10-15 клеток можно считать достаточным для целей создания рогалика.

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

Re: Precomputed Shade - FOV алгоритм, Golang

Сообщение Максим Кич » 09 ноя 2019, 19:42

С моим алгоритмом почти получилось. Теперь надо экспериментировать с графом, чтобы сделать его менее жадным. Возможность видеть за колоннами, как я предполагаю, проистекает из избыточного количества путей.

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

Когда заборю проблемы с жадностью — выложу proof-of-concept в отдельной теме.
strange1.png
strange1.png (89.41 КБ) 141 просмотр
Dump the screen? [y/n]

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

Re: Precomputed Shade - FOV алгоритм, Golang

Сообщение thefish » 12 ноя 2019, 13:04

Немножко потюнил алгоритм,обнаружил что некоторые колонны при определенном угле взгляда на них становятся прозрачными. И тут до меня дошло, что "жадность", которая обнаружилась и у precomputed shade - скорее всего обусловлена работой bresenham line, которая может причудливо изламываться при изменении конечной точки (на внешнем конце радиуса окружности).

Бороться с этим конечно можно (я бы опять применил расчет освещенности тайла), но сделаю это попозже.

Добавил Dev-читы, открываются по Shift+Z.
Вложения
alchemyst-go-win64-v0.0.1.6.zip
(1.83 МБ) 0 скачиваний
alchemyst-go-linux64-v0.0.1.6.zip
(1.59 МБ) 1 скачивание
Последний раз редактировалось thefish 12 ноя 2019, 15:16, всего редактировалось 2 раза.

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

Re: Precomputed Shade - FOV алгоритм, Golang

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

thefish писал(а):
12 ноя 2019, 13:04
И тут до меня дошло, что "жадность", которая обнаружилась и у precomputed shade - скорее всего обусловлена работой bresenham line, которая может причудливо изламываться при изменении конечной точки на внешнем радиусе окружности.
Так оно и есть. Я хочу проверить простую гипотезу: запретить лучу продолжаться «по другую сторону» непрозрачного блока. Т.е.:

Код: Выделить всё

* * . . . .
. # * * . .
. . . . * *
Вот это, скорее всего, и есть «причудливо изломанная линия». И мы можем «заглядывать» за блок из-за погрешности округления. Тут, чисто теоретически, мог бы сработать модицифированный алгоритм Ву, но это будет адовый оверкилл.

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

Код: Выделить всё

* * . . . .
. # → x . .
. . . . x x
Но я не уверен, насколько это будет работать с Precomputed Shade без существенных дополнений. В моём случае проверка получается сравнительно несложной.
Dump the screen? [y/n]

Ответить

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

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