8
Hi guys,
I was looking at random maze generators on the web. I found this prims algorithm but everytime I run it, it doesnt display the random maze as it should. It just displays a blank applet. Also, does any one know how to save this generated applet to a png or jpg format? Source code is attached below. Thanks.
************************************************** *******************************************
package ares;
import java.awt.*;
import java.util.*;
import java.applet.*;
public class Prim extends Applet implements Runnable
{
public static final int WTOP = 1;
public static final int WRGT = 2;
public static final int WBOT = 4;
public static final int WLFT = 8;
int cells[][];
Point current_cell;
Vector inlist;
Vector outlist;
Vector frontlist;
int gridw, gridh, cellsize;
Image offscreen;
Graphics offgr;
Thread t;
public void init()
{
int x, y;
String param;
/* Get applet params */
param = getParameter("gridw");
gridw = Integer.parseInt(param);
param = getParameter("gridh");
gridh = Integer.parseInt(param);
param = getParameter("cellsize");
cellsize = Integer.parseInt(param);
cells = new int[gridw][gridh];
/* Or together the wall bits to show that all
* the walls are up.
*/
int full = WTOP | WBOT | WLFT | WRGT;
for (x = 0; x < gridw; x++)
for (y = 0; y < gridh; y++)
cells[x][y] = full;
/* Then, mark the borders
*/
int left = WLFT << 4;
int right = WRGT << 4;
for (y = 0; y < gridh; y++)
{
cells[0][y] |= left;
cells[gridw-1][y] |= right;
}
int top = WTOP << 4;
int bottom = WBOT << 4;
for (x = 0; x < gridw; x++)
{
cells[x][0] |= top;
cells[x][gridh-1] |= bottom;
}
offscreen = createImage((gridw+2)*cellsize, (gridh+2)*cellsize);
offgr = offscreen.getGraphics();
}
public void start()
{
t = new Thread(this);
t.start();
}
public void stop()
{
t.stop();
t = null;
}
public void run()
{
int dir, x, y;
/*
* Implement Prim's algorithm to build maze
*/
outlist = new Vector(gridw*gridh);
inlist = new Vector(10,10);
frontlist = new Vector(10,10);
for (x = 0; x < gridw; x++)
for (y = 0; y < gridh; y++)
outlist.addElement(new Point(x,y));
current_cell = (Point)rndElement(outlist);
inlist.addElement(current_cell);
moveNbrs(current_cell);
while (!frontlist.isEmpty())
{
current_cell = (Point)rndElement(frontlist);
inlist.addElement(current_cell);
moveNbrs(current_cell);
dir = findInNbr(current_cell);
removeWall(current_cell, dir);
/*
* Break for the animation effect
*/
repaint();
try
{
Thread.sleep(50);
} catch (Exception e) {};
}
/*
* All done
*/
current_cell = null;
repaint();
}
public void update(Graphics g)
{
paint(offgr);
g.drawImage(offscreen,0,0,this);
}
public void paint(Graphics g)
{
int val, x ,y;
int basex = 10;
int basey = 10;
g.setColor(Color.white);
g.fillRect(basex, basey, gridw*cellsize, gridh*cellsize);
g.setColor(Color.black);
for (x = 0; x < gridw; x++)
for (y = 0; y < gridh; y++)
{
val = cells[x][y];
if ((val & WTOP) != 0)
g.drawLine(basex+x*cellsize, basey+y*cellsize,
basex+(x+1)*cellsize, basey+y*cellsize);
if ((val & WRGT) != 0)
g.drawLine(basex+(x+1)*cellsize-1, basey+y*cellsize,
basex+(x+1)*cellsize-1, basey+(y+1)*cellsize);
if ((val & WBOT) != 0)
g.drawLine(basex+x*cellsize, basey+(y+1)*cellsize-1,
basex+(x+1)*cellsize, basey+(y+1)*cellsize-1);
if ((val & WLFT) != 0)
g.drawLine(basex+x*cellsize, basey+y*cellsize,
basex+x*cellsize, basey+(y+1)*cellsize);
}
/*
* Draw the current_cell as well
*/
g.setColor(Color.red);
if (current_cell != null)
g.fillOval(basex+current_cell.x*cellsize, basey+current_cell.y*cellsize,
cellsize, cellsize);
}
/*
* The following routines provide access to the underlying
* maze data structure.
*/
int findInNbr(Point p)
{
/* Return a random direction in which the point p has
* a neighbor which is in inlist.
*/
int d = rnd(4)-1;
int k = 0;
while (k < 4)
{
switch(d)
{
case 0: /* Top nbr? */
if ((cells[p.x][p.y] & (WTOP<<4)) != 0) break;
if (inlist.indexOf(new Point(p.x,p.y-1)) >= 0)
return WTOP;
break;
case 1: /* Right nbr? */
if ((cells[p.x][p.y] & (WRGT<<4)) != 0) break;
if (inlist.indexOf(new Point(p.x+1,p.y)) >= 0)
return WRGT;
break;
case 2: /* Bottom nbr? */
if ((cells[p.x][p.y] & (WBOT<<4)) != 0) break;
if (inlist.indexOf(new Point(p.x,p.y+1)) >= 0)
return WBOT;
break;
case 3: /* Left nbr? */
if ((cells[p.x][p.y] & (WLFT<<4)) != 0) break;
if (inlist.indexOf(new Point(p.x-1,p.y)) >= 0)
return WLFT;
break;
}
d = (d+1) % 4;
k++;
}
return 0; // This shouldn't ever happen
}
void moveNbrs(Point p)
{
Point s;
/*
* Move any neighbors of p which are in outlist from
* outlist to frontlist.
*/
if ((cells[p.x][p.y] & (WTOP<<4)) == 0)
{
s = new Point(p.x, p.y-1);
movePoint(s, outlist, frontlist);
}
if ((cells[p.x][p.y] & (WRGT<<4)) == 0)
{
s = new Point(p.x+1, p.y);
movePoint(s, outlist, frontlist);
}
if ((cells[p.x][p.y] & (WBOT<<4)) == 0)
{
s = new Point(p.x, p.y+1);
movePoint(s, outlist, frontlist);
}
if ((cells[p.x][p.y] & (WLFT<<4)) == 0)
{
s = new Point(p.x-1, p.y);
movePoint(s, outlist, frontlist);
}
}
void movePoint(Point p, Vector v, Vector w)
{
/*
* If p is element of v, move it to w
*/
int i = v.indexOf(p);
if (i >= 0)
{
v.removeElementAt(i);
w.addElement(p);
}
}
void removeWall(Point p, int d)
{
/* Exclusive or bit with cell to drop wall
*/
cells[p.x][p.y] ^= d;
/*
* And drop neighboring wall as well
*/
switch(d)
{
case WTOP: cells[p.x][p.y-1] ^= WBOT;
break;
case WRGT: cells[p.x+1][p.y] ^= WLFT;
break;
case WBOT: cells[p.x][p.y+1] ^= WTOP;
break;
case WLFT: cells[p.x-1][p.y] ^= WRGT;
break;
}
}
// Utility routines
int rnd(int n)
{
return (int)(Math.random()*n+1);
}
Object rndElement(Vector v)
{
int i = rnd(v.size())-1;
Object s = v.elementAt(i);
v.removeElementAt(i);
return s;
}
}
************************************************** ******************************************
