ポケモンのアイス スライディング パズルに似たパズル ゲームを作成する目的で、有向グラフをランダムに生成しようとしています。
これは基本的に、ランダムに生成できるようにしたいものです: http://bulbanews.bulbagarden.net/wiki/Crunching_the_numbers:_Graph_theory
x 次元と y 次元でグラフのサイズを制限できるようにする必要があります。リンクの例では、8x4 グリッドに制限されます。
私が直面している問題は、グラフをランダムに生成することではなく、ノードの反対側に何か (岩のようなもの) が必要なため、2D 空間で適切にマップできるグラフをランダムに生成することです。スライドを止めると視覚的に意味があります。これに伴う問題は、岩が他の 2 つのノード間のパスまたは別のノード自体にある可能性があり、グラフ全体が壊れてしまうことがあります。
私が知っている何人かの人々と問題について話し合った後、解決につながる可能性のあるいくつかの結論に達しました. グラフを作成するときに、障害物をグラフの一部としてグリッドに含めます。完全に塗りつぶされたグリッドから始めて、ランダムなパスを描画し、そのパスを機能させるブロックを削除するだけですが、問題は、追加の短いパスを誤って導入しないように、どのブロックを削除するかを考え出すことになります. また、動的計画法アルゴリズムが有益かもしれないと考えていましたが、動的計画法アルゴリズムをゼロから作成することに熟練した人は誰もいません。この問題が公式に何と呼ばれているかについてのアイデアや参照 (公式のグラフの問題である場合) が最も役立ちます。