Nicht-kachelbasierte Map Engine

[S.O.P.M.]

Hallo,

eine vielleicht nicht ganz so triviale Angelegenheit aber sicher auch gut lösbar, nur ich komme noch auf keine richtig befriedigende Lösung bisher: mich würde interessieren, wie man am sinnvollsten eine Map Engine schreibt, die nicht auf Kacheln basiert - heißt konkret, die Map ist nicht aus gleichgroßen Kacheln zusammengesetzt, sondern besteht aus unterschiedlich großen Sprites, die völlig nach Belieben angeordnet sein können. Nun stelle ich mir vor, dass alle diese Sprites für die Map in einem Array eines Types abgelegt sein müssten, in welchem X-Y-Position, Sprite ID und vielleicht die Ebene erfasst sind. So weit so gut. Nun müsste ja jedesmal das komplette Array durchgegangen werden, um herauszufinden, ob ein bestimmtes Sprite sich gerade im Bildausschnitt befindet und gezeichnet werden muss. Bei einer großen Map mit sagen wir ein paar tausend Objekten bestimmt zu langsam oder? Aber dann kommt auf jeden Fall noch die Kollisionserkennung dazu, für die ja schon wieder das gesamte Array durchforstet werden müsste, ob ein Sprite gerade mit z.B. dem Spieler kollidiert. Da es kein klares Raster gibt, lassen sich die für die Prüfung infrage kommenden Objekte nicht eingrenzen, das ist mein Problem. Dann hatte ich mir überlegt, dass es doch ein Raster geben müsste, also wie mit Kacheln, nur dass jede Kachel in einem sehr eingegrenzten Bereich durch Offset-Angaben verschoben dargestellt werden kann, für eben die künstlerische Freiheit der Map. Dann hätte man alles wieder in einer geordneten Struktur, nur was wenn in einem kleinen Bereich mehrere Objekte dargestellt werden sollen? Ich hoffe, mein Problem nachvollziehbar geschildert zu haben. Es geht im Grunde darum, eine geeignete Datenstruktur zu finden, um schnelle und gezielte Abfragen zu ermöglichen.

Gruß
S.O.P.M.

[Kitty Hello]

Pach elente in blöcke (2D octree)

[S.O.P.M.]

Das ist aber leider kein Lösungsvorschlag für mein Problem. Auf die Idee, größere Objekte aus mehreren Kacheln zusammenzusetzen, bin ich auch schon gekommen, doch das würde die künstlerische Freiheit immernoch einschränken, da Objekte nicht frei plaziert werden können und immernoch in einem Raster sitzen. Außerdem erschwert diese Methode einen intuitiven Mapeditor, bei welchem der Künstler ja fertige Objekte ganz schnell auf die Map setzen können soll. Der Map Editor bräuchte dann aus einem Tileset noch aufwendige Informationen, welche Kacheln er als ein zusammenhängenes Objekt behandeln soll. Also alles nicht so toll...

[Kitty Hello]

Nein. Ichmeine ganz frei. Aber dann gruppiere sie in einem Raster zum schnellen Abfragen und zeichnen. Verstehst eas ich meine?

[S.O.P.M.]

Ich bin mir nicht sicher, ob ich recht verstehe. Wenn eine Map völlig freie und unregelmäßig positionierte Objekte hat, wie soll ich die dann in einem Raster gruppieren? Wie meinst du, sollen die Objekte nun gespeichert werden - in einem Array eines Types, also in Form einer Datenbank oder klassisch in einem Raster? Klar man könnte sicher einen Algorithmus schreiben, der die Objekte in der Datenbank dann weitestgehend ordnet und anhand derer Positionen diese verschiedenen Quadranten zuweist. Doch durch die Unregelmäßigkeit, also der unterschiedlich vielen Objekte in bestimmten Bereichen, hätte man unterschiedlich große Datengruppen und dann würde eine gezielte Abfrage doch wieder nicht funktionieren. Ich kapier's nicht

[kanonet]

Einteilung in Gruppen (Octree) ist schon der richtige Ansatz. Die Gruppen können ja ruhig unterschiedlich groß sein, unregelmäßig gerastert und sich gegenseitig überschneiden. Es geht ja nur darum dass sich die Anzahl der Vergleiche etc. reduziert. Den Nutzer muss das nicht unbedingt einschränken, du kannst einfach im Hintergrund die Gruppen aus den Nutzerdaten errechnen.
Statt dann beim Zeichnen oder der Kollision hunderte Objekte zu testen, testest du einfach die Boundingbox aller Gruppen und nur wenn ein Test positiv war, testest du alle Tiles in der Gruppe. Normalerweise sollte dir da deutliche Einsparungen bringen.

[S.O.P.M.]

Ok, danke erstmal soweit für die Antworten. Das klingt erstmal in der Theorie gut. Wüsste jetzt zwar spontan nicht, wie ich das programmtechnisch genau umsetzen sollte, aber ich versuche mir nochmal einen Kopf drum zu machen. Die Frage ist halt, wie ich die Map formattechnisch speichere.

Eine etwas abgefahrene Idee wäre noch, zu jedem Objekt der Map Informationen über das nächste Nachbarobjekt für alle 4 Richtungen N, O, S, W zu speichern. Am Ende befinden sich dann nur die Objekte temporär im Speicher, die im aktuellen Kartenausschnitt zu sehen sind. Sobald die Map in eine Richtung weiterscrollt, werden die nächsten Nachbarobjekte geladen und mittlerweile nicht mehr sichtbare gelöscht