spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Hallo zusammen,
ich habe mal wieder ein kleines algorithmisches Problem. Und zwar möchte ich in einem Gitter der größe 11x11, in dem Felder frei (weiß) oder bereits belegt (schwarz) sein können, ausgehend von einem Feld, alle Rechteckgrößen (über freie (weiße) Felder hinweg) finden, die das Startfeld enthalten. Das Setup sieht also in etwa so aus:


Das Kreuz ist das Startfeld (ohne Einschränkung hat dies die Koordinaten (0,0)). Von den grauen Feldern um das Startfeld hinweg wissen wir, dass mindestens eines davon belegt ist, in der Praxis werden es meistens zwei sein.
Die schwarzen Felder stellen bereits belegte Felder dar. Ob, wie viele und welche Felder in dem Gitter belegt sind, ist unbekannt, abgesehen von dem mindestens einen Feld in Nachbarschaft zum Startfeld.
Nun möchte ich alle Rechteckgrößen herausfinden, die im freien Bereich liegen, die das Startfeld enthalten, sowie die Koordinaten der rechten unteren Ecke dieses Rechtecks.

Ein Beispiel aus der Praxis:

Da das Feld (0,-1) unter dem Startfeld blockiert ist, muss ich nur in der oberen Hälfte suchen (also in dem roten Bereich). Hier finde ich natürlich das triviale 1x1-Rechteck mit den Koordinaten (0,0) als "rechte untere Ecke". Wenn ich nach oben gehe, finde ich desweiteren 1x2, 1x3 und 1x4 Rechtecke mit (0,0) als Koordinaten in der rechten unteren Ecke.
Weiter geht es mit 2x2 und 2x3. Weitere 2x1 Rechtecke kann ich ignorieren, da es für mich keine Rolle spielt, ob das Rechteck liegt oder steht, da ich Objekte darin drehen kann und wir ja schon ein 1x2-Rechteck am Anfang gefunden haben. Dann finde ich noch ein 2x4-Rechteck mit den Koordinaten (3,0) in der rechten unteren Ecke, und am Ende sogar ein 2x8-Rechteck mit den Koordinaten (5,0). Auch ein 3x3 (Koordinaten (1,0)) und ein 3x4-Rechteck (Koordinaten (2,0)) können in dem freien Raum Platz finden. Eine gültige Ausgabe des Problems unter obigen Voraussetzungen wäre also:


Hat jemand eine Idee, wie ich das algorithmisch anfassen kann, oder geht da nur Trial&Error? Als Eingabe habe ich eine Matrix mit 1en und 0en, die jeder Koordinate zwischen (-5,-5) und (5,5) zuordnet, ob das Feld bereits belegt ist, ... und (0,0) ist immer das (freie!) Startfeld.
Rechtecke, die das Startfeld als Ecke haben, sind leicht zu ermitteln, etwas schwerer tue ich mich mit solchen wie das 3x4-Rechteck, das die Koordinaten (2,0) als rechte untere Ecke hat. Denn damit geht meine erste Lösung, mit Quadranten zu arbeiten, nicht mehr direkt auf. Oder komme ich nicht drum herum, die am Ende wieder aneinander zu puzzeln? Das Ganze sollte natürlich möglichst schnell berechenbar sein.

Oder gibt es dafür schon eine schönere Methode, oder einen Namen eines Algorithmus, nach dem ich mal googlen könnte?
Vielen Dank für Input

Ja an den Contest habe ich beim Erstellen des Posts auch schon gedacht Darfst du gerne dafür verwenden, wirklich eilig ist die Lösung nicht.

Zitat von »David Scherfgen«

Darf ich fragen, was das für ein Spiel(?) werden soll?

Klar darfst du. Es geht um einen Teil des Terrain-Generators für mein Spiel Space Engies. Dieser arbeitet mit Chunks, wobei die schwarzen Felder in obiger Aufgabe bereits generierte Chunks und die weißen noch nicht existente Chunks sind. Mit einer gewissen Wahrscheinlichkeit soll der Generator in einem neuen Chunk (der wäre das X in der obigen Aufgabe) ein Objekt generieren, statt einen Standard-Zufalls-Chunk mit Gesteinen, wobei ein Objekt, z.B. eine Raumstation, eben auch größer als ein Chunk sein kann. Ich möchte auf diesem Weg herausfinden, welche Rechteck-Formen an freien Chunks mir um den aktuellen Chunk zur Verfügung stehen, um daraus dann eine Liste der möglichen Objekte, die dort generiert werden können, zu erstellen, um daraus eines zufällig auszuwählen. Deswegen brauche ich auch die Position des Rechtecks.

Deine Methode sieht recht brute-force aus, ähnelt meinem ersten Ansatz. Ich habe jedoch überlegt, ob man das nicht noch effizienter hinbekommen kann. Zum Beispiel dadurch, dass ich ja die Belegungen der Nachbarfelder des X kenne, kann ich das Gitter ja schon einmal auf die Hälfte des Gitters, ein Viertel, oder sogar nur einen Streifen der Breite 1 eingrenzen. Wobei ich das neben der Möglichkeit, dass es nur ein 1x1-Rechteck gibt, als trivial abstemplet.

Ich habe überlegt, ob man nicht vielleicht (Voraussetzung nur 1 oder 2 blockierte Nachbarfelder) mit Quadranten arbeiten kann, in denen man deinen Algorithmus durchführt, um dann die Rechtecke benachbarter Quadranten zusammenzupuzzlen. Das könnte eventuell ein paar redundante Abfragen auf schwarz oder weiß ersparen.. Was denkst du? Oder vielleicht noch andere Ideen?

In der Theorie hast du mit den Komplexitätsklassen natürlich Recht, in der Praxis finde ich es jedoch ziemlich wichtig, ob ich §n^4§ oder §1/2*n^4§ Rechenoperationen brauche.
Nein, eigentlich muss es nicht sonderlich schnell sein, zumal man sogar noch weitere Einschränkungen zur obigen Aufgabe machen kann (z.B. brauche ich nur Rechtecke mit maximaler Kantenlänge von 5, das ergibt ein maximales Rechteck von 5x5 und damit könnte man das Feld sogar auf 9x9 reduzieren), aber man hat ja auch einen gewissen Optimierungsehrgeiz :-)