Tuesday, August 21, 2012

Creating a Pentomino game using AS3: Part 34

Today we will start writing auto solving code.

I have to admit that writing this kind of algorithm is new to me, and I don't have any information on how this is usually done, so I'm going to have to invent my own way of looking for solutions. I'll be adding code and most likely changing something along the way. My methods might not be most efficient ones, but right now the goal is just to make the solver work, after that comes optimisation.

Go to level_solver.as. Declare 10 new variables:

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;

Now in solve() function we'll be adding some code to set values to some of the variables above.

The first variable we'll handle is givenShapes. This is an array of all the available shapes. The difference between this array and the one in levelItem Object is that in givenShapes, each shape is contained separately. So, if we have 2 L shapes available, they will be located in givenShapes as 2 different elements.

We add these values using a loop:

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

Next is the allCells array, this one contains each available cell as a separate element. Each element is a Point with coordinates of the cell.

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

The givenGrid value is simply the map data that we receive:

givenGrid = levelItem.grid;

The two temporary variables - tempGrid and tempShapes - will be updated with each cycle, set them to empty arrays for now:

tempGrid = [];
tempShapes = [];

The solutions array will become an array of map grids that represent solutions:

solutions = [];

LevelName is the name of the level:

levelName = levelItem.name;

The attempts value will be used for debugging mainly. It will count how many attempts to check if a shape can be placed in a location are made.

The cycleNum value is the current cycle number, I will explain this in details later. Set both values to 0:

attempts = 0;
cycleNum = 0;

The shapeValues array is the same as the one in pentomino_game:

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

Now we add an ENTER_FRAME listener with a handler onFrame:

addEventListener(Event.ENTER_FRAME, onFrame);

Full function:

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

Now that everything has been initialized, we can start solving the puzzle. To prevent long term program freezes, we're going to use this ENTER_FRAME handler to call cycles over multiple frames, rather than execute all of the code in 1 frame.

This is basically a hand made for..loop that executes each cycle once a frame.

The function onFrame() does 4 things - set temporary values, solve the puzzle, display information to the user, move on to the next cycle.

We're going to need to use a clone() function when setting tempGrid and tempShapes values, so add this function now:

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

Now we'll add some code to onFrame(). Firstly, set values to tempGrid and tempShapes:

// set temporary values
tempGrid = clone(givenGrid);
tempShapes = clone(givenShapes);

Declare the following variables:

var i:int;
var u:int;
var currentShapeValues:Array;

That's the first part of onFrame() done. Moving on to the solutions part. Today we'll only add a little bit of code here, it will take more than one tutorial to finish the solution algorithm.

Firstly apply the value to currentShapeValues by cloning an item in shapeValues that represents the first shape in the cycle. Each cycle is started with a different first shape.

// Take the first shape in this cycle...
currentShapeValues = clone(shapeValues[tempShapes[cycleNum]]);

Remove this shape from tempShapes because we don't want to use it twice:

// ...remove it from shapes array (so that it isn't used twice)...
tempShapes.splice(cycleNum, 1);

Now we will loop through all the cells and try putting this first shape in each cell. Count each attempt using the attempts variable. Use a canPut() function to see if the shape can be put here, pass 3 values as the parameters - currentShapeValues, x and y coordinates. In case of success, do nothing - we'll work on that part next time.

// ...try putting it in each available cell...
for (i = 0; i < allCells.length; i++) {
attempts++;
// ...if successful, continue placing other cells...
if (canPut(currentShapeValues, allCells[i].x, allCells[i].y)) {
// ---code that places other cells---
}
}

Third part of the function is to display info:

// display info
tInfo.text = 'Solving level "' + levelName + '"\nAttempts: ' + attempts + "\nSolutions: " + solutions.length;

And move onto next cycle by calling nextCycle():

// next cycle
nextCycle();

Full function so far:

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

The nextCycle() function adds 1 to cycleNum, checks if loop has reached its last cycle, and if so - stops the process by removing ENTER_FRAME listener:

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

The canPut() function is empty for now:

private function canPut(currentValues:Array, cellX:int, cellY:int):void {
// ---code that checks if the shape can be put here---
}

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++) {
attempts++;
// ...if successful, continue placing other cells...
if (canPut(currentShapeValues, allCells[i].x, allCells[i].y)) {
// ---code that places other cells---
}
}
// 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):void {
// ---code that checks if the shape can be put here---
}

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