Ich verwende Verfahrenstechniken, um Grafiken für ein Spiel zu erstellen, das ich schreibe.
Um einige Hölzer zu erzeugen, möchte ich Bäume zufällig innerhalb eines regelmäßigen hexagonalen Gebiets, das um & lt; 0,0 & gt; zentriert ist, streuen.
Was ist der beste Weg, um diese Punkte auf einheitliche Weise zu generieren?
Wenn es ein regelmäßiges Sechseck ist, ist es die einfachste Methode, es in drei Rauten zu teilen. Auf diese Weise (a) haben sie die gleiche Fläche, und (b) Sie können einen zufälligen Punkt in einer beliebigen Raute mit zwei zufälligen Variablen von 0 bis 1 auswählen. Hier ist ein Python-Code, der funktioniert.
%Vor%Ein paar Leute in der Diskussion haben die Frage aufgeworfen, wie man eine diskrete Version des Sechsecks gleichmäßig bemustert. Die natürlichste Diskretisierung ist mit einem Dreiecksgitter, und es gibt eine Version der obigen Lösung, die noch funktioniert. Sie können die Rauten ein wenig zuschneiden, so dass sie jeweils die gleiche Anzahl an Punkten enthalten. Sie vermissen nur die Herkunft, die als Sonderfall gesondert zugelassen werden muss. Hier ist ein Code dafür:
%Vor%Und hier ist ein Bild.
alt text http://www.freeimagehosting.net/uploads/0f80ad5d9a.png
Wenn Sie eine gute rechteckige Bounding-Box für Ihr Sechseck finden können, ist die einfachste Möglichkeit, gleichmäßig zufällige Punkte zu erzeugen, das Zurückweisen von Stichproben ( Ссылка )
Suchen Sie also ein Rechteck, das Ihr Sechseck vollständig enthält, und erzeugen Sie dann gleichmäßig zufällige Punkte innerhalb des Rechtecks (dies ist einfach, erzeugen Sie unabhängig voneinander zufällige Werte für jede Koordinate im rechten Bereich). Überprüfen Sie, ob der zufällige Punkt in das Sechseck fällt. Wenn ja, behalten Sie es. Wenn nein, zeichne einen anderen Punkt.
Solange Sie eine gute Bounding-Box finden können (die Fläche des Rechtecks sollte nicht mehr als ein konstanter Faktor größer als die Fläche des Sechsecks sein, das es umschließt), wird dies extrem schnell sein.
Ein möglicherweise einfacher Weg ist der folgende:
%Vor%Betrachten Sie die Parallelogramme ADCO (Zentrum ist O) und AOBF.
Irgendein Punkt in diesem kann als eine lineare Kombination der zwei Vektoren AO und AF geschrieben werden.
Ein Punkt P in diesen beiden Parallelogrammen erfüllt
P = x * AO + y * AF oder x AO + y AD.
wobei 0 & lt; = x & lt; 1 und 0 & lt; = y & lt; = 1 (wir nehmen die mit BECO geteilten Kanten ab).
Ähnlich kann jeder Punkt Q in dem Parallelogramm BECO als die lineare Kombination der Vektoren BO und BE geschrieben werden, so dass
Q = x BO + y BE wobei 0 & lt; = x & lt; = 1 und 0 & lt; = y & lt; = 1.
So wählen Sie einen zufälligen Punkt
wählen wir
A mit Wahrscheinlichkeit 2/3 und B mit Wahrscheinlichkeit 1/3.
Wenn Sie A gewählt haben, wählen Sie x in [0,1] (beachten Sie das halboffene Intervall [0,1)] und y in [-1,1] und wählen Sie den Punkt P = x AO + y AF wenn y & gt; 0 wähle sonst P = x * AO + | y | * AD.
Wenn Sie B gewählt haben, wählen Sie x in [0,1] und y in [0,1] und wählen Sie den Punkt Q = x BO + y BE.
Es wird also drei zufällige Nummern erfordern, um einen Punkt auszuwählen, der je nach Situation gut genug ist.
Der traditionelle Ansatz (anwendbar auf Regionen mit beliebiger polygonaler Form) ist die trapezförmige Zerlegung Ihres ursprünglichen Sechsecks. Sobald dies erledigt ist, können Sie Ihre zufälligen Punkte durch den folgenden zweistufigen Prozess auswählen:
1) Wählen Sie ein zufälliges Trapez aus der Zerlegung. Jedes Trapez wird mit einer Wahrscheinlichkeit ausgewählt, die proportional zu seiner Fläche ist.
2) Wählen Sie einen zufälligen Punkt gleichmäßig in dem in Schritt 1 gewählten Trapez.
Sie können Triangulation anstelle von trapezförmiger Zerlegung verwenden, wenn Sie dies bevorzugen.
Zerschneide es in sechs Dreiecke (daher gilt dies für jedes reguläre Polygon), wähle zufällig ein Dreieck und Wählen Sie nach dem Zufallsprinzip einen Punkt im ausgewählten Dreieck .
Die Auswahl zufälliger Punkte in einem Dreieck ist ein gut dokumentiertes Problem .
Und natürlich ist das ziemlich schnell und Sie müssen nur 3 Zufallszahlen pro Punkt erzeugen - keine Zurückweisung usw.
Da Sie zwei Zufallszahlen erzeugen müssen, so machen Sie es :
%Vor%Sie können meine Arbeit von 2009 überprüfen, wo ich einen "genauen" Ansatz herleitete, um "zufällige Punkte" innerhalb verschiedener Gitterformen zu erzeugen: "hexagonal", "rhombus" und "dreieckig". Soweit ich weiß, ist es der "optimalste Ansatz", da für jede 2D-Position nur zwei Stichproben benötigt werden. Andere früher abgeleitete Arbeiten erfordern 3 Abtastungen für jede 2D-Position!
Hoffe, das beantwortet die Frage!
1) biege von Punkten zu Zahlen (nur aufzählen), Zufallszahl bekommen - & gt; Punkt bekommen.
Eine andere Lösung.
2) Wenn N - Länge der Sechseckseite, erhalten Sie 3 Zufallszahlen von [1..N], beginnen Sie von einer Ecke und bewegen Sie sich 3 Mal mit diesen Zahlen für 3 Richtungen.
Die obige Lösung zur Zurückweisungsentnahme ist intuitiv und einfach, verwendet jedoch ein Rechteck und (vermutlich) euklidische X / Y-Koordinaten. Sie könnten dies etwas effizienter machen (obwohl immer noch suboptimal), indem Sie einen Kreis mit Radius r verwenden und zufällige Punkte stattdessen mit Polarkoordinaten von der Mitte erzeugen, wobei die Entfernung rand () * r und Theta (in Radianten) wäre rand () * 2 * PI.
Tags und Links algorithm language-agnostic random procedural-generation
