Java – Use BFS to find the number of possible paths to objects on the grid

I

have a matrix representing a grid and I want to find out all the possible positions where an object can be moved.

Objects can only move horizontally or vertically.

Let’s say the example below is the mesh I’m looking at, which is represented as a two-dimensional matrix. The object is *, 0 is the empty space that the object can move to, and 1 is the wall that the object cannot jump over or continue on.

If an object can only be moved horizontally or vertically, what is the best way to find all the possible moves for that object?

I want to print a message that says, “Objects can go in 9 places.” 9 is used for the example below, but I would expect it to work with any configuration of the grid below. So all I have to do is give the current coordinates of * and it will give me the number of possible locations it can move to.

It is important to note that the original location of * is not considered in the calculation, which is why for the example below, the message prints 9 instead of 10.

I have an isaWall method that tells me if the cell is a wall or not. The isaWall method is in the Cell class. Each cell is represented by its coordinates. I looked into using algorithms like BFS or DFS, but I don’t quite understand how to implement them in this case because I’m not very familiar with them. I’ve thought about using Cells as the node for the graph, but I’m not quite sure how to traverse the graph, because from the BFS and DFS examples I’ve seen on the web, you usually have a location for a target node and a source node (the source is *), but I don’t really have a target node in this case. Thank you very much for your help.

00111110
01000010
100*1100
10001000
11111000

Edit: I checked the recommended sites in the comments and tried to implement my own version. Unfortunately, it didn’t work. I knew I had to extend the “boundary”, I basically just translated the extension code into Java, but it still didn’t work. The website goes on to explain the process, but in my case, there is no destination unit to go to. I would appreciate examples or clearer explanations related to my case.

EDIT2: I’m still confused, can someone help?

While BFS/DFS is often used to find connections between the start and end points, they are not. BFS/DFS is a “graph traversal algorithm,” a fancy term that finds every point that can be reached from a starting point. DFS (Deep First Search) is easier to implement, so we’ll use it according to your needs (note: use BFS when you need to find out how far any point is from the starting point, and use DFS to go to every point when you just need to).

I

don’t know how your data is structured, but I’m assuming your map is an array of integers and defines some basic functionality (I made starting cell 2 for simplicity).

Map.java

import java.awt.*;

public class Map {
    public final int width;
    public final int height;

private final Cell[][] cells;
    private final Move[] moves;
    private Point startPoint;

public Map(int[][] mapData) {
        this.width = mapData[0].length;
        this.height = mapData.length;

cells = new Cell[height][width];
         define valid movements
        moves = new Move[]{
            new Move(1, 0),
            new Move(-1, 0),
            new Move(0, 1),
            new Move(0, -1)
        };

generateCells(mapData);
    }

public Point getStartPoint() {
        return startPoint;
    }

public void setStartPoint(Point p) {
        if (!isValidLocation(p)) throw new IllegalArgumentException("Invalid point");

startPoint.setLocation(p);
    }

public Cell getStartCell() {
        return getCellAtPoint(getStartPoint());
    }

public Cell getCellAtPoint(Point p) {
        if (!isValidLocation(p)) throw new IllegalArgumentException("Invalid point");

return cells[p.y][p.x];
    }

private void generateCells(int[][] mapData) {
        boolean foundStart = false;
        for (int i = 0; i < mapData.length; i++) {
            for (int j = 0; j < mapData[i].length; j++) {
                /*
                0 = empty space
                1 = wall
                2 = starting point
                 */
                if (mapData[i][j] == 2) {
                    if (foundStart) throw new IllegalArgumentException("Cannot have more than one start position");

foundStart = true;
                    startPoint = new Point(j, i);
                } else if (mapData[i][j] != 0 && mapData[i][j] != 1) {
                    throw new IllegalArgumentException("Map input data must contain only 0, 1, 2");
                }
                cells[i][j] = new Cell(j, i, mapData[i][j] == 1);
            }
        }

if (!foundStart) throw new IllegalArgumentException("No start point in map data");
         Add all cells adjacencies based on up, down, left, right movement
        generateAdj();
    }

private void generateAdj() {
        for (int i = 0; i < cells.length; i++) {
            for (int j = 0; j < cells[i].length; j++) {
                for (Move move : moves) {
                    Point p2 = new Point(j + move.getX(), i + move.getY());
                    if (isValidLocation(p2)) {
                        cells[i][j].addAdjCell(cells[p2.y][p2.x]);
                    }
                }
            }
        }
    }

private boolean isValidLocation(Point p) {
        if (p == null) throw new IllegalArgumentException("Point cannot be null");

return (p.x >= 0 && p.y >= 0) && (p.y < cells.length && p.x < cells[p.y].length);
    }

private class Move {
        private int x;
        private int y;

public Move(int x, int y) {
            this.x = x;
            this.y = y;
        }

public int getX() {
            return x;
        }

public int getY() {
            return y;
        }
    }
}

Cell.java

import java.util.LinkedList;

public class Cell {
    public final int x;
    public final int y;
    public final boolean isWall;
    private final LinkedList<Cell> adjCells;

public Cell(int x, int y, boolean isWall) {
        if (x < 0 || y < 0) throw new IllegalArgumentException("x, y must be greater than 0");

this.x = x;
        this.y = y;
        this.isWall = isWall;

adjCells = new LinkedList<>();
    }

public void addAdjCell(Cell c) {
        if (c == null) throw new IllegalArgumentException("Cell cannot be null");

adjCells.add(c);
    }

public LinkedList<Cell> getAdjCells() {
        return adjCells;
    }
}

Now let’s start writing our DFS function. DFS recursively touches each reachable unit once by following these steps:

1. Mark the current cell as accessed
2. Iterate through each adjacent cell

If the cell

3. has not been accessed, DFS is applied to the cell and the number of cells adjacent to the cell is added to the current count
4. Returns the number of cells adjacent to the current cell +1

You can see this visualization of here. With all the accessibility features we’ve already written, it’s pretty simple:

MapHelper.java

class MapHelper {
    public static int countReachableCells(Map map) {
        if (map == null) throw new IllegalArgumentException("Arguments cannot be null");
        boolean[][] visited = new boolean[map.height][map.width];

 subtract one to exclude starting point
        return dfs(map.getStartCell(), visited) - 1;
    }

private static int dfs(Cell currentCell, boolean[][] visited) {
        visited[currentCell.y][currentCell.x] = true;
        int touchedCells = 0;

for (Cell adjCell : currentCell.getAdjCells()) {
            if (!adjCell.isWall && !visited[adjCell.y][adjCell.x]) {
                touchedCells += dfs(adjCell, visited);
            }
        }

return ++touchedCells;
    }
}

That’s it! Let me know if you need any explanation about the code.