Viewing Program

Program Data

Program thumbnail for "{props.program.title}"

Title	Maze Generator
ID	6306847405637632
Created	11 years ago, 1411231076823
Updated	11 years ago, 1411366644383
Code	/* THIS IS NOT A GAME ... This is just an exercise in maze generation. A program to flesh out a maze generating algorithm. UPDATE: I've finished the algorithm, and made a simple game out of it: http://www.khanacademy.org/cs/maze-run/4565274112294912 The questions this program tries to answer are: 1. are there enough turns (few long straightaways) 2. are there enough decision points (difficulty level) 3. does every part of the grid get used? (no blank areas) Do be aware that this program repeatedly draws the grid as it is building the maze which slows down the process. For actual use the code in the draw function would be wrapped in a 'test if done' loop and allowed to run full speed... Once this is running well, what sort of algorithm is needed to find the path through the maze? I'm thnking I can just walk through the maze and drop a bread crumb at every decision point so if I hit a dead end, I can drop back to the previous decision point and try a new direction.... I've added TURNS and DECISIONS to the top of the program so you can change them and see how these effect the maze. Turns is dependant on not opting to add a decision point. So more decisions means less chances to turn. Both values must be between 0 and 1. / var DECISIONS = 0.3; var TURNS = 0.9; var ROWS = 49; var COLS = 49; // must be odd ROWS = ROWS \| 1; COLS = COLS \| 1; var curs = {s:0, x:1, y:1, dx:1, dy:0}; var nodes = []; var grid = []; grid.get = function(x, y){ if (grid[yCOLS + x] === undefined){ return -1; } else { return (grid[yCOLS + x]===false)?false:true; } }; grid.set = function(x, y, v){ grid[yCOLS + x] = (v===false)?false:true; }; grid.draw = function(flags) { // cell borders? if (flags & 1) { stroke(96); } else { noStroke(); } var siz = floor( (COLS>ROWS) ? 399/COLS : 399/ROWS); // draw grid for (var y=0; y<ROWS; y++){ for (var x=0; x<COLS; x++){ fill((grid.get(x, y))?255:0); rect(xsiz, ysiz, siz, siz); } } // end markers? if (flags & 2){ fill(0, 192, 0); rect(siz, siz, siz, siz); fill(255, 0, 0); rect((COLS-2)siz, (ROWS-2)siz, siz, siz); // mark decision points var tst; fill(128, 204, 255); for (var y=1; y<ROWS-1; y+=2){ for (var x=1; x<COLS-1; x+=2){ tst = 0; tst += (get((x+1)siz+3, ysiz+3) & 1); tst += (get((x-1)siz+3, ysiz+3) & 1); tst += (get(xsiz+3, (y+1)siz+3) & 1); tst += (get(xsiz+3, (y-1)siz+3) & 1); if (tst>2){ ellipse(xsiz+siz/1.9, ysiz+siz/1.9, siz/2, siz/2); } } } } }; grid.reset = function(){ for (var i=0; i<ROWS*COLS; i++){ grid[i]=false; } }; curs.push = function(){ nodes.push({x:this.x, y:this.y}); }; curs.pop = function(){ var pos = nodes.pop(); this.x = pos.x; this.y = pos.y; }; curs.atIntersection = function(){ return (this.x & this.y & 1)?true:false; }; curs.test = function(){ // finds available directions from current cursor location var rtn = []; if (this.x>2){ if (!grid.get(this.x-2, this.y)){ rtn.push({dx:-1, dy:0}); } } if (this.x<COLS-2){ if (!grid.get(this.x+2, this.y)){ rtn.push({dx:1, dy:0}); } } if (this.y>2){ if (!grid.get(this.x, this.y-2)){ rtn.push({dx:0, dy:-1}); } } if (this.y<ROWS-2){ if (!grid.get(this.x, this.y+2)){ rtn.push({dx:0, dy:1}); } } return rtn; }; curs.mark = function(){ grid.set(this.x, this.y, 1); }; curs.move = function(){ this.x += this.dx; this.y += this.dy; // save crumb? if (this.atIntersection() && this.test().length>1){ this.push(); } }; curs.forward = function(){ // determines if cursor can move ahead if (this.dx<0 && this.x>1){ return !grid.get(this.x-2, this.y); } if (this.dx>0 && this.x<COLS-2){ return !grid.get(this.x+2, this.y); } if (this.dy<0 && this.y>1){ return !grid.get(this.x, this.y-2); } if (this.dy>0 && this.y<ROWS-2){ return !grid.get(this.x, this.y+2); } return false; }; var pick = function(list){ // picks a random direction from (test) list var r = floor(random(list.length)); if (list.length){ var d = list[r]; curs.dx = d.dx; curs.dy = d.dy; } }; // Init grid grid.reset(); curs.mark(); curs.push(); grid.draw(1); frameRate(44); draw = function(){ // test if done if (nodes.length<1){ grid.draw(2); noLoop(); return; } // can move forward ? if (curs.forward()){ curs.move(); curs.mark(); // must backtrack } else { var tst; do { // bail out if no crumbs left if (nodes.length < 1){return;} // get next crumb curs.pop(); // find available directions tst = curs.test(); } while (tst.length<1); // pick a direction from test list pick(tst); // resave spot if it has multiple directions to go if (tst.length>1){ curs.push(); } } if (curs.atIntersection()) { grid.draw(1); // pick a random bread crumb ? if (random() < DECISIONS){ // save current spot if (curs.test().length){ curs.push(); } // pick a random node (crumb) var r = floor(random(nodes.length)); var n = nodes[r]; // set cursor to new spot curs.x = n.x; curs.y = n.y; pick(curs.test()); // make a random turn ? } else if (random()<TURNS){ var tst = curs.test(); // save current spot ? if (tst.length>1){ curs.push(); } pick(tst); } } };
Folds
Fork	false
Key	ag5zfmtoYW4tYWNhZGVteXIXCxIKU2NyYXRjaHBhZBiAgJC6tYGaCww
Votes	179
Spin-Offs	20
Type	PJS
Width	400
Height	400
User Flagged	false
Origin Scratchpad	null
Hidden From Hotlist	false
Restricted Posting	false
By Child	false
Author Nick	Larry Serflaten
Author Name	LarrySerflaten
Author ID	kaid_271442154897019790150825
Author Profile Access	COACH

Archive Data

Added	10 months ago, 1739456315803
Updated	10 months ago, 1739456323449
Source Deleted	unknown