Алгоритм Java DepthFirstSearch не работает

Я попытался написать алгоритм поиска в глубину для решения лабиринта. Это то, что у меня есть до сих пор. Я постарался добавить как можно больше деталей, чтобы логика была понятна:

//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, но обнаружил, что на самом деле он не равен нулю. В чем может быть проблема? Буду признателен за любые советы. Спасибо.

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

trincot 22.07.2024 21:01

Вопросы этого типа должны включать трассировку стека. Но вас может заинтересовать этот вопрос и ответы на него: stackoverflow.com/questions/3988788/… . Надеюсь, это поможет вам решить проблему самостоятельно.

Old Dog Programmer 22.07.2024 21:04

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

LonelyBoi404 22.07.2024 21:11

Вам не обязательно помечать ответ как принятый, но некоторая обратная связь похожа на то, что хотел бы получить тот, кто публикует ответ. Как бы вы себя почувствовали, если бы потратили время на написание ответа, а всем плевать? Но я вижу, что вы сейчас отвечаете ;-)

trincot 22.07.2024 21:15

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

LonelyBoi404 22.07.2024 21:18

код проверяет if ((mazeArr[row-1][col]..., но затем currentNode = mazeArr[row][col+1]; (проверка вниз, но назначение вправо) -- аналогично проверке влево, но назначение вправо -- mazeArr[row-1][col].setParentNode неверно для всех, кроме первого (вверх) -- типичные ошибки копирования и вставки (и своего рода частое повторение кода)

user85421 22.07.2024 23:20

также вообще нет проверок ограничений... если данные лабиринта неверны, код может/выдаст исключение IndexOutOfBoundsException

user85421 22.07.2024 23:28
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
1
7
58
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Во-первых, вы выполняете отладку не в том месте. Ошибка возникает в условии 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 был нулевым, что очень помогает. Я очень ценю помощь.

LonelyBoi404 23.07.2024 19:09

Приятно слышать, что это было полезно!

trincot 23.07.2024 19:20

Проголосовал за генерацию движений сетки. :)

Unmitigated 24.07.2024 00:32

Другие вопросы по теме