Java program to find path from char ‘s’ to char ‘e’ in 2D char array.
For this map – “maze.txt”:
####################################################################### #s# # # # # # # # # ############### ## ########## ### # # # # # # # ########### ##### # # # # # # # # # ### ####### # # # # # # # # # # ########### # ####### ##### # # # ##### # # # # # # # # # # # # # ### ##### ########### # # # # # ### # # # ######### # ### ### # # # # # ### # # # # # # # # # # # # # # # # # # # ## # ###### #### #### # # # # # # ### # # # # # # # # # # # # # # # # # # # # ##### # ### # # # # # # # # # # # # #### # # # ##### # # # # # # # # # # # ##### ##### # ### # ## ########## # # # # # ##### ####### # # # # # # # # # # # # # # # # ### # ### # # ############# ################### ######### # # ##### # # # # # # # # # # # ##### # # # ### # # # # ##### #### ######### # # ####### #### # # # # ### # # # # # # # # # # # # ## # # # # ###### # # # # # # # # # ##### # ######## # ##### ### # # # ##### # # ## # # # # # # # # # # # # # # #### # # ### ###### # # ### # # # # ### ### ###### # # # ### # # ##### #### # # # # # # #### # # # ###### # # # # # # # # #### ##### # # # # ############# # ##### # # # # # # # # # # # # # # # # ## # ### # # # # # ######## # # #### # # # ### #### # # # # # ####### ### # # # # # # # # # # # # # # # # # ## # # # # # # ### ### ### ############ ############ ########## # # # # # # # # e# #######################################################################
the output is:
00000000000000000000000000000000000000000000000000000000000000000000000 000RRRRRRRRRRRRRRRRRRRRRRRRRRRRDLLLL0D0DLL0DLL0DLL0DLLLLLLL0RRRDLLLLLL0 0U000000000000000U00D0000000000D000U0D0D0U0D0ULL0U0D00000000000D00000D0 0U0DLLLLL0RRRRRD0U0RRRRRRRRRRRRD0D0ULL0D000D0000000D0RRRRD0D0D0D0D000D0 0U0D00000000000D0U0000000U00000RRD0U0U0RRRRRRRRRRRRD00000D0DLL0DLL000D0 0U0DLLLLLLLLLL0D0U0DLLLL0U0D00000D00000U00000000000D0DLL0D0D0U0D00000D0 0ULL000000000U0D000D000D0U0DL0RRDLLLLL0ULLL0DLLL000D0D0ULL0D0U0DLL000D0 0U0U0DLL0DLL0ULL000D0D0D0U0D00U0D000000U0000D0000DLLLL0U0U0D0U0D0D000D0 0U0U0D0U0D0U0U0U000D0D0D0U0RRRD0RRRD0D0U0RRRRDLL0D00000ULL0D000D0D0DLL0 0U0ULL0ULL0U0U0U000DLL0D0000U0RRU0RRRD0U00000D0U0D00000U0U0RRRRD0D0D0U0 0U00000U00000U0U000D0DLL0000000000000RRU0D0D0D0U0D00000U0000000D0D0D0U0 0ULLLL0U0RRRRULLLLLLLL0U0000RRRRRRRRRUUULL0DLL0ULLLL0RRU0D0DLLLLLL0D000 0U000U0D0U0000000000000U0000000000000000000D000000000U0ULL0D00000D0DLL0 0U0D0U0D0U0RRRRD0RRRRRRU0RRRRRDLLLLLLLLLLL0DLLLLLLLL00000U0RRRRD0D0D000 0U0D0ULL0U00000D0000U000000000DL0U0U0000000D0000U0ULL0RD0U0U000D0D0D0D0 0ULL0U0U0ULLLL0RRRD0U0RRRRDLL0D00U0U0DLLLLLL0D0RU000000D0U0U0D0D0D0D0D0 0U00000U0U00000000D0U00000D000D0RU0U0D00000U0D0U00DLLLLL0U0ULL0D0DLL0D0 0ULLLLLL0U0RRDLLLLL0U0D0D0DLLLL0U0000DLLLL0ULL0ULLL000U000000U0D0D000D0 0U0U0U000U000D000000U0D0D0D000U0ULLLLL0U00000U0000ULL0ULLLLL0U0D0RRRRD0 0U0000RRRULLLLLLLLLLL0DLL0RRD0U000000U0D0RRD0ULL0RU0U0U0U0U0000D00000D0 0U0RD0U0000000000000U0D00000D0U0DLL0RU0RRU0D0U0U0UU0U0U0U0ULLLLLLL0D0D0 0U00D0ULLLLLLLLLLLL000D0DLL0D0U0D0U00000000D0U0U0000U0U0U0D000U0000D0D0 0U0DL0U0000000U000U0DLL0D0ULL0U0D0ULLLLLLLLL0U0ULLL0U0U0U0D0RRULLLLL0D0 0U0D00U0DLL0D0U0D0U0D000D000U000D000000000000U000000000000D0000000000D0 0ULLL0ULL0ULL0ULL0ULLLLLLLL0ULLLLLLLLLLL0RRRRULLLLLLLLLLLLLLLLLLLLLLLL0 00000000000000000000000000000000000000000000000000000000000000000000000
To find path form every available point in the board to the ‘s’ – starting position, follow path by going to directions shown by tiles, until you have reached the begining:
‘L’ – go left
‘R’ – go right
‘U’ – go up
‘D’ – go down
Main.java
// 2018 TheFlyingKeyboard and released under MIT License // theflyingkeyboard.net public class Main { public static void main(String[] args) { MapLoader mapLoader = new MapLoader(); MapSaver mapSaver = new MapSaver(); BreadthFirstSearch breadthFirstSearch = new BreadthFirstSearch(mapLoader.load("maze.txt")); mapSaver.save("output.txt", breadthFirstSearch.search()); } }
MapSaver.java
import java.io.*; // 2018 TheFlyingKeyboard and released under MIT License // theflyingkeyboard.net public class MapSaver { public void save(String fileName, char[][] map){ Writer writer = null; try { writer = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(fileName), "utf-8")); for(int i = 0; i < map.length; ++i){ for(int j = 0; j < map[i].length; ++j){ writer.write(map[i][j]); } writer.write("\n"); } } catch (IOException ex) { ex.printStackTrace(); } finally { try { writer.close(); } catch (Exception ex) { ex.printStackTrace(); } } } }
MapLoader.java
import java.io.File; import java.util.ArrayList; import java.util.Scanner; // 2018 TheFlyingKeyboard and released under MIT License // theflyingkeyboard.net public class MapLoader { public char[][] load(String fileName){ char[][] map = null; try{ Scanner scanner = new Scanner(new File(fileName)); ArrayList<ArrayList<Character>> file = new ArrayList<ArrayList<Character>>(); String line; int counter = 0; while(scanner.hasNextLine()) { line = scanner.nextLine(); file.add(new ArrayList<Character>()); for(int i = 0; i < line.length(); ++i){ file.get(counter).add(line.charAt(i)); } ++counter; } map = new char[file.size()][file.get(0).size()]; for(int i = 0; i < file.size(); ++i){ for(int j = 0; j < file.get(i).size(); ++j){ map[i][j] = file.get(i).get(j); } } }catch (Exception e){ e.printStackTrace(); } return map; } }
Point2D.java
// 2018 TheFlyingKeyboard and released under MIT License // theflyingkeyboard.net public class Point2D { private double x; private double y; public Point2D(double x, double y) { this.x = x; this.y = y; } public double getX() { return x; } public double getY() { return y; } }
BreadthFirstSearch.java
import java.util.LinkedList; import java.util.Queue; // 2018 TheFlyingKeyboard and released under MIT License // theflyingkeyboard.net public class BreadthFirstSearch { private final char start = 's'; private final char empty = ' '; private final char exit = 'e'; private char[][] map; private char pathMap[][]; private Queue<Point2D> frontiers = new LinkedList<Point2D>(); private int currentX = 0; private int currentY = 0; public BreadthFirstSearch(char[][] map) { this.map = map; pathMap = new char[map.length][map[0].length]; //u - up, d - down, l - left, r - right, 0 - not set yet for(int i = 0; i < map.length; ++i){ for(int j = 0; j < map[i].length; ++j){ pathMap[i][j] = '0'; if(map[i][j] == start){ //Searching for starting position. currentX = j; currentY = i; } } } } public char[][] search(){ int counter = 0; while(true){ if(frontiers.size() != 0){ Point2D point = frontiers.poll(); currentX = (int)point.getX(); currentY = (int)point.getY(); }else{ if(counter != 0){ break; } } findFrontiers(); ++counter; } return pathMap; } private void findFrontiers(){ for(int i = 0; i < 4; ++i){ updatePathMap(calculateNextPoint(i), i); } } private Point2D calculateNextPoint(int i){ switch (i){ case 0: //Up return new Point2D(currentX, currentY - 1); case 1: //Left return new Point2D(currentX - 1, currentY); case 2: //Down return new Point2D(currentX, currentY + 1); case 3: //Right return new Point2D(currentX + 1, currentY); } return null; } private void updatePathMap(Point2D point2D, int i){ if(map[(int)point2D.getY()][(int)point2D.getX()] == empty || map[(int)point2D.getY()][(int)point2D.getX()] == exit){ frontiers.offer(point2D); map[(int)point2D.getY()][(int)point2D.getX()] = 'x'; switch (i){ case 0: //Up pathMap[(int)point2D.getY()][(int)point2D.getX()] = 'D'; break; case 1: //Left pathMap[(int)point2D.getY()][(int)point2D.getX()] = 'R'; break; case 2: //Down pathMap[(int)point2D.getY()][(int)point2D.getX()] = 'U'; break; case 3: //Right pathMap[(int)point2D.getY()][(int)point2D.getX()] = 'L'; break; } } } }