CODEWITHSUNDEEP
javaalgorithmrecursionarraylist
L3n95
L3n95

Reputation: 1615

Basic recursive Algorithm in Java

I'm trying to implement a basic RRT (rapidly-exploring random tree) algorithm in Java. I have a class TreeNode, which saves the x and y position of the node and in an ArrayList it saves all the child-nodes it has. In my main program I have the root of the tree. If I want to find the nearest neighbour in tree I call this code. The method is called with the root node as "node" and minAbstand is Integer.MAX_VALUE

private void NEAREST_NEIGHBOUR(int xrand, int yrand, TreeNode node, int minAbstand) {
    if((Math.sqrt(Math.pow(node.getxPos()-xrand, 2) + Math.pow(node.getyPos()-yrand, 2))) <= minAbstand){//normal method to find the distance
        minAbstand = (int) Math.sqrt(Math.pow(node.getxPos()-xrand, 2) + Math.pow(node.getyPos()-yrand, 2));
        xnearest = node;
    }
    for(int i = 0; i < node.getNodes().size(); i++){
        NEAREST_NEIGHBOUR(xrand, yrand, node.getNodes().get(i), minAbstand);
    }
}

I thought I am going recursively through all nodes and find that one, with the lowest distance. After the NEAREST_NEIGHBOUR method, the nearest neighbour shoudl be saved in xnearest. Now I add the new node to the nearest node via this method:

xnearest.addNode(xnew).

addNode is a method from the TreeNode class which calls arraylist.add(node), so just adding the node to the ArrayList. After this the new node should be a "child-node" of the nearest node. And then all starts from the beginning: - create random node, -finding nearest node to random node, - adding random node to nearest node,... But in fact this isn't what happens.

In the highlighted area you can see that it didn't choose the node with the lowest distance. What am I doing wrong there?

The whole code:

    private void doRRT(Canvas canvas, PaintEvent e, int K, int deltaT){
      for(int i = 0; i < K; i++){
          xrand = new TreeNode(new Random().nextInt(canvas.getSize().x * 2) - 500, new Random().nextInt(canvas.getSize().y * 2) - 300);

          NEAREST_NEIGHBOUR(xrand.getxPos(), xrand.getyPos(), xstart, Integer.MAX_VALUE);

          NEW_STATE(xrand.getxPos(), xrand.getyPos(), deltaT);

          e.gc.drawRectangle(xnearest.getxPos() - 1, xnearest.getyPos() - 1, 2, 2);
          e.gc.drawLine(xnearest.getxPos(), xnearest.getyPos(), xnew.getxPos(), xnew.getyPos());
      }
  }

  private void NEW_STATE(int xrand, int yrand, int deltaT) {
      int nearx = xnearest.getxPos(), neary = xnearest.getyPos();
      if(Math.sqrt(Math.pow(nearx - xrand, 2) + Math.pow(neary - yrand, 2)) > deltaT){
          float faktor = (float) (Math.sqrt(Math.pow(nearx - xrand, 2) + Math.pow(neary - yrand, 2)) / deltaT);
          xnew = new TreeNode((int) (nearx + (xrand - nearx)/ faktor), (int) (neary + (yrand - neary)/ faktor));
      } else {
          xnew = new TreeNode(xrand, yrand);
      }
      xnearest.addNode(xnew);
  }

private void NEAREST_NEIGHBOUR(int xrand, int yrand, TreeNode node, int minAbstand) {
    counter2++;
      if((Math.sqrt(Math.pow(node.getxPos()-xrand, 2) + Math.pow(node.getyPos()-yrand, 2))) < minAbstand){
          minAbstand = (int) Math.sqrt(Math.pow(node.getxPos()-xrand, 2) + Math.pow(node.getyPos()-yrand, 2));
          xnearest = node;
      }
      for(int i = 0; i < node.getNodes().size(); i++){
          NEAREST_NEIGHBOUR(xrand, yrand, node.getNodes().get(i), minAbstand);
      }
  }

And the TreeNode class:

TreeNode(int x, int y){
    xPos = x;
    yPos = y;
    nodes = new ArrayList<TreeNode>();
}

public ArrayList<TreeNode> getNodes() {
    return nodes;
}

public int getxPos() {
    return xPos;
}

public int getyPos() {
    return yPos;
}

public void addNode(TreeNode node){
    nodes.add(node);
}

The solution?

Is this right now? Recursion is really tricky

private int NEAREST_NEIGHBOUR(int xrand, int yrand, TreeNode node, int minAbstand) {
  if((Math.sqrt(Math.pow(node.getxPos()-xrand, 2) + Math.pow(node.getyPos()-yrand, 2))) < minAbstand){
      minAbstand = (int) Math.sqrt(Math.pow(node.getxPos()-xrand, 2) + Math.pow(node.getyPos()-yrand, 2));
      xnearest = node;
  }
  for(int i = 0; i < node.getNodes().size(); i++){
      minAbstand = NEAREST_NEIGHBOUR(xrand, yrand, node.getNodes().get(i), minAbstand);
  }
  return minAbstand;

}

Upvotes: 3

Views: 263

Answers (1)

Little Santi
Little Santi

Reputation: 8783

I must correct myself: The NEAREST_NEIGHBOUR method has a failing logic. Look:

When the method starts, compares the recived minAbstand with the distance to the current evaluated node. And, if it is lower, the minAbstand value is updated in order to restrict the search criterium within the current subtree recursively. So far, so good.

But, what about the sibling-subtrees? I mean: when the current subtree is completely browsed, the current method invocation ends, and thus, returns the control to the calling method, which its itself, in a previous recursive frame. But the values of the local variables get missed (like minAbstand).

What you need is to return minAbstand as the return value of NEAREST_NEIGHBOUR, and update it every time it is recursively invoked.

Upvotes: 1

Related Questions