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

Для чисто случайного вы начинаете с пустая сетка и список «кандидатов» (тоже пустой).

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

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

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

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

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

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

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

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

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

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

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

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

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

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