Создать алгоритм генерации блоков тетриса для картинки?
Возможно ли создать оптимальный алгоритм для генерации блоков как в игре тетрис?
Не только блоки как в оригинальной игре, а возможно и другие формы.
В данный момент я закончил написание алгоритма для генерации блоков, однако он достаточно грязный. На маленьких картах размером 10x18 он работает хорошо, затрачивается около полу-секунды на генерацию, однако на больших картах он перестает работать вовсе.
Исходная задача такая. У нас есть какая либо пиксельная картинка. Нам надо сгенерировать блоки так, что бы они двигались сверху вниз и как в обычном тетрисе, но должны не проваливаться в пустые области. Например, представим человечка. У него есть руки и если блок должен быть расположен в позиции ладони, то он провалится, т.к. под ним нет установленных блоков и рука как бы висит над нулевыми координатами. А значит блок должен кое-как цеплять соседний блок.
Мой алгоритм описывается так. Первоначально генерируются стартовые точки блоков на карте примерно на одном расстоянии. Далее генерируются блоки вокруг этих точек, пока вся картинка не заполнится. После этого делается две проверки: одна на проваливание блоков, а вторая проверяет, сможет ли пользователь расположить блок в нужную позицию.
И если одна из проверок не проходит, перегенерируем карту по новой. Я согласен что это затратный способ, но его можно было бы оптимизировать, если бы он был работоспособнее.
Буду рад ярким мыслям и идеям, как ещё можно генерировать блоки.
Если все-таки имеется в виду разбиение поля на фигуры тетриса, то я с успехом применял такой алгоритм:
1. Разбиваем поле на фигуры нужного размера (для тетриса и поля с четными сторонами - просто квадраты 2х2)
2. Отрываем у одной из фигур одну клетку.
3. Обходим всех ее соседей и выбираем, какие клетки она может у них позаимствовать, не разорвав тем самым на две части.
4. Выбираем одну из таких клеток, дополняем эту фигуру и возвращаемся на п. 3 для той, которая после отрыва клетки стала ущербной, пока через какое-то время в соседях очередной ущербной фигуры не окажется та самая оторванная в п. 2 клетка.
5. Тогда проверяем энтропию полученных фигур (достаточно ли они разнообразны), и если результат пока не устраивает - продолжаем отрывать или присоединяем оторванную и возвращаемся в п. 2.
Алгоритм должен успешно работать на любом количестве клеток фигуры, изначальную разбивку стоит делать фигурами "покруглее", не полосками.
