Thursday, August 23, 2012

Creating a Pentomino game using AS3: Part 36

Today we continue working on the solving algorithm.

Go to level_solver's onFrame() function and inside the if..statement that checks if we can put a shape in this spot add two lines. The first line calls a function called putHere(). Using this, we apply a change to tempGrid array. After that we call a function tryRemainingShapes().

Below you can see the full onFrame code with these two lines added and the parameters that we pass to these functions:

private function onFrame(evt:Event):void {
// set temporary values
tempGrid = clone(givenGrid);
tempShapes = clone(givenShapes);
// perform a new cycle
var i:int;
var u:int;
var currentShapeValues:Array;
// Take the first shape in this cycle...
currentShapeValues = clone(shapeValues[tempShapes[cycleNum]]);
// ...remove it from shapes array (so that it isn't used twice)...
tempShapes.splice(cycleNum, 1);
// ...try putting it in each available cell...
for (i = 0; i < allCells.length; i++) {
// ...try putting the shape in all 8 possible positions...
for (u = 0; u < 8; u++) {
// ...if successful, continue placing other cells...
if (canPut(currentShapeValues, allCells[i].x, allCells[i].y, tempGrid, u)) {
// ...first put the first shape on the grid...
putHere(currentShapeValues, allCells[i].x, allCells[i].y, tempGrid, u, tempShapes[cycleNum] + 2);
// ...try all remaining shapes...
tryRemainingShapes(tempShapes, tempGrid);
}
}
}
// display info
tInfo.text = 'Solving level "' + levelName + '"\nAttempts: ' + attempts + "\nSolutions: " + solutions.length;
// next cycle
nextCycle();
}

The putHere() function receives the coordinates and other info about the placed shape, and sets tempGrid's values according to the data. You can see that we set the values of occupied cells to tempShapes[cycleNum]+2 - this will ensure that we can later distinguish different shapes ont he grid, and that these values are all greater than 1:

private function putHere(currentValues:Array, cellX:int, cellY:int, mapGrid:Array, rotation:int, shape:int):void {
currentValues = clone(currentValues);
updateCurrentValues(currentValues, rotation);
for (var i:int = 0; i < currentValues.length; i++) {
var cX:int = currentValues[i][0] + cellX;
var cY:int = currentValues[i][1] + cellY;
mapGrid[cY][cX] = shape;
}
}

Now we'll add the tryRemainingShapes() function. This is possibly the most complicated part of the code. Note that this is a recursive function, which means that it will also call itself, going deeper and deeper until certain conditions are met.

The function has to receive temporary Shapes and Grid arrays. It will, however, not use the received values as references, instead it will clone the data and store the values in its own variables innerTempShapes and innerTempGrid.

With these values stored, we create a while() loop that executes itself until innerTempShapes' length is 0. We delete the first element in the array in the end of each cycle and thanks to this we can always refer to the selected element using index 0.

Loop through all cells, and loop through all 8 rotations. Check if the shape can be put, if so - put it and call tryRemainingShapes() once again. Remember to pass a modified Shapes array though - delete the first element before you do it. Then check if all cells are taken - in that case you could say that a solution is found.

After this process, take a step backwards by calling a function removeHere(). This will reset the Grid array back to what it was before putHere() was called.

private function tryRemainingShapes(tShapes:Array, tGrid:Array):void {
var innerTempShapes:Array = clone(tShapes);
var innerTempGrid:Array = clone(tGrid);
var e:int;
var t:int;
// ...take each remaining shape...
while (innerTempShapes.length > 0) {
var currentShapeValues:Array = clone(shapeValues[innerTempShapes[0]]);
// ...try putting it in each cell...
for (e = 0; e < allCells.length; e++) {
// ...rotate the shape...
for (t = 0; t < 8; t++) {
// ...check if it can be put...
if (canPut(currentShapeValues, allCells[e].x, allCells[e].y, innerTempGrid, t)) {
// ...on success, put this shape and try all remaining shapes...
putHere(currentShapeValues, allCells[e].x, allCells[e].y, innerTempGrid, t, innerTempShapes[0] + 2);
tryRemainingShapes(clone(innerTempShapes).splice(0, 1), innerTempGrid);
// ...if no empty cells remaining, then the puzzle is solved.
if (checkWin(innerTempGrid)) solutions.push(clone(innerTempGrid));
// ...step backwards...
removeHere(currentShapeValues, allCells[e].x, allCells[e].y, innerTempGrid, t);
}
}
}
// ...get rid of the shape and continue...
innerTempShapes.shift();
}
}

The checkWin() function:

private function checkWin(mapGrid:Array):Boolean {
var i:int;
var u:int;
var didWin:Boolean = true;
var width:int = mapGrid[0].length;
var height:int = mapGrid.length;

for (i = 0; i < height; i++) {
for (u = 0; u < width; u++) {
if (mapGrid[i][u] == 1) {didWin = false;}
}
}

return didWin;
}

The removeHere() function:

private function removeHere(currentValues:Array, cellX:int, cellY:int, mapGrid:Array, rotation:int):void {
currentValues = clone(currentValues);
updateCurrentValues(currentValues, rotation);
for (var i:int = 0; i < currentValues.length; i++) {
var cX:int = currentValues[i][0] + cellX;
var cY:int = currentValues[i][1] + cellY;
mapGrid[cY][cX] = 1;
}
}

Full code so far:

package  
{
import fl.controls.TextInput;
import flash.display.MovieClip;
import flash.display.Shape;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.geom.Point;
import flash.net.SharedObject;
import flash.text.TextField;
import flash.utils.ByteArray;

/**
 * Open-source pentomino game engine
 * @author Kirill Poletaev
 */

public class level_solver extends MovieClip
{

private var allCells:Array;
private var tempGrid:Array;
private var tempShapes:Array;
private var givenGrid:Array;
private var givenShapes:Array;
private var cycleNum:int;
private var attempts:int;
private var solutions:Array;
private var levelName:String;
private var shapeValues:Array;

public function level_solver() 
{
}

public function solve(levelItem:Object):void {
drawPreview(levelPreview, levelItem.grid);
tInfo.text = 'Solving level "' + levelItem.name + '"';
var shapes:Array = levelItem.shapes;
var i:int
var u:int;
givenShapes = [];
for (i = 1; i <= 12; i++) {
this["tShape" + i].text = shapes[i - 1];
for (u = 0; u < shapes[i - 1]; u++) {
givenShapes.push(i - 1);
}
}
allCells = [];
for (i = 0; i < levelItem.grid.length; i++) {
for (u = 0; u < levelItem.grid.length; u++) {
if (levelItem.grid[i][u] == 1) {
allCells.push(new Point(u, i));
}
}
}
givenGrid = levelItem.grid;
tempGrid = [];
tempShapes = [];
solutions = [];
levelName = levelItem.name;
attempts = 0;
cycleNum = 0;
shapeValues = [
[[0, 0], [0, 1], [0, 2], [0, -1], [0, -2]],
[[0, 0], [0, -1], [0, 1], [1, 0], [1, -1]],
[[0, 0], [0, 1], [0, 2], [0, -1], [ -1, -1]],
[[0, 0], [0, 1], [0, -1], [ -1, 0], [1, -1]],
[[0, 0], [ -1, 0], [ -2, 0], [0, -1], [1, -1]],
[[0, 0], [0, 1], [0, -1], [1, -1], [ -1, -1]],
[[0, 0], [1, 0], [ -1, 0], [1, -1], [ -1, -1]],
[[0, 0], [ -1, 0], [ -2, 0], [0, -1], [0, -2]],
[[0, 0], [0, 1], [ -1, 1], [1, 0], [1, -1]],
[[0, 0], [0, 1], [0, -1], [1, 0], [ -1, 0]],
[[0, 0], [ -1, 0], [ -2, 0], [1, 0], [0, -1]],
[[0, 0], [0, 1], [1, 1], [0, -1], [-1, -1]]
];
addEventListener(Event.ENTER_FRAME, onFrame);
}

private function onFrame(evt:Event):void {
// set temporary values
tempGrid = clone(givenGrid);
tempShapes = clone(givenShapes);
// perform a new cycle
var i:int;
var u:int;
var currentShapeValues:Array;
// Take the first shape in this cycle...
currentShapeValues = clone(shapeValues[tempShapes[cycleNum]]);
// ...remove it from shapes array (so that it isn't used twice)...
tempShapes.splice(cycleNum, 1);
// ...try putting it in each available cell...
for (i = 0; i < allCells.length; i++) {
// ...try putting the shape in all 8 possible positions...
for (u = 0; u < 8; u++) {
// ...if successful, continue placing other cells...
if (canPut(currentShapeValues, allCells[i].x, allCells[i].y, tempGrid, u)) {
// ...first put the first shape on the grid...
putHere(currentShapeValues, allCells[i].x, allCells[i].y, tempGrid, u, tempShapes[cycleNum] + 2);
// ...try all remaining shapes...
tryRemainingShapes(tempShapes, tempGrid);
}
}
}
// display info
tInfo.text = 'Solving level "' + levelName + '"\nAttempts: ' + attempts + "\nSolutions: " + solutions.length;
// next cycle
nextCycle();
}

private function tryRemainingShapes(tShapes:Array, tGrid:Array):void {
var innerTempShapes:Array = clone(tShapes);
var innerTempGrid:Array = clone(tGrid);
var e:int;
var t:int;
// ...take each remaining shape...
while (innerTempShapes.length > 0) {
var currentShapeValues:Array = clone(shapeValues[innerTempShapes[0]]);
// ...try putting it in each cell...
for (e = 0; e < allCells.length; e++) {
// ...rotate the shape...
for (t = 0; t < 8; t++) {
// ...check if it can be put...
if (canPut(currentShapeValues, allCells[e].x, allCells[e].y, innerTempGrid, t)) {
// ...on success, put this shape and try all remaining shapes...
putHere(currentShapeValues, allCells[e].x, allCells[e].y, innerTempGrid, t, innerTempShapes[0] + 2);
tryRemainingShapes(clone(innerTempShapes).splice(0, 1), innerTempGrid);
// ...if no empty cells remaining, then the puzzle is solved.
if (checkWin(innerTempGrid)) solutions.push(clone(innerTempGrid));
// ...step backwards...
removeHere(currentShapeValues, allCells[e].x, allCells[e].y, innerTempGrid, t);
}
}
}
// ...get rid of the shape and continue...
innerTempShapes.shift();
}
}

private function checkWin(mapGrid:Array):Boolean {
var i:int;
var u:int;
var didWin:Boolean = true;
var width:int = mapGrid[0].length;
var height:int = mapGrid.length;

for (i = 0; i < height; i++) {
for (u = 0; u < width; u++) {
if (mapGrid[i][u] == 1) {didWin = false;}
}
}

return didWin;
}

private function nextCycle():void {
cycleNum++;
if (cycleNum == givenShapes.length) {
removeEventListener(Event.ENTER_FRAME, onFrame);
// display info
tInfo.text = 'SOLVED "' + levelName + '"\nAttempts: ' + attempts + "\nSolutions: " + solutions.length;
trace("complete!");
}
}

private function canPut(cValues:Array, cellX:int, cellY:int, mapGrid:Array, rotation:int):Boolean {
attempts++;
var canPutHere:Boolean = true;
var currentValues:Array = clone(cValues);
updateCurrentValues(currentValues, rotation);
for (var i:int = 0; i < currentValues.length; i++) {
var cX:int = currentValues[i][0] + cellX;
var cY:int = currentValues[i][1] + cellY;
if (cX < 0 || cY < 0 || cX >= mapGrid[0].length || cY >= mapGrid.length || mapGrid[cY][cX]!=1) {
canPutHere = false;
}
}
return canPutHere;
}

private function putHere(currentValues:Array, cellX:int, cellY:int, mapGrid:Array, rotation:int, shape:int):void {
currentValues = clone(currentValues);
updateCurrentValues(currentValues, rotation);
for (var i:int = 0; i < currentValues.length; i++) {
var cX:int = currentValues[i][0] + cellX;
var cY:int = currentValues[i][1] + cellY;
mapGrid[cY][cX] = shape;
}
}

private function removeHere(currentValues:Array, cellX:int, cellY:int, mapGrid:Array, rotation:int):void {
currentValues = clone(currentValues);
updateCurrentValues(currentValues, rotation);
for (var i:int = 0; i < currentValues.length; i++) {
var cX:int = currentValues[i][0] + cellX;
var cY:int = currentValues[i][1] + cellY;
mapGrid[cY][cX] = 1;
}
}

private function updateCurrentValues(currentValues:Array, rot:int):void{
for (var i:int = 0; i < 5; i++) {
// do nothing if rot == 0
if (rot == 1) {
currentValues[i].reverse();
currentValues[i][0] *= -1;
}
if (rot == 2) {
currentValues[i][0] *= -1;
currentValues[i][1] *= -1;
}
if (rot == 3) {
currentValues[i].reverse();
currentValues[i][1] *= -1;
}
if (rot == 4) {
currentValues[i][0] *= -1;
}
if (rot == 5) {
currentValues[i].reverse();
}
if (rot == 6) {
currentValues[i][1] *= -1;
}
if (rot == 7) {
currentValues[i].reverse();
currentValues[i][1] *= -1;
currentValues[i][0] *= -1;
}
}
}

private function clone(source:Object):*{
var myBA:ByteArray = new ByteArray();
myBA.writeObject(source);
myBA.position = 0;
return(myBA.readObject());
}

private function drawPreview(levelPreview:MovieClip, mapGrid:Array):void {
var columns:int = mapGrid[0].length;
var rows:int = mapGrid.length;
var frameWidth:int = levelPreview.width;
var frameHeight:int = levelPreview.height;
var padding:int = 5;
var fitWidth:int = levelPreview.width - (padding * 2);
var fitHeight:int = levelPreview.height - (padding * 2);
var gridStartX:int;
var gridStartY:int;

// calculate width of a cell:
var gridCellWidth:int = Math.round(fitWidth / columns);

var width:int = columns * gridCellWidth;
var height:int = rows * gridCellWidth;

// calculate side margin
gridStartX = (frameWidth - width) / 2;

if (height < fitHeight) {
gridStartY = (fitHeight - height) / 2;
}
if (height >= fitHeight) {
gridCellWidth = Math.round(fitHeight / rows);
height = rows * gridCellWidth;
width = columns * gridCellWidth;
gridStartY = (frameHeight - height) / 2;
gridStartX = (frameWidth - width) / 2;
}

// draw map
levelPreview.shape.x = gridStartX;
levelPreview.shape.y = gridStartY;
levelPreview.shape.graphics.clear();
var i:int;
var u:int;

for (i = 0; i < rows; i++) {
for (u = 0; u < columns; u++) {
if (mapGrid[i][u] == 1) {
drawCell(u, i, 0xffffff, 1, 0x999999, gridCellWidth, levelPreview.shape);
}
}
}
}

private function drawCell(width:int, height:int, fill:uint, thick:Number, line:uint, gridCellWidth:int, gridShape:MovieClip):void {
gridShape.graphics.beginFill(fill);
gridShape.graphics.lineStyle(thick, line);
gridShape.graphics.drawRect(width * gridCellWidth, height * gridCellWidth, gridCellWidth, gridCellWidth);
}
}

}

Note that the code currently is unoptimized and very slow. So only test it on small puzzles (for example - 2x6 grid with 10 shapes available). It also doesn't delete duplicates yet and is generally pretty inefficient. We will work on that next time.

Thanks for reading!

No comments:

Post a Comment