function World() {

    	this.tileWidth = 40;
    	this.tileHeight = 40;
    	
        this.position = { 'x' : 0, 'y' : 0 };
        this.matrix = null;
        this.objects = null;
        
        
    }
    
    World.prototype.getGridWidth = function() {
    	return this.matrix[0].length;
    }
    
    World.prototype.getGridHeight = function() {
    	return this.matrix.length;
    }
    
    World.prototype.getWidth = function() {
    	return this.matrix[0].length * this.tileWidth;
    }
    
    World.prototype.getHeight = function() {
    	return this.matrix.length * this.tileHeight;
    }
    

    World.prototype.update = function(elapsed) {
    	
    	if (frog.moving) {
        	var movement = elapsed * this.speed;
        	if (this.direction == UP) {
        		this.position.y -= movement;
        	} else if (this.direction == DOWN) {
        		this.position.y += movement;
        	} else if (this.direction == LEFT) {
        		this.position.x -= movement;
        	} else {
        		this.position.x += movement;
        	}
    		
    	}
    	
    	//frog.update(elapsed);
    	
    }
    
    World.prototype.collideWith = function(fb) {
    	
    	var gridX = Math.round((fb.center.x + (fb.width / 2)) / world.tileWidth) - 1; 
    	var gridY = Math.round((fb.center.y + (fb.height / 2)) / world.tileHeight) - 1;
    	
    	for (var i = gridY - 1; i <= gridY + 1; i++) {
    		for (var j = gridX - 1; j <= gridX + 1; j++) {
    			if (this.objects[i]) {
    				var o = this.objects[i][j];
    				if (o != null && o.boxcenter && o.blocking) {
    					var c = new Point(((j*world.tileWidth) + (this.tileWidth / 2)), ((i*world.tileHeight) + (this.tileHeight / 2)));
    					var b = new Box(c, o.boxwidth, o.boxheight);
    					var intersection = fb.intersectsWith(b);
    					if (intersection) {
    						return intersection;
    					}
    				}
    			}
    			if (this.matrix[i] && this.matrix[i][j] && TileImgCache[this.matrix[i][j].id].block) {
    				var p = TileImgCache[this.matrix[i][j].id].block;
    				var rp = new Polygon({x: p.center.x, y: p.center.y});
    				rp.points = p.points;
    				rp.shiftCenter((j * world.tileWidth), (i * world.tileHeight));
					var intersection = fb.poly.intersectsWith(rp);
   					if (intersection) {
   						return intersection;
   					}
    			}
    		}
    	}
    	return false;
    	
    }
    
    World.prototype.isWaterAt = function(x, y) {
    	
    	if (this.matrix[y] && this.matrix[y][x] && TileImgCache[this.matrix[y][x].id].water) {
    		return true;
    	} else {
    		return false;
    	}
    	
    }
    
    World.prototype.draw = function(ctx) {

    	ctx.translate(viewport.x,viewport.y);
    	
        ctx.save();

        var startTileX = Math.floor(Math.abs(viewport.x) / this.tileWidth);
        var stopTileX = Math.floor(startTileX + Math.ceil(canvas.width / this.tileWidth)) + 1;

        var startTileY = Math.floor(Math.abs(viewport.y) / this.tileHeight);
        var stopTileY = Math.floor(startTileY + Math.ceil(canvas.height / this.tileHeight)) + 1;

        if (startTileX < 0) startTileX = 0;
        if (stopTileX > this.matrix[0].length) stopTileX = this.matrix[0].length;

        if (startTileY < 0) startTileY = 0;
        if (stopTileY > this.matrix.length) stopTileY = this.matrix.length;

        ctx.translate(-this.tileWidth,startTileY * this.tileHeight);
        for (var i = startTileY; i < stopTileY; i++) {
       		ctx.translate(this.tileWidth * startTileX, 0);
        	for (var j = startTileX; j < stopTileX; j++) {
        		ctx.translate(this.tileWidth, 0);
        		ctx.drawImage(TileImgCache[this.matrix[i][j].id],0,0);
        		// draw the "blocking" polygon if in debug mode
        		if (debug && TileImgCache[this.matrix[i][j].id].block) {
        			var p = TileImgCache[this.matrix[i][j].id].block;
    				var rp = new Polygon({x: p.center.x, y: p.center.y}, "red");
    				rp.points = p.points;
    				rp.shiftCenter((j * world.tileWidth), (i * world.tileHeight));
    				rp.draw(ctx);
        		}
        	}
            ctx.translate(-(this.tileWidth * stopTileX), this.tileHeight);
        }

        ctx.restore();

        this.unifiedDraw(sprites, ctx);
        
        /*
        
        for (var e = 0; e < sprites.length; e++) {
            sprites[e].draw(ctx);
        }

        if (frog) {
        	//var rowsBeforeFrog = Math.round((frog.position.y + (frog.img.height / 2)) / this.tileHeight);
        	var rowsBeforeFrog = Math.round((frog.position.y + (frog.standardHeight / 2)) / this.tileHeight);
        	this.drawStuff(0, rowsBeforeFrog-1, ctx);
        	this.drawStuffOnFrogRow(rowsBeforeFrog-1, ctx);
        	//frog.draw(ctx);
        	this.drawStuff(rowsBeforeFrog, this.objects.length, ctx);
        } else {
        	this.drawStuff(0, this.objects.length, ctx);
        }
        
        */
        
    }
    
    World.prototype.drawStuffOnFrogRow = function(row, ctx) {

    	var drawAfterFrog = new Array();
    	var innerArray = this.objects[row];
    	if (innerArray != null) {
    		for (var j = 0; j < innerArray.length; j++) {
    			var o = innerArray[j];
    			if (o != null) {
    				var px = (j * this.tileWidth) + (this.tileWidth / 2);
    				var py = (row * this.tileHeight) + (this.tileHeight / 2);
    				var offsetY = 0;
    				if (o.boxheight) {
    					offsetY = o.boxheight / 2;
    				}
    				if (o.heightOffset) {
    					py += o.heightOffset;
    				}
    				if (o.widthOffset) {
    					px += o.widthOffset;
    				}
  				    if (py + offsetY >= frog.position.y + (frog.standardHeight/2)) {
                   	    drawAfterFrog.push( { "obj":o, "x":px, "y":py } );
                    } else {
        				ctx.save();
        				ctx.translate(px, py);
    	    			if (o.boxcenter) {
    	    				if (debug) {
    		    			    var box = new Box(new Point(0, 0), o.boxwidth, o.boxheight);
    			    		    box.poly.draw(ctx);
    			                ctx.globalAlpha=0.5;
    	    				}
    					    ctx.drawImage(ObjectImgCache[o.imgid], -o.boxcenter.x, -o.boxcenter.y);
        			        if (debug) {
        			        	ctx.globalAlpha=1.0;
        			        }
        				} else {
        					var img = ObjectImgCache[o.imgid];
        					ctx.drawImage(img, -(img.width/2), -img.height);
    		    		}
    			    	ctx.restore();
                    }
    			}
    		}
    	}
    	
    	frog.draw(ctx);
    	
    	for (var i = 0; i < drawAfterFrog.length; i++) {
    	    var o = drawAfterFrog[i].obj;
    	    var px = drawAfterFrog[i].x;
    	    var py = drawAfterFrog[i].y;
			ctx.save();
			ctx.translate(px, py);
			if (o.boxcenter) {
				if (debug) {
    			    var box = new Box(new Point(0, 0), o.boxwidth, o.boxheight);
	    		    box.poly.draw(ctx);
	                ctx.globalAlpha=0.5;
				}
			    ctx.drawImage(ObjectImgCache[o.imgid], -o.boxcenter.x, -o.boxcenter.y);
		        if (debug) {
		        	ctx.globalAlpha=1.0;
		        }
			} else {
				var img = ObjectImgCache[o.imgid];
				ctx.drawImage(img, -(img.width/2), -img.height);
    		}
	    	ctx.restore();
    	}
    	
    	
    	
    	
    }
    
    World.prototype.drawStuff = function(start, end, ctx) {
    	
        for (var i = start; i < end; i++) {
        	var innerArray = this.objects[i];
        	if (innerArray != null) {
        		for (var j = 0; j < innerArray.length; j++) {
        			var o = innerArray[j];
        			if (o != null) {
        				var px = (j * this.tileWidth) + (this.tileWidth / 2);
        				var py = (i * this.tileHeight) + (this.tileHeight / 2);
        				if (o.heightOffset) {
        					py += o.heightOffset;
        				}
        				if (o.widthOffset) {
        					px += o.widthOffset;
        				}
        				ctx.save();
        				ctx.translate(px, py);
        				if (o.boxcenter) {
        					if (debug) {
        					    var box = new Box(new Point(0, 0), o.boxwidth, o.boxheight);
        					    box.poly.draw(ctx);
        			            ctx.globalAlpha=0.5;
        					}
        					ctx.drawImage(ObjectImgCache[o.imgid], -o.boxcenter.x, -o.boxcenter.y);
        					if (debug) {
        						ctx.globalAlpha=1.0;
        					}
        				} else {
        					var img = ObjectImgCache[o.imgid];
        					ctx.drawImage(img, -(img.width/2), -img.height);
        				}
        				ctx.restore();
        			}
        		}
        	}
        }
    	
    }
    
    World.prototype.unifiedDraw = function(stuff, ctx) {
    	
    	sprites = spriteSort(stuff);
    	
    	for (var i = 0; i < stuff.length; i++) {
    		stuff[i].draw(ctx);
    	}
    	
    }

    
    
    // =====================
    
    /**
     * sort an array of sprites.
     */
    function spriteSort(arr) {
    	
        if (arr.length < 2)
            return arr;
     
        var middle = parseInt(arr.length / 2);
        var left   = arr.slice(0, middle);
        var right  = arr.slice(middle, arr.length);
     
        return spriteMerge(spriteSort(left), spriteSort(right));
    	
    }
    
    function spriteMerge(left, right) {
    	
        var result = [];
        
        while (left.length && right.length) {
            //if (left[0].position.y <= right[0].position.y) {
        	if (left[0].bottom() <= right[0].bottom()) {
                result.push(left.shift());
            } else {
                result.push(right.shift());
            }
        }
     
        while (left.length)
            result.push(left.shift());
     
        while (right.length)
            result.push(right.shift());
     
        return result;
    	
    }