11

有機的でランダムに見える方法で、中心点から放射状に広がる大きなグリッドにタイルを配置する必要があります。新しいタイルは、少なくとも 1 つの他のタイルに接触しているグリッド上のオープン スペースを見つける必要があります。

誰かがこれに役立つ可能性のあるものへの方向性を教えてもらえますか? または、私が読むことができるいくつかの基本的な概念は、この流れにありますか?

たとえば、この図では、既に作成された形状 (黄色) があり、1x1、2x2、または 3x3 の新しいタイルを受け取っている可能性があります。現在のタイルの最大量に触れるように、新しいタイルを配置できる場所を見つける良い方法を見つけようとしています.

写真: 代替テキスト http://osomer.com/grid.JPG

4

4 に答える 4

3

または、黄色のタイルが青/背景で「浸食」するため、この問題に対処することもできます。これを行うには、すべてのステップで、黄色のタイルに基本方向に隣接するすべての背景タイルの「浸食合計」Eに固定数を追加します (おそらく、斜めに隣接する背景タイルにその一部を加えます)。 ）。

次に、新しいタイルを配置するときが来たら、背景タイルごとに 0 からEまでの乱数を選択できます。最大のものは「浸食」されます。または、 Eを重みとして、単純な重み付きランダム選択を行うこともできます。

2x2 または 3x3 のタイルの場合、2x2 または 3x3 の正方形に適切に「収まる」タイルからのみ選択できます (つまり、2x2 または 3x3 の侵食されたタイルの端がすでに配置されたタイル)。しかし実際には、侵食やタイルを 1 つずつ配置するほど自然に見えるものは得られません。

新しいタイルを追加するときにのみ、その周りの侵食の合計を増やすだけで、繰り返しごとに侵食の合計を維持することで、侵食の合計を再計算する時間を節約できます (単純な+=)。この時点で、視点/哲学は異なりますが、提案された別の回答と本質的に同じです。

Erosion Sums Eのサンプル グリッド。直接のカーディナル ネイバーは +4、対角のネイバーは +1 です。

侵食合計 http://img199.imageshack.us/img199/4766/erosion.png

より高いEを持つものは、 「侵食」される可能性が最も高くなります。たとえば、この例では、西面と南面にある 2 つの小さな入り江が黄色によって侵食される可能性が最も高く、次に北面と東面の小さな入り江が続きます。最も可能性が低いのは、1 つのコーナーが黄色にかろうじて触れているものです。各タイルに 0 からEまでの乱数を割り当てて、乱数が最も大きいものを浸食するか、単純な加重ランダム選択を行うか、任意の決定方法を使用して、どれを決定するかを決定できます。

于 2010-06-25T06:25:56.723 に答える
2

純粋にランダムにするには、空のグリッドと「候補」リスト (これも空) から始めます。

最初のタイルをグリッドの中央に配置し、隣接する各タイルを「候補」リストに配置したばかりのタイルに追加します。次に、各ターン、「候補」リストからランダムなエントリを選択し、そこにタイルを配置します。タイルを配置した場所の隣に隣接する各グリッド位置を見て、空になっているそれぞれについて、次回の「候補」リストに入れます (まだそこにない場合)。

タイル グリッドに穴ができないようにするには、既に埋められている隣接するタイルの数に基づいて、グリッド位置を選択する確率を増やします (したがって、隣接するタイルが 1 つだけ埋められている場合、可能性は低くなります。それらがすべて埋められている場合、非常に高い確率になります）。

擬似コード:

grid = new array[width,height];
candidates = new list();

function place_tile(x,y) {
   // place the tile at the given location
   grid[x,y] = 1;

   // loop through all the adjacent grid locations around the one
   // we just placed
   for(y1 = y - 1; y1 < y + 1; y1++) {
       for(x1 = x - 1; x1 < x + 1; x1++) {
           // if this location doesn't have a tile and isn't already in
           // the candidate list, add it
           if (grid[x,y] != 1 && !candidates.contains(x1,y1)) {
               candidates.add(x1,y1);
           }
       }
   }
}

// place the first tile in the centre
place_tile(width/2, height/2);

while (!finished) {
   // choose a random tile from the candidate list
   int index = rand(0, candidates.length - 1);

   // place a tile at that location (remove the entry from
   // the candidate list)
   x, y = candidates[index];
   candidates.remove(index);
   place_tile(x, y);
}
于 2010-06-25T05:06:09.493 に答える
1

あなたの質問の問題は、「有機的でランダム」がさまざまなものになる可能性があることです。2つのリンクを表示させてください

  • ランダムなフラクタル地形を生成します（セクション「曇り空」を見て、それを白黒、またはあなたの場合は黄色/背景にすると想像してください）。
  • 侵食のシミュレーション(「侵食」の下の画像を見てください)

上記の 2 つのサンプルは、私にとっては「オーガニックでランダム」ですが、満足できないかもしれません。ですから、「有機的でランダム」とは何かをよりよく定義する必要があると思います.

今のところ、新しいタイルを追加するためのガイド ルールの定義を使用します (ただし、必ずしも同じ問題であるとは思いません)。

与えられた 2 つの形状 (ビットマップを想定) で、接触する辺の数が最大になるような形状の相対位置を見つけます

私も仮定します

  • オーバーラップは許可されていません
  • 結果のマージされた形状の中に穴を残すことができます
  • 図形を回転できません

このような条件下では、 x y ソリューションよりも少ないテストを行う必要があり、それぞれで必要な - オーバーラップがある場合は破棄する - 接触していない場合は破棄する - 接触している場合は、共通のエッジの数をカウントする の 3 つすべて上記のテストは、すべての黄色のタイルをスキャンすることで一定時間で実行できます (その数は konst x*y です) 。

では、上記は O(n^4) で簡単に実行できますが、それで十分ですか?

于 2010-06-25T08:54:39.633 に答える
0

双対グラフ、つまり頂点がセルの中心であるグリッドのランダム スパニング ツリーを計算します。そのためには、グリッドの中心から始めて、ランダムな深さ優先検索を行います。次に、中心からの木の距離が増加するようにセルをプロットします。

于 2010-06-25T11:46:46.820 に答える