Java Breadth First Search 2D ASCII Grid Path Search

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;
            }
        }
    }
}