У меня сейчас простая тетрис-подобная игра, и я столкнулся с проблемой, которую не могу решить.
В отличие от тетриса, где есть одна падающая фигура, у меня есть несколько потенциально взаимосвязанных фигур, которые должны упасть; Мне нужно рассчитать свои окончательные позиции. Учтите следующее:
Чтобы вычислить конечную позицию зеленой фигуры, я просто сканирую каждый квадрат, пока не достигну другого квадрата или края доски. Выполнено
Для нескольких простых форм я работаю по доске. Таким образом, красный не нуждается в движении, оранжевый падает на единицу, зеленый - на три. Выполнено
Я не знаю, как обращаться со связанными зелеными и красными фигурами. Используя логику # 2, мы в конечном итоге «застряли» в воздухе. Если я смотрю вниз на зеленую фигуру, я сталкиваюсь с красным и, следовательно, не двигаюсь, и наоборот для красного. Решение может заключаться в том, чтобы рассматривать две фигуры как одну.
Подобно # 3, в этом сценарии я также мог бы преуспеть, рассматривая объекты как единое целое.
В отличие от № 3 и № 4, я не мог воспринимать форму как единое целое, поскольку оранжевая фигура в конечном итоге всплыла бы на один квадрат слишком высоко ...
Еще один вариант проблемы № 6.
Могут быть и другие сценарии, в которых у меня есть множество форм, которые переплетаются в более сложных сценариях, но я думаю, что вышеизложенное охватывает наиболее фундаментальные части проблемы.
Я чувствую, что есть элегантное решение, с которым мне еще предстоит столкнуться / придумать, и буду очень признателен за любые идеи, идеи или ресурсы.
РЕШЕНИЕ
Решение, которое я придумала, действительно элегантное, основываясь на ответе @ user35958 ниже, я создал следующую рекурсивную функцию (псевдокод)
function stop(square1, square2){
// Skip if we're already stopped
if(square1.stopped){
return;
}
// Are we comparing squares?
if(!square2){
// We are NOT comparing squares, simply stop.
square1.stopped = true;
} else {
// Stop IF
// square1 is directly above square2
// square1 is connected to square2 (part of the same complex shape)
if(square1.x == square2.x && square1.y == (square2.y+1) || isConnected(square1, square2)){
square1.stopped = true;
}
}
// If we're now stopped, we must recurse to our neighbours
stop(square1, squareAbove);
stop(square1, squareBelow);
stop(square1, squareRight);
stop(square1, squareDown);
}
Анимированный GIF, показывающий каждый проход решения
Чтобы обобщить:
- При «остановке» квадрата мы также останавливаемся:
- ЛЮБОЙ квадрат над ним. ВСЕГДА.
- Соседний квадрат, к которому мы подключены (т.е. той же формы).
- Мы останавливаем весь нижний ряд, и функция повторяется через квадраты.
- Мы повторяем, пока все квадраты не останавливаются.
- Тогда мы оживляем.
источник
Ответы:
Ну, вам точно не нужно относиться к фигурам как к одному, если есть различие между фигурами, которые движутся, и фигурами, которые находятся в покое. Форма (A) может обнаружить форму (B) непосредственно под ней, и если она движется, то форма B может затем увидеть, есть ли что-нибудь непосредственно под ней, и если есть фигура в состоянии покоя, то A и B теперь отдыхают, и если ничего нет, они оба двигаются вниз, но если есть движущаяся фигура, то эта новая фигура будет обрабатываться A и B как A, а B - рекурсивно. Имейте в виду, что для каждого шага самые низкие фигуры должны сначала проверять фигуры под ними.
Итак, для задачи № 6 зеленая фигура является самой низкой движущейся формой, и она увидит, что единственная фигура, которая находится непосредственно под ней, это красная фигура, поэтому красная фигура ничего не обнаружит непосредственно под ней, и они будут двигаться вниз , Как только зеленая фигура будет смежна с оранжевой, она будет отдыхать, а красная будет двигаться вниз, а затем обнаружит покоящуюся зеленую форму, и она тоже будет отдыхать.
источник
Кажется, что проблема в случаях № 5 и № 6 проистекает из одного корня: вы выполняете только один проход проверок движения. Вы должны продолжать двигать вещи вниз (давайте назовем это «проходом гравитации»), пока вы не узнаете, что ничего не двигалось.
Например, в случае 6 это произойдет, если вы использовали несколько проходов:
Эта стратегия множественных проходов гравитации также может решить проблему № 5, хотя она не поможет в случаях № 3 и № 4, где, по-видимому, вам нужно рассматривать их как одно целое.
Чтобы различать, когда два или более фрагментов следует рассматривать как один фрагмент, я думаю, что самый простой алгоритм - это проверить, есть ли какие-либо «дыры» в объединенном пространстве всех фрагментов. Если есть, это можно рассматривать как несколько частей.
источник