Recursively evaluate neighbors in a two dimensional grid I'm creating a puzzle mini game where there is a board of gems, varying in color, and chosen at random.

This is what my code generates:


When you click on a gem the game should traverse the board and find all connecting gems of the same color. When you click the orange square all orange square neighbors are selected. 



Here is my Board class. The locateNeighbors() method recursively searches adjoining grid tiles until it reaches a non-matching gem or the edge of the board.

public class Board {

    public int rows, columns;
    public int x, y;
    private GemPool pool;
    private Gem[][] board;

    public Board(int rows, int columns) {

        x = 0;
        y = 0;

        this.rows = rows;
        this.columns = columns;

        board = new Gem[rows][columns];
        pool = new GemPool(COLOR.BLUE, COLOR.RED, COLOR.YELLOW, COLOR.GREEN, COLOR.ORANGE, COLOR.PURPLE);

        for(int i = 0; i &lt; rows; i++) {
            for(int j = 0; j &lt; columns; j++) {
                board[i][j] = pool.grabGem();
            }
        }

    }

    public Gem at(int row, int column) {

        return board[row][column];

    }

    public void draw(SpriteBatch batch) {

        for(int i = 0; i &lt; rows; i++) {
            for(int j = 0; j &lt; columns; j++) {
                String color = board[i][j].getColorName();
                //I'm aware of the magic numbers here
                batch.draw(pool.grabTexture(color), (i * 72) + x, (j * 72) + y);
            }
        }

    }

    public void dispose() {

        pool.dispose();

    }

    public void click(Vector3 touchPos) {

            //I'm aware of the magic numbers here
            int x = (int)(touchPos.x / 72);
            int y = (int)(touchPos.y / 72);

            if(x &lt; rows &amp;&amp; y &lt; columns) {
                Gem g = this.at(x, y);
                HashSet&lt;Point&gt; matches = new HashSet&lt;Point&gt;();
                locateNeighbors(x, y, g.getColor(), matches);
                System.out.println(matches.size() + " matches found.");
            }

    }

    private void locateNeighbors(int x, int y, COLOR color, HashSet&lt;Point&gt; matches) {

        Point p = new Point(x, y);

        if(matches.contains(p))
        {
            return;
        }
        else
        {
            matches.add(p);
        }

        //Check north
        if(y + 1 &lt; columns)
        {
            if(this.at(x, y + 1).getColor() == color)
                locateNeighbors(x, y + 1, color, matches);
        }

        //Check east
        if(x + 1 &lt; rows)
        {
            if(this.at(x + 1, y).getColor() == color)
                locateNeighbors(x + 1, y, color, matches);
        }

        //Check south
        if(y - 1 &gt;= 0)
        {
            if(this.at(x, y - 1).getColor() == color)
                locateNeighbors(x, y - 1, color, matches);
        }

        //Check west
        if(x - 1 &gt;= 0)
        {
            if(this.at(x - 1, y).getColor() == color)
                locateNeighbors(x - 1, y, color, matches);
        }

    }

}


I would love your opinions on optimizations that could be made to the recursive method.
Avoid unnecessary calculations

It's a trivial performance improvement, but in 


        //Check south
        if(y - 1 &gt;= 0)
        {
            if(this.at(x, y - 1).getColor() == color)
                locateNeighbors(x, y - 1, color, matches);
        }

        //Check west
        if(x - 1 &gt;= 0)
        {
            if(this.at(x - 1, y).getColor() == color)
                locateNeighbors(x - 1, y, color, matches);
        }



changing to 

        //Check south
        if (y &gt; 0)
        {
            if (this.at(x, y - 1).getColor() == color)
            {
                locateNeighbors(x, y - 1, color, matches);
            }
        }

        //Check west
        if (x &gt; 0)
        {
            if (this.at(x - 1, y).getColor() == color)
            {
                locateNeighbors(x - 1, y, color, matches);
            }
        }


will be faster when the expression is false.  When it's true, it's unlikely to matter, as the compiler should optimize down to just one subtraction.  But when false, no subtractions are needed at all.  Of course, subtractions add a trivial amount of time in boards with just a few hundred squares.  

Note:  I also added brackets around the single statement form if statements.  While the compiler is fine with the other syntax, it tends to lead to a coding error that can be hard to diagnose.  For that reason, many programmers always use the block form.  

Recursion adds overhead

You could also try rewriting the recursive function iteratively.  Note that there is more state in a function call than you need to save.  The color doesn't change, and it always refers to the same matches Set.  Only the points change.  

You don't provide all the code, so I can't test it.  But it would look something like.  

        List&lt;Point&gt; candidates = new ArrayList&lt;&gt;();
        candidates.add(new Point(x, y));
        while (!candidates.isEmpty())
        {
            Point p = candidates.remove(candidates.size() - 1);
            if (matches.contains(p))
            {
                continue;
            }
            else
            {
                matches.add(p);
            }

            //Check north
            if (p.getY() + 1 &lt; columns)
            {
                if(at(p.getX(), p.getY() + 1).getColor() == color)
                {
                    candidates.add(new Point (p.getX(), p.getY() + 1));
                }
            }

            //Check east
            if (p.getX() + 1 &lt; rows)
            {
                if(at(p.getX() + 1, p.getY()).getColor() == color)
                {
                    candidates.add(new Point (p.getX() + 1, p.getY());
                }
            }

            //Check south
            if (p.getY() &gt; 0)
            {
                if (at(p.getX(), p.getY() - 1).getColor() == color)
                {
                    candidates.add(new Point (p.getX(), p.getY() - 1);
                }
            }

            //Check west
            if (p.getX() &gt; 0)
            {
                if (at(p.getX() - 1, p.getY()).getColor() == color)
                {
                    candidates.add(new Point (p.getX() - 1, p.getY());
                }
            }
        }


Note however that the compiler may optimize out the suboptimal portions of the original code.  In that case, this may not be faster.  

You also should question whether this is the place in the program where optimizations are most helpful.  I would think that removing gems, adding new ones, and redrawing the board would take more time.  Shaving off a few milliseconds here won't help you if you're stuck with extra seconds elsewhere.  As a general rule, you want to finish the program and then find where optimizations would be most useful.  

It's unnecessary to write this.at unless there is a conflict.  Simply saying at will almost always work.  

Declare as the interface

You define matches as a HashSet.  In Java, it is more common to define objects as interfaces rather than implementations.  So 


                HashSet&lt;Point&gt; matches = new HashSet&lt;Point&gt;();



would be written as 

                Set&lt;Point&gt; matches = new HashSet&lt;&gt;();


instead.  This allows you to change the implementation quickly in one place without affecting the rest of the program.  

Assuming that you are using Java 8, you don't have to write Point twice.  The compiler will figure out the appropriate type for you.