Java ищет массив для повторения шаблона

Question

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

редактировать для ясности, http://www.logicmazes.com/theseus.html лабиринт три - это тот, который я тестирую. получается, что он застревает, двигаясь вверх и вниз в столбце, в котором он начинается.

Answer 1

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

Что касается структуры данных, я вижу две основные возможности:

• сохранить массив - или набор - координат, которые вы посетили; или
• имеет логический массив тех же размеров, что и лабиринт, устанавливая посещенные ячейки на true.

Answer 2

Похоже, проблема в том, что ваше "состояние" на самом деле не содержит достаточно информации о состоянии.В каждом цикле после перемещения Тесея и перемещения Минотавра дважды состояние состоит из следующего:

• x-координата Тесея.
• y-координата Тесея.
• Минотавр по x-координате.
• Минотавр по y-координате.

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

Поскольку движение Минотавра следует очень жесткой программе, каждое движение, которое совершает Тесей (влево / вправо / вверх / вниз / задержка), будет перемещаться из одногочетко определенное состояние для другого.Затем вам нужно запретить Тесею совершать любые действия, которые:

• приведут к тому, что координаты Минотавра по x и y равны координатам Тесея (поскольку это означает, что Тесей мертв).
• Приведет к тому, что новое состояние будет равным состоянию, в котором вы были ранее (поскольку это означает, что никакого прогресса не было сделано).

Для этого вы можете сохранить предыдущие состоянияв HashSet<MazeState>.

Answer 3

Если вы используете массив, то вы должны иметь возможность использовать метод «содержит», чтобы проверить, находится ли перемещение уже в массиве.

Для этого вам, возможно, придется изменить метод равенства, чтобы сравнить два разных хода, чтобы проверить, совпадают ли они.

В этом случае, когда вы идентифицируете тот же ход, вы можете игнорировать это и искать другие ходы. Пример псевдокода

public class Move {
  int x;
  int y;

  public boolean equals(Object o){
    if(o == null) return false;
    if(!(o instanceof) Move) return false;

    Move other = (Move) o;
    if(this.x != other.x) return false;
    if(this.y != other.y)   return false;

    return true;
  }
}

public class SolveMaze {
    List<Move> moves;
    ...
    public boolean isValidMove(Move move) {
        if (moves.contains(move)) return false;
        else {
            ...
                moves.add(move);
        }
    }
}