TileGrid

E

Eichelhäer

Bekanntes Mitglied
Hallo,

ich möchte ein reguläres 180x180 tilegrid in felder unterteilen, die 9x9 tiles groß sind. Das wären bei dem Beispiel 400 solcher 9x9 Felder.

Das habe ich bisher:

Java: 
for (int y = 0; y < worldSize.y; y++) {
            for (int x = 0; x < worldSize.x; x++) {
                for (int j = 0; j < 3; j++) {
                    for (int i = 0; i < 3; i++) {
                        for (int k = 0; k < 9; k++) {
                            resourceFields[(y / 20) * 20 + (x / 20)].field[k] = nodeGrid[((j % 3) + (i * 3)) * worldSize.x + ((i / 3) + (i * 3))];
                        }
                    }
                }
            }
        }

Wäre für Hilfe dankbar.
 
Robert Zenz

Robert Zenz

Top Contributor
Haeh? Also du hast ein Array:

Java: 
Field[][] world = new Field[180][180];

Und jetzt willst du das in 9x9 grosze Felder unterteilen? Also in etwa:

Java: 
for (int x = 0; x < WORLD_SIZE; x = x + 9) {
    for (int y = 0; y < WORLD_SIZE; y = y + 9) {
        // x..x+9
        // y..y+9
    }
}

Oder so?
 
KonradN

KonradN

Super-Moderator
Mitarbeiter
Erst einmal muss ich gestehen, dass ich nicht ganz verstehe, was Du da überhaupt im Detail vor hast und was Du mit dem Code versuchst.

Daher wäre es super, wenn Du etwas näher erläutern würdest, was Du genau machst und was für Datenstrukturen Du Dir so überlegt hast und so.

Generell sieht das aber erst einmal sehr dubios aus, denn Du hast da 5 verschachtelte Schleifen, aber unter dem Strich hast Du nur 3 davon genutzt für die Zuweisung, die Du ja in resourceFields[(y / 20) * 20 + (x / 20)].field[k] vornimmst. Daher ist da am Ende der letzte Wert gespeichert, also der mit i und j jeweils 2.

(Das ist so, weil auf der rechten Seite auch nur ein Wert aus einem Array gelesen wird. Da wird also nichts verändert!)

Generell solltest Du Dir überlegen, Code immer lesbar zu schreiben. Und zum einen der Ausdruck der Zuweisung selbst als auch die verschachtelten Schleifen sind extrem unverständlich.

Edit: Und die Lesbarkeit lässt sich natürlich verbessern durch:
  • kleine, übersichtliche Methoden mit sinnvollen Namen
  • sinnvolle Variablennamen (x, y, i, j, k sind keine gute Zusammenstellung!)
 
E

Eichelhäer

Bekanntes Mitglied
naja. ich versuche mich gerade an einem resourcenfindungs system für mein game. ich habe mir halt gedacht, dass ich das spielfeld in größere teilbereiche einteile, um nicht jede resource(also alle auf dem Spielfeld) zu prüfen ob diese die geeigneteste ist. Ich habe von greedy algorithmen gehört allerdings weiss ich nicht ,ob das für meine zwecke passt. In so einem tilebased rts game gibt es sehr viele szenarios, die man (nicht nur bei einem click auf eine beliebige Resource) berücksichtigen muss um ein einigermaßen passables game hinzubekommen. In einem Fall ist das z.B. so, dass ich einen wald habe, der komplett von obstacles umgeben ist. wenn man nun in diesen wald klickt, berechnet mein Algorithmus zuerst den kürzesten Weg zur Resource und prüft ob auf dem Weg eine Resource gleichen Typs ist. Ist das nicht der Fall nimmt sie die nächste im Wald und wiederholt das solange bis eine passende resource gefunden wurde. Wenn ich nun aber schon beim ersten Klick auf die resource keine Resource finde heißt das direkt, dass in diesem Wald keine weitere gefunden werden kann. Allerdings können ja außerhalb des Waldes noch weitere resourcen gefunden werden, die aber weiter von der Spielfigur weg sind als die erste. ........

Ich habe das rekursive programmiert und hatte, je mehr resourcen auf dem spielfeld waren immer größere verzögerungen, da die Suche zu lange gedauert hat.

Daher habe ich mir gedacht, das Spielfeld in größere Bereiche einzuteilen und dann pro Bereich zu fragen ob bei irgendeiner resource darin ein Weg gefunden werden kan. wenn nicht dann nimm das nächste feld in abhängigkeit zur Distanz der Spielfigur.

Ich weiss das klingt sehr verwirrend und ich glaube auch nicht, dass das die effiizienteste Methode ist, aber mir fiel nichts besseres ein.

Wenn du einen besseren Vorschlag dafür hast nur her damit.

Grüße Eichelhäer.
 
KonradN

KonradN

Super-Moderator
Mitarbeiter
Also für mich hört sich das etwas nach einem Problem der Datenhaltung an und damit dann automatisch verbunden: Die Algorithmen, um etwas mit den Daten zu machen.

Also wenn Du diverse Ressourcen hast, dann kannst Du diese doch einfach verwalten. Eine Ressource hat dann Eigenschaften wie einen Typ und die Koordinaten.

Davon hast Du dann eine gewisse Anzahl - wie hoch wird die sein? Vermutlich nicht zu hoch. Und wenn Du dann eine Ressource in der Nähe suchst, dann hast Du eine einzelne Schleife. Statt über alle Felder zu gehen hast Du dann nur genau die Ressourcen, also deutlich weniger durchzugehen. Und den Abstand zu bestimmen wird auch nicht besonders schwer.

Also wenn Du bei einem 100x100 Feld z.B. 10 Goldminen hast: Du gehst dann nicht 10.000 Felder durch sondern eben nur genau die 10 Goldminen. Und von denen kannst Du ggf. einfach einige ausfiltern weil zu weit weg oder so....

Und was ich aus Deinem Text heraus lese:
Eichelhäer hat gesagt.:
Ich habe das rekursive programmiert und hatte, je mehr resourcen auf dem spielfeld waren immer größere verzögerungen, da die Suche zu lange gedauert hat.
Zum Vergrößern anklicken....
Du hast bei einer erstellten Lösung ein Performance Problem. Aber dann fängst Du an zu optimieren ohne wirklich die Problematik erfasst zu haben. Das ist kein sehr guter Ansatz. Bei so einer Analyse sollte immer klar sein: Was für Daten liegen derzeit vor, was brauchst du? Was sind effektive Algorithmen? Man sollte ein Algorithmus also immer bewerten und so eine 5fach verschachtelte Schleife ist immer sehr hart (Da hast Du dann ein O(x*y*i*j*k) - was also sehr schlecht skalliert, wenn x,y,i und j zusammen hängen und dann größer werden. Wenn das jeweils durch n ersetzt würde, dann wären wir da bei O(n^4). Das sind so Dinge, die man meist versucht zu vermeiden. (Wobei das bei Dir ggf. einfacher ist, weil da einzelne Zähler nur zu 3 oder 9 werden, so dass nur x und y bleiben was dann O(n^2) wäre ...) Ich habe das mit der Komplexität jetzt nicht im Detail geprüft und analysiert - es ist nur etwas, das eben aufgefallen ist.

Bei Performance Problemen ist immer der Blick auf den Algorithmus wichtig. Bei einem schlechten Algorithmus das n klein zu halten mag zwar auch zu einer Lösung führen, aber das ist nur dann gut, wenn man sonst keine Lösung finden kann. (Aus meiner Sicht)

Der zweite Teil aber nur als allgemeiner Hinweis zur Vorgehensweise. So Optimierungen sollten halt immer mit klarer Analyse und einem kritischen Blick auf die Datenhaltung durchgeführt werden.
 
E

Eichelhäer

Bekanntes Mitglied
Laufzeitanalysen mit oberer und unterer Schranke sind gut. Das hatte ich im Studium auch und auf Performance zu verzichten um ein Problem zu lösen, damit lässt sich leben. Ich habe das Grundkonzept rekursiver Funktionen verstanden. Allerdings bleibt dennoch die Frage, ob meine Vorgehensweise die richtige Wahl für das Problem ist. Es ist klar, dass ich nur die Resourcen prüfe und nicht das ganze Feld. Mir ging es nur darum erstmal die Teilfelder zu erzeugen, um damit dann weiterzumachen. Die Schleifen oben sind nur ein Ansatz mehr nicht. Und ja Analyse von Algorithmen ist richtig und wichtig.
 
E

Eichelhäer

Bekanntes Mitglied
Die Sache ist nicht wirklich immer so einfach mit nur einer Schleife zu lösen, denn es gibt mehrere Varianten wo sich eine Resource in Relation zur spielfigur befindet, speziell auf die Obstacles bezogen oder ob bereits eine andere Spielfigur die Resource abbaut. Es sind halt nur die Fälle bei denen nicht sofort eine direkte Lösung gefunden wird. ansonsten läuft mein Algorithmus mit einer Laufzeit O(log(n)). Also nur dieser Resourcenfindealgorithmus.
 
E

Eichelhäer

Bekanntes Mitglied
Und manchmal speziell auf die Goldminen bezogen, es ist nicht immer die kürzeste Distanz der Spielfigur zur Resource die richtige, sondern es kann auch eine weiter entferntere die bessere Lösung sein, deshalb habe ich die Greedy Variante ins Spiel gebracht, die ja nicht immer die kürzeste, sondern gierig, wie der Name schon sagt, nach der besten Lösung sucht.
 
E

Eichelhäer

Bekanntes Mitglied
ok ich habs jetzt.

Java: 
this.resourceFields = new ResourceField[nodeGrid.length/9];

        for (int i = 0;i< resourceFields.length;i++) {
            resourceFields[i] = new ResourceField(9);
        }
        int n= 0;
        for(int k = 0;k<resourceFields.length;k++) {
            if(k>0 && k%60 == 0)n++;
            for(int j = 0;j<3;j++) {
                for(int i = 0;i<3;i++) {
                    resourceFields[k].field[j*3+i] = nodeGrid[(j+(n*2)) * worldSize.x + (i+k*3)];
                }
            }
        }
Allerdings ist die Bedingung unschön.
 

Aktuelle Jobs

Neue Themen


Oben