# BFS in a grid with wall breaking saldo in Java

In this problem, we are given a 2-dimentional grid, with each cell being walkable or holding a wall. Given an integer $s \geq 0$, find the shortest path from the source node to target node breaking no more than $s$ walls.

Grid.java

package net.coderodde.grid.router;

import java.util.Objects;

public final class Grid {

/**
* The minimum width of any grid.
*/
private static final int MINIMUM_WIDTH = 1;

/**
* The minimum height of any grid.
*/
private static final int MINIMUM_HEIGHT = 1;

/**
* The value denoting that a grid cell is unoccupied by the wall.
*/
private static final boolean WALKABLE = false;

/**
* The value denoting that a grid cell is occupied by the wall.
*/
private static final boolean OCCUPIED = true;

/**
* The default character for printing a free cell.
*/
private static final char DEFAULT_FREE_CELL_CHARACTER = ' ';

/**
* The default character for printing an occupied cell.
*/
private static final char DEFAULT_WALL_CELL_CHARACTER = '#';

/**
* The actual grid.
*/
private final boolean[][] grid;

public Grid(int width, int height) {
checkWidth(width);
checkHeight(height);
this.grid = new boolean[height][width];
}

public int getWidth() {
return grid[0].length;
}

public int getHeight() {
return grid.length;
}

public boolean isFreeCell(int x, int y) {
checkXCoordinate(x);
checkYCoordinate(y);
return grid[y][x] == WALKABLE;
}

public boolean isWallCell(int x, int y) {
checkXCoordinate(x);
checkYCoordinate(y);
return grid[y][x] == OCCUPIED;
}

public void setWallCell(int x, int y) {
checkXCoordinate(x);
checkYCoordinate(y);
grid[y][x] = OCCUPIED;
}

public void setFreeCell(int x, int y) {
checkXCoordinate(x);
checkYCoordinate(y);
grid[y][x] = WALKABLE;
}

public static Grid getGridFromMatrix(boolean[][] matrix) {
Objects.requireNonNull(matrix, "The input matrix is null.");
int height = matrix.length;
int width = -1;

for (boolean[] row : matrix) {
if (row != null && width < row.length) {
width = row.length;
}
}

Grid grid = new Grid(width, height);

for (int y = 0; y < height; ++y) {
if (matrix[y] != null) {
for (int x = 0; x < matrix[y].length; ++x) {
if (matrix[y][x]) {
grid.setWallCell(x, y);
}
}
}
}

return grid;
}

public static char[][] getTextualRepresentation(Grid grid,
char freeCellCharacter,
char wallCharacter) {
int width = grid.grid[0].length;
int height = grid.grid.length;

char[][] charMatrix = new char[height][width];

for (int y = 0; y < height; ++y) {
for (int x = 0; x < width; ++x) {
charMatrix[y][x] =
grid.isWallCell(x, y) ?
wallCharacter :
freeCellCharacter;
}
}

return charMatrix;
}

public static char[][] getTextualRepresentation(Grid grid) {
return getTextualRepresentation(grid,
DEFAULT_FREE_CELL_CHARACTER,
DEFAULT_WALL_CELL_CHARACTER);
}

public static String textualRepresentationToString(char[][] textMatrix) {
int width = textMatrix[0].length;
int height = textMatrix.length;

StringBuilder sb = new StringBuilder();
sb.append("\n");

for (int y = 0; y < height; ++y) {
sb.append('|');

for (int x = 0; x < textMatrix[0].length; ++x) {
sb.append(textMatrix[y][x]);
}

sb.append("|\n");
}

return sb.toString();
}

private static void loadHorizontalBar(StringBuilder sb, int width) {
sb.append('+');

for (int i = 0; i < width; ++i) {
sb.append('-');
}

sb.append('+');
}

private void checkWidth(int width) {
if (width < MINIMUM_WIDTH) {
throw new IllegalArgumentException(
"The input width is too small: " + width + ". Must be at " +
"least " + MINIMUM_WIDTH + ".");
}
}

private void checkHeight(int height) {
if (height < MINIMUM_HEIGHT) {
throw new IllegalArgumentException(
"The input height is too small: " + height + ". Must be "  +
"at least " + MINIMUM_HEIGHT + ".");
}
}

private void checkXCoordinate(int x) {
if (x < 0) {
throw new IndexOutOfBoundsException(
"The X-coordinate is negative: " + x + ".");
}

if (x >= grid[0].length) {
throw new IndexOutOfBoundsException(
"The X-coordinate is too large: " + x + ". Must be at " +
"most " + (grid[0].length - 1) + ".");
}
}

private void checkYCoordinate(int y) {
if (y < 0) {
throw new IndexOutOfBoundsException(
"The Y-coordinate is negative: " + y + ".");
}

if (y >= grid.length) {
throw new IndexOutOfBoundsException(
"The Y-coordinate is too large: " + y + ". Must be at " +
"most " + (grid.length - 1) + ".");
}
}
}


Router.java

package net.coderodde.grid.router;

import java.awt.Point;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;

public class Router {

private static final char PAINT_CHAR_PATH_STEP = '.';
private static final char PAINT_CHAR_BREAK_WALL = 'X';
private static final char PAINT_CHAR_SOURCE = 'S';
private static final char PAINT_CHAR_TARGET = 'T';

public static List<Point> getEscapeRoute(Grid grid,
Point sourceCoordinates,
Point targetCoordinates,
int saldo) {
Objects.requireNonNull(grid, "The input grid is null.");
checkSourceCoordinates(sourceCoordinates, grid);
checkTargetCoordinates(targetCoordinates, grid);
checkSaldo(saldo);
return new Router(grid,
sourceCoordinates,
targetCoordinates,
saldo).search();
}

public static void paintPath(char[][] textMatrix,
Grid grid,
List<Point> path) {
paintPath(textMatrix,
grid,
path,
PAINT_CHAR_PATH_STEP,
PAINT_CHAR_BREAK_WALL,
PAINT_CHAR_SOURCE,
PAINT_CHAR_TARGET);
}

public static void paintPath(char[][] textMatrix,
Grid grid,
List<Point> path,
char pathStep,
char breakWall,
char sourceChar,
char targetChar) {
if (path.isEmpty()) {
return;
}

for (Point p : path) {
if (grid.isWallCell(p.x, p.y)) {
textMatrix[p.y][p.x] = breakWall;
} else {
textMatrix[p.y][p.x] = pathStep;
}
}

Point source = path.get(0);
Point target = path.get(path.size() - 1);

textMatrix[source.y][source.x] = sourceChar;
textMatrix[target.y][target.x] = targetChar;
}

private final Grid grid;
private final Point sourceCoordinates;
private final Point targetCoordinates;
private final int saldo;

private Router(Grid grid,
Point sourceCoordinates,
Point targetCoordiantes,
int saldo) {
this.grid = grid;
this.sourceCoordinates = sourceCoordinates;
this.targetCoordinates = targetCoordiantes;
this.saldo = saldo;
}

private final class GridNode {
final int x;
final int y;
final int saldo;

GridNode(int x, int y, int saldo) {
this.x = x;
this.y = y;
this.saldo = saldo;
}

@Override
public int hashCode() {
return x ^ y;
}

@Override
public boolean equals(Object o) {
if (o == null) {
return false;
}

if (o == this) {
return true;
}

if (!getClass().equals(o.getClass())) {
return false;
}

GridNode other = (GridNode) o;
return x == other.x && y == other.y;
}

List<GridNode> getNeighborNodes() {
List<GridNode> neighborNodeList = new ArrayList<>(4);
int width = grid.getWidth();
int height = grid.getHeight();

if (x > 0) {
boolean wall = grid.isWallCell(x - 1, y);

if (wall) {
if (saldo > 0) {
neighborNodeList.add(new GridNode(x - 1, y, saldo - 1));
}
} else {
neighborNodeList.add(new GridNode(x - 1, y, saldo));
}
}

if (x < width - 1) {
boolean wall = grid.isWallCell(x + 1, y);

if (wall) {
if (saldo > 0) {
neighborNodeList.add(new GridNode(x + 1, y, saldo - 1));
}
} else {
neighborNodeList.add(new GridNode(x + 1, y, saldo));
}
}

if (y > 0) {
boolean wall = grid.isWallCell(x, y - 1);

if (wall) {
if (saldo > 0) {
neighborNodeList.add(new GridNode(x, y - 1, saldo - 1));
}
} else {
neighborNodeList.add(new GridNode(x, y - 1, saldo));
}
}

if (y < height - 1) {
boolean wall = grid.isWallCell(x, y + 1);

if (wall) {
if (saldo > 0) {
neighborNodeList.add(new GridNode(x, y + 1, saldo - 1));
}
} else {
neighborNodeList.add(new GridNode(x, y + 1, saldo));
}
}

return neighborNodeList;
}
}

private List<Point> search() {
GridNode sourceNode = new GridNode(sourceCoordinates.x,
sourceCoordinates.y,
saldo);
Deque<GridNode> queue = new ArrayDeque<>(Arrays.asList(sourceNode));
Map<GridNode, GridNode> parentMap = new HashMap<>();

parentMap.put(sourceNode, null);

while (!queue.isEmpty()) {
GridNode currentNode = queue.removeFirst();

if (nodeIsAtTarget(currentNode)) {
return buildPath(currentNode, parentMap);
}

for (GridNode childNode : currentNode.getNeighborNodes()) {
if (!parentMap.containsKey(childNode)) {
parentMap.put(childNode, currentNode);
}
}
}

// Return empty path to denote unreachability:
return new ArrayList<>(0);
}

private List<Point> buildPath(GridNode targetNode,
Map<GridNode, GridNode> parentMap) {
List<Point> path = new ArrayList<>();
GridNode currentNode = targetNode;

while (currentNode != null) {
currentNode = parentMap.get(currentNode);
}

Collections.<Point>reverse(path);
return path;
}

private boolean nodeIsAtTarget(GridNode node) {
return node.x == targetCoordinates.x &&
node.y == targetCoordinates.y;
}

private static void checkSaldo(int saldo) {
if (saldo < 0) {
throw new IllegalArgumentException(
"The saldo is negative: " + saldo + ".");
}
}

private static void checkSourceCoordinates(Point sourceCoordinates,
Grid grid) {
Objects.requireNonNull(sourceCoordinates,
"The source coordinates are null.");

int x = sourceCoordinates.x;
int y = sourceCoordinates.y;

if (x < 0) {
throw new IndexOutOfBoundsException(
"The X-coordinate of the source point is negative: " + x +
".");
}

if (x >= grid.getWidth()) {
throw new IndexOutOfBoundsException(
"The X-coordinate of the source point is too large: " +
x + ". Must be at most " + (grid.getWidth() - 1) + ".");
}

if (y < 0) {
throw new IndexOutOfBoundsException(
"The Y-coordinate of the source point is negative: " + x +
".");
}

if (y >= grid.getHeight()) {
throw new IndexOutOfBoundsException(
"The Y-coordinate of the source point is too large: " +
x + ". Must be at most " + (grid.getHeight() - 1) + ".");
}
}

private static void checkTargetCoordinates(Point targetCoordinates,
Grid grid) {
Objects.requireNonNull(targetCoordinates,
"The source coordinates are null.");

int x = targetCoordinates.x;
int y = targetCoordinates.y;

if (x < 0) {
throw new IndexOutOfBoundsException(
"The X-coordinate of the target point is negative: " + x +
".");
}

if (x >= grid.getWidth()) {
throw new IndexOutOfBoundsException(
"The X-coordinate of the target point is too large: " +
x + ". Must be at most " + (grid.getWidth() - 1) + ".");
}

if (y < 0) {
throw new IndexOutOfBoundsException(
"The Y-coordinate of the target point is negative: " + x +
".");
}

if (y >= grid.getHeight()) {
throw new IndexOutOfBoundsException(
"The Y-coordinate of the target point is too large: " +
x + ". Must be at most " + (grid.getHeight() - 1) + ".");
}
}
}


Main.java

package net.coderodde.grid.router;

import java.awt.Point;
import java.util.List;

public class Main {

public static void main(String[] args) {
boolean[][] matrix =
{{false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false},
{true, true, false, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, false},
{true, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false},
{true, true, true, false, false, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true},
{true, true, true, true, false, false, true, true, true, true, true, true, true, true, true, true, true, true, true, false},
{true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false},
{true, true, true, true, true, true, false, true, true, true, true, true, true, true, true, true, true, true, true, false},
{false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false},
{false, true, true, true, true, true, true, false, false, true, true, true, true, true, true, true, true, true, true, true},
{false, true, true, true, true, true, true, true, false, false, true, true, true, true, true, true, true, true, true, true},
{false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false},
{true, true, true, true, true, true, true, true, true, true, false, true, true, true, true, true, true, true, true, false},
{false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false},
{false, true, true, true, true, true, true, true, true, true, false, false, true, true, true, true, true, true, true, true},
{false, true, true, true, true, true, true, true, true, true, true, false, true, true, true, true, true, true, true, true},
{false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false},
{true, true, true, true, true, true, true, true, true, true, true, true, true, false, true, true, true, true, true, false},
{false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false},
{false, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, false},
{false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false}};

Grid grid = Grid.getGridFromMatrix(matrix);
Point source = new Point(0, 0);
Point target = new Point(grid.getWidth() - 1, grid.getHeight() - 1);
int saldo = 1;

long startTime = System.currentTimeMillis();
List<Point> path = Router.getEscapeRoute(grid, source, target, saldo);
long endTime = System.currentTimeMillis();

System.out.println("Found a path of length " + (path.size()) +
" in " + (endTime - startTime) + " milliseconds.");

char[][] textMatrix = Grid.getTextualRepresentation(grid);
Router.paintPath(textMatrix, grid, path);

System.out.println(Grid.textualRepresentationToString(textMatrix));
}
}


The output is:

Found a path of length 39 in 8 milliseconds.
+--------------------+
|S.X                 |
|##.################ |
|##...               |
|### .###############|
|####..############# |
|#    ..             |
|######.############ |
|      ...           |
| ###### .###########|
| #######..##########|
|         ..         |
|##########.######## |
|          ..        |
| ######### .########|
| ##########.########|
|           .........|
|############# #####.|
|                   .|
| ##################.|
|                   T|
+--------------------+


Critique request

I would like to hear any comments, yet I am most interested in the API design critique.

• I have just took a look, and my first impression is that there is too much indent (like nested if / for). I'll take a deeper look on that implementation and the API soon :) – mfrachet Jan 24 '17 at 10:50
• You could factor all the calls in the if statements of getNeighborNodes with a private function maybe – mfrachet Jan 24 '17 at 10:52

First look, I'd change the if-chain in getNeighborNodes by defining directions, their offsets, and taking the same actions in a loop for all directions. Along the lines of:

enum Direction {
NORTH(-1, 0), // or the other way around for your coordinate system ;-)
SOUTH(1, 0),
EAST(0, 1),
WEST(0, -1);

public final int offsetX;
public final int offsetY;

private Direction(int offsetX, int offsetY) {
this.offsetX = offsetX;
this.offsetY = offsetY;
}
};

... (in getNeighborNodes):

for(Direction dir : Direction.values()) {
int newx = x + dir.offsetX;
int newy = y + dir.offsetY;
if(newx >= 0 && newx < width && newy >= 0 && newy < height) {
... do the logic
}
}


## Too many static methods

You have too many static methods. Specifically, some of the should not be static.

This is fine (it's a factory method):

public static Grid getGridFromMatrix(boolean[][] matrix) {


This is not fine:

public static char[][] getTextualRepresentation(Grid grid,
char freeCellCharacter,
char wallCharacter) {


The method getTextualRepresentation works on a Grid, is defined in Grid class and it leaves the Grid and all parameters un-mutated. I'd rather use grid.getTextualRepresentation(' ', '#') than Grid.getTextualRepresentation(grid, ' ', '#') which is very repetitive. Additionally the method code will refer to this and not to a grid reference, so it's more natural. Also, if Grid is ever sub-classed (to make a sparse grid?) it won't be able to override that static method, so you'd have several static methods, and of course the user is likely to use the wrong one or to be unable to chose!

The same goes for public static char[][] getTextualRepresentation(Grid grid) of course.

Hovering in the same area is :

public static String textualRepresentationToString(char[][] textMatrix);


Which looks just like an internal helper method, which should be therefore private. The way to expose this functionality would be to make it non-static as well:

public String textualRepresentationToString();


## Split responsibilities

I would argue that all three static methods are dealing with printing a Grid object, and would be better regouped under a GridPrinter Object. loadHorizontalBar is similarly guilty.

Such a GridPrinter can be loaded ahead of time with the prefered character encoding of the user, or made graphic etc. This would leave Grid with dealing solely with Grid logic, which is a better encapsulation.

This, of course, leads to the conclusion that Grid should stop representing its internals as an array of a representation (chars) and start using an array of logical entities like a Tile object (which incidentally would be able to say it is WALKABLE and SLOW and WET and HAS_DRAGON without running out of chars!)

It is the same for Router, which should use the same Tile logical objects as Grid. Additionally, GridNode could subclass that Tile.

This bit in Router:

for (Point p : path) {
if (grid.isWallCell(p.x, p.y)) {


...shows you're dearly missing that logical entity. Indeed a Tile could be a Point - it's good to reuse Java standard library. You should have a grid.isWall(cell) method somewhere.

## String splitting

Don't split Strings just to have a nice line return in your code (". Must be at " + "least "). It introduces operations tha can be confusing to the reader who thinks you're inserting an Object's toString() when you're not.

## Width checking

It is the first time I've seen this:

private void checkWidth(int width) {


Usually checkXCoordinate is sufficient. I'd replace it with a void checkRect(int x, int y, int width, int height) maybe?

## Weird loop style

Try to reduce indenting. Handle errors in an if, then proceed with the normal part outside it. This example:

    for (int y = 0; y < height; ++y) {
if (matrix[y] != null) {
for (int x = 0; x < matrix[y].length; ++x) {
if (matrix[y][x]) {
grid.setWallCell(x, y);
}
}
}
}


Can be advantageously reduced to:

    for (int y = 0; y < height; ++y) {
if (matrix[y] == null) {
continue; // Also makes it obvious you're *ignoring* the error here
}
for (int x = 0; x < matrix[y].length; ++x) {
if (matrix[y][x]) {
grid.setWallCell(x, y);
}
}
}


By the way, if given a matrix assumed to be rectangular, I ignored a missing line (which you did) or found an irregular width (which you did not check) I'd be worried, and might throw a tantrum Exception

## Don't repeat yourself

You're doing bounds checking again in Router class (checkTargetCoordinates). USe Grid's functions for that.

## The main method

That boolean[][] matrix is painful to see. I can't imagine typing it.

You have a getTextualRepresentation, surely you can make a Grid makeFromTextualRepresentation(String) ? That way you just draw the map naturally in a String (or a String[] might be easier), and it is analysed. Much easier on the eye.