Рекурсивный shadowcasting
Алгоритм поля зрения для игр на сетке: просматривает каждый из восьми октантов, отслеживая диапазоны видимых углов, — клетки-преграды отбрасывают тени, скрывающие всё за ними.
Задача — точно определить, какие клетки видит персонаж в сеточном мире со стенами; это поле часто рисуют как туман войны. Рекурсивный shadowcasting делит обзор на восемь симметричных октантов и сканирует каждый по рядам (или по столбцам). Для каждого ряда он несёт диапазон видимых «наклонов»; клетка-преграда разрезает этот диапазон надвое, и алгоритм рекурсивно обрабатывает половины, так что клетки в её тени вообще не посещаются.
Описал метод Бьёрн Бергстрём в 2001 году. Он быстрый и симметричный — если A видит B, то и B видит A, — и стал стандартом в рогаликах. Есть и альтернативы: permissive FOV и raycasting для каждой клетки.