Gesucht: Effektiver Algorithmus für zufällige Anordnung von nicht-überlappenden MCs

[cip22]

Bei mir landen zwischen 3 und weit über 50 kleine MCs mit Textfeldern auf der Bühne; sie sollen zufällig, aber relativ gleichmäßig verteilt innerhalb bestimmter Grenzen erscheinen.

Wer hat den super-effizienten Algorithmus dazu? Mir kommt es ziemlich dämlich vor, jeden mit jedem MC einen Kollisionstest durchführen zu lassen, da muß es doch noch andere Möglichkeiten geben? Etwa mein Rechteck grob rastern die jeweiligen Felder in einem Array als 'besetzt' markieren? Dann sieht's aber wieder schwierig aus mit der besten (gleichmäßigen) Verteilung...

Wäre für Tips, Links etc. sehr dankbar. Vielleicht gibt's ja einen Schwarm-Algorithmus, der sich auch auf MCs *mit* Ausdehnung übertragen läßt...

Viele Grüße
cip

[wasi1]

Hab da mal im FF was über schnee gesehen der vom Himmel

fällt, weiß aber nicht ob der über nen Algorithmus gesteuert

wird.

Schau doch mal unter Suchen und Finden über Schnee nach.

Vielleicht hilfts.

[hgseib]

sieh dir mal da das zip an:

http://www.flashforum.de/forum/showt...390#post804390

funktioniert allerdings nach der "Mir kommt es ziemlich dämlich vor"- methode ;-)

ob man allerdings 50 mc's nicht überdeckend auf den bildschirm bekommt? da muss das zeug schon irre klein sein. oder programmierst du an einer kinoleinwand?

Hallo cip,

schöne Samstag Morgen-Aufgabe... versuch's mal damit:

arrangeMCs = function(baseName, numberOfMCs, scope, areaWidth, margin, overlap) {
    var x = 0;
    var maxHeight = 0;
    var rowY = 0;
    for (var i=0;i<numberOfMCs;i++) {
        var mc = scope[baseName+i];
        if (x+mc._width>areaWidth) {//Zeilenwechsel
            x = 0;
            rowY = maxHeight;
        }
        mc._x = x + margin + Math.random()*overlap*2-overlap;
        mc._y = rowY + margin + Math.random()*overlap*2-overlap;
        x += mc._width + margin;
        maxHeight = Math.max(maxHeight, mc._height+mc._y);//Höhe der Zeile tracken
    }   
}
 
arrangeMCs ("tf_mc", 9, _root, 300, 15, 15);//Beispielsaufruf 
 

Voraussetzung ist, dass du alle MCs vorher durchnummeriert hast (zero based) und alle auf der gleichen Timeline liegen. Sie können ganz unterschiedlich groß sein, Höhe und Breite werden ausgelesen.

Du musst nur die Funktion aufrufen und folgendes übergeben:
baseName = Name vor der Nummer
numberOfMCs = Zahl der MCs (da kann auch einfach eine riesige Zahl stehen)
scope = Referenz zur Timeline, in der die MCs liegen
areaWidth = Breite des Feldes, in dem die MCs angeordnet werden sollen
margin = Abstand zwischen MCs
overlap = maximale Abweichung von der Position; auf Grund dieses Wertes wird eine zufällige Verschiebung durchgeführt. Wenn er größer als margin ist, können sich die MCs auch überlappen. Einfach mal experimentieren

Ich kann dir auch ein Beispiels-fla mailen, wenn's nicht klappt!

Happy Weekend, nroy

noch was: mit negativem Wert für margin überlappen die Dinger natürlich immer, damit kann man das ganze also zusammenstauchen!

[cip22]

Danke für die Antworten!

ich werd's gleich mal mit der samstag-morgen-lösung von nroy versuchen... nein, ich progammiere (leider) nicht für eine kinoleinwand, es handelt sich meist um Einzeiler in 10 pt., paßt also noch ganz gut auf einen mittelgroßen Schirm. URL des fertigen Projekts wird dann in diesem Tread gepostet!

thx & greez
cip

[cip22]

nroy,

danke nochmal für dein script, aber das war's leider nicht...

Um es kurz zu machen: Ich brauche mehr *Zufall*! - also: über den screen verteilte MCs, die aber sozusagen 'voneinander wissen' und sich aus dem Weg gehen, wenn sie sich zu nahe sind.

Bin gerade dabei, selber was zu stricken, um der von mir bemängelten 'dämlichen' Lösung (jeder checkt kollision mit jedem) aus dem Weg zu gehen.

Dazu gibt es ein Raster, und jedem Rechteck im Raster ist ein Objekt beigegeben, an dem sich die MCs anmelden, wenn sie in das Rechteck kommen, und sich abmelden, wenn sie es wieder verlassen.

So hat jeder MC, wenn man die benachbarten Rasterfelder einschließt, maximal neun 'Nachbarfelder' und checkt nur Kollisionen oder zu große Nähe mit den MCs, die sich bei den jeweiligen Rasterfeldern registriert haben. Spart einen Haufen Performance.

....

Hm, ich erinnere mich dunkel, daß auf der Sun-Seite in den Anfangszeiten von Java mal ein Applet gepostet war, das ziemlich genau das machte, was ich hier will: ein lockerer Schwarm von Begriffen (Textfelder), bei dem die Members einen mittleren Abstand voneinander einhielten, der sich aber als Schwarm bewegte, wenn man einen von ihnen zog... Kennt das jemand noch (oder was ähnliches)?

Grüße und TIA
cip

verstehe, hab nicht geschnallt, dass die Dinger in Bewegung bleiben sollen.

Da hilft dir mein Script nicht viel. Hmm, all zu schwer ist das nicht, aber da fehlt mir jetzt die Zeit, muss morgen früh raus

Spontane Thesen:
1. Kollisionscheck halte ich auch für zu rechenintensiv, vor allem, da Text sowieso immer langsam gerendert wird
2. Eine Klasse erstellen, die so eine Art gravity-Loop durchführt (um die optimale Position kreist) und dabei von den 8 direkt benachbarten Objekten bei geringem Abstand "Wind" aus der jeweiligen Richtung bekommt => je näher die Objekte, desto stärker stoßen sie sich ab
3. Damit nicht permanent _width und _height ausgelesen werden müssen sollten diese Werte in der Klasse gespeichert werden (das kann echt Performance bringen)
4. Die Mausbewegung verschiebt die "Optimalposition", und zwar umso schneller, je näher ein Objekt der Maus ist. Dann müssten alle mit Verzögerung hinterherkommen

Ob dir das jetzt hilft... Ist mir nur so durch den Kopf gegangen

[cip22]

Naja, ich habe jetzt die pragmatische Lösung gewählt. Jeder MC guckt, in welchem Rasterfeld er ist und schiebt nur diejenigen etwas zur Seite, die im selben oder den (bis zu) acht benachbarten Feldern liegen.
Ich suche weiter nach dem 'Java'-Algo, aber im Moment kann ich nix komplizierteres machen, weil noch viel anders zu tun ist.

Danke jedenfalls fürs Mitdenken!

Gruß
cip