(möglichst effiziente)Datenstruktur für Spielfeld

[Ap0kalyps3]

Guten Tag,

ich habe ein kleines Projekt in Angriff genommen und möchte gerne ein Spiel programmieren(in Java).

Das Spielfeld soll ~(40-50)x(40-50) groß sein und jedes feld soll in alle Richtungen, also waagerecht,senkrecht und diagonal,
mit anderen Felder verbunden sein können. Das immer jedes Feld diese Verbindungen voll ausnutzt ist aber kein muss, zB an rändern etc.

Mit dieser "Digitalisierung" wird dann auch intern gearbeitet, primär für eine K.I. die die günstigsten Züge berechnet etc.

Nun die Frage die mich seit ein paar Stunden beschäftigt: welche Datenstruktur wäre dafür am effizientesten?
Ein 2d array kommt für mich nicht in frage, hatte eine art List und eine Hashtable ins Auge gefasst. Oder gibt es noch andere Alternativen die ich gar nicht in betracht gezogen habe?

Wäre dankbar für feedback und/oder Inspiration

 

[Mika911]

Kannst du mir bitte begründen, warum du kein Array benutzen möchtest?

 

[michi.o]

Für die Felder könntest du einen Graphen implementieren. Man kann Graphen als Matrix oder Liste darstellen.
Auf folgender Seite ist ein Beispiel dafür: http://www.r-krell.de/if-java-g.htm

 

[Yuuri]

Was aber wieder ein Array ist... Im Prinzip ist alles ein Array. Aber was an Feld[x][y] nicht effizient ist, weiß ich nicht.

 

[Ap0kalyps3]

hi, also dieser einwand ist berechtigt. Die Spielfelder sollen "dynamisch" sein, also nicht einfach nur quadrate sondern auch mal in Form von Kreuzen, Sternen etc. .
Das ganze in einem Array abgespeichert und man hat bei einer suche, bei zB einem Kreuz, in einem Array 4 Bereiche wo nichts drin steht.
Das würde ich gerne vermeiden und meine Datenstruktur daran anpassen, so dass wirklich nur Felder die wirklich existieren berücksichtigt werden

 

[Mika911]

Dann bau dir doch deine eigene Datenstrucktur auf,
wie du sie benötigst und Schaufelst die wiederum in ein Array.
Bei deinem Anwendungsfall find ich führt kaum ein Weg am Array vorbei. =)

 

[DasBoeseLebt]

hi, also dieser einwand ist berechtigt. Die Spielfelder sollen "dynamisch" sein, also nicht einfach nur quadrate sondern auch mal in Form von Kreuzen, Sternen etc. .
Das ganze in einem Array abgespeichert und man hat bei einer suche, bei zB einem Kreuz, in einem Array 4 Bereiche wo nichts drin steht.
Das würde ich gerne vermeiden und meine Datenstruktur daran anpassen, so dass wirklich nur Felder die wirklich existieren berücksichtigt werden

Fülle doch dein Array mit Werten oder Objekten die den Zustand des Feldes wiederspiegeln.
,,Ist begehbar'', ,,ist eine Mauer'', ,,Spielfigur'', ,,"Gegner'' ,,Startpunkt'', ,,Ziel'', ... usw.

So hast du eigentlich keine leeren Felder im Array, sondern immer Zustände und je nach Zustand verhält sich das Feld anders.

 

[carom]

Bei einem 50x50 Spielfeld stellt sich die Frage der Effizienz doch eigentlich gar nicht, das könntest du noch deutlich größer machen und müsstest dir keine Sorgen machen. Nimm ein Array und verwende dein Gehirnschmalz für andere Dinge

edit: Es wäre noch interessant, was du mit effizient meinst. Speichertechnisch?

 

[Yuuri]

Die Spielfelder sollen "dynamisch" sein, also nicht einfach nur quadrate sondern auch mal in Form von Kreuzen, Sternen etc. .

Wo ist dann der Unterschied zu [x,y]? Wo willst du die dritte Dimension einführen? Die Dritte wäre in dem Falle z und ich glaube nicht, dass du Spielfelder mit mehreren Ebenen vor hast zu erstellen. Die Form wird ja nicht durch die Feldposition bestimmt.

 

[Jyskall]

Ein Array ist ja erstmal eine Liste von Daten die theoretisch eine beliebige Anzahl an Dimensionen annehmen kann.
Was du in einen Platz/Koordinate in diesem Array speicherst bleibt völlig dir überlassen.
(Beispielsweise ein Object vom Typ Spielfeld)

Am besten versteht man das wenn man sich anschaut wie ein Bild im Computer gespeichert wird:

Jede Koordinate ist ein Pixel, das wiederum aus 3 oder 4 Bytes besteht.
Jedes dieser Bytes gibt an welche Intensität ein bestimmter Farbkanal hat. (RGBA = Rot, grün, Blau, Alpha)

So kann man theoretisch in 32bit ~16,7 Millionen unterschiedliche Informationen/Farben speichern.


Mit deinem Spielfeld Object sieht das dann genau so aus. Nur das du z.B. einfach nur 1Byte (8bit) verwendest, das würde für 256 Spielfeldtypen reichen. (Dein Level Editor könnte dann ein simples Bildprogramm sein in dem du ein Graustufenbild mahlst.)

Und für Bildbearbeitung Analyse etc. gibt es viele tolle Bibliotheken die dir die Verarbeitung etc. erleichtern. Gleichzeitung hast du eine einfache Möglichkeit die Ergebnisse die dein Code liefert Bildlich darzustellen.

 

[Daaron]

Yuuri, ich glaub er meint, dass es eben z.B. A1 oder B12 nicht zwingend gibt. Im Array hättest du das Feld (grundlegend) trotzdem in der Iteration, aber es wäre eben ein nicht nutzbares Feld.

 

[Mika911]

Ich denke Yuuri hat das schon verstanden.
Nur ist der Performanceaufwand verschwindend gering, wenn dort diese "leere" Feld mit rein müsste.

 

[Yuuri]

@ Daaron: Wenn das Spielfeld x*y groß ist, hat man doch aber zwangsweise was auf B2, auch wenn es spieltechnisch nicht genutzt werden kann (Wasser, Wüste, Berge, ...). Einen Zustand hat das Feld also schon gegeben. Wenn man es als Stern aufbaut, hat das Spielfeld ja aber trotzdem x*y Dimensionen, nur dass davon vielleicht A1 als nicht begehbar deklariert wird, ergo bspw. der Fog of War ist o.ä. Deswegen ist das Feld ja trotz allem "vorhanden".

Als ineffizient würde ich es beschreiben, wenn er in Reihe A nur drei Felder speichert, in Reihe B fünf, in C sieben usw. So müsste man immer wieder mit Abfrageverschachtelungen rumhandtieren und entscheiden, wo Feld X nun hingehört (erstmal unabhängig der Position im Spielfeld selbst). Deshalb lieber einfach x*y reservieren und diese dann als nicht begehbar deklarieren, so spart er sich u.U. lästige Abfrage- und Schleifenkonstrukte.

 

[kuddlmuddl]

Genau was Yuuri sagt denke ich auch: Ne Art 2D-Liste wo einfach für alle Felder ihre reale Position und ihre Nachbarn abgelegt sind macht GARANTIERT mehr Arbeit in der Verwaltung als ein 2D-Array.

Das ist auch einer der Gründe, wieso selbst für Einfüge und Lösch-Operationen in C++ Vectoren oft die bessere Wahl sind als Listen, denn Umkopieren von linear geordnetem Speicher geht viel viel schneller als in einer verketteten Liste rumsuchen. Stichwort: Cache-Misses

Außerdem: Alle mir bekannten Strategie-Spiele machen es auch so. Man denke nur mal an Warcraft/Starcraft und die Minimap. Wenn man nen Map-Editor benutzt merkt mans besonders.

 

[Daaron]

Tja, wenns so einfach wäre. Klar, die ganzen RTS-Sparte nutzt quadratische Tiles, wobei ich mir bei CoH und Warhammer 40k Dawn of War grad nicht sicher bin.... und das uralte M.A.X. 2 hatte glaub ich auch keine quadratischen Tiles...
Aber in der rundenbasierten Strategie ist der Standard zum Beispiel das Hexgrid. Heroes of Might & Magic, Civilisation, Siedler von Cathan,... Da wird es schon wieder um einiges komplexer, einfach stur über ein Array zu gehen und Nachbarn simpel zu bestimmen, ob die X- und Y-Koordinate eben im Bereich von +/-1 liegt.

 

[Yuuri]

Ja klar, aber ich denke mal, dass dies eher bei großen oder komplexen Projekten (à la Civilization) zum Tragen kommt. Bei nem kleinen Spiel, wo man nur ein wenig lernen(?) und sich ein wenig verwirklichen will, schlägt man sich nicht anfänglich damit rum. Man könnte die Sache ja auch von Anfang an abstrahieren, um dann einfach den Karten-Layer auszutauschen und so einfach von quadratischen auf hexagonale Tiles umstellen kann. Dem ist ja keine Grenze gesetzt und dank Vererbung funktioniert dies ja auch wunderbarst.

Aber wieso Hexgrids jetzt so viel komplexer sein und nicht in ein 2D-Array passen sollen, versteh ich nicht ganz. Hab ich irgendwo nen Denkfehler? Im Prinzip ist es doch auch nur ein [x,y]-Array, mit Anzeige eines gewissen Versatzes des Tiles. Die Handhabung ist natürlich eine andere, aber das Vorhalten der Daten, würde ich jetzt nicht anders sehen. Kommt natürlich drauf an, ob es nicht vielleicht doch Geeigneteres gibt.

 

[Ap0kalyps3]

danke für die Kritik, eure Kommentare haben mich überzeugt doch ein 2d array zu nehmen. ist auch in der handhabung sehr viel umkomplizierter