問題グリッド (2D 配列) をランダムな形状の部分 (地球の構造プレート
と考えてください) に分割したいと考えています。
基準は次のとおりです。
- ユーザー入力グリッド サイズ (これは非常に大きくなる可能性があるため、プログラムはスケーリングする必要があります)。
- ユーザーがグリッドの分割係数 (パーツの数) を入力します。
- Grid は長方形の 16 進グリッドで、上下にキャップがあり、左右に回り込みます。
- パーツの分解はありません。
- 他のパーツの中にパーツはありません。
- 極小部品や超大型部品はありません。
- 真円でないランダムな形状のパーツ、または伸びた蛇行形状。
私の解決策：
- 隣接するセルにアクセス/操作できるメソッドを作成します。
- 各パーツのサイズをランダムに決定します (すべてのパーツの合計が 2D 配列全体のサイズに等しくなります)。
- 2D 配列全体を最後の部分の ID 番号で埋めます。
- 最後の部分を除く各部分について:
- 2D 配列のランダムなセルに現在のパーツ ID 番号をシードします。
- 配列全体を反復処理し、現在のパーツ ID 番号で既にシードされているセルに隣接する各セルのアドレスを格納します。
- 保存されているアドレスの 1 つを抽出し、そのセルに現在のプレート ID 番号を入力します (したがって、パーツが形成され始めます)。
- 部品サイズに達するまで繰り返します。
長く伸びた「腕」や内部に大きな穴があるパーツを避けるために、2 つのストレージ アレイを作成したことに注意してください。それから私は前者の前に後者を使い果たします。
私のソリューションを実行すると、次のようになります:
グリッド サイズ: 200
幅: 20
高さ: 10
パーツ: 7
66633333111114444466
00033331111114444466
00003331111114444466
00003331111144444660
00000333111164444660
00000336111664422600
00000336615522222200
00006655555522222200
00006655555552222220
00066655555552222220
品番：0
品番：47
パーツ数：1
パーツサイズ：30
パーツ数：2
パーツサイズ：26
パーツ数：3
パーツサイズ：22
パーツ数：4
パーツサイズ：26
パーツ数：5
パーツサイズ：22
パーツ数：6
パーツサイズ：27
私の解決策の問題：
- 最後の部分は常に断片化されています。上記の場合、6 の 3 つの別々のグループがあります。
- パーツが袋小路で形成され、フルサイズに成長する余地がない場合、アルゴリズムは停止します (アルゴリズムは、他のパーツの上にパーツを形成することを許可しません。開始時の 2D 配列)。
- 2D 配列を形成する前にパーツ サイズを指定せず、パーツの数を指定してその場でパーツ サイズをランダムに生成するだけで間に合わせると、小さなパーツが形成される可能性が残ります。特に 2D 配列が非常に大きい場合は特にそうです。現在のパーツ サイズの方法では、パーツ サイズを 2D 配列の合計サイズの 10% から 40% に制限しています。これを行うための非常にエレガントな方法があれば、パーツのサイズを指定しなくても大丈夫かもしれません - ユーザーが持つ唯一の制御は、2次元配列のサイズとパーツの数です。
その他のアイデア:
- パーツを完全に整列した正方形に形成し、2D アレイを実行して、各パーツが他のパーツにランダムに侵入し、ランダムな形状に変形させます。
- グリッドを横切る蛇行を描き、作成されたスペースを埋めます。おそらく次のような数学を使用します: http://mathworld.wolfram.com/PlaneDivisionbyLines.html
結論:
ここに問題があります: 私は初心者プログラマーで、この問題に正しい方法で取り組んでいるかどうか確信が持てません。断片化されたパーツを一緒に移動し、成形パーツが袋小路に詰まった場合に袋小路から「飛び出す」ことを可能にする「パッチアップ」メソッドをさらに作成できますが、面倒です。
この問題にどのように取り組みますか? おそらく物事を単純化するために使用できるセクシーな数学はありますか?
どうも