1

I'm trying to write the a* path finding algorithm using recursion and am having trouble. The code finds the path to smaller distances but when I try to use it with larger numbers, I get a stack overflow error. I am new to recursion so there is definitely something I am doing wrong but I can't figure it out. I have an exit condition and it works fine on smaller numbers so I don't know what to do unless I have a problem with the algorithm itself. The problem occurs in the findAlgorithm() method where the recursion is being done.

Algorithm:

Node[][]nodes;
ArrayList<Node> options = new ArrayList<Node>();
ArrayList<Node> path = new ArrayList<Node>();
private int x, y, endX, endY;
Node endNode;

public Algorithm(Node[][]nodes) {
    this.nodes = nodes;
    setStartPosition();
    findEndPosition();
}

public ArrayList<Node> getPath() {

    Node node = endNode;

    while(node.hasParent()) {
        path.add(node);
        node = node.getParent();
    }

    return path;

}

public void findPath() {

    if(x!=endX || y!=endY) {
        getSurroundingNodes();
        if(options.size()>0) {
            Node lowestVal = options.get(0);
            for(Node i : options) {
                if(i.getValue()<lowestVal.getValue()) {
                    lowestVal = i;
                }
                else if(i.getValue() == lowestVal.getValue()) {
                    if(i.getEndDistance()<lowestVal.getEndDistance()) {
                        lowestVal = i;
                    }
                }
            }
            x = lowestVal.getX();
            y = lowestVal.getY();
            lowestVal.setTaken();
            options.remove(lowestVal);
            findPath();
        }
    }
    else {
        System.out.println("Made it");
    }

}

private void getSurroundingNodes() {

    Node parent = nodes[y][x];
    for(int i=y-1;i<y+2; i++) {
        for(int z=x-1;z<x+2; z++) {

            if(i>=0&&z>=0&&i<nodes.length&&z<nodes[i].length) {
                Node node = nodes[i][z];
                double endDistance = Math.sqrt((i-endY)*(i-endY)+(z-endX)*(z-endX));
                double startDistance = parent.getStartDistance()+Math.sqrt((i-y)*(i-y)+(z-x)*(z-x));
                double value = endDistance+startDistance;
                if(!node.isWall()&&!node.isTaken()) {
                    if(!options.contains(node)) {
                        node.setParent(parent);
                        node.setX(z);
                        node.setY(i);
                        node.setStartDistance(startDistance);
                        node.setEndDistance(endDistance);
                        node.setValue(value);
                        options.add(node);
                    }
                    else {
                        if(node.getValue()<value) {
                            //do nothing
                        }
                        else if (node.getValue() == value) {
                            if(node.getEndDistance()<=endDistance) {
                                //do nothing
                            }
                            else {
                                node.setParent(parent);
                                node.setX(z);
                                node.setY(i);
                                node.setStartDistance(startDistance);
                                node.setEndDistance(endDistance);
                                node.setValue(value);
                                options.add(node);
                            }
                        }
                        else {
                            node.setParent(parent);
                            node.setX(z);
                            node.setY(i);
                            node.setStartDistance(startDistance);
                            node.setEndDistance(endDistance);
                            node.setValue(value);
                            options.add(node);
                        }
                    }
                }
            }
        }
    }

}

private boolean findEndPosition() {

    for(Node[] i : nodes) {
        for(Node z : i) {
            if(z.isEnd()) {
                endX = z.getX();
                endY = z.getY();
                endNode = z;
                return true;
            }
        }
    }
    return false;       
}

private boolean setStartPosition() {

    for(Node[] i : nodes) {
        for(Node z : i) {
            if(z.isStart()) {
                z.setTaken();
                x = z.getX();
                y = z.getY();
                return true;
            }
        }
    }
    return false;       
}

Node:

private int x, y;
private boolean wall, start, end, taken, hasAParent;
private double endDistance, startDistance, value;
private Node parent = null;

public Node() {
    wall=false;
    start=false;
    end=false;
    taken=false;
    hasAParent = false;
}

public boolean hasParent() {
    return hasAParent;
}

public int getX() {
    return x;
}

public void setX(int x) {
    this.x = x;
}

public int getY() {
    return y;
}

public void setY(int y) {
    this.y = y;
}

public boolean isWall() {
    return wall;
}

public void setWall() {
    wall = true;
    end = false;
    start = false;
}

public boolean isStart() {
    return start;
}

public void setStart(int x, int y) {
    this.x = x;
    this.y = y;
    start = true;
    end = false;
    wall = false;
    endDistance=0.0;
    startDistance=0.0;
    value=0.0;
}

public boolean isEnd() {
    return end;
}

public void setEnd(int x, int y) {
    this.x = x;
    this.y = y;
    end = true;
    start = false;
    wall = false;
    hasAParent = true;
}

public boolean isTaken() {
    return taken;
}

public void setTaken() {
    taken = true;
}

public double getEndDistance() {
    return endDistance;
}

public void setEndDistance(double endDistance) {
    this.endDistance = endDistance;
}

public double getStartDistance() {
    return startDistance;
}

public void setStartDistance(double startDistance) {
    this.startDistance = startDistance;
}

public double getValue() {
    return value;
}

public void setValue(double value) {
    this.value = value;
}

public Node getParent() {
    return parent;
}

public void setParent(Node parent) {
    this.parent = parent;
    hasAParent = true;
}
  • 1
    https://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration – tsolakp Feb 12 '19 at 02:28
  • 1
    Haven't read your code, but Java is not optimized for recursion. If you have a large number of iterations, you'll easily get stackoverflow error. The way to solve it is use loops instead of recursion. – Kartik Feb 12 '19 at 02:30
  • That is a very generic claim. Recursion done right can easily work with Java, too. So: how large is "large" in your case? How many nodes do you have in a working case, what is the smallest example that fails? Beyond that please read [mcve] and enhance your question accordingly. – GhostCat Feb 12 '19 at 02:48
  • @GhostCat I reversed a 8000 length String using recursion and got StackOverflowError on default JVM settings. Of course there would be other factors at play here, but won't you agree that a loop would have done it easily without causing this error? I find recursion easier to understand and solve problems, but would refrain from using it if the number is *high*. – Kartik Feb 12 '19 at 03:02
  • I switched it to a loop and it works but I'd like to try to get it done in recursion as that's what I'm studying in school right now. It starts failing around maybe 5,000 nodes. – Joshua Paige Feb 12 '19 at 03:04
  • @JoshuaPaige If despite the above warning you want to continue using recursion, you can increase the size as described [here](https://blogs.oracle.com/saas-fusion-app-performance/how-to-set-stack-size-to-overcome-javalangstackoverflowerror). – Kartik Feb 12 '19 at 03:07
  • @Joshua maybe that is the "lessen learned" for this case: use the iterative solution and be done now or waste a lot of time and headache in the recursive one(and think "real life": what about all the other poor ones who have to read and understand/maintain/revise the code?). So what is the better and solider and easier to maintain and understand version? – kai Feb 12 '19 at 03:33
  • Thanks, I'll stick to iteration from now on unless recursion is needed. – Joshua Paige Feb 12 '19 at 05:18
  • Then you should consider what to do about the question. Either write a self answer ... or simply delete it. It isnt too helpful for future readers as it is right now ... – GhostCat Feb 12 '19 at 08:15

0 Answers0