import java.applet.*; // applet class import java.awt.*; // Abstract Window Toolkit import java.util.*; import graph.*; import polya.*; public class Maze extends Applet { Color backgroundColor = Color.white; // Colors of various features Color wallColor = Color.blue; Color pathColor = Color.red; int gridWidth = 50; int gridHeight = 30; int x10, y10; int lastX, lastY; Color gridColor[][] = new Color[gridWidth][gridHeight]; Image image; // Image to be drawn on screen by paint method Graphics graphics; // Graphics part of image, acts as buffer Button eraseButton; // Button to erase square public static Polylist findPath(Color walledColor[][]) { Queue queue = new Queue(); Hashtable visitedPoints = new Hashtable(); Point startPoint = new Point(0, 1); Point finishPoint = new Point(49, 28); queue.enqueue(startPoint); visitedPoints.put(startPoint, startPoint); // puts start in the hash table while( queue.nonEmpty() ) { Polylist current = (Polylist)queue.dequeue(); Point p = (Point)current.first(); // Get next node on queue. if( p == finishPoint ) // See if path found. return current.reverse(); // If so, return its reverse. if (walledColor[(p.x)+1][p.y] == backgroundColor) Node newPoint = (Point)( Point((p.x)+1, p.y) ); if (walledColor[p.x][(p.y)+1] == backgroundColor) Node newPoint = (Point)( Point(p.x, (p.y)+1) ); if (walledColor[(p.x)-1][p.y] == backgroundColor) Node newPoint = (Point)( Point((p.x)-1, p.y) ); if (walledColor[p.x][(p.y)-1] == backgroundColor) Node newPoint = (p)( Point(p.x, (p.y)-1) ); if( !current.member(newPoint) ) // See if node already seen. { if ( visitedPoints.get(newPoint) == null )// Check if it's not already in the // hashtable (and, thus, the queue) { queue.enqueue(current.cons(newPoint)); // If it's not already there, visitedPoints.put(newNode,newPoint); // enqueue it and add to the table. } } } return Polylist.nill; } /////////////////////////////////////////////////////////////////////////// // Initialize the applet. public void init() { makeImageBuffer(); drawSquare(wallColor); add(eraseButton = new Button("Clear")); } // Draw a square. void drawSquare(Color color) { int x = ( size().width - 500 ) / 2; // size() is size of applet frame int y = ( size().height - 300) / 2; int width = 500; int height = 300; graphics.setColor(color); graphics.fillRect(x, y, width, 10); graphics.fillRect(x, y+height-10, width, 10); graphics.fillRect(x, y+20, 10, height-20); graphics.fillRect(x+width-10, y, 10, height-20); } void drawLine() { graphics.setColor(gridColor[x10][y10]); graphics.fillRect(x10*10+50, y10*10+50, 10, 10); } // show draws the mouse coordinates and square into the graphics buffer boolean drawPath(Point shortPath) { graphics.setColor(pathColor); //while (shortPath.hasNextElement()) //{ // int pointX = first(shortPath).x; // int pointY = first(shortPath).y; graphics.fillRect(shortPath.x*10+50, shortPath.y*10+50, 10, 10); //} return true; } boolean show(int x, int y) { x10 = (x-50) / 10; y10 = (y-50) / 10; if (x10 < 1 || x10 > 48 || y10 < 1 || y10 > 28 ) return true; if (x10 < 0 || y10 < 0) return true; if (gridColor[x10][y10] == backgroundColor) gridColor[x10][y10] = wallColor; else gridColor[x10][y10] = backgroundColor; drawLine(); Polylist path = findPath(gridColor[][]); // Erase!!! graphics.setColor(Color.black); graphics.drawString(Polylist.list(path) + " hahaha", 50, 100); // graphics.drawString(path.x + " hahaha", 50, 150); repaint(); return true; } // mouseDown is called when the mouse button is depressed. public boolean mouseDown(Event e, int x, int y) { return show(x, y); } // mouseDrag is called when the mouse is dragged. public boolean mouseDrag(Event e, int x, int y) { if ( x10 == ((x-50)/10) && y10 == ((y-50)/10) ) return true; else return show(x, y); } public boolean mouseUp(Event v, int x, int y) { return drawPath(findPath()); } // mouseUp is called when the mouse button is released. // handle erase button event public boolean action(Event event, Object arg) { if( event.target == eraseButton ) { clear(); drawSquare(wallColor); repaint(); } return super.action(event, arg); // Call super } // The following methods are "boilerplate" which you will probably // want to use as is. // Make off-screen image buffer based on size of the applet. void makeImageBuffer() { image = createImage(size().width, size().height); graphics = image.getGraphics(); clear(); } // clear clears the graphics image void clear() { graphics.setColor(backgroundColor); graphics.fillRect(0, 0, size().width, size().height); graphics.drawRect(0, 0, size().width-1, size().height-1); for (int i=0; i<50; i++) { for (int j=0; j<30; j++) { gridColor[i][j] = backgroundColor; } } } // update is implicitly called when repaint() is called // g will be bound to the Graphics object in the Applet, // not the one in the image. paint will draw the image into g. public void update(Graphics g) { paint(g); } // paint(Graphics) is called by update(g) and whenever // the screen needs painting (such as when it is newly exposed) public void paint(Graphics g) { g.drawImage(image, 0, 0, null); } } //////////////////////////////////////////////////////////////////// class Queue { QueueCell head = null; QueueCell tail = null; // Create a Queue. Queue() { } // Check whether this Queue is empty. boolean isEmpty() { return head == null; } // Check whether this Queue is non-empty. boolean nonEmpty() { return head != null; } // Enqueue an Object. void enqueue(Object data) { if( isEmpty() ) { head = tail = new QueueCell(data, null); } else { tail = tail.next = new QueueCell(data, null); } } // Dequeue an Object. public Object dequeue() { if( isEmpty() ) throw new NoSuchElementException("can't dequeue from empty queue"); Object result = head.data; head = head.next; if( head == null ) { tail = null; } return result; } // List Cell for constructing Queue class QueueCell { Object data; QueueCell next; QueueCell(Object data, QueueCell next) { this.data = data; this.next = next; } } } ///////////////////////////////////////////////////////////////////////////