Попиксельные разрушения

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

     Пожалуй, самый известнейший пример использования такого вида разрушения это серия игр Worms.

     "Ice & Flora" - это попытка создать арканоид с попиксельними разрушениями. 

     Одной из проблем попиксельных разрушений является то, что пиксель - слишком маленький интерактивный элемент. Отдельно расположенные в пустоте пиксели не создаю красивой картины и вызывают неприятные физические последствия. В Worms небольшие огрызки мешают пролетанию снаряда, в Ice & Flora маленькие незаметные кусочки могли бы непредсказуемо отклонять мяч, и по ним бы было сложнее попасть целенаправленно. Только достаточно большая связная группа пикселей может восприниматься игроком.

     Возможно, для разработчиков Worms эта проблема показалась не существенной, или это такая фича, поэтому она прослеживалась во всех частях. Но я не мог смириться с этим в   Ice & Flora и сейчас опишу алгоритм, который мне помог. Возможно это не самый лучший алгоритм, в таком случае я рад буду прочитать ваши версии и предложения.

Рис. 1

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

     Итак, наша цель создать круглое разрушение с центром в данной точке и радиусом R, представим этот круг. Замыслим дополнительный круг радиуса R2 > R концентрический с первым. Небольшой квадратный участок, который мы рассматриваем и в котором умещаются оба круга должен быть лишь немного больше большего круга. (Рис.2.)

Рис. 2

     Отметим все точки достижимые из центра разрушения по тверди как "связные". На (Рис. 3) можно видеть их жёлтым цветом. Есть необходимость искать связные точки только внутри рассматриваемого квадрата.

     На данном этапе можно добавить условие на свойства материалов, для того чтобы сделать некоторые пиксели неразрушимыми. Для этого надо не отмечать пиксели неразрушимого материала как будто они относятся к сквозному пространству. Стоит заметить, что неразрушимые части картины на фоне попиксельных разрушений остальной части выглядят весьма интересно. Данный приём также используется в Ice & Flora.

     В Worms проверка на связность отсутствует, что конечно не может не печалить.

Рис. 3

     Далее нужно пройтись по всем точкам квадрата не лежащим внутри кругов и из тех из них которые "связные" произвести поиск на все достижимые точки лежащие вне круга радиуса R и отметить их как "часть чего-то большего". На Рис. 4 все такие точки обозначены оранжевым цветом. 

Рис 4.

     Далее уничтожаем все "связные" пиксели не являющиеся "частью чего-то большего", на Рис 4. эти пиксели остались закрашены жёлтым цветом. Получаем результат. На Рис. 5 можно видеть сравнение обычного разрушения связных пикселей попавших в радиус R (слева) и разрушение по рассматриваемому алгоритму (справа).

Рис. 5

     На рисунке слева осталась неразрушенной небольшая группа пикселей, на рисунке справа нам удалось этого избежать. Разрушение захватило их, несмотря на то, что они не входили в круг разрушения радиуса R. Таким образом, данный алгоритм рассматривает пиксели не входящие в круг разрушения радиуса R, но входящие в круг радиуса R2 как потенциально подлежащие разрушению, и разрушает их, если они не являются "частью чего-то большего". То насколько R2 большее R есть диаметр минимально допустимой области. Например,  r = R2 - R = 20пикселей  означает, что минимальные кусочки, оставшиеся после разрушений, не смогут быть меньше чем 20 пикселей между самыми дальними точками.