Kollisions-Check: Momentan O(n^2)

Ich musste gerade feststellen, dass das Performance-Leck nicht von der collides() -Funktion kommt, sondern von der for-Schleife:

for(auto& enemy : enemies) enemy.update();

Und da gibts nicht viel zu optimieren.
Soll ich Threads verwenden?
Nachteil davon ist, dass beide CPU's auf 70% arbeiten.
Ist das ok, oder ist das schon Vergewaltigung?

Columbo

Soll ich Threads verwenden?

Wenn es einen signifikante Beschleunigung verpasst, dann natürlich.

Im Ernst, das musst du schon selber testen. Es interessiert auch nicht, wie die Prozessoren dann ausgelastet sind, sondern ob dein Programm schneller läuft.

Arcoth schrieb:

Es interessiert auch nicht, wie die Prozessoren dann ausgelastet sind, sondern ob dein Programm schneller läuft.

Mit Threads funktioniert alles einwandfrei. Aber doch, wie sehr die Prozessoren ausgelastet sind, geht mich sehr wohl was an. 70% auf beiden CPU's, ist das nicht schon Vergewaltigung? Oder ist das im Grenzbereich, wo man noch "OK" sagen könnte?

Du hast doch für 100% CPU gezahlt, warum willst du dann nur 70% nutzen?

Na bei Spielen ist eigentlich keiner knausrig mit Ressourcen.

Ich will nicht oberlehrerisch wirken, aber Game-State-Updates auf mehrere Threads verteilen bringt normal eine ganz eigene Klasse von Problemem mit sich, ich hoffe das ist dir klar!

Prinzipiell ist multithreading natürlich gut um die CPU voll auszulasten, vor allem da heute ja jeder Mehrkern-CPUs hat.

Ich würde allerdings, wenn single-threaded jetzt schon Performanceprobleme macht definitiv schauen, warum das so ist. Ich halte es für eher unwahrscheinlich, dass Hobbyprojekte (wenn sie nicht gerade ein komplettes Universum simulieren, oder Vollphysik für alle Spielobjekte o.ä. implementieren) so viel Leistung benötigen sollte.

manni66 schrieb:

Du hast doch für 100% CPU gezahlt, warum willst du dann nur 70% nutzen?

Weil das meiner Meinung nach zu viel ist für ein textbasiertes Jump&Run von einer Map die 200x50 Zeichen groß ist und 100 Gegnern auf ihr sitzen hat...

gfgdfgdfg schrieb:

Na bei Spielen ist eigentlich keiner knausrig mit Ressourcen.

Das freut mich.

Ich will nicht oberlehrerisch wirken, aber Game-State-Updates auf mehrere Threads verteilen bringt normal eine ganz eigene Klasse von Problemem mit sich, ich hoffe das ist dir klar!

Ja. Aber bisher ging mir das Programm mit Multithreading noch nicht durch die Lappen

Prinzipiell ist multithreading natürlich gut um die CPU voll auszulasten, vor allem da heute ja jeder Mehrkern-CPUs hat.

Das finde ich nicht gut. Volle Auslastung. Das will ich ändern.

Ich würde allerdings, wenn single-threaded jetzt schon Performanceprobleme macht definitiv schauen, warum das so ist. Ich halte es für eher unwahrscheinlich, dass Hobbyprojekte (wenn sie nicht gerade ein komplettes Universum simulieren, oder Vollphysik für alle Spielobjekte o.ä. implementieren) so viel Leistung benötigen sollte.

Genau das. Gibt es etwas besseres als std::vector<tile> ? Ein Konstrukt, das schneller läuft? Könnte hier vielleicht eine (unodered_)map<position, char> eine Performance-Verbesserung bringen? Oder std::vector<std::vector<tile>> (auch wenn ich mir hier noch nicht vorstellen kann wie ich das umsetze)? Ich will jetzt nicht viel mit Code kommen, aber ich muss sagen, ich benutze erstaunlich oft solche Algorithmen wie find_if() , all_of() und any_of() . Ich habe mir sagen lassen, dass es bessere Wege gibt, um direkt auf etwas entsprechendes zugreifen zu können. Wie?

Also sofern ich alles bisher richtig interpretiere hast du eine 2D-Spielwelt, daher bietet sich natürlich auch ein 2D-Container an. Solltest du z.B. einen Doppelvektor nehmen:

std::vector<std::vector<tile>> map;
map.resize(WIDTH,std::vector<tile>(HEIGHT));

std::cout << "Tile in unterer Ecke: " << map[WIDTH-1][HEIGHT-1] << std::endl;
map[x][y] = SteinTile;
std::cout << "Map-Breite: " << map.size() << std::endl;
std::cout << "Map-Hoehe : " << map[0].size() << std::endl; //oder jedes andere Element, alle Spalten sind ja gleich hoch

Dann kannst du einfach über map[x][y] auf ein Tile zugreifen. Damit kannst du dann natürlich auch Koordinaten bei Checks wegwerfen, die zu weit weg sind usw., kein Grund mehr, über alle Tiles die es gibt zu iterieren.

Vektoren sind sehr sparsam, kommen also sehr nah an normale Arrays ran. Alternativ bietet, wenn die (maximale) Mapgröße immer fest steht, std::array<> noch ein modernen Wrapper um normale C-Arrays an, ich denke aber im Spielkontext ist vector<vector<>> sinnvoller.

Zur Performance: Wenn du ein Spiel programmierst, will man normal maximale Hardwarenutzung, denn mehr FPS = gut, weil flüssigere Optik. Heute probiert man ja bei z.B. 144 FPS hinzukriegen, damit VSync bei den 144 Hz-Monitoren funktioniert. Wie gesagt, bei Spielen guckt eigentlich keiner drauf, ob die Hardware am Anschlag läuft, das ist quasi gegeben.

Meep Meep

checker2 schrieb:

Ich musste gerade feststellen, dass das Performance-Leck nicht von der collides() -Funktion kommt, sondern von der for-Schleife:
for(auto& enemy : enemies) enemy.update();
Und da gibts nicht viel zu optimieren.

was genau macht enemy::update() ?

TyRoXx

checker2 schrieb:

Kann mir jemand einen Trick verraten?

Um bei Kollisionserkennung von O(n^2) wegzukommen, kann man einen Quadtree nehmen. Würde ich zumindest als erstes versuchen.

Jester

Also mein Bauchgefühl sagt mir, dass da irgendwo was ganz schön schief läuft, wenn es bei ca. 100 Einheiten schon anfängt zu ruckeln. Auf einem halbwegs aktuellen Rechner solltest Du in diesen Größenordnungen eigentlich keine Schwierigkeiten kriegen -- auch nicht wenn Du etwas mit quadratischer Laufzeit machst. Das ist fast unabhängig davon was Du konkret vor hast.

Insofern vermute ich, dass da irgendwo unabsichtlich Zeit verbraten wird (etwa indem Dinge mehrfach gemacht werden). Versuche mal genau herauszufinden wo die Zeit verbraten wird (Profiler nutzen!). Dann siehst Du klarer und kannst gezielt eingreifen.

Okay, ich hab jetzt den Profiler angeschmissen, und wo am meisten verbraucht wird, ist in movable_object::move() . Ich sehe jedoch nicht, wie ich die Methode optimieren könnte, drum poste ich den Code mal.

bool movable_object::change_left_direction() const{
    return std::any_of(tiles.begin(), tiles.end(), [this](const cc::tile& tile){
        return tile.position.x - 1 <= -1 || next_edge(map.get_tile(tile.position.x - 1, tile.position.y).character);
    });
}

bool movable_object::change_right_direction() const{
    return std::any_of(tiles.begin(), tiles.end(), [this](const cc::tile& tile){
        return tile.position.x + 1 >= map.width() || next_edge(map.get_tile(tile.position.x + 1, tile.position.y).character);
    });
}

void movable_object::move(){
    switch(current){
        case direction::left:
            if(change_left_direction())
                current = direction::right;
            else
                go_left();
            break;

        case direction::right:
            if(change_right_direction())
                current = direction::left;
            else
                go_right();
            break;

        default:;
    }
}

Eine andere Datenstruktur benutzen wurde ja schon erwähnt. Mir fällt das jetzt aber ehrlich gesagt ziemlich schwierig, eine andere Datenstruktur zu benutzen, weil ich blicke da gerade noch nicht so ganz durch. Aber es wurde erwähnt es solle auch mit quadratischen Laufzeit gut funktionieren, also will ich das erstmal versuchen. In map.get_tile(...) wird wiederum ein std::find_if() aufgerufen.

Hat jemand ne Ahnung, wie ich das optimieren könnte?
Echt nur mit ner besseren Datenstruktur?
Oder gehts auch einfacher?

Ich habe die Datenstruktur nun von Grund auf geändert. Man kann jetzt direkt mit map[x][y] zur gewünschten Position indizieren. Von find_if() any_of() und all_of() keine Spur mehr.
Danke euch für die Hilfestellung.