Image 15-Puzzle mechanics
canvasgamedevtutorialjavascripthtmlarchivedImage 15 Puzzle theory
Remember those Image Puzzle (otherwise known as 15-puzzle, 16-puzzle, or variants thereof), where you have to slide around sections of an image to get it into order?
If you're as old as me, perhaps you had some of those little plastic handheld ones?
Personally, I was terrible at them and used to pop the pieces out and cheat, but whilst I'm not great help at solving them, I can at least show you how to write them. First of all, let's look at how they work...
15-Puzzle mechanics
We start with an image with a known width and height, and a known number of tiles we want to section the image in to (gridW, gridH):
[Tile Object]:
[image position] = [x, y];
[canvas position] = [x, y];
[Image Tiles] = Array();
[Free Position] = [(gridW - 1), (gridH - 1)];
for y = 0 to (gridH - 1):
for x = 0 to (gridW - 1):
if x==(gridW - 1) and y==(gridH - 1) then skip;
t = new [Tile Object];
t.[image position] = [x, y];
t.[canvas position] = [x, y];
[Image Tiles].add( t );
end x loop
end y loop
This gives us a grid where each image segment is on the same position on the canvas (or game screen) as it is on the source image, with a tile at the bottom right of the image not included. This is how the puzzle will look when it's solved, but wouldn't make for an interesting game, so lets look at how we'll shuffle this grid.
Shuffling the 15-puzzle
With our [Image Tiles], and the "hole" or free position at [gridW - 1, gridH - 1]. Shuffling is quite simple:
for i = 0 to (some number, let's say 100):
[dir] = (Select random direction; up, down, left, or right);
if [Free Position] modified by [dir] is in map bounds:
swap [Free Position] and [Image Tiles] entry at ([Free Position] modified by [dir])'s [canvas position]
end if
end i loop
In other words, for each loop iteration we choose a cardinal direction, and if the tile in this direction relative to the [Free Position] is inside the grid bounds; if so, we swap the [Free Position] coordinates and the [Tile Object]'s [canvas position] property in this direction.
This works as though you had taken the solved puzzle and shifted pieces around the board at random to shuffle it.
The HTML Document
Firstly, we'll create a HTML Document with a reference to our external Javascript file in the head (which we'll call image-puzzle-game.js), and a Canvas element in the Body, with a width and height of 400 and 300 pixels respectively and the id game:
<!DOCTYPE html>
<html>
<head>
<script type="text/javascript" src="image-puzzle-game.js"></script>
</head>
<body>
<canvas id="game" width="400" height="300"></canvas>
</body>
</html>Globals, mouse, and tile object
We'll start by creating some global variables. These will be used throughout the script. The first of these will be ctx which will provide a reference to the Canvas elements 2D drawing context, and tileW, tileH, which will specify the width and height of each tile the images are divided into in pixels. These Canvas dimensions should be divisible by these values with no remainder.
var ctx = null;
var tileW = 125, tileH = 100;We also need some globals to keep track of the images we'll be using for these puzzles:
var imageURLs = ["img1.jpg", "img2.jpg", "img3.jpg"];
var images = [];
var imageTiles = [];
var imageBest = [];
var imageIndex = 0;The first of these, imageURLs is an array of paths or absolute URLs of the images our game will use. We can use as many as we want - once the player completes one puzzle they'll be moved to the next. Images should have the same dimensions as the Canvas element.
The second variable, images, is an array of the Image objects as we begin loading them from the specified URLs. imageTiles will be an array of Tile objects (we'll create this class later) that make up the current image puzzle, and imageBest is an array of the best completion scores (the lowest number of moves) to complete each image puzzle.
Additionally, imageIndex is the array index of the image the player is currently puzzling over - we'll start at 0, the first image in the list.
Our other globals are as follows:
var freePos = [0,0];
var loadCount = imageURLs.length;
var movesTaken = 0;Where freePos is the x, y grid position where the "hole" or missing image tile is (to allow moving around tiles), loadCount is the number of images we need to load before the game can begin (to start with, this is all the images, so we just use the length of the imageURLs array), and movesTaken is the number of moves taken so far to solve the current puzzle.
Mouse status
We'll be using mouse clicks to move puzzle segments, so we'll keep track of the with an object called mouseState:
var mouseState = {
click : null
};The click property records the position of the last mouse click event on the Canvas in the form of an array ([x, y]), or null if no new click event needs to be processed.
Tile Object
We'll also create a tile object for keeping keeping track of each section of the image.
function Tile()
{
this.imgPos = [0, 0];
this.canvasPos = [0, 0];
}The Tile object has two properties: imgPos, which is the x, y offset of this tile segment on the source image (the grid position, not the pixel position; these values must be multiplied by tileW and tileH to get the pixel position); the other property, canvasPos, is the grid position of this segment on the Canvas element or game screen. Again, to get the pixel position these values must be multiplied by tileW, tileH.
New level and Shuffling
When we start a new level, such as when the game first starts or a new image is loaded after another has been completed, the startLevel method is called with the index of the image this puzzle will be formed from in the images array, idx.
This method begins by setting the imageIndex global to the idx value passed, emptying the imageTiles array, and resetting the imageIndex to 0:
function startLevel(idx)
{
imageIndex = idx;
imageTiles.length = 0;
movesTaken = 0;We then calculate the number of grid rows and columns by rounding down the current images width and height divided by the tileW, tileH values and subtracting 1 from each value (as our arrays are 0 based), and set the freePos x, y values to the bottom right of the grid, xMax, yMax:
var yMax = Math.floor(images[idx].height / tileH) - 1;
var xMax = Math.floor(images[idx].width / tileW) - 1;
freePos = [xMax, yMax];To create each segment or Tile of the image puzzle, we'll now loop over the rows and columns from y = 0 to yMax, and x = 0 to xMax.
for(var y = 0; y <= yMax; y++)
{
for(var x = 0; x <= xMax; x++)
{First, we'll check if we've reached the bottom-right of the grid; if so, we'll finish here without creating a Tile, as this will be the empty space or "hole":
if(x==xMax && y==yMax) { break; }We'll now create a Tile for the image; its position on the source image and the Canvas will be the x, y values of the current loop iterations (we'll shuffle later), and add the object to the imageTiles global array.
var t = new Tile();
t.imgPos = [x, y];
t.canvasPos = [x, y];
imageTiles.push(t);We'll now close the loops and call the shuffle method before closing the startLevel function completely:
}
}
shuffle();
}Shuffling the 15-puzzle
Our shuffle method begins by calculating the maximum x and y values on the grid:
function shuffle()
{
var yMax = Math.floor(images[imageIndex].height / tileH) - 1;
var xMax = Math.floor(images[imageIndex].width / tileW) - 1;We'll then create a loop that we'll run as many times as we want to randomly swap pieces on the grid. In our example, we're using the value 150 for the number of swaps we want to perform. For each iteration we'll generate a random value between 0 and 1 and assign it to the r variable, and we'll copy the x, y values of the freePos global to the mov variable.
for(var i = 0; i < 150; i++)
{
var r = Math.random();
var mov = [freePos[0], freePos[1]];Depending on the value of r we'll try and move the "hole" up (<0.25), right (0.25-0.5), down (0.5-0.75), or left (0.75-1): we'll check that modifying the corresponding freePos x or y value would still be in grid bounds, and if so we'll update the freePos position.
if(r < 0.25 && freePos[1]>0) { freePos[1]--; }
else if(r < 0.5 && freePos[0]<xMax) { freePos[0]++; }
else if(r < 0.75 && freePos[1]<yMax) { freePos[1]++; }
else if(freePos[0]>0) { freePos[0]--; }Next, we'll loop over all of the imageTiles entries, and if one of them has canvasPos coordinates that match the freePos coordinates, we'll change the entry's canvasPos coordinates to the previous freePos position, stored in the mov variable and exit the loop:
for(var it in imageTiles)
{
if(imageTiles[it].canvasPos[0]==freePos[0] &&
imageTiles[it].canvasPos[1]==freePos[1])
{
imageTiles[it].canvasPos = [
mov[0], mov[1]
];
break;
}
}We can then close the shuffling main loop and the method itself:
}
}Updating and current state
Every time the player moves a tile, we'll check to see if the puzzle is completed. This is very simple - we'll use a function called checkState, and we'll loop over all of the imageTiles and check if the imagePos x, y matches the the canvasPos x, y.
If this is not the case for any image tiles, the puzzle is not finished so we just return out of the function:
function checkState()
{
for(var i in imageTiles)
{
if(imageTiles[i].imgPos[0]!=imageTiles[i].canvasPos[0] ||
imageTiles[i].imgPos[1]!=imageTiles[i].canvasPos[1])
{
return;
}
}If all tiles have been checked, the level is complete. We check and see if the movesTaken is better than the current imageBest entry for the current imageIndex, or if there is not currently a recorded total (the imageBest entry is 0). If so, we update the imageBest entry for this imageIndex:
if(movesTaken<imageBest[imageIndex] || imageBest[imageIndex]==0)
{
imageBest[imageIndex] = movesTaken;
}Lastly, this function will start the next level; this will be imageIndex + 1, or 0 if this was the last image in the list. Afterwards, we can close the function.
startLevel((imageIndex + 1)>=images.length ? 0 : (imageIndex + 1));
}Game Update method
Our update method, updateGame, which is run each frame, only needs to do anything if there's a new click event the process, so we check that first:
function updateGame()
{
if(mouseState.click!=null)
{We then calculate the tile on which the click event fell by rounding down the event x, y values divided by the tileW, tileH values respectively:
var tile = [
Math.floor(mouseState.click[0]/tileW),
Math.floor(mouseState.click[1]/tileH)
];We'll then create a tileIdx variable to store the index of the tile on which the event fell in the imageTiles array, and loop through the array to see if our tile matches the canvasPos property of any of these tiles. If it does, we update the tileIdx to the corresponding index and leave the loop.
var tileIdx = -1;
for(var i in imageTiles)
{
if(imageTiles[i].canvasPos[0]==tile[0] &&
imageTiles[i].canvasPos[1]==tile[1])
{
tileIdx = i;
break;
}
}If no index has been found (a valid tile was not clicked on), we clear the click event and leave the function.
if(tileIdx==-1)
{
mouseState.click = null;
return;
}If a valid Tile was clicked on, we'll look above, below, left and right of this tile to see if the freePos is neighbouring it. If so, we'll swap the Tile canvasPos values with the freePos values and increase the movesTaken counter.
if(tile[0]==freePos[0] && tile[1]==(freePos[1]-1))
{
freePos[1]-= 1;
imageTiles[i].canvasPos[1]+= 1;
movesTaken++;
}
else if(tile[0]==freePos[0] && tile[1]==(freePos[1]+1))
{
freePos[1]+= 1;
imageTiles[i].canvasPos[1]-= 1;
movesTaken++;
}
else if(tile[1]==freePos[1] && tile[0]==(freePos[0]-1))
{
freePos[0]-= 1;
imageTiles[i].canvasPos[0]+= 1;
movesTaken++;
}
else if(tile[1]==freePos[1] && tile[0]==(freePos[0]+1))
{
freePos[0]+= 1;
imageTiles[i].canvasPos[0]-= 1;
movesTaken++;
}After, we'll clear the click event, call the checkState method to see if the puzzle is complete, and close the if block and function.
mouseState.click = null;
checkState();
}
}Window onload
When the window has loaded we need to do a few things, so we'll use the window.onload event to do so. First of all, we'll assign the ctx global a reference to the Canvas 2D drawing context, and then set a font for the Canvas.
window.onload = function()
{
ctx = document.getElementById('game').getContext('2d');
ctx.font = "bold 10pt sans-serif";We'll also add a click event handler for the Canvas element that will update the mouseState.click property with the coordinates of the event relative to the top-left of the Canvas:
document.getElementById('game').addEventListener('click', function(e) {
var pos = realPos(e.pageX, e.pageY);
mouseState.click = pos;
});Loading images
We'll then loop through all of the images we want to load from the imageURLs array. For each entry, we'll begin by creating a new Image object:
for(var i in imageURLs)
{
var img = new Image();If the image fails to load, we'll alert the user, and clear the ctx variable, essentially ending the script from performing further actions.
img.onerror = function()
{
ctx = null;
alert("Failed loading image " + this.src);
};If the image loads, we'll have the onload event handler log the loading of the image to the developer console, and decrease the loadCount global by 1. If loadCount now equals 0, we know all images have been loaded and we start the first level:
img.onload = function()
{
console.log("Image loaded " + this.src);
loadCount--;
if(loadCount==0)
{
startLevel(0);
}
};Now our event handlers are ready, we begin loading this image by setting its src attribute to the URL we're currently loading, and push the object on to the images array. We also push a value of 0 on to the imageBest array to signify that there is not current best score (lowest move count) for this image, and end the image loading loop.
img.src = imageURLs[i];
images.push(img);
imageBest.push(0);
}Finally, before closing the onload method, we'll let the browser know the drawGame method will handle drawing when it's ready for us to modify the Canvas.
requestAnimationFrame(drawGame);
};Mouse position helper
We'll also add in a helper function: this converts the mouse coordinates from their position on the screen to their actual position on the Canvas element:
function realPos(x, y)
{
var p = document.getElementById('game');
do {
x-= p.offsetLeft;
y-= p.offsetTop;
p = p.offsetParent;
} while(p!=null);
return [x, y];
}Main game loop
Our drawGame method will handle drawing to the Canvas, as well as updating the game where needed. First of all though, we'll perform a couple of checks. If the ctx global is null, we'll simply quit the function and the script will not be doing any further processing - this is to handle failed image loading.
We'll also check if all of the images have loaded. If not, we'll tell the browser to check back with us when it's ready for us to draw to the Canvas again, and then leave the function as there's nothing more we currently want to do in this case:
function drawGame()
{
if(ctx==null) { return; }
if(loadCount>0) { requestAnimationFrame(drawGame); return; }Next we'll call the updateGame method to process any click events, and the set the fill colour to plain white and clear the whole Canvas by drawing a rectangle at 0, 0 (the top left of the Canvas) that has the same width and height as the Canvas element:
updateGame();
ctx.fillStyle = "#ffffff";
ctx.fillRect(0, 0, 400, 300);We'll then loop over all of the imageTiles, and draw the corresponding section of the current image from the imgPos property of the Tile at its current position on the Canvas, canvasPos with the dimensions tileW, tileH:
for(var i in imageTiles)
{
ctx.drawImage(images[imageIndex],
imageTiles[i].imgPos[0] * tileW,
imageTiles[i].imgPos[1] * tileH,
tileW, tileH,
imageTiles[i].canvasPos[0] * tileW,
imageTiles[i].canvasPos[1] * tileH,
tileW, tileH);
}We'll then set the stroke colour to black, and stroke and fill some text in the top-left corner to show the number of moves currently taken to complete this puzzle:
ctx.strokeStyle = "#000000";
ctx.strokeText("Moves: " + movesTaken, 10, 20);
ctx.fillText("Moves: " + movesTaken, 10, 20);If there's also a current best score for this image, we'll show that also just below this text:
if(imageBest[imageIndex]>0)
{
ctx.strokeText("Best: " + imageBest[imageIndex], 10, 30);
ctx.fillText("Best: " + imageBest[imageIndex], 10, 30);
}Once this is done, we'll let the browser know to call this drawGame method again when it's ready for us to next update the Canvas, and close the function.
requestAnimationFrame(drawGame);
}Javascript source code
var ctx = null;
var tileW = 125, tileH = 100;
var imageURLs = ["img1.jpg", "img2.jpg", "img3.jpg"];
var images = [];
var imageTiles = [];
var imageBest = [];
var imageIndex = 0;
var freePos = [0,0];
var loadCount = imageURLs.length;
var movesTaken = 0;
var mouseState = {
click : null
};
function Tile()
{
this.imgPos = [0, 0];
this.canvasPos = [0, 0];
}
function startLevel(idx)
{
imageIndex = idx;
imageTiles.length = 0;
movesTaken = 0;
var yMax = Math.floor(images[idx].height / tileH) - 1;
var xMax = Math.floor(images[idx].width / tileW) - 1;
freePos = [xMax, yMax];
for(var y = 0; y <= yMax; y++)
{
for(var x = 0; x <= xMax; x++)
{
if(x==xMax && y==yMax) { break; }
var t = new Tile();
t.imgPos = [x, y];
t.canvasPos = [x, y];
imageTiles.push(t);
}
}
shuffle();
}
function shuffle()
{
var yMax = Math.floor(images[imageIndex].height / tileH) - 1;
var xMax = Math.floor(images[imageIndex].width / tileW) - 1;
for(var i = 0; i < 150; i++)
{
var r = Math.random();
var mov = [freePos[0], freePos[1]];
if(r < 0.25 && freePos[1]>0) { freePos[1]--; }
else if(r < 0.5 && freePos[0]<xMax) { freePos[0]++; }
else if(r < 0.75 && freePos[1]<yMax) { freePos[1]++; }
else if(freePos[0]>0) { freePos[0]--; }
for(var it in imageTiles)
{
if(imageTiles[it].canvasPos[0]==freePos[0] &&
imageTiles[it].canvasPos[1]==freePos[1])
{
imageTiles[it].canvasPos = [
mov[0], mov[1]
];
break;
}
}
}
}
function checkState()
{
for(var i in imageTiles)
{
if(imageTiles[i].imgPos[0]!=imageTiles[i].canvasPos[0] ||
imageTiles[i].imgPos[1]!=imageTiles[i].canvasPos[1])
{
return;
}
}
if(movesTaken<imageBest[imageIndex] || imageBest[imageIndex]==0)
{
imageBest[imageIndex] = movesTaken;
}
startLevel((imageIndex + 1)>=images.length ? 0 : (imageIndex + 1));
}
function updateGame()
{
if(mouseState.click!=null)
{
var tile = [
Math.floor(mouseState.click[0]/tileW),
Math.floor(mouseState.click[1]/tileH)
];
var tileIdx = -1;
for(var i in imageTiles)
{
if(imageTiles[i].canvasPos[0]==tile[0] &&
imageTiles[i].canvasPos[1]==tile[1])
{
tileIdx = i;
break;
}
}
if(tileIdx==-1)
{
mouseState.click = null;
return;
}
if(tile[0]==freePos[0] && tile[1]==(freePos[1]-1))
{
freePos[1]-= 1;
imageTiles[i].canvasPos[1]+= 1;
movesTaken++;
}
else if(tile[0]==freePos[0] && tile[1]==(freePos[1]+1))
{
freePos[1]+= 1;
imageTiles[i].canvasPos[1]-= 1;
movesTaken++;
}
else if(tile[1]==freePos[1] && tile[0]==(freePos[0]-1))
{
freePos[0]-= 1;
imageTiles[i].canvasPos[0]+= 1;
movesTaken++;
}
else if(tile[1]==freePos[1] && tile[0]==(freePos[0]+1))
{
freePos[0]+= 1;
imageTiles[i].canvasPos[0]-= 1;
movesTaken++;
}
mouseState.click = null;
checkState();
}
}
window.onload = function()
{
ctx = document.getElementById('game').getContext('2d');
ctx.font = "bold 10pt sans-serif";
// Event listeners
document.getElementById('game').addEventListener('click', function(e) {
var pos = realPos(e.pageX, e.pageY);
mouseState.click = pos;
});
for(var i in imageURLs)
{
var img = new Image();
img.onerror = function()
{
ctx = null;
alert("Failed loading image " + this.src);
};
img.onload = function()
{
console.log("Image loaded " + this.src);
loadCount--;
if(loadCount==0)
{
startLevel(0);
}
};
img.src = imageURLs[i];
images.push(img);
imageBest.push(0);
}
requestAnimationFrame(drawGame);
};
function realPos(x, y)
{
var p = document.getElementById('game');
do {
x-= p.offsetLeft;
y-= p.offsetTop;
p = p.offsetParent;
} while(p!=null);
return [x, y];
}
function drawGame()
{
if(ctx==null) { return; }
if(loadCount>0) { requestAnimationFrame(drawGame); return; }
updateGame();
ctx.fillStyle = "#ffffff";
ctx.fillRect(0, 0, 400, 300);
for(var i in imageTiles)
{
ctx.drawImage(images[imageIndex],
imageTiles[i].imgPos[0] * tileW,
imageTiles[i].imgPos[1] * tileH,
tileW, tileH,
imageTiles[i].canvasPos[0] * tileW,
imageTiles[i].canvasPos[1] * tileH,
tileW, tileH);
}
ctx.strokeStyle = "#000000";
ctx.strokeText("Moves: " + movesTaken, 10, 20);
ctx.fillText("Moves: " + movesTaken, 10, 20);
if(imageBest[imageIndex]>0)
{
ctx.strokeText("Best: " + imageBest[imageIndex], 10, 30);
ctx.fillText("Best: " + imageBest[imageIndex], 10, 30);
}
requestAnimationFrame(drawGame);
}