Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Datenstruktur für Spielfeld (Brettspiel)

  • 1
  • 2

Werbeanzeige

Sacaldur

Community-Fossil

  • »Sacaldur« ist der Autor dieses Themas

Beiträge: 2 301

Wohnort: Berlin

Beruf: FIAE

  • Private Nachricht senden

1

15.06.2012, 15:17

Datenstruktur für Spielfeld (Brettspiel)

ich habe vor kurzem damit angefangen, ein Brettspiel, welches ich auf einem Mini Game Jam in Berlin entwickelt habe, als Computerspiel umzusetzen
zunächst habe ich damit begonnen, die benötigten Klassen zur Speicherung des Spielzustands zu implementieren
dabei bin ich mir allerdings nicht ganz sicher, welches die geeignetste Lösung ist

zum Spiel selbst:
das Spielfeld besteht aus vielen, (derzeit nur) in einem Raster angeordneten Feldern
nicht an jeder möglichen Stelle befindet sich ein Feld
die Felder, sofern sie direkt benachbart sind, können eine Verbindung zueinander haben (senkrecht oder waagerecht)
auf den Feldern befinden sich ggf. die Spieler Gegenstände und die "Werfer"
die Spieler werden in 1 Richtung über mehrere Felder hinweg geworfen (solange diese miteinander verbunden sind)
die Werfer dürfen sich nicht zurück bewegen (außer, wenn sie in eine Sackgasse bewegt wurden)

das Problem:
wie speichere ich (zur Laufzeit der Anwendung) am Besten die Verbindungen zwischen den Feldern?

mögliche Lösungen:
  • für jedes (bzw. in jedem) Feld wird gespeichert, welches Feld sich rechts, links, über und unter diesem befindet
    • enorm redundante Speicherung von Informationen -> bei Fehlern Inkonsistenz
    • etwas umständliche Initialisierung
    • einfache Umsetzung der letzten beiden genannten Spieleigenschaften
    • grafischen Ausgabe bedingt gut umsetzbar
  • es wird in einer eigenen Klasse die Beziehung gespeichert, indem diese die entsprechenden beiden Felder beinhaltet, vergleichbar mit der Umsetzung von m-n-Beziehungen in relationalen Datenbanken
    • m. E. logisch
    • rechenintensiver (bei der Abfrage einer bestimmten Verbindung muss die gesamte Liste an Verbindungen durchgegangen werden)
    • grafischen Ausgabe und genannte Eigenschaften bedingt gut umsetzbar
  • in einer Liste wird gespeichert, ob (Wahrheitswert) eine Verbindung vorhanden ist
    • grafischen Ausgabe einfach umsetzbar
    • genannte Eigenschaften gut genug umsetzbar
    • Datenstruktur eher weniger intuitiv

gibt es neben den Lösungen, auf die ich bisher gekommen bin, auch noch die eine oder andere andere Möglichkeit, die besser geeignet sein könnte?

ich realisiere das Spiel mit C# (und XNA) und habe für die Speicherung der Felder ein 2-dimensionales-Array verwendet
Spieleentwickler in Berlin? (Thema in diesem Forum)
---

Zitat von »Jonathan_Klein«

Es ist ja keine Schande etwas falsch zu machen, als Programmierer tu ich das täglich, [...].

BurningWave

Alter Hase

Beiträge: 1 106

Wohnort: Filderstadt/Konstanz

Beruf: Student

  • Private Nachricht senden

2

15.06.2012, 15:46

Ich würde an deiner Stelle vielleicht eine map<int, vector<int>> verwenden. Die Map kann zu jedem Feld einen Vector enthalten, der eine Liste von Verbindungsdaten darstellt. So kannnst du relativ schnell die Verbindungen eines bestimmten Felds bekommen. Alle Verbindungen sollten eben (solange die Verbindung keine Richtung hat) für jeweils beide Felder, die verbunden sind, gespeichert werden. Das hätte den Vorteil, dass du nicht jedes Mal die komplette Liste durchgehen musst, wenn du eine bestimmte Verbindung suchst.

RmbRT

Treue Seele

Beiträge: 169

Wohnort: Darmstadt

Beruf: Student

  • Private Nachricht senden

3

15.06.2012, 16:11

Wenn ich das richtig verstanden habe, benutzt du immer noch ein 2D-Array für die Felder, und Felder, welche sich direkt berühren, haben eine Verbindung.
Als

C-/C++-Quelltext

 
1
2
3
4
5

Field * conn;
if((conn=Field[x][y].getLeftConnection()) != NULL)
{
//Mache etwas mit dem Nachbarfeld...
}

Wäre das nicht so leicht umzusetzen (oder nur über die Speicherung von 4 (oder mehr) pointern pro Feld).
Aber du könntest es ja so machen:

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

struct sField
{
    sField() : fieldData(NULL) {}   //Initialisieren auf "Leeres Feld"
    ~sField() {dealloc();}

    void alloc(){if(!fieldData) fieldData = new rawField;}
    void dealloc(){if(fieldData) delete fieldData; fieldData = NULL;}   //Verhinderung von Speicher-Leaks welche durch Pointer entstehen können

    rawField *fieldData; //rawField ist deine wahre Klasse, die das Feld wirklich managet. Wenn fieldData = 0, dann ist das Feld leer.
};
class FieldManager
{
public:
    rawField *getField(int x, int y)
    {
        if(x<0 || y<0 || x>=W || y>=H)
            return NULL;
        return Field[W][H].fieldData;
    }

    //Linker nachbar, returnt 0, falls keiner vorhanden.
    rawField *leftField(int x, int y)
    {
        return getField(x-1, y);
    }
private:
    sField Field[W][H];
};


und dann kannst du mittels getField(x-1,y) z.B. den linken Nachbarn ermitteln, falls keine Verbindung vorhanden ist, returnt es NULL.

Du musst halt nur gucken, dass du nicht versuchst, von einem Feld aus ein anderes anzusteuern,
sondern immer mittels der FieldManager- Klasse (hoffe, das lässt sich einrichten ;)).

Aber du wirst ja nicht die Spielelogik von einem Feld aus sondern vom Manager steuern - von daher sollte es ja kein Problem sein.

Hoffe, du weißt, was ich meine ;)
MfG, RmbRT
PS.: bin auf deinen entgültigen Lösungsweg gespannt ;)
"Dumm ist, wer dummes tut."

Sacaldur

Community-Fossil

  • »Sacaldur« ist der Autor dieses Themas

Beiträge: 2 301

Wohnort: Berlin

Beruf: FIAE

  • Private Nachricht senden

4

15.06.2012, 17:37

@BurningWave:
statt separat zu den Feldern, die bereits in einer Liste stehen, die Verbindungsinformationen zu speichern, wäre es doch sinnvoller, diese direkt in den Feldern zu speichern
das unterscheidet sich dann von meiner 1. Idee nur noch dahin gehend, dass verbundene Felder nicht mit "rechts", "links", "oben" oder "unten" angesprochen werden können
(das Durchgehen der Liste entspricht meiner 2. Idee)

Zitat von »RmbRT«

[...] und Felder, welche sich direkt berühren, haben eine Verbindung.

aber genau das ist ja nicht gegeben - sie _können_ eine Verbindung haben (andere nicht)
andernfalls wäre es ja sehr einfach, da man keine Zusatzinformation speichern müsste
Spieleentwickler in Berlin? (Thema in diesem Forum)
---

Zitat von »Jonathan_Klein«

Es ist ja keine Schande etwas falsch zu machen, als Programmierer tu ich das täglich, [...].

BurningWave

Alter Hase

Beiträge: 1 106

Wohnort: Filderstadt/Konstanz

Beruf: Student

  • Private Nachricht senden

5

15.06.2012, 17:48

Welche Felder dürfen nun verbunden sein? Benachbarte oder willkürlich verteilte Felder?

Was spricht denn gegen Listen? Wenn du die Informationen im Feld speichern willst, wirst du nicht umhin kommen, für alle 8 Nachbarn eine Variable zu verwenden, die angibt, ob die Verbindung zum Nachbarfeld beseteht oder nicht.

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

6

15.06.2012, 17:49

Ohne weitere Informationen darüber, was das Ding eigentlich genau tun soll, würd ich jetzt wohl mal Variante 1 wählen, also einfach das Spielfeld als Array speichern und jedem Feld 4 Pointer auf seine Nachbarn geben...
m4studios

Sacaldur

Community-Fossil

  • »Sacaldur« ist der Autor dieses Themas

Beiträge: 2 301

Wohnort: Berlin

Beruf: FIAE

  • Private Nachricht senden

7

15.06.2012, 18:24

@BurningWave:
festgelegte Felder

für mich klingt dein Vorschlag bisher so, als würde es eine Liste mit Feldern geben und zusätzlich eine Liste mit gleichen Indizes mit den Verbindunginformationen
sollte ich dich falsch verstanden haben, dann beschreibe bitte nochmal, in wie weit es sich davon unterscheidet

@dot:
ich weiß nicht, was du mit "das Ding" meinst oder welche Informationen fehlern

allerdings wollte ich eigentlich schon in meinem letzten Beitrag exemplarisch ein Bild einfügen (habe ich wohl vergessen x.x):

(Link)

zu sehen sind die Felder (Vierecke) und die Verbindungen (dicke Linien zwischen den Vierecken)
bei dem Feld handelte es sich um einen 1. Entwurf (bzw. Versuch)
die Ziffern markieren die Startfelder (nur als Randinformation)
Spieleentwickler in Berlin? (Thema in diesem Forum)
---

Zitat von »Jonathan_Klein«

Es ist ja keine Schande etwas falsch zu machen, als Programmierer tu ich das täglich, [...].

BurningWave

Alter Hase

Beiträge: 1 106

Wohnort: Filderstadt/Konstanz

Beruf: Student

  • Private Nachricht senden

8

15.06.2012, 18:31

Zitat von »Sacaldur«

@BurningWave:
für mich klingt dein Vorschlag bisher so, als würde es eine Liste mit Feldern geben und zusätzlich eine Liste mit gleichen Indizes mit den Verbindunginformationen


Ganz so habe ich es nicht gemeint. Du hast eine Liste (map) die alle Felder als Einträge enthält. Der Index des Felds ist der Schlüssel der Map. Der Wert ist eine Liste (Vector oder auch ein Array von 4 bools etc.), die die Verbindungen zu anderen Felder (deren Indices enthält). So brauchst du insgesamt nur eine Liste (die Map).

map<int /*Field ID*/, vector<int> /*Feld IDs der verlinkten Felder*/>

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

9

15.06.2012, 18:36

Ah ok. Gut, dann würde ich mir als erstes die Frage stellen, ob die zweidimensionale Anordnung der Felder für die Logik in irgendeiner Form wichtig ist, oder ob sich alles nur über die Nachbarschaftsbeziehungen abspielt.
m4studios

Chromanoid

Alter Hase

Beiträge: 1 410

  • Private Nachricht senden

10

15.06.2012, 18:51

Ich würde einfach sowas machen:

C-/C++-Quelltext

 
1
2
3
4
5
6
7

Spielfeld[] spielfelder;

class Spielfeld {
     vector<Spielfeld *> nachbarn;
     int x,y;//position    
     ///... Platzhalter für Spielobjekt auf dem Feld o.Ä.
}

man kann dann noch eine funktion implementieren, die ermittelt in welcher räumlichen relation ein feld zu einem anderen steht. so kann man dann ziemlich schnell alle möglichen wurfrouten etc. ermitteln. wenn dir das ermitteln zu viel zeit frisst, kannst du die ergebnisse cachen (halte ich allerdings für irrsinn)...
Besucht auch mal ZFX + Developia: Forum für Spieleentwicklung & TIGSource Forums: Independent Gaming Discussion

Dieser Beitrag wurde bereits 4 mal editiert, zuletzt von »Chromanoid« (15.06.2012, 19:17)

Werbeanzeige

  • 1
  • 2

Ähnliche Themen