Нужна помощь в оптимизации C++

Question

Я запрограммировал простую игру, ведущую в нисходящую машину, которая напоминает первый GTA, на GameBoyAdvance. Для этого я использовал только векторную графику, и GBA не справляется с этим очень хорошо; в основном с 5 пешеходными инстанциями он отстает.

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

Испытание на столкновение, которое я использую, - это SAT (теорема о разделительной оси), поскольку я нашел, что это самый легкий для проверки столкновения с векторной графикой; игра очень проста сама.

Вот код:

/* 
GTA Vector City 
Author: Alberto Taiuti 
Version: 2.0 
*/ 

#include "Global.h" 
#include <string.h> 
#include <cstdio> 
#include "font.h" 
#include "CVector2D.h" 
#include "CCar.h" 
#include "CPed.h" 
#include <vector> 
#include <memory> 

/* GLOBAL VARIABLES */ 
void CheckCollisionsRect(CRect *test_a, CRect *test_b); 
std::vector<CVector2D> PrepVectors(CRect *shape); 
CVector2D GetMinMaxShape(std::vector<CVector2D> vect_shape, CVector2D axis); 
void CheckCollisionRectVSPoint(CRect *test_a, CVector2D *point); 

/* MAIN */ 

// The entry point for the game 
int main() 
{ 
// Frame counter 
uint32_t frames = 0; 

// Previous & current buttons states 
static uint16_t prev_buttons = 0, cur_buttons = 0; 

    // Put the display into bitmap mode 3, and enable background 2. 
REG_DISPCNT = MODE4 | BG2_ENABLE; 

    // Set up the palette. 
SetPaletteBG(BLACK, RGB(0, 0, 0)); // black 
SetPaletteBG(WHITE, RGB(31, 31, 31)); // white 
SetPaletteBG(GREY, RGB(15, 15, 15)); // grey 
SetPaletteBG(RED, RGB(31, 0, 0)); // red 
SetPaletteBG(GREEN, RGB(0, 31, 0)); // green 
SetPaletteBG(BLUE, RGB(0, 0, 31)); // blue 

// Create car instance 
CCar *car = new CCar(50,50); 

// Create a building 
/*CRect *test_b = new CRect(100.0f, 100.0f, 30, 30); 
CRect *test_c = new CRect(120.0f, 120.0f, 30, 30); 
CRect *test_d = new CRect(30.0f, 30.0f, 30, 30);*/ 

// Pedestrian instances 
int ped_number = 10; // Number of pedestrians 
std::vector<CPed*> peds; // Ped. entities container (made of smart pointers) 
typedef std::vector<CPed*>::iterator p_itor; // Iterator 

for(int i = 1; i <= ped_number; i++) 
{ 
    peds.push_back(new CPed(i, RED, 2.0f)); 
} 

// Check whether the game is over 
bool end = false; 

// Main loop 
while (!end) 
{ 
    // Flip the screen 
    FlipBuffers(); 

    //Clear the screen 
    ClearScreen8(BLACK); 

    // Update frame counter 
    frames ++; 

    // Get the current state of the buttons. 
    cur_buttons = REG_KEYINPUT; 

    // Handle Input 
    car->HandleInput(prev_buttons, cur_buttons); 

    // Logic 

    car->Update(); 
    for(int i = 0; i < ped_number; i++) 
    { 
     peds[i]->Update(); 
    } 

    for(int i = 0; i < ped_number; i++) 
    { 
     CheckCollisionRectVSPoint(car->shape, peds[i]->pos); 
    } 

    /*CheckCollisionsRect(car->shape, test_b); 
    CheckCollisionsRect(car->shape, test_c); 
    CheckCollisionsRect(car->shape, test_d); 
    CheckCollisionRectVSPoint(car->shape, test_ped->pos);*/ 

    // Render 
    car->Draw(); 
    for(int i = 0; i < ped_number; i++) 
    { 
     peds[i]->Draw(); 
    } 
    /*test_b->DrawFrame8(GREEN); 
    test_c->DrawFrame8(WHITE); 
    test_d->DrawFrame8(RED); 
    test_ped->Draw();*/ 


    prev_buttons = cur_buttons; 

    // VSync 
    WaitVSync(); 
} 



// Free memory 
delete car; 
//delete test_b; delete test_c; delete test_d; 
//delete test_ped; 
for(p_itor itor = peds.begin(); itor != peds.end(); itor ++)// Delete pedestrians 
{ 
    peds.erase(itor); 
} 

return 0; 
} 

void CheckCollisionsRect(CRect *test_a, CRect *test_b) 
{ 
// If the two shapes are close enough, check for collision, otherways skip and save calculations to the CPU 
//if((pow((test_a->points[0]->x - test_b->points[0]->x), 2) + pow((test_a->points[0]->y - test_b->points[0]->y), 2)) < 25.0f) 
{ 

    // Prepare the normals for both shapes 
    std::vector<CVector2D> normals_a = test_a->GetNormalsAsArray(); 
    std::vector<CVector2D> normals_b = test_b->GetNormalsAsArray(); 

    // Create two containers for holding the various vectors used for collision check 
    std::vector<CVector2D> vect_test_a = PrepVectors(test_a); 
    std::vector<CVector2D> vect_test_b = PrepVectors(test_b); 

    // Get the min and max vectors for each shape for each projection (needed for SAT) 
    CVector2D result_P1 = GetMinMaxShape(vect_test_a, normals_a[1]); // 
    CVector2D result_P2 = GetMinMaxShape(vect_test_b, normals_a[1]); // 
    // If the two objects are not colliding 
    if(result_P1.y < result_P2.x || result_P2.y < result_P1.x) 
    { 
     return; 
    } 
    CVector2D result_Q1 = GetMinMaxShape(vect_test_a, normals_a[0]); // First axis couple 
    CVector2D result_Q2 = GetMinMaxShape(vect_test_b, normals_a[0]); // 
    if(result_Q1.y < result_Q2.x || result_Q2.y < result_Q1.x) 
    { 
     return; 
    } 
    CVector2D result_R1 = GetMinMaxShape(vect_test_a, normals_b[1]); // 
    CVector2D result_R2 = GetMinMaxShape(vect_test_b, normals_b[1]); // 
    if(result_R1.y < result_R2.x || result_R2.y < result_R1.x) 
    { 
     return; 
    } 
    CVector2D result_S1 = GetMinMaxShape(vect_test_a, normals_b[0]); // Second axis couple 
    CVector2D result_S2 = GetMinMaxShape(vect_test_b, normals_b[0]); // 
    if(result_S1.y < result_S2.x || result_S2.y < result_S1.x) 
    { 
     return; 
    } 


    // Do something 
    PlotPixel8(200, 10, WHITE); 
    PlotPixel8(200, 11, WHITE); 
    PlotPixel8(200, 12, WHITE); 

} 
} 

// Check for collision between an OOBB and a point 
void CheckCollisionRectVSPoint(CRect *test_a, CVector2D *point) 
{ 
// Prepare the normals for the shape 
std::vector<CVector2D> normals_a = test_a->GetNormalsAsArray(); 

// Create a container for holding the various vectors used for collision check 
std::vector<CVector2D> vect_test_a = PrepVectors(test_a); 

// Get projections for the OOBB (needed for SAT) 
CVector2D result_P1 = GetMinMaxShape(vect_test_a, normals_a[1]); 
float result_point = point->DotProduct(normals_a[1]); 
// If the two objects are not colliding on this axis 
if(result_P1.y < result_point || result_point < result_P1.x) 
{ 
    return; 

} 
CVector2D result_Q1 = GetMinMaxShape(vect_test_a, normals_a[0]); 
result_point = point->DotProduct(normals_a[0]); 
// If the two objects are not colliding on this axis 
if(result_Q1.y < result_point || result_point < result_Q1.x) 
{ 
    return; 

} 

// Do something 
PlotPixel8(200, 10, WHITE); 
PlotPixel8(200, 11, WHITE); 
PlotPixel8(200, 12, WHITE); 
} 

// Returns a container with projection vectors for a given shape 
std::vector<CVector2D> PrepVectors(CRect *shape) 
{ 
std::vector<CVector2D> vect; 

// Create vectors for projection and load them into the arrays 
for(uint16_t i=0; i < 5; i++) 
{  
    // Get global position of vectors and then add them to the array 
    vect.push_back(shape->GetVectorGlobal(i)); 
} 

return vect; 
} 

CVector2D GetMinMaxShape(std::vector<CVector2D> vect_shape, CVector2D axis) 
{ 
// Set initial minimum and maximum for shape's projection vectors 
float min_proj = vect_shape[1].DotProduct(axis); 
float max_proj = vect_shape[1].DotProduct(axis); 
// Calculate max and min projection vectors by iterating along all of the corners 
for(uint16_t i = 2; i < vect_shape.size(); i ++) 
{ 
    float current_proj = vect_shape[i].DotProduct(axis); 
    // Select minimum projection on axis 
    if(current_proj < min_proj) // If current projection is smaller than the minimum one 
     min_proj = current_proj; 
    // Select maximum projection on axis 
    if(current_proj > max_proj) // If current projection is greater than the minimum one 
     max_proj = current_proj; 
} 

return (CVector2D(min_proj, max_proj)); // Return a vector2D as it is a handy way for returning a couple of values 
} 

Заранее большое спасибо всем, и извините за грязный код!

Answer 1

Одно выскакивает у меня

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

for(int i = 0; i < ped_number; i++) 
{ 
    CheckCollisionRectVSPoint(car->shape, peds[i]->pos); 
} 

Затем в детекторе столкновений, вы повторив много те же обработки на форме автомобиля каждый раз, когда: -

// Prepare the normals for both shapes 
std::vector<CVector2D> normals_a = test_a->GetNormalsAsArray(); 

// Create two containers for holding the various vectors used for collision check 
std::vector<CVector2D> vect_test_a = PrepVectors(test_a); 

.. и т.д ...

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

Answer 2

Я дал ему очень быстрое чтение, поэтому я, возможно, что-то упустил. Ну, есть очевидные советы для улучшения производительности, такие как перенос векторов в функции по ссылке. Использование приращения префикса вместо постфикса также является хорошей привычкой. Эти два правила, безусловно, не похожи на «преждевременную оптимизацию, корень ...». Не удаляйте пешеходов один за другим, но используйте std::vector::clear().. И если вы утверждаете, что используете смарт-указатели, вы стремитесь, потому что кажется, что у вас есть утечка памяти, потому что вы не удалили указатели пешеходов. И используйте ключевое слово const. После того, как вы сделаете очевидную коррекцию, и скорость все еще не удовлетворительна, вам нужно использовать профайлер.

И прочитал что-то об оптимизации, вот например: http://www.agner.org/optimize/optimizing_cpp.pdf