私は、2 人から 4 人のプレイヤーが迷路の別々のエントリ ポイントに配置され、ゴール ポイントに到達する必要がある単純なマルチプレイヤー ゲームに取り組んでいます。一般的に迷路を生成するのは非常に簡単ですが、この場合、ゲームの目標は他の誰よりも早くゴールに到達することであり、生成アルゴリズムが特定のプレイヤーを他のプレイヤーよりも大幅に優先することは望ましくありません。
だから私は迷路生成アルゴリズムを探しています。このアルゴリズムでは、各プレーヤーの開始点からゴールまでの最適なパスは、平均パスよりも 10% 以上歩数が多くなりません。このようにして、プレイヤーは多かれ少なかれ平等な競技場にいます。誰かがそのようなアルゴリズムを思いつくことができますか?
（現状では1つのアイデアがありますが、よく考えられておらず、最適とはほど遠いようです-回答として投稿します。）
フリースペースの答えに代わるものは、ランダムな迷路を生成し、迷路の終わりに到達するまでの移動回数を表す値を各セルに割り当てることです (「終わりから始めると決めた場合は、両方を一度に行うことができます」 ')。次に、距離を選択し (おそらく、その距離で n ポイントの最大のものでしょうか?)、その値を持つ正方形にプレイヤーを配置します。
最初にプレイヤーとゴールの位置と等しい長さのパスを選択し、その後、定義されたパスを尊重して迷路を構築するのはどうですか? パスが交差しない場合、これは簡単に機能するはずです。
これには、ゴールと各プレーヤーのエントリ ポイントを設定してから、各プレーヤーのゴールまでの長さがほぼ同じパスを生成することでアプローチします。次に、これらのパスに沿って偽のブランチを追加し始め、他のプレイヤーのパスにリンクしたり、ブランチをパスに接続したりしないように注意しました。したがって、本質的にすべてのブランチは行き止まりです。
このようにして、パスの長さが類似していることを保証します。ただし、プレイヤー同士が交流することはできません。ただし、どちらのパスの分岐エントリ ポイントもゴールから同じ距離にあるように、分岐間にリンクを作成することで、これを組み込むことができます。そして、このブランチでは、楽しみと利益のために、より多くの行き止まりを分岐させることができます :-)
私が思いつく最も簡単な解決策は、通常のように迷路全体をランダムに生成してから、ゴール ポイントとプレイヤーの開始点をランダムに選択することです。これが完了したら、各開始点からゴールまでの最短経路を計算します。平均を見つけて、すべてのパスが適切なマージン内に収まるまで、平均を大幅に上回っているパスの「平滑化」を開始します (バリアを削除/移動します。これがどのように機能するかはわかりません)。さらに、平均を大幅に下回るものを取得して、追加のバリアを挿入することもできます。
途中のどこかで出口点を選んでください
そこから N 個のパスを開始し、ループごとに各パスに 1 を追加して、必要な長さにします。
N 個の開始点があり、それらはすべて同じ長さです。
迷路がいっぱいになるまで、行から分岐を追加します。