こんにちは、みなさん。私はこれでロジックを理解するのに本当に苦労していて、あなたが私を助けてくれることを望んでいました. 先に進む前に、私はアマチュア プログラマーであり、正式なコンピューター サイエンスのトレーニングを受けていない初心者であることをお伝えしたいと思います。ご容赦ください。:D また、私は Python を使用していますが、Java などを使用することもできます。
とにかく、初歩的な Drawbot で使用する Region Growing の実装を検討しています。地域の拡大に関する記事は次のとおりです: http://en.wikipedia.org/wiki/Region_growing
私が思い描く方法では、抽選の基になる画像は次の基準を満たします。
画像は、任意の色深度で最大 3x3 インチのサイズになります
画像は、白い背景に黒い連続した形になります
形状は、背景のどこにでも配置できます。
この問題に対する次の解決策を検討しました。ある程度機能するものもありますが、それぞれのパフォーマンスまたは実現可能性にかなりの欠陥があります (少なくとも、私には実行可能ではないようです)。さらに、これは Drawbot であるため、これは 1 つの連続した線で行う必要があります。ただし、これは後戻りできないという意味ではなく、複数の開始点 (シード) の可能性を排除するだけです。
考慮されるアプローチ:
ランダムウォーク：
この問題をランダム ウォークで解決することは、私の最初の本能でした。これを実現するランダム ウォーク プログラムは、次のようになると思います。
疑似パイソン...
Cells To Visit = Number of Black Cells
Cells Visited = 0
MarkColor = red
While Cells Visited < Cells To Visit:
if currentcell is black:
Mark Current Cell As Visited #change pixel to red
Cells Visited +=1
neighbors = Get_Adjacent_Cells() #returns cells either black or red
next cell = random.choose(neighbors)
currentCell = next cell
これは実現可能だと思いますが、非常に効果がないように思われ、良い結果を保証するものではありませんが、実際に何かを成し遂げるために、これを試すことになるかもしれません...疑似コードの私のロジックは漠然と正しいですか? ?
掃引パターン:
私には、この方法が最も簡単に実装できるように思えました。ここでの私の考えは、形状の 1 つの極値 (たとえば、一番左の一番下の点) で開始点を選択できるということです。そこから右に描画し、白いピクセルに到達するまで x 軸上でのみ移動します。ここから、y 軸で 1 ピクセル上に移動し、次に x 軸で白いピクセルに到達するまで左に移動します。真上のピクセルがたまたま白だった場合は、その上に黒いピクセルが見つかるまで x 軸をバックトラックします。
さらに調べてみると、この方法にはいくつかの大きな欠点があります。このような形状に直面した場合:
結果は次のようになります。
そして、しばらくしてからスイープを開始するように指示しても、中足はまだ見落とされます。
4/8 コネクテッド ネイバーフッド:
http://en.wikipedia.org/wiki/8-connected_neighborhood
この方法は私には最も強力で効果的であるように見えますが、現時点では完全には理解できません。
すべてのセルで、隣接する黒いセルを見て、どのセルを最初に訪問するかをランク付けする方法を考案し、それらすべてを訪問し、すべてのセルがカバーされるまでプロセスを繰り返します。
ここで見られる問題は、まず、これを達成するために必要なデータ構造を処理することと、その背後にあるロジックを理解することです。
これらは私が考えることができた最良の解決策です。時間を割いて読んでいただきありがとうございます。長いことは承知していますが、できるだけ明確にする必要があると思いました。すべての提案は大歓迎です...ありがとう！
編集：
迷路の生成と解決のアルゴリズムも調べましたが、ここでそれを実装する方法がわかりませんでした。迷路を解くアルゴリズムについての私の理解では、それらは迷路の通路が同じ幅であることに依存しているということです。もちろん、私はそれについて間違っている可能性があります。