Simulation Planet WaTor

[MaXgOeKy]

Ich hatte bereits einen anderen Thread zu diesem Thema geöffnet, wo ich Fragen zum Zeichnen mit QT gestellt und geklärt habe.
http://entwickler-forum.de/showthrea...eichnen-mit-QT

Da das Thema des Threads nicht wirklich mehr zu den Fragen passt, öffne ich hier einen neuen.

Es geht um die Programmierung folgender Simulation:
http://de.wikipedia.org/wiki/Wator

Stand:
Die Initialisierung des Spielfelds funktioniert soweit, ist aber sehr langsam. Die Visualisierung des Spielfelds funktioniert.

Nun zu dem Problem:

Für die Initialisierung speichere ich alle möglichen Positionen für das Spielfeld in einem Vector:

    for (int z = 0; z < worldSize.second; z++) //Zeilen
    {
        for (int s = 0; s < worldSize.second; s++) //Spalten
        {
            positions.push_back(std::pair<int, int>(z, s));
        }//end for
        
    }//end for Zeilen

Im Anschluss vergebe ich für alle Positionen eine Spielfigur:

     while(positions.size() > 0)
    {
        //Generiere Zufallszahl für Position
        randomPos = rand() % positions.size();
        
        //Erstelle neues Individuum
        newIndividual = _createRandomIndividual();
        
        //Setze neues Individuum auf Spielfeld
        _setPlayingFieldValue(positions.at(randomPos).first,
                              positions.at(randomPos).second,
                              *newIndividual);
        
        //Entferne die gerade genutzten Positionen aus den Vectoren
        int counter = 0;
        for (std::vector<std::pair<int, int> >::iterator it = positions.begin();
             it != positions.end(); it++)
        {
            if (*it == positions.at(randomPos))
            {
                positions.erase(it);
                break;
            }//end if
            else
                counter ++;
            
        }//end for xPosition
        
    }//end while

Am Ende muss ich die gerade verwendete Position noch aus dem Vector löschen, damit diese nicht nochmal verwendet wird. Es gibt leider keine andere Möglichkeit aus einem Vector ein Element zu löschen, als über einen Iterator. Um an den Iterator zu gelangen muss ich jedes mal den Vector durchlaufen und den Wert des aktuellen Iterators mit dem Gesuchten zu vergleichen. Das geht bei einem Spielfeld mit 50x50 Felder noch recht Zügig wird aber bereits bei 150x150 extrem langsam.

Habt ihr eine andere Idee wie ich das umsetzen könnte? Hab ich vllt einen Fehler gemacht und es geht doch?!

Grüße
MaX

[Christian Marquardt]

http://www.sgi.com/tech/stl/find.html

für das suchen eines Iterators Des Weitern ist da Feld mit den Spielpostionen überflüssig.
Ein Feld kann 3 Zustände haben: Fisch, Hai, Leer. Du kannst also die Zeilen und Spalten des Felde in der gewünschten Größe durchlaufen und zu jedem Feld per Zufall eines der 3 Objekte generieren.

[MaXgOeKy]

So habe die std::find eingebaut.

        //Suche Iterator zum Wert
        std::vector<std::pair<int, int> >::iterator pIt = std::find(positions.begin(),
                                                                    positions.end(),
                                                                    positions.at(randomPos));
        
        //Entferne Element aus dem Vector
        positions.erase(pIt);

Ist zwar etwas schneller, jedoch nicht ausreichend..... 300x300 12 sec...

Gibt es noch eine performantere Möglichkeit?

Ein Feld kann 3 Zustände haben: Fisch, Hai, Leer. Du kannst also die Zeilen und Spalten des Felde in der gewünschten Größe durchlaufen und zu jedem Feld per Zufall eines der 3 Objekte generieren.

Habe ich auch gedacht. Es ist mir dann aber aufgefallen, dass es nicht ganz so einfach ist.

Damit die Simulation funktionieren kann müssen mehr Fische auf dem Spielfeld sein, als Haie. Sagen wir also: 60 % Fische / 25 % Haie / 15% leer.
Um also eine gerechte Verteilung zu gewährleisten ist entweder ein ausgeklügelter Initialisierungsalgorythmus oder eine zufällige Verteilung notwendig.

Ich habe mich für die zufällige Verteilung entschieden. Wenn man das Spielfeld sequentiell durchiteriert, dann kommt sowas raus:
Screen Shot 2013-01-01 at 14.08.18.jpg

Grüße

[Christian Marquardt]

Ich kann das nur wiederholen: Du legst eine Matrix von Zellenobjekten an und füllst diese mit den gewünschten Elementen (Hai, Fisch, Leer). Diese Matrix wird dann bei der Darstellung durchlaufen (Feld in welcher Farbe), bei der Simulation geändert (Obejkte bewegen sich). Dann brauch nichts kopiert gelöacht o.a. werden

[MaXgOeKy]

Ganz ehrlich? Ich verstehe Dich nicht...

.... Du legst eine Matrix von Zellenobjekten an...

--> Mache ich...

.... und füllst diese mit den gewünschten Elementen (Hai, Fisch, Leer)....

--> Hier ist das Problem...die Matrix muss initialisiert werden und das so, dass alle Objekte auf dem ganzen Spielfeld verteilt sind...

Diese Matrix wird dann bei der Darstellung durchlaufen (Feld in welcher Farbe), bei der Simulation geändert (Obejkte bewegen sich). Dann brauch nichts kopiert gelöacht o.a. werden

--> hast du Dir den Quellcode oben einmal angeschaut?! Hier geht es nur um die Initialisierung des Spielfelds und nicht um die Simulation. Ich lösche auch nix vom Spielfeld?!

[Christian Marquardt]

Ja, ich habe mir den Quellcode angeschaut. Du kannst jede Zelle per Zufall befüllen. Du kannst jede Zelle per gaußsche Verteilung füllen. Also alle 7 Zellen mit einem möglichen Versatz von +-6. Und das je nach gewünschter Prozentzahl. Ich wüsste nicht, wo da eine 2. Matrix beötigt wird, wo man dann einzelen Positionen löschen muss. "Entferne die gerade genutzten Positionen aus den Vectoren". Das ist es doch was nach deinen Aussagen lange dauert. "damit diese nicht nochmal verwendet wird.". Es ist also möglich, eine Verteilung zu erreichen OHNE eine Matrix mit den möglichen Positionen zu führen

Weiterhin ist es möglich eine Liste der schon vergebenen Positionen zu führen und bei der Vergabe nachzuschauen, ob die neue ermittelte Postion schon mal benutzt wurde. Dann wäre auch nichts zu löschen. Wenn man solche Listen als map http://www.sgi.com/tech/stl/Map.html anlegt, entfällt die Suche nach einem Wert. Die Kombiantion aus Reihe/Spalte ist einmalig und kann als Hash genutzt werden

Wenn also auf einem Spielfeld mit 100 Feldern 20% Fische da sein sollen, bedeutet das also, das auf jedem 5. Feld ein Fisch sitzt. Damit das nun nicht gleichförmig wird, wird also nicht stur an jeder 5. Stelle ein Fisch gesetzt, sondern an jeder 5. Stelle mit einem zufälligem Versatz von bsp. +-7. Das kann alles in einer erstellten Matirx aus Zellen erfolgen ohne irgendeine Liste zusätzlich zu führen

[MaXgOeKy]

Hi.

Ich habe es leider noch nicht geschafft weiter an meinem Projekt zu arbeiten. Bist du mittlerweile schon fertig?

Grüße

[Christian Marquardt]

ja, da aber hier kein Interesse bestand auch ad Akta gelegt

[MaXgOeKy]

Hallo Programmierer,

ich habe wieder mal ein wenig Zeit mich meinem Projekt zu wenden.

Und zwar habe ich immer noch ein Performance-Problem!

In der folgenden Methode wird meine Spielwelt initialisiert. Das funktioniert bei einem Spielfeld von 100 x 100 einwandfrei. Die einzelnen Lebewesen sind schön ungleichmäßig über die ganze Karte verteilt. Sobalt es an 300 x 300 geht dauert die Initialisierung bereits eine Minute. Bei 600 x 600 habe ich nach 5 Minuten abgebochen...

Was brauche ich? Ich brauche eine Mölichkeit, wie ich einen Container der STL wahlfrei Initialisieren kann, also nicht von 0 bis n sonder ich möchte zufällige Positionen im Vektor ansteuern bis alle Felder initialisiert worden. Ich habe da schon ein wenig bei der STL (std::generade) geschaut aber keine wirklich gute Variante gefunden.

Nun hoffe ich, dass Euch eine Möglichkeit einfällt.

void TWorldWator::_initializeWorld()
{
	//Variablen
	TIndividual     *newIndividual = 0; //Fuer das Erstellen eines neuen Lebewesens
    std::vector<std::pair<int, int> > positions;
    TWorldSize       worldSize;
    long             randomPos = 0;
    
    //Hole Groesze der Spielwelt
	worldSize = getWorldSize();
    
    //Initialisiere Zufallszahlengenerator
    srand(time(NULL));
    
    //Initialisiere Vectoren
    for (int z = 0; z < worldSize.second; z++) //Zeilen
    {
        for (int s = 0; s < worldSize.second; s++) //Spalten
        {
            positions.push_back(std::pair<int, int>(z, s));
        }//end for
        
    }//end for Zeilen
    
    //Wiederhole bis alle Positionen vergeben
    while(positions.size() > 0)
    {
        //Generiere Zufallszahl für Position
        randomPos = rand() % positions.size();
        
        //Erstelle neues Individuum
        newIndividual = _createRandomIndividual();
        
        //Setze neues Individuum auf Spielfeld
        _setPlayingFieldValue(positions.at(randomPos).first,
                              positions.at(randomPos).second,
                              *newIndividual);
        
        //Entferne die gerade genutzten Positionen aus den Vectoren
        //Suche Iterator zum Wert
        std::vector<std::pair<int, int> >::iterator pIt = std::find(positions.begin(),
                                                                    positions.end(),
                                                                    positions.at(randomPos));
        
        //Entferne Element aus dem Vector
        positions.erase(pIt);
        
    }//end while

}//end initilizeWorld

Das eigentliche und langse Problem im Code ist dieses hier:

//Entferne die gerade genutzten Positionen aus den Vectoren
        //Suche Iterator zum Wert
        std::vector<std::pair<int, int> >::iterator pIt = std::find(positions.begin(),
                                                                    positions.end(),
                                                                    positions.at(randomPos));
        
        //Entferne Element aus dem Vector
        positions.erase(pIt);

Grüße
MaX

[Christian Marquardt]

Wo ist der Unterschied zur Ausgangsfrage?

Wozu diese Listen?

Erstelle ein 2-dim. Array.
Belege dies mit Wasser o.a. vor
Zum setzen von x Kreaturen

Schleife die läuft bis x==0
x=RandomX Position
y=RandomY Position
Ist Position noch nicht besetzt
{
setze Kreatur
x--
}
Schleifenende

[MaXgOeKy]

Moin,

nen Kollege hat mir nen guten Tipp gegeben:
Hier ist die Lösung:

	//Variablen
	TIndividual     *newIndividual = 0; //Fuer das Erstellen eines neuen Lebewesens
    std::vector<std::pair<int, int> > positions;
    TWorldSize       worldSize;

    
    //Hole groesze der Spielwelt
    worldSize = getWorldSize();
    
    //Initialisiere Vectoren
    for (int z = 0; z < worldSize.second; z++) //Zeilen
    {
        for (int s = 0; s < worldSize.second; s++) //Spalten
        {
            positions.push_back(std::pair<int, int>(z, s));
        }//end for
        
    }//end for Zeilen
    
    //Bringe den Inhalt des Vectors positions durcheinander
    std::random_shuffle(positions.begin(), positions.end());
    
    //Wiederhole bis alle Positionen vergeben
    for (std::vector<std::pair<int, int> >::iterator it = positions.begin();
         it != positions.end();
         it++)
    {
        newIndividual= _createRandomIndividual();
        _setPlayingFieldValue(it->first, it->second, *newIndividual);
    }//end for

Der ganze Algorythmus ist sehr schnell. Eine Erstellung einer Größe von 600*600 ist unter einer Sekunde fertig, was vorher 7 Minuten gedauert hat. 1000 * 1000 ist ebenfalls unter einer Sekunde fertig!

Meld mich bei weiteren Fortschritten oder Fragen zu meinem Projekt wieder.

Grüße
MaX

[Christian Marquardt]

Schön, dass es schnell geht, aber die Vektoren sind immer noch überflüssig....