Отслеживание столкновения пикселей

Question

У меня есть персонаж, скажем, размером 20 на 10 пикселей, и у меня есть карта столкновений, основанная на пикселях (думаю, черви).

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

Я делаю это в Lua (Love 2D), но универсальное решение было бы идеальным.

Answer 1

Я бы объединил столкновение ограничивающего прямоугольника и столкновение совершенства пикселей.

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

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

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

придумать битовую маску для каждого спрайта (например, карту пикселей, но только один бит на пиксель), например:

00000000
00100000
01100000
01110000

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

Как только это будет сделано, поразрядно 'и' все байты в этих двух масках.Если какой-либо байтовый результат> 0, вы столкнулись.

Answer 2

Ваше решение самое простое - переберите каждый пиксель.

Просто убедитесь, что вы проверяете только «новые» пиксели на каждой итерации.

Скажите, что персонаж движется вправо и вниз одновременно:

*****   .....       .....        * = "Present"
*****   .*****      .****#       . = "Old and now empty"
*****   .*****  =>  .****#        # = "New"; check these on iteration 2
*****   .*****      .****#
         *****       #####

It. 1   It. 2      "New" pixels

На каждой итерации вдоль движения есть небольшая разница в проверяемых пикселях; только те, которые отмечены как «новые», нуждаются в проверке на воздействие. Проверьте их, и если нет столкновения, продолжайте движение. Вы можете использовать это, чтобы оптимизировать множество вычислений.