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

 



Java Breadth First Search 2D ASCII Grid Path Search
Tagged on:             

Leave a Reply

Your email address will not be published. Required fields are marked *

By continuing to use the site, you agree to the use of cookies. You can read more about it the Cookies&Privacy Policy Section Above. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this. You can read more about it the Cookies&Privacy Policy Section.

Close