maze prim

practice prim maze generation.

Created by chaiyuntian on 2019/2/14
101
0

Log in to post a comment.

// You can find the Turtle API reference here: https://turtletoy.net/syntax
Canvas.setpenopacity(1);

// Global code will be evaluated once.
const turtle = new Turtle();
function line(x1,y1,x2,y2){turtle.penup();turtle.goto(x1,y1);turtle.pendown();turtle.goto(x2,y2);}

// masks
const L = 1;
const R = 2;
const U = 4;
const D = 8;
const IN = 16;

function opposite(direction)
{
    if(direction == L)return R;
    if(direction == R)return L;
    if(direction == U)return D;
    if(direction == D)return U;
}

// canvas parameters
let width = 200.0
let height = 200.0

let margin = 5.0

let maze_width  = width - margin*2.0;
let maze_height = height - margin*2.0;
let maze_left = -maze_width*0.5;
let maze_top = -maze_height*0.5;

// maze
const num_grid = 120;

grid_size = maze_width/num_grid;

let map =new Array();
for(let y=0;y<num_grid;y++)
{
    map[y]=new Array(); 
    for(let x=0;x<num_grid;x++){
        map[y][x]=0;
    }
}

let front = new Set()

function valid(x,y)
{
    return x>=0 && x<num_grid && y>=0 && y<num_grid
}

function inside(x,y)
{
    return map[y][x] & IN;
}

function neighbors(x,y)
{
    let nb = new Array();
    if(valid(x-1,y) && inside(x-1,y)){nb.push([x-1,y,L]);}
    if(valid(x+1,y) && inside(x+1,y)){nb.push([x+1,y,R]);}
    if(valid(x,y-1) && inside(x,y-1)){nb.push([x,y-1,U]);}
    if(valid(x,y+1) && inside(x,y+1)){nb.push([x,y+1,D]);}
    return nb;
}

function get_xy(id){
    return [Math.floor(id/num_grid),id%num_grid];
}

function id(x,y){
    return x*num_grid+y;
}

function add_front(x,y){
    if(valid(x,y) && !inside(x,y)){
       front.add(id(x,y))
    }
}

function mark(x,y)
{
    map[y][x] |= IN;
    add_front(x-1,y);
    add_front(x+1,y);
    add_front(x,y-1);
    add_front(x,y+1);
}

function rand_int(max) {
  return Math.floor(Math.random() * max);
}

function rand_pop(myset)
{
    let items = Array.from(myset);
    let it = items[rand_int(items.length)];
    myset.delete(it)
    return it
}

function generate_maze()
{
    // random start cell
    let start_x = rand_int(num_grid);
    let start_y = rand_int(num_grid);
    mark(start_x,start_x)
    
    let steps = 0;
    
    // generation loop
    while(front.size)
    {
        // get random element from fontier
        let xyid = rand_pop(front);
        let xy = get_xy(xyid);
        let x = xy[0],y = xy[1];
        
        // find fontier's neighbors
        nbs = neighbors(x,y);
        // pick random neighbor
        let nb = nbs[rand_int(nbs.length)];
        
        let nx = nb[0], ny = nb[1];
        let dir = nb[2];
        
        // break the wall and make a way
        map[y][x] |= dir;
        map[ny][nx] |= opposite(dir);
        steps++;
        // mark the cell as inside
        mark(x,y);
        
    }
}

generate_maze();


function draw_grid(x,y)
{
    let l = maze_left + grid_size*x;
    let r = l + grid_size;
    let t = maze_top + grid_size*y;
    let b = t + grid_size;
    let dir = map[y][x];
    
    if(!(dir&L))line(l,t,l,b);
    if(!(dir&U))line(l,t,r,t);
    if((x==num_grid-1)&&!(dir&R))line(r,t,r,b);
    if((y==num_grid-1)&&!(dir&D))line(l,b,r,b);
    
    
}

// The walk function will be called until it returns false.
function walk(i) {
    
    let xy = get_xy(i);
    let x = xy[0],y = xy[1];
    draw_grid(x,y);
    return i < num_grid*num_grid-1;//num_grid
}