Усатый стрелок с полигональным пузом. Часть вторая

в 8:16, , рубрики: C#, gamedesign, lloyd relaxation, lowpoly, posteffects, procedural generation, shadow volumes, shadows, triangulation, unity3d, voronoi diagram, разработка игр, Разработка под android

Усатый стрелок с полигональным пузом. Часть вторая - 1

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

А теперь, когда опубликована вторая часть, материала достаточно и для третьей части! :)

Сегодня в программе: смесь визуала и архитектуры проекта. Но сначала, ещё парочка деталей про тени.
Итак, поехали!

Статьи

Оглавление

Усатый стрелок с полигональным пузом. Часть вторая - 2Level 3.4. Менеджер теней.

Как вы помните, тени уже генерируются на CPU с кучей оптимизаций. А вот их отрисовку нужно доработать. Пока я разбирался с генерацией, мне нужен был самый простой способ рендеринга, поэтому всё работает так:

  1. У каждого объекта, отбрасывающего тень, два потомка, которые рендерят тени с разными шейдерами (один только back — грани, другой — front);
  2. На сцене лежит огромный спрайт, который отрисовывается самым последним, и подкрашивается в нужный цвет, если в стенсиле ненулевое значение.

Догадываетесь, какие проблемы это вызывает?

  1. Самое простое — дублирование объектов (по два одинаковых потомка у каждого элемента). Избавиться от них, сделав двухпроходный шейдер — не вариант, т.к. объекты с многопроходными шейдерами не умеют батчиться;
  2. Далее, возможность сделать только один источник света с тенями;
  3. Очень скупые возможности по работе со светом (т.к. по сути, света и нет, только тень). Так что сделать цветную тень можно, а цветное освещение — нет;
  4. Стенсил буфер занят целиком и его не получится использовать для других эффектов.

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

  • LightSource, фонарик с бесконечной дальностью, настройкой цветов тени и освещения;
  • IShadowSource, интерфейс с функцией пересчёта тени void RebuildShadow(Vector3 lightPosition);
  • ShadowRenderer, который регистрирует все источники света и теней и умеет рендерить тени.

Код написан, шейдеры проверены, можно двигаться дальше. И тут начались проблемы.
Косяки с тенями
Забагованные тени.
На изображении выше целых две проблемы.
Во-первых, тени слишком длинные и иногда неправильно перекрывают объекты. Такое может быть, если тени рендерятся поверх пустого z-buffer'а (другие объекты могут перекрывать тень, но сами тени в z-buffer ничего не пишут).
Во-вторых, тени в каком-то странном шуме. Такое бывает, если работать с неочищенным буфером.

Итак, проблема в том, что z-buffer, с которым я работаю, судя по всему, не использовался камерой. Рендеринг кадра сейчас работает так:

  1. Рендеринг сцены в RenderTexture;
  2. Рендеринг тени, depth-buffer берётся из п.1, а color-buffer свой (об этом ниже);
  3. Композинг теней и отрендереной сцены;
  4. Постэффекты.

Про раздельное использование буферов.

Когда работаешь с постэффектами зачастую нужно с помощью какого-то шейдера преобразовать текстуру. В Unity3D для этого есть метод Graphics.Blit. Мы передаём в него исходную текстуру, указываем target — куда отрисовывать, материал и даже проход шейдера.
По сути, мы работаем минимум с тремя различными буферами:

  1. Исходный color buffer, откуда мы читаем цвета пикселей;
  2. Целевой color buffer, куда мы пишем цвета;
  3. Depth+stencil buffer, в который мы пишем (и из которого читаем глубину и данные стенсила).

И в методе Graphics.Blit целевой color buffer и depth buffer неразделимы. Т.е., если нам нужно, например, читать глубину геометрии сцены из исходной текстуры, а записывать пиксели в целевую — облом.
Или если мы сделали рендеринг сцены в текстуру, при этом часть шейдеров записала данные в стенсил, а теперь хотим получить новую текстуру, воспользовавшись этими данными (и сохранив исходную текстуру!) — тоже облом.

Выход есть и в документации Unity3D об этом прямо сказано:

Note that if you want to use depth or stencil buffer that is part of the source (Render)texture, you'll have to do equivalent of Blit functionality manually — i.e. Graphics.SetRenderTarget with destination color buffer and source depth buffer, setup orthographic projection (GL.LoadOrtho), setup material pass (Material.SetPass) and draw a quad (GL.Begin).

В общем, модифицированная версия Blit, позволяющая разделить передачу буферов:

static void Blit(RenderBuffer colorBuffer, RenderBuffer depthBuffer, Material material) {
    Graphics.SetRenderTarget(colorBuffer, depthBuffer);

    GL.PushMatrix();
    GL.LoadOrtho();

    for (int i = 0, passCount = material.passCount; i < passCount; ++i) {
        material.SetPass(i);

        GL.Begin(GL.QUADS);
        GL.TexCoord(new Vector3(0, 0, 0));
        GL.Vertex3(0, 0, 0);
        GL.TexCoord(new Vector3(0, 1, 0));
        GL.Vertex3(0, 1, 0);
        GL.TexCoord(new Vector3(1, 1, 0));
        GL.Vertex3(1, 1, 0);
        GL.TexCoord(new Vector3(1, 0, 0));
        GL.Vertex3(1, 0, 0);
        GL.End();
    }

    GL.PopMatrix();

    Graphics.SetRenderTarget(null);
}

Использование в коде:

void RenderShadowEffect(RenderTexture source, RenderTexture target, LightSource light) {
    shadowEffect.SetColor("_ShadowColor", light.ShadowColor);
    shadowEffect.SetColor("_LightColor", light.LightColor);
    shadowEffect.SetTexture("_WorldTexture", source);
    shadowEffect.SetTexture("_ShadowedTexture", target);

    Blit(target.colorBuffer, source.depthBuffer, shadowEffect);
}

Итак, в чем же дело? Почему моя RenderTexture, в которую я рендерю камеру на выходе совершенно пуста (и даже не очищена от мусора)?
Выключаю тени и смотрю, что показывает frame debug:
Усатый стрелок с полигональным пузом. Часть вторая - 4
Усатый стрелок с полигональным пузом. Часть вторая - 5
Странные рендер-текстуры.
Любопытно. Судя по всему, постэффект антиалиасинга принудительно переводит камеру на рендеринг в свою текстуру. При этом доступа до этой текстуры у меня нет: при дебаге в Camera.аctiveTexture пустая.
Ах, так, антиалиасинг! Лезешь в мою последовательность отрисовки? Тогда я залезу в твой код!
Постэффекты работают через метод MonoBehaviour.OnRenderImage, а я через MonoBehaviour.OnRenderImage и
MonoBehaviour.OnPostRender. Делаю грязный хак: переименовываю OnRenderImage в Apply и вызываю его руками, после рендеринга теней, с моими renderTexture. Теперь антиалиасинг не мешает теням.

Новые тени позволяют делать смешные, но не очень нужные штуки вроде хроматической aберрации или гладких теней.
Усатый стрелок с полигональным пузом. Часть вторая - 6
Сотня обычных бледных теней с небольшим смещением.
Усатый стрелок с полигональным пузом. Часть вторая - 7
Три цветных тени.

Пока тени притормаживают на мобилках (съедают примерно 10 — 15 лишних fps). Если все будет грустно, переведу под конец все в однопроходную отрисовку, а пока не буду налегать на источники света.

Хинт: импровизируйте в отладке графики! Отлаживать вертексные шейдеры бывает больно, поэтому визуализируйте все данные, которые сможете: вытягивайте вертексы вдоль нормалей, добавляйте цвет и прозрачность и т.д.
Усатый стрелок с полигональным пузом. Часть вторая - 8
Дебажная визуализация через шейдеры и гизмо.

Оказалось, что добавлять новые классы стало тяжелее из-за некоторых неудачных проектных решений.
Todo: почистить архитектуру и код проекта.

Усатый стрелок с полигональным пузом. Часть вторая - 9Level 4.1. Рефакторинг архитектуры.

Как вы помните, я развиваю проект с прототипа. Но тянуть все прототипную архитектуру (знаете, какая архитектура в прототипах, написанных за 2 часа?) не хочется, значит, нужен рефакторинг.
Итак:
Для начала выношу как можно больше данных из MonoBehaviour в ScriptableObject. Это всяческие стили, настройки, библиотека префабов;
Усатый стрелок с полигональным пузом. Часть вторая - 10
Настройки проекта.

Разбиваю всю логику на маленькие классы, например, BulletCaster или MovableObject. Каждый из них содержит в себе нужные настройки и преследует только одну цель.

Эти классы обладают очень простым интерфейсом.

public class BulletCaster : MonoBehaviour {
    public void CastBullet(Vector2 direction);
}

public class MovingBody : MonoBehaviour {
    public Vector2 Direction {get; set;}
    public bool IsStopped {get; set;}
}

Усатый стрелок с полигональным пузом. Часть вторая - 11
Из микроклассов можно собрать сложную логику.

Убираю прямые зависимости от синглтонов (Clock, ShadowManager и т.д.) и реализую паттерн service locator (несколько спорная вещь, но куда аккуратнее, чем россыпь синглтонов).

Реализую обработку столкновений через слои, оптимизирую их, явно убирая невозможные столкновения (например, статика <-> статика).

Оптимизирую создание объектов, написав глобальный pool. Думаю, это очередной велосипед, но мне хотелось написать его своими руками. Пул умеет создавать объекты по ключу-префабу, инициализировать их после создания, уведомлять объекты о создании/удалении.

А однажды с пулом вышел забавный казус.

У моих пуль есть ограничение по времени жизни (примерно 10 секунд "незамороженного" времени). Как то раз появился странный баг: часть пуль исчезала прямо в воздухе, словно кулдаун наступал раньше срока и пуля исчезала по таймеру.
Отловить было сложно: не все пули исчезали, а дебажить каждую, надеясь, что хоть одна исчезнет — очень утомительно.
Впрочем, удалось выяснить два странных факта:

  1. Пули начинали исчезать только после перезапуска уровня;
  2. Код, ответственный за удаление пуль вообще не вызывался.

Самое важное правило в очередной раз не подвело:

Чем страннее кажется баг, тем глупее его причины.

Итак, наслаждайтесь:

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

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

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

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

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

Усатый стрелок с полигональным пузом. Часть вторая - 12Level 4.2. Рефакторинг игровых объектов.

Когда я обдумывал геймплейные фичи, я был заворожён огромным количеством возможностей. Судите сами, все объекты могут обладать четырьмя ортогональными характеристиками:

  1. Отражает ли пули или поглощает их?
  2. Уничтожим ли объект пулей?
  3. Подвижен ли или статичен?
  4. Каков тип объекта (игрок/враг/гражданский)?

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

  1. Обычные стены. Поглощают пули;
  2. Зеркальные стены. Отражают пули;
  3. Многоэтажные стены. Каждый этаж — обычный или зеркальный. При попадании пули нижний этаж уничтожается, верхние падают вниз. Так можно делать счётчики и т.д.;
  4. Ящики. Динамические, но неуничтожимые, поглощают пули;
  5. Зеркальные ящики. Динамические, но неуничтожимые, отражают пули.;
  6. Цыплята. Динамические, уничтожимые, игрок теряет очки при их гибели;
  7. Враги. Динамические, уничтожимые, нужно победить всех для прохождения уровня;
  8. Зеркальные враги. Обычные враги, но пуля, уничтожая врага, отражается;
  9. Кристаллы. Динамические, уничтожаются пулей, если игрок коснётся их, он получает бонус;
  10. Игрок.

Усатый стрелок с полигональным пузом. Часть вторая - 13
Все доступные объекты.

У меня явно будут проблемы с понятной визуализацией всей этой красоты. Когда я начинал работать над low-poly версией, я планировал использовать простое цветовое кодирование:

  1. Цвет кромки определяет тип объекта;
  2. Белый цвет потолка обозначает статический объект (стену), тонированный в цвет кромки потолок — динамический.

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

  1. Многоэтажные стены. Когда остаётся только один этаж — он не будет отличаться от обычной стены. Но он будет уничтожим. Или нет? Очень нелогичная фича;
  2. Зеркальные ящики. Пуля всегда движется с одной скоростью. Переотражаясь от ящиков, она будет их бесконечно и непредсказуемо ускорять;
  3. Зеркальные враги. Придётся использовать другой цвет, не похожий ни на "вражеский", ни на "зеркальный". Эта сущность только путает все карты.

Итого, остаётся:

  1. Два типа стен, обычные и зеркальные;
  2. Игрок;
  3. Цыплята;
  4. Враги;
  5. Кристаллы;
  6. Ящики.
    Усатый стрелок с полигональным пузом. Часть вторая - 14
    Объекты, оставшиеся после чистки.

Всё хорошо кодируется цветом, объектов стало мало, но есть простор для левелдизайна.

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

Todo: начать разработку релизных эффектов.

Усатый стрелок с полигональным пузом. Часть вторая - 15Level 5.1. Эффект гибели.

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

Да, хочется какого-то фана при попадании пули. Чтобы игра визуально говорила:

  • "Да, чел, ты это сделал! Ты расфигачил его в чёртовой бабушке!"
    Или наоборот:
  • "Аккуратнее, аккуратнее… Нееееет! Ты был так близко, а теперь придётся проходить все снова!"

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

Ладно, что требуется от эффекта гибели?

  1. Он должен быть ярким, ощутимым и значимым;
  2. Последствия гибели должны быть видны в течении всего уровня, помогая планировать перепрохождение, но не отвлекая.

Осколки! Пусть пуля разбивает противников на кусочки! Хм, а это не сложно? Неа, все объекты выпуклые, а резать выпуклые многоугольники — одно удовольствие.

На самом деле, просто разрезать противника пополам я не могу. Он состоит из нескольких мешей:

  1. Внутренняя часть, выпуклый многоугольник, тут все просто;
  2. Цветное кольцо. Оно мало того, что не выпуклое, да ещё и с дыркой. Но состоит из N (где N — количество сторон) выпуклых четырёхугольников. Так что просто сохраню их в массиве и разрежу каждый из них;
  3. Внешняя сторона. По сути, это внешняя сторона четырёхугольников из предыдущего пункта. Но я буду работать с ней как с большим выпуклым многоугольником — для рендеринга боковых граней и физики через PolygonCollider2D.

Усатый стрелок с полигональным пузом. Часть вторая - 16
Части объекта, которые нужно разрезать отдельно.

В результате алгоритм получается такой:

  1. Преобразую объект (игрока, врага и т.д.) во внутреннюю часть, массив кусков кольца, внешнюю часть. В дальнейшем буду именовать эту структуру "Piece";
  2. Нахожу геометрический центр для Piece;
  3. Выбираю случайное направление и "провожу" прямую в этом направлении через геометрический центр;
  4. Разрезаю Piece этой прямой. Для этого беру каждый многоугольник из Piece (кольцо, внутренняя и внешняя части или их кусочки):
    4.1. Создаю левый и правый массив точек;
    4.2. Указываю текущий массив — левый;
    4.3. Добавляю первую точку многоугольника в текущий массив;
    4.4. Прохожу по всем оставшимся точкам;
    4.5. Если текущая и предыдущая точки находятся с одной стороны прямой, добавляю текущую точку в текущий массив;
    4.5. Если текущая и предыдущая точки находятся с разных сторон прямой, нахожу точку пересечения, добавляю её и в левый и в правый массивы. Переключаю текущий массив на противоположный. Добавляю в новый текущий массив текущую точку.
  5. Добавляю все левые осколки в новый левый Piece, а правые — в правый;
  6. Снов разрезаю получившиеся осколки рекурсивно, до указанной глубины.

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

Получаю примерно такие осколки.

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

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

Итак, теперь при попадании пули в объект я подменяю последний на осколки. Объект убирается в пул, а осколки загружаются из пула и обновляют свои меши/коллайдеры согласно своей новой форме. Скорости для rigidBody рассчитываются исходя из скорости разрушенного элемента и направления пули. У осколков выключен флаг isBullet, они взаимодействуют только со стенами и друг с другом. У каждого осколка есть специальный класс FloorHider, он опускает объект по координате z сквозь пол, а после его полного исчезновения — удаляет (перемещает в пул.)

Небольшая ретроспектива:

  1. Осколки — очень "физически" понятный образ. Поэтому он помогает понять концепцию остановки времени. Осколки начинают разлетаться, тут время останавливается и всё замирает. Игра перестала выглядеть детерминированно пошаговой;
  2. Все осколки батчатся друг с другом и не тормозят;
  3. Кристалл сейчас удаляется при прикосновении без эффектов. Может, тоже разбивать на кусочки?
  4. Не хватает какого-то следа после уничтожений, хочется, чтобы на уровне оставались последствия атак;
  5. Фаново смотрится, хочется стрелять!

Осколки!

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

Todo: реализовать эффект следов от осколков.

Усатый стрелок с полигональным пузом. Часть вторая - 17Level 5.2.1. Эффект пятен.

Когда я думал над визуалом, у меня в голове крутилась идея "пятен крови", которые бы появлялись при гибели игрока или npc. На длинных уровнях такие пятна станут удобными метками для навигации. А в случае проигрыша помогут оценить начальное положение врагов и обдумать тактику повторного прохождения.

Итак, пятна. Вариант с декалями и отрисованными текстурами отбрасываю: мне кажется, так я выбьюсь из стиля. Пробую отобразить след от осколков или места их исчезновения. Смотрится плохо:
Усатый стрелок с полигональным пузом. Часть вторая - 18
Усатый стрелок с полигональным пузом. Часть вторая - 19
Разные варианты пятен.

Думаю над полноценной заливкой, среди вариантов прототипирую такой:

Просто создание кучи треугольников.
Да, этот вариант мне понравился больше. Но создавать множество треугольников с диким overdraw'ом — плохая идея. Впрочем, результат похож на мозаику, так что думаю в сторону диаграммы Вороного.
Вот только генерировать её на лету, особенно с последующей релаксацией Ллойда (релаксация делает ячейки схожими по размеру) на мобильных устройствах будет слишком больно. Нужен предрассчет. И отсюда очередная проблема: пятна могут быть на любом расстоянии друг от друга, и я, очевидно, не могу предрассчитать бесконечно большую диаграмму. Знаете, что такое тайлинг? :)

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

  1. Создаю N точек в квадрате с координатами {-0.5, -0.5, 0.5, 0.5};
  2. Для каждого Y в интервале [-tiles, tiles] и X в интервале [-tiles, tiles], кроме X = 0, Y = 0:
    2.1. Копирую точки со смещением X, Y (при tiles = 1 получается 9 тайлов с моим начальным в центре);
  3. Строю по всем точкам (включая смещённые клоны) диаграмму Вороного;
  4. Применяю при необходимости релаксацию Ллойда;
  5. Прохожу по всем получившимся полигонам и оставляю только те, у которых центр находится в исходном квадрате {-0.5, -0.5, 0.5, 0.5}.

В результате получается тайл с полигонами, у которого левая сторона идеально подходит к правой, верхняя — к нижней (с диагоналями — аналогично). На самом деле, не всё так гладко.
Идея в том, что диаграмма Вороного — очень локальная штука, поэтому можно эмулировать тор, сделав несколько копий исходных точек во все стороны. Но вот релаксация Ллойда уж точно локальной не является, и чем больше количество итераций, тем больше нужно делать копий (увеличивать значение tiles).
Да и координаты центров не всегда получается корректно проверить, все-таки, плавающая запятая. Поэтому иногда, очень редко, на краешке мозаики не хватает какого-нибудь элемента.
Усатый стрелок с полигональным пузом. Часть вторая - 20
Найдёте повторения?

Подсказка

Усатый стрелок с полигональным пузом. Часть вторая - 21

Итак, получается примерно такой кусочек мозаики:
Усатый стрелок с полигональным пузом. Часть вторая - 22
Мозаика отрендерена на текстуре средствами библиотеки.

Делаю небольшой ScriptableObject, хранящий массив рассчитанных тайлов и редактор с большой кнопкой "recalculate tiles".

Проблемы с редкими дырами из-за float'а в проверках на попадание полигона в тайл я решил перегенерированием некорректных тайлов. Т.к. я делаю предрассчет один раз, руками в редакторе, могу себе такое позволить. :)

Теперь бы выводить эти тайлы на экран!

Todo: генерировать треугольники тайлов мозаики.

Усатый стрелок с полигональным пузом. Часть вторая - 23Level 5.2.2. Рендеринг тайлов.

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

Для проверки алгоритма создал вот такую "мозаику", с ней проще будет найти проблемы:
Усатый стрелок с полигональным пузом. Часть вторая - 24
Поддельная мозаика

Допустим, у меня мозаика генерируется из 512 точек. Значит, на выходе получится 512 полигонов и проверять каждый на пересечение с окружностью — слишком дорого. Поэтому храню мозаику в виде небольших прямоугольных блоков:
Усатый стрелок с полигональным пузом. Часть вторая - 25
Визуализация разделения на блоки.
Зная площадь мозаики и количество полигонов, можно получить оптимальное количество блоков, при котором скорость поиска будет максимальна.

Итак, логика поиска такая:
Дана окружность с координатами center и радиусом radius. Нужно найти все полигоны, попадающие в окружность.

  1. Считаем из AABB окружности координаты первого и последнего блоков, попадающих в AABB (Значения координат могут быть меньше 0 или больше rows — 1 из-за тайлинга).
    var rectSize = size / (float)rows;
    int minX = Mathf.FloorToInt((center.x - radius) / rectSize);
    int minY = Mathf.FloorToInt((center.y - radius) / rectSize);
    int maxX = Mathf.CeilToInt((center.x + radius) / rectSize);
    int maxY = Mathf.CeilToInt((center.y + radius) / rectSize);
  2. Проходим по каждому блоку от min до max;
  3. Отбрасываем блоки, не пересекающиеся с окружностью;
  4. Получаем реальные координаты блока внутри тайла:
    int innerX = ((x + rows) % rows + rows) % rows;
    int innerY = ((y + rows) % rows + rows) % rows;
  5. Проходим по всем полигонам в блоке;
  6. Добавляем в список те полигоны, центры которых принадлежат окружности (с учётом смещения).

Итак, теперь можно одним запросом получить данные обо всех полигонах, попадающих в заданную окружность:
Усатый стрелок с полигональным пузом. Часть вторая - 26
Запрос полигонов. Тестовая мозаика изменена на более наглядную

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

Выглядит, мягко говоря, скучно. Более того, если два пятна создаются с примерно на расстоянии одного тайла, например, {0, 0} и {1, 1}, бывают заметны повторения.

Спасибо любимой, она предложила хорошую модификацию этого алгоритма:

  1. Убрать релаксацию Ллойда, сделав полигоны более резкими;
  2. Заменить многоугольники на треугольники;
  3. Добавить больше случайности в расположение треугольников.

А теперь в картинках:
Пусть у нас есть вот такая мозаика:
Усатый стрелок с полигональным пузом. Часть вторая - 27
Points = 500, Relax = 5

В ней бывают видны повторы, а ещё она очень однообразна.
Убираем релаксацию Ллойда:
Усатый стрелок с полигональным пузом. Часть вторая - 28
Points = 500, Relax = 0

А теперь смешиваем все карты: считаем полигоном не многоугольник, сгенерированные в диаграмме Вороного, а треугольники, получаемые триангуляцией для рендеринга:
Усатый стрелок с полигональным пузом. Часть вторая - 29
Triangles, Points = 500, Relax = 0

Теперь избавляемся от видимых паттернов. Полигоны, полученные из диаграммы Вороного, фактически, однонаправленны: нулевая вершина сверху, следующие вершины идут по часовой стрелке. Из-за этого чётко прослеживается "направление", как будто бумагу скомкали по диагонали и получилась мятая поверхность со складками, вытянутыми в одну сторону:
Усатый стрелок с полигональным пузом. Часть вторая - 30
Выделены нулевые треугольники в каждом полигоне диаграммы.

Всё, что требуется — создавать треугольники начиная со случайной вершины полигона. Дополнительным плюсом становится то, что после триангуляции исчезают все повторы: в каждом тайле полигон триангулируется по-разному:
Усатый стрелок с полигональным пузом. Часть вторая - 31
Паттерны перестали быть заметны.

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

Todo: придумать конкретную геометрию пятен и замостить её мозаикой.

Заключение.

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

Итак, ещё несколько выводов:

  1. Процедурные эффекты рулят. Иногда классические алгоритмы (вроде диаграммы Вороного) не очень подходят, но после напильника и лобзика приобретают нужные качества;
  2. Закон Хофштадтера: Любое дело всегда длится дольше, чем ожидается, даже если учесть закон Хофштадтера. В общем, разработка проекта затягивается. :)
  3. Unity3D очень полезна, но иногда ставит палки в колёса. Если ваши кастомные постэффекты перестали работать — посмотрите во frame debug, может, после обновления Unity3D решила дополнить отрисовку своими эффектами (и включила на камере msaa).

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

Спасибо за внимание, жду ваших комментариев и feedback'a!

Автор: Русанов Семен

Источник

Поделиться

* - обязательные к заполнению поля