Случайный макет плитки

Ответ 1

В качестве альтернативы вы можете подойти к этой проблеме, поскольку желтые плитки "размываются" на синем фоне. Для этого на каждом шаге на желтой черепице добавьте фиксированное число в "сумму эрозии" E всех фоновых плит, соседствующих с ним в кардинальном направлении (и, возможно, к фоновым плиткам, соседствующим с ним по диагонали).

Затем, когда придет время разместить новую плитку, вы можете для каждой фоновой плитки выбрать случайное число от 0 до E; самый большой из них "разрушен". Альтернативно, вы можете сделать простой взвешенный случайный выбор, при этом E будет их весом.

Для плиток 2x2 или 3x3 вы можете выбрать только из плиток, которые соответствующим образом "соответствуют" квадрату 2x2 или 3x3 (т.е. 2x2 или 3x3 эродированная плитка на ее краю, так что она не вызывает перекрытия с уже размещенными плитами). Но на самом деле, вы никогда не получите нечто естественное, как одноразовое размещение эрозии/плитки.

Вы можете сэкономить время, пересчитывая суммы эрозии, сохраняя их с каждой итерацией, только при добавлении новой плитки вверх по сумме эрозии вокруг нее (простой +=). На данный момент это по существу то же самое, что и другой ответ, хотя и с другой перспективой/философией.

Примерная сетка Эрозионных сумм E, при этом прямые кардинальные соседи равны +4, а диагональные соседи - +1:

Эрозионные суммы http://img199.imageshack.us/img199/4766/erosion.png

Те, у кого больше E, скорее всего, будут "размыты"; например, в этом, два маленьких входа на запад и юг лица, скорее всего, будут размыты желтым, а затем меньшие заливы на северной и восточной сторонах. Скорее всего, они едва касаются желтого на один угол. Вы можете решить, какой из них можно либо присвоить случайному числу от 0 до E для каждого фрагмента, и подобрать номер с наивысшим случайным числом, либо сделать простой взвешенный случайный выбор, либо любым методом принятия решений выбор.

Ответ 2

Для чисто случайных, вы начинаете с пустой сетки и списка "кандидатов" (также пустых).

Поместите первую плиту в центр сетки, затем добавьте каждую соседнюю плиту в ту, которую вы только что разместили, в список "кандидат" . Затем, каждый поворот, выберите случайную запись в списке "кандидат" и поместите там фрагмент. Посмотрите на каждую соседнюю сетку, расположенную рядом с местом, где вы только что поместили плитку, и для каждого, который также пуст, поместите его в список "кандидат" в следующий раз (если он еще не существует).

Чтобы избежать создания отверстий в вашей сетке плитки, увеличьте вероятность выбора местоположения сетки на основе количества смежных фрагментов, которые уже заполнены (так что если только одна соседняя плитка уже заполнена, она имеет низкий уровень вероятности. все они заполнены, это будет иметь очень высокую вероятность).

В псевдокоде:

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);
}

Ответ 3

Проблема с вашим вопросом заключается в том, что "органические и случайные" могут быть разными. Позвольте мне показать две ссылки

• генерация случайный фрактальный ландшафт (посмотрите раздел "Облачные небеса" и представьте, что вы превращаете его в ч/б или в ваш случай желтый/фон).
• моделирование эрозия (посмотрите изображение под "erode" )

Два вышеприведенных образца являются "органическими и случайными" для меня, но вы можете быть не удовлетворены этими. Итак, я думаю, вам нужно будет лучше определить, что является "органическим и случайным".

В настоящее время я возьму ваше определение руководящего правила для добавления новых фрагментов (но не думаю, что это обязательно одна и та же проблема), которую я читаю как:

Учитывая две формы (предполагая растровые изображения) найти относительное положение таким образом, чтобы количество трогательные стороны максимально

Я также предполагаю

• перекрытие не разрешено
• вы можете оставить отверстия внутри результирующей, объединенной формы
• вы можете не вращать фигуры

В таких условиях вам нужно протестировать меньше xy-решений, и в каждом случае вам нужно  - отбросить его, если есть перекрытие  - отбросьте его, если они не касаются  - если они касаются, то подсчитайте количество ребер, которые являются общими Все три вышеуказанных теста можно выполнить в течение постоянного времени, просматривая все желтые плитки (число которых равно konstx * y)

Итак, вышесказанное легко может быть сделано в O (n ^ 4), это достаточно хорошо для вас?

Ответ 4

Вычислить случайное связующее дерево для двойного графа, то есть сетку, вершины которой являются центрами ваших ячеек. Для этого начинайте в центре сетки и выполняйте случайный поиск по глубине. Затем создайте ячейки для увеличения расстояния между деревьями от центра.