package mazegenerator;
import java.applet.Applet;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Image;
import java.util.BitSet;
public class MazeGenerationVisualization extends Applet implements Runnable{
Maze m;
MazeSolver ms;
BitSet bs;
Thread thread;
int height = 50;
int width = 20;
int scale = 8;
int w = width2+1;
int h = height2+1;
int count = 0;
boolean solved;
int reprint = 0;
Graphics bufferOS;
Graphics bufferMS;
Image offscreen;
Image mazescreen;
@Override
public void init(){
resize(w * scale, h * scale + 10);
offscreen = createImage(w*scale,h*scale + 10);
mazescreen = createImage(w*scale,h*scale + 10);
bufferOS = offscreen.getGraphics();
bufferMS = mazescreen.getGraphics();
m = new Maze(width, height);
bs = m.getBitSet();
solved = false;
thread = new Thread(this);
thread.start();
}
@Override
public void run() {
while (!m._generate()){
count++;
bs = m.getBitSet();
repaint();
try {
thread.sleep(6,0);
} catch (InterruptedException ex) {
System.out.println(ex);
}
}
ms = new MazeSolver(m);
solved = true;
System.out.println("Solving");
while (!ms.solve()){
count++;
if (ms.isSolved()){
bs = ms.getBitSet();
}
repaint();
try {
thread.sleep(6,0);
} catch (InterruptedException ex) {
System.out.println(ex);
}
}
bs = ms.getBitSet();
repaint();
kill();
}
public void kill(){
System.out.println("Killing");
thread = null;
}
@Override
public void update(Graphics g) {
paint(g);
}
@Override
public void paint(Graphics g){
g.setColor(Color.red);
if (solved && ms.isSolved()){
bufferMS.setColor(Color.black);
bufferMS.clearRect(0, 0, w*scale, h*scale);
bufferMS.drawString(""+count, 0, scale * h + 10);
bufferMS.setColor(Color.yellow);
bufferMS.drawImage(offscreen, 0, 0, this);
for (int i = 0; i < h; i++){
for (int j = 0; j < w; j++){
if (bs.get(i * w + j)){
bufferMS.fillRect(j * scale, i * scale, scale, scale);
}
}
}
g.drawImage(mazescreen, 0, 0, this);
}
else{
bufferOS.clearRect(0, 0, w*scale, h*scale + 10);
bufferOS.drawString(""+count, 0, scale * h + 10);
for (int i = 0; i < h; i++){
for (int j = 0; j < w; j++){
if (!bs.get(i * w + j)){
bufferOS.fillRect(j * scale, i * scale, scale, scale);
}
}
}
if (solved){
bufferOS.setColor(Color.red);
int x = (ms.getLoc()%w) * scale;
int y = (ms.getLoc()/w) * scale;
bufferOS.fillRect(x, y, scale, scale);
bufferOS.setColor(Color.black);
}
g.drawImage(offscreen, 0, 0, this);
}
}
}
package mazegenerator;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.image.BufferedImage;
import static java.awt.image.BufferedImage.TYPE_INT_ARGB;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Stack;
import javax.imageio.ImageIO;
public class Maze {
private int width;
private int height;
private BitSet maze;
private Stack<Integer> stack = new Stack();
private char[] hashKey;
private int finish;
private int count = 0;
public Maze(BitSet maze, int width, int height){
this.maze = maze;
this.width = width;
this.height = height;
}
//initializes the maze
public Maze(int w, int h){
width = w * 2 + 1;
height = h * 2 + 1;
maze = new BitSet(width * height);
finish = (int)(Math.random() * (width / 2)) * 2 + 1;
maze.set(width*height - 1 - finish);
finish = width*height - 1 - finish - width;
int start = (int)(Math.random() * (width / 2)) * 2 + 1;
maze.set(start);
maze.set(start + width);
stack.push(start + width);
}
public BitSet getBitSet(){
return maze;
}
public int getWidth(){
return width;
}
public int getHeight(){
return height;
}
//takes one step towards converting maze
//returns true if maze is finished
//else returns false
public boolean generate(){
if (stack.empty()) return true;
int m;
int loc = stack.peek();
ArrayList<Integer> move = new ArrayList();
if (loc - 2 * width >= 0 && !maze.get(loc - 2*width)) move.add(-1 * width);
if (loc + 2 * width < width * height && !maze.get(loc + 2*width)) move.add(1 * width);
if (loc + 2 < width * height && (loc + 2)/width == loc/width && !maze.get(loc + 2)) move.add(1);
if (loc - 2 >= 0 && (loc - 2)/width == loc/width && !maze.get(loc - 2)) move.add(-1);
if (move.size()>0){
m = move.get((int)(Math.random()*move.size()));
maze.set(stack.push(loc + 2*m));
maze.set(loc + m);
return false;
}
stack.pop();
return stack.empty();
}
//takes one step towards converting maze
//returns true if maze is finished
//else returns false
//reverses the stack after every move
public boolean _generate(){
if (stack.empty()) return true;
int m;
int loc = stack.peek();
ArrayList<Integer> move = new ArrayList();
if (loc - 2 * width >= 0 && !maze.get(loc - 2*width)) move.add(-1 * width);
if (loc + 2 * width < width * height && !maze.get(loc + 2*width)) move.add(1 * width);
if (loc + 2 < width * height && (loc + 2)/width == loc/width && !maze.get(loc + 2)) move.add(1);
if (loc - 2 >= 0 && (loc - 2)/width == loc/width && !maze.get(loc - 2)) move.add(-1);
if (move.size()>0){
count++;
m = move.get((int)(Math.random()*move.size()));
maze.set(stack.push(loc + 2*m));
maze.set(loc + m);
if (loc + 2*m == finish){
Stack<Integer> temp = new Stack();
while(!stack.empty())
temp.push(stack.pop());
stack = temp;
}
if (count == 1){
Stack<Integer> temp = new Stack();
while(!stack.empty())
temp.push(stack.pop());
stack = temp;
count = 0;
}
return false;
}
stack.pop();
return stack.empty();
}
//returns a string representation of the maze
//1 represents path and 0 represents wall
@Override
public String toString(){
String str = "";
for (int i = 0; i < height; i++){
for (int j = 0; j < width; j++){
if (maze.get(i * width + j)){
str += 1;
}
else str += 0;
}
str += "\n";
}
return str;
}
//draws the maze to a png file
public void draw(String name){
BufferedImage bi = new BufferedImage(width, height, TYPE_INT_ARGB);
Graphics g = bi.getGraphics();
g.setColor(Color.black);
for (int i = 0; i < height; i++){
for (int j = 0; j < width; j++){
if (!maze.get(i * width + j)){
g.drawLine(j, i, j, i);
}
}
}
try {
File outputfile = new File(name + ".png");
ImageIO.write(bi, "png", outputfile);
} catch (IOException e) {}
}
}