Week 35 was Javascript! I do a lot of web development so I already had a ton of Javascript examples, but decided to use this as an excuse to play with Canvas, the new HTML5 element that gives a set of primitive drawing functions you can manipulate using Javascript.

On top of that, I had wanted to try a few procedural generation algorithms so I decided to take an example of generating a maze from the Procedural Content Generation WIki (a great resource, I encourage everyone to look at it and potentially contribute). There is a page explaining the Growing Tree algorithm, with a sample Python script, so I decided to take that and port it to Javascript.

It generates a 2D array filled with periods for empty floor, and hash marks for walls. The drawing function then simply loops through it and draws a colored rectangle to the appropriate location. It could be expanded to draw tiles instead of simple filled rectangles as well.


Live example of creating the maze and then manipulating Canvas


This example uses color droppers from http://jscolor.com/ as an UI aid, and the maze generation is ported as directly as possible from the Python script on the PCG wiki. There is also a useful function to shuffle a Javascript array taken from http://snippets.dzon.../posts/show/849 .

Now to go over the various functions-

Initializing Canvas

var canvas;
var ctx;
var maze;

$(document).ready(function(){ init(); });

function init(){
	canvas = $("#cvMain");
	canvas = canvas[0];
	ctx = canvas.getContext('2d');

	//fill bg
	ctx.fillStyle = "rgb(158,153,94)";
	ctx.fillRect(0,0,800,600);

	maze = createMaze(0,0,60,80);
	drawMaze(ctx,maze,0,0);
}

I setup a couple globals to hold the canvas object, the context (the actual surface you draw on), and the 2d array for the maze data;
Next is binding the init function to the document ready event. This makes sure that the code isn't called before the actual html objects are parsed, which is generally always a good idea when manipulating the html dom.
The init function grabs the canvas and it's context, fills it with a background color, and calls the maze functions.

Onto maze generation, put in a seperate JS file
first, I use a few globals, which isn't very good coding practice but made this example much simpler:

var mazeW; var mazeH; var field; var frontier;
var debugConsole = 0; //set to 1 to print errors to console. Requires chrome or firebug

field is a 2d array that holds the map data, and frontier list of all the next map positions for the algorithm to check. These could be passed between functions if you wanted to encapsulate your data better.

The main createMaze function

//create a maze based off python growing tree algorithm at http://pcg.wdfiles.com/local--files/pcg-algorithm:maze/growingtree.py
//returns field, an array of said size
function createMaze(x,y,rows,cols){
	//the grid of the maze
	// # is wall  . is empty space  , is exposed but undertemined  ? is unexposed and undertermined
	field = new Array();
	mazeH = rows;
	mazeW = cols;
	
	debug("Creating a "+cols+" by "+cols+" big maze");
	
	//populate grid with ?'s
	for(var i=0; i<rows;i++){
		var row = new Array();
		for(var ii=0; ii<cols; ii++){
				row.push('?');
		}
		field.push(row);
	}
	
	
	//list of coordinates of exposed but undetermined cells
	frontier = new Array();
	
	//choose random starting point
	var xchoice = Math.floor(Math.random()*cols);
	var ychoice = Math.floor(Math.random()*rows);
	debug("starting at "+xchoice+","+ychoice);
	
	carve(new Array(ychoice, xchoice));
	
	//parameter branchrate:
	//zero is unbiased, positive will make branches more frequent, negative will cause long passages
    //this controls the position in the list chosen: positive makes the start of the list more likely,
    //negative makes the end of the list more likely
    //large negative values make the original point obvious
    //try values between -10, 10 
	var branchrate = 0;
	
	debug("Starting main loop. Frontier is "+frontier.length+" long");
	
	
	while(frontier.length > 0){
		var pos = Math.random();
		pos = Math.pow(pos,Math.pow(Math.E,-branchrate));
		var rpos = Math.floor(pos * frontier.length);
		var choice = frontier[rpos];
		debug("frontier: "+frontier.length+" - rpos: "+rpos+" - choice: "+choice);
		if (check(choice)){
			carve(choice);
		}
		else {
			harden(choice);
		}
		frontier.splice(rpos,1);
	}
	
	for(var iy=0; iy<rows; iy++){
		for(var ix=y; ix<cols; ix++){
			if(field[y][x] == '?'){ field[y][x] = '#'; }
		}
	} 
	
	
	//Done return it
	return field;
}

I left the comments from the original python code to help tell how it works. The main while loop itself is fairly small and relies on the next few functions for choosing whether a position should be wall or floor. The debug() calls is a small custom function I use that outputs the string to your Javascript console if you are using Chrome or Firefox w/Firebug . Since leaving it on would break the code in other browsers, I have it toggled as a global.

Check() is the bulk of the code, which essentially just a whole bunch of conditionals to see if the square needs to become an empty space. The checks under "if(diagonal)" are optional if the maze character cannot move diagonally.

 
function check(posi) {
    var y = posi[0]; var x = posi[1];
	var nodiagonals = 1; //make the default to check for diagonals 
	if(posi[2]){ nodiagonals = posi[2]; }
	
	debug("Check: "+posi);

	var edgestate = 0;
    if (x > 0) {
        if (field[y][x-1] == '.'){
            edgestate += 1 ;
		}
	}
    if (x < mazeW-1){
        if (field[y][x+1] == '.'){
            edgestate += 2;
		}
	}
    if (y > 0){
        if (field[y-1][x] == '.'){
            edgestate += 4;
		}
	}
    if (y < mazeH-1){
        if (field[y+1][x] == '.'){
            edgestate += 8 ;
		}
	}
	
	if(nodiagonals){
		if (edgestate == 1){
            if (x < mazeW-1){
                if (y > 0){
                    if (field[y-1][x+1] == '.'){
                        return 0;
					}
				}
                if (y < mazeH-1){
                    if (field[y+1][x+1] == '.'){
                        return 0;
					}
				}
            return 1;
			}
		}
        else if ( edgestate == 2){
            if (x > 0){
                if (y > 0){
                    if (field[y-1][x-1] == '.'){
                        return 0;
					}
				}
                if (y < mazeH-1){
                    if (field[y+1][x-1] == '.'){
                        return 0;
					}
				}
            return 1;
			}
		}
        else if ( edgestate == 4){
            if (y < mazeH-1){
                if (x > 0){
                    if (field[y+1][x-1] == '.'){
                        return 0;
					}
				}
                if (x < mazeW-1){
                    if (field[y+1][x+1] == '.'){
                        return 0;
					}
				}
            return 1;
			}
		}
        else if ( edgestate == 8){
            if (y > 0){
                if (x > 0){
                    if (field[y-1][x-1] == '.'){
                        return 0;
					}
				}
                if (x < mazeW-1){
                    if (field[y-1][x+1] == '.'){
                        return 1;
					}
				}
			return 1;
			}
		}
		return 0;
	}
	else {
		var diags = new Array(1,2,4,8);
		if( arrayCount(diags,edgestate) ){
			return 1;
		}
		return 0;
	}
    

}

The next two functions just make a certain map position a space or wall. If a space is made, then it checks the surrounding positions to see if they have been processed, and if not it adds it to the list

//make a cell at y,x a space
function carve(posi) {
	var y = posi[0]; var x = posi[1];
	debug("Carve: "+field.length+" - "+frontier.length+" at "+y+","+x);
	var extra = new Array();
	field[y][x] = '.' ;
	if (x > 0){
		if (field[y][x-1] == '?') {
			field[y][x-1] = ',';
			extra.push(new Array(y,x-1));
		}
	}
	if (x < mazeW - 1){
		if (field[y][x+1] == '?') {
			field[y][x+1] = ',';
			extra.push(new Array(y,x+1));
		}
	}
	if (y>0){
		if (field[y-1][x] == '?') {
			field[y-1][x] = ',';
			extra.push(new Array(y-1,x));
		}
	}
	if (y < mazeH - 1){
		if (field[y+1][x] == '?') {
			field[y+1][x] = ',';
			extra.push(new Array(y+1,x));
		}
	}
	//debug("extra length: "+extra.length+" : "+extra);
	extra = shuffle(extra);
	frontier = frontier.concat(extra);
}

//make the cell at y,x a wall
function harden(posi) {
	var y = posi[0]; var x = posi[1];
	field[y][x] = '#';
}

Then finally, after the maze is made you'll want to display it, so drawMaze will draw it onto the specified canvas context:

//draw a generated maze. Uses a field array and from drawMaze
//ctx-canvas context. field - maze array. csize - size of each tile. ccolors - array defining what color to draw the tiles
function drawMaze(ctx, field, csize, ccolors) {
	ctx.fillStyle = "rgb(35,35,5)";
	var cellsize = 10;
	if(csize){ cellsize = csize; }
	var cellcolors = "rgb(35,35,5)";
	if(ccolors){ cellcolors = ccolors; ctx.fillStyle = cellcolors; }
	for(var y=0; y<field.length; y+=1){
		var row = field[y];
		for(var x=0; x<row.length; x+=1){
			if(row[x] == '#'){
				//ctx.fillStyle = "rgb(35,35,5)";
				ctx.fillRect(x*cellsize,y*cellsize,cellsize,cellsize);
			}
			else if(row[x] == '.'){
				
			}
			else {
				debug(x+","+y+" is a "+row[x]);
				//ctx.fillStyle = "rgb(117,209,96)";
				ctx.fillRect(x*cellsize,y*cellsize,cellsize,cellsize);
			}
		}	
	}
}