Wednesday, August 22, 2012

Creating a Pentomino game using AS3: Part 35

Today we continue working on our solving algorithm.

We left off with an empty canPut() function and an if..statement that is supposed to try place all the other shapes after the first one.

Right now we try to put the first shape in each cell and if we succeed, continue on to the code inside the if..statement (which is empty right now). The method that we use to check if a shape can be put here is called canPut(), and is also empty right now.

The issue right now with placing the shapes is that we are placing them without rotating. There are 4 possible rotation positions for each shape, and 2 ways for the shapes to be flipped, so that makes 8 possible variations of how a shape can be positioned. That means we need to try putting the first shape in each cell in each of the 8 possible positions.

Create another loop inside of the allCells.length loop in onFrame() that cycles 8 times, inside of it have the canPut() if...statement.

Count attempts in the second loop, and also push a placeholder item in solutions array if the canPut() conditional is true.

Instead of passing just 3 values as parameters to canPut(), we also pass tempGrid and the second cycle's cycle number:

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++) {
attempts++;
// ...if successful, continue placing other cells...
if (canPut(currentShapeValues, allCells[i].x, allCells[i].y, tempGrid, u)) {
// ---code that places other shapes---
solutions.push("test");
}
}
}
// display info
tInfo.text = 'Solving level "' + levelName + '"\nAttempts: ' + attempts + "\nSolutions: " + solutions.length;
// next cycle
nextCycle();
}

In the canPut() function we declare a canPutHere boolean, set it to true by default. Then we set currentValues value to a clone() of its own. Call a function updateCurrentValues(), pass currentValues and the rotation number (the one received from the second loop in onFrame()). This function will modify currentValues array to match the needed rotation.

Then create a loop that cycles through currentValues elements and checks if all the cells are placeable in their spots. If a cell isn't, set canPutHere to false.

In the end, return canPutHere.

private function canPut(currentValues:Array, cellX:int, cellY:int, mapGrid:Array, rotation:int):Boolean {
var canPutHere:Boolean = true;
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;
if (cX < 0 || cY < 0 || cX >= mapGrid[0].length || cY >= mapGrid.length || mapGrid[cY][cX]!=1) {
canPutHere = false;
}
}
return canPutHere;
}

The updateCurrentValues() modifies the received values based on the rotation number.

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

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++) {
attempts++;
// ...if successful, continue placing other cells...
if (canPut(currentShapeValues, allCells[i].x, allCells[i].y, tempGrid, u)) {
// ---code that places other shapes---
solutions.push("test");
}
}
}
// display info
tInfo.text = 'Solving level "' + levelName + '"\nAttempts: ' + attempts + "\nSolutions: " + solutions.length;
// next cycle
nextCycle();
}


private function nextCycle():void {
cycleNum++;
if (cycleNum == givenShapes.length) {
removeEventListener(Event.ENTER_FRAME, onFrame);
trace("complete");
}
}

private function canPut(currentValues:Array, cellX:int, cellY:int, mapGrid:Array, rotation:int):Boolean {
var canPutHere:Boolean = true;
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;
if (cX < 0 || cY < 0 || cX >= mapGrid[0].length || cY >= mapGrid.length || mapGrid[cY][cX]!=1) {
canPutHere = false;
}
}
return canPutHere;
}

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

}

Thanks for reading!

No comments:

Post a Comment