Registriert: Di Feb 13, 2018 19:02 Beiträge: 24
Programmiersprache: Java
Hallo,
ich programmiere gerade ein 2D-Spiel. Das Spiel besteht aus einer großen Welt mit mehreren tausenden Objekten (Bodenteile, Bäume, Kisten, ...). Von den einzelnen Objekten sind aber in der Regel nicht alle sichtbar, sondern es befinden sich nur immer max. 100 Objekte im sichtbaren Bereich der 2D-Welt.
Wie kann ich nun am effizientesten ermitteln, ob ein Objekt im Sichtbereich liegt? Klar könnte ich bei jedem Durchlauf mit einer for-Schleife alle Objekte durchlaufen und prüfen ob sich im Sichtbereich liegen, aber das scheint mir nicht besonders effektiv zu sein.
Kennt ihr da bessere Möglichkeiten bzw. Verfahren? Irgendwas mit einer Baumstruktur oder so?
Registriert: Mi Jun 05, 2013 15:12 Beiträge: 166 Wohnort: Glinde
Programmiersprache: Delphi 7
Auch wenn es ein bisschen Spät ist. Ich habe meine 2D Spielwelt in Chunks unterteilt. Anhand meineres Sichtbereiches X/Y ermittle ich, welche Chunks ich rechnen muss.
Hierzu einfach mal eine kleines Beispiel: (Ich lasse jetzt mal beabsichtigt negative Zahlen und die echte zentrierung des Bildschirms weg)
Meine Welt ist 10 000 Felder groß. (100*100 Felder) Jedes Feld ist 10*10 Pixel groß. Jeder Chunk ist eine Displaylist an Objekten und umfasst 10*10 Felder. Mein Sichtbereich ist bei Pixel X 457 Y 543
Rechnung 1. (über welchen Feld bin ich gerade) X 457 Pixel durch Feldgröße 10 = X45 Y 543 Pixel durch Feldgröße 10 = Y54 Jetzt weiß ich bereits das mein Fenster bei Feld X45 Y54 sein muss.
Rechnung 2. (über welchen Chunk bin ich gerade) X 45 Feld durch Chunkgröße 10 = X4 Y 54 Feld durch Chunkgröße 10 = Y5 Ich befinde mich also in Chunk X4 Y5.
Ich sag das jetzt mal ganz allgemein. Wenn ich einen Array an Displaylisten habe. Dann zeichne ich jetzt einfach Chunk_Array[54] (X4 +(Y5*Chunkbreite(10))) etc 51 x x ;D x x x x x x 41 x x x x x x x x x 31 x x x x x x x x x 21 x x x x x x x x x 11 x x x x x x x x x 1 2 3 4 5 6 x x x x etc
Und wenn mein Sichtfeld größer ist, z.B (3*3) dann Zeichne ich halt
Code:
for Ix:= 0 to 2 do
for Iy:= 0 to 2 do
Chunk_Array[54+(Ix)+(Iy*10)]
Natürlich muss man prüfen, ob der zugriff nicht ausserhalb der Array liegt,aber das ist eine andere Geschicht.
Optimierung ist natürlich auch möglich. Ich weiß das meine Chunks 100*100 Pixel beinhalten, also kann ich alles auch in einer kleinen Rechnung machen.
_________________ 幸福は笑う人に来て ~~ koufuku wa warau hito ni kite Das Glück kommt zu denen die lachen
Registriert: Di Feb 13, 2018 19:02 Beiträge: 24
Programmiersprache: Java
Danke für eure Antworten und sorry für meine späte Antwort. Ich bin jetzt auch "Quadtrees" gestossen, das müsste eigentlich die optimale Lösung für mein Problem sein. Leider läuft der Quadtree-Algorithmus bei mir relativ langsam, was aber vermutlich nur an meiner Implementierung liegt. Muss mich da nochmal tiefer reinarbeiten.
Mitglieder in diesem Forum: 0 Mitglieder und 16 Gäste
Du darfst keine neuen Themen in diesem Forum erstellen. Du darfst keine Antworten zu Themen in diesem Forum erstellen. Du darfst deine Beiträge in diesem Forum nicht ändern. Du darfst deine Beiträge in diesem Forum nicht löschen. Du darfst keine Dateianhänge in diesem Forum erstellen.