動的迷路変異

Question

私はまだ別の迷路ゲームを作成する考えがあります。しかし、重要な違いがあります。ゲーム中に迷路がオンザフライで変化します。私は問題を考えるときには、以下の制限が私の心に入って来る：メインルートがフィニッシュ

迷路突然変異につながる唯一のルートである

変化しない迷路の主なルートはあり

1. バックメインルート

へのパスをブロックしてはいけませんまた、（ゲームの難易度に影響を与える）を制御するとよいでしょう：

1. 1回の突然変異の間にどのくらいの迷路が変化するか
2. 与えられた制限に違反しないであろう説明迷路生成/突然変異のために、あなたはアルゴリズムを提案する（またはあなたのアイデアを与えることができます）：プレイヤーしばらく迷路にブロックされ得ることができます）

EDIT： 質問はありますか？

Answer 1

あなたは可能性：

1. ランダム（またはいくつかの卑劣な基準を使用して）でパスをブロックします。

2. 迷路をスキャンして、接続されていない2つの領域に分割されているかどうかを確認します。

3. 接続を解除すると、両方の領域に隣接する限り、壁をランダムにノックダウンすることができます。

迷路に任意の2点間に1つのパスしかない場合、手順2は常に迷路を分割するため、常に＃3が必要になります。

Answer 2

迷路のすべてのセルとそれらの間の歩行可能な接続を接続するグラフを作成します。迷路を修正するには、まずランダムな壁を選択してノックダウンし、グラフに新しいエッジを生成します。次に、そのエッジを含むグラフ内のサイクルを見つけ、そのサイクル内のランダムで非メインパスのエッジを削除します。これにより、他のどこかでエッジを立てます。

このアルゴリズムでは、すべてのセルが開始時に到達可能であった場合でも、そのままになります。あなたはおそらくその機能を欲しがることはできません。

Answer 3

これはおそらくかなり簡単です。 standard depth-first-search algorithmを使用して迷路を生成します。 （唯一の）パスを形成するセルのリストを、リストの最初から最後まで格納します。

1. クリティカルパスに沿った任意のセルを除いて、迷路全体をデフォルト状態（すべての壁が定位置）にリセットします。必要に応じて、迷路全体をリセットします。プレイヤの現在の位置の見通し内のセルはほとんどありません。
2. 最初から幅優先探索アルゴリズムを再実行します。変更するには、未探索の探索対象ノードを選択するときに、既に壁を削除したエッジを優先します。

第2ステップの変更により、アルゴリズムがまず既存のパスを探索し、そこからサイドパスなどを追加することが保証されます。あなたが望んでいない場合でもクリティカルパスを保持することは厳密には必要ではありません。ユーザーが立っている場所を除いて迷路全体を再生成し、有効なままにしておくことができます。

I これは、元のアルゴリズムと同じ方法で常に有効なツリーを生成するはずですが、ユーザーの周りにあるセルを保存することの意味については100％確信していません。クリティカルパス。私は再構成された迷路はユーザーの立場からいつでも解決できるということは肯定的です。

これはかなりきちんとしたアイデアです。私は、ユーザーが探していない場所でも、迷路のレイアウトを大幅に変更するというアイデアが大好きです。一人称でこれをやっているのであれば、見ることができないときにカメラの視界を変えることさえ可能です。