最適なマルチプレイヤー迷路生成アルゴリズム

Question

私は、2 ～ 4 人のプレイヤーが迷路の別々の入り口に配置され、ゴール ポイントに到達する必要がある単純なマルチプレイヤー ゲームに取り組んでいます。一般に迷路を生成するのは非常に簡単ですが、この場合、ゲームの目的は他のプレイヤーよりも早くゴールに到達することであり、生成アルゴリズムで 1 人のプレイヤーが他のプレイヤーよりも大幅に有利になることは望ましくありません。

そこで、スタート地点からゴールまでの各プレ​​ーヤーにとっての最適な経路が、平均的な経路よりも 10% 多いステップ数以下となる迷路生成アルゴリズムを探しています。このようにして、プレーヤーは多かれ少なかれ平等な競争の場に立つことができます。誰かそのようなアルゴリズムを思いつくことができますか?

(現状ではアイデアが 1 つありますが、よく考えられておらず、最適とは程遠いようです。回答として投稿します。)

Answer 1

フリースペースの答えに代わる方法は、ランダムな迷路を生成し、各セルに迷路の終わりに到達するまでの移動回数を表す値を割り当てることです（終わりから始めると決めた場合は、両方を一度に行うこともできます） ')。次に、距離 (おそらくその距離に n ポイントがある最も高い距離) を選択し、その値の正方形にプレーヤーを配置します。

Answer 2

最初にプレーヤーとゴールの位置、および等しい長さのパスを選択し、その後、定義されたパスを尊重して迷路を構築するのはどうでしょうか?パスが交差していなければ、これは簡単に機能すると思います

Answer 3

私はこれに、ゴールと各プレーヤーのエントリーポイントを設定し、各プレーヤーのゴールまでの同様の長さのパスを生成することでアプローチします。次に、他のプレイヤーのパスにリンクしたり、分岐がパスに再び接続されたりしないように注意しながら、これらのパスに沿って偽の分岐を追加し始めます。したがって、基本的にすべての分岐は行き止まりになります。

こうすることで、パスの長さがほぼ同じになることが保証されます。ただし、プレイヤーが相互に対話することはできません。ただし、どちらかのパスの分岐エントリ ポイントがゴールから同じ距離にあるように分岐間にリンクを作成することで、これを組み込むことができます。そして、この分岐では、楽しみと利益のためにさらに行き止まりを分岐させることができます :-)

Answer 4

私が思いつく最も簡単な解決策は、通常のように迷路全体をランダムに生成し、ゴール ポイントとプレイヤーのスタートポイントをランダムに選択することです。これが完了したら、各スタートポイントからゴールまでの最短パスを計算します。平均を見つけて、すべてのパスが適切なマージン内に収まるまで、その平均を大幅に上回るパスの「平滑化」(バリアの削除/移動 -- これがどのように機能するかはわかりません) を開始します。さらに、平均を大幅に下回っているものを選択し、追加の障壁を挿入することも可能です。

Answer 5

中間のどこかに出口ポイントを選択してください

そこからnパスを開始し、ループごとに各パスに1を追加します。

N 個の開始点があり、それらはすべて同じ長さです。

迷路がいっぱいになるまで、線から分岐を追加してください。