Усатый стрелок из двадцати трёх полигонов

А давайте отвлечёмся немного и напишем игру в google play? И не такую огромную и неподъёмную фигню, про которую я обычно пишу статьи, а что-нибудь простое и милое сердцу?

На самом деле, всё очень просто: я наконец-то зарегистрировал аккаунт разработчика и очень хочу его опробовать. На момент написания этих строк у меня нет ни одного написанного класса и ни одного нарисованного пикселя. По сути, эта статья — самый настоящий devlog.

Оглавление

• Идея
• Микропрототип
• Первая карта
• Выбор сеттинга и визуального стиля
• Переход к 3D
• Procedural generation
• Правильные многоугольники в 2D
• Правильные многоугольники в 3D
• Тени
• Тени в вертексном шейдере
• Генерация теней на cpu
• Оптимизации теней
• Заключение первой части

Level 1.1. Идея.

Первые каляки-маляки.

Видите этот кружочек на бумаге? С него и начнём. Мне кажется, любую игру (да ладно, любое произведение) можно начать с подобной окружности. Чем он станет через несколько секунд? Колесом? Шляпой? Планетой? Рисую каракули, пытаюсь представить, что этот кружок означает. Шляпу!

Некий суровый дядя ходит по дорогам, а мы смотрим на него сверху. Суровый — потому что с пистолетом и стрелять умеет. Топает себе по городу, дует в усы, пускает пули в бандитов.
Эта заготовка — просто образ, который давно крутится в голове. Вот только делать игру на подобии Crimsonland делать решительно не хочется. И gui с двумя джойстиками я всегда недолюбливал. Обрезаем бритвой Оккама всё лишнее и получаем на выходе такую концепцию:

Уровень: небольшой городок с домами, ящиками и бочками.
Персонажи: главный герой (стрелок), бандиты и прохожие.
Игра стоит на паузе и ждёт действия игрока. Игрок делает свайп в любом направлении. В этот момент:
1. Время в игре начинает идти;
2. Главный герой стреляет в указанном игроком направлении;
3. Главный герой начинает двигаться в указанном направлении.

Проходит половина секунды и время в игре снова останавливается. Игроку нужно победить всех бандитов, ранив как можно меньше прохожих.

Это сочетание автоматической стрельбы и остановки времени мне очень приглянулось:

• Автоматическая стрельба:
  • Упрощает управление (один свайп вместо двух джойстиков);
  • Добавляет интересную механику (приходится смотреть, куда идёшь, чтобы не выстрелить в прохожего).
• Остановка времени:
  • Добавляет вариативность в геймплей (можно делать разные уровни: медленные задумчивые головоломки или шустрый шутер);
  • Смягчает сложность от автоматической стрельбы;
  • Позволяет контролировать динамику как мне (через level design), так и игроку.

Постепенно идея визуализируется и обрастает деталями. Отметаю одну за другой, хватит на сегодня.

Todo: сделать крохотный прототип и проверить, насколько фаново будет двигаться/стрелять с остановкой времени.

Level 1.2. Микропрототип.

Спасибо Unity3D, прототипирование на нём очень простое.
Добавляю пару стен с BoxCollider2D, круглые спрайты с RigidBody2D и CircleCollider2D (игрок, прохожие и бандиты). Пули — тот же спрайт, только маленький, красный, с RigidBody2D, CircleCollider2D и TrailRenderer для траектории полёта.

Управление временем делаю через свой класс Clock, все прочие классы (игрок, пуля и тд) используют дельту времени из него, а не Time.DeltaTime.

using UnityEngine;
using System.Collections;

public class Clock : MonoBehaviour {
    [SerializeField, Range(0, 2)] float stepDuration;
    [SerializeField] AnimationCurve stepCurve;

    float time = -1;
    float timeRatio = 0;
    float defaultFixedDeltaTime = 0;

    static Clock instance;

    public static Clock Instance { get { return instance; } }

    void Start() {
        instance = this;
        defaultFixedDeltaTime = Time.fixedDeltaTime;
    }

    void OnDestroy() {
        if (instance == this)
            instance = null;
    }

    public bool Paused {
        get { return time < 0; }
    }

    public float DeltaTime {
        get { return 
            timeRatio * Time.deltaTime; }
    }

    public float FixedDeltaTime {
        get { return 
            timeRatio * Time.fixedDeltaTime; }
    }

    public void Play() {
        if (!Paused)
            return;

        time = 0;
        timeRatio = Mathf.Max(0, stepCurve.Evaluate(0));
        UpdatePhysicSpeed();
    }

    public void Update() {
        if (Paused)
            return;

        time = Mathf.Min(time + Time.unscaledDeltaTime, stepDuration);

        if (time >= stepDuration) {
            timeRatio = 0;
            time = -1;
            UpdatePhysicSpeed();
            return;
        }

        timeRatio = Mathf.Max(0, stepCurve.Evaluate(time / stepDuration));
        UpdatePhysicSpeed();
    }

    void UpdatePhysicSpeed() {
        Time.timeScale = timeRatio;
        Time.fixedDeltaTime = defaultFixedDeltaTime * timeRatio;
    }

}

Самый базовый прототип готов через полтора часа, полно багов:

1. Движение игрока и пули сделано через transform.position, а не velocity, поэтому игрока колбасит, когда он упирается в стены;
2. Остановка времени не останавливает физику (не меняется fixedDeltaTime), поэтому в режиме паузы персонажи чуть-чуть двигаются (выталкиваются друг из друга).

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

Первый играбельный прототип

Но уже появляются таски на следующий день:
Фишки:

1. Добавить "отражающие" стены, от которых пуля будет рикошетить;
2. Добавить уничтожение ботов при столкновении с пулей (пока они этого не умеют);
3. Добавить гибкое управление временем (сейчас есть длительность и кривая для "скорости течения времени", но это неудобно).

Фиксы:

1. Переделать движение на изменение velocity, а не transform.position;
2. Запрещать создавать пули в стенах (Игрок упирается в стену, стреляет, пуля сразу же убивает игрока).

Todo: сделать тестовый обучающий уровень с придуманными фишками.

Level 1.3. Первая карта.

Пока шёл по улице, придумал план тестового уровня:

1. Безопасная зона. Игрок учится ходить, все пули уходят в стены;
2. Узкий коридор с неактивным врагом. Игрок идёт по коридору и понимает, как атаковать;
3. Расширение коридора с неактивным бандитом и парой прохожих. Расширение — после поворота, поэтому игрок не может случайно попасть в прохожего;
4. Поворот в виде перископа, вместо зеркала — отражающая стена, за поворотом — неактивный враг. Игрок стреляет в стену, видит, как работает рикошет;
5. Коридор с зеркальными стенами, врагами и прохожими. Игрок аккуратно проходит по коридору, стараясь не попасть в прохожих (или стреляет в них, если хочет);
6. Песочница.

Закидываю объекты на сцену, перекрашиваю отражающие стены в жёлтый. Получается что-то такое:

Вид обучающего уровня

Делаю отражающие стены через отдельный слой, код столкновения пули с препятствием становится таким:

void OnCollisionEnter2D(Collision2D coll) {
    int layer = 1 << coll.gameObject.layer;

    if (layer == wall.value)
        Destroy(gameObject);
    else if (layer == human.value) {
        Destroy(gameObject);

        var humanBody = coll.gameObject.GetComponent<Human>();

        if (humanBody != null)
            humanBody.Kill();

        return;
    } else if (layer == wallMirror.value) {
        Vector2 normal = Vector2.zero;

        foreach (var contact in coll.contacts)
            normal += contact.normal;

        direction = Vector2.Reflect(direction, normal);
    }
}

Исправляю баги, добавляю придуманные за прошлый день фишки.
Переделываю класс Clock: раньше ход длился stepDuration реальных секунд, а коэффициент скорости времени определялся кривой stepCurve. Кривая нужна для плавного старта и завершения хода.

Старые настройки в Clock.cs

Вот только если изменить длительность хода, изменится и длительность начала/конца (где значение ординаты на кривой не равно 1). И при слишком небольшой длительности хода "включение" времени кажется слишком резким, а при длительности порядка секунды — слишком медленным (т.к. кривая "растягивается" на всё время хода). Добавляю отдельные кривые для начала и конца хода, а также длительности начала/конца.

Добавляю камеру, которая следит за игроком и визуализацию траектории игрока.

Молча показываю прототип нескольким знакомым, не объясняя ни цель, не управление. Все смогли разобраться с управлением, но есть и проблемы, которых я не замечал. Для себя записал выводы playtest'а:

1. Сложно целиться. Я использую дельту между последними двумя позициями пальца, нужно бы брать больше значений;
2. Палец устаёт свайпать по экрану. Решается длительностью хода, левелдизайном;
3. Иногда пропадает сделанный свайп. Люди начинают делать свайп, когда ход ещё не кончился и часто отпускают палец, пока останавливается текущий ход. Т.к. во время хода менять направление нельзя, жест тратится впустую. Решается хитрым кодом (каким — ещё не знаю);
4. Было бы круто сделать собираемые объекты, которые разрушаются от пуль. К ним нужно подойти, но не по прямой;
5. Рикошеты добавляют интереса: можно устроить безумный bullet storm;
6. Игроки не различают прохожих и врагов. Лечится артом;

Прототип готов настолько, что можно показать геймплей!

Todo: определиться с сеттингом, графикой.

Level 1.boss [100hp]. Выбор сеттинга и визуального стиля.

Моим первым "боссом" оказался именно этот этап, вот уж не думал.
Планировал я следующее: прошерстить интернет на тему популярных игровых сеттингов, поискать референсы и арт для вдохновения, и начать рисовать уровни в пиксельарте.

После некоторого гугления решил остановиться на антураже викторианской Англии. Папоротники, культ смерти, мрачные доки. Дерево, металл, пар и масло.

Пробую нарисовать первые спрайты и обнаруживаю проблему. Все объекты в игре могут вращаться. А пиксели, как известно, нет.
Отрисовать по 360 вариантов каждого спрайта, очевидно, не вариант. К счастью, сейчас возникла мода не "нечестный пиксельарт", когда спрайты свободно вращаются вокруг своей оси. В этом случае нужно что-то делать с лесенками алиасинга, которые неизбежно появятся, высунут хищные угловатые мордочки и будут мелькать тут и там. Можно смириться и сказать: "Это и есть мой стиль!", как сделали создатели Hotline miami (и ведь получилось!). Можно подключить антиалиасинг: "Да здравствует мыло душистое!".
Во всяком случае, у меня так и получилось: либо алиасинг и лесенки, либо нечёткие грани после антиалиасинга.

Тестовый пиксельарт

Отметаю пиксельарт (прости, друг!) и упрощаю, упрощаю!

Todo: выбрать подходящий визуальный стиль.

Level 1.boss [75hp]. Переход к 3D.

Город из бумаги! Похожий немного на Wildfire worlds, только ещё проще. Благородные белые грани шершавой бумаги, пятна краски на полу, вот такие персонажи в смешных шляпах:

Цилиндрический чел

По правде говоря, с 3д в геймдеве я никогда не работал, а 3д редакторы открывал последний раз несколько лет назад. Но знаю, что многое решается освещением и тенями. Особенно, если текстура — белая бумага, где толком не скроешь недостатки плохого света.

Трачу вечер на моделирование первого объекта: пакета молока. Разбираюсь со стандартными шейдерами, освещением.
Вывод простой: не потяну. Я трачу очень много времени на моделлинг и не могу получить красивую картинку стандартными средствами. Запекание освещения помогает, но я хотел сделать небольшую игрушку с множеством уровней, так что запекание в пролёте. Похоже, босс ещё не побеждён...

Пакет молока с простым освещением

Level 1.boss [15hp]. Procedural generation.

Вспоминаю свои сильные и слабые стороны. Обычно, если я не могу нарисовать какой-нибудь арт для своего проекта, я пишу скрипт, который сделает это за меня. Чем 3д хуже? Итак, процедурная генерация! Базовые примитивы, фактически, low poly. Яркие, контрастные цвета, визуально кодирующие геймплейные различия.

Нужно определиться, какие примитивы мне понадобятся для создания уровней. Цилиндры и кубы, возможно, пятиугольники… Хм, это ведь все можно генерировать одним кодом. За работу!

Todo: реализовать простую генерацию примитивов.

Level 2.1. Правильные многоугольники в 2D.

Пока для уровня будет достаточно правильных многоугольников. Для начала я решил попробовать в 2д, перевёл камеру в ортогональный режим и создал элементы из двух кусочков:

• Тело (просто правильный многоугольник) белого цвета;
• Цветное кольцо вокруг, показывающее цветом тип объекта (как будет вести себя пуля при коллизии).

Немножко стенсильной магии, чтобы не было видно колец внутри других многоугольников и получаем такого зайку:

Зайка

И тут завертелось!
Добавил стандартную клеточную текстуру на тело, подобрал цвета и наконец не удержался и подключил мои любимые тени (о них я уже как-то писал).

Просто и аккуратно.

Делюсь скрином с девушкой и получаю резонный фидбек: тень, падающая с высокого объекта на более низкий имеет искажения, изломы. Согласен, я постоянно такое вижу в реальном мире. Пробую нарисовать на бумаге и понять, как должны эти искажения выглядеть. И тут понимаю: какие искажения, если камера — ортогональная?

Слева тени при перспективной камере, справа при ортогональной

Получается, мои красивые тени только подчёркивают плоский вид карты. Время возвращаться в 3D.

Level 2.2. Правильные многоугольники в 3D.

Честно говоря, процедурная генерация в 3D для меня совершенно новый опыт. С другой стороны, он ничем не должен отличаться от 2D.

Для начала определился с настройками конкретного многоугольника:

1. height — Высота;
2. edges — Количество граней;
3. size — Vector2D, позволяет задать размер многоугольника или растянуть его по одной из осей;
4. isCircle — Цилиндр ли это? Если да, количество граней выставляется автоматически, исходя из радиуса, а size.y становится равным size.x.

И с общими настройками, которые будут одинаковы для одного типа игровых объектов:

1. Цвет "потолка";
2. Цвет границы;
3. Ширина границы;
4. Минимальное количество граней в цилиндре;
5. Отношение количества граней в цилиндре к 1 юниту периметра.

Теперь самое время создавать эти многоугольники. Я разбил каждый на 3 меша:

1. Body — верхнее основание;
2. Border — цветное кольцо на верхнем основании;
3. Side — боковая поверхность;

Нижнее основание нет смысла генерировать, т.к. объекты не могут поворачиваться по осям x или y, а камера всегда находится над картой.

Получаем вот такие многоугольники

Время для оптимизаций:
Во первых, я постоянно рассчитываю единичные вектора, повёрнутые на определённые углы.
Заводим класс AnglesCache с одним публичным методом:

namespace ObstacleGenerators {
    public class AnglesCache {
        public Vector3[] GetAngles(int sides);
    }
}

Далее, кеширую все 3 типа мешей, в качестве ключей использую значимые параметры (количество сторон, цвет, круг ли это и т.д.). Цвет сохраняю в вершины, это позволит использовать для мешей один материал и, как следствие, динамический батчинг.

Правда теперь возникла проблема с границами и стенсилом: раньше я объединял границы с помощью стенсила, теперь, когда появился объём, этот подход даёт плохие результаты:

Границы более высоких цилиндров не рисуются, т.к. под ними отрисованы основания низких цилиндров

Перестаю пользоваться стенсил буфером. Теперь все границы обязательно отрисовываются:

Без стенсил буфера

И наконец, меняю в шейдере границ настройки ZTest с On (LEqual) на Less. Теперь границы не будут рисоваться поверх оснований цилиндров с такой же высотой. В результате получаю аккуратное объединение границ, которое корректно работает с объектами разной высоты:

Объединение границ через настройки ZTest'а

Наконец, последние штрихи:

1. В качестве uv координат для оснований цилиндров использую мировые координаты. У всех объектов получается общая текстура без швов;
2. Крашу боковую поверхность в высветленный цвет границы;
3. Добавляю к шейдеру боковой поверхности _fixed3 _LightPosition, чуть-чуть освещаю боковые поверхности (классический метод тонирования Гуро). Тут, кстати, пригодился флаг isCircle в объектах: если он не установлен, у каждого треугольника уникальные вершины, если установлен — вершины общие. В результате нормали интерполируются и для isCircle получается сглаженная поверхность.

Освещение, сглаживание, шейдеры и мировые uv координаты. (Освещение выкручено посильнее для наглядности)

Последний штрих — генерируем для многоугольников PolygonCollider2D нужной формы.
Итого: трёхмерные многоугольники с физикой и аккуратным lowpoly стилем.

Todo: тени.

Level 3.1. Тени.

Конечно, теперь прежние двумерные тени не подойдут:

Плоские тени выглядят странно, т.к. не учитывают объёмность объекта

А должны они выглядеть примерно вот так:

Более реалистичные тени

"Ну в в чём проблема?" — Спросите вы. "В Unity3D есть отличные тени!".
Действительно, есть. Вот только для построения теней используется алгоритм Shadow mapping. В двух словах: Если мы посмотрим на сцену из источника света, то все объекты, которые нам видны — освещены, а те, которые чем-то закрыты — в тени. Мы можем создать теневую карту, расположив камеру в координатах источника света и отрендерив сцену (в z-buffer'е окажутся данные расстоянии до источника света). Проблема в перспективном искажении. Чем дальше объекты от источника света, тем больше экранных пикселей соответствует текселям из теневой карты.
Т.е. тени не "pixel perfect", это не их фишка, куда важнее, что они очень быстрые. Обычно в искажениях нет проблемы, так как тени накладываются на сложные объекты с текстурой, в результате небольшая потеря качества не заметна. Но у меня очень светлые текстуры, очень мало полигонов, поэтому низкое качество теней прекрасно видно.

Впрочем, есть неплохое решение. Называется алгоритм "Shadow volume" и он очень похож на те двумерные тени, что я делал в прошлых статьях.
Пусть у нас есть некий меш, который должен отбрасывать тени от источника света.

1. Мы находим его силуэтные грани (те грани, которые разделяют освещённую часть меша и не освещённую);
2. "Вытягиваем" их от источника света (каждая грань превращается в 2 треугольника).
3. Рисуем все эти вытянутые грани (в color buffer не пишем ничего, из z-buffer'а только читаем, а вот в стенсил пишем):
   3.1. Если нормаль треугольника направлена на камеру (front): добавляем в стенсил буфер единицу;
   3.1. Если нормаль треугольника направлена от камеры (back): вычитаем из стенсил буфера единицу.

Получается, что если мы 1 раз "вошли" в тень (пересекли front треугольник) и один — "вышли" (пересекли back треугольник) — значение в стенсиле будет равно $inline$-1 + 1 = 0$inline$ и пиксель освещён. Если же мы вошли в тень большее количество раз, чем вышли (когда, перед между front и back находится какой-то треугольник, который отрисовался и записал данные в z-buffer) — пиксель в тени и его освещать не нужно.

Итак, нужно получить теневые меши от объектов, пройтись шейдером, добавив в стенсил нужные данные, а затем, отрисовать тень там, где в стенсиле ненулевое значение. Звучит как задача, решаемая на шейдерах!

Todo: генерация теней на шейдерах.

Level 3.2. Тени в вертексном шейдере.

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

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

Судите сами: нам не нужно отрисовывать все грани, только силуэтные (те, которые разделяют свет и тень). Значит, нам нужно для каждой вершины в вершинном шейдере:

1. Найти положение предыдущей грани;
2. Расчитать значения A, B, C для прямой, проходящей через текущую и предыдущую грань;
3. Определить, с какой стороны от прямой находится центр многоугольника;
4. Определить, с какой стороны от прямой находится источник света;
5. Повторить пункты 1-4 для следующей грани;
6. Сравнить значения — если одна из граней на свету (центр и источник в разных полуплоскостях), а другая в тени — данная вершина силуэтная и её нужно отрисовывать;
7. Узнать, нужно ли вытягивать текущую вершину, или она лежит на самом цилиндре;
8. Если вытягивать нужно, найти позицию вершины в мировых координатах, получить направление от источника света и переместить её по этому направлению на некое расстояние (например, 100 юнитов);

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

Представьте себе, работает!
Однако, этот способ создания теней содержит столько фатальных недостатков, что грустно становится:

1. Огромное количество вершин и треугольников. Чаще всего тень состоит из двух боковых граней, половины нижних и половины верхних граней. Для 32х угольного цилиндра и бесконечно удалённого источника света получается точек и треугольников. Вместо этого я отдаю на видеокарту 256 треугольников и 512 вершин.
2. Не работает батчинг. Для расчёта теней в вершинах должна тем или иным образом храниться информация о соседних вершинах (позиции и нормали). Соответственно, данные завязаны на локальные координаты в пространстве меша. При батчинге множество мешей объединяются (при этом меняется система координат на мировую) и теперь вершины уже не обладают информацией о положении соседних точек.

Большое количество вершин оказалось неприятным следствием выбранного метода, но сломаный батчинг забил последний гвоздь: 100-200 draw call'ов на тени для мобильного устройства — неприемлемый результат. Судя по всему, придётся переводить расчёты теней на CPU. Однако, так ли это плохо, как кажется? :)

Todo: перенести генерацию теней на CPU.

Level 3.2. Генерация теней на cpu.

Начну с решения в лоб.

1. Для каждой вершины:
   1.1. Получить уравнение прямой проходящей через текущую и предыдущую вершину;
   1.2. Проверить с одной ли стороны находятся центр многоугольника и источник света;
   1.3. Взять результаты для предыдущей вершины и сравнить с текущей;
   1.4. Если предыдущая грань освещена, а текущая — нет, сохранить вершину как силуэтную (lightToShadowIndex);
   1.5.1 Если предыдущая грань в тени, а текущая на свету, сохранить вершину как силуэтную (shadowToLightIndex);

2. Верхнее основание цилиндра:
   2.1. Для каждой грани от вершины lightToShadowIndex до вершины shadowToLightIndex добавить в список полигонов тени 2 треугольника (помните, каждую грань мы превращаем в 4х-угольник, где 2 вершины лежат на цилиндре, а 2 — вытягиваются, создавая тень);

3. Нижнее основание цилиндра:
   3.1 Для каждой грани от вершины shadowToLightIndex до вершины lightToShadowIndex добавить в список полигонов тени 2 треугольника;

4. Боковая поверхность цилиндра:
   4.1 Добавляем теневые треугольники для боковых граней под индексами shadowToLightIndex и lightToShadowIndex;

Парочка замечаний:
Если источник находится над цилиндром, боковых силуэтных граней не будет вовсе (зато будет целая тень от верхнего основания).
Стоит ввести ограничения на положение источника света: если он окажется внутри цилиндра, тени станут некорректными.

Алгоритм работает, пришло время для оптимизаций. На данный момент, чтобы обеспечить 60fps при 10 объектах, нужно рассчитать 600 мешей за секунду. (Если не впечатлило — 6к за 10 секунд).

Todo: Оптимизация теней, 60fps с включёнными тенями на моём nexus 5.

Level 3.3. Оптимизации теней.

Удаляю лишнее:
Самое очевидное — большинство цилиндров стоит на полу, а источник света всегда над полом. Перестаю генерировать тень от нижнего основания, если объект не висит в воздухе.

Меньше тригонометрии:
Избавляюсь от вездесущих синусов и косинусов. Воспользуюсь классом AnglesCache, описанным выше. Для любознательных вот его полный код:

using UnityEngine;
using System.Collections.Generic;

namespace ObstacleGenerators {
    public class AnglesCache {
        List<Vector2[]> cache;
        const int MAX_CACHE_SIZE = 100;

        public AnglesCache () {
            cache = new List<Vector2[]>(MAX_CACHE_SIZE);

            for (int i = 0; i < MAX_CACHE_SIZE; ++i)
                cache.Add(null);
        }

        public Vector2[] GetAngles(int sides) {
            if (sides < 0)
                return null;

            if (sides > MAX_CACHE_SIZE)
                return GenerateAngles(sides);

            if (cache[sides] == null)
                cache[sides] = GenerateAngles(sides);

            return cache[sides];
        }

        public float AngleOffset {
            get { return Mathf.PI * 0.25f; }
        }

        Vector2[] GenerateAngles(int sides) {
            var result = new Vector2[sides];

            float deltaAngle = 360.0f / sides;
            float firstAngle = AngleOffset;

            var matrix = Matrix4x4.TRS(Vector2.zero, Quaternion.Euler(0, 0, deltaAngle), Vector2.one);
            var direction = new Vector2(Mathf.Cos(firstAngle), Mathf.Sin(firstAngle));

            for (int i = 0; i < sides; ++i) {
                result[i] = direction;
                direction = matrix.MultiplyPoint3x4(direction);
            }

            return result;
        }
    }
}

Расширяю кеш:
Кеширую коэффициенты прямых (для расчёта освещённости граней). Теперь для поиска силуэтных граней достаточно получить позицию источника света в локальных координатах многоугольника, а затем пройтись по предрасcчитанному массиву прямых.

Убираю медленные операции:
Вместо использования Transform.TransformPoint в циклах использую матрицу transform.localToWorldMatrix и MultiplyPoint3x4.
Избавляюсь от неявных преобразований из Vector3 в Vector2 (куда дешевле кешировать трёхмерные вектора, чем делать каст внутри циклов), в большинстве случаев напрямую присваиваю компоненты вектора, а не сами вектора:

Vector2 v2;
Vector3 v3;

// присвоение компонент куда быстрее, 
v2.x = v3.x;
v2.y = v3.y;
// чем вызов функции
v2.Set(v3.x, v3.y);
// и в разы быстрее, чем неявный каст
v2 = v3;

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

Оптимизирую поиск граней:
Ещё одна крупная оптимизация. Очень много времени тратится на поиск силуэтных граней, однако, чаще всего тень рассчитывается для очень простой конфигурации:

1. Многоугольник правильный (size.x == size.y);
2. Источник света достаточно удалён от многоугольника.

По сути, правильный многоугольник — аппроксимация для окружности. А рассчитать силуэтные точки на грани — элементарно.

Алгоритм прост:

1. Проверяем, можем ли использовать быстрый поиск граней: size.x == size.y и источник света находится снаружи описанной окружности многоугольника;
2. Находим направление от источника света до центра многоугольника:

   direction = lightPosition - obstacleCenter;

3. В прямоугольном треугольнике LCT (L — источник света, C — центр окружности, T — любая из двух касательных, проходящих через L) нам известны длины LC, CT (радиус). Рассчитываем deltaAngle — угол между LC и CT;
4. Считаем directionAngle — угол (относительно оси OX) прямой LC;
5. Считаем firstAngle, secondAngle — углы между центром окружности и точкой касания LT:

   firstAngle = directionAngle - deltaAngle;
   secondAngle = directionAngle + deltaAngle;

6. Дискретизируем полученные углы, шаг — 360° / edges, смещение — поворот многоугольника по оси z:

   fromLightToShadow = Mathf.FloorToInt(firstAngle / pi2 * edges + edges) % edges;
   fromShadowToLight = Mathf.FloorToInt(secondAngle / pi2 * edges + edges) % edges;

7. Силуэтная точка на описанной окружности лежит между двумя точками на многоугольнике, одна из которых является силуэтной. Но просто получить её, округлив firstAngle до ближайшего целого не получится: чем ближе источник цвета к многоугольнику, тем сильнее сказывается разница между описанной окружностью и самой фигурой. Поэтому проверяем, освещена ли грань, следующая за найденной точкой (fromLightToShadow и fromShadowToLight), при необходимости выбираем следующую за ней грань:

   if (linesCache[fromLightToShadow].HalfPlainSign(lightPosition) < 0)
   fromLightToShadow = (fromLightToShadow + 1) % edges;
   if (linesCache[fromShadowToLight].HalfPlainSign(lightPosition) >= 0)
   fromShadowToLight = (fromShadowToLight + 1) % edges;

В результате получаем индексы силуэтных вершин. Из тяжёлых операций — несколько тригонометрических преобразований (Acos, Atan2) и расчёт длины вектора. Зато — ни одного цикла. Куда понятнее станет, если посмотреть видео. Обратите внимание, что правильная силуэтная вершина не всегда ближайшая к силуэтной точке на описанной окружности:

Работа алгоритма быстрого поиска силуэтных вершин.

bool CanUseFastSilhouette(Vector2 lightPosition) {
    if (size.x != size.y || edgesList != null)
        return false;

    return (lightPosition - (Vector2)transform.position).sqrMagnitude > size.x * size.x;
}

bool FindSilhouetteEdges(Vector2 lightPosition, Vector3[] angles, out int fromLightToShadow, out int fromShadowToLight) {
    if (CanUseFastSilhouette(lightPosition))
        return FindSilhouetteEdgesFast(lightPosition, angles, out fromLightToShadow, out fromShadowToLight);

    return FindSilhouetteEdges(lightPosition, out fromLightToShadow, out fromShadowToLight);
}

bool FindSilhouetteEdgesFast(Vector2 lightPosition, Vector3[] angles, out int fromLightToShadow, out int fromShadowToLight) {
    Vector2 center = transform.position;
    float radius = size.x;

    Vector2 delta = center - lightPosition;
    float deltaMagnitude = delta.magnitude;

    float sin = radius / deltaMagnitude;
    Vector2 direction = delta / deltaMagnitude;

    float pi2 = Mathf.PI * 2.0f;
    float directionAngle = Mathf.Atan2(-direction.y, -direction.x) - anglesCache.AngleOffset - transform.rotation.eulerAngles.z * Mathf.Deg2Rad;
    float deltaAngle = Mathf.Acos(sin);
    float firstAngle = ((directionAngle - deltaAngle) % pi2 + pi2) % pi2;
    float secondAngle = ((directionAngle + deltaAngle) % pi2 + pi2) % pi2;

    fromLightToShadow = Mathf.RoundToInt(firstAngle / pi2 * edges - 1 + edges) % edges;
    fromShadowToLight = Mathf.RoundToInt(secondAngle / pi2 * edges - 1 + edges) % edges;

    return true;
}

Оптимизирую меш:
Так как теперь все расчёты происходят на cpu, можно использовать общие точки для смежных граней. Так, например, для цилиндра с 32мя гранями и далёким источником света, когда освещена половина цилиндра, получаю 42 вершины и 36 треугольников (сравните с 512 вершинами и 256 треугольниками при расчётах на gpu).

Сокращаю количество вызовов:
Если силуэтные грани не изменились, не нужно и перерассчитывать меш. А они довольно часто остаются неизменными — при небольших перемещениях источника света или многоугольника меняется только направление "вытягивания" тени. Сравниваю индексы силуэтных граней с их предыдущим значением и не рассчитываю тень, если в этом нет необходимости.

Ещё сильнее сокращаю количество вызовов:
Если не изменились x и y координаты у источника света (высота света не повлияет на силуэтные грани) и позиция многоугольника — не расcчитываем вообще ничего, даже силуэтные грани.

Рассчитываю bounding box:
Стандартный Mesh.RecalculateBounds для тени не подойдёт — ведь она вытягивается искусственно в шейдере. Попробую рассчитать AABB для тени самостоятельно.

Очередной нумерованный список:

1. Беру 4 точки на описанной окружности: две пересечении с прямой circleCenter — lightPosition, две на пересечении с перпендикуляром этой прямой;
2. Добавляю ещё 4 точки — копии первых 4-х, но смещённых по z на высоту многоугольника (все 8 точек в сумме — прямоугольный параллелепипед, описанный вокруг нашего многоугольника);
3. Для каждой точки получаю направление от источника света до текущей точки.
4. Продлеваю эту прямую до пересечения с полом (тут все просто, у него z == 0)
5. Получаю минимальные и максимальные значения координат для всех 16 точек — исходных, лежащих на параллелепипеде и их проекции на пол;
6. Эти координаты как раз описывают AABB тени.

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

Вид сверху (только нижние точки)

Вид сбоку (только нижние точки)

Bounding box приподнятых над землёй (нижние точки тоже рассчитываются) многоугольников

Теперь те тени, которые не попадают на экран, будут отсекаться.

Заключение

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

Судя по ощущениям, скорость написания статьи примерно в полтора раза медленнее, чем написание проекта, поэтому материала для следующей части накопилось достаточно. Однако, я не буду спойлерить, лучше подведу итоги:

1. Я определился с основной игровой механикой и проверил её в прототипе;
2. Разобрался с визуальным стилем и поддержал его в коде;
3. Реализовал механику и визуализацию.

Несколько выводов по процессу разработки:

1. Я выбрасываю все лишние идеи и стараюсь не усложнять, но процедурная генерация тратит довольно много времени, это значительный минус;
2. Радуют возможности отладки и профилирования — они сохранили очень много времени;
3. Простое 3д — вполне подходящая ниша для человека, не умеющего моделировать;
4. Школьный курс геометрии — неимоверно полезная вещь.
5. Старайтесь визуализировать все алгоритмы (например, через Gizmos), это позволяет найти ошибки на ранних этапах.

Спасибо за внимание, встретимся в комментариях и следующей статье! :)

Автор: nightrain912

Источник