Java обучения лабиринтом решатель

Question

Я работаю на некоторый код, чтобы вести «робот» через лабиринт с множеством тупиков и 1 правильный путь к цели, как это:

Я использовал стек, чтобы записать направление, с которым робот сталкивается в первый раз, когда он достигает квадрата с 3 или 4 возможными выходами, и если все соседние квадраты уже были посещены, используется pop(), чтобы заставить робота вернуться с того направления, в котором он впервые появился (напротив к направлению прибыл). В конце выполнения стек содержит направление, полученное на всех квадратах по маршруту до цели. Следуя противоположным направлениям стека, робот от цели вернется к начальной точке. Я изо всех сил пытаюсь выяснить, как использовать этот стек, чтобы на следующем запуске робот получал оптимальный путь для достижения цели.

Некоторые из моего кода:

private int pollRun = 0; // Incremented after each pass 
private int explorerMode; // 1 = explore, 0 = backtrack 

public void exploreControl(IRobot robot) { 

    byte exits = nonwallExits(robot); 
    int direction; 

    switch (exits) { //passes control to respective method 
    case 1: direction = deadEnd(robot); break; 
    case 2: direction = corridor(robot); break; 
    case 3: direction = junction(robot); break; 
    default: direction = crossroads(robot); break; 
    } 

    if (exits == 1) {explorerMode = 0;} 

    robot.face(direction); 

    pollRun++; 

} 

public void backtrackControl(IRobot robot) { 

    byte exits = nonwallExits(robot); 
    int direction = IRobot.CENTRE; 

    switch (exits) { //passes control to respective method 
    case 1: direction = deadEnd(robot); break; 
    case 2: direction = corridor(robot); break; 
    default: direction = junction(robot); break; // do nothing 
    } 

    if (exits > 2) { 
    if (passageExits(robot) > 0){ 
     exploreControl(robot); 
     explorerMode = 1; 
     pollRun++; 
     return; 
    } else { 
     robot.setHeading(st.pop()); 
     robot.face(IRobot.BEHIND); 
     pollRun++; 
     return; 
    } 

    } 

    robot.face(direction); 

    pollRun++; 

} 

public void optimal(IRobot robot) { 

    byte exits = nonwallExits(robot); 
    int direction; 
    int heading; 

    for(int i = 0; i < st.size(); i++) { 
    stNew.push(st.pop()); 
    } 

    if (exits < 3) { 

    switch (exits) { //passes control to respective method 
     case 1: direction = deadEnd(robot); break; 
     default: direction = corridor(robot); break; 
    } 

    robot.face(direction); 

    } else { 
    robot.setHeading(stNew.pop()); 
    } 

} 

public void controlRobot(IRobot robot) { 

    if ((robot.getRuns() == 0) && (pollRun == 0)) { 
    robotData = new RobotData(); //reset the data store 
    explorerMode = 1; 
    } 

    if (robot.getRuns() = 1) { 
    optimal(robot); 
    return; 
    } 

    if (robot.getRuns() <= 0 && (nonwallExits(robot) >= 3) 
     && (beenbeforeExits(robot) <= 0)) { 
    st.push(robot.getHeading()); 
    } 

    if (explorerMode == 1) { 
    exploreControl(robot); 
    } else {backtrackControl(robot);} 

} 

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

Например, этот лабиринт,

оставить бы меня со стеком: ИСТ, восток, юг, юг, восток, юг, юг, восток, восток, юг, юг, восток , EAST, EAST, SOUTH, EAST, SOUTH

Answer 1

Это правда, что эту проблему можно решить, используя стек и исчерпывающий поиск лабиринта. Есть более эффективные методы, но этот будет работать.

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

Вот несколько примеров кода psuedo для исчерпывающего поиска по глубине. Этот код будет содержать все возможные решения, а не только один. У вас должен быть метод, который выглядит примерно так в вашем коде.

void findPath(Stack currentPath) { 
    if (currentPath.peek() == goal) { 
     solutions.add(currentPath); 
    } else { 
     for (Position next: currentPath.openPositions()) { 
      currentPath.push(next); 
      findPath(currentPath); 
      currentPath.pop(); 
     } 
    } 
} 

Метод «openPositions» должен явно остановить любое удвоение назад, глядя на текущем пути - другими словами, он не должен возвращать никаких позиций, которые уже находятся в стеке currentPath или вы будете в конечном итоге с бесконечным рекурсии.

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

Заключительное примечание: вы попытались смешать задачу установки направления, которое робот должен будет включить, с задачей найти путь через лабиринт. Я рекомендую хранить их отдельно. Используйте вышеприведенный алгоритм, чтобы найти путь (или более эффективный, такой как *), а затем, когда вы пройдете через него пути, чтобы определить список направлений для робота.