Geeignete Datenstruktur für Spiel gesucht

  • Antworten:10
39
Gelöschter Account
  • Forum-Beiträge: 2.492

02.10.2015, 08:03:12 via Website

Hallo,

ich bin gerade dabei ein Spiel zu programmieren, meine verwendete Datenstruktur weist aber jetzt schon nicht akzeptable Performanceprobleme auf, und da ich bisher nicht selbst auf etwas Besseres gekommen bin wollte ich mal hier um Rat fragen.

Das Ziel
Mein Spiel ist ähnlich wie Tetris. Es fallen Blöcke (immer einzelne) von oben und diese können nach Links und Rechts bewegt werden. Wenn bestimmte Blöcke neben oder übereinander sind sollen diese entfernt werden.

Mein bisheriger Ansatz
Für die Blöcke habe ich eine eigene Klasse. Im Spiel führe ich eine ArrayList in der alle Blöcke gespeichert sind. Wenn ein neuer Block erscheint wird er an das Ende der Liste hinzugefügt. Außerdem habe ich ein zweidimensionales Array welches die gleichen Maße hat, wie das Spielfeld. Wenn sich die Blöcke bewegen wird in dem Array festgehalten, wo sich die Blöcke befinden. Damit schaffe ich es, dass sich Blöcke nicht "übereinander" her bewegen, sondern stoppen wenn einer im Weg ist.

Mein Problem bei diesem Ansatz
Wenn ich die Blöcke löschen will ist es noch recht einfach sie aus dem zweidimensionalen Array zu entfernen. Das Problem ist aber die Liste. Die Blöcke müssen daraus auch entfernt werden. Erstens weiß ich nicht an welcher Position in der Liste sich die Blöcke befinden (ich weiß nur, dass der aktuell fallende Block an der letzten Position ist) und zweitens würden sich diese Positionen einiger Blöcke ja ändern, wenn ich einen Block entferne (wodurch mein Ansatz ein zweites Array zu führen, in dem die Positionen in der Liste gespeichert sind zunichte gemacht wird, bzw. zu viel Arbeit aufweisen würde, da das Array dann ja ständig aktualisiert werden müsste).
Nochmal anders beschrieben: Wenn sich die Möglichkeit zum Löschen einiger Blöcke ergibt, dann habe ich nur

  • dieses zweidimensionale Array in dem beschrieben wird wo sich Blöcke befinden
  • aus dem Array habe ich die x und y Koordinaten welche Blöcke entfernt werden
  • die Position in der Liste des zuletzt bewegten Blockes (= die Letzte Position in der Liste)

Hat jemand eine Idee, wie ich das alles schöner und sauberer programmieren kann, mit einer geeigneten Datenstruktur für das Spiel? Wenn noch etwas besser erklärt werden muss gebt eben Bescheid, das ist nicht so einfach zu beschreiben.

Antworten
16
Gelöschter Account
  • Forum-Beiträge: 438

04.10.2015, 14:49:21 via Website

Was ist der konkrete Sinn der ArrayList? Nur um den fallenden Block zu identifizieren?
Über wie viele Blöcke reden wir und welche Dimensionen hat das 2d-Array.
Für mich ist es mit den bisherigen Infos schwer vorstellbar, wie es da zu Perf-problemen kommen soll...

Aktuelles Entwicklungsprojekt: (thinking) Sudoku Dojo Free (lightbulb)
Ich freue mich über Tester/innen.

Gelöschter Account

Antworten
39
Gelöschter Account
  • Forum-Beiträge: 2.492

04.10.2015, 21:35:20 via App

Die Arraylist ist dafür um alle Blöcke zu speichern und dann auch entfernen zu können. Das Feld ist 10*18. Die Performance Probleme treten auch nur beim löschen auf weil ich da so viel durch die Arrays iterieren muss und zusätzlich noch ne große Datenbank durchsuchen muss, sodass es da ab und zu geringe Wartezeiten gibt.
Ich habe zum testen jetzt mal ein 2 Dimensionales Array aus den Block Objekten erstellt damit kann ich all meine Probleme lösen. Aber wirklich elegant ist das glaub ich nicht oder:

Antworten
Rexxar 43
Rexxar
  • Forum-Beiträge: 2.563

05.10.2015, 08:06:45 via App

Kann man da nicht was mit MySQL machen?
Also direkt ne richtige Datenbank.
Aber keine Ahnung, ob das geht.
Ansonsten benutz doch ne Hashmap.
Blockid, Blockposition.
Und dann kannst du einfach gucken, wo welcher Block mit welcher Id is und nur den entfernen.

Liebe Grüße, Rexxar :)
Moto Z Play Stock
Nvidia Shield Tablet K1
http://www.androidpit.de/forum/634540/allgemeines-faq-fuer-neulinge

Gelöschter Account

Antworten
39
Gelöschter Account
  • Forum-Beiträge: 2.492

05.10.2015, 14:45:47 via Website

HashMap hab ich mich noch nicht mit beschäftigt, hört sich aber gut an. Schau ich mir mal an.

Antworten
16
Gelöschter Account
  • Forum-Beiträge: 438

05.10.2015, 16:05:02 via Website

Moment - große Datenbank durchsuchen????
Bei maximal 180 Blöcken sollten die im RAM befindlichen Speicherstrukturen kaum Relevanz haben.

Was machst Du denn auf der DB?

Aktuelles Entwicklungsprojekt: (thinking) Sudoku Dojo Free (lightbulb)
Ich freue mich über Tester/innen.

Antworten
39
Gelöschter Account
  • Forum-Beiträge: 2.492

05.10.2015, 16:10:49 via Website

Ich gehe durch die Blöcke aber in 2-3 for-Schleifen. Es könnte aber natürlich auch sein, dass der Zugriff auf die DB so lange dauert und das arbeiten mit den Blöcken gar nicht relevant ist. Muss ich wenn ich Zeit hab mal testen.

Suche nach einem passenden Datensatz.

Antworten
39
Gelöschter Account
  • Forum-Beiträge: 2.492

05.10.2015, 16:10:52 via Website

Ich gehe durch die Blöcke aber in 2-3 for-Schleifen. Es könnte aber natürlich auch sein, dass der Zugriff auf die DB so lange dauert und das arbeiten mit den Blöcken gar nicht relevant ist. Muss ich wenn ich Zeit hab mal testen.

Suche nach einem passenden Datensatz.

Antworten
16
Gelöschter Account
  • Forum-Beiträge: 438

06.10.2015, 13:44:27 via Website

Bis jetzt tauchen für mich mehr Fragen auf, als dass das wirkliche Problem klar wird.

"Die Arraylist ist dafür um alle Blöcke zu speichern und dann auch entfernen zu können."
Kapiere ich immer noch nicht - die Blöcke sind doch auch alle im 2d Array und können auch dort gelöscht werden (i.e. arr[x][y] = null;)

"Ich gehe durch die Blöcke aber in 2-3 for-Schleifen."
Wofür brauchst Du drei geschachtelte Iterationen über die Blöcke???
Nur zur Sicherheit: stelle ich mir das so richtig vor?

for (final Block aussen : blockListe) {
    // irgendwas
    for (final Block mittel : blockListe) {
    // irgendwas mit der Kombination aussen / mittel
        for (final Block innen : blockListe) {
            // irgendwas mit der Kombination aussen / mittel / innen
        }
    // vielleicht nochwas mit aussen / mittel
    }
    // vielleicht nochwas mit aussen
}

Und irgendwo passiert auch noch ein DB Zugriff (womöglich in einer der inneren Schleifen)?
Das wäre ziemlich suboptimal...

Aktuelles Entwicklungsprojekt: (thinking) Sudoku Dojo Free (lightbulb)
Ich freue mich über Tester/innen.

Antworten
39
Gelöschter Account
  • Forum-Beiträge: 2.492

06.10.2015, 16:33:55 via Website

Die Arraylist brauchte ich eigentlich nur zum Bewegen des letzten Blockes ist mir auch grad aufgefallen. Also die könnte ich eigentlich auslassen und nur den letzten Block zwischenspeichern.
EDIT: Mir ist gerade eingefallen ich nutze die Liste auch um die Blöcke zu zeichnen (auf dem Canvas). Also ich gehe die Liste durch und lasse jeden zeichnen.

Die drei Iterationen benötige ich um mehrere Kombinationen der vorhandenen Blöcke durchzugehen. ich muss alle Nachbarn und deren Nachbarn und nur teile der Nachbarn betrachten.

Ja dass das nicht optimal ist habe ich auch gedacht, der Zugriff ist aber in der zweiten Schleife.

— geändert am 06.10.2015, 19:04:00

Antworten
16
Gelöschter Account
  • Forum-Beiträge: 438

07.10.2015, 12:48:51 via Website

Wenn ich das richtig verstanden habe läuft das so:

  • es gibt einen "ausgezeichneten", einzelnen Block - nämlich derjenige, der momentan das Ende der Liste bildet, und den man eigentlich in einer Variable ("mCurrentlyFallingBlock") halten könnte
  • nur dieser Block sorgt für Änderungen der Konstellationen der Blöcke - immer wenn er sich bewegt, gibt es eine ggf. neue Konfiguration, die weitere Ereignisse (Löschen, ...) auslöst
  • relevant für die Ereignisse sind Nachbarn des "1. Grades" (also unmittelbar benachbarte Blöcke) und Nachbarn des 2. Grades - also die unmittelbaren Nachbarn der Nachbarn des 1. Grades
  • ich gehe davon aus, dass der Block in diskreten Schritten bewegt wird (also in einer bestimmten Zeiteinheit immer eine Blockhöhe nach unten fällt)
  • weiterhin gehe ich davon aus, dass man jedem Block seine x/y Position als Zustand mitgeben kann (somit hat man sowohl Zugriff von Position auf Block (über Array) und von Block auf Position)

Wenn das alles so richtig sein sollte würde ich von folgendem Pseudocode ausgehen:

if (platzFuerBlockZumFallenVorhanden) {
    verschiebeFallendenBlockNachUnten();
    for (final Block nachbarErstenGrades : getNachbarn( mFallenderBlock )) {
        if (istBesondereKonstellation(mFallenderBlock, nachbarErstenGrades) {
            behandleKonstellation(mFallenderBlock, nachbarErstenGrades);
            break;
        } else {
            for  (final Block nachbarZweitenGrades : getNachbarn( nachbarErstenGrades )) {
                if (nachbarZweitenGrades != mFallenderBlock && 
                    istBesondereKonstellation(mFallenderBlock, nachbarErstenGrades, nachbarZweitenGrades )) {
                    behandleKonstellation(mFallenderBlock, nachbarErstenGrades);
                    break;
                }
            }
        }
    }
} else {
    // keine Ahnung was passieren soll
}

getNachbarnkönnte auch als Methode der Blöcke realisiert werden, falls diese das Array kennen.

So sind zwar immer noch redundante Konstellationen drin, aber die Zahl irrelevanter Kombination wird schonmal verringert.

Aktuelles Entwicklungsprojekt: (thinking) Sudoku Dojo Free (lightbulb)
Ich freue mich über Tester/innen.

Antworten