Алгоритм выпадения элементов сетки

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

Учитывая состояние элементов в сетке слева, знает ли кто-нибудь алгоритм эффективного нахождения конечных позиций, показанных в сетке справа?В этом случае все предметы «упали» «вниз», но направление, конечно, произвольное. Дело в том, что:

• Есть набор предметов произвольной формы, но все они состоят из смежных квадратов
• . Элементы не могут перекрываться
• Все предметы должны перемещаться на максимальное расстояние в заданном направлении, пока они не коснутся стены или не коснутся другого предмета, который [...касается другого предмета до бесконечности...] касается стены.

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

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

Если вы не знаете ответа, но собираетесь попытаться составить алгоритм на месте, просто помните, что могут быть круговые зависимости, например, с переплетением розового (наоборот )"С" и синего " Т-образные формы. Части T находятся ниже C, а части C ниже T. Это было бы еще более сложно, если бы взаимосвязанные элементы были заблокированы через «петлю» из нескольких частей.

Некоторые примечания к применимому алгоритму :Все нижеследующее очень легко и быстро сделать благодаря тому, как я построил структуру управления объектами сетки:

• Перечислите отдельные квадраты внутри куска
• Перечислить все части
• Найдите фигуру, если она есть, занимающую определенную клетку в общей сетке

Примечание к ответу: maniek первым намекнул на это, но bloops дал блестящее объяснение. Я думаю, что абсолютным ключом является понимание того, что все части, перемещающиеся на одинаковую величину, сохраняют свои отношения друг с другом,и поэтому эти отношения не должны рассматриваться .

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

Последнее примечание:На самом деле я реализовал алгоритм, описанный ляпами, с некоторыми модификациями -, специфичными для реализации. Это прекрасно работает.