Java - Iterative deepening search with nodes

Question

I'm in the process of designing a program that is meant to search through a two-dimensional array of numbers that represents a map for a path to a specified end point. I've been using nodes that have several parameters, most prominently adjacent north, south, east, and west nodes each representing a square within the map. The search method I'm currently trying to finish is with iterative deepening but every time I try running the program, I wind up with a stack overflow error. This is the iterative deepening class.

import java.util.*;
import java.io.*;
public class IDeepeningSearch {
    private Node start;
    private Node end;
    private int[][] map;
    private ArrayList<Node> solution;

    //Build using file handler
    public IDeepeningSearch(String file){
        FileHandler handle = new FileHandler(file);

        //Create map
        map = handle.getMap();

        //Start node coordinates and value
        start = new Node();
        start.setRow(handle.getSRow());
        start.setCol(handle.getSCol());
        start.setValue(map[start.getRow()][start.getCol()]);

        //End node coordinates
        end = new Node();
        end.setRow(handle.getERow());
        end.setCol(handle.getECol());
        end.setValue(map[start.getRow()][start.getCol()]);
    }

    //Runs search
    public void run(){
        int i = 0;
        solution = new ArrayList<Node>();
        //Value of i indicates depth to be explored; will increment with each failure
        while(solution.isEmpty()){
            search(start, i);
            i++;
        }
        if(!solution.isEmpty()){
            System.out.println("It worked.");
        }
        System.out.println("If you're not seeing the other message then it failed.");
    }

    //Building tree
    public void build(Node head){
        setNLeaf(head);
        setSLeaf(head);
        setELeaf(head);
        setWLeaf(head);
//      if(head.getNorth() != null){
//          build(head.getNorth());
//      }
//      if(head.getSouth() != null){
//          build(head.getSouth());
//      }
//      if(head.getEast() != null){
//          build(head.getEast());
//      }
//      if(head.getWest() != null){
//          build(head.getWest());
//      }
    }

    //Performs search
    public void search(Node head, int depth){
        if(head.getRow() == end.getRow() && head.getCol() == end.getCol()){
            solution.add(head);
            return;
        }
        else{
            if(depth == 0){
                return;
            }
            build(head);
            if(head.getNorth() != null){
                search(head.getNorth(), depth--);
            }
            if(head.getSouth() != null){
                search(head.getSouth(), depth--);
            }
            if(head.getEast() != null){
                search(head.getEast(), depth--);
            }
            if(head.getWest() != null){
                search(head.getWest(), depth--);
            }
        }
    }

    //Sets north leaf
    public void setNLeaf(Node node){
        //Determines if parent is on edge of map and if desired space has 0 value
        if(node.getRow() != 0 && map[node.getRow() - 1][node.getCol()] != 0){
            Node n = new Node();
            n.setRow(node.getRow() - 1);
            n.setCol(node.getCol());
            n.setValue(map[n.getRow()][n.getCol()]);
            n.setParent(node);
            node.setNorth(n);
        }
    }

    //Sets south leaf
    public void setSLeaf(Node node){
        //Determines if parent is on edge of map and if desired space has 0 value
        if(node.getRow() != (map.length - 1) && map[node.getRow() + 1][node.getCol()] != 0){
            Node n = new Node();
            n.setRow(node.getRow() + 1);
            n.setCol(node.getCol());
            n.setValue(map[n.getRow()][n.getCol()]);
            n.setParent(node);
            node.setSouth(n);
        }
    }

    //Sets east leaf
    public void setELeaf(Node node){
        //Determines if parent is on edge of map and if desired space has 0 value
        if(node.getRow() != (map[0].length - 1) && map[node.getRow()][node.getCol() + 1] != 0){
            Node n = new Node();
            n.setRow(node.getRow());
            n.setCol(node.getCol() + 1);
            n.setValue(map[n.getRow()][n.getCol()]);
            n.setParent(node);
            node.setEast(n);
        }
    }

    //Sets west leaf
    public void setWLeaf(Node node){
        //Determines if parent is on edge of map and if desired space has 0 value
        if(node.getCol() != 0 && map[node.getRow()][node.getCol() - 1] != 0){
            Node n = new Node();
            n.setRow(node.getRow());
            n.setCol(node.getCol() - 1);
            n.setValue(map[n.getRow()][n.getCol()]);
            n.setParent(node);
            node.setWest(n);
        }   
    }
}

I thought I was doing this correctly but the errors I've been getting have been pretty constant. This is what I wind up with.

Exception in thread "main" java.lang.StackOverflowError
at Node.setSouth(Node.java:88)
at IDeepeningSearch.setSLeaf(IDeepeningSearch.java:113)
at IDeepeningSearch.build(IDeepeningSearch.java:48)
at IDeepeningSearch.search(IDeepeningSearch.java:75)
at IDeepeningSearch.search(IDeepeningSearch.java:77)
at IDeepeningSearch.search(IDeepeningSearch.java:80)
at IDeepeningSearch.search(IDeepeningSearch.java:77)

The second-to-last and last lines repeat. I've tried building a full tree as well but that either gives me another stack overflow error or a null pointer exception. I'm not really sure what the issue is here but if I can fix this, I'm sure I can finish my breadth-first search method as well.

Answer 1

The StackOverflowError is because of the flawed recursive calls of search(node, depth--) as Chris Rise has mentioned in his answer. Try --depth to fix this.

There is also poor memory management in this code, which is wasting heap memory that could either slow the program due to several calls to GC (Garbage-Collector) or lead to an OutOfMemeoryError! This problem is visible in the setXLeaf(Node n) methods (e.g. setNLeaf(Node north) etc.) where every time you are creating a new Node, while this can be done only when it's necessary with a simple check:

if (node.getSouth() == null) {
    Node n = new Node();
    n.setParent(node);
    node.setSouth(n);
}
node.getSouth().setRow(node.getRow() + 1);
node.getSouth().setCol(node.getCol());
node.getSouth().setValue(map[node.getRow() + 1][node.getCol()]);

This way you will avoid creating new objects that are unnecessary. This should be fixed in all the setXLeaf(...) methods.

Answer 2

depth-- evaluates to the original value of depth. This means that the unmodified version of depth is being passed to the recursive call to search(), so your code is never approaching the base case. Try depth-1 instead. Or, if you need the value of the local variable depth to change, --depth.

For example, this will continually print 10 until it reaches stack overflow

public void foo(int x) {
    if (x == 0) {
        return;
    }
    System.out.println(x);
    foo(x--);
}

foo(10);