Friday, January 30, 2015
Creating a Pentomino game using AS3 Part 39
Go to tryRemainingShapes() function and before the if..statement that calls hasSpace() function add another if..statement that checks if the cell with provided coordinates has value of 1. This is basically what we have in hasSpace() right now, but well be completely rewriting that function and checking for different things in it.
We need to label the while... loop by writing "outerLoop: " before the loop. This will allow us to break this loop from inside another loop. We break outerLoop if hasSpace() returns false.
Another change here is that we declare a new passedShapes Array that we can use to later remove the first element from and pass it to the next tryRemaininShapes() cycle. Simply passing a clone of innerTempShapes with .splice() does not work - it returns the element instead of the array.
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();
}
}
Go to onFrame() and add the hasSpace() check there as well:
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 isnt used twice)...
var shapeType:int = tempShapes[cycleNum] + 2;
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...
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 + "
Attempts: + attempts + "
Solutions: " + solutions.length;
// next cycle
nextCycle();
}
The hasSpace() function checks if the area on the grid that the cell is located in has more than 5 cells in it. Well call these cells neighbours. However, the cell itself counts as a neighbour too.
Declare a variable called "neighbours" and set its value to 1. Clone the grid data and set the current cells value in the grid to "n". All cells that are connected to this cell will have value "n".
Then add a line that adds returned value of getNeighbours() function to neighbours. Check if the number is greater than or equals 5, return true. Otherwise, return false.
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;
}
The getNeighbours() function is a recursive function that loops through neighbours and checks their neighbours as well, and goes on before it meets a wall.
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;
}
Our solving algorithm is now more efficient (uses considerably less attempts => computes faster) and more accurate in finding solutions. Still, it is not fast enough to solve medium or bigger sized puzzles.
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;
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);
btn_prev.addEventListener(MouseEvent.CLICK, goPrev);
btn_next.addEventListener(MouseEvent.CLICK, goNext);
}
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 isnt used twice)...
var shapeType:int = tempShapes[cycleNum] + 2;
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...
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 + "
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;
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 {
cycleNum++;
updateCurrentInfo();
if (cycleNum == givenShapes.length) {
removeEventListener(Event.ENTER_FRAME, onFrame);
// display info
tInfo.text = Finished solving " + 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);
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!
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.