• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

help

 
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Preparing the maze

Consider your basic maze. It has walls and pathways, and it has one (or more)starting point(s) and one (or more) finish point(s). Furthermore, one wall isjust like another, and any open spaces (not including start and finish) are also identical. That sounds like a job for. . . enumerated types!

So, make an enumerated type Square that can represent those four values.Each one has an associated one-character representation:
Walls # (hash mark)
open spaces . (period)
start o (lowercase ‘O’)
finish * (asterisk)

Include in the enumerated type a toString method that returns a one-characterlongstring containing only the character corresponding to this Square. Alsoinclude a static method fromChar that returns the Square associated with thegiven char. (That is, a method with header public static Square fromChar(char ch) that, when provided with one of the four legal characters, returns oneof the Square values. Any other input can generate an IllegalArgumentException.)

In thisproblem, you’ll adapt existing library code into a more abstract framework.First, write the Agenda<T> interface. It should require five methods: isEmpty,size, add, remove, and peek.Then, write two classes MyStack<T> and MyQueue<T> that implement that interface using, respectively, a LIFO policy and a FIFO policy. Code re-use is key here; all the real algorithm work is already done, and your only job for this problem is to adapt it for use in this framework.Remember, you’re using the Java libraries in this problem. Don’t try to use ListNode!

Create a Maze class that can store the logical layout of a maze. It should containa 2D array of either Square or char.1 (Remember, a 2D array is just like a 1Darray, except that you always provide two indices.)Maze should have a constructor that can read from a Scanner. The format willbe that the first line contains the dimensions of the maze (width and height),and subsequent lines each contain one row of the maze, with each characterrepresenting one square of the maze. BE CAREFUL about the interactionsbetween line- and chunk-based scanning!Also, write a toString method that makes a String representation of this Mazein the same format as the input. (This will be handy in testing your code...)

Import java.io.*;
import java.util.*;
public class Main {




static String[][]maze;
public static void main(String[] args)
{
maze=new String[20][20];
maze=fillArray("maze.txt");
}
public static String[][]fillArray(String file)
{
maze = new String[20][20];//establish 20 X 20 array to hold maze
//read maze info from file and call print method
try{
Scanner sc = new Scanner(new File(file));
//for loops to loop through 2d array
for(int row = 0; row < 20; row++)
{
for(int col = 0; col < 20; col++)
{
maze[row][col] = sc.next();//from file to array
}//end for
sc.nextLine();//move to next line of input
}//end for
printArray();
}//end try
catch(FileNotFoundException fe)
{
System.out.println("Error: file maze.txt not found!");//exception handling
}//end catch
return maze;
}
public static void printArray()
{
System.out.println();
for(int row=0;row<20;row++)
{
for(int col=0;col<20;col++)
{
System.out.print(maze[row][col]+" ");
}
System.out.println();
}


}
}

A simple example of the input/output format:

7 4
#######
#...#o#
#*#...#
#######

A more complex example:

12 10
############
#.#........#
#.#.######.#
#.#....#...#
#.###.*#.#.#
#...####.#.#
#.#.#..#.#.#
#.#.#.##.#.#
#o#......#.#
############

Solving the maze

Note that this project does not explicitlylist all of the classes you’ll have to write—part of that will be design decisionsleft up to you.

The GUI

To handle all the fiddly graphical stuff, write a MazeApp class. When the GUIis started up it should present the following components across the top of the window:
• a text field
• a button labelled “Load”
• a button labelled “Start (stack)”
• a button labelled “Start (queue)”
• a button labelled “Step”
• a button labelled “Toggle animation”



When the user types a filename into the text field and clicks the “Load” button,the maze in that file should be read in and displayed in the application: open squaresare white, walls are black. The two start buttons should initiate the mazesolution process (further described below). Once initiated, the step buttonmakes the solution proceed by just one step, and turning on the animation usesa Timer (see below) to set the solution a-running at the rate of a few steps asecond. (Clicking the animation button again should stop the animation.)Somewhere conspicuous, the GUI should display a status line giving the currentstatus of the solution process: “No maze”, “Maze loaded”, “Stack-based solutionin progress”, “Queue-based solution in progress”, “Solution complete: finishreachable”, “Solution complete: finish not reachable”.

What we should see as the solution process goes on is that the squares thathave been explored—yes, we can reach them, but no, we haven’t found thefinish yet—change from white to medium-grey. Whether stepping by hand oranimating, we should see the maze slowly shaded in until the solver reaches thefinish (or determines that it’s unreachable).

Notes on Timer

There are two Timer classes in the java libraries, with similar functionality. Youwant the one in javax.swing, because the way it triggers its action is exactly thesame way a Button does—via an ActionListener. Once the Timer is created,you will call its start(), stop(), and isRunning() methods to control it.The one you don’t want to use is in java.util. If you are freely importingeverything from that package, make sure you’re not accidentally using the wrongTimer!

The maze itself

You have a Maze class that stores char or Squareand can read from a Scanner. You may assume that any well-formed maze will have exactly one start andexactly one finish. You may not assume that all valid mazes will be entirelyenclosed with walls.

The agenda

As with Maze, it’s expected that have working Agenda<T>, MyStack<T>, and MyQueue<T> classes. If not,finish them.

The maze solver

The meat of the project will be the writing of a MazeSolver class (and associatedclasses), which will bundle up the functionality of determining whether a mazehas a solution—that is, whether you can get from the start to the finish (withoutjumping over any walls). The algorithm one usually follows goes something likethis: start at the start location, and trace along all possible paths to (eventually)all reachable open squares. If at some point you run across the finish, it wasreachable. If not, it wasn’t.

Boiling this down into pseudo code, we have the following:

At the start:

1. Create an (empty) agenda of locations to explore.

2. Add the start location to it.

Each step thereafter:

1. Is the agenda empty? If so, the finish is unreachable; terminate thealgorithm.

2. Grab a location from the agenda.

3. Have we pulled this location from the agenda before? If so, no needto explore it again; this step is done.

4. Does the location correspond to the finish square? If so, the finishwas reachable; terminate the algorithm.

5. Otherwise, it is a reachable non-finish location that we haven’t seenyet. So, explore it as follows:

• compute all the adjacent locations that are inside the maze andaren’t walls, and

• add them to the agenda for later exploration.

6. Also, record the fact that you’ve explored this location so you won’tever have to explore it again.

Note that this pseudocode is entirely agnostic as to what kind of agenda youuse. You’ll need to pick one when you create the agenda, but subsequentlyeverything should work more abstractly in terms of the Agenda operations.

Design and discussion questions

You would do well to read the following questionsfirst and think about them early, and take notes on what you plan to do—theywill help you shape your design. There are also a few hints as to what you canand can’t do.

What kind of a Maze will the MazeApp have before you’ve loaded any file?

Which object should be responsible for generating the status message?

How will you share the responsibility for actually drawing the maze? Rememberthat the solution-in-progress should display explored squares in grey—whichdata structure is keeping track of that information?

How will you represent locations? Why can’t you just modify Square for this?

How will you keep track of the locations you’ve explored vs those you haven’t?

What other data structure(s) would you need if your solver needed to be ableto report the actual path from the start to finish, instead of just the fact thatone existed (or not)?
(Bonus marks for implementing and displaying the actual path!)

The obvious time to click the Step button is immediately after one of theStart buttons, which was probably clicked right after the Load button. Whatshould happen if a user clicks buttons at an unexpected time? (Hint: not aNullPointerException.)
 
Sheriff
Posts: 67746
173
Mac Mac OS X IntelliJ IDE jQuery TypeScript Java iOS
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Looks like homework to me. What's the problem?

And please use better titles than "help".
 
reply
    Bookmark Topic Watch Topic
  • New Topic