Есть 2х мерная сетка, описывающая локацию. Есть начальная и конечные точки, и радиус в котором клетки считаются посещёнными. Собственно нужно пройти из начальной точки в конечную, исследовав определенный минимальный процент клеток, при этом минимизировать повторное посещение клеток (возможны тупики, при которых в любом случае придётся возвращаться). Во время движения возможно отхождение от изначального пути, поэтому, скорее всего, не получится всё просчитать заранее. Думал попробовать подкрутить A* под задачу, но не факт что получится, и возможно есть варианты получше.
Я правильно понял, что есть ограничение, что надо пройти не меньше заданного количество вершин? При этом найти минимальный из возможных путь? Что за радиус? Т.е. надо найти минимальный путь, что не менее K клеток лежат от него на расстоянии не более r?
Как у вас препятствия на карте - стены между соседними клетками, или некоторые клетки посещать нельзя? Соседей 4 или 8 (можно ли ходить по диагонали)?
Илья Николаевский, Да, надо "посетить" не менее определенного числа клеток. По радиусу, при прохождении через клетку, 8 соседних клеток считаются посещенными, можно сказать это обзор/радиус видимости. Все клетки проходимы, но не у каждой клетки есть 8 соседних. По диагонали ходить можно.
Простой
