Как роботу выбраться из лабиринта?

Question

Как роботу выбраться из лабиринта?

Константин Гуру (3153), закрыт 14 лет назад

Робот стоит в коридоре лабиринта. роботу задают какую-либо цель: точку находящуюся на несколько клеток ниже и правее (например). Помогите, пожалуйста, какой должен быть алгоритм примерно? проблема заключается в том что я не знаю как его вывести если он попал в угол (то есть цель находится ниже и правее а справа и снизу от него стена) что делать в этом случае?

Начало алгоритма выглядит так:
если цель ниже и снизу нет стены то сделать шаг вниз
иначе
если цель правее и справа нет стены то сделать шаг вправо
иначе

Answer 1

построй граф лабиринта, и обходи его. алгоритмов обхода графа куча, ищи в инете

Answer 2

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

Answer 3

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

Answer 4

Самый простой алгоритм - рекурсивный обход лабиринта до достижения нужной точки.
Примерно так:
Процедура "обход":
- Если искомая точка достигнута - конец.
- Отметить точку, где стоим.
- Если можно идти вправо и точка справа не отмечена, то идти вправо и выполнить "обход". Вернуться влево.
- Если можно идти влево и точка слква не отмечена, то идти влево и выполнить "обход". Вернуться вправо.
- Аналогично для направлений верх и низ.

Все.