迷路を表すデータ構造

Question

私は動的迷路のゲームを書いています。その都度、迷路の構造が変わります（いくつかの扉は閉じられ、いくつかの扉が開きます.HP4ではTriwazardのようなものです）。誰が私にどのデータ構造がこれを表現するのに最適であると私に提案できますか？

Answer 1

迷路は長方形のグリッドですか？他に何か？

また、地図のどの部分に有用な情報（パスまたはオブジェクト）が含まれるかによって異なります。

矩形のグリッドで、ほとんどのグリッドの四角にSOMETHINGが含まれている場合、良好なデータ構造は2D配列（配列の配列）であり、配列の各要素は1行、内部配列の各要素は1セルこの行には、そのセルに関連するデータを含むオブジェクト（隣り合ったセルを移動することができます。セルには何が含まれていますか、その上に文字があります）。しかしながら、迷路が矩形でない場合、または大きな迷路内のセルの大部分が実際に有用なものを実際には含まない（例えば、通過不可能なブロックである）場合、良好なデータ構造がグラフである。

グラフの各頂点は、通過可能なセルです。エッジは、移動可能なセルのペアを表します（一部のドアが片方向の場合のみ有向グラフにすることができます）。すべての頂点/セルは、そのセルに関する情報を含むオブジェクトである（例えば、物理的な迷路におけるその位置など）。

配列の構造上の利点は、それを描画するのが非常に簡単で、処理が簡単であることです（すべての移動はインデックスの中または消滅している）。壁の追加/削除は、隣接する2つのセルの配列要素のデータを変更するのと同じくらい簡単です。

グラフ構造のメリットは、迷路の通過が非常に疎な場合（たとえば、フィールドの1/100だけがパスである場合）、スペースが大幅に少なくなることです。ランダム（例えば、非長方形グリッド）ジオメトリを表すことができる唯一の構造であり、処理はかなり簡単である。 壁を追加/削除するのは、グラフにエッジを追加するだけなので簡単です。