Алгоритм для отображения закрытого лабиринта и помнить, как он выглядит в будущем.

Question

Я работаю над проектом, в котором у меня будет агент в случайном лабиринте, и у этого лабиринта нет выхода. Цель будет заключаться в том, чтобы агент исследовал лабиринт и «помнил», как он выглядит. Через некоторое время я создам элемент в случайном месте, и агент будет уведомлен только в том случае, если он наметил эту область. Агент будет использовать созданную карту для определения кратчайшего пути к элементу.

Я знаю алгоритмы лабиринта, такие как A *, но для этих алгоритмов требуется, чтобы начальное и конечное положение остановилось. Эти алгоритмы не «запоминают», как выглядит лабиринт, они определяют самый короткий путь между двумя точками. Поскольку лабиринт закрыт, конечная позиция отсутствует. Моя первоначальная идея заключалась в том, чтобы агент перемещался случайным образом и заполнял 2D-массив того, как выглядит карта, это просто кажется мне неэффективным. Любые идеи были бы замечательными.

Answer 1

Итак, у вас будет два шага, исследование и пересечение.

Предположим, что вы полностью изучили лабиринт, а затем, когда элемент появляется, вы можете просто использовать A *, а цель - элемент.

Чтобы изучить карту и сохранить ее, вы можете создать структуру данных, соответствующую карте. Например, если пути подключения не имеют значения, и только конъюнкции, то просто создайте класс Node, где каждый узел имеет список подключенных узлов. Наконец, вы можете начать поиск по ширине или поиск по глубине, чтобы исследовать всю карту, сохраняя информацию в вышеупомянутой структуре данных.

В зависимости от реальной карты алгоритмы исследования могут быть более эффективными. Сначала я начинал с глубины - хотя это звучит похоже на наш человеческий подход к лабиринтам - всегда поворачивайтесь в одном направлении на перекрестке! (Хорошо, что dfs заботится о круговых дорожках!)