Représenter un labyrinthe

Question

Comment est-ce que je représenterais ce labyrinthe, afin que je puisse exécuter l'algorithme de dijkstras dessus?

Maze

J'ai regardé autour, et les représentations les plus communes semblent être la matrice de contiguïté et la liste des contiguïté.

Alors:

1) Que devraient mes sommets être?

2) Quels devraient être mes bords? Comme il s'agira d'une course, le labyrinthe n'est pas connu à la main.

3) Comment mettre à jour ma matrice? Note: Nous avons la chance d'explorer le labyrinthe, donc j'utiliserai un suiveur de mur avec un mapper qui calcule la distance du robot depuis le début, mais je ne sais pas comment cela se traduirait par être de toute utilisation lors de la construction de la matrice.

Answer 1

Par exemple, vous pouvez declaes une structure de la salle:

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 : 

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

Et déclarer votre labyrinthe comme:

struct tRoom[WIDTH][HEIGHT]; 

Initialement, le robot est mis à la salle de départ (qui a une étoile) .

Ensuite, le joueur peut cotrol mouvement du robot par une touche ou d'autres appareils.
La partie se termine lorsque le robot atteint la salle des buts.

Vous pouvez certainement trouver un chemin à l'aide d'un algorithme, puis guider le robot vers le but.

Answer 2

Je définirais une structure qui représente chaque jonction du labyrinthe comme un nœud, chaque corridor se ramifiant comme un sommet sous la forme d'un pointeur vers un autre nœud. Quelque chose le long de ce qui suit devrait le faire:

#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]; 
}; 

Il est simple à appliquer Dijkstra (ou tout autre algorithme de la théorie des graphes) à cette représentation.