Мне нужно запрограммировать алгоритм для навигации робота через «лабиринт» (прямоугольную сетку с отправной точкой, целью, пустыми пространствами и не проходимыми пространствами или «стенами»).Он может двигаться в любом кардинальном направлении (N, NW, W, SW, S, SE, E, NE) с постоянной стоимостью за ход.
Проблема в том, что робот не «знает» расположение карты.Он может только просматривать свои 8 окружающих пространств и сохранять их (он запоминает окружающие плитки каждого пространства, которое он посещает).Единственный другой вход - это основное направление, в котором цель находится на каждом шаге.
Есть ли какой-нибудь исследовательский алгоритм, который я мог бы реализовать, чтобы решить эту проблему?Типичные, такие как Dijkstra или A *, не просто адаптированы к задаче, так как я не могу вернуться к повторному посещению предыдущих узлов на графике без затрат (пересмотр шагов робота для перехода к лучшему пути будет стоить ходов).снова), и не могу придумать способ сделать разумную эвристику для A *.
Я, вероятно, мог бы придумать что-нибудь разумное, но я просто хотел знать, была ли это уже решенная проблема, иМне не нужно изобретать велосипед: P
Спасибо за любые советы!