4
\$\begingroup\$

I wrote a little program in JavaFX which displays a path of neighbouring open tiles going from top to bottom. It should simulate a percolation.

The algorithm iterates through the whole grid (every tile) populating a list with tiles that have a continuous connection to the top. It all works somewhat. My concern however is that it probably is highly inefficient and I don't really know how to improve said efficiency as we didn't learn anything of that sort in my school.

burnt is just another ArrayList initialised as a member variable.

GitHub link

public void searchCluster(Grid grid){
    Node[][] array = grid.getNodeArray();
    ArrayList<Node> tmpBurnt = new ArrayList();
    LinkedList<Node> tmpSave = new LinkedList();
    Node left;
    Node right;
    Node below;

    for(Node n : array[0]){
        if(n.isSet()){
            tmpBurnt.add(n);
        }
    }

    for(;;){
        if(tmpBurnt.isEmpty()){
            return;
        }
        for(Node n : tmpBurnt){
            //-----check left--------
            if(n.getX() > 0){
                left = array[n.getY()][n.getX() - 1];
                if(left.isSet() && !tmpBurnt.contains(left) && !this.burnt.contains(left)){
                    tmpSave.add(left);
                }
            }
            //-----check right--------
            if(n.getX() < array[n.getY()].length - 1){
                right = array[n.getY()][n.getX() + 1];
                if(right.isSet() && !tmpBurnt.contains(right) && !this.burnt.contains(right)){
                    tmpSave.add(right);
                }
            }
            //-----check below--------
            if(n.getY() < array.length - 1){
                below = array[n.getY() + 1][n.getX()];
                if(below.isSet() && !tmpBurnt.contains(below) && !this.burnt.contains(below)){
                    tmpSave.add(below);
                }
            }
        }
        for(Node n : tmpBurnt){
            this.burnt.add(n);
        }
        tmpBurnt.clear();
        for(Node n : tmpSave){
            tmpBurnt.add(n);
        }
        tmpSave.clear();
    }
}
\$\endgroup\$
  • \$\begingroup\$ why do you scan left and right but not up and down? \$\endgroup\$ – Martin Frank Feb 14 '18 at 13:05
  • 1
    \$\begingroup\$ @MartinFrank I actually do scan downwards, see the "check below" comment. I didn't scan upwards at the time which you correctly stated was a mistake. \$\endgroup\$ – Equiphract Apr 7 '18 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.