Recursively evaluate neighbors in a two dimensional grid

Question

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 < rows; i++) {
            for(int j = 0; j < 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 < rows; i++) {
            for(int j = 0; j < 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 < rows && y < columns) {
                Gem g = this.at(x, y);
                HashSet<Point> matches = new HashSet<Point>();
                locateNeighbors(x, y, g.getColor(), matches);
                System.out.println(matches.size() + " matches found.");
            }

    }

    private void locateNeighbors(int x, int y, COLOR color, HashSet<Point> matches) {

        Point p = new Point(x, y);

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

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

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

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

        //Check west
        if(x - 1 >= 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.

Answer 1

Avoid unnecessary calculations

It's a trivial performance improvement, but in

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

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

changing to

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

        //Check west
        if (x > 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<Point> candidates = new ArrayList<>();
        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 < 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 < rows)
            {
                if(at(p.getX() + 1, p.getY()).getColor() == color)
                {
                    candidates.add(new Point (p.getX() + 1, p.getY());
                }
            }

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

            //Check west
            if (p.getX() > 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<Point> matches = new HashSet<Point>();

would be written as

                Set<Point> matches = new HashSet<>();

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.

Answer 2

As much as possible, make your fields private and final. Especially private

These

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

Would be better of as:

private final int rows, columns;
private int x, y; // not sure what these are used for
private final GemPool pool;
private final Gem[][] board;

i and j in double for-loops.

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

I honestly find it ridiculous to have names like i and j in 2D for-loops. Unfortunately, I see this quite often. Is i or j for the columns? Please name them row and col instead.

Speaking of x and y...

Last time I checked, x were for columns and y is for rows. Your code mixes this up, however.

There's the at method:

public Gem at(int row, int column) {

And there's the calls to the at method:

if(this.at(x, y + 1).getColor() == color)

And there's this if statement:

if(x < rows && y < columns) {

Whenever you see x < rows, a big alarm should go off in your head. It should be:

if (x < columns && y < rows) {

Good, then do something about them.

//I'm aware of the magic numbers here

java.awt.Point

You mentioned in a comment that you're using java.awt.Point, and you are doing libgdx. I would not recommend to use java.awt.Point in a LibGDX project. I doubt it will work for the Android platform and for the HTML5 platform (if you are interested in targeting those, which really never hurts to do). I'd recommend using LibGDX's GridPoint2 class instead.

locateNeighbors method

This is something I tend to recommend quite often, use a Direction4 enum:

public enum Direction4 {
    NORTH(0, -1), EAST(1, 0), SOUTH(0, 1), WEST(-1, 0);

    private final int dx;
    private final int dy;

    private Direction4(int dx, int dy) {
        this.dx = dx;
        this.dy = dy;
    }
    public int getX() { return dx; }
    public int getY() { return dy; }
}

Using this, you can loop through the Direction4.values()

private void locateNeighbors(int x, int y, COLOR color, Set<Point> matches) {
    ...

    for (Direction4 dir : Direction4.values()) {
        int newX = x + dir.getX();
        int newY = y + dir.getY();
        if (this.isInRange(newX, newY)) {
            if (this.at(newX, newY).getColor() == color) {
                locateNeighbors(newX, newY, color, matches);
            }
        }
    }
}

This significantly reduces the code duplication.

Another suggestion here is to use GemCell[][] board for your board, where GemCell contains both the color of a Gem and also the x and y position of the tile, and use a Set<GemCell> in your recursive method. This allows you to call that method without having to create new Point objects all the time.