Tuesday, August 28, 2012

Creating a Pentomino game using AS3: Part 41

Today we'll further optimize our solving algorithm by making each cycle execute more often. This will make the program not crash in some situations where it would've crashed before the changes. Also, we're adding a progress bar.

Start by declaring a new variable, cycleNumSub:

private var cycleNumSub;

Set its value to 0 in solve():

cycleNumSub = 0;

The reason for adding this variable is that we will not use a loop in onFrame() to loop through all cells, instead we'll do 1 cycle per frame. This means we have to put each shape in each cell, and do it one frame at a time. In total, we will have n frames, where n = total shapes * total cells.

Go to onFrame() and change delete the for..i loop, add a line that applies cycleNumSub value to i instead:

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 current shape from shapes array (so that it isn't used twice)...
var shapeType:int = tempShapes[cycleNum] + 2;
tempShapes.splice(cycleNum, 1);
// ...try putting it in each available cell...
i = cycleNumSub;
// ...try putting the shape in all 8 possible positions...
if(hasSpace(tempGrid, allCells[i].x, allCells[i].y)){
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, shapeType);
// ...try all remaining shapes...
tryRemainingShapes(tempShapes, tempGrid);
removeHere(currentShapeValues, allCells[i].x, allCells[i].y, tempGrid, u);
}
}
}
// display info
tInfo.text = 'Solving level "' + levelName + '"\nAttempts: ' + attempts + "\nSolutions: " + solutions.length;
// next cycle
nextCycle();
}

Now in nextCycle(), instead of increase cycleNum, we increase cycleNumSub. Then we check if the value has reached allCells.length, and if so - reset cycleNumSub to 0 and increase cycleNum:

cycleNumSub++;
if (cycleNumSub == allCells.length) {
cycleNumSub = 0;
cycleNum++;
}

Now we'll add a progress bar. Open the project in Flash, go to the solutions screen MovieClip and add a rectangular MovieClip. Give it an id of progressBar and make sure its registration point is its left edge. You can draw borders outside of the bar MC that indicate the full size of the bar.

We're going to be scaling the bar movie clip using its scaleX property.

Go to solve() and set its scaleX value to 0:

progressBar.scaleX = 0;

Making the whole function look like this:

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;
cycleNumSub = 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]]
];
btn_prev.addEventListener(MouseEvent.CLICK, goPrev);
btn_next.addEventListener(MouseEvent.CLICK, goNext);
btn_back.addEventListener(MouseEvent.CLICK, goBack);
btn_back.alpha = 0.5;
btn_back.mouseEnabled = false;

// display warning message
warningScreen = new solution_screen();
addChild(warningScreen);
warningScreen.btn_back.addEventListener(MouseEvent.CLICK, goBack);
warningScreen.btn_continue.addEventListener(MouseEvent.CLICK, goContinue);

progressBar.scaleX = 0;
}

Now go to nextCycle() and set progressBar's scaleX to number of total cycles executed divided by total number of cycles. This can be calculated like this:

progressBar.scaleX = (cycleNum * allCells.length + cycleNumSub) / (allCells.length * givenShapes.length);

If the final cycle has been executed, set its scaleX to 1. Full nextCycle() function:

private function nextCycle():void {
cycleNumSub++;
if (cycleNumSub == allCells.length) {
cycleNumSub = 0;
cycleNum++;
}
progressBar.scaleX = (cycleNum * allCells.length + cycleNumSub) / (allCells.length * givenShapes.length);

updateCurrentInfo();
if (cycleNum == givenShapes.length) {
removeEventListener(Event.ENTER_FRAME, onFrame);
// display info
tInfo.text = 'Finished solving "' + levelName + '"\nAttempts: ' + attempts + "\nSolutions: " + solutions.length;
btn_back.alpha = 1;
btn_back.mouseEnabled = true;
progressBar.scaleX = 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;
private var currentSol:int = 0;
private var warningScreen:MovieClip;
private var cycleNumSub;

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;
cycleNumSub = 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]]
];
btn_prev.addEventListener(MouseEvent.CLICK, goPrev);
btn_next.addEventListener(MouseEvent.CLICK, goNext);
btn_back.addEventListener(MouseEvent.CLICK, goBack);
btn_back.alpha = 0.5;
btn_back.mouseEnabled = false;

// display warning message
warningScreen = new solution_screen();
addChild(warningScreen);
warningScreen.btn_back.addEventListener(MouseEvent.CLICK, goBack);
warningScreen.btn_continue.addEventListener(MouseEvent.CLICK, goContinue);

progressBar.scaleX = 0;
}

private function goContinue(evt:MouseEvent):void {
warningScreen.parent.removeChild(warningScreen);
addEventListener(Event.ENTER_FRAME, onFrame);
}

private function goBack(evt:MouseEvent):void {
(root as MovieClip).gotoAndStop(1);
}

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 current shape from shapes array (so that it isn't used twice)...
var shapeType:int = tempShapes[cycleNum] + 2;
tempShapes.splice(cycleNum, 1);
// ...try putting it in each available cell...
i = cycleNumSub;
// ...try putting the shape in all 8 possible positions...
if(hasSpace(tempGrid, allCells[i].x, allCells[i].y)){
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, shapeType);
// ...try all remaining shapes...
tryRemainingShapes(tempShapes, tempGrid);
removeHere(currentShapeValues, allCells[i].x, allCells[i].y, tempGrid, u);
}
}
}
// 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;
var passedShapes:Array;
// ...take each remaining shape...
outerLoop: 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...
if (innerTempGrid[allCells[e].y][allCells[e].x] == 1) {
if (hasSpace(innerTempGrid, allCells[e].x, allCells[e].y)) {
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);
passedShapes = innerTempShapes.concat();
passedShapes.splice(0, 1);
tryRemainingShapes(passedShapes, innerTempGrid);
// ...if no empty cells remaining, then the puzzle is solved.
if (checkWin(innerTempGrid)) doWin(clone(innerTempGrid));
// ...step backwards...
removeHere(currentShapeValues, allCells[e].x, allCells[e].y, innerTempGrid, t);
}
}
}else {
break outerLoop;
}
}
}
// ...get rid of the shape and continue...
innerTempShapes.shift();
}
}

private function hasSpace(mapGrid:Array, cX:int, cY:int):Boolean {
var neighbours:int = 1; // count self as neighbour
var nGrid:Array = clone(mapGrid);
nGrid[cY][cX] = "n"; // set to "n" if together
neighbours += getNeighbours(cX, cY, nGrid);
if (neighbours >= 5) return true;
return false;
}

private function getNeighbours(cX:int, cY:int, grid:Array):int {
var n:int = 0;
if (cY != 0 && grid[cY - 1][cX] == 1) {
n++;
grid[cY - 1][cX] = "n";
n += getNeighbours(cX, cY - 1, grid);
}
if (cY != grid.length - 1 && grid[cY + 1][cX] == 1) {
n++;
grid[cY + 1][cX] = "n";
n += getNeighbours(cX, cY + 1, grid);
}
if (cX != 0 && grid[cY][cX - 1] == 1) {
n++;
grid[cY][cX - 1] = "n";
n += getNeighbours(cX - 1, cY, grid);
}
if (cX != grid[0].length - 1 && grid[cY][cX + 1] == 1) {
n++;
grid[cY][cX + 1] = "n";
n += getNeighbours(cX + 1, cY, grid);
}
return n;
}

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 doWin(grid:Array):void {
var exists:Boolean = false;
for (var i:int = 0; i < solutions.length; i++) {
if (compare(solutions[i], grid)) {
exists = true;
break;
}
}
if (!exists) solutions.push(grid);
}

private function compare(arr1:Array, arr2:Array):Boolean {
for (var i:int = 0; i < arr1.length; i++) {
for (var u:int = 0; u < arr1[i].length; u++){
if (arr1[i][u] != arr2[i][u]) {
return false;
break;
}
}
}
return true;
}

private function goPrev(evt:MouseEvent):void {
currentSol--;
updateCurrentInfo();
}

private function goNext(evt:MouseEvent):void {
currentSol++;
updateCurrentInfo();
}

private function updateCurrentInfo():void {
var sol:int = (solutions.length > 0)?(currentSol + 1):(0);
tSol.text = sol + "/" + solutions.length;
if (sol <= 1) {
btn_prev.alpha = 0.5;
btn_prev.mouseEnabled = false;
}else {
btn_prev.alpha = 1;
btn_prev.mouseEnabled = true;
}
if (sol == solutions.length) {
btn_next.alpha = 0.5;
btn_next.mouseEnabled = false;
}else {
btn_next.alpha = 1;
btn_next.mouseEnabled = true;
}
if (solutions.length > 0) drawPreview(levelPreview, solutions[currentSol]);
}

private function nextCycle():void {
cycleNumSub++;
if (cycleNumSub == allCells.length) {
cycleNumSub = 0;
cycleNum++;
}
progressBar.scaleX = (cycleNum * allCells.length + cycleNumSub) / (allCells.length * givenShapes.length);

updateCurrentInfo();
if (cycleNum == givenShapes.length) {
removeEventListener(Event.ENTER_FRAME, onFrame);
// display info
tInfo.text = 'Finished solving "' + levelName + '"\nAttempts: ' + attempts + "\nSolutions: " + solutions.length;
btn_back.alpha = 1;
btn_back.mouseEnabled = true;
progressBar.scaleX = 1;
}
}

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);
if (mapGrid[i][u] == 2) drawCell(u, i, 0xff66cc, 1, 0x000000, gridCellWidth, levelPreview.shape);
if (mapGrid[i][u] == 3) drawCell(u, i, 0x00FF66, 1, 0x000000, gridCellWidth, levelPreview.shape);
if (mapGrid[i][u] == 4) drawCell(u, i, 0x99ff00, 1, 0x000000, gridCellWidth, levelPreview.shape);
if (mapGrid[i][u] == 5) drawCell(u, i, 0x00ccff, 1, 0x000000, gridCellWidth, levelPreview.shape);
if (mapGrid[i][u] == 6) drawCell(u, i, 0xffcc66, 1, 0x000000, gridCellWidth, levelPreview.shape);
if (mapGrid[i][u] == 7) drawCell(u, i, 0x66cc33, 1, 0x000000, gridCellWidth, levelPreview.shape);
if (mapGrid[i][u] == 8) drawCell(u, i, 0x9900ff, 1, 0x000000, gridCellWidth, levelPreview.shape);
if (mapGrid[i][u] == 9) drawCell(u, i, 0xff5858, 1, 0x000000, gridCellWidth, levelPreview.shape);
if (mapGrid[i][u] == 10) drawCell(u, i, 0xff6600, 1, 0x000000, gridCellWidth, levelPreview.shape);
if (mapGrid[i][u] == 11) drawCell(u, i, 0x00ffff, 1, 0x000000, gridCellWidth, levelPreview.shape);
if (mapGrid[i][u] == 12) drawCell(u, i, 0xff6b20, 1, 0x000000, gridCellWidth, levelPreview.shape);
if (mapGrid[i][u] == 13) drawCell(u, i, 0xffff66, 1, 0x000000, 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);
}
}

}

Thanks for reading!

Results:


No comments:

Post a Comment