4

あらかじめ決められたサイズの 2D 配列と、そのスペースに収まる番号付きの四角形のリストがあります。これらの各長方形には、既知の固定の高さと幅があります。2D 配列は、すべての四角形を快適に収めるのに十分な大きさであることが保証されています。

これらの各長方形を配列にランダムに配置して、重ならないようにし、すべてが配置されるようにする必要があります。それらは任意の方向に配置できます。戦艦のゲームに自分の船を配置することを想像してみてください。船のサイズがより多様で、グリッドがはるかに大きくなっています。

完成した配列は次のようになります: (0 は空のスペースを表し、ゼロ以外の数値は四角形の数値を表します)

0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 4 4 4 0
0 1 1 0 2 2 2 2 2 0 0 0 4 4 4 0
0 1 1 0 2 2 2 2 2 0 0 0 0 0 0 0
0 2 2 2 2 0 0 0 0 0 0 0 0
0 2 2 2 2 0 5 5 0 0 0 0
0 3 3 3 3 3 0 0 0 0 5 5 0 0 0
0 3 3 3 3 0 7 7 7 5 5 6 6 0 0
0 0 0 0 0 7 7 5 5 6 6 0 0

私が検討した 1 つのアプローチは、四角形ごとに、ランダムな配置と方向を選択し、それをマトリックスに配置しようとすることです。以前に配置されたブロックとの衝突が検出された場合は、再試行してください。これはおそらく最も簡単に実装できますが、あまり効率的ではないようで、明確に決定論的な方法で終了しません (リストの末尾近くの長方形は、以前に生成されたブロックとかなりの時間衝突し続ける可能性があります)。

後の長方形を配置するのにそれほど問題にならない、これを行うためのより良い方法はありますか?

4

4 に答える 4

1

次のアプローチ：

  • あなたの最小寸法が何であるかを調べてください。この寸法よりも小さいが、ボックスに複数回収まるサイズを計算します。例：最小サイズは7 cm /インチ、ボックスは120cm/インチです。120/20 =6cm/インチを選択します。考えられるすべての座標をリストに保存するので、問題が十分に小さいことを願っています。この場合、20x20=400の座標があります。

  • 領域全体をブロックできないことを保証するには、最小の次元（x、y）が長方形の最大の次元の2倍以上になるように行列を選択します（たとえば、長方形の最大長= 8、xとyの両方）少なくとも32）が必要であり、マトリックスの領域全体に、挿入されたすべての要素の2倍の領域が少なくとも含まれている必要があります。

  • 配置の選択：乱数ジェネレーターを使用して、座標をランダムに選択します。指定された座標に長方形を配置し、ランダムな方向も選択します。長方形をボックスにセットしてみてください。最初に収まらない場合は、回転させてください。それでも収まらない場合は、次の座標を試してください。

  • 最終的に収まる場合は、長方形と重なっているすべての座標をリストから削除します。したがって、他の長方形に対してのみ有効な座標を選択しています。

  • ランダム化：線形合同法を使用しないでください（残念ながら、ほとんどのプログラミング言語のタスク標準には使用されていません）。それらは悪い多次元特性を持っています。安全なランダムハードウェアジェネレーター、またはMersenneTwisterなどの既知の良好なジェネレーターを使用します。

于 2012-06-29T17:21:15.393 に答える
1

IMOの問題は、「次の長方形に収まる十分なスペースがあるか、この場所を効率的に見つけるにはどうすればよいか?」という質問に悪化します。そう：

  1. 初期条件 - 「使用可能な長方形のリスト」に使用可能な長方形 (初期マトリックス) が 1 つあります。基本的には、自由な長方形の高さと重量、および初期マトリックスの左上の位置のみを格納する必要があります。
  2. 追加するランダムな長方形を選択 = 「toAdd」、「長方形を追加するリスト」から削除
  3. 「toAdd」=「利用可能」以上の空いている利用可能な四角形をランダムに選択し、「利用可能な四角形のリスト」から削除します。利用可能な四角形がない場合は、ステップ 2 に進みます。
  4. 「利用可能」のランダムな場所を選択して、「toAdd」長方形を追加します
  5. 「使用可能な」長方形を切り取って「toAdd」を減算します。ここでは異なるカット戦略を適用できますが、最終的には最大 4 つの新しい利用可能な長方形を受け取ることができます
  6. 「使用可能な長方形のリスト」に新しい使用可能な長方形を追加します
  7. ステップ 2 に進みます

理想的な世界では、ステップ 6 で利用可能な 2 つのネイバーを連結する必要があるため、アルゴリズムは最適ではありません。

于 2012-06-29T17:40:13.137 に答える
0

この問題は、ローグライクダンジョンマップの生成とほとんど同じです。これには、さまざまな外観のアプローチがたくさんあります。

ここからBSPツリーアプローチを提案します（手順は簡単です）： http ：//www.futuregadgetlab.com/proceduraldungeon/

于 2012-06-29T20:43:54.050 に答える
0

計算を簡素化し、回転の制限から開始してから、kd ツリーを使用できます。良い例は、jquery masonry プラグインまたは jquery ツリーマップ アルゴリズムです。アイデアは、長方形をどこかに配置し、x ポイントをツリーの左側に、y ポイントを右側に分離することです。

于 2012-06-29T22:54:29.767 に答える