グリッド上で無作為に指向グラフを生成する

Question

ポケモンの氷摺動パズルと似たパズルゲームを作成する目的で、有向グラフをランダムに生成しようとしています。

これは私がランダムに生成できるようにするものであり、本質的に：http://bulbanews.bulbagarden.net/wiki/Crunching_the_numbers:_Graph_theory

Iは、x及びy次元でグラフのサイズを制限できるようにする必要があります。リンクの例では、8x4グリッドに制限されています。

ランダムなグラフを生成するのではなく、ノードの反対側に何か（岩のような）が必要なので、グラフをランダムに生成して2次元空間に正しくマップすることができますスライドを止めたときに視覚的に意味をなさせるようにします。この問題は、岩石が2つの他のノードの間の経路にあるか、場合によっては別のノード自体に到達することがあり、グラフ全体が壊れてしまうことがあります。

私が知っている少数の人々との問題を話し合った後、我々は解決策につながるかもしれない2つの結論に達しました。グラフを作成するときにグリッドに障害物を含める。完全に塗りつぶされたグリッドを使い、無作為なパスを描き、そのパスを動作させるブロックを削除します。ただし、削除するパスを見つけ出すことで、誤って短いパスを追加することはありません。ダイナミックプログラミングアルゴリズムは有益かもしれないと考えていましたが、私たちの誰もがダイナミックプログラミングアルゴリズムを作成することができませんでした。この問題が公式に呼び出されたことについてのアイデアやリファレンス（公式のグラフ問題の場合）が最も役立ちます。

Answer 1

表現が不完全だと言うので、グラフの問題としては見ません。パズルを生成するには、グリッド上で直接作業し、を後ろに置いて;最初に目的地を修正し、岩石を1つ以上の地点から到達させるために何らかの方法で配置し、反復的に石を追加して、他の地点に到達するようにします。

Answer 2

planar graphを生成すると、グラフのエッジが2次元空間内で重なり合わないことを意味します。平面グラフの別の定義は、各平面グラフがタイプK_3,3（6節点を有する完全な2つの部分）またはK_5（5つの節点を有する完全なグラフ）のいかなる部分グラフも持たないことである。

フラットグラフの高速生成にはpaperがあります。