Привет! Моя последняя игра – изометрическая бродилка, одной из особенностью которой является «исследование» территории: изначально карта чёрная и игрок открывает этот «туман войны» по ходу игры. Причём видимость тайлов зависит не только от расстояния до персонажа, но и от окружения: клетки за непрозрачными стенами не видны, даже если подойти в упор, а, например, кустарник ухудшает видимость клеток за ним на 50%.

image

Чтобы не нагружать процессор покадровой трассировкой лучей (для определения какая клетка насколько в данный момент «видима»), я использовал довольно интересный метод «тотального предрасчёта» – основные параметры для фактически всех возможных ситуаций считаются до игры в большую матрицу, и во время игры остаётся только обращаться к ней, выбирая нужные значения.

Что я имею ввиду под предварительными расчётами:

Герой ставится в клетку начала координат (0;0). Для каждой клетки в пределах видимости экрана (с запасом, в пределах двух экранов) считаются различные игровые параметры, в том числе список клеток, которых пересекает отрезок от начала координат до её центра:

image

Если быть точнее, то подобные списки считаются для каждого из 4х углов каждой клетки:

image

Все эти данные записываются в «матрицу видимостей» M.

Как это работает? У каждого объекта в игре есть параметр «непрозрачность» — величина от 0 до 1, процент загораживаемости обзора. В игре, чтобы узнать насколько виден тайл (xt;yt) относительно положения героя (x0;y0), мне нужно:

1. Обратиться к элементу матрицы Mt = M[xt-x0;yt-y0]
2. Посчитать насколько виден каждый из углов этого тайла (причём не учитываются углы, которые загораживаются самим тайлом (xt;yt), так что их 2 или 3): для этого я считываю из Mt вектор тайлов, которые встречаются на пути до угла и перемножаю «степени видимости» всех объектов, которые в них находятся (и да, как только встречается объект с нулевой видимостью, прохождение по списку можно не продолжать).
3. Степень видимости тайла Vt= среднее арифметическое видимостей каждого из его углов.

Так я делаю для каждого из тайлов в некоторой области вокруг героя, когда что-то меняется (положение героя или объектов).

Расчёт по углам вместо одного центра тайла ведётся для сглаживания артефактов, когда клетку незначительно загораживает какая-нибудь непрозрачная стена своим концом, но из-за этого клетка становится полностью невидима.

image

Способ, как вы понимаете, не совсем точный (по сравнению с честной «аналоговой» трассировкой луча), но даёт хорошие значения. Дискретность заметна тем меньше, чем визуально меньше клетки в игре.

Насколько будет повышать производительность предварительный расчёт всех параметров в «матрицу видимостей» (по сравнению с определением параметров на ходу) будет зависеть от языка, но по сути все геометрические расчёты заменяются на операцию доступа к элементу матрицы/вектора. У меня на AIR прирост в скорости колеблется от 7 до 11 раз (зависит от степени нагруженности области карты объектами)

Ту же самую матрицу можно использовать для определения освещённости клетки, когда какие-то объекты могут испускать свет, а какие-то его загораживать. Алгоритм тут точно такой же.

image
(монетки имеют небольшое свечение)

Демонстрация смены видимости тайлов в динамике:



Спасибо за внимание!
Поделиться с друзьями
-->

Комментарии (21)


  1. napa3um
    23.11.2016 18:26
    +2

    https://ru.wikipedia.org/wiki/Двоичное_разбиение_пространства


    1. napa3um
      23.11.2016 19:28
      +1

      (Впрочем, если для 2D тормозит просчёт поля видимости без предрасчётов, то, кажется, сделано что-то неверно.)


  1. splatt
    23.11.2016 18:28
    +1

    Интересная идея. На видео с демо освещение появляется резкими переходами из одного состояния в другое.
    Я понимаю, что это из-за того что количество состояний освещения напрямую зависит от количества тайлов.
    Но тем не менее, нельзя сделать интерполяцию между двумя значениями освещения во время перехода от одного тайла к другому?
    Мне кажется, плавный переход будет выглядеть гораздо приятнее.


    1. AntonRiot
      23.11.2016 19:56

      Алгоритм даёт циферки, а как их отображать — тут уже вопрос визуализации.
      На самом деле, переходы как раз «сглажены» – степень видимости меняется с некоторой максимальной дельтой. Но поле для экспериментов с визуальной составляющей всегда есть, согласен.


      1. perfect_genius
        23.11.2016 20:20
        +1

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


        1. AntonRiot
          23.11.2016 20:25

          Возможно.

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


  1. Dendroid
    23.11.2016 19:15
    +1

    Буквально недавно делал похожее, у меня хранились в матрице все клетки простреливаемые из этой в порядке дальности. И тоже, что интересно, на AIR )

    Можно организовать клуб анонимных пользователей AIR. Главное, не произносить вслух слово на букву F )))


    1. AntonRiot
      23.11.2016 20:14

      Ох, да, я старался обойти инструмент реализации стороной.


  1. rrrrex
    23.11.2016 20:08

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


    1. AntonRiot
      23.11.2016 20:17

      Да, кстати это реализовано. Вот тут лучше видно будет:


  1. perfect_genius
    23.11.2016 20:43

    Вначале показалось, что игра пластилиновая.
    Какую функцию выполняют клетки?


    1. AntonRiot
      23.11.2016 21:05
      +2

      Игра и есть пластилиновая – всё из фотографий. Клетки… Такой стиль. Большие пластилиновые пространства трудно было фотографировать и как-то компоновать, а тут составлено из кубиков.
      Ну и карта проходимости тоже потайловая.


  1. OlegKozlov
    24.11.2016 00:45

    Обожаю дешевые способы не считать всё в рантайме, а попотеть в предрасчётах. Я так в RTS с поиском пути делал — заранее делил карту на квадраты и считал все возможные пути между ними. Тут, по моим ощущениям, тот же подход. Круто!


  1. schetilin
    24.11.2016 02:27

    И сколько памяти примерно занимает эта матрица?


    1. AntonRiot
      24.11.2016 14:35
      +1

      Да копейки, пусть даже она будет 50х50 и в каждой ячейке хранится по 80 чисел – это получается полтора мегабайта, а на практике данных на порядок меньше.


      1. schetilin
        24.11.2016 14:45

        Не ценят люди память. Это примерно 30 полноценных игр для компа типа «Спектрум». А тут только таблица видимости :(


        1. AntonRiot
          24.11.2016 14:59

          Память дешевле, чем процессорное время


  1. claygod
    24.11.2016 09:11

    Антон, графика в Вашей игре мне немного напомнила старую Ecstatica, посмотрите её, может в дизайне той игры почерпнёте для себя что-нибудь интересное.


    1. AntonRiot
      24.11.2016 14:26

      Неужели у меня всё так плохо?..


      1. claygod
        24.11.2016 14:32

        Про плохо я не писал. Я говорю о стиле.


        1. AntonRiot
          24.11.2016 14:38

          Кстати мы тут вспоминали эту игру не так давно в разговоре «что было бы, если бы техника 3D пошла не по пути отрисовки треугольников». Конечно, игра выглядит забавно, но ей больше 20 лет как-никак…