Как роботу выбраться из лабиринта?
Робот стоит в коридоре лабиринта. роботу задают какую-либо цель: точку находящуюся на несколько клеток ниже и правее (например). Помогите, пожалуйста, какой должен быть алгоритм примерно? проблема заключается в том что я не знаю как его вывести если он попал в угол (то есть цель находится ниже и правее а справа и снизу от него стена) что делать в этом случае?
Начало алгоритма выглядит так:
если цель ниже и снизу нет стены то сделать шаг вниз
иначе
если цель правее и справа нет стены то сделать шаг вправо
иначе
построй граф лабиринта, и обходи его. алгоритмов обхода графа куча, ищи в инете
Самый простой алгоритм - рекурсивный обход лабиринта до достижения нужной точки.
Примерно так:
Процедура "обход":
- Если искомая точка достигнута - конец.
- Отметить точку, где стоим.
- Если можно идти вправо и точка справа не отмечена, то идти вправо и выполнить "обход". Вернуться влево.
- Если можно идти влево и точка слква не отмечена, то идти влево и выполнить "обход". Вернуться вправо.
- Аналогично для направлений верх и низ.
Все.
Робот не должен стремиться к цели.
Робот должен обходить лабиринт по правилу правой либо левой руки (с определением циклов, если лабиринт предусматривает их наличие) , пока не достигнет цели или не обойдет весь лабиринт (цель недоступна с текущей позиции) .
Алгоритмы, учитывающие местоположение цели, очень сложны и в общем случае не гарантируют успеха.
Следует загрузить карту лабиринта в память робота, на той карте должна быть обозначена точка. Иначе придется писать искусственный интеллект, который будет тупо кататься и искать. Кстати, на счет тупо искать. Пусть он у тебя пройденный путь запоминает, заставь его считать пройденное расстояние, угол поворота и прочее, чтобы все это записывалось в память и на этой основе строилась карта пройденного пути, так исключишь прохождение одного и того же пути без надобности. А алгоритм немного не будет работать я так думаю...