Axis Aligned Spatial Division: Raum in zufällige Rechtecke teilen?

11

Ich brauche eine Methode, um den 3D-Raum in zufällig achsenausgerichtete Kastenformen zu unterteilen. Im Moment teile ich den 2D-Raum zu Testzwecken. Der unmittelbarste Ansatz, den ich gefunden habe, bestand darin, ein Rechteck der Größe (1, 1) zu definieren und dann alle vorhandenen Rechtecke rekursiv in zwei ungleichmäßige Rechtecke aufzuteilen, die sich zwischen Achse X und Y abwechseln.

Geben Sie hier die Bildbeschreibung ein

Das Problem liegt hier auf der Hand. Dieser Ansatz führt zu langen Dehnungslinien (rot markiert).

Geben Sie hier die Bildbeschreibung ein

Was ich möchte, ist etwas organischeres (ich habe ein Beispiel beigefügt)

Sehen Sie, keine langen geraden Linien von oben nach unten oder von links nach rechts.

Geben Sie hier die Bildbeschreibung ein

Die einzige Einschränkung besteht darin, dass ich möglicherweise die minimale Größe des Rechtecks ​​begrenzen möchte, ohne die Granularität der Größen zu beeinträchtigen. dh wenn das kleinste Rechteck 1 Quadratzentimeter als der Sekunden kleinste Raum ist, sollte es nicht 2 Quadratzoll sein.

Idealerweise sollte der Algorithmus also alle drei folgenden Einschränkungen erfüllen:

  1. Rechtecke sind nicht unendlich klein.
  2. Rechteckgrößen sind keine diskrete Multiplikation der kleinsten Rechteckgröße. dh wenn das kleinste Rechteck eine Einheit von 3 Quadraten ist, als größere Rechtecke nicht auf 6, 9, 12 usw. beschränkt sind und stattdessen 3,2 oder 4,7 betragen könnten).
  3. Der Algorithmus läuft in Polynomzeit (muss schnell berechnet werden).
AturSams
quelle

Antworten:

12

Der Ansatz, den Sie skizzieren, ist einfach und nützlich, leidet jedoch wie gezeigt unter schrecklichen Artefakten. Vermeide es. Sie benötigen einen parallelen Wachstumsalgorithmus. Für ein Single-Threaded-Modell folgt ein Round-Robin-Ansatz:

  1. Platziere zufällig verschiedene Punkte in deinem Kartenraum. Normalisieren Sie ihre Verteilung (vermeidet hässliche Clusterbildung) mithilfe der Gaußschen Verteilung oder durch Anwendung eines iterativen Relaxationsalgorithmus, um zufällig platzierte Punkte gemäß der Lloyd-Relaxation für Voronoi-Diagramme voneinander zu entfernen . Diese Punkte repräsentieren die Schwerpunkte Ihrer zukünftigen Räume.
  2. (Parallel / Repeat Round-Robin für alle Räume) Wachsen Sie von jedem Punkt aus 4 Scheitelpunkte nach außen (ein rechteckiger Raum), wobei Sie sich pro globaler Iteration vom Mittelpunkt bewegen (Sie können verschiedene Räume mit unterschiedlichen Raten in jeder Achse vergrößern, anstatt für dieselbe alle, und sehen Sie, wie sich dies herausstellt - möglicherweise für ein organischeres / abwechslungsreicheres Ergebnis). Irgendwann beginnen einige Ihrer Rechtecke gegeneinander zu drücken. Begrenzen Sie an diesem Punkt das Wachstum in dieser Achse, stellen Sie sicher, dass sich die angrenzenden Kanten der beiden Räume genau berühren, und fahren Sie fort.
  3. Wiederholen Sie Schritt 2, indem Sie jeden Raum schrittweise vergrößern, bis das gesamte Wachstum durch benachbarte Räume oder die Grenzen der Karte eingeschränkt ist.
  4. Dadurch bleiben noch einige Leerzeichen frei. Das Problem besteht nun darin, Räume aus nicht belegten Räumen zu lokalisieren und daraus zu machen. Wenn Ihr zugrunde liegender Speicherplatz ein (ganzzahlig indiziertes) Raster ist (und jede Wachstumsiteration in diesem Raster einrastet), ist dies viel einfacher zu handhaben, da Sie Listen besetzter und nicht besetzter Rasterzellen verwalten können: Sobald Sie Nachdem Sie alle Ihre Räume platziert und vergrößert haben, durchsuchen Sie die unbesetzte Liste nach diskreten Räumen, die aus Gruppen benachbarter Zellen bestehen. Da viele nicht verwendete Räume nicht rechteckige Formen haben, müssen Sie eine Zelle zufällig aus diesem nicht rechteckigen Raum auswählen und auf ihre maximale Größe vergrößern, genau wie Sie es mit Räumen in Schritt 2 getan haben. Wiederholen Sie diesen Vorgang innerhalb dieser nicht -rechteckiger Raum, bis es vollständig gefüllt ist.
  5. Wiederholen Sie Schritt 4, bis Ihre Karte zu 100% belegt ist.
Ingenieur
quelle
Das ist ein guter Rat. Der Nachteil ist, dass es möglicherweise nichts unternimmt, um mich vor unendlich kleinen Rekten zu schützen. Ich brauche eine Möglichkeit, um zu begrenzen, wie klein und wie groß die Rechtecke sind. Derzeit arbeite ich an einer anderen Methode. Ich werde die Ergebnisse vergleichen und aktualisieren.
AturSams
@ArthurWulfWhite Dann war Ihre Frage unterbestimmt und sollte aktualisiert werden. Ihre minimale Raumgröße wird durch Ihre Kartenzellenauflösung bestimmt. Wenn Sie also grobkörnig genug sind, um die minimale Raumgröße zu berücksichtigen, können Sie die Achsen anschließend auf Gleitkommabasis anpassen, um ein organischeres Aussehen zu erhalten.
Ingenieur
Du hast Recht! Ich dachte, ich hätte diesen Teil geschrieben. Aber ich habe nicht. Ich entschuldige mich für diesen Fehler. Ja, mir ist die Rastergröße bekannt. Ein Raum kann nur so klein sein, wie es das Raster zulässt.
AturSams
OK - hoffe, Sie finden eine geeignete Lösung. Übrigens meinte ich "Gitterlinien anpassen", nicht "Achsen anpassen".
Ingenieur
1
Eigentlich mache ich so etwas locker, basierend auf den Konzepten, die du mir gedacht hast. Ich werde die Ergebnisse auch hier veröffentlichen.
AturSams
2

Wie Sie sehen können, habe ich es geschafft, die Welt von diesen Artefakten zu befreien. Die Idee ist sehr ähnlich.

  1. Teilen Sie das 2D-Feld in ein ungleichmäßiges Raster. Wenn zwei Linien zu eng sind, entfernen Sie eine.
  2. Wählen Sie ein Rechteck nach dem Zufallsprinzip aus und prüfen Sie, ob es über die Achse y (in der Höhe) geändert wurde und ob der direkte Nachbar über die Achse y geändert wurde. Ich habe beide nicht modifiziert, lassen sie das Segment zwischen ihnen neu verhandeln (einer spendet dem anderen etwas Platz).
  3. Machen Sie dasselbe wie in Schritt 2 nur dieses Mal auf der anderen Achse.
  4. Wiederholen Sie den Vorgang, bis Sie so viele wie möglich geändert haben.

Ungleichmäßiges Gitter (1):

Geben Sie hier die Bildbeschreibung ein

Verhandeln auf Achse x (2):

Geben Sie hier die Bildbeschreibung ein

Verhandeln auf der Achse y (3):

Geben Sie hier die Bildbeschreibung ein

Ergebnis (4):

Geben Sie hier die Bildbeschreibung ein

Geben Sie hier die Bildbeschreibung ein

AturSams
quelle
Dies wurde lose durch die Einsicht von @Nick Wiggill
AturSams
2
Man könnte dies weiter verbessern, indem man zuerst Gruppen von n * m benachbarten Zellen zufällig zu einem einzigen Rechteck zusammenführt. Dies maskiert das zugrunde liegende Raster, das in der obigen Ausgabe noch sichtbar ist. Die Verhandlung mit diesen größeren Rechtecken muss nun an allen Zellen entlang einer ihrer Kanten funktionieren.
DMGregory
IN ORDNUNG. Immer noch sehr viele kolineare Grenzen, ich würde weiter daran arbeiten, aber gut, dass Sie Ihre Lösung gefunden haben! Freut mich zu helfen.
Ingenieur
@DMGregory Ich habe dies in Betracht gezogen, aber ich wollte, dass das Verhältnis zwischen den kleinen und den großen Rekten etwas konsistent ist. Wenn dies eine Textur oder ein Level wäre, würde ich es definitiv tun (habe tatsächlich ein vorheriges Beispiel, das das tut).
AturSams
@ NickWiggill Ich kann die kolinearen Linien vollständig entfernen. Es geht nur darum, den Algorithmus zu optimieren. Es muss einen Weg geben, es weiter zu verbessern (Update mit der neuesten Variante)
AturSams