1
\$\begingroup\$

Please help review my code.

public class Maze {
    // question: give a maze. Find shortest path from left top corner to right bottom corner.
    // 1 is wall. cannot go thru.
    int minFoundLen = Integer.MAX_VALUE;
    int m = 0;
    int n = 0;
    public void findPath(int[][] mazePlan){
        if(mazePlan.length == 0) return;

        m = mazePlan.length;
        n = mazePlan[0].length;
        int[][] path = new int[m][n];


        helper(mazePlan, 0, 0, 0,path);
        System.out.println("shortest path is " + minFoundLen);
    }

    private void helper(int[][] maze, int x, int y, int pathLen,int[][] path){
        if(x < 0 || y < 0 || x >= m || y >= n){
            return;
        }
        if(path[x][y]!=0){
            return;
        }
        if(maze[x][y] != 0){
            return;
        }
        if(x == m-1 && y == n-1){
            minFoundLen = Math.min(minFoundLen, pathLen);
            return;
        }
        path[x][y] = 1;
        helper(maze, x+1,y,pathLen+1,path);
        helper(maze, x-1,y,pathLen+1,path);
        helper(maze, x,y+1,pathLen+1,path);
        helper(maze, x,y-1,pathLen+1,path);
        path[x][y] = 0;

    }
    public static void main(String[] args){
        int[][] mazePlan = {
        {0,1,0,0,0},
        {0,0,0,1,0},
        {0,0,0,0,0},
        {1,1,1,0,0},
        {0,0,0,0,0}
        };

        Maze maze = new Maze();
        maze.findPath(mazePlan);
    }
}
\$\endgroup\$
  • \$\begingroup\$ This looks like a weird, informal implementation of Dijkstra’s Algorithm. Is that what you were trying to achieve? \$\endgroup\$ – Zack May 6 '16 at 5:09
3
\$\begingroup\$

1 Algorithm

This is not Dijkstra's algorithm and that is not breadth-first search either. It's an unweighted brute-force shortest path algorithm. Basically, you generate all possible paths from the source node (top-left cell) to the target node (bottom-right) cell.

On my machine (2.5 GHz) the following maze takes about 300 milliseconds to solve:

int[][] mazePlan = {
    {0,1,0,0,0,0,0,0},
    {0,0,0,1,0,0,0,0},
    {0,0,0,0,0,0,0,0},
    {1,1,1,0,0,0,0,0},
    {0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0},
};

2 Coding

You should rename the fields minFoundLen, n and m to something like shortestPathLengthSoFar mazeHeight and mazeWidth, respectively. Also, you do not have to initialize m and n to zero; Java initializes integer fields to zero by default.

Taking into consideration what you do with int[][] path, I suggest you rename it to boolean[][] visited.

System.out.println("shortest path is " + minFoundLen);

It's not funky to print the result of an algorithm to standard output; instead, return the actual result, and let the caller of the algorithm do whatever he/she wants.

You can always store maze and visited in the fields of your object; that way, helper asks only three arguments instead of five.

if(path[x][y]!=0){
    return;
}
  1. There should be one space before and after a binary operator.
  2. There should be one space before and after a parenthesized expression.

So, combining the two above points you should rather write:

if (path[x][y] != 0) {
    return;
}

You should also separate "logical blocks" by a single empty line; like this:

    if (maze[x][y] != 0) {
        return;
    }

    if (x == m - 1 && y == n - 1) {
        minFoundLen = Math.min(minFoundLen, pathLen);
        return;
    }

    path[x][y] = 1;

    helper(maze, x + 1, y, pathLen + 1, path);
    helper(maze, x - 1, y, pathLen + 1, path);
    helper(maze, x, y + 1, pathLen + 1, path);
    helper(maze, x, y - 1, pathLen + 1, path);

    path[x][y] = 0;

And don't forget that you should have a space after any comma.

3 Alternative impelmentation

I have gathered all the points and used breadth-first search for solving the maze. That it how it might look:

Maze.java:

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

public class Maze {

    private static final boolean CELL_OCCUPIED = true;

    private final boolean[][] maze;

    public Maze(final boolean[][] maze) {
        Objects.requireNonNull(maze, "The input maze is null.");

        final int numberOfRows = maze.length;

        if (numberOfRows == 0) {
            throw new IllegalArgumentException("The input maze is empty.");
        }

        int numberOfColumns = 0;

        for (int row = 0; row < maze.length; ++row) {
            numberOfColumns = Math.max(numberOfColumns, maze[row].length);
        }

        this.maze = new boolean[numberOfRows][numberOfColumns];

        for (int row = 0; row < numberOfRows; ++row) {
            for (int column = 0;
                     column < Math.min(numberOfColumns, maze[row].length);
                     column++) {
                this.maze[row][column] = maze[row][column];
            }
        }
    }

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

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

    public boolean cellIsFree(final Point p) {
        return cellIsFree(p.x, p.y);
    }

    public boolean cellIsWithinMaze(final Point p) {
        return p.x >= 0 && p.x < getWidth() && p.y >= 0 && p.y < getHeight();
    }

    public boolean cellIsTraversible(final Point p) {
        return cellIsWithinMaze(p) && cellIsFree(p);
    }

    public boolean cellIsFree(final int x, final int y) {
        checkXCoordinate(x);
        checkYCoordinate(y);
        return maze[y][x] != CELL_OCCUPIED;
    }

    public String withPath(final List<Point> path) {
        final char[][] matrix = new char[getHeight()][getWidth()];

        for (int i = 0; i < matrix.length; ++i) {
            for (int j = 0; j < matrix[0].length; ++j) {
                matrix[i][j] = maze[i][j] ? 'x' : '.';
            }
        }

        for (final Point p : path) {
            matrix[p.y][p.x] = 'o';
        }

        final StringBuilder sb = new StringBuilder();

        sb.append(new String(matrix[0]));

        for (int i = 1; i < matrix.length; ++i) {
            sb.append('\n');
            sb.append(new String(matrix[i]));
        }

        return sb.toString();
    }

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

        if (x >= maze[0].length) {
            throw new IndexOutOfBoundsException(
                    "The x-coordinate is too large (" + x + 
                    "). The amount of columns in this maze is " + 
                    maze[0].length + ".");
        }
    }

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

        if (y >= maze.length) {
            throw new IndexOutOfBoundsException(
                    "The y-coordinate is too large (" + y + 
                    "). The amount of rows in this maze is " + 
                    maze.length + ".");
        }
    }
}

MazePathFinder.java:

package review;

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

public class MazePathFinder {

    private Maze maze;
    private Point source;
    private Point target;
    private boolean[][] visited;
    private Map<Point, Point> parents;

    public MazePathFinder() {}

    private MazePathFinder(final Maze maze, 
                           final Point source, 
                           final Point target) {
        Objects.requireNonNull(maze, "The input maze is null.");
        Objects.requireNonNull(source, "The source node is null.");
        Objects.requireNonNull(target, "The target node is null.");

        this.maze = maze;
        this.source = source;
        this.target = target;

        checkSourceNode();
        checkTargetNode();

        this.visited = new boolean[maze.getHeight()][maze.getWidth()];
        this.parents = new HashMap<>();
        this.parents.put(source, null);
    }

    public List<Point> findPath(final Maze maze, 
                                final Point source, 
                                final Point target) {
        return new MazePathFinder(maze, source, target).compute();
    }

    private List<Point> compute() {
        final Queue<Point> queue = new ArrayDeque<>();
        final Map<Point, Integer> distances = new HashMap<>();

        queue.add(source);
        distances.put(source, 0);

        while (!queue.isEmpty()) {
            // Removes the head of the queue.
            final Point current = queue.remove();

            if (current.equals(target)) {
                return constructPath();
            }

            for (final Point child : generateChildren(current)) {
                if (!parents.containsKey(child)) {
                    parents.put(child, current);
                    // Appends 'child' to the end of this queue.
                    queue.add(child);
                }
            }
        }

        // null means that the target node is not reachable
        // from the source node.
        return null;
    }

    private List<Point> constructPath() {
        Point current = target;
        final List<Point> path = new ArrayList<>();

        while (current != null) {
            path.add(current);
            current = parents.get(current);
        }

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

    private Iterable<Point> generateChildren(final Point current) {
        final Point north = new Point(current.x, current.y - 1);
        final Point south = new Point(current.x, current.y + 1);
        final Point west = new Point(current.x - 1, current.y);
        final Point east = new Point(current.x + 1, current.y);

        final List<Point> childList = new ArrayList<>(4);

        if (maze.cellIsTraversible(north)) {
            childList.add(north);
        }

        if (maze.cellIsTraversible(south)) {
            childList.add(south);
        }

        if (maze.cellIsTraversible(west)) {
            childList.add(west);
        }

        if (maze.cellIsTraversible(east)) {
            childList.add(east);
        }

        return childList;
    }

    private void checkSourceNode() {
        checkNode(source, 
                  "The source node (" + source + ") is outside the maze. " +
                  "The width of the maze is " + maze.getWidth() + " and " +
                  "the height of the maze is " + maze.getHeight() + ".");

        if (!maze.cellIsFree(source.x, source.y)) {
            throw new IllegalArgumentException(
                    "The source node (" + source + ") is at a occupied cell.");
        }
    }

    private void checkTargetNode() {
        checkNode(target, 
                  "The target node (" + target + ") is outside the maze. " +
                  "The width of the maze is " + maze.getWidth() + " and " +
                  "the height of the maze is " + maze.getHeight() + ".");

        if (!maze.cellIsFree(target.x, target.y)) {
            throw new IllegalArgumentException(
                    "The target node (" + target + ") is at a occupied cell.");
        }
    }

    private void checkNode(final Point node, final String errorMessage) {
        if (node.x < 0 
                || node.x >= maze.getWidth()
                || node.y < 0
                || node.y >= maze.getHeight()) {
            throw new IllegalArgumentException(errorMessage);
        }
    }

    public static void main(String[] args) {
        int[][] mazePlan = {
            {0,1,0,0,0,0,0,0},
            {0,0,0,1,0,0,0,0},
            {0,0,0,0,0,0,0,0},
            {1,1,1,0,0,0,0,0},
            {0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0},
        };

        boolean[][] maze2 = new boolean[mazePlan.length][mazePlan[0].length];

        for (int i = 0; i < maze2.length; ++i) {
            for (int j = 0; j < maze2[i].length; ++j) {
                maze2[i][j] = mazePlan[i][j] > 0;
            }
        }

        final Maze maze = new Maze(maze2);
        final Point source = new Point(); // Same as new Point(0, 0):
        final Point target = new Point(7, 5);


        long startTime = System.nanoTime();
        final List<Point> path = new MazePathFinder().findPath(maze, 
                                                               source, 
                                                               target);
        long endTime  = System.nanoTime();

        System.out.printf("BFS maze finder in %d milliseconds.\n",
                          (endTime - startTime) / 1_000_000L);

        System.out.println("Shortest path length: " + (path.size() - 1));
        System.out.println(maze.withPath(path));
    }
}

Hope that helps.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.