1

これは実際には迷路ではありませんが、考え方は似ています。

私はこれを持っています：

ここに画像の説明を入力

問題は赤丸で囲んだところです。残りのパズルの一部ではない長方形を取り除く方法が必要です。

正方形で機能する単純なアルゴリズムを作成しました。

これが機能する方法は、2D 配列の各要素が頂点 (グラフ ノード) を表すことです。各グラフ ノードには、接続先の頂点のリストがあります。グラフは、各頂点からそれらの接続のそれぞれに線を引くことによって描かれます。

private void removeDisconnectedSquare(int x, int y)
{
    GraphNode topLeft = getNodeAt(x, y);
    GraphNode topRight = getNodeAt(x + 1, y);
    GraphNode bottomLeft = getNodeAt(x, y + 1);
    GraphNode bottomRight = getNodeAt(x + 1, y + 1);

    if(topLeft != null &&
       topRight != null &&
       bottomLeft != null &&
       bottomRight != null &&
       !hasNodeToLeft(topLeft) && hasNodeToRight(topLeft) && 
       !hasNodeAbove(topLeft) && hasNodeBelow(topLeft) &&
       hasNodeToLeft(topRight) && !hasNodeToRight(topRight) && 
       !hasNodeAbove(topRight) && hasNodeBelow(topRight) &&
       !hasNodeToLeft(bottomLeft) && hasNodeToRight(bottomLeft) && 
       hasNodeAbove(bottomLeft) && !hasNodeBelow(bottomLeft) &&
       hasNodeToLeft(bottomRight) && !hasNodeToRight(bottomRight) && 
       hasNodeAbove(bottomRight) && !hasNodeBelow(bottomRight))
    {
        removeVertex(x, y);
        removeVertex(x + 1, y);
        removeVertex(x,  y + 1);
        removeVertex(x + 1, y + 1);
    }
}

頂点のパスが頂点の大きな接続パスの一部ではないかどうかを検出できるアルゴリズムまたは方法はありますか? これにより、小さなパスが生成されることがあります。

ありがとう

4

1 に答える 1

0

良いグラフ ライブラリを見つけることをお勧めします。次に、各正方形をノードとして表し、それらの間に直接パスが開いている場合、正方形間にエッジを持ちます。最後に、「入口ノード」から開始する「接続ノード」アルゴリズム (グラフ ライブラリによって提供される) を使用します。最後に、接続アルゴリズムによってマークされていないすべてのノードをループして、それらを適切に処理できます。

たとえば、C++ を使用している場合は、Boost Graph Library Connected Components アルゴリズムを使用できます。他の優れたグラフ ライブラリにも同様のサポートがあるはずです。

このようなアルゴリズムの独自のバージョンを作成することもできます。たとえば、マークされていない隣接ノードをスタックにプッシュし、訪問したノードをマークしてから、完了するまでスタックからノードをポップします。ただし、優れたグラフ ライブラリがあると、この種のプロジェクトで発生する可能性が高い他の問題に役立ちます。IMO は、独自のものを開発するよりも望ましい方法です。

また、迷路生成アルゴリズムを変更して、常に接続されたグラフを生成する可能性があることにも注意してください。これにより、切断されたコンポーネントを後からクリーンアップする必要がなくなります。

于 2012-10-06T19:40:28.113 に答える