Страница 1 из 2

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

Добавлено: 31 окт 2019, 21:32
thefish
Набрел на 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, с примером использования.

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

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 сводится к обходу дерева до вершин, соответствующих непрозначным клеткам. Одна из неочевидных фишек такого подхода заключается в том, что уровень тоже может описываться графом, открывая возможности делать порталы, анизотропные коридоры и всякие комнаты, которые внутри больше, чем снаружи.

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

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

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

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

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

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

Пишите об обнаруженных багах. Вскоре постараюсь запилить и алгоритм М. Кича.

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

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

stencil.jpg
stencil.jpg (670.44 КБ) 4924 просмотра

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

Ну и дело немного медленно идёт, потому что движок и язык для меня почти незнакомые.

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

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

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

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

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

Добавлено: 06 ноя 2019, 17:33
karagy
А там не маячит какой-нибудь precomputed pathfinding заодно с фовом?

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

Добавлено: 06 ноя 2019, 18:18
Максим Кич
thefish писал(а):
05 ноя 2019, 20:40
Пишите об обнаруженных багах.
А не слишком ли этот алгоритм за углы заглядывает? По идее, отмеченных стенок не должно быть видно.
corners.jpg
corners.jpg (50.32 КБ) 4901 просмотр

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

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

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

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

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

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

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

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

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

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

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

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

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

Когда заборю проблемы с жадностью — выложу proof-of-concept в отдельной теме.
strange1.png
strange1.png (89.41 КБ) 4787 просмотров

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

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

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

Добавил Dev-читы, открываются по Shift+Z.

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

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

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

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

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

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

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