Skip to content

Instantly share code, notes, and snippets.

@JakeSteam
Created January 5, 2017 16:00
Show Gist options
  • Save JakeSteam/b4821859e08202a0040d67f0b6158bec to your computer and use it in GitHub Desktop.
Save JakeSteam/b4821859e08202a0040d67f0b6158bec to your computer and use it in GitHub Desktop.
Asynchronous Puzzle Generator for Android, published on Game Dev Algorithms blog
package uk.co.jakelee.cityflow.components;
import android.app.Activity;
import android.app.Dialog;
import android.content.DialogInterface;
import android.content.Intent;
import android.os.AsyncTask;
import android.widget.TextView;
import java.util.ArrayList;
import java.util.List;
import java.util.Locale;
import uk.co.jakelee.cityflow.R;
import uk.co.jakelee.cityflow.helper.Constants;
import uk.co.jakelee.cityflow.helper.RandomHelper;
import uk.co.jakelee.cityflow.main.EditorActivity;
import uk.co.jakelee.cityflow.main.PuzzleActivity;
import uk.co.jakelee.cityflow.model.Iap;
import uk.co.jakelee.cityflow.model.Puzzle;
import uk.co.jakelee.cityflow.model.PuzzleCustom;
import uk.co.jakelee.cityflow.model.Tile;
import uk.co.jakelee.cityflow.model.TileType;
import static uk.co.jakelee.cityflow.helper.PuzzleHelper.createBasicPuzzleCustomObject;
import static uk.co.jakelee.cityflow.helper.PuzzleHelper.createBasicPuzzleObject;
import static uk.co.jakelee.cityflow.helper.PuzzleHelper.getDefaultTileId;
import static uk.co.jakelee.cityflow.helper.PuzzleHelper.getNextCustomPuzzleId;
public class PuzzleGenerator extends AsyncTask<String, Integer, Integer> {
private Activity activity;
private TextView progressText;
private TextView progressPercentage;
private Dialog dialog;
private int xValue;
private int yValue;
private int environmentId;
private boolean blankPuzzle;
private boolean shuffleAndPlay;
private int totalTiles;
private boolean cancelReceived = false;
private int failedTiles = 0;
private boolean hasAllTiles = false;
public PuzzleGenerator(Activity activity, Dialog dialog, int xValue, int yValue, int environmentId, boolean blankPuzzle, boolean shuffleAndPlay) {
this.activity = activity;
this.dialog = dialog;
this.xValue = xValue;
this.yValue = yValue;
this.environmentId = environmentId;
this.blankPuzzle = blankPuzzle;
this.shuffleAndPlay = shuffleAndPlay;
this.hasAllTiles = Iap.hasAllTiles();
this.progressText = (TextView) dialog.findViewById(R.id.progressText);
this.progressPercentage = (TextView) dialog.findViewById(R.id.progressPercentage);
}
@Override
protected void onPreExecute() {
dialog.setOnCancelListener(new DialogInterface.OnCancelListener() {
@Override
public void onCancel(DialogInterface dialogInterface) {
cancel();
}
});
}
public void cancel() {
cancelReceived = true;
}
@Override
protected Integer doInBackground(String... params) {
totalTiles = xValue * yValue;
if (blankPuzzle) {
return createEmptyPuzzle(xValue, yValue, environmentId);
} else {
return createFilledPuzzle(xValue, yValue, environmentId);
}
}
private int createEmptyPuzzle(int maxX, int maxY, final int environmentId) {
int newPuzzleId = getNextCustomPuzzleId();
int defaultTileId = getDefaultTileId(environmentId);
Puzzle newPuzzle = createBasicPuzzleObject(newPuzzleId);
PuzzleCustom puzzleCustom = createBasicPuzzleCustomObject(newPuzzleId, maxX, maxY);
newPuzzle.save();
puzzleCustom.save();
List<Tile> tiles = new ArrayList<>();
for (int x = 0; x < maxX; x++) {
for (int y = 0; y < maxY; y++) {
if (cancelReceived) {
newPuzzle.safelyDelete();
return 0;
}
tiles.add(new Tile(newPuzzleId, defaultTileId, x, y, Constants.ROTATION_NORTH));
publishProgress(tiles.size());
}
}
Tile.saveInTx(tiles);
return newPuzzleId;
}
private int createFilledPuzzle(int maxX, int maxY, int environmentId) {
int newPuzzleId = getNextCustomPuzzleId();
Puzzle newPuzzle = createBasicPuzzleObject(newPuzzleId);
PuzzleCustom puzzleCustom = createBasicPuzzleCustomObject(newPuzzleId, maxX, maxY);
newPuzzle.save();
puzzleCustom.save();
List<Tile> tiles = new ArrayList<>();
int prevY = 0;
int failedAttempts = 0;
int totalAttempts = 0;
int maxAttemptsPerTile = 3;
int maxTotalAttempts = 10;
for (int x = 0; x < maxX; x++) {
for (int y = 0; y < maxY; y++) {
if (cancelReceived) {
newPuzzle.safelyDelete();
return 0;
}
List<Tile> potentialTiles = getPossibleTiles(newPuzzleId, tiles, x, y, maxX - 1, maxY - 1, environmentId);
if (potentialTiles.size() > 0) {
Tile selectedTile = potentialTiles.get(RandomHelper.getNumber(0, potentialTiles.size() - 1));
tiles.add(selectedTile);
prevY = y;
failedAttempts = 0;
} else {
failedAttempts++;
totalAttempts++;
if (failedAttempts > maxAttemptsPerTile || totalAttempts > maxTotalAttempts) {
tiles.add(new Tile(newPuzzleId, 0, x, y, Constants.ROTATION_NORTH));
prevY = y;
failedAttempts = 0;
totalAttempts = 0;
failedTiles++;
} else {
tiles.remove(tiles.size() - 1);
if (y == 0) {
x--;
y = maxY - 1;
} else {
y = prevY - 1;
}
}
}
publishProgress(tiles.size());
}
}
if (shuffleAndPlay) {
Puzzle.shuffle(tiles);
Tile.executeQuery("UPDATE tile SET default_rotation = rotation WHERE puzzle_id = " + newPuzzleId);
} else {
Tile.saveInTx(tiles);
}
return newPuzzleId;
}
private List<Tile> getPossibleTiles(int puzzleId, List<Tile> existingTiles, int tileX, int tileY, int maxX, int maxY, int environmentId) {
Tile southTile = tileY == 0 ? new Tile() : existingTiles.get(existingTiles.size() - 1); // Get the south tile, or an empty one if we're starting a new column
Tile westTile = tileX == 0 ? new Tile() : existingTiles.get(existingTiles.size() - (maxY + 1)); // Get the west tile (#Y tiles previous), or empty if new row
TileType southTileType = TileType.get(southTile.getTileTypeId());
TileType westTileType = TileType.get(westTile.getTileTypeId());
int nFlow = tileY == maxY ? 0 : Constants.FLOW_ANY;
int eFlow = tileX == maxX ? 0 : Constants.FLOW_ANY;
int sFlow = southTileType.getFlow(Constants.SIDE_NORTH, southTile.getRotation());
int wFlow = westTileType.getFlow(Constants.SIDE_EAST, westTile.getRotation());
// If there's no flow, then do any height we want
int nHeight = Constants.FLOW_ANY;
int eHeight = Constants.FLOW_ANY;
int sHeight = sFlow > 0 && tileY > 0 ? southTileType.getHeight(Constants.SIDE_NORTH, southTile.getRotation()) : Constants.FLOW_ANY;
int wHeight = wFlow > 0 && tileX > 0 ? westTileType.getHeight(Constants.SIDE_EAST, westTile.getRotation()) : Constants.FLOW_ANY;
// Make list
List<Tile> tiles = getPossibleTilesByRotation(puzzleId, tileX, tileY, environmentId, Constants.ROTATION_NORTH, nFlow, eFlow, sFlow, wFlow, nHeight, eHeight, sHeight, wHeight);
tiles.addAll(getPossibleTilesByRotation(puzzleId, tileX, tileY, environmentId, Constants.ROTATION_WEST, wFlow, nFlow, eFlow, sFlow, wHeight, nHeight, eHeight, sHeight));
tiles.addAll(getPossibleTilesByRotation(puzzleId, tileX, tileY, environmentId, Constants.ROTATION_SOUTH, sFlow, wFlow, nFlow, eFlow, sHeight, wHeight, nHeight, eHeight));
tiles.addAll(getPossibleTilesByRotation(puzzleId, tileX, tileY, environmentId, Constants.ROTATION_EAST, eFlow, sFlow, wFlow, nFlow, eHeight, sHeight, wHeight, nHeight));
return tiles;
}
private List<Tile> getPossibleTilesByRotation(int puzzleId, int x, int y, int environmentId, int rotation, int nFlow, int eFlow, int sFlow, int wFlow, int nHeight, int eHeight, int sHeight, int wHeight) {
String flowSql = String.format(Locale.ENGLISH, "%1$s AND %2$s AND %3$s AND %4$s",
match("flow_north", nFlow),
match("flow_east", eFlow),
match("flow_south", sFlow),
match("flow_west", wFlow));
String forceFlowSql = (x == 0 && y == 0 ? " AND (flow_north > 0 OR flow_east > 0 OR flow_south > 0 OR flow_west > 0)" : "");
String heightSql = String.format(Locale.ENGLISH, "%1$s AND %2$s AND %3$s AND %4$s",
match("height_north", nHeight),
match("height_east", eHeight),
match("height_south", sHeight),
match("height_west", wHeight));
String sql = String.format(Locale.ENGLISH, "environment_id %1$s %2$d AND " + flowSql + forceFlowSql + " AND " + heightSql + " AND status %3$s %4$d",
environmentId > 0 ? "=" : ">=", environmentId,
hasAllTiles ? ">=" : "=",
Constants.TILE_STATUS_UNLOCKED);
List<TileType> tileTypes = TileType.find(TileType.class, sql);
List<Tile> tiles = new ArrayList<>();
for (TileType tile : tileTypes) {
tiles.add(new Tile(puzzleId, tile.getTypeId(), x, y, rotation));
}
return tiles;
}
private static String match(String name, int value) {
return String.format(Locale.ENGLISH, "(%1$s %2$s %3$s)",
name,
(value >= 0 ? "=" : ">="),
value);
}
@Override
protected void onPostExecute(Integer result) {
if (dialog.isShowing()) {
dialog.dismiss();
if (!blankPuzzle && shuffleAndPlay) {
activity.startActivity(new Intent(activity, PuzzleActivity.class)
.putExtra(Constants.INTENT_PUZZLE, result)
.putExtra(Constants.INTENT_IS_CUSTOM, true)
.putExtra(Constants.INTENT_FAILED_TILES, failedTiles)
.addFlags(Intent.FLAG_ACTIVITY_REORDER_TO_FRONT));
} else {
activity.startActivity(new Intent(activity, EditorActivity.class)
.putExtra(Constants.INTENT_PUZZLE, result)
.putExtra(Constants.INTENT_ENVIRONMENT, environmentId)
.putExtra(Constants.INTENT_FAILED_TILES, failedTiles)
.addFlags(Intent.FLAG_ACTIVITY_REORDER_TO_FRONT));
}
}
}
@Override
protected void onProgressUpdate(Integer... values) {
int percent = (int) (((double) values[0]) / ((double) totalTiles) * 100);
progressPercentage.setText(String.format(Locale.ENGLISH, "%1$d%%", percent));
progressText.setText(String.format(Locale.ENGLISH, "(%1$d/%2$d)", values[0], totalTiles));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment