/* built with Studio Sketchpad:
* https://sketchpad.cc
*
* observe the evolution of this sketch:
* https://mhmscc.sketchpad.cc/sp/pad/view/ro.08HhGuSaEdm/rev.1327
*
* authors:
* Steven Dollins
* trevor
*
* license (unless otherwise specified):
* creative commons attribution-share alike 3.0 license.
* https://creativecommons.org/licenses/by-sa/3.0/
*/
color bgcolor = #103010;
color fgcolor = #FFE4C4;
color endcolor = #FF0077;
color pathcolor = #0000df;
int CROSSOVER = 16;
int BORDER = 64;
int[] doffset = {
0, 0, 0, 0, 0
};
int[] dcross = {
0, 10, 5, 10, 5
};
int wide, high;
int cwide;
int ctotal;
int[] cells;
int startc, endc;
int mdiam;
int[] soln;
int nsoln;
PGraphics mazeImg;
void makeMaze(int w, int h) {
wide = w;
high = h;
cwide = wide+2;
ctotal = cwide * (high + 2);
doffset[1] = 1;
doffset[2] = cwide;
doffset[3] = -1;
doffset[4] = -cwide;
cells = new int[(h+2)*(w+2)];
for ( int j=0; j<h+2; j+=h+1 ) {
for ( int i=0; i<w+2; ++i ) {
cells[j*cwide+i] = BORDER;
}
}
for ( int j=1; j<=h; ++j ) {
cells[j*cwide] = BORDER;
for ( int i=1; i<=w; ++i ) {
cells[j*cwide+i] = 0;
}
cells[j*cwide+wide+1] = BORDER;
}
int[] path = new int[w*h];
path[0] = int(h/2 *cwide + w/2);
int npath = 1;
int lastdir = 0;
while ( npath > 0 ) {
int ci, c;
// pick a cell from the path
if ( random(100) < 10 ) {
ci = int( random(npath) );
lastdir = 0;
} else {
ci = npath - 1;
}
c = path[ ci ];
// get choices
int[] choices = new int[16];
int nchoices = 0;
int newcell;
for ( int d=1; d<=4; ++d ) {
newcell = c + doffset[d];
while ( cells[newcell] == dcross[d] ) {
newcell += doffset[d];
}
if ( cells[newcell] == 0 ) {
choices[nchoices++] = d;
if ( d == lastdir ) {
choices[nchoices++] = d;
}
}
}
if ( nchoices < 2 ) {
path[ ci ] = path[ npath-1 ];
--npath;
}
if ( nchoices == 0 ) {
continue;
}
// update door(s)
int d = choices[ int(random(nchoices)) ];
cells[c] |= (1 << (d-1));
newcell = c + doffset[d];
while ( cells[newcell] != 0 ) {
cells[newcell] = CROSSOVER;
newcell += doffset[d];
}
cells[newcell] = 1 << ((d+1)&3);
path[ npath++ ] = newcell;
lastdir = d;
}
int[] dist1 = new int[ctotal*2];
startc = findMostDistant( cwide+1, dist1 );
endc = findMostDistant( startc, dist1 );
mdiam = dist1[endc];
soln = new int[ctotal];
soln[0] = startc;
nsoln = 1;
}
// returns index of cell most distant from 'start'
// the vertical part of a crossover cells[c] is stored
// in dist[c+ctotal]
int findMostDistant( int start, int[] dist ) {
for( int i=0; i<ctotal*2; ++i ) {
dist[i] = -1;
}
dist[start] = 0;
int[] q = new int[ctotal*2];
q[0] = start;
int qfirst = 0;
int qlast = 0;
int c = start;
int numcells = 0;
int maxqlast = 0;
while( qfirst <= qlast ) {
c = q[qfirst++];
numcells++;
if( qfirst > qlast ) {
qfirst = 0;
qlast = -1;
}
int doors;
if( c >= ctotal ) {
doors = 10;
} else if( cells[c] == CROSSOVER ) {
doors = 5;
} else {
doors = cells[c];
}
for( int d=1; d<=4; d++ ) {
if( (doors & (1 << (d-1))) > 0 ) {
int nc = c + doffset[d];
if( c >= ctotal ) {
nc -= ctotal;
}
if( cells[nc] == CROSSOVER && (d == 2 || d == 4) ) {
nc += ctotal;
}
if( dist[nc] == -1 ) {
dist[nc] = dist[c] + 1;
q[++qlast] = nc;
if( maxqlast < qlast ) {
maxqlast = qlast;
}
}
}
}
}
return c;
}
void drawMaze( PGraphics pg ) {
pg.strokeWeight( 40 );
pg.stroke( fgcolor );
pg.translate( -50, -50 );
for ( int j=0; j<high+2; ++j ) {
for ( int i=0; i<cwide; ++i ) {
pg.pushMatrix();
pg.translate( 100.0*i, 100.0*j );
//pg.strokeWeight( 1 );
//pg.rect(-50, -50, 100, 100);
//pg.strokeWeight( 40 );
int doors = cells[j*cwide+i];
if ( doors == BORDER ) {
} else if ( doors == CROSSOVER ) {
if ( ((i^j) & 1) == 1 ) {
pg.rotate(PI/2);
}
pg.line( -50, random(-2, 2), 50, random(-2, 2) );
pg.strokeCap( SQUARE );
pg.line( 0.0, -60, 0.0, -28 );
pg.line( 0.0, 28, 0.0, 60 );
pg.stroke( bgcolor );
pg.strokeWeight(2);
pg.line(-15, -15, -15, 15);
pg.line( 15, -15, 15, 15);
pg.stroke( fgcolor );
pg.strokeWeight( 40 );
pg.strokeCap( ROUND );
} else {
if ( (doors & 1) != 0 ) {
pg.line( 0.0, 0.0, 50, random(-3, 3) );
}
if ( (doors & 2) != 0 ) {
pg.line( 0.0, 0.0, random(-3, 3), 50 );
}
if ( (doors & 4) != 0 ) {
pg.line( 0.0, 0.0, -50, random(-3, 3) );
}
if ( (doors & 8) != 0 ) {
pg.line( 0.0, 0.0, random(-3, 3), -50 );
}
}
pg.popMatrix();
}
}
}
void drawSolution( float fmouseX, float fmouseY ) {
int i0, j0, i1, j1;
translate( -50, -50 );
j0 = int(endc/cwide);
i0 = endc - j0*cwide;
strokeWeight( 35 );
stroke( endcolor );
point( 100*i0, 100*j0 );
strokeWeight( 20 );
stroke( pathcolor );
if( soln[nsoln-1] == endc ) {
stroke( endcolor );
}
int c = soln[0] % ctotal;
j0 = int(c/cwide);
i0 = c - j0*cwide;
point( 100*i0, 100*j0 );
for( int i=1; i<nsoln; ++i ) {
c = soln[i] % ctotal;
j1 = int(c/cwide);
i1 = c - j1*cwide;
line( 100*i0, 100*j0, 100*i1, 100*j1 );
j0 = j1;
i0 = i1;
}
float mx = fmouseX * wide + 0.5;
float my = fmouseY * high + 0.5;
float ang = atan2( my - j0, mx - i0 );
int d = int(ang/PI*2+4.5) % 4;
float r = dist( i0, j0, mx, my );
pushMatrix();
translate( 100*i0, 100*j0 );
rotate( ang );
strokeWeight( 10 );
line( 0, 10, 40, 0 );
line( 0, -10, 40, 0 );
popMatrix();
int doors = cells[c];
if( doors == CROSSOVER ) {
doors = ( soln[nsoln-1] < ctotal ) ? 5 : 10;
}
if( r < 5 && r > 0.6 && (doors & (1<<d)) > 0 ) {
int nc = c + doffset[d+1];
if( cells[nc] == CROSSOVER && (d & 5) > 0 ) {
nc += ctotal;
}
if( nsoln < 2 || nc != soln[nsoln-2] ) {
soln[nsoln++] = nc;
} else {
--nsoln;
}
}
}
void generateNewMaze( int mazeSize ) {
randomSeed( (hour()*60+minute())*60+second()+millis() );
makeMaze( mazeSize, mazeSize );
mazeImg = createGraphics( width, height-30 );
mazeImg.beginDraw();
mazeImg.scale( 0.01 * width / wide, 0.01 * (height-30) / high );
randomSeed(4);
drawMaze(mazeImg);
mazeImg.endDraw();
}
void setup() {
//randomSeed(5);
size( 600, 630 );
smooth();
generateNewMaze( 20 );
noLoop();
//frameRate(10);
}
void draw () {
background( bgcolor );
stroke( fgcolor );
fill( fgcolor );
text( wide+"x"+high+" maze. Solution is " + mdiam + " steps.", 10, 18 );
text( "New maze: ", 260, 18 );
if( mouseY < 22 && mouseY > 4 && mouseX > 328 && mouseX < 552 ) {
int i = int((mouseX - 328) / 32);
fill( #408040 );
noStroke();
rect( 328 + i * 32, 4, 29, 18 );
}
stroke( fgcolor );
strokeWeight( 1 );
for( int i=12; i<=36; i+=4 ) {
noFill();
rect( 232 + i*8, 4, 29, 18 );
fill( fgcolor );
text( i, 240 + i*8, 18 );
}
image( mazeImg, 0, 25 );
translate(0, 25);
scale( 0.01 * width / wide, 0.01 * (height-30) / high );
drawSolution( float(mouseX)/width, float(mouseY-25)/(height-30) );
}
void mouseMoved() {
redraw();
}
void mouseDragged() {
redraw();
}
void mouseReleased() {
if( mouseY < 22 && mouseY > 4 && mouseX > 328 && mouseX < 552 ) {
int i = int((mouseX - 328) / 32) * 4 + 12;
generateNewMaze( i );
redraw();
}
}