Короткая версия
Я думаю, что алгоритм поиска в глубину может помочь вам.
В вашем случае каждая плитка может рассматриваться как узел графа, и между двумя узлами существует ребро, если они имеют общую сторону или угол.
Хорошее видео, объясняющее, как работает этот алгоритм, я нашел здесь: Первый поиск по глубине на YouTube
Алгоритм DFS, вероятно, очень похож на то, что вы пытались использовать с рекурсивнымОднако основное отличие заключается в том, что вы «окрашиваете» узлы / плитки, которые вы посещаете, по мере продвижения в алгоритме.Вместо того, чтобы хранить исследуемые узлы в отдельной структуре данных, я бы посоветовал вам сделать это свойством каждой из ваших плиток.
Тогда, если вы наткнетесь на плитку, которую вы уже посетили, вы ее не исследуете.Если вы исследовали всех соседей вашего текущего узла, вы возвращаетесь к узлу, который вы исследовали непосредственно перед этим, и исследуете его соседей (рекурсивно), пока не вернетесь к узлу, с которого вы начали алгоритм.
Еще несколько подробностей, связанных с вашей конкретной проблемой
Обнаружение соседей
Вы упомянули, что ваши квадраты хранятся в ArrayList,Это отлично.Но это не мешает вам строить 2D массив квадратов, чьи ячейки равны null , если квадратов нет или они содержат ссылку на экземпляр квадрата, расположенный в этой позиции.По моему скромному мнению, это сделало бы поиск соседей намного проще, чем поиск столкновений между каждой парой квадратов (что я думаю, это то, что вы делаете сейчас).
Вам не нужно было бы использовать такой 2D-массив для чего-либо еще в вашей программе.Я вполне уверен, что это сделало бы вещи быстрее для большого количества квадратов.
Конечно, есть и другие структуры данных, которые позволяют легко искать пересечения между узлами графа.Например, вы можете создать матрицу смежности один раз и использовать ее для любых последующих вычислений, но вам не нужно это делать.
Запуск DFS на вашем примере
Я собираюсь использовать стек, чтобы отслеживать, где я нахожусь в исследовании тайлов.Я собираюсь ссылаться на типы по их координатам.Ячейка, с которой мы запускаем алгоритм, на вашем рисунке окрашена в красный цвет и имеет координаты (1,2).
Алгоритм следующий:
while (!stack.isEmpty()) {
currentTyle = stack.top();
boolean currentHasNeighborsToExplore = false;
for (n in neighbors of currentTyle) {
if (n is not explored) {
n is explored;
stack.add(n);
currentHasNeighborsToExplore = true;
break;
}
}
if (!currentHasNeighborsToExplore) {
stack.pop();
}
}
Мы запускаем алгоритм с вашего начального типа (1,2).
ШАГ 1
Стек: [(1,2)
Верх стека составляет (1,2)
(1,2) имеет соседа n: (2,2), который не исследован
(2,2), теперь исследуется, мы добавляем его в стек и делаем следующий шаг
ШАГ 2
Стек: [(1,2) (2,2)
Вершина стека составляет (2,2)
(2, 2) имеет соседа n: (1,2), который исследуется
(2,2) имеет соседа n: (3,1), который не исследован
(3,1) являетсяТеперь, изучив его, мы добавляем его в стек и делаем следующий шаг
ШАГ 3
Стек: [(1,2) (2,2) (3,1)
Вершина стека (3,1)
(3,1) имеет соседа n: (2,2), который исследуется
(3,1) имеет соседа n: (4,2), который не исследован
(4,2) теперь исследуется, мы добавляем его в стек и делаем следующий шаг
STEP4
Стек: [(1,2) (2,2) (3,1) (4,2)
Вершина стека составляет (4,2)
(4,2) имеет соседа n: (4,3), которыйch не исследован
(4,3) теперь исследуется, мы добавляем его в стек и делаем следующий шаг
STEP 5
Stack: [(1,2) (2,2) (3,1) (4,2) (4,3)
Вершина стека составляет (4,3)
(4,3) имеет соседа n: (4,2), который исследуется
(4,3) не имеет неисследованных соседей, мы извлекаем его из стека и делаем следующий шаг
ШАГ 6
Стек: [(1,2) (2,2) (3,1) (4,2)
Вершина стека равна (2,2)
(4,2) имеет соседа n: (4,3), который исследуется
(4,2) имеет соседа n: (5,1), который не исследован
(5,1), мы добавили его в стек и сделали следующий шаг
Следующие шаги
На следующем шаге (5,1)нет неисследованных соседей, он будет выталкиваться из стека, как и каждый последующий тип, поскольку не осталось неисследованных соседей.