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?


Schon mal vielen Dank für eure Hilfe,

Liebe Grüße arenas

Tutorial Octree müsste an der Stelle noch aktuell sein.

_________________
Steppity,✲steppity,✴step,❆step,✳step!
❆ ❄ ❄ ❄ ❅ ❄ ❆ ❄ ❅ ❄ ❅ ❄ ❅ ❄ ❄
❅ ☃ ❄ ❄ ❄ ❅ ❄ ❄ ❄ ❅ ❄ ☃ ❄ ❆ ❄ ❄

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

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

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.

Werde es solange erst mal mit Chunks probieren.

Nochmal vielen Dank für eure Antworten.


LG arenas