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

Я думаю о создании игры-головоломки, цель которой - заполнить сетку фигурными кусочками головоломки (например, классическими фигурами тетриса).

Как я могу создать набор частей, которые можно гарантированно использовать для заполнения сетки, не оставляя пробелов? Как я могу адаптировать этот алгоритм, чтобы масштабировать сложность получаемой головоломки?

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

Однако, если вы строите головоломки и умеете управлять частями, это обратная, конструктивная проблема и проще ...

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

Что касается решения / раскладки кусочков, типичный метод грубой силы - заполнить их слева направо, а затем сверху вниз. Найдите первую открытую ячейку (пронумерованную LR, TB) и попробуйте положить разрешенные фигуры в их разрешенную ориентацию (8 ориентаций для асимметричной фигуры, если вы разрешаете переворачивать). Возможно, проверьте сначала большие разрешенные части и прибегните к меньшим, если это необходимо. Когда вы достигнете состояния, которое вам не нравится (тупик, слишком много мелких кусочков или что-то еще), то возвращайтесь назад. Если данный набор сеток / фигур не соответствует вашим критериям, то есть он полностью откатился назад без завершения, попробуйте другой набор прямоугольников и фигур.

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

Некоторые известные полиоминологи включают в себя:

==> http://ee.usc.edu/faculty_staff/faculty_directory/golomb.htm Голомб изначально придумал термин «Полемино»

==> http://www.eklhad.net/polyomino/ Дальке решил довольно много прямоугольников, заполненных одинаковыми кусочками (особенно редкая форма мозаики)

В этой статье (стр. 11-13, отказ от ответственности: я один из авторов) описывается алгоритм, который использует динамическое программирование для равномерной генерации идеально плиточных прямоугольных областей ширины w и высоты h во времени, которое является линейным по h после предварительной обработки, которая занимает около 2 ^{( w . D )} времени / пространства ( D - самое длинное измерение индивидуальной формы, например, 4 в случае фигур Tetris).

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

Алгоритм работает для любого набора (выпуклых) форм.

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

Не стесняйтесь спрашивать, есть ли у вас проблемы с реализацией (у меня может даже быть какая-то быстрая и грязная реализация Python где-то рядом ...)

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

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

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

Вы выпускаете кусочки по одной полосе за раз, рандомизируя в каждом наборе "полосок". Если вы хотите увеличить сложность, случайным образом выпускайте из двух или более полос одновременно.

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

Продолжайте генерировать полосы, пока игрок не проиграет. Конечно, мой пример - полоса высотой 4 блока, но вы можете выбрать что-то большее и более сложное: