logo
down
shadow

Maze solve and shortest path with Java BFS


Maze solve and shortest path with Java BFS

Content Index :

Maze solve and shortest path with Java BFS
Tag : java , By : Harvey
Date : November 28 2020, 03:01 PM

I think the issue was by ths following , Please review the following code. It lets you printout all paths found, as well as the shortest one found.
I did not change nor checked the search algorithm. I think it needs more work because I think it does not find the shortest path possible to each exit. I will look into it later.
class Maze {

    private static char NUMBER_SIGN = '#', DOT = '.', START = 'S';
    private static char EXIT = 'E', PATH = '1';
    private static Node[][] nodes;
    private static Node start;
    private static boolean[][] visited; //no need to use Boolean
    //exit holds the same information as Node.blocked. No need to duplicate
    //private static boolean[][] blocked;
    //exit holds the same information as Node.exit. No need to duplicate
    //private static boolean[][] exits;

    private static int mazeWidth, mazeHeight, startH, startW; //use meaningful names
    private static List<List<Node>> paths;

    public static void main(String args[]) {

        mazeWidth = 21;//use meaningful names
        mazeHeight = 21;
        startH = 9; startW = 10;

        String[] mazeData = getMazeData()  ;
        makeMaze(mazeData);
        drawMaze(); //draw maze as built from input data

        List<Node> result = new ArrayList<>();
        paths = new ArrayList<>();

        findExits(start, nodes, visited, mazeWidth, mazeHeight, result, paths);

        if (!result.isEmpty()) {
            Collections.sort(result, new Comparator<Node>() {
                @Override
                public int compare(Node o1, Node o2) {
                    if (Integer.compare(o1.x, o2.x) == 0) {
                        return Integer.compare(o1.y, o2.y);
                    } else {
                        return Integer.compare(o1.x, o2.x);
                    }
                }
            });
        }
        drawAllPaths(); // see all paths found
        List<Node> shortestPath = getShortestPath();
        drawShortestPath(shortestPath);
    }

    private static void drawMaze() {

        System.out.println("***************************************************");
        System.out.println("Maze as defined by input");
        System.out.println("***************************************************");
        drawMaze(null);
    }

    private static void drawAllPaths() {

        for (List<Node> path : paths) {
            System.out.println("***************************************************");
            System.out.println("Path to exit ["
            + path.get(0).x + "," + path.get(0).y + "] length:"+ path.size());
            System.out.println("***************************************************");
            drawMaze(path);
        }
    }

    private static void drawShortestPath(List<Node> path) {

        System.out.println("***************************************************");
        System.out.println("Shortest path is to exit ["
        + path.get(0).x + "," + path.get(0).y + "] length:"+ path.size());
        System.out.println("***************************************************");
        drawMaze(path);
    }

    private static void drawMaze(List<Node> path) {

        for(Node[] row : nodes ) {

            for(Node node : row) {

                char c = node.getGraphics();
                if ((path != null) && path.contains(node)) {c = PATH;}
                System.out.print(c);
            }
            System.out.println("");
        }
    }

    private static void makeMaze(String[] mazeData) {

        nodes = new Node[mazeHeight][mazeWidth];
        visited = new boolean[mazeHeight][mazeWidth];

        for (int height = 0; height < mazeHeight; height++) {
            String row = mazeData[height];
            for (int width = 0; width < mazeWidth; width++) {
                Node node = new Node(height, width);
                node.blocked = row.charAt(width) == NUMBER_SIGN;
                visited[width][height] = false;
                node.exit = (!node.blocked) && ((height == (mazeHeight - 1)) ||
                                (width == (mazeWidth - 1)) || (height == 0) || (width == 0));
                nodes[height][width] = node;
            }
        }
        start = nodes[startH][startW];//no need to set it in the loop
    }

    //use boolean instead of Boolean
    private static void findExits(Node start, Node[][] nodes,
            boolean[][] visited, int W, int H, List<Node> result, List<List<Node>> paths) {

        int x = start.x;
        int y = start.y;
        visited[x][y] = true;
        if (start.exit) {
            result.add(start);
            visited[x][y] = false;
            List<Node> path = new ArrayList<>();
            while (start.parent != null) {
                path.add(start);
                start = start.parent;
            }
            path.add(start);
            paths.add(path);
        }
        //TOP
        if ((y - 1) >= 0) {
            if (!visited[x][y - 1] && (!nodes[x][y - 1].blocked)) {
                nodes[x][y - 1].parent = start;
                findExits(nodes[x][y - 1], nodes, visited, W, H, result, paths);
            }
        }
        //BOT
        if ((y + 1) < H) {
            if (!visited[x][y + 1] && (!nodes[x][y + 1].blocked)) {
                nodes[x][y + 1].parent = start;
                findExits(nodes[x][y + 1], nodes, visited, W, H, result, paths);
            }
        }
        //LEFT
        if ((x - 1) >= 0) {
            if (!visited[x - 1][y] && (!nodes[x - 1][y].blocked)) {
                nodes[x - 1][y].parent = start;
                findExits(nodes[x - 1][y], nodes, visited, W, H, result, paths);
            }
        }
        //RIGHT
        if ((x + 1) < W) {
            if (!visited[x + 1][y] && (!nodes[x + 1][y].blocked)) {
                nodes[x + 1][y].parent = start;
                findExits(nodes[x + 1][y], nodes, visited, W, H, result, paths);
            }
        }
    }

    public static class Node {

        public int x, y;
        boolean blocked = false;
        boolean exit = false;
        Node parent = null;

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

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final Node other = (Node) obj;
            if (x != other.x) {
                return false;
            }
            if (y != other.y) {
                return false;
            }
            return true;
        }

        //it is simpler to have Node return its graphic representation
        char getGraphics() {

            char c = blocked ? NUMBER_SIGN : DOT;
            if(equals(start)) { c=START;}
            else if (exit) { c=EXIT;}

            return c;
        }
    }

    private static List<Node> getShortestPath() {
        //initialize with an arbitrary path
        List<Node> shortest = paths.get(0);
        for (List<Node> path : paths) {
            if(path.size() < shortest.size()) {
                shortest = path;
            }
        }
        return shortest;
    }

    private static String[] getMazeData() {

        return  new String[] {
                "##########.##########",
                "..#...........#.....#",
                "#.#.#########.#.###.#",
                "#...#.........#.#...#",
                "###############.#.###",
                "#.....#.......#.#...#",
                "#.#######.###.#.#.#.#",
                "#...#...#...#...#.#..",
                "###.###.###.###.#.#.#",
                "#.#.#.#...#.#...#.#.#",
                "#.#.#.#.#.#.#.###.#.#",
                "#...#.#.#.#.#...#.#.#",
                "#####.###.#.#####.###",
                "#.#.......#.#...#...#",
                "#.#.#######.#.#.###.#",
                "#.#.#...#...#.#.#...#",
                "#.#.###.#.#####.#####",
                "#.#.................#",
                "#.##.####.#########.#",
                "#.........#..........",
                "####.######.#########"
                };
    }
}
class Maze {

    private static char NUMBER_SIGN = '#', DOT = '.', START = 'S';
    private static char EXIT = 'E', PATH = '1';
    private static Node[][] nodes;
    private static Node startNode;
    private static boolean[][] visited; //no need to use Boolean
    //exit holds the same information as Node.blocked. No need to duplicate
    //private static boolean[][] blocked;
    //exit holds the same information as Node.exit. No need to duplicate
    //private static boolean[][] exits;

    private static int mazeRows, mazeCols, startRow, startCol; //use meaningful names
    private static List<List<Node>> paths;

    public static void main(String args[]) {

        mazeCols = 21; mazeRows = 21;//use meaningful and consistent names
        startRow = 9; startCol = 10;        //better keep h,w or height,width all over

        String[] mazeData = getMazeData()  ;
        makeMaze(mazeData);
        drawMaze(); //draw maze as built from input data
        paths = new ArrayList<>();
        findExits(startNode);
        drawAllPaths(); // print all paths found
        List<Node> shortestPath = getShortestPath();
        drawShortestPath(shortestPath);
    }

    private static void drawMaze() {

        System.out.println("*****************************************");
        System.out.println("Maze as defined by input");
        System.out.println("*****************************************");
        drawMaze(null);
    }

    private static void drawAllPaths() {

        for (List<Node> path : paths) {
            System.out.println("*****************************************");
            System.out.println("Path to exit ["
                    + path.get(0).row + "," + path.get(0).col + "] length:"+ path.size());
            System.out.println("*****************************************");
            drawMaze(path);
        }
    }

    private static void drawShortestPath(List<Node> path) {

        System.out.println("*****************************************");
        System.out.println("Shortest path is to exit ["
                + path.get(0).row + "," + path.get(0).col + "] length:"+ path.size());
        System.out.println("*****************************************");
        drawMaze(path);
    }

    private static void drawMaze(List<Node> path) {

        for(Node[] row : nodes ) {
            for(Node node : row) {
                char c = node.getGraphics();
                //overwrite c if node is in path
                if ( (c != EXIT) && ( c != START ) &&
                        (path != null) && path.contains(node)) {c = PATH;}
                System.out.print(c);
            }
            System.out.println("");
        }
    }

    private static void makeMaze(String[] mazeData) {

        nodes = new Node[mazeRows][mazeCols];
        visited = new boolean[mazeRows][mazeCols];

        for (int rowIndex = 0; rowIndex < mazeRows; rowIndex++) {
            String row = mazeData[rowIndex];
            for (int colIndex = 0; colIndex < mazeCols; colIndex++) {
                Node node = new Node(rowIndex, colIndex);
                node.blocked = row.charAt(colIndex) == NUMBER_SIGN;
                visited[rowIndex][colIndex] = false;
                node.exit = (!node.blocked) && ((rowIndex == (mazeRows - 1)) ||
                        (colIndex == (mazeCols - 1)) || (rowIndex == 0) || (colIndex == 0));
                nodes[rowIndex][colIndex] = node;
            }
        }
        startNode = nodes[startRow][startCol];//no need to set it in the loop
    }

    //use boolean instead of Boolean
    private static void findExits(Node node) {

        int row = node.row;
        int col = node.col;

        if(visited[row][col]) { return; }

        if (node.exit) {
            List<Node> path = new ArrayList<>();
            while (node.parent != null) {
                path.add(node);
                node = node.parent;
            }
            path.add(node);
            paths.add(path);
            return; //do not continue to check exit neighbors
        }

        //LEFT
        if ((col - 1) >= 0) {
            Node testNode = nodes[row][col - 1];
            //the following if statement repeats for all directions
            //better put in a method
            if ((testNode.parent == null) && ! testNode.blocked) {
                testNode.parent = node; //parent ! null indicates that cell is tested
                findExits(testNode);
                testNode.parent = null; //set back to null: test finished
            }
        }

        //RIGHT
        if ((col + 1) < mazeCols) {
            Node testNode = nodes[row][col + 1];
            if ((testNode.parent == null) && ! testNode.blocked) {
                testNode.parent = node;
                findExits(testNode);
                testNode.parent = null;
            }
        }

        //TOP
        if ((row - 1) >= 0) {
            Node testNode = nodes[row-1][col];
            if ((testNode.parent == null) && ! testNode.blocked) {
                testNode.parent = node;
                findExits(testNode);
                testNode.parent = null;
            }
        }

        //BOTTOM
        if ((row + 1) < mazeRows) {
            Node testNode = nodes[row+1][col];
            if ((testNode.parent == null) && ! testNode.blocked) {
                testNode.parent = node;
                findExits(testNode);
                testNode.parent = null;
            }
        }

        visited[row][col] = true; //mark as visited after all directions explored
        node.parent = null;
    }

    public static class Node {

        public int row, col;
        boolean blocked = false;
        boolean exit = false;
        Node parent = null;

        public Node(int row, int col) {
            this.row = row;
            this.col = col;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final Node other = (Node) obj;
            if (row != other.row) {
                return false;
            }
            if (col != other.col) {
                return false;
            }
            return true;
        }

        //it is simpler to have Node return its graphic representation
        char getGraphics() {

            char c = blocked ? NUMBER_SIGN : DOT;
            if(equals(startNode)) { c=START;}
            else if (exit) { c=EXIT;}

            return c;
        }

        @Override
        public String toString() {

            return "Node " + row +"-"+ col +" ("+ getGraphics() + ")";
        }
    }

    private static List<Node> getShortestPath() {
        //initialize with an arbitrary path
        List<Node> shortest = paths.get(0);
        for (List<Node> path : paths) {
            if(path.size() < shortest.size()) {
                shortest = path;
            }
        }
        return shortest;
    }

    private static String[] getMazeData() {

        return  new String[] {
                "##########.##########",
                "..#...........#.....#",
                "#.#.#########.#.###.#",
                "#...#.........#.#...#",
                "###############.#.###",
                "#.....#.......#.#...#",
                "#.#######.###.#.#.#.#",
                "#...#...#...#...#.#..",
                "###.###.###.###.#.#.#",
                "#.#.#.#...#.#...#.#.#",
                "#.#.#.#.#.#.#.###.#.#",
                "#...#.#.#.#.#...#.#.#",
                "#####.###.#.#####.###",
                "#.#.......#.#...#...#",
                "#.#.#######.#.#.###.#",
                "#.#.#...#...#.#.#...#",
                "#.#.###.#.#####.#####",
                "#.#.................#",
                "#.##.####.#########.#",
                "#.........#..........",
                "####.######.#########"
        };
    }
}

Comments
No Comments Right Now !

Boards Message :
You Must Login Or Sign Up to Add Your Comments .

Share : facebook icon twitter icon

How do I start making a shortest path maze solver from a maze matrix in Java?


Tag : java , By : kbrust
Date : March 29 2020, 07:55 AM
Hope this helps One of the most widely used and effective pathfinding algorithms is the A* Pathfinding Algorithm Whilst this is probably surplus to your needs, it is a often used in games and other forms of computer science, and is scalable to your needs.

Java Maze shortest path 2d int array


Tag : java , By : Mike
Date : March 29 2020, 07:55 AM
This might help you I just looked at the wikipedia article on Dijkstra's Algorithm.
Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes. Mark all nodes unvisited. Set the initial node as current. Create a set of the unvisited nodes called the unvisited set consisting of all the nodes except the initial node. For the current node, consider all of its unvisited neighbors and calculate their tentative distances. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6+2=8. If this distance is less than the previously recorded distance, then overwrite that distance. Even though a neighbor has been examined, it is not marked as visited at this time, and it remains in the unvisited set. When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again; its distance recorded now is final and minimal. If the unvisited set is empty, then stop. The algorithm has finished. Set the unvisited node marked with the smallest tentative distance as the next "current node" and go back to step 3.

Kth shortest path in a given MAZE c++


Tag : development , By : user181945
Date : March 29 2020, 07:55 AM
like below fixes the issue I have a dynamic programming solution for this.
Use a 3D matrix cost[M][N][K] where cost[x][y][i] will represent the ith shortest path to reach cell (x, y) from the top right hand corner.
for (int x = 0; x < m; x++) {
    for (int y = 0; y < n; y++) {
       //Process
    }
}

Java Maze Shortest Path misunderstanding


Tag : java , By : Munir
Date : March 29 2020, 07:55 AM
I think the issue was by ths following , Here is code, using recursion, I am trying to solve maze with shortest pathing, but it is getting solved with a longer way and I don't really understand why. Here is code of recursion : , Try this, it should work and go straight to finish:
public boolean findPath(int row, int col) {
  board[row][col].visit();

  if ((col == 7) && (row == 7)) {
    board[row][col].selectCell();
    return true;
  }

  if ((row < 7) && !board[row + 1][col].marked() &&
      !board[row + 1][col].blocked() && !board[row + 1][col].visited()) {
    block(row, col);

    if (findPath(row + 1, col)) {
      board[row][col].selectCell();
      return true;
    }

    unblock(row, col);
  }

  if ((col > 0) && !board[row][col - 1].marked() &&
      !board[row][col - 1].blocked() && !board[row][col - 1].visited()) {
    block(row,col);

    if (findPath(row, col - 1)) {
      board[row][col].selectCell();
      return true;
    }

    unblock(row,col);
  }

  if ((col < 7) && !board[row][col + 1].marked() &&
      !board[row][col + 1].blocked() && !board[row][col + 1].visited()) {
    block(row,col);

    if (findPath(row, col + 1)) {
      board[row][col].selectCell();
      return true;
    }

    unblock(row,col);
  }
  if ((row > 0) && !board[row - 1][col].marked() &&
      !board[row - 1][col].blocked() && !board[row - 1][col].visited()) {
    block(row, col);

    if (findPath(row - 1, col)) {
      board[row][col].selectCell();
      return true;
    }

    unblock(row, col);
  }

  return false;
}

shortest path through a maze


Tag : java , By : John Phipps
Date : March 29 2020, 07:55 AM
Related Posts Related QUESTIONS :
  • Unexpected Output while retrieving Data from mongodb and displaying in a csv file?
  • Algorithm for searching a value in two arrays
  • How to avoid casting with generic return values?
  • Java/RegEx - Negation of pattern not working
  • How to split a string to non empty words if it might include a separator like tab on first place
  • Supplier<Sequence<String>> cannot be iterated more than once
  • Why there is only one thread can actually started in @PostConstruct method?
  • Manage CompletionStage inside of Netty handler
  • Url Problem while Developing on Localhost and deploy on Remote Virtual Server
  • How to identify the missing type id in Jackson error?
  • android data binding error: cannot find symbol
  • Spring Boot application with a jar dependency does not run after maven build
  • Spring Data JPA query , filter ? search engine ? JPQL?
  • Why LiveData returns null in ViewModel?
  • what this line of code mean....new URLClassLoader(new URL[0],getClass().getClassLoader());
  • Why do need to use new Random() instead of just Random Randomnum?
  • I want to access zk components from the java file
  • How do I cast FieldValue.serverTimestamp() to Kotlin/Java Date Class
  • Insertion Sort Double Array with User Input - JAVA
  • Creating 2 dimesional array with user input and find sum of specific columns
  • can not get Advertising ID Provider in android
  • Convert list of Objects to map of properties
  • How to represent an undirected weighted graph in java
  • Return values as array from collection
  • ByteBuddy generic method return cast to concrete type
  • ImageView hides the round corners of the parent
  • Is there a way to find setter method by its getter method or vice versa in a class?
  • Get aggregated list of properties from list of Objects(Java 8)
  • Unable to find a document in Mongodb where exact date match in java
  • UsernamePasswordAuthenticationFilter skips success handler
  • Use Java filter on stream with in a stream filter
  • Default Login not successful in spring boot 2.1.7
  • Adding key value pairs from a file to a Hashmap
  • Rub regex: matching a char except when after by another char
  • Convert Base64 String to String Array
  • Escape Unicode Character 'POPCORN' to HTML Entity
  • An empty JSON field which is a boolean/nullable field in Java model, is getting converted as null
  • Mongo java driver cannot find public constructor for interface
  • How to unit test writing a file to AWS Lambda output stream?
  • How to make a GitHub GraphQL API Call from Java
  • What's the difference between @ComponentScan and @Bean in a context configuration?
  • Expected class or package adding a view using a class
  • can be delete of a element in a static array be O(1)?
  • Instance variable heap or stack ? ( with specific example)
  • Assert progress of ProgressBar in Espresso test
  • How to detect if gson.fromjson() has excess elements
  • I cant generate the proper code to select the a specific filter on a BI dashboard I am working on
  • How to Inject Dependencies into a Servlet Filter with Spring Boot Filter Registration Bean?
  • Thrift types as a Generic
  • Effective algorithm to random 4 unique integers less than a big max such as 100_000
  • Combining or and negation in Java regex?
  • Unable to instantiate default tuplizer Exception
  • Multi-tenant migration to work with quarkus
  • Ignite persisting a Set: Cannot find metadata for object with compact footer
  • Maven cannot resolve Jacob dependency using eclipse
  • testcontainers oracle database container starts before database user is created
  • Launching two spring boot apps in integration test
  • Is there a way to add a HashMap's value that is a integer array into a ArrayList?
  • Is there any way that I can get a parameter in paintComponent?
  • Empty stack with one recursive method and one iterative method
  • shadow
    Privacy Policy - Terms - Contact Us © scrbit.com