Ein Array aus Listen für Kollisionserkennung?



  • Hallo liebe C++ Gemeinde,

    ich bin schon seit einiger Zeit als Hobby damit beschäftigt, ein "einfaches" 2D Rollenspiel zu basteln. Anfangs wollte ich auf rundenbasierte Kämpfe a la Final Fantasy, Pokemon & co. setzen. Aber in letzter Zeit würde ich das ganze doch lieber in Echtzeit haben. Der Grund wieso ich mich bisher davor gedrückt hab, war die KI Programmierung und die Kollisionserkennung bei vielen Gegnern 😉

    Ich hab mir schon viele Threads zu dem Thema durchgelesen und ein einfaches durchlaufen einer std::list voll mit Gegner objekten möchte ich nicht, da ich (auch wenn es ein Hobby ist) gerne den Code so perfomant wie möglich schreiben möchte. Also bin ich dann über Threads mit Sektorisierung der Spielwelt mit Hilfe von Binär Bäumen gestossen. Da muss ich dann aber wieder zugeben, dass ich dafür nicht kreativ/schlau? genug bin, um zu wissen, wie ich diese auf einer 2D Tile Map umsetzen soll 😕

    Also wollte ich einen eigenen Weg finden und hab überlegt, ob man denn nicht über die ganzen Grafik Layer (1 Ebene für Bodengrafiken, 2te für Häuser Bäume etc.) einen logischen Layer legen könnte in dem festgehalten wird, wer sich wo befindet.

    Quasi ein 2Dimensionales Array aus std::list<*LivingCreature>

    und jedesmal wenn sich der Spieler oder ein Gegner bewegt, wird überprüft auf welchem Array feld er sich befindet ([x][y]) und wenn er ein neues Feld betritt, wird der Pointer zu diesem Spieler oder Gegner aus der Aktuellen std::list gelöscht und in die list der neuen Array position verschoben.

    Und bei einem Hittest würde ich dann schauen, in welche Richtung der Spieler guckt und demnach einfach nur einen Kollisionstest machen, in dem ich die Listen von den angrenzenden Array Feldern durchlaufe.

    Ist diese Lösung geeignet für mein Vorhaben, wenn ich a la Diablo gerne mehrere Gegner auf den Helden zukommen lassen möchte und man eine Gruppe aus bis zu 3 Spielern steuern soll?

    Ist das ganze performant oder hab ich irgendwo einen grossen Denkfehler?

    Freue mich über Anregungen, Kritik und Ideen 🙂



  • Ich hätte da auch eine Idee, die klingt zwar nicht extrem schnell, aber schon schnell und sehr einfach.
    Du macht für je 16*16 Tiles eine Liste.
    Wenn sich einer bewegt, muß er nur die 9 Listen seiner Nachbarschaft durchgehen, statt die ganze Welt.

    Ähm, warum nicht für jedes Tile eine eigene Liste?


  • Mod

    normalerweise hast du bei 2d tiled based rpgs pro tile einen gegner, entsprechend reicht ein byte-index eintrag auf den aktuellen gegner, da du vermutlich nicht mehr als 256 gegner verwalten wirst.

    falls du dennoch mehr als einen gegner haben willst, kannst du eine einfache linked list oder double linked list machen. (sollte selbst mit den byte-indices gut gehen).

    es gibt spiele die so alle entities verwalten, z.b. baeume, haeuser etc.
    das hat ein paar nette eigenschaften,
    - dass es mit den ganzen anderen tile daten die man normalerweise hat (z.b. boden texture id, eigenschaften wie begehbar,blockierend, lava, wasser.. ), kombiniert abgelegt werden kann. z.b. mal etwas 6bit, mal 3bit, sodass du am ende aber dennoch bei 'freundlichen' 32bit ankommst.
    -dass es sich einfach streamen laesst, falls deine level gross ist, du laedst einfach nur 'bitmaps', und das ist auch gut komprimierbar z.b. in einem zip archive. (z.b. werden die meisten felder keine entities haben, somit 0 sein und zip wird das dank huffman gut verkleinern.


Anmelden zum Antworten