Maze Solver

The Maze class contains the JavaFX code to create a window and display the maze, which is represented as a 2D array of char. 'X' represents a wall and ' ' represents a blank space. There is a player, represented as an that can move through the maze. The program exits when the player reaches the . The Maze class only handles display of the maze. The Maze class works with the MazeSolver class. The purpose of the MazeSolver class is to have logic to actually move the player to the exit. There are methods in the MazeSolver class to help achieve this goal, such as methods to move the player or check if there is a wall in either the up, down, left, or right direction. The actual implementation of a maze solver is made by creating a child class of MazeSolver. There are two examples provided in the zip file. The first, HumanMazeSolver.java, expects a human to pick the direction to move the player by pressing the arrow keys. The second, RandomMazeSolver.java, picks a random direction to move the player. By creating different child classes of MazeSolver for each type of solution we can take advantage of the interface of code between the Maze and MazeSolver class, but use different implementations. In this case, it becomes just a one-line change to go from a Human maze solver to a computer random maze solver. (This organization of code has a special name, it is called the Bridge pattern or the Handle/Body pattern).

To do:

1. Study and experiment with the code to see how it works. Swap the comments in Maze.java to use the RandomMazeSolver class instead of HumanMazeSolver.

2. Based on RandomMazeSolver, create a new class that is also derived from MazeSolver. The new class should pick a random direction and keep moving in that direction until it hits a wall. When a wall is hit, pick a new random direction to move and repeat moving in that direction until a wall is hit.

3. Modify the Maze class to try out your new maze solving algorithm.

Maze.java

This is the main class that displays a maze represented in a 2d

array, shown below. It displays the maze in a graphical window.

* You can ignore most of the code in here for Homework #5 except * the line in the start method that creates a Maze solver object. * You might like to look through this code to see how it works, though. *******************************************************************/ import javafx.application.Application; import javafx.stage.Stage; import javafx.scene.canvas.Canvas; import javafx.scene.Scene; import javafx.scene.Group; import javafx.scene.canvas.GraphicsContext; import javafx.scene.paint.Color; import javafx.scene.image.Image;

public class Maze extends Application {

public static final char WALL = 'X'; public static final char BLANK = ' '; public static final int SIZE = 20; // Maze is 20x20 public static final int SPRITE_SIZE = 30; // 30x30 pixel square for each cell in the maze // In the line below I hard-coded the maze with X's for walls and blanks for spaces public static char[][] maze = { {'X','X','X','X','X','X','X','X','X','X','X','X','X','X','X','X','X','X','X','X'}, {'X',' ','X',' ',' ',' ',' ','X',' ',' ',' ',' ',' ','X',' ',' ',' ',' ',' ','X'}, {'X',' ','X',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','X',' ',' ',' ',' ',' ','X'}, {'X',' ','X',' ',' ',' ',' ',' ','X','X','X','X',' ',' ',' ',' ',' ',' ',' ','X'}, {'X',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','X',' ',' ',' ',' ',' ',' ',' ','X'}, {'X','X','X','X','X',' ',' ',' ',' ',' ',' ','X',' ',' ',' ',' ',' ',' ',' ','X'}, {'X',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','X',' ',' ',' ',' ',' ',' ',' ','X'}, {'X',' ',' ',' ',' ',' ',' ','X',' ',' ',' ',' ',' ',' ','X','X','X','X',' ','X'}, {'X',' ',' ',' ',' ',' ',' ','X',' ',' ',' ','X',' ',' ',' ',' ',' ','X',' ','X'}, {'X',' ','X','X',' ',' ','X','X',' ',' ',' ','X',' ',' ','X',' ',' ','X',' ','X'}, {'X',' ',' ',' ','X',' ',' ',' ',' ',' ',' ','X',' ',' ','X',' ',' ','X',' ','X'}, {'X',' ',' ',' ','X',' ',' ',' ','X','X',' ','X',' ',' ','X',' ',' ','X',' ','X'}, {'X','X','X',' ','X',' ',' ',' ',' ',' ',' ',' ',' ',' ','X','X',' ','X',' ','X'}, {'X',' ',' ',' ',' ',' ',' ',' ',' ','X',' ',' ',' ',' ',' ',' ',' ',' ',' ','X'}, {'X',' ',' ',' ',' ',' ',' ',' ',' ','X',' ',' ',' ',' ','X','X','X',' ',' ','X'}, {'X',' ',' ',' ',' ',' ',' ',' ',' ','X',' ',' ',' ',' ','X','X','X',' ',' ','X'}, {'X',' ',' ',' ',' ','X','X','X',' ','X',' ',' ',' ',' ','X','X','X',' ',' ','X'}, {'X',' ',' ',' ',' ',' ',' ','X',' ','X',' ',' ',' ',' ',' ',' ',' ',' ',' ','X'}, {'X',' ',' ',' ',' ',' ',' ','X',' ','X',' ',' ',' ',' ',' ',' ',' ',' ',' ','X'}, {'X','X','X','X','X','X','X','X','X','X','X','X','X','X','X','X','X','X','X','X'} };

private int playerX = 1, playerY = 1; // Initial coordinate of player in maze

private int exitX = 18, exitY = 18; // Coordinates of the maze exit private Scene scene; // This is a class variable so multiple methods can access it private GraphicsContext gc; // This is a class variable so multiple methods can access it private Image playerIcon; // An emoticon that displays location in the maze private Image flagIcon; // Image of a red flag that indicates the exit

// This method returns the Scene object. // It is needed to add a keyboard handler to the scene from a separate class. public Scene getScene() { return scene; } // By hard-coding the maze above, the y coordinate is first and x is second. // i.e. maze[y][x]. This code flips it around so we can access it as the // more familiar [x][y] and have it match the depiction of the maze as // it is hard-coded above. private void flipMaze() { char[][] flippedMaze = new char[SIZE][SIZE]; for (int y = 0; y < SIZE; y++) for (int x = 0; x < SIZE; x++) flippedMaze[x][y] = maze[y][x]; maze = flippedMaze; } // This method draws the maze in a JavaFX window. It draws an empty cell as white, // black for walls, and paints an emoticon icon for the player using drawImage // and a flag for the exit. The emoticon and flag are loaded as image files. public void drawMaze() { for (int x = 0; x < SIZE; x++) { for (int y = 0; y < SIZE; y++) { if (maze[x][y]==' ') gc.setFill(Color.WHITE); else if (maze[x][y]=='X') gc.setFill(Color.BLACK); gc.fillRect(x*SPRITE_SIZE,y*SPRITE_SIZE,SPRITE_SIZE,SPRITE_SIZE); }} // Draw player emoji at coordinates of player gc.drawImage(playerIcon,playerX*SPRITE_SIZE,playerY*SPRITE_SIZE,SPRITE_SIZE,SPRITE_SIZE); // Draw flag at coordinates of exit gc.drawImage(flagIcon,exitX*SPRITE_SIZE,exitY*SPRITE_SIZE,SPRITE_SIZE,SPRITE_SIZE); } // This method moves the player in the specified direction (UP, DOWN, LEFT, RIGHT). // It first checks to make sure the target location is a blank space. public void movePlayer(String direction) { switch (direction) { case "UP": if (maze[playerX][playerY-1]==BLANK) playerY--; break; case "DOWN": if (maze[playerX][playerY+1]==BLANK) playerY++; break; case "LEFT": if (maze[playerX-1][playerY]==BLANK) playerX--; break; case "RIGHT": if (maze[playerX+1][playerY]==BLANK) playerX++; break; } drawMaze(); // If we landed on the exit print a message and quit if ((playerX == exitX) && (playerY == exitY)) { System.out.println("You escaped the maze!"); System.exit(0);}} /************************************************************************** ** TO DO: The following line creates a child class of MazeSolver that ** requires a human to type in arrow keys for directions to move. ** Comment it out and uncomment the RandomMazeSolver to instead make a ** class that randomly picks a direction to move. ** In this assignment, you are asked to make a new child class of MazeSolver ** that keeps moving in the same direction until it hits a wall, then picks ** a random direction to move. After your class is written you can fire it ** off by creating an instance of it here instead of the HumanMazeSolver ** or RandomMazeSolver. ***************************************************************************/ //HumanMazeSolver solver = new HumanMazeSolver(playerX, playerY, this); //RandomMazeSolver solver = new RandomMazeSolver(playerX, playerY, this); root.getChildren().add(canvas); primaryStage.setScene(scene); primaryStage.setTitle("Maze Mania"); primaryStage.show();}

// Only needed below for older versions of Java

public static void main(String[] args) {

launch(args);}}

/*******************************************************************

* MazeSolver.java * This class helps you build a maze solver. You don't need to change * anything in this class, but you should make a child of MazeSolver * and use the methods inherited from this class. The methods give you access to * the coordinates in the maze, access to the maze itself, and methods * to check if there is a wall up/down/left/right and methods to move * up, down, left, or right. *******************************************************************/ public class MazeSolver { protected int x,y; // Coordinates in the maze protected Maze maze; // Access back to the Maze object // Default constructor; not used in this program public MazeSolver() { x=1; y=1; maze = null; } // This program sets the coordinates and saves a reference to the maze object. // This reference allows us to make moves on the maze and to access the 2D array. public MazeSolver(int x, int y, Maze maze) { this.x = x; this.y = y; this.maze = maze; } // Returns true or false depending on whether there is a wall in the // specified direction from our current position. public boolean isWallUp() { return (maze.maze[x][y-1] == Maze.WALL); } public boolean isWallDown() { return (maze.maze[x][y+1] == Maze.WALL); } public boolean isWallLeft() { return (maze.maze[x-1][y] == Maze.WALL); } public boolean isWallRight() { return (maze.maze[x+1][y] == Maze.WALL); } // Attempts to move the player in the specified direction in the maze. public void moveUp() { if (!isWallUp()) { y--; maze.movePlayer("UP"); }} public void moveDown() { if (!isWallDown()) { y++; maze.movePlayer("DOWN"); }} public void moveLeft() { if (!isWallLeft()) { x--; maze.movePlayer("LEFT"); } } public void moveRight() { if (!isWallRight()) { x++; maze.movePlayer("RIGHT"); }}}

/******************************************************************* * RandomMazeSolver.java * This is an example of implementing a child class of MazeSolver. * You don't need to change anything in this class. * You should use this class as a starting point to write your own class * to complete the homework problem. * It randomly picks an available direction from possible directions * and moves there. It can take a long time to randomly make its * way to the exit! *******************************************************************/ import java.util.Random; import javafx.animation.KeyFrame; import javafx.animation.Timeline; import javafx.util.Duration;

public class RandomMazeSolver extends MazeSolver { public RandomMazeSolver() { super(); // Call parent constructor } public RandomMazeSolver(int x, int y, Maze maze) { super(x,y,maze); // Call parent constructor // This timeline object calls the randomMove method // once every 0.1 seconds. You can change the 0.1 to a different // number to make the move more quickly or more slowly. Timeline timeline = new Timeline( new KeyFrame(Duration.seconds(0.1), e -> { randomMove(); }) ); timeline.setCycleCount(Timeline.INDEFINITE); timeline.play(); } // This method moves the player in a random up/down/left/right direction // as long as there is not a wall in that direction public void randomMove(){ Random rnd = new Random(); // Pick a random direction and if we can move that direction then do it boolean foundDirection = false; // Repeat if we picked a direction with a wall do{ switch (rnd.nextInt(4)) { case 0: if (!isWallUp()) { foundDirection = true; moveUp() } break; case 1:

/******************************************************************* * HumanMazeSolver.java * * This is an example of implementing a child class of MazeSolver. * You don't need to change anything in this class. * * It gets input from the keyboard as arrow keys and sends it to * the maze to make the move. *******************************************************************/ import javafx.scene.Scene; import javafx.event.EventHandler; import javafx.scene.input.KeyEvent;

public class HumanMazeSolver extends MazeSolver { public HumanMazeSolver() { super(); } public HumanMazeSolver(int x, int y, Maze maze) { super(x,y,maze); // We haven't covered what this setOnKeyPressed EventHandler does, // but basically it creates an instance of a class here in the code // with a method that is run when a key is pressed. maze.getScene().setOnKeyPressed(new EventHandler() { @Override public void handle(KeyEvent event) { switch (event.getCode()) { case UP: if (!isWallUp()) moveUp(); break; case DOWN: if (!isWallDown()) moveDown(); break; case LEFT: if (!isWallLeft()) moveLeft(); break; case RIGHT: if (!isWallRight()) moveRight(); break; }} }); }}