Оптимизация простого движка 2D-плиток (+ потенциальное исправление)

Question

Оптимизация простого движка 2D-плиток (+ потенциальное исправление)

Предисловие

Да, здесь есть, что рассказать... но я сделаю все возможное, чтобы это было как можно лучше организовано, информативно и прямо к делу!

Используя библиотеку HGE в C++, я создал простой движок плиток.
И до сих пор я реализовал следующие проекты:

CTile класс, представляющий одну плитку в пределах CTileLayer, содержащий информацию о строке / столбце, а также HGE::hgeQuad (где хранится информация о вершинах, цвете и текстуре, подробности см. здесь).
CTileLayer класс, представляющий двумерную "плоскость" плиток (которые хранятся в виде одномерного массива CTile объекты), содержащие количество строк / столбцов, информацию о мировых координатах X/Y, информацию о ширине / высоте пикселя плитки и общую ширину / высоту слоя в пикселях.

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

вопросы

Проблема, с которой я сейчас сталкиваюсь, сводится к следующим проблемам архитектуры / оптимизации:

В моем цикле рендеринга, даже несмотря на то, что я не отрисовываю никакие листы, находящиеся за пределами видимого диапазона, я все еще перебираю все листы, что, как представляется, оказывает существенное влияние на производительность для более крупных карт листов (т. Е. Любой вещи, превышающей 100x100 строк Размеры столбцов columns @ 64x64 по-прежнему снижают частоту кадров на 50% и более).
В конце концов, я намереваюсь создать необычный редактор тайлкарт, который будет совпадать с этим движком.
Однако, поскольку я храню всю двумерную информацию в одном или нескольких одномерных массивах, я понятия не имею, насколько возможно было бы реализовать какую-либо функцию прямоугольного выбора и копирования / вставки без какого-либо значительного снижения производительности -- Включая цикл по каждой клетке дважды за кадр. И все же, если бы я использовал 2D-массивы, было бы чуть меньше, но более универсальное падение FPS!

ошибка

Как уже говорилось ранее... В моем коде рендеринга для CTileLayer объект, я оптимизировал, какие плитки должны быть нарисованы на основе того, находятся ли они в пределах диапазона просмотра. Это прекрасно работает, и для больших карт я заметил падение только на 3-8 FPS (по сравнению с падением на 100+ FPS без этой оптимизации).

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

Этот промежуток постепенно увеличивается в размере по мере продвижения вдоль оси X и Y, в конечном итоге поглощая почти половину верхней и левой сторон экрана на большой карте. Мой код рендеринга для этого показан ниже...

Код

//
// [Allocate]
// For pre-calculating tile information
// - Rows/Columns   = Map Dimensions (in tiles)
// - Width/Height   = Tile Dimensions (in pixels)
//
void CTileLayer::Allocate(UINT numColumns, UINT numRows, float tileWidth, float tileHeight)
{
    m_nColumns = numColumns;
    m_nRows = numRows;

    float x, y;
    UINT column = 0, row = 0;
    const ULONG nTiles = m_nColumns * m_nRows;
    hgeQuad quad;

    m_tileWidth = tileWidth;
    m_tileHeight = tileHeight;
    m_layerWidth = m_tileWidth * m_nColumns;
    m_layerHeight = m_tileHeight * m_nRows;

    if(m_tiles != NULL) Free();
    m_tiles = new CTile[nTiles];

    for(ULONG l = 0; l < nTiles; l++)
    {
        m_tiles[l] = CTile();
        m_tiles[l].column = column;
        m_tiles[l].row = row;
        x = (float(column) * m_tileWidth) + m_offsetX;
        y = (float(row) * m_tileHeight) + m_offsetY;

        quad.blend = BLEND_ALPHAADD | BLEND_COLORMUL | BLEND_ZWRITE;
        quad.tex = HTEXTURE(nullptr); //Replaced for the sake of brevity (in the engine's code, I used a globally allocated texture array and did some random tile generation here)

        for(UINT i = 0; i < 4; i++)
        {
            quad.v[i].z = 0.5f;
            quad.v[i].col = 0xFF7F7F7F;
        }
        quad.v[0].x = x;
        quad.v[0].y = y;
        quad.v[0].tx = 0;
        quad.v[0].ty = 0;
        quad.v[1].x = x + m_tileWidth;
        quad.v[1].y = y;
        quad.v[1].tx = 1.0;
        quad.v[1].ty = 0;
        quad.v[2].x = x + m_tileWidth;
        quad.v[2].y = y + m_tileHeight;
        quad.v[2].tx = 1.0;
        quad.v[2].ty = 1.0;
        quad.v[3].x = x;
        quad.v[3].y = y + m_tileHeight;
        quad.v[3].tx = 0;
        quad.v[3].ty = 1.0;
        memcpy(&m_tiles[l].quad, &quad, sizeof(hgeQuad));

        if(++column > m_nColumns - 1) {
            column = 0;
            row++;
        }
    }
}

//
// [Render]
// For drawing the entire tile layer
// - X/Y          = world position
// - Top/Left     = screen 'clipping' position
// - Width/Height = screen 'clipping' dimensions
//
bool CTileLayer::Render(HGE* hge, float cameraX, float cameraY, float cameraTop, float cameraLeft, float cameraWidth, float cameraHeight)
{
    // Calculate the current number of tiles
    const ULONG nTiles = m_nColumns * m_nRows;

    // Calculate min & max X/Y world pixel coordinates
    const float scalarX = cameraX / m_layerWidth;  // This is how far (from 0 to 1, in world coordinates) along the X-axis we are within the layer
    const float scalarY = cameraY / m_layerHeight; // This is how far (from 0 to 1, in world coordinates) along the Y-axis we are within the layer
    const float minX = cameraTop + (scalarX * float(m_nColumns) - m_tileWidth); // Leftmost pixel coordinate within the world
    const float minY = cameraLeft + (scalarY * float(m_nRows) - m_tileHeight);  // Topmost pixel coordinate within the world
    const float maxX = minX + cameraWidth + m_tileWidth;                        // Rightmost pixel coordinate within the world
    const float maxY = minY + cameraHeight + m_tileHeight;                      // Bottommost pixel coordinate within the world

    // Loop through all tiles in the map
    for(ULONG l = 0; l < nTiles; l++)
    {
        CTile tile = m_tiles[l];
        // Calculate this tile's X/Y world pixel coordinates
        float tileX = (float(tile.column) * m_tileWidth) - cameraX;
        float tileY = (float(tile.row) * m_tileHeight) - cameraY;

        // Check if this tile is within the boundaries of the current camera view
        if(tileX > minX && tileY > minY && tileX < maxX && tileY < maxY) {
            // It is, so draw it!
            hge->Gfx_RenderQuad(&tile.quad, -cameraX, -cameraY);
        }
    }

    return false;
}

//
// [Free]
// Gee, I wonder what this does? lol...
//
void CTileLayer::Free()
{
    delete [] m_tiles;
    m_tiles = NULL;
}

Вопросы

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

Спасибо за ваше время!

0

c++ optimization graphics 2d tile-engine

Источник

user1500110 18 апр '13 в 09:50

2 ответа

Решение

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

Итак, сначала полный пример, и я объясню каждую часть ниже.

// x and y are counters, sx is a placeholder for x start value as x will 
// be in the inner loop and need to be reset each iteration.
// mx and my will be the values x and y will count towards too.
x=0,
y=0, 
sx=0, 
mx=total_number_of_tiles_on_x_axis, 
my=total_number_of_tiles_on_y_axis

// calculate the lowest and highest worldspace values of the cam
min = cam.center - cam.extent
max = cam.center + cam.extent

// subtract with tilemap corners and divide by tilesize to get 
// the anount of tiles that is outside of the cameras scoop
floor = Math.floor( min - ( tilemap.center - tilemap.extent ) / tilesize)
ceil = Math.ceil( max - ( tilemap.center + tilemap.extent ) / tilesize)

if(floor.x > 0)
    sx+=floor.x
if(floor.y > 0)
    y+=floor.y

if(ceil.x < 0)
    mx+=ceil.x
if(ceil.y < 0)
    my+=ceil.y

for(; y<my; y++)
    // x need to be reset each y iteration, start value are stored in sx
    for(x=sx; x<mx; x++)
       // render tile x in tilelayer y

Объяснил понемногу. Первым делом в функции рендера мы будем использовать несколько переменных.

// x and y are counters, sx is a placeholder for x start value as x will 
// be in the inner loop and need to be reset each iteration.
// mx and my will be the values x and y will count towards too.
x=0,
y=0, 
sx=0, 
mx=total_number_of_tiles_on_x_axis, 
my=total_number_of_tiles_on_y_axis

Чтобы предотвратить рендеринг всех плиток, вам необходимо предоставить либо похожий на камеру объект, либо информацию о том, где видимая область начинается и останавливается (в мировом пространстве, если сцена подвижна)

В этом примере я предоставляю объект камеры для функции рендеринга, у которой есть центр и экстент, сохраненный как 2d векторы.

// calculate the lowest and highest worldspace values of the cam
min = cam.center - cam.extent
max = cam.center + cam.extent

// subtract with tilemap corners and divide by tilesize to get 
// the anount of tiles that is outside of the cameras scoop
floor = Math.floor( min - ( tilemap.center - tilemap.extent ) / tilesize)
ceil = Math.ceil( max - ( tilemap.center + tilemap.extent ) / tilesize)
// floor & ceil is 2D vectors

Теперь, если этаж выше 0 или ceil ниже 0 на любой оси, это означает, что за пределами совка камеры столько же плиток.

// check if there is any tiles outside to the left or above of camera
if(floor.x > 0)
    sx+=floor.x// set start number of sx to amount of tiles outside of camera
if(floor.y > 0)
    y+=floor.y // set startnumber of y to amount of tiles outside of camera

 // test if there is any tiles outisde to the right or below the camera
 if(ceil.x < 0)
     mx+=ceil.x // then add the negative value to mx (max x)
 if(ceil.y < 0)
     my+=ceil.y // then add the negative value to my (max y)

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

// will loop through only the visible tiles
for(; y<my; y++)
    // x need to be reset each y iteration, start value are stored in sx
    for(x=sx; x<mx; x++)
       // render tile x in tilelayer y

Надеюсь это поможет!

0

Источник

user2652729 02 авг '15 в 17:51

Другие вопросы по тегам c++ optimization graphics 2d tile-engine

18 апр '13 в 10:26 2013-04-18 10:26 · Accepted Answer · 2013-04-18 10:26

Оптимизация итерации карты довольно проста.

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

Получив эти координаты плитки (tl, tt, tr, tb), вы можете очень легко вычислить первую видимую плитку в вашем одномерном массиве. (То, как вы вычисляете любой индекс плитки по 2D-координате: (y*width)+x - не забудьте сначала убедиться, что входная координата верна.) Затем у вас просто есть двойной цикл for для итерации видимых плиток:

int visiblewidth = tr - tl + 1;
int visibleheight = tb - tt + 1;

for( int rowidx = ( tt * layerwidth ) + tl; visibleheight--; rowidx += layerwidth )
{
    for( int tileidx = rowidx, cx = visiblewidth; cx--; tileidx++ )
    {
        // render m_Tiles[ tileidx ]...
    }
}

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

Что касается вашей ошибки, почему у вас есть x, y, left, right, width, height для камеры? Просто сохраните положение камеры (x,y) и вычислите видимый прямоугольник по размерам экрана / окна просмотра вместе с любым заданным вами коэффициентом масштабирования.