Skip to content

Instantly share code, notes, and snippets.

@need12648430
Last active September 1, 2015 16:59
Show Gist options
  • Save need12648430/8924d1d5a9506fec4ed7 to your computer and use it in GitHub Desktop.
Save need12648430/8924d1d5a9506fec4ed7 to your computer and use it in GitHub Desktop.
Maze Generator in 532 bytes.
// only semi-golfed, mostly because i was in the headspace; only used for debugging
var w, h, x, y, m=maze(w=16,h=16), g=[];
// generate fully walled grid
for(y = 0; y < h * 2 + 1; y ++) {
g[y]=[]
for(x = 0; x < w * 2 + 1; x ++)
g[y].push(!(y&1)?"#":!(x&1)?"#":" ");
}
// knock out walls according to maze(w,h) output
for (y = 0; y < h; y ++)
for(x = 0; x < w; x ++) {
var c=m[y*w+x];
g[y*2+1][x*2+1];
// north bit
if(!(c&2))g[y*2][x*2+1]=" ";
// south bit
if(!(c&4))g[y*2+2][x*2+1]=" ";
// east bit
if(!(c&8))g[y*2+1][x*2+2]=" ";
// west bit
if(!(c&16))g[y*2+1][x*2]=" ";
}
// puke it onto the console
for(y = 0; y < g.length; y ++)
console.log(g[y].join(""))
// maze(w,h) + init some vars
function maze(w,h,a,v,m,p,c,o,f,r,l) {
// shorthand some things
with(Math){f=floor,r=random,l="length"}
// init the grid of cells to 30 (11110b, NSEW visited)
for(c=[];c[l]<(a=w*h);c.push(30));
// set visited count (v) to 1
// set position (p) to 0
// set visited bit in cell[position]
// init moves array with first cell
m=[c[p=0]|=(v=1)]
for(;v<a;){
// init movement options (o)
// init array of possible positions (i) (north, east, south, BS value)
// init position we're testing (j) to west
// loop until array is empty
// shift the first value from i after we're done with each iteration
for(o=[],i=[p-w,p+1,p+w,0],j=p-1;i[l]>0;j=i.shift())
// bound and unvisited check
if(j>=0 && j<a && !(c[j]&1))
// array is XYXY; so i.length parity == direction
// runs a horizontal-specific check (make sure it stays on X)
if((i[l]&1)==0 && f(p/w)==f(j/w)) o.push(j-p)
else if((i[l]&1)==1) o.push(j-p)
// if there are valid moves
if(o.length){
// pick one
o=o[f(r()*o[l])]
// set appropriate bits
if(o==-1){c[p]^=16;c[p+=o]^=8;}
if(o==1){c[p]^=8;c[p+=o]^=16;}
if(o==w){c[p]^=4;c[p+=o]^=2;}
if(o==-w){c[p]^=2;c[p+=o]^=4;}
// increase visited count, set cell to visited, push to moves
v++;c[p]^=1;m.push(p);
// otherwise backtrack
}else p=m.pop();
}
return c;
}
function maze(w,h,a,v,m,p,c,o,f,r,l) {
with(Math){f=floor,r=random,l="length"}
for(c=[];c[l]<(a=w*h);c.push(30));
m=[c[p=0]|=(v=1)]
for(;v<a;){
for(o=[],i=[p-w,p+1,p+w,0],j=p-1;i[l]>0;j=i.shift())
if(j>=0 && j<a && !(c[j]&1))
if((i[l]&1)==0 && f(p/w)==f(j/w)) o.push(j-p)
else if((i[l]&1)==1) o.push(j-p)
if(o.length){
o=o[f(r()*o[l])]
if(o==-1){c[p]^=16;c[p+=o]^=8;}
if(o==1){c[p]^=8;c[p+=o]^=16;}
if(o==w){c[p]^=4;c[p+=o]^=2;}
if(o==-w){c[p]^=2;c[p+=o]^=4;}
v++;c[p]^=1;m.push(p);
}else p=m.pop();
}
return c;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment