Я попытался написать алгоритм поиска в глубину для решения лабиринта. Это то, что у меня есть до сих пор. Я постарался добавить как можно больше деталей, чтобы логика была понятна:
//Upgraded dfs algorithm that creates an array of nodeclass objects
package depthfirstsearch;
public class DepthFirstSearch {
public static void main(String[] args) {
int[][] stateArr =
{
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 2, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0},
{0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0},
{0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0},
{0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0},
{0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0},
{0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0},
{0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0},
{0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0},
{0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0},
{0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0},
{0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0},
{0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
//Maze array declaration
int mazeRows = stateArr.length;
int mazeCols = stateArr[0].length;
//Creates an array of NodeClass objects
NodeClass[][] mazeArr = new NodeClass[mazeRows][mazeCols];
//Assigning values to the nodes (state, isPath, coords)
for(int i = 0; i < mazeRows; i++)
{
for(int j = 0; j < mazeCols; j++)
{
int state = stateArr[i][j];
mazeArr[i][j] = new NodeClass(i, j, state); //Assigning coordinates & state (wall, path) to the node
} //End of col for-loop
} //End of row for-loop
//Currently have an array of nodes with coordinates, state and isPath = false
NodeClass currentNode = mazeArr[1][1]; //This is the node we'll be working with. Assigned the value of the starting node at position (1;1)
while(currentNode.getState() != 3) //3 Indicates the end of the maze. While we haven't reached the end
{
//Getting the position of the current node
int row = currentNode.getNodeRow();
int col = currentNode.getNodeCol();
System.out.println("Run");
System.out.println(currentNode);
//We'll be taking the currentNode and checking every unchecked adjacent node:
//Check up
if ((mazeArr[row-1][col].getState() == 1 || mazeArr[row-1][col].getState() == 3) && (mazeArr[row-1][col].haveTried() == false))
{
//Storing the parent node:
NodeClass temp = currentNode; //Stores the current node as the node temp
mazeArr[row-1][col].setParentNode(temp); //Stores the current node as the parent node the new checked node
mazeArr[row][col].setTried(true); //Sets the current node as tried
mazeArr[row][col].setIsPath(true); //Considers the current node as a potential path
currentNode = mazeArr[row-1][col]; //The new current node is the node above the original node
System.out.println("Up"); //We moved up
}
//Check right
else if ((mazeArr[row][col+1].getState() == 1 || mazeArr[row][col+1].getState() == 3) && (mazeArr[row][col+1].haveTried() == false))
{
//Storing the parent node:
NodeClass temp = currentNode; //Stores the current node as the node temp
mazeArr[row-1][col].setParentNode(temp); //Stores the current node as the parent node the new checked node
mazeArr[row][col].setTried(true); //Sets the current node as tried
mazeArr[row][col].setIsPath(true); //Considers the current node as a potential path
currentNode = mazeArr[row][col+1]; //The new current node is the node above the original node
System.out.println("Right"); //We moved right
}
//Check down
else if ((mazeArr[row-1][col].getState() == 1 || mazeArr[row-1][col].getState() == 3) && (mazeArr[row-1][col].haveTried() == false))
{
//Storing the parent node:
NodeClass temp = currentNode; //Stores the current node as the node temp
mazeArr[row-1][col].setParentNode(temp); //Stores the current node as the parent node the new checked node
mazeArr[row][col].setTried(true); //Sets the current node as tried
mazeArr[row][col].setIsPath(true); //Considers the current node as a potential path
currentNode = mazeArr[row][col+1]; //The new current node is the node above the original node
System.out.println("Down"); //We moved down
}
//Check left
else if ((mazeArr[row][col-1].getState() == 1 || mazeArr[row][col-1].getState() == 3) && (mazeArr[row][col-1].haveTried() == false))
{
//Storing the parent node:
NodeClass temp = currentNode; //Stores the current node as the node temp
mazeArr[row-1][col].setParentNode(temp); //Stores the current node as the parent node the new checked node
mazeArr[row][col].setTried(true); //Sets the current node as tried
mazeArr[row][col].setIsPath(true); //Considers the current node as a potential path
currentNode = mazeArr[row][col+1]; //The new current node is the node above the original node
System.out.println("Left"); //We moved left
}
//If there are no paths left: we reached a dead end and need to back track
else
{
mazeArr[row][col].setTried(true); //Sets the current node as tried
mazeArr[row][col].setIsPath(false); //Since it's a dead end, we remove it from the potential solution
currentNode = mazeArr[row][col].getParentNode(); //Sets the current node as the previous node
}
} //End of while-loop for fining the solution
System.out.println("Yay yay, we did it!");
} //End of main method
} //End of DepthFirstSearch Class
Проблема в том, что я получаю сообщение об ошибке: Исключение в потоке «main» java.lang.NullPointerException: невозможно вызвать «Deepfirstsearch.NodeClass.getState()», поскольку «currentNode» имеет значение NULL.
Я распечатал узел currentNode, но обнаружил, что на самом деле он не равен нулю. В чем может быть проблема? Буду признателен за любые советы. Спасибо.
Вопросы этого типа должны включать трассировку стека. Но вас может заинтересовать этот вопрос и ответы на него: stackoverflow.com/questions/3988788/… . Надеюсь, это поможет вам решить проблему самостоятельно.
Мне очень жаль, я не знал, что вам пришлось выбрать ответ как принятый. Спасибо за подсказку, теперь обязательно так и сделаю. Кроме того, первый пост был давно, я, должно быть, забыл о нем.
Вам не обязательно помечать ответ как принятый, но некоторая обратная связь похожа на то, что хотел бы получить тот, кто публикует ответ. Как бы вы себя почувствовали, если бы потратили время на написание ответа, а всем плевать? Но я вижу, что вы сейчас отвечаете ;-)
Да, справедливое замечание. Я понимаю, что было бы обидно приложить усилия для написания ответа и не получить подтверждения. В будущем я постараюсь быть более внимательным и оставлять отзывы или выражать благодарность тем, кто нашел время, чтобы помочь. Спасибо, что указали на это.
код проверяет if ((mazeArr[row-1][col]...
, но затем currentNode = mazeArr[row][col+1];
(проверка вниз, но назначение вправо) -- аналогично проверке влево, но назначение вправо -- mazeArr[row-1][col].setParentNode
неверно для всех, кроме первого (вверх) -- типичные ошибки копирования и вставки (и своего рода частое повторение кода)
также вообще нет проверок ограничений... если данные лабиринта неверны, код может/выдаст исключение IndexOutOfBoundsException
Во-первых, вы выполняете отладку не в том месте. Ошибка возникает в условии while
, поэтому, если вы хотите увидеть, что currentNode
равно null
, вы должны напечатать ее непосредственно перед оценкой этого условия, то есть в самом конце тела цикла.
Непосредственная причина в том, что getParentNode()
возвращает null
на первой итерации цикла. Это странно, потому что эта часть кода — последний блок else
— не должна выполняться на такой ранней стадии процесса поиска. И да, родителя нет, когда вы начинаете поиск только с самого первого узла по координате 1, 1.
Настоящая причина заключается в том, что ваши блоки кода, работающие с четырьмя разными соседями, содержат несколько ошибок. Существует смесь row-1
, row+1
, col-1
и col+1
, которая не имеет смысла. Только первый блок (для движения вверх) правильный, все остальные имеют несоответствия, а блок для спуска самый худший: ни одна из ссылок на соседей не указывает на соседа вниз! Когда вы исправите все эти несоответствия (действительно проведите тщательную проверку!), все заработает.
Способ снизить вероятность таких ошибок — избегать повторения кода и обрабатывать четыре направления в цикле, делая добавление к row
и col
динамически определяемым переменной цикла. Вот как это может выглядеть для вашего основного цикла:
while (currentNode.getState() != 3)
{
int row = currentNode.getNodeRow();
int col = currentNode.getNodeCol();
currentNode.setTried(true);
int side;
for (side = -1; side < 3; side++) {
int nextRow = row + side % 2;
int nextCol = col + (side - 1) % 2;
NodeClass neighbor = mazeArr[nextRow][nextCol];
int state = neighbor.getState();
if ((state == 1 || state == 3) && !neighbor.haveTried()) {
neighbor.setParentNode(currentNode);
currentNode.setIsPath(true);
currentNode = neighbor;
break;
}
}
if (side == 3) { // No neighbor available
currentNode.setIsPath(false);
currentNode = currentNode.getParentNode();
}
}
NB: Я предполагаю, что ваша сетка всегда будет иметь стену на внешних границах, как в вашем примере. Если нет, вам нужно будет проверить, находятся ли координаты в пределах сетки.
Спасибо! Ух ты, я допустил много ошибок в своем коде, спасибо, что указали на них. Ваш код намного эффективнее моего, и я постараюсь изо всех сил понять и реализовать его. Я не заметил, что на первой итерации родительскийNode был нулевым, что очень помогает. Я очень ценю помощь.
Приятно слышать, что это было полезно!
Проголосовал за генерацию движений сетки. :)
Из немногих вопросов, которые вы задали ранее, два получили ответ. От вас нет никакой реакции на эти два ответа, как, например, отзыв в комментарии, пусть даже вы отметили ответ как принятый. Это не совсем мотивирует.