Решение лабиринта следования за стеной

У меня проблемы с алгоритмом решения лабиринта. Я пытаюсь реализовать правило левой руки.

public Direction move(View v) {
    if (!wallExistsToLeft(v)) {
        turnLeft();
    } else if (v.mayMove(direction)) {
        return direction;
    } else if (!wallExistsToRight(v)){
        turnRight();
    } else {
        turnAround();
    }
    return direction;
}

Направление всегда устанавливается равным текущему направлению, в котором находится решатель лабиринта.

TurnX меняет направление в зависимости от направления, в котором вы сейчас находитесь

Функция перемещения возвращает направление, в котором решатель лабиринта перемещается на 1 позицию в этом направлении.

Может кто-то указать мне верное направление? Я уверен, что есть какой-то простой рекурсивный способ, которым это можно реализовать, но я не могу его решить.

В настоящее время я терплю неудачу в этих двух тестах:

введите здесь описание изображения

Любая помощь будет принята с благодарностью.


java algorithm maze
person Michael Doyle    schedule 19.03.2011    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Судя по твоим фотографиям, ты всегда поворачиваешь направо.

Что, согласно вашему коду, указывает на то, что wallExistsToLeft(v) всегда возвращает true, а v.mayMove(direction) всегда возвращает false.

person mbeckish    schedule 19.03.2011

arrow_upward
0
arrow_downward

правило левой руки применимо только в том случае, если начало и цель находятся рядом с сегментами стены одного и того же связного компонента стен. Если в середине комнаты есть столб, и вы начинаете рядом с ним, вы всегда будете ходить вокруг него. вторая проблема исходит от открытых пространств. Если нет стены, за которую можно было бы цепляться, алгоритм всегда будет ходить по кругу. Обычно при предложении этого алгоритма думают об узких коридорах. Таким образом, независимо от того, верна ли ваша реализация, тестовые случаи не могут быть пройдены простым правилом левой руки.

person example    schedule 15.05.2014