TIPS COM: Creating a Pentomino game using AS3 Part 37

Friday, January 30, 2015

Creating a Pentomino game using AS3 Part 37

Today well work on improving our solving algorithm.

The first two changes will be made in the onFrame() function. We need to add a line that calls removeHere() after calling tryRemainingShapes(), so that a step backwards is taken in order to properly look for solutions, and we need to move the line that deletes the first element in tempShapes array under the loop. This way the shape ids will have proper values and the calculations will be more accurate.

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]]);
// ...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);
removeHere(currentShapeValues, allCells[i].x, allCells[i].y, tempGrid, u);
}
}
}
// ...remove it from shapes array (so that it isnt used twice)...
tempShapes.splice(cycleNum, 1);
// display info
tInfo.text = Solving level " + levelName + "
Attempts:  + attempts + "
Solutions: " + solutions.length;
// next cycle
nextCycle();
}

In tryRemainingShapes() add an if..statement inside the for..loop that cycles through allCells. Set the conditional of statement to a hasSpace() function which returns a boolean value. Pass innerTempGrid, allCells[e].x and allCells[e].y as parameters.

Then update the line that pushes an element to the solutions array, call a doWin() function instead of pushing an item. Pass a clone of innerTempGrid as parameter.

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...
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);
tryRemainingShapes(clone(innerTempShapes).splice(0, 1), 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);
}
}
}
}
// ...get rid of the shape and continue...
innerTempShapes.shift();
}
}

The hasSpace() function right now checks if the provided cells value is 1. If it isnt, return false.

private function hasSpace(mapGrid:Array, cX:int, cY:int):Boolean {
if (mapGrid[cY][cX] != 1) return false;
return true;
}

I turned that into a function because I am planning on expanding the function and adding more checks that improve the algorithm speed.

The doWin() function has an "exists" variable which is set to false by default. Then we compare all existing solutions to the one that we have and check if a solution like that already exists. If it doesnt - add it to the array.

Use a compare() function to compare two grids:

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);
}

The compare() functions loops through values of the first array and compares them to the values of the other array. False is returned if a value doesnt match:

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;
}

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]]);
// ...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);
removeHere(currentShapeValues, allCells[i].x, allCells[i].y, tempGrid, u);
}
}
}
// ...remove it from shapes array (so that it isnt used twice)...
tempShapes.splice(cycleNum, 1);
// display info
tInfo.text = Solving level " + levelName + "
Attempts:  + attempts + "
Solutions: " + 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...
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);
tryRemainingShapes(clone(innerTempShapes).splice(0, 1), 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);
}
}
}
}
// ...get rid of the shape and continue...
innerTempShapes.shift();
}
}

private function hasSpace(mapGrid:Array, cX:int, cY:int):Boolean {
if (mapGrid[cY][cX] != 1) return false;
return true;
}

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 nextCycle():void {
cycleNum++;
if (cycleNum == givenShapes.length) {
removeEventListener(Event.ENTER_FRAME, onFrame);
// display info
tInfo.text = SOLVED " + levelName + "
Attempts:  + attempts + "
Solutions: " + solutions.length;
}
}

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);
}
}

}

The code is now more accurate and slightly faster, but it still is slow and should only be tested on small puzzles.

Thanks for reading!

TIPS COM

Friday, January 30, 2015

Creating a Pentomino game using AS3 Part 37

No comments:

Post a Comment