2Dタイルマップでランダムパスを生成するアルゴリズム

Question

2Dタイルマップで単純なランダムパスを生成する必要があります。入力パラメータはいくつかのステップです。条件は、各タイルがパス上に2つの隣接するタイルを持つだけなので、ルームも交差もないということです。

ネット上で解決策を探していましたが、このようなものは見つかりませんでした。 Drunkardアルゴリズムは部屋を作り、その他はすべて迷路生成アルゴリズムです。たぶん私は適切なキーワードで検索していません。

毎回完全に異なるパスが必要なので、ランダム性が重要です。

編集：サンプル画像

サンプルパス追加：

を主な特徴は、各タイルがちょうど2隣人を有することです。

改善されたバージョンでは、特定のターゲットタイルをパスの最後と最小値と最大値として使用しますが、それは今のところ重要ではありません。

ありがとうございます。

Answer 1

1. ので、例えばNランダム障害

   を追加するには、マップのサイズの2次元配列を作成し、例えば0

2. ことによってそれをクリアする2Dマップ

   を作成塗りつぶされた円は

最短経路あなたは私のものを使用することができます

を見つける

3. ユースA * ... C++ A* example

あなたがより複雑な何かをしたいなら、あなたは、ランダムな地形を作成し、最短を見つけるために*を使用することができますパス（上がっていくとコストが下がります...）。ランダムな地形を作成するには、使用することができます。

• もランダムマップ生成に使用使用することができますDiamond and Square Island generator

が...

Answer 2

これを分割すると、あなたが取らなければならない唯一の決定は、ジャンクションを形成せずにパス上の任意の点で左/右/上/下に移動するかどうかです。マシンのタイムスタンプは、例えば、天気をチェックするために、最後の桁は偶数か奇数であり、偶数と奇数の場合は左に、モジュロ4の場合は上になります。

比較的高速で計算を遅くして、これを多くの時間にわたりスピンさせ、よりランダム性を導入してください。

また、2Dマップ上でDFSのようなトラバーサルを行い、各ユニークなパスをハッシュマップまたはセットに格納し、このマップに一意の番号をキーとして追加します。これがプリプロセッシングパートです。すべての可能な解の集合から一意の鍵を取り出し、それを集合から取り除きます。別のランダムな一意の経路が必要な場合は、残りの利用可能な経路からランダムに1つを選択します。