Notes 5.5

Sie können diese Seite ausdrucken oder mit einem PDF-Drucker in ein PDF umwandeln, um Ihre eigenen Notizen hinzuzufügen.

Einführung

In dieser Vorlesung wiederholen wir Linked Lists anhand eines praktischen Beispiels: einem kleinen Retro-RPG-Spiel. Dabei implementieren wir eine generische verkettete Liste, die Entities (NPCs, Gegner, Items) verwaltet.

Repository: github.com/UBA-PSI/retrorpg

Der didaktische Bogen dieser Vorlesung:

Alles in einem Struct → unsauber, Trennung einführen
Entity eingebettet in Node → funktioniert, aber nicht generisch
void* für Generizität → erzwingt Pointer
Pointer auf Stack-Variable → kaputt
Also Heap
Doppelpointer für sichere Modifikation

Teil 1: Entities speichern – ganz naiv

Ausgangspunkt: Wir haben ein Spiel mit einer Map, der Spieler läuft rum. Jetzt wollen wir NPCs und Gegner hinzufügen.

Wir wollen NPCs und Gegner speichern, und zwar mehrere. Wie?

Erste Idee: Alles in ein Struct packen:

typedef struct Node {
    int x, y;
    char sprite[32];
    struct Node *next;
} Node;

Problem:

Was ist ein “Node”? Das vermischt zwei Dinge: Die Daten (x, y, sprite) und die Struktur (next-Pointer)
Was wenn wir später einen Entity-Baum wollen statt einer Liste? Dann hat Entity plötzlich left und right statt next?
Was wenn eine Entity in mehreren Strukturen gleichzeitig sein soll?

Lösung: Trennung von Daten und Datenstruktur

// Die fachlichen Daten
typedef struct {
    int x, y;
    char sprite[32];
} Entity;

// Die Listenstruktur
typedef struct Node {
    Entity data;
    struct Node *next;
} Node;

Entity weiß nichts von der Liste. Könnte genauso in einem Array, Baum, oder Hashtable leben.

Teil 2: Liste befüllen – by value

Node* add_entity(Node *list, Entity e) {
    Node *new_node = malloc(sizeof(Node));
    new_node->data = e;    // Struct-Zuweisung kopiert
    new_node->next = list;
    return new_node;
}

Entity create_entity(int x, int y, char *sprite) {
    Entity e;
    e.x = x;
    e.y = y;
    strcpy(e.sprite, sprite);
    return e;
}

// Nutzung:
Node *entities = NULL;
entities = add_entity(entities, create_entity(5, 3, "villager"));
entities = add_entity(entities, create_entity(7, 2, "slime"));

Das funktioniert. Entity wird by value übergeben, in Node wird eine Kopie gespeichert.

Zwischenstand: Wir haben eine saubere Trennung und eine funktionierende Liste. Fertig?

Teil 3: Warum doch Pointer? – Generizität

Was wenn wir später nicht nur Entities speichern wollen, sondern auch Items fürs Inventar? Und Befehle für eine Queue?

Mit dem jetzigen Ansatz:

typedef struct EntityNode {
    Entity data;
    struct EntityNode *next;
} EntityNode;

typedef struct ItemNode {
    Item data;
    struct ItemNode *next;
} ItemNode;

typedef struct CommandNode {
    Command data;
    struct CommandNode *next;
} CommandNode;

Und für jede: add_entity, add_item, add_command, delete_entity, delete_item, delete_command…

Fast identischer Code, dreimal.

Idee: Generische Liste, die alles speichern kann.

typedef struct Node {
    void *data;   // Zeigt auf... irgendwas
    struct Node *next;
} Node;

void* ist ein “generischer Pointer” – kann auf jeden Typ zeigen
Eine einzige add_to_list-Funktion für alles
Der Aufrufer weiß, was drin ist

Aber: void* ist ein Pointer. Wir können keine Entity mehr direkt einbetten – wir müssen einen Pointer speichern.

Das heißt: Die Entity muss irgendwo leben, und wir speichern nur die Adresse.

Teil 4: Wo lebt die Entity? – Das Stack-Problem

Wir lesen Entities aus einer Datei:

5 3 villager
7 2 slime
8 8 chest

Erster Versuch:

Node *entities = NULL;

FILE *f = fopen("entities.txt", "r");
int x, y;
char sprite[32];

while (fscanf(f, "%d %d %s", &x, &y, sprite) == 3) {
    Entity e = create_entity(x, y, sprite);  // e auf dem Stack
    add_to_list(&entities, &e);               // Adresse von e speichern
}

Was passiert hier?

e liegt auf dem Stack, immer an derselben Adresse
Bei jedem Schleifendurchlauf wird e überschrieben
Alle Nodes zeigen auf dieselbe Adresse
Nach der Schleife zeigen alle auf den letzten Wert (oder Garbage)

Demonstration:

Schleife Durchlauf 1:
  Stack: [e: x=5, y=3, sprite="villager"]  Adresse: 0x1000
  Node 1 -> data zeigt auf 0x1000

Schleife Durchlauf 2:
  Stack: [e: x=7, y=2, sprite="slime"]     Adresse: 0x1000 (DIESELBE!)
  Node 2 -> data zeigt auf 0x1000
  Node 1 -> data zeigt auf 0x1000          (zeigt jetzt auf "slime"!)

Schleife Durchlauf 3:
  Stack: [e: x=8, y=8, sprite="chest"]     Adresse: 0x1000 (DIESELBE!)
  Alle Nodes zeigen auf 0x1000

Nach der Schleife:
  Alle drei Nodes zeigen auf dieselbe Adresse
  Dort steht: "chest" (oder Garbage nach Funktionsende!)

Das Ergebnis:

// Erwartung:          Realität:
// villager            chest
// slime               chest
// chest               chest

Oder noch schlimmer: Nach Verlassen der Funktion ist der Stack-Speicher ungültig → Crash oder Garbage!

Teil 5: Die Lösung – Heap

Jede Entity braucht ihren eigenen, permanenten Speicher:

Entity* create_entity(int x, int y, char *sprite) {
    Entity *e = malloc(sizeof(Entity));  // Auf dem Heap
    e->x = x;
    e->y = y;
    strcpy(e->sprite, sprite);
    return e;
}

Jetzt:

while (fscanf(f, "%d %d %s", &x, &y, sprite) == 3) {
    Entity *e = create_entity(x, y, sprite);  // Jedes Mal NEUE Adresse
    add_to_list(&entities, e);
}

Jede Entity hat ihre eigene Adresse. Problem gelöst.

Zusammenfassung:

Warum Heap?

1. void* für Generizität
      ↓
2. void* speichert nur Adressen, keine Werte
      ↓
3. Die Daten müssen irgendwo dauerhaft leben
      ↓
4. Stack-Variablen in Schleifen werden überschrieben
      ↓
5. Also: malloc() für permanenten Heap-Speicher

Teil 6: add_to_list – Return vs. Doppelpointer

Return-Variante

Node* add_to_list(Node *list, void *data) {
    Node *new_node = malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = list;
    return new_node;
}

// Korrekter Aufruf:
entities = add_to_list(entities, e);

Was passiert wenn jemand schreibt:

add_to_list(entities, e);  // Return-Wert ignoriert

Problem:

entities zeigt immer noch auf den alten Kopf
Der neue Node ist unerreichbar → Memory Leak
Schlimm, aber Programm läuft weiter (erstmal)

Teil 7: delete – hier wird es fatal

Wie löschen wir eine Entity aus der Liste?

Erste Idee:

Node* delete_from_list(Node *list, void *target) {
    Node *prev = NULL;
    Node *curr = list;

    while (curr != NULL) {
        if (curr->data == target) {
            if (prev == NULL) {
                // Kopf löschen
                Node *new_head = curr->next;
                free(curr->data);
                free(curr);
                return new_head;
            } else {
                prev->next = curr->next;
                free(curr->data);
                free(curr);
                return list;
            }
        }
        prev = curr;
        curr = curr->next;
    }
    return list;
}

// Aufruf:
entities = delete_from_list(entities, some_enemy);

Wieder: Was wenn jemand den Return-Wert vergisst?

delete_from_list(entities, some_enemy);  // some_enemy ist zufällig der Kopf

Problem:

Kopf wird gelöscht und free’d
entities zeigt immer noch auf den alten (jetzt freigegebenen) Speicher
Nächster Zugriff auf entities → Undefined Behavior, Crash, Garbage

Bei add war vergessener Return-Wert nur ein Memory Leak. Bei delete ist es ein Use-After-Free!

Teil 8: Die Lösung – Doppelpointer

Wie können wir erzwingen, dass die Liste sich ändert?

Analogie:

void set_to_five(int x) {
    x = 5;  // Ändert nur lokale Kopie
}

int a = 3;
set_to_five(a);
// a ist immer noch 3

Das kennen wir schon. Lösung:

void set_to_five(int *x) {
    *x = 5;
}

int a = 3;
set_to_five(&a);
// a ist jetzt 5

Zurück zur Liste:

list ist ein Node*. Wenn wir list selbst ändern wollen (nicht worauf er zeigt, sondern den Pointer selbst), brauchen wir einen Pointer auf den Pointer:

void add_to_list(Node **list, void *data) {
    Node *new_node = malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = *list;
    *list = new_node;
}

// Aufruf:
add_to_list(&entities, e);

Kein Return-Wert. entities wird direkt modifiziert. Kann nicht vergessen werden!

delete:

void delete_from_list(Node **list, void *target) {
    Node *prev = NULL;
    Node *curr = *list;

    while (curr != NULL) {
        if (curr->data == target) {
            if (prev == NULL) {
                *list = curr->next;  // Ändert entities in main!
            } else {
                prev->next = curr->next;
            }
            free(curr->data);
            free(curr);
            return;
        }
        prev = curr;
        curr = curr->next;
    }
}

// Aufruf:
delete_from_list(&entities, some_enemy);

Das & beim Aufruf signalisiert: “Diese Variable könnte sich ändern.”

Bonus: Vergisst man das &, gibt’s einen Compiler-Fehler! Viel sicherer.

Zusammenfassung der Erkenntnisse

Naive Idee	Problem	Lösung
Daten + Struktur vermischt	Unflexibel	Trennung Entity / Node
Entity eingebettet in Node	Nicht generisch	`void*`
Entity auf Stack	Wird überschrieben	Heap mit `malloc`
Return-Wert für neuen Head	Kann vergessen werden	Doppelpointer

Umsetzung im Spiel

Die Dateien im Repository:

Datei	Was implementiert wird
`simple/live/list.c`	`add_to_list()`, `delete_from_list()`, `free_list()`
`simple/live/entity.c`	`create_entity()`, `free_entity()`

add_to_list

void add_to_list(Node **list, void *data)
{
    // 1. Neuen Node auf dem Heap erstellen
    Node *new_node = malloc(sizeof(Node));

    // 2. Daten-Pointer speichern
    new_node->data = data;

    // 3. Neuer Node zeigt auf bisherigen Head
    new_node->next = *list;

    // 4. Head-Pointer aktualisieren (Doppelpointer!)
    *list = new_node;
}

*list ist der aktuelle Head (oder NULL bei leerer Liste)
*list = new_node überschreibt den Head-Pointer in der aufrufenden Funktion
Ohne Doppelpointer würden wir nur eine lokale Kopie ändern

free_list

void free_list(Node **list)
{
    Node *current = *list;

    while (current != NULL)
    {
        Node *next = current->next;  // ERST nächsten merken!
        free(current);               // DANN aktuellen freigeben
        current = next;              // Weitergehen
    }

    *list = NULL;  // Liste ist jetzt leer
}

Wichtig: Warum speichern wir next bevor wir free aufrufen? Nach free(current) ist current->next ungültiger Speicher! Zugriff wäre Undefined Behavior.

create_entity

Die Entity-Struktur:

typedef enum { ENTITY_NPC, ENTITY_ENEMY, ENTITY_ITEM } EntityType;

typedef struct {
    int x, y;           // Position auf der Map
    EntityType type;    // NPC, ENEMY oder ITEM
    char sprite[32];    // Name des Sprites
    int frame;          // Animation-Frame
    int move_timer;     // Fuer Gegner-Bewegung
} Entity;

Die Implementierung:

Entity* create_entity(int x, int y, EntityType type, const char *sprite)
{
    // 1. Speicher auf dem Heap reservieren
    Entity *e = malloc(sizeof(Entity));

    if (e == NULL)
    {
        return NULL;  // malloc fehlgeschlagen (kein Speicher)
    }

    // 2. Felder initialisieren
    e->x = x;
    e->y = y;
    e->type = type;
    strcpy(e->sprite, sprite);
    e->frame = 0;       // Animation startet bei Frame 0
    e->move_timer = 0;  // Bewegungs-Timer startet bei 0

    return e;
}

malloc(sizeof(Entity)) reserviert genau so viel Speicher wie eine Entity braucht
Der Speicher bleibt bestehen bis wir free() aufrufen
Jeder Aufruf von create_entity gibt eine neue, einzigartige Adresse zurück

free_entity

void free_entity(void *entity)
{
    free(entity);
}

Warum void* statt Entity*? Die generische Liste weiß nicht, welchen Typ die Daten haben. free_entity wird als Funktionspointer übergeben und muss daher void* akzeptieren.

delete_from_list

void delete_from_list(Node **list, void *target)
{
    Node *prev = NULL;
    Node *curr = *list;

    while (curr != NULL)
    {
        if (curr->data == target)
        {
            if (prev == NULL)
                *list = curr->next;
            else
                prev->next = curr->next;
            free(curr);
            return;
        }
        prev = curr;
        curr = curr->next;
    }
}

Hinweis: Diese Funktion gibt nur den Node frei, nicht die Daten! Die Daten werden separat mit free_entity freigegeben (in game_cleanup).

Bonus: Der Entity-Loader (zum Nachschlagen)

Der Entity-Loader (simple/shared/entity_loader.c) ist bereits fertig implementiert. Hier kommt alles zusammen: Datei lesen, parsen, Entities erstellen, zur Liste hinzufügen.

Dateiformat (data/entities.txt):

# Kommentar
NPC 10 5 villager
ENEMY 15 8 slime
ITEM 12 7 sword

Hilfsfunktion für EntityType:

static EntityType parse_type(const char *str)
{
    if (strcmp(str, "NPC") == 0) return ENTITY_NPC;
    if (strcmp(str, "ENEMY") == 0) return ENTITY_ENEMY;
    if (strcmp(str, "ITEM") == 0) return ENTITY_ITEM;
    return ENTITY_NPC;  // Fallback
}

static bedeutet: Nur in dieser Datei sichtbar
strcmp vergleicht Strings, gibt 0 bei Gleichheit zurück

Die load_entities Funktion:

bool load_entities(Node **entities, const char *filename)
{
    FILE *file = fopen(filename, "r");
    if (file == NULL)
    {
        printf("Datei nicht gefunden: %s\n", filename);
        return false;
    }

    char line[256];
    int count = 0;

    while (fgets(line, sizeof(line), file) != NULL)
    {
        // Kommentare und Leerzeilen überspringen
        if (line[0] == '#' || line[0] == '\n' || line[0] == '\r')
            continue;

        char type_str[32];
        int x, y;
        char sprite[32];

        // Zeile parsen: "TYPE X Y SPRITE"
        if (sscanf(line, "%31s %d %d %31s", type_str, &x, &y, sprite) == 4)
        {
            // 1. Typ bestimmen
            EntityType type = parse_type(type_str);

            // 2. Entity auf dem Heap erstellen
            Entity *e = create_entity(x, y, type, sprite);

            // 3. Zur Liste hinzufügen
            if (e != NULL)
            {
                add_to_list(entities, e);
                count++;
            }
        }
    }

    fclose(file);
    printf("Entities geladen: %d\n", count);
    return true;
}

Erklärungen:

fgets liest eine Zeile (inkl. \n) in den Buffer
sizeof(line) verhindert Buffer Overflow
sscanf ist wie scanf, aber liest aus einem String statt stdin
%31s begrenzt auf 31 Zeichen (+ Null-Terminator = 32)
Rückgabewert von sscanf ist die Anzahl erfolgreich gelesener Felder

Was das Spiel kann

Nach Implementierung aller Funktionen:

NPCs, Gegner und Items erscheinen auf der Map
Schwert aufsammeln (Item mit sprite “sword”)
Gegner besiegen (wenn Spieler Schwert hat)
Spieler kann sterben (Gegner berühren ohne Schwert)