Случайное расположение плиток

Question

Мне нужно разместить плитки на большой сетке, исходящей из центральной точки таким образом, чтобы она выглядела органично и случайно. Новые плитки должны найти открытое пространство в сетке, которое касается по крайней мере 1 другой плитки.

Может ли кто-нибудь указать мне в праве на указание на что-нибудь, что может помочь с этим? Или какие-то базовые концепции, которые я могу прочитать по этому поводу?

Например, на этом рисунке уже создана форма (желтая), и я могу получить новую плитку, которая может быть 1x1, 2x2 или 3x3. Пытаясь найти хороший способ выяснить, где я могу разместить новую плитку, чтобы она касалась максимального количества текущих плиток.

Изображение: альтернативный текст http://osomer.com/grid.JPG

Answer 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 для каждого элемента мозаичного изображения и удалить значение с наибольшим случайным числом, либо сделать простой взвешенный случайный выбор, либо любым методом выбора по вашему выбору. .

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

Answer 3

Проблема с вашим вопросом в том, что «органический и случайный» может быть множеством разных вещей.Позвольте мне показать две ссылки

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

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

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

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

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

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

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

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

Answer 4

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