Как они это сделали: миллионы плиток в Террарии

Я работал над игровым движком, похожим на Terraria , в основном как вызов, и, хотя я понял большую его часть, я не могу понять, как они справляются с миллионами интерактивных / собираемых плиток в игре есть одно время. Создание около 500 000 плиток, что составляет 1/20 от того, что возможно в Terraria , в моем движке приводит к падению частоты кадров с 60 до около 20, даже если я все еще только отображаю плитки в поле зрения. Имейте в виду, я ничего не делаю с плитками, только храню их в памяти.

Обновление : код добавлен, чтобы показать, как я делаю вещи.

Это часть класса, который обрабатывает плитки и рисует их. Я предполагаю, что виновником является часть «foreach», которая повторяет все, даже пустые индексы.

...
    public void Draw(SpriteBatch spriteBatch, GameTime gameTime)
    {
        foreach (Tile tile in this.Tiles)
        {
            if (tile != null)
            {
                if (tile.Position.X < -this.Offset.X + 32)
                    continue;
                if (tile.Position.X > -this.Offset.X + 1024 - 48)
                    continue;
                if (tile.Position.Y < -this.Offset.Y + 32)
                    continue;
                if (tile.Position.Y > -this.Offset.Y + 768 - 48)
                    continue;
                tile.Draw(spriteBatch, gameTime);
            }
        }
    }
...

Также здесь есть метод Tile.Draw, который также можно сделать с обновлением, поскольку каждый Tile использует четыре вызова метода SpriteBatch.Draw. Это часть моей системы автотайлинга, которая подразумевает рисование каждого угла в зависимости от соседних плиток. texture_ * - это прямоугольники, которые устанавливаются один раз при создании уровня, а не при каждом обновлении.

...
    public virtual void Draw(SpriteBatch spriteBatch, GameTime gameTime)
    {
        if (this.type == TileType.TileSet)
        {
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position, texture_tl, this.BlendColor);
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position + new Vector2(8, 0), texture_tr, this.BlendColor);
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position + new Vector2(0, 8), texture_bl, this.BlendColor);
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position + new Vector2(8, 8), texture_br, this.BlendColor);
        }
    }
...

Любая критика или предложения к моему коду приветствуются.

Обновление : решение добавлено.

Вот последний метод Level.Draw. Метод Level.TileAt просто проверяет введенные значения, чтобы избежать исключений OutOfRange.

...
    public void Draw(SpriteBatch spriteBatch, GameTime gameTime)
    {
        Int32 startx = (Int32)Math.Floor((-this.Offset.X - 32) / 16);
        Int32 endx = (Int32)Math.Ceiling((-this.Offset.X + 1024 + 32) / 16);
        Int32 starty = (Int32)Math.Floor((-this.Offset.Y - 32) / 16);
        Int32 endy = (Int32)Math.Ceiling((-this.Offset.Y + 768 + 32) / 16);

        for (Int32 x = startx; x < endx; x += 1)
        {
            for (Int32 y = starty; y < endy; y += 1)
            {
                Tile tile = this.TileAt(x, y);
                if (tile != null)
                    tile.Draw(spriteBatch, gameTime);

            }
        }
    }
...

Вы просматриваете все 500 000 плиток при рендеринге? Если так, то это, вероятно, вызовет часть ваших проблем. Если вы перебираете полмиллиона плиток при рендеринге и полмиллиона плиток при выполнении отметок «обновление», то вы зацикливаете по миллиону плиток в каждом кадре.

Очевидно, что есть способы обойти это. Вы можете выполнять свои тики обновления во время рендеринга, тем самым экономя половину времени, затрачиваемого на циклы по всем этим плиткам. Но это связывает ваш код рендеринга и ваш код обновления вместе в одну функцию, и, как правило, это ПЛОХАЯ ИДЕЯ .

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

Наконец, и, возможно, лучший вариант (это делают большинство крупных мировых игр), это разделить вашу местность на регионы. Разделите мир на куски, скажем, 512x512 плиток и загружайте / выгружайте регионы, когда игрок приближается к региону или удаляется от него. Это также избавляет вас от необходимости перебирать дальние тайлы для выполнения любого вида обновления.

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

Я вижу одну огромную ошибку, которая не обрабатывается ни одним из ответов. Конечно, вы никогда не должны рисовать и перебирать больше плиток, чем вам нужно. Менее очевидно, как вы на самом деле определяете плитки. Как я вижу, вы создали класс плиток, я всегда делал это тоже, но это огромная ошибка. Вероятно, у вас есть все виды функций в этом классе, и это создает много ненужной обработки.

Вы должны перебирать только то, что действительно необходимо для обработки. Так что подумайте, что вам на самом деле нужно для плитки. Чтобы нарисовать меня, вам нужна только текстура, но вы не хотите перебирать реальное изображение, так как оно велико для обработки. Вы можете просто сделать int [,] или даже неподписанный байт [,] (если вы не ожидаете более 255 текстур плиток). Все, что вам нужно сделать, это перебрать эти небольшие массивы и использовать оператор switch или if для рисования текстуры.

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

struct TileUpdate
{
public byte health;
public byte type;
public byte damage;
}

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

Если вы сохраняете вышеуказанную структуру, она занимает всего 3 байта на плитку. Так что для сохранения и памяти это идеально. Для скорости обработки не имеет значения, используете ли вы int или byte, или даже long int, если у вас 64-битная система.

Есть разные методы кодирования, которые вы можете использовать.

RLE: Итак, вы начинаете с координаты (x, y), а затем подсчитываете, сколько одинаковых плиток существует бок о бок (длина) вдоль одной из осей. Пример: (1,1,10,5) будет означать, что начиная с координаты 1,1 имеется 10 плиток рядом с типом плиток 5.

Массивный массив (растровое изображение): каждый элемент массива содержит тип плитки, который находится в этой области.

РЕДАКТИРОВАТЬ: Я только что столкнулся с этим превосходным вопросом здесь: функция случайного семени для генерации карты?

Генератор шума Perlin выглядит как хороший ответ.

Вы, вероятно, должны разделить карту тайлов, как уже предлагалось. Например, со структурой Quadtree, чтобы избавиться от любой потенциальной обработки (например, даже просто циклического прохождения) ненужных (не видимых) плиток. Таким образом, вы обрабатываете только то, что может потребовать обработки, и увеличение размера набора данных (карты листов) не приводит к практическому снижению производительности. Конечно, предполагая, что дерево хорошо сбалансировано.

Я не хочу звучать скучно или что-то подобное, повторяя «старое», но при оптимизации всегда не забывайте использовать оптимизации, поддерживаемые вашей цепочкой инструментов / компилятором, вам следует немного поэкспериментировать с ними. И да, преждевременная оптимизация - корень всего зла. Доверяйте своему компилятору, он знает лучше вас в большинстве случаев, но всегда, всегдаизмерять дважды и никогда не полагаться на догадки. Речь идет не о быстрой реализации самого быстрого алгоритма, если вы не знаете, где на самом деле узкое место. Вот почему вы должны использовать профилировщик, чтобы найти самые медленные (горячие) пути кода и сосредоточиться на их устранении (или оптимизации). Низкий уровень знаний целевой архитектуры часто необходим для того, чтобы выжать все, что может предложить аппаратное обеспечение, поэтому изучите эти кэши ЦП и узнайте, что такое предсказатель ветвлений. Посмотрите, что ваш профилировщик говорит вам о попаданиях / промахах кэша / ветки. И как показывает использование некоторой формы древовидной структуры данных, лучше иметь интеллектуальные структуры данных и глупые алгоритмы, чем наоборот. Данные приходят первыми, когда речь заходит о производительности. :)

Разве это не слишком много звонков? Если вы поместите все текстуры листов карт в одно изображение - атлас плиток, при рендеринге переключение текстур не будет. И если вы объединяете все свои плитки в одну сетку, это должно быть нарисовано за один вызов.

О динамическом подборе ... Может быть, дерево квадов не такая уж плохая идея. Предполагая, что плитки помещаются в листовые, а неконечные узлы являются просто пакетными сетками своих дочерних элементов, корень должен содержать все плитки, объединенные в одну сетку. Удаление одной плитки требует обновлений узлов (повторной сборки сетки) вплоть до корня. Но на каждом уровне дерева есть только 1/4-ая часть меша, что должно быть много, 4 * tree_height меш присоединяется?

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

Просто мои мысли, без кода, может быть, это чепуха.

@arrival прав. Проблема в коде розыгрыша. Вы строите массив 4 * 3000 + рисовать квадроциклов команды (24000+ Жеребьевка полигонных команд) для каждого кадра. Затем эти команды обрабатываются и передаются в графический процессор. Это довольно плохо.

Есть несколько решений.

• Рендеринг больших блоков (например, размер экрана) плиток в статическую текстуру и рисование в один вызов.
• Используйте шейдеры для рисования тайлов, не отправляя геометрию в GPU каждый кадр (т.е. сохраняйте карту тайлов в GPU).

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

С точки зрения обработки таких вещей, как растения, растущие в областях, удаленных от текущего экрана игрока, у вас могут быть таймеры, например. Эти таймеры будут перебирать, скажем, файлы, хранящие информацию о растениях, их положении и т. Д. Вам просто нужно прочитать / обновить / сохранить файлы в таймерах. Когда игрок снова достигает этих частей света, движок считывает файлы в обычном режиме и выводит на экран новые данные о заводе.

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

Я думал о том, как справиться с таким количеством миллиардов блоков, и единственное, что приходит мне в голову, это шаблон проектирования Flyweight. Если вы не знаете, я настоятельно рекомендую прочитать об этом: это может помочь, когда речь идет о экономии памяти и обработки: http://en.wikipedia.org/wiki/Flyweight_pattern