Вопрос по разработке игр для Android (программирование / алгоритм)

Question

У меня есть куча объектов (воздушных шаров), которые движутся вверх, попадают на крышу (то есть object.yPos <= 0) и останавливаются.Воздушные шары, которые следуют за ними, ударяют о существующие воздушные шары и останавливаются.Теперь я стреляю по воздушным шарам и удаляю те, которые попали ... достаточно легко, если они уже находятся на дне.Тем не менее, <b>Я также должен удалить те воздушные шары, которые остались подвешенными после того, как их опорный Якорь был поражен и удален, то есть они больше не прикреплены к крыше ИЛИ ни к одному из других шаров. В связи с этим у меня есть следующие вспомогательные методы в моем объекте Balloon:

balloon.getAdjacentList () -> Возвращает ArrayList всех воздушных шаров, которые прикреплены к шару

balloon.getX () -> Возвращает X Pos воздушного шара

balloon.getY () -> Возвращает Y Pos воздушного шара

Один из способов обнаружения "зависания в воздухе" воздушного шарая могу подумать о том, чтобы использовать «обход графика» с DFS или BFS, где источником будут все смежные шары того, который был поражен (и удален), а пунктом назначения будет ... если любой из соседних шаров (или «соседнихсмежный "шар ИЛИ" смежный соседний смежный "и т. д.) имеет метод getY () <= 0, т. е. найти путь к крыше. </p>

Эта проверка кажется очень дорогой, особенно если убрать один или два висящих шараЯ должен выполнить десятки поисков.Также имейте в виду, что, теоретически, к воздушному шару может быть прикреплено много других, и при этом его Якорь (тот, который поддерживает их всех на крыше) удаляется и удаляется, и поэтому все они должны уйти ... так что ...if (getAdjacent (). size () == 0) не будет работать.

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

Заранее спасибо за любую помощь

Answer 1

Вот простой алгоритм, который, вероятно, работает достойно для ваших целей: просто начните с якоря и пометьте каждый узел, к которому вы добираетесь с якоря, как достижимый.Когда вы закончите, поп все шары, которые не были помечены как доступные.Стоимость этого будет линейной по количеству воздушных шаров плюс соединений, что, я думаю, близко к оптимальному для этой задачи (поскольку выстрел мог бы попасть в каждый воздушный шар на графике, вам, по крайней мере, нужно выполнить работу O (воздушные шары)).

Answer 2

Когда воздушный шар находит якорь, попросите его сказать, что он привязывается.Сохраняйте список закрепленных воздушных шаров на якоре. Сохраняйте список закрепленных на воздушном шаре ячеек, которые обнаружили якорь (якоря), когда якорь уходит, сообщают закрепленным на ящике воздушным шарам, что его нет.Затем вы можете использовать список якорей, чтобы определить, нужно ли вам двигаться вверх.

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

Answer 3

Почему вы просто не сказали нам, что делаете клон Frozen Bubbles ?Сделал бы вопрос короче:)

Если вы хотите избежать поиска, сделайте что-то вроде подсчета ссылок схема:

Для каждого баллона сохраните список дочерних (прикрепленных) шариков и целое число, подсчитывающее количество родительских (привязывающих) шариков .Когда шарик лопнет, просмотрите всех его детей и уменьшите их число якоря.Если после этого на баллоне ребенка не осталось родителей, вставьте его (сделайте это рекурсивно или добавьте в некоторую очередь ...)

Это должно работать, пока нет циклических зависимостей *Возможно 1016 *(Я думаю, что это так. Однако, если существуют круговые зависимости, поиск по графику - единственное решение)

---

Кстати, пробный поиск для обнаружения связанных шариков - это только O (числобаллонов).Я серьезно сомневаюсь, что в вашей игре так много шаров, что это станет настоящей проблемой.Ведь рендеринг баллонов в первую очередь должен иметь такую ​​же сложность ...