Rat in a Maze in C++ lösen: Stack, Queue, Makefile

Einführung: Das Rat-in-a-Maze-Problem und warum es heute wichtig ist

Stell dir vor, eine KI-gesteuerte Ratte sucht den Weg durch ein Labyrinth – genau wie ein autonomer Staubsauger oder ein Roboter in einer Lagerhalle. In diesem Tutorial lernst du, wie du das klassische Rat-in-a-Maze-Problem mit Stacks und Queues in C++ löst. Dieses Problem ist ein Paradebeispiel für die Anwendung von Datenstrukturen und Algorithmen, die auch in modernen Apps wie Google Maps oder KI-Spielen stecken. Wir nutzen dabei Makefiles, ADTs und Header-Dateien – genau wie in der Aufgabenstellung CS3530 gefordert.

Grundlagen: Stacks und Queues im Vergleich

Ein Stack arbeitet nach dem LIFO-Prinzip (Last In, First Out) – wie ein Stapel Bücher. Eine Queue dagegen folgt FIFO (First In, First Out) – wie eine Warteschlange an der Mensa. Für das Labyrinth-Problem eignet sich der Stack für die Tiefensuche (DFS) und die Queue für die Breitensuche (BFS). Stell dir vor, du suchst in einem Spiel wie Minecraft nach einem Schatz: Mit DFS gehst du einen Weg zu Ende, mit BFS suchst du schichtweise.

Projektstruktur: Makefile und separate Kompilierung

Wir erstellen mehrere Dateien: maze.h (ADT für das Labyrinth), maze.cpp (Implementierung), stack.h und queue.h (eigene Header) sowie main.cpp. Ein Makefile automatisiert die Kompilierung. So sieht ein einfaches Makefile aus:

CC = g++
CFLAGS = -Wall -g

all: maze

maze: main.o maze.o stack.o queue.o
	$(CC) $(CFLAGS) -o maze main.o maze.o stack.o queue.o

main.o: main.cpp maze.h stack.h queue.h
	$(CC) $(CFLAGS) -c main.cpp

maze.o: maze.cpp maze.h
	$(CC) $(CFLAGS) -c maze.cpp

stack.o: stack.cpp stack.h
	$(CC) $(CFLAGS) -c stack.cpp

queue.o: queue.cpp queue.h
	$(CC) $(CFLAGS) -c queue.cpp

clean:
	rm -f *.o maze

Mit make wird alles übersetzt – das spart Zeit und vermeidet Fehler. Separate Kompilierung ist besonders bei größeren Projekten wie Spieleentwicklung oder KI-Modellen üblich.

Implementierung der ADTs: Stack und Queue

Wir definieren eigene abstrakte Datentypen (ADTs) für Stack und Queue. Hier ein Beispiel für den Stack als Template-Klasse:

// stack.h
#ifndef STACK_H
#define STACK_H

template <typename T>
class Stack {
private:
    struct Node {
        T data;
        Node* next;
        Node(const T& d) : data(d), next(nullptr) {}
    };
    Node* top;
public:
    Stack() : top(nullptr) {}
    ~Stack();
    void push(const T& item);
    T pop();
    bool isEmpty() const;
};

#include "stack.cpp"
#endif

Die Queue wird ähnlich aufgebaut, aber mit front und rear. Diese Header-Dateien und die dazugehörigen Implementierungen sind das Herzstück des Projekts.

Das Labyrinth-Modell: 2D-Array und Pfadfindung

Das Labyrinth speichern wir in einem 2D-Array (int** maze). 0 = frei, 1 = Wand, 2 = Ziel. Die Ratte startet bei (0,0). Wir markieren besuchte Zellen, um Endlosschleifen zu vermeiden. Hier ein Ausschnitt aus maze.h:

// maze.h
#ifndef MAZE_H
#define MAZE_H

#include "stack.h"
#include "queue.h"

class Maze {
private:
    int rows, cols;
    int** grid;
    bool** visited;
public:
    Maze(int r, int c);
    ~Maze();
    void loadFromFile(const char* filename);
    bool solveWithStack();  // DFS
    bool solveWithQueue();  // BFS
    void printPath();
};

#endif

Algorithmus: Tiefensuche (DFS) mit Stack

Bei DFS nutzen wir einen Stack. Wir pushen den Startpunkt und solange der Stack nicht leer ist, holen wir die oberste Position. Wenn es das Ziel ist, fertig. Sonst prüfen wir die vier Nachbarn (oben, unten, links, rechts) und pushen unbesuchte, begehbare Zellen. Das ist wie beim Backtracking in einem Puzzle-Spiel – du gehst einen Weg und kehrst zurück, wenn es nicht weitergeht.

bool Maze::solveWithStack() {
    Stack<pair<int,int>> s;
    s.push({0,0});
    visited[0][0] = true;
    while (!s.isEmpty()) {
        auto [r,c] = s.pop();
        if (grid[r][c] == 2) return true;
        // Nachbarn prüfen (Reihenfolge: oben, unten, links, rechts)
        int dr[] = {-1,1,0,0};
        int dc[] = {0,0,-1,1};
        for (int i=0; i<4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr>=0 && nr<rows && nc>=0 && nc<cols && !visited[nr][nc] && grid[nr][nc]!=1) {
                visited[nr][nc] = true;
                s.push({nr,nc});
            }
        }
    }
    return false;
}

Algorithmus: Breitensuche (BFS) mit Queue

BFS verwendet eine Queue. Wir enqueuen den Start und markieren ihn. Dann holen wir vorn ein Element, prüfen auf Ziel und enqueuen alle Nachbarn. So wird das Labyrinth schichtweise durchsucht – ähnlich wie ein Virus sich in einem Netzwerk ausbreitet oder wie soziale Medien Freunde vorschlagen (Grad der Trennung). BFS findet den kürzesten Weg, wenn alle Schritte gleiches Gewicht haben.

bool Maze::solveWithQueue() {
    Queue<pair<int,int>> q;
    q.enqueue({0,0});
    visited[0][0] = true;
    while (!q.isEmpty()) {
        auto [r,c] = q.dequeue();
        if (grid[r][c] == 2) return true;
        int dr[] = {-1,1,0,0};
        int dc[] = {0,0,-1,1};
        for (int i=0; i<4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr>=0 && nr<rows && nc>=0 && nc<cols && !visited[nr][nc] && grid[nr][nc]!=1) {
                visited[nr][nc] = true;
                q.enqueue({nr,nc});
            }
        }
    }
    return false;
}

Vollständiges Beispiel: main.cpp

In main.cpp laden wir ein Labyrinth aus einer Datei und rufen beide Lösungen auf:

#include <iostream>
#include "maze.h"

int main() {
    Maze maze(5,5);
    maze.loadFromFile("maze.txt");
    
    if (maze.solveWithStack()) {
        std::cout << "DFS: Weg gefunden!" << std::endl;
        maze.printPath();
    } else {
        std::cout << "DFS: Kein Weg." << std::endl;
    }
    
    // visited zurücksetzen für BFS
    maze.resetVisited();
    if (maze.solveWithQueue()) {
        std::cout << "BFS: Weg gefunden!" << std::endl;
        maze.printPath();
    } else {
        std::cout << "BFS: Kein Weg." << std::endl;
    }
    return 0;
}

Makefile und Kompilierung

Erstelle eine Datei maze.txt mit dem Labyrinth (0= frei, 1= Wand, 2= Ziel):

Führe make aus und dann ./maze. Du siehst die Ausgabe, ob ein Pfad gefunden wurde. Dieses Setup ist typisch für UNIX/Linux-Umgebungen und wird auch in der Spieleentwicklung oder bei Embedded Systems verwendet.

Erweiterungen und reale Anwendungen

Das Rat-in-a-Maze-Problem ist die Basis für viele Algorithmen in der Robotik, Navigation und KI. Zum Beispiel nutzen autonome Fahrzeuge ähnliche Konzepte, um Hindernisse zu umfahren. Auch in Computerspielen wie The Legend of Zelda oder Minecraft werden Pfadfindungsalgorithmen eingesetzt. Mit Stacks und Queues hast du mächtige Werkzeuge an der Hand, um solche Probleme zu lösen.

Häufige Fehler und Tipps

Vergessen, besuchte Zellen zu markieren: Führt zu Endlosschleifen.
Falsche Reihenfolge der Nachbarn: Beeinflusst den Pfad, aber nicht die Korrektheit.
Keine Speicherbereinigung: Verwende Destruktoren, um den Heap-Speicher freizugeben.
Makefile nicht aktuell: Nach Änderungen an Headern muss make neu ausgeführt werden.

Fazit

Du hast gelernt, wie man das Rat-in-a-Maze-Problem mit Stacks und Queues in C++ löst, inklusive Makefile, ADTs und Header-Dateien. Diese Techniken sind essenziell für die Softwareentwicklung und helfen dir, komplexe Probleme strukturiert anzugehen. Probiere es selbst aus – und denk daran: Jedes große Labyrinth wird Schritt für Schritt gelöst!