В этой статье соберём на C# поле зрения для пошаговой игры на сетке: алгоритм симметричного shadowcasting, который честно считает, какие клетки видит персонаж из-за углов и колонн, и поверх него туман войны на Tilemap с тремя состояниями клеток: «не видел», «видел раньше», «вижу сейчас». В конце будет тест, который ловит самую неприятную ошибку FOV-алгоритмов — асимметрию, когда игрок не видит монстра, а монстр игрока видит.
Зачем считать видимость, если есть Physics2D.Raycast
Первое, что приходит в голову: для каждой клетки в радиусе пустить луч от игрока и посмотреть, упёрся ли он в стену. В реальном времени с коллайдерами так и делают. Но в рогалике, тактике или пошаговой стратегии мир — это сетка, и у такого подхода сразу три проблемы.
- Цена. При радиусе 12 в круге около 450 клеток, и каждый луч проходит до 12 клеток. Это тысячи проверок на каждый шаг игрока, а если поле зрения нужно ещё и двадцати врагам, получается заметная нагрузка на ровном месте.
- Артефакты. Луч, проведённый по алгоритму Брезенхэма, на диагоналях «проскальзывает» между двумя стенами, стоящими уголком, или, наоборот, цепляется за угол и прячет клетку, которую игрок очевидно должен видеть.
- Асимметрия. Линия из A в B и линия из B в A на дискретной сетке проходят через разные клетки. Значит, игрок может видеть врага, а враг игрока нет. Для игры, где ИИ решает «атаковать или нет» по видимости, это источник странных багов.
Shadowcasting решает все три. Он обходит каждую клетку в области видимости ровно один раз, а стены отбрасывают «тени» — диапазоны углов, в которые дальше смотреть не нужно. В варианте, который описал Альберт Форд (статья «Symmetric Shadowcasting» на albertford.com), алгоритм вдобавок симметричен для клеток пола: если A видит B, то и B видит A. Этот вариант мы и реализуем.
Идея алгоритма на пальцах
Разделим пространство вокруг наблюдателя на четыре квадранта: север, юг, восток и запад. Каждый — треугольник, расширяющийся от наблюдателя. В квадранте «север» клетки идут рядами: ряд 1 — соседи сверху, ряд 2 — следующая полоса и так далее. Ряд на глубине d содержит клетки со столбцами от −d до d.
Видимую часть ряда задают два наклона: начальный и конечный. Наклон — отношение столбца к глубине. Для пустого квадранта это −1 и 1: смотрим по всей ширине треугольника. Сканируя ряд слева направо, алгоритм следит за переходами:
- если предыдущая клетка была стеной, а текущая — пол, тень закончилась, и начальный наклон ряда сдвигается к краю этой клетки;
- если предыдущая была полом, а текущая — стена, начинается тень. Кусок ряда до неё порождает следующий ряд со своим конечным наклоном;
- если ряд кончился на клетке пола, следующий ряд продолжает оставшийся диапазон.
Так квадрант разбивается на «конусы» света между стенами, и каждый конус сканируется дальше независимо. Клетки, которые попали в тень, просто никогда не посещаются, поэтому сложность пропорциональна числу видимых клеток, а не площади круга.
Ключевой момент симметрии: клетка пола считается видимой, только если её центр лежит внутри диапазона наклонов. Стены же открываются, если в диапазон попала любая их часть. Благодаря этому стены комнаты видны целиком («расширяющиеся стены»), а видимость пола остаётся симметричной.
Наклоны без float
В оригинале на Python наклоны хранятся в Fraction, и это не прихоть. Наклон краёв клеток выражается дробями вида (2·col − 1) / (2·depth), и при float-арифметике граничные случаи вроде 0.5 превращаются в 0.49999 и 0.50001. В итоге клетка на границе тени то видна, то нет, и симметрия ломается ровно там, где игрок её заметит — у дверных проёмов.
Нам хватит целочисленной дроби: знаменатель всегда положительный, а числа маленькие.
using UnityEngine;
// Наклон хранится дробью Num/Den: float даёт ошибки на границах теней
public readonly struct Slope
{
public readonly int Num;
public readonly int Den; // всегда больше нуля
public Slope(int num, int den)
{
Num = num;
Den = den;
}
// Наклон левого края клетки (depth, col)
public static Slope OfTileEdge(int depth, int col) => new Slope(2 * col - 1, 2 * depth);
}
public struct Row
{
public int Depth;
public Slope Start;
public Slope End;
public Row(int depth, Slope start, Slope end)
{
Depth = depth;
Start = start;
End = end;
}
// Первый и последний столбец ряда, которые хотя бы частично в диапазоне
public int MinCol => FovMath.RoundTiesUp(Depth * Start.Num, Start.Den);
public int MaxCol => FovMath.RoundTiesDown(Depth * End.Num, End.Den);
public Row Next() => new Row(Depth + 1, Start, End);
// Центр клетки внутри диапазона наклонов: условие симметрии для пола
public bool IsSymmetric(int col) =>
col * Start.Den >= Depth * Start.Num &&
col * End.Den <= Depth * End.Num;
}
public static class FovMath
{
// floor(n/d + 1/2) для d > 0
public static int RoundTiesUp(int n, int d) => FloorDiv(2 * n + d, 2 * d);
// ceil(n/d - 1/2) для d > 0
public static int RoundTiesDown(int n, int d) => -FloorDiv(-(2 * n - d), 2 * d);
// Целочисленное деление с округлением вниз и для отрицательных чисел
public static int FloorDiv(int a, int b)
{
int q = a / b;
if (a % b != 0 && (a < 0) != (b < 0))
q--;
return q;
}
}Обратите внимание на FloorDiv. Оператор деления в C# округляет к нулю, то есть −3 / 2 даёт −1, а нам нужно −2. Без этой поправки левая половина каждого квадранта (отрицательные столбцы) будет считаться со сдвигом на клетку, и вы получите несимметричный конус обзора, который долго будете списывать на «так задумано».
Почему округление «половинки вверх» для начала ряда и «половинки вниз» для конца? Если край диапазона проходит ровно по границе двух клеток, клетка за границей в него не попадает. Именно эти два правила дают аккуратные, предсказуемые края теней.
Интерфейс карты
Алгоритму не нужно знать ни про Tilemap, ни про GameObject. Ему достаточно двух операций: узнать, непрозрачна ли клетка, и отметить клетку видимой.
public interface IFovMap
{
// Стена, закрытая дверь или клетка за пределами карты
bool IsOpaque(int x, int y);
void MarkVisible(int x, int y);
}За пределами карты клетки должны считаться непрозрачными. Иначе алгоритм на открытом краю уровня уйдёт сканировать пустоту до самого радиуса, а без радиуса — бесконечно.
Сам shadowcasting
Оригинальная реализация рекурсивная. В C# рекурсию легко заменить своим стеком: порядок обработки рядов на результат не влияет, потому что каждый ряд несёт свои наклоны с собой. Стек выделяем один раз и переиспользуем, чтобы расчёт поля зрения не создавал мусора.
using System.Collections.Generic;
using UnityEngine;
public sealed class ShadowcastFov
{
readonly Stack<Row> _rows = new Stack<Row>(64);
public void Compute(IFovMap map, Vector2Int origin, int radius)
{
map.MarkVisible(origin.x, origin.y);
// +radius делает круг чуть «полнее», без одиночных клеток на осях
int radiusSq = radius * radius + radius;
for (int quadrant = 0; quadrant < 4; quadrant++)
{
_rows.Clear();
_rows.Push(new Row(1, new Slope(-1, 1), new Slope(1, 1)));
while (_rows.Count > 0)
{
Row row = _rows.Pop();
if (row.Depth > radius)
continue;
bool hasPrev = false;
bool prevWall = false;
int minCol = row.MinCol;
int maxCol = row.MaxCol;
for (int col = minCol; col <= maxCol; col++)
{
ToWorld(quadrant, origin, row.Depth, col, out int x, out int y);
bool wall = map.IsOpaque(x, y);
bool inRadius = row.Depth * row.Depth + col * col <= radiusSq;
if (inRadius && (wall || row.IsSymmetric(col)))
map.MarkVisible(x, y);
// Тень кончилась: сужаем начало ряда
if (hasPrev && prevWall && !wall)
row.Start = Slope.OfTileEdge(row.Depth, col);
// Тень началась: свет до стены уходит в следующий ряд
if (hasPrev && !prevWall && wall)
{
Row next = row.Next();
next.End = Slope.OfTileEdge(row.Depth, col);
_rows.Push(next);
}
hasPrev = true;
prevWall = wall;
}
// Ряд закончился полом: продолжаем оставшийся конус
if (hasPrev && !prevWall)
_rows.Push(row.Next());
}
}
}
// Переводит (глубина, столбец) квадранта в координаты сетки. Y в Unity растёт вверх
static void ToWorld(int quadrant, Vector2Int o, int depth, int col, out int x, out int y)
{
switch (quadrant)
{
case 0: x = o.x + col; y = o.y + depth; break; // север
case 1: x = o.x + col; y = o.y - depth; break; // юг
case 2: x = o.x + depth; y = o.y + col; break; // восток
default: x = o.x - depth; y = o.y + col; break; // запад
}
}
}Несколько неочевидных мест.
Изменение row.Start посреди цикла. Границы minCol и maxCol посчитаны до цикла, поэтому сужение диапазона не меняет набор обходимых клеток текущего ряда. Но проверка симметрии для следующих клеток уже идёт по новому начальному наклону — так и должно быть: клетки сразу за стеной частично в тени, и пол в них виден, только если центр не затенён.
Диагонали посещаются дважды. Клетки со столбцом, равным ±глубине, принадлежат сразу двум квадрантам. Это нормально, нужно лишь, чтобы MarkVisible был идемпотентным — в следующем разделе так и сделаем.
Радиус. Отсечка по глубине обрывает скан, а проверка по квадрату расстояния делает границу круглой. Стены за кругом при этом всё равно участвуют в построении теней, просто не помечаются видимыми.
Хранение видимости без очистки массива
Каждый ход нужно «забыть» старое поле зрения и посчитать новое. Наивно — обнулить массив bool размером с карту. На карте 200×200 это 40 тысяч записей на каждый шаг, хотя видимых клеток от силы пара сотен. Стандартный приём — метки поколений: вместо bool храним номер расчёта, в котором клетка была видна. Чтобы «очистить» всё, достаточно увеличить счётчик.
using System.Collections.Generic;
using UnityEngine;
public sealed class GridVisibility : IFovMap
{
public readonly int Width;
public readonly int Height;
readonly bool[] _opaque;
readonly bool[] _explored;
readonly int[] _visibleStamp;
int _stamp = 1;
readonly List<Vector2Int> _visibleNow = new List<Vector2Int>(512);
readonly List<Vector2Int> _visibleBefore = new List<Vector2Int>(512);
readonly ShadowcastFov _fov = new ShadowcastFov();
public IReadOnlyList<Vector2Int> VisibleNow => _visibleNow;
public IReadOnlyList<Vector2Int> VisibleBefore => _visibleBefore;
public GridVisibility(int width, int height)
{
Width = width;
Height = height;
_opaque = new bool[width * height];
_explored = new bool[width * height];
_visibleStamp = new int[width * height];
}
public bool InBounds(int x, int y) => x >= 0 && y >= 0 && x < Width && y < Height;
public void SetOpaque(int x, int y, bool value) => _opaque[y * Width + x] = value;
public bool IsOpaque(int x, int y) => !InBounds(x, y) || _opaque[y * Width + x];
public bool IsVisible(int x, int y) => InBounds(x, y) && _visibleStamp[y * Width + x] == _stamp;
public bool IsExplored(int x, int y) => InBounds(x, y) && _explored[y * Width + x];
public void MarkVisible(int x, int y)
{
if (!InBounds(x, y))
return;
int i = y * Width + x;
if (_visibleStamp[i] == _stamp)
return; // уже отмечена, например на диагонали двух квадрантов
_visibleStamp[i] = _stamp;
_explored[i] = true;
_visibleNow.Add(new Vector2Int(x, y));
}
public void Recompute(Vector2Int origin, int radius)
{
// Старый список становится «предыдущим» без копирования данных
_visibleBefore.Clear();
_visibleBefore.AddRange(_visibleNow);
_visibleNow.Clear();
_stamp++;
_fov.Compute(this, origin, radius);
}
}Списки VisibleNow и VisibleBefore пригодятся отрисовке: обновлять нужно только клетки, у которых изменилось состояние, а не всю карту. Переполнение int у счётчика при одном пересчёте на ход наступит через два миллиарда ходов, так что об этом можно не думать.
Туман войны на Tilemap
Самый простой и быстрый способ нарисовать туман — отдельный Tilemap поверх уровня с более высоким Order in Layer. В нём два тайла: непрозрачно-чёрный для неизведанных клеток и полупрозрачный тёмный для клеток, которые игрок уже видел, но сейчас не видит. Видимые клетки в тумане просто пустые.
Карту непрозрачности строим из Tilemap стен: всё, где есть тайл, блокирует обзор. Чтобы индексы массива начинались с нуля, запоминаем левый нижний угол границ.
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.Tilemaps;
public sealed class FogOfWar : MonoBehaviour
{
[SerializeField] Tilemap _walls;
[SerializeField] Tilemap _fog;
[SerializeField] TileBase _unknownTile;
[SerializeField] TileBase _rememberedTile;
[SerializeField] int _radius = 10;
GridVisibility _visibility;
Vector3Int _origin;
readonly List<Vector3Int> _positions = new List<Vector3Int>(1024);
readonly List<TileBase> _tiles = new List<TileBase>(1024);
public GridVisibility Visibility => _visibility;
void Awake()
{
_walls.CompressBounds();
BoundsInt b = _walls.cellBounds;
_origin = b.min;
_visibility = new GridVisibility(b.size.x, b.size.y);
var all = new TileBase[b.size.x * b.size.y];
for (int y = 0; y < b.size.y; y++)
for (int x = 0; x < b.size.x; x++)
{
var cell = new Vector3Int(_origin.x + x, _origin.y + y, 0);
_visibility.SetOpaque(x, y, _walls.HasTile(cell));
all[y * b.size.x + x] = _unknownTile;
}
// Заливаем весь уровень туманом одним вызовом
_fog.SetTilesBlock(new BoundsInt(_origin, new Vector3Int(b.size.x, b.size.y, 1)), all);
}
public Vector2Int ToGrid(Vector3Int cell) => new Vector2Int(cell.x - _origin.x, cell.y - _origin.y);
public Vector3Int ToCell(Vector2Int g) => new Vector3Int(g.x + _origin.x, g.y + _origin.y, 0);
public void Refresh(Vector3Int playerCell)
{
_visibility.Recompute(ToGrid(playerCell), _radius);
_positions.Clear();
_tiles.Clear();
// Ушли из поля зрения: становятся «воспоминанием»
foreach (Vector2Int g in _visibility.VisibleBefore)
{
if (_visibility.IsVisible(g.x, g.y))
continue;
_positions.Add(ToCell(g));
_tiles.Add(_rememberedTile);
}
// Видимые сейчас: убираем туман
foreach (Vector2Int g in _visibility.VisibleNow)
{
_positions.Add(ToCell(g));
_tiles.Add(null);
}
_fog.SetTiles(_positions.ToArray(), _tiles.ToArray());
}
}Пакетный SetTiles заметно быстрее, чем сотни отдельных SetTile: Tilemap обновляет меш и коллайдеры один раз. Два вызова ToArray создают небольшие массивы на каждый ход. Для пошаговой игры это незаметно; если пересчитывать каждый кадр, держите собственные массивы с запасом и используйте перегрузку SetTiles с TileChangeData или обновляйте через SetTile только изменившиеся клетки.
Альтернатива отдельному Tilemap — красить клетки самого уровня через SetColor. Тогда перед покраской нужно снять с клетки флаг TileFlags.LockColor (метод SetTileFlags), иначе цвет молча не применится: большинство тайлов по умолчанию запирают цвет. Вариант с отдельным слоем тумана проще, к тому же он прячет и спрайты врагов, стоящих под туманом, если поставить слой тумана выше них.
Когда пересчитывать
Поле зрения меняется в двух случаях: наблюдатель переместился или изменилась непрозрачность клеток (открыли дверь, взорвали стену). Самый надёжный вариант — флаг «грязно», который выставляют оба события, и один пересчёт в конце хода.
public sealed class FovController : MonoBehaviour
{
[SerializeField] FogOfWar _fog;
[SerializeField] Grid _grid;
[SerializeField] Transform _player;
Vector3Int _lastCell = new Vector3Int(int.MinValue, 0, 0);
bool _dirty = true;
public void SetDoorOpen(Vector3Int cell, bool open)
{
Vector2Int g = _fog.ToGrid(cell);
_fog.Visibility.SetOpaque(g.x, g.y, !open);
_dirty = true;
}
void LateUpdate()
{
Vector3Int cell = _grid.WorldToCell(_player.position);
if (cell != _lastCell)
{
_lastCell = cell;
_dirty = true;
}
if (!_dirty)
return;
_dirty = false;
_fog.Refresh(cell);
}
}LateUpdate здесь выбран намеренно: к этому моменту все скрипты движения отработали, и туман не отстаёт от игрока на кадр.
Враги и симметрия
Вот где окупается симметричный вариант. Скрыть врагов, которых игрок не видит, — одна проверка:
foreach (Enemy enemy in _enemies)
{
Vector2Int g = _fog.ToGrid(enemy.Cell);
enemy.SetRendered(_fog.Visibility.IsVisible(g.x, g.y));
}А раз для клеток пола видимость симметрична, тот же результат отвечает и на обратный вопрос: видит ли враг игрока. Не нужно считать отдельное поле зрения для каждого монстра — достаточно проверить, что клетка врага видна игроку и расстояние не больше радиуса обзора самого врага. Это превращает десятки вызовов FOV в одну проверку массива.
public bool EnemySeesPlayer(Enemy enemy, Vector3Int playerCell)
{
Vector2Int e = _fog.ToGrid(enemy.Cell);
if (!_fog.Visibility.IsVisible(e.x, e.y))
return false;
Vector3Int d = enemy.Cell - playerCell;
return d.x * d.x + d.y * d.y <= enemy.SightRadius * enemy.SightRadius;
}Тонкость: радиус игрока должен быть не меньше радиуса любого врага, иначе дальнозоркий снайпер за пределами круга игрока «ослепнет». Если у врагов обзор больше, считайте поле зрения игрока с максимальным радиусом, а для тумана отдельно фильтруйте клетки по радиусу игрока.
Ещё один момент: симметрия гарантирована для пола. Стена может быть видна игроку, а «взгляд со стены» не определён — но враги на стенах обычно не стоят. Если у вас есть существа в стенах (призраки, турели в нишах), заведите для их клетки отдельную проверку.
Когда хватит одной линии
Не каждой проверке видимости нужен полный FOV. Если вопрос разовый — «может ли турель выстрелить в эту клетку» — дешевле пройти одной линией. Чтобы она не противоречила туману, удобно считать её от центра клетки к центру клетки и проверять обе стороны:
public static bool HasLineOfSight(IFovMap map, Vector2Int a, Vector2Int b)
{
return Walk(map, a, b) || Walk(map, b, a);
}
// Брезенхэм: идём по клеткам между a и b, концы не проверяем
static bool Walk(IFovMap map, Vector2Int a, Vector2Int b)
{
int dx = Mathf.Abs(b.x - a.x), sx = a.x < b.x ? 1 : -1;
int dy = -Mathf.Abs(b.y - a.y), sy = a.y < b.y ? 1 : -1;
int err = dx + dy;
int x = a.x, y = a.y;
while (true)
{
if (x == b.x && y == b.y)
return true;
if ((x != a.x || y != a.y) && map.IsOpaque(x, y))
return false;
int e2 = 2 * err;
if (e2 >= dy) { err += dy; x += sx; }
if (e2 <= dx) { err += dx; y += sy; }
}
}Проверка «в обе стороны» делает функцию симметричной по построению, но результат всё равно иногда расходится с shadowcasting на диагоналях вблизи углов. Поэтому правило простое: если результат виден игроку на экране (туман, подсветка, скрытие врагов), берите shadowcasting; если это внутренняя механика без визуальной обратной связи — можно линией.
Тест на симметрию
FOV-код ломается тихо: ошибка в одном знаке даёт поле зрения, которое выглядит почти правильно. Поэтому стоит закрепить главное свойство тестом в Edit Mode. Карту удобно описывать строками: решётка — стена, точка — пол.
using NUnit.Framework;
using UnityEngine;
public class ShadowcastFovTests
{
static readonly string[] Map =
{
"##########",
"#....#...#",
"#.##.#.#.#",
"#....#...#",
"#.#......#",
"#...##.#.#",
"##########",
};
static GridVisibility Build()
{
int h = Map.Length, w = Map[0].Length;
var v = new GridVisibility(w, h);
for (int y = 0; y < h; y++)
for (int x = 0; x < w; x++)
v.SetOpaque(x, y, Map[h - 1 - y][x] == '#');
return v;
}
[Test]
public void FloorVisibility_IsSymmetric()
{
const int radius = 20;
var a = Build();
var b = Build();
for (int ay = 0; ay < a.Height; ay++)
for (int ax = 0; ax < a.Width; ax++)
{
if (a.IsOpaque(ax, ay)) continue;
a.Recompute(new Vector2Int(ax, ay), radius);
for (int by = 0; by < b.Height; by++)
for (int bx = 0; bx < b.Width; bx++)
{
if (b.IsOpaque(bx, by)) continue;
b.Recompute(new Vector2Int(bx, by), radius);
Assert.AreEqual(a.IsVisible(bx, by), b.IsVisible(ax, ay),
$"({ax},{ay}) и ({bx},{by}) видят друг друга по-разному");
}
}
}
[Test]
public void OriginIsAlwaysVisible()
{
var v = Build();
v.Recompute(new Vector2Int(1, 1), 5);
Assert.IsTrue(v.IsVisible(1, 1));
}
}Тест квадратичный по числу клеток пола, поэтому карту держите маленькой, но с колоннами, нишами и диагональными проходами — именно там ломается симметрия. Отдельно полезно прогнать тест с float-наклонами вместо дробей: на этой карте он, скорее всего, упадёт, и вы своими глазами увидите, зачем понадобилась целочисленная арифметика.
Производительность и расширения
На карте с комнатами и коридорами расчёт с радиусом 10–15 занимает микросекунды и не выделяет памяти: ряды — структуры в переиспользуемом стеке, метки поколений избавляют от очистки массивов. Если нужно поле зрения для многих источников одновременно (например, видимость всех союзников в тактике), считайте их по очереди в один GridVisibility без увеличения счётчика между вызовами Compute: MarkVisible объединит результаты сам. Для этого вынесите увеличение _stamp и очистку списков в отдельный метод BeginFrame.
Ещё несколько идей, которые ложатся на ту же основу:
- Освещение. Каждый факел — свой Compute с маленьким радиусом в отдельную карту освещённости. Клетка видна игроку, только если она в его FOV и освещена. Так получаются тёмные комнаты, в которые видно лишь пятна света.
- Полупрозрачные препятствия. Кусты или туман можно сделать «стеной для обзора за ними, но не для самих себя»: клетка помечается видимой, а для сканирования считается непрозрачной.
- Память о врагах. В клетку «воспоминания» можно записывать последнего увиденного врага и рисовать его призрачный силуэт — игроку это подсказывает, где он видел опасность.
- Гексагональные сетки. Shadowcasting переносится и на гексы, но там шесть секторов вместо четырёх квадрантов и другие формулы наклонов. Если у вас гексы, подход тот же, а код ряда придётся переписать.
Итог
Поле зрения на сетке — задача, которую легко решить «почти правильно» лучами и потом долго ловить странности у дверей и колонн. Симметричный shadowcasting даёт честный результат за время, пропорциональное видимой области, а пара инженерных решений — целочисленные наклоны, свой стек вместо рекурсии и метки поколений вместо очистки массива — делают его быстрым и предсказуемым в Unity. Поверх него туман войны на отдельном Tilemap собирается за сотню строк, а симметрия бесплатно отвечает на вопрос, видит ли враг игрока.
