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