Zufällige Verteilung in Zonen

Aus EnigmaWiki

Verfügbare Sprachen: Deutsch, English, Русский

Inhaltsverzeichnis 1 Zufällige Verteilung von Objekten in Zonen 1.1 Problemstellung 1.2 Lösungsansatz 1.3 Lösungsbeispiel 1.4 Analyse

Zufällige Verteilung von Objekten in Zonen

Problemstellung

Man möchte ein (oder mehrere) Objekt(e) zufällig verteilen. Das Problem dabei ist, dass sie nur in bestimmten Positionen liegen dürfen. Das einfachste Beispiel ist ein Stein, der innerhalb eines Rechtecks (einer Zone) liegen muss. Das ist noch sehr einfach. Wenn aber die Form der Zone nicht mehr rechteckig ist, wird das schnell etwas komplizierter.

Lösungsansatz

Man zerlegt die Zone in möglichst wenige, sich nicht überlappende Rechtecke. Überlappen sich die Rechtecke, ist die Wahrscheinlichkeit ein Objekt in diesen "doppelten" Bereichen zu finden höher.

Man wählt nun zuerst ein zufälliges Rechteck aus der Liste aller Rechtecke und dann eine zufällige Position innerhalb des gewählten Rechtecks.

Annmerkung 1: Bei mehreren Objekten besteht immer das Problem des Überschreibens! Wir müssen also irgendwie feststellen, ob die soeben gewählte Position schon einmal gebraucht wurde. Man könnte das ignorieren, aber nur solange man nicht eine fixe Anzahl von Objekten haben muss. Gutes Beispiel sind Oxydsteine - fehlt einer, weil überschrieben, ist das Level unlösbar! Dafür gibt es 2 Ansätze: entweder man entfernt jede Position sofort nach Gebrauch aus dem Array oder man prüft bei jeder Position vor Gebrauch, ob schon ein Objekt an dieser Stelle liegt. Methode 1 kommt hier nicht in Frage, als müssen wir stets prüfen ...

Annmerkung 2: Besteht die Zone aus zu vielen einzelnen, unzusammenhängenden Stücken, im extremen Fall nur aus wenigen einzelnen 1-Feld-Positionen, wird dieser Ansatz ineffizient. Mann sollte dann eine Positionsliste vorziehen.

Lösungsbeispiel

rectangulars = {{{0,0},{2,12}},{{17,0},{19,12}},{{3,1},{16,2}},{{3,10},{16,12}}}
 
function set_obstacle(akt_rect)
    local left_border = akt_rect[1][1]
    local right_border = akt_rect[2][1]
    local top_border = akt_rect[1][2]
    local bottom_border = akt_rect[2][2]
 
    repeat
        x = random(left_border, right_border)
        y = random(top_border, bottom_border)
    until enigma.GetStone(x,y) == nil -- Damit wir nicht versehentlich einen anderen Stein überschreiben
 
    set_stone("st-woven",x,y)
end
 
function obstacle_wrapper()
    local n = table.getn(ractangulars)
    local r = random(1,n)
    set_obstacle(rects[r])
end

Analyse

Die variable rectangulars enthält die Daten aller Rechtecke, in denen jedes Feld benutzt werden darf. Sie ist eine einfach auflisten von Rechteckdaten. Diese wiederum besten aus einer Auflisten der Koordinaten 2er Ecken. Es sind die der oberen-linken und der unteren-rechten Ecke.

Die Funktion set_obstacle übernimmt genau die Daten über ein Rechteck. dann wird sie ein Objekt (hier einen st-woven) an zufälligen Koordinaten innerhalb dieses Rechtecks ablegen.

Bisher ist das alles noch nicht wirklich interessant.

Nun kommt aber die Funktion obstacle_wrapper. Sie wählt per Zufall eines der Rechtecke aus rectangulars aus und ruft damit die Funktion set_obstacle auf.

Im obigen Beispiel darf der st-woven nur in einem 3 Felder breiten Rahmen entlang des Levelrandes auftauchen.