迷路を表現する

Question

私はこの迷路をどのように表していますか？そのため、私はdijkstrasアルゴリズムを実行できますか？

Maze

私は周りを探してきた、そして最も一般的な表現は隣接行列と隣接リストであるように見えます。

So：

1）頂点は何ですか？

2）私のエッジは何ですか？

レースになるので、迷路は手前では分かりません。

3）マトリックスを更新するにはどうすればよいですか？

注：私たちは迷路を探索するチャンスを与えられているので、ロボットが最初からどの距離にあるかを計算するマッパーと一緒にウォールフォロワーを使用しますマトリックスを構築する際の任意の用途の

Answer 1

たとえば、として部屋の構造を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 : 

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

としてあなたの迷路を宣言します。

struct tRoom[WIDTH][HEIGHT]; 

当初ロボットは（星を持っている）の出発部屋に置かれています。

プレーヤーは、キーを押すなどの操作でロボットの動きを制御できます。
ロボットはゴールルームに到達するとゲームが終了します。

確かに、いくつかのアルゴリズムでパスを見つけ、ロボットを目標に導くことができます。

Answer 2

私は、迷路の各ジャンクションをノードとして表現する構造体を定義します。各構造体は、別のノードへのポインタの形で頂点として分岐します。以下に沿って何かがそれを行うべき：

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

この表現にダイクストラ（またはその他のグラフ理論のアルゴリズム）を適用することは簡単です。