Имея список комнат с их связью друг с другом, как мне найти отдельные группы комнат?

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

Я могу выделить комнаты, не связанные между собой, но как узнать, какие комнаты связаны только друг с другом, но не с большинством других, образуя остров?

Чтобы проиллюстрировать лучше, проблема здесь - изображение с консоли на заболоченном уровне. Номера 5 и 6 связаны только друг с другом. Какой алгоритм я могу использовать, чтобы обнаружить это?

введите описание изображения здесь

java algorithm petervaz
источник

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

MichaelHouse

Да, я сначала не совсем понял, что ты здесь сделал. Извините, я отменил ваши изменения.

petervaz

Почему бы вам не сконструировать его так, чтобы в первую очередь не было отдельных комнат? Или вы хотите, чтобы там были изолированные множества?

AlbeyAmakiir

@AlbeyAmakiir, как я уже сказал в другом комментарии ниже, я генерирую комнаты отдельно методом проб и ошибок до тех пор, пока не заполню карту, только затем запускаю процедуру для подключения, а затем запускаю другую для подключения этих островов. Я знаю, что это, вероятно, слишком запутанный, но не мог придумать другого пути.

petervaz

Ответы:

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

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

Такие проблемы легко адаптируются к задачам теории графов. Например, проблема, которую вы описали выше, напрямую связана с подключением .

MichaelHouse
источник

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

Бенджамин Дэнджер Джонсон

Это очень логично. Я должен быть уставшим. Спасибо за вашу помощь. Примут, как только это позволит.

petervaz

@BenjaminDangerJohnson Ваш комментарий кажется более подходящим для вопроса, а не для этого ответа.

MichaelHouse

@petervaz Нет проблем. Я думаю, что моя степень CS имеет свои применения в конце концов.

MichaelHouse

@BenjaminDangerJohnson Мой алгоритм генерации состоит в том, чтобы просто размещать случайные комнаты, пока они не заполнят пространство, и не искать соединения позже. = P Постараюсь исправить соединения, прежде чем прибегать к изменению создания.

petervaz

Ваша коллекция комнат - это, по сути, график, и ваша проблема сводится к поиску связанных компонентов («островков») в этом графике.

Простой способ найти связанные компоненты - выполнить BFS (поиск в ширину) из каждой вершины. Выполнение BFS из вершины A даст вам все вершины в связанном компоненте, которому принадлежит вершина A.

Итак, в основном вы начинаете с произвольной вершины, делаете BFS и помечаете каждую встреченную вершину как член 1-го «острова». Затем вы переходите к следующей немаркированной вершине и снова делаете BFS, на этот раз помечая встреченные вершины как членов 2-го «острова», и так далее.

источник

Вы можете изобразить комнаты как вершины на ориентированном графе . Сделав это, вы сможете применять хорошо известные алгоритмы для решения вашей проблемы.

Алгоритм Дейкстры , например, создает дерево кратчайших путей для заданной начальной вершины графа. Это дерево будет содержать все достижимые вершины из начальной точки. Затем вы можете сделать вывод, что вершины, отсутствующие в дереве, являются частью других островов. Вы можете применить алгоритм к этим вершинам, чтобы получить деревья, представляющие каждый остров.

Asakeron
источник

Даже неориентированный граф сделает это ... за исключением того, что у вас есть только односторонние маршруты.

Aron_dc

@Aron_dc, вы правы, вы можете изобразить комнаты как вершины на неориентированном графе и получить аналогичные результаты, используя алгоритм Крускала. Я просто предложил изобразить его в виде ориентированных графов из-за того, как petervaz представлял связи - т.е. Комната 1> 3

Asakeron