Algo zur... ähmm.. zusammenhängenden Flächenerkennung?

Hi,

Ich benutze in meinem momentanen Projekt die box2d engine (eine 2D-Physik Engine).

Kurze Einführung:

Ich habe in meiner Spielwelt dynamische (also sich bewegende, physikalisch interagierende) und statische (sowas wie feste betonpfeiler) Objekte, die zwar auch physisch mit dynamischen Objekten interagieren, jedoch nicht reagieren, d.h. sie bewegen sich nicht wenn sie gestuppst werden , jedoch bewegen sich die Objekte die dran stupsen.

Gängige während des Spielablaufs erzeugte Objekte (z.B. geworfene Steine) sind bei mir immer dynamisch, und eben statische Objekte (z.B. Tiles meiner Tilemap) sind immer statisch.

Um Performance und Speicherplatz zu sparen, will ich nicht für jeden einzelnen Tile ein statisches Objekt anlegen. Da große Teile des Bodens, also eigentlich alles bis auf Treppen, Erhöhungen (Klippen usw), miteinander eben sind, könnte ich diese Teile zu einem sehr großen statischen Objekt zusammenfassen.

Hier mal eine grobe Zeichnung:

[ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ]
[ ][ ][ ][X][X][ ]
[X][X][X][X][X][X]
[X][X][X][X][X][X]

Boden [ ] Leerer Himmel

Wie sich erkennen lässt, sind die unteren 2 Bodenreihen eben und könnten als 1 statisches Objekt dargestellt werden. Auch die Oberen beiden abgrenzenden "x-es" könnte man zu einem Objekt zusammenfassen.

Ich suche jetzt einen Algorithmus, mit denen ich diese "Ebenen" (nicht im mathematischen Sinn) finden kann.

Edit: Brute Force Verfahren (alle Möglichkeiten durchrechnen) ist sehr schlecht, da die Map unter Umständen riesig sein kann und ich für sowas keine 2 Min Ladezeiten haben will, ausserdem wird der Spieler das Terrain in Echtzeit beeinflussen können.

Tipps?

Kuldren

Ich weiß nicht ob ich dein Problem richtig verstanden habe aber könntest du nicht beim Erzeugen der einzelnen Objekte prüfen ob sie im deltaXYZ - Bereich eines Objekts liegen (also somit zu der Ebene gehören?)
Wenn jetzt ein Objekt nicht im Einzugsbereich eines anderen liegt hast du eine neue Ebene gefunden. (Passiert beim ersten Objekt ja auch)
Klar würde dass bei vielen Objekten eine Weile dauern aber wenn du das geschickt löst, sind das nur ein paar (zeitlich gesehen) billige Vergleiche und würde selbst bei 10000 Objekten recht schnell stattfinden.
Aber wie gesagt...kein Schimmer ob ichs richtig verstanden habe

Kuldren schrieb:

Ich weiß nicht ob ich dein Problem richtig verstanden habe aber könntest du nicht beim Erzeugen der einzelnen Objekte prüfen ob sie im deltaXYZ - Bereich eines Objekts liegen (also somit zu der Ebene gehören?)
Wenn jetzt ein Objekt nicht im Einzugsbereich eines anderen liegt hast du eine neue Ebene gefunden. (Passiert beim ersten Objekt ja auch)
Klar würde dass bei vielen Objekten eine Weile dauern aber wenn du das geschickt löst, sind das nur ein paar (zeitlich gesehen) billige Vergleiche und würde selbst bei 10000 Objekten recht schnell stattfinden.
Aber wie gesagt...kein Schimmer ob ichs richtig verstanden habe

Es geht nicht um mathematische Ebenen. Die liegen alle in einer Ebene, da es 2D ist. Ich meinte damit praktisch, dass die einen "geraden" (also "ebenen") Weg ohne Stufen oder sonstwas bilden.

gerader, ebener weg:

[ ][ ][ ][ ][ ][ ]
[x][x][x][x][x][x]

(die kleinen vierecke sind jeweils einzelne tiles)
ließe sich zu einem langen objekt (das die länge x.length*6 hätte und höhe x.height).
würde ich nur die insgesamten objekte zeichnen so sähe das so aus:

[ ][ ][ ][ ][ ][ ]
[                ]

ebenfalls gerader, ebener weg, aber mit einem "hübbel" oben drauf, der sich nicht mit den anderen , in einer "gerade" liegenden objekten zu einem objekt zusammen fassen ließe:

[ ][ ][ ][x][ ][ ]
[x][x][x][x][x][x]

zusammenfassend gezeichnet:

[ ][ ][ ][x][ ][ ]
[                ]

mittels eines algos finden, um so wenige statische objekte wie möglich zu erzeugen.

so verständlicher?

Peppie

Ist das ganze eine Art Scrolling-Game? Wenn ja, dann lass doch deinen Algo so und zeichne immer nur den Ausschnitt den man sehen kann, da wäre ja dein Problem mit der "großen" Map egal, oder?

Kuldren

Peppie schrieb:

Ist das ganze eine Art Scrolling-Game? Wenn ja, dann lass doch deinen Algo so und zeichne immer nur den Ausschnitt den man sehen kann, da wäre ja dein Problem mit der "großen" Map egal, oder?

Er zeichnet sicher ohnehin nur den Teil der Map der im Bild ist.

@TravisG:
Die Idee, die ich gepostet habe funktioniert auch bei 2D:
Am Anfang erstellst du ja deine Tiles irgendwie - und in dem Moment prüfst du ob im Raster links bzw Rechts ein anderes statisches Tile existiert.
Am besten du prüfst nur links weil du wahrscheinlich von links nach rechts initialisierst.
Wenn jetzt 2 Tiles zusammenhängen erstellst du ein 2er Tile und ignorierst die 2 einzelnen. Wenn jetzt noch eines daneben liegt wird auch dieses nicht einzeln initialisiert sondern eben an das 2er drangehängt und somit das 2er um die Größe des neuen Tile( welche alle wohl die gleiche Größe haben) verlängert..usw
Hoffe das war verständlicher. Natürlich betrifft das nur die Berechnungen bzgl. der Boundingboxes.
So gehst du einfach das Feld Zeile für Zeile durch und erhältst deine zusammenhängenden Tiles.
Hoffe das hilft.

EDIT: wenn du das ganze mit einem Raster (Feld/Vector/Whatever) machst ist es noch einfacher. So setzt du das Feld einfach auf true wenn ein Tile vorhanden ist ansonsten auf false. Das lässt sich dann einfach mit Feld[actPos.x-1][actPos.y] prüfen

Jester

Könnte man also die Aufgabenstellung folgendermaßen beschreiben?

Gesucht ist eine Überdeckung der X-Regionen mit möglichst wenigen disjunkten (achsenparallelen) Rechtecken.

Oder meinst Du was anderes?

Jester schrieb:

Könnte man also die Aufgabenstellung folgendermaßen beschreiben?

Gesucht ist eine Überdeckung der X-Regionen mit möglichst wenigen disjunkten (achsenparallelen) Rechtecken.

Oder meinst Du was anderes?

genau das.

@kuldren. die idee ist gut, aber nicht optimal. wenn die entstehenden "groß"-rechtecke nur "1-zeilig" sind, reicht das natürlich gut aus, aber ich will auch mehrere reihen zusammenfassen.

also so:

[x][x][x][x][x][x][x]

dies so zusammenzufassen, dass das rauskommt:

[                   ]

ist performancetechnisch kein problem.

allerdings das:

[x][x][x][ ][x]
[x][x][x][x][x]
[x][x][x][x][x]

in das:

[       ][ ][x]
[              ]  \_ //Die beiden Zeilen sollen
[              ]  /  //ein einziges statisches Objekt sein.

wird schon schwieriger, zumal es pro Bildschirmausschnitt meist ca. 100-200 teilige Reihen (in x und y richtung) gibt (also je 100-200 x tiles von links nach rechts und von oben nach unten). Da wird das Brute Force Verfahren schon unperfomanter, wenn ich ständig überprüfe "OK, eine Reihe oben ist komplett, nachguggen ob sich mit der Reihe unter Dieser vll ein größeres Rechteck bilden lässt. Ok so ganz geht das nicht, also machen wir mal das obere Rechteck um ein 1 Stück kürzer und guggen nochmal nach".

klar könnte ich das trotzdem so machen, aber mir ist es wichtig an dieser Stelle performance zu sparen, da ich mir sicher bin, dass es für sowas schon gut funktionierende Algos gibt. Schliesslich hab ich noch viel vor, und so will ich von Anfang an jeden Frame wie Gold hüten.

Kuldren

Naja...wenn ich das richtig sehe willst du die große Objekte ja für die Kollisionsabfragen verwenden. Wenn du genauso vorgehst wie beschrieben und anschließend alle initialisierten Objekte nochmal auf gleiche Länge und Position +/- 1 in y prüfst kannst du auch diese zusammenfassen

Klar willst du die Frames wie Gold hüten, aber das lässt sich am Anfang schnell berechnen...und 200 Zeilen bei 200 Spalten sind zwar 40000 Tiles aber das brauchst du alles anfangs nur einmal durchführen - das geschieht in kürzester Zeit.
Wenn die Landschaft sich während des Spiels aber ändern sollte kannst du ja die betroffenen Regionen nochmal überprüfen lassen.

Jester

Kuldren schrieb:

Naja...wenn ich das richtig sehe willst du die große Objekte ja für die Kollisionsabfragen verwenden. Wenn du genauso vorgehst wie beschrieben und anschließend alle initialisierten Objekte nochmal auf gleiche Länge und Position +/- 1 in y prüfst kannst du auch diese zusammenfassen

Ich hab jetzt nicht lange darüber nachgedacht, aber meine Vermutung wäre, dass dieses Vorgehen bei diesem Problem sogar eine optimale Lösung findet.