# Recursively evaluate neighbors in a two dimensional grid

Posted on

Problem

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
{
}

//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.

Solution

## 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.

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<>();
while (!candidates.isEmpty())
{
Point p = candidates.remove(candidates.size() - 1);
if (matches.contains(p))
{
continue;
}
else
{
}

//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.

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 . 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.