Darstellen eines Labyrinths

Question

Wie würde ich dieses Labyrinth darstellen, so dass ich den Dijkstras-Algorithmus darauf ausführen kann?

Maze

Ich habe um gesucht, und die häufigsten Darstellungen scheinen die Adjazenzmatrix und Adjazenzliste zu sein.

So:

1) Was soll meine Ecken sein?

2) Was sollen meine Kanten sein?

Weil es ein Rennen sein wird, ist das Labyrinth vorher nicht bekannt.

3) Wie aktualisiere ich meine Matrix?

Hinweis: Wir haben die Chance, das Labyrinth zu erkunden, also werde ich einen Wall-Follower zusammen mit einem Mapper verwenden, der die Entfernung des Roboters von Anfang an berechnet, aber nicht sicher, wie das alles aussehen würde von jeder Verwendung beim Aufbau der Matrix.

Answer 1

Zum Beispiel können Sie eine Raumstruktur als declaes:

struct tRoom { 
    enum { 
     NORTH, 
     EAST, 
     SOUTH, 
     WEST 
    }; 
    int walls[4]; /* status: 0 -- The wall is open 
          1 -- The wall is close 
        */ 
    ... 
} 

/* A room in the game looks like: 

     ____ The wall is close and cannot walk through 
     | 
     | 
     v 
    +-----+ 
    |  | 
    | 
    |  | 
    +- -+ 
    ^
     | 
     |____ The wall is open and can walk through 

*/ 

/* A maze looks like : 

    +-----+-----+-----+ 
    |  |  |  | 
    | *    | 
    |  |  |  | 
    +- -+-----+- -+ 
    |  |  |  | 
    |  |  |  | 
    |  |  |  | 
    +-----+-----+-----+ 
*/ 

und erklären Labyrinth als:

struct tRoom[WIDTH][HEIGHT]; 

Zunächst wird der Roboter auf den Startraum gelegt wird (die einen Stern hat) .

Dann kann der Spieler die Bewegung des Roboters per Tastendruck oder anderen Geräten steuern.
Das Spiel endet, wenn der Roboter den Zielraum erreicht.

Sicherlich können Sie einen Pfad durch einen Algorithmus finden und dann den Roboter zum Ziel führen.

Answer 2

Ich würde eine Struktur definieren, die jede Kreuzung des Labyrinths als Knoten darstellt, wobei jeder Korridor als Knoten in Form eines Zeigers zu einem anderen Knoten verzweigt. Etwas in der folgenden sollte es tun:

#define MAX_VERTEXES_PER_NODE 4 

struct junction; 

struct corridor { 
    int weight; 
    struct junction *other_end; 
}; 

struct junction { 
    struct corridor junctions[MAX_VERTEXES_PER_NODE]; 
}; 

Es ist unkompliziert Dijkstra (oder jede andere Graphentheorie Algorithmus) auf diese Darstellung anzuwenden.