問題タブ [flood-fill]

また週末、ということは、趣味のプロジェクトで遊ぶことができるということです。

手動でテスト レベルを作成するのに飽きてきたので、エンジン開発から離れてレベル エディターに取り掛かることにしました。

レベルエディタ http://gfilter.net/junk/Editor.JPG

ペイント プログラムと同じように機能する塗りつぶしアルゴリズムをエディタに実装したいと考えています。ここで私にとってどのテクニックがうまくいくかについて誰かが何か指針を持っていますか?

レベルは単なる 2 次元配列なので、実際にはビットマップと同じと見なすことができます。

ありがとう！

再帰を使用して次のプログラムを作成しましたが、非再帰的に記述する方法がわかりません。非再帰バージョンを実行するたびに、数値がかなりずれています。再帰なしで次のメソッドを記述する方法について何か提案はありますか?

これは私が試したことです：

簡単なレベルでは手でプレイできますが、難しいレベルではコンピューター プログラムで解決することを意図したパズル ゲームを作成しています。パズルは、六角形のボード上の塗りつぶしです。ここでプロトタイプを試すことができます。

_{(出典: hacker.org )}

パズルの仕組みは次のとおりです。上から色を選択すると、左上のタイルから塗りつぶしが始まります。これにより、ボードが徐々に単色に変換されます。課題は、特定の数の手でこれを行うことです。

これに似たパズルをいくつか作成しましたが、キーは、作成方法を知らずに解決するのが難しいボードを生成するアルゴリズムを使用することです. たとえば、ここでは塗りつぶしを逆にしてボードを作成する場合があります。塗りつぶしがなくなるまで、ソリッド ボードから逆方向に作業します。これにかかったステップ数がわかっているので、これを解の下限として設定できます。

私が直面している問題は、このアプローチを試みると、上限が高すぎることです。ランダムに移動しても、この手数以内にパズルを解くのは簡単です。

解決策ではないアプローチは、ランダムなボードを生成し、それを最適に解決して、これをターゲットに設定することです。ポイントは、最適に解くことが NP 時間または少なくともハード P であるパズルを作成することです。

だから私が探しているのは、非常に難しいボードを生成できるアルゴリズムであり、それらを解決することは、ボードが大きくなるにつれて深刻な課題になります.

機能するフラッドフィル アルゴリズムを見つけようとしています。私が試した多くのアルゴリズムのうち、「再帰的な行の塗りつぶし」だけが、時々スタックを吹き飛ばすという主な注意事項を除いて、本来の動作をします。:(

私が見つけた多くの非再帰的な実装を試してみましたが、それらはすべて非常に気まぐれでした: 奇妙な場所にギャップを残すか、領域全体をあふれさせます (それらを囲む必要がある場合)。

C (または OOP が重すぎず、簡単に解きほぐすことができる C++) で記述された非再帰的なフラッドフィルで動作するソースコードを持っている人はいますか?

パスを構成するポイントの NSArray があります。それがいつ自己交差するかを検出できます。これが発生すると、パスを埋めようとします。

最初は CoreGraphics を使用しましたが、現在は openGl を使用して三角形の配列を描画しています。画像でわかるようにうまく機能しません。

「尻尾」を残して円形の領域だけを塗りつぶすにはどうすればよいですか? リバース フラッド フィルを考えていましたが、CG にはこのための API 関数がないと思います...

塗りつぶしアルゴリズムを作成しています...個々のピクセルをペイントする必要があります。これを行う最速の方法は何ですか? 最初はcocos2dのドローポイントを使おうと思ったのですが、320×480の頂点はちょっと物足りないです。memset などを使用するより速い方法はありますか?

パズル ゲーム Flood-It をプレイするのが好きです。このゲームは次の URL でオンラインでプレイできます。

https://www.lemoda.net/javascript/flood-it/game.html

iGoogle ガジェットとしても利用できます。目的は、連続するフラッド フィルの数を最小限に抑えてボード全体を埋めることです。

このパズルを最適に解決できるプログラムを作成しようとしています。この問題にアプローチする最善の方法は何ですか? 理想的にはA*アルゴリズムを使用したいのですが、残りのステップ数を推定する関数がどうあるべきかわかりません。塗りつぶされた領域を最大化するために深さ 4 のブルート フォース検索を実行するプログラムを作成しました。それはかなりうまく機能し、パズルを解くことで私を打ち負かしましたが、私はそのアルゴリズムに完全に満足していません.

助言がありますか？前もって感謝します。

OpenCV (キャニー エッジ検出)のエッジ検出モジュールからエッジ マップを抽出しました。私がやりたいことは、エッジ マップの穴を埋めることです。

私はC++とOpenCVライブラリを使用しています。OpenCV にはcvFloodFill()関数があり、穴をシード (フラッディングを開始する場所の 1 つ) で埋めます。ただし、シードを知らずにすべての内部の穴を埋めようとしています ( MATLAB のimfill()に似ています)。

Q1: 'cvFloodFill()' を適用できるように、すべてのシードを見つける方法は?
Q2: 'imfill()' に相当するものを実装する方法は?

OpenCVの初心者であり、ヒントをいただければ幸いです。

私はターボC ++を使用してCの単純なグラフィカルライブラリで作業しています。これは、ペイントスタイルプログラムの非常に原始的なバージョンを開発しているためです。すべてがうまく機能しますが、フラッドフィルアルゴリズムを機能させることができません。4 方向のフラッド フィル アルゴリズムを使用しています。最初に再帰バージョンを試しましたが、小さな領域でしか機能せず、大きな領域を埋めるとクラッシュします。読むと、明示的なスタックバージョンを実装すると問題が解決することがわかりましたが、実際にはわかりません。

私はこのようなスタックを開発しました:

そして、これは私がフラッドフィル関数に作成したコードです:

しかし、それでも機能しません。大きな領域を塗りつぶそうとすると停止します。プログラムで解像度 640 X 480 で作業しているため、これは本当に問題です。なぜそれがうまくいかないのですか？