2D-Welt verwalten

marten123

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

Ich lass mal folgenden link hier
http://www.roguebasin.com/index.php?title=Comparative_study_of_field_of_view_algorithms_for_2D_grid_based_worlds

rapso

das einfachste waere die welt gleichmaessig zu unterteilen, z.B. in teile die so gross sind wie deine sicht. dann sortierst du die objekte anhand des zentrums in diese "teile"
verbesserung: berechnest anschliessend fuer jedes teil die ausmasse von allem was drinnen ist. (weil die objekte herausragen koennten).
beim zeichnen, kannst du der einfachheit halber dann erst durch die "teile" mit einer for-Schleife gehen und alles was ausserhalb der sicht ist ueberspringen, gehst also nur fuer die sichtbaren "teile" mit einer for-Schleife die objekte durch, die einsortiert wurden.

das kannst du anschliessend beliebig verbessern/verkomplizieren, schau dir z.B. https://www.youtube.com/watch?v=RMBQn_sg7DA an

hustbaer

@marten123
Ich kann noch zwei Abänderungen von @rapso's Vorschlag anbieten:

Du fügst die Objekte in alle Teile/Abschnitte ein die sie überschneiden.
Du machst die den Umstand zu nutzen dass die Objekte eine maximale Grösse haben. Dabei fügst du die Objekte immer nur in den Abschnitt ein in dem z.B. der linke obere Punkt des Objekts liegt. Das musst du dann nur bei der Berechnung welche Abschnitte sichtbar sein könnten berücksichtigen. Also wenn z.B. keines deiner Objekte grösser als ein Abschnitt ist, dann musst du mit dieser Methode einfach nur links und oben jeweils einen Abschnitt mehr zeichnen.