java/maze-generator
1
0
Fork 0
Code Issues Pull requests Releases Packages Wiki Activity Actions

Compare commits

base: java:feature/wilson-algorithm
Branches Tags
java:master
java:feature/wilson-algorithm
java:v0.2.1
java:v0.2.0
java:v0.1.0
java:v0.0.8
java:v0.0.7
java:v0.0.6
java:v0.0.5
java:v0.0.4
java:v0.0.3
java:v0.0.2
java:v0.0.1
..
compare: java:master
Branches Tags
java:feature/wilson-algorithm
java:master
java:v0.2.1
java:v0.2.0
java:v0.1.0
java:v0.0.8
java:v0.0.7
java:v0.0.6
java:v0.0.5
java:v0.0.4
java:v0.0.3
java:v0.0.2
java:v0.0.1

No commits in common. "feature/wilson-algorithm" and "master" have entirely different histories.
feature/wi ... master

26 changed files with 310 additions and 1066 deletions
Show stats Expand all files Collapse all files

20
src/main/java/ch/fritteli/maze/generator/algorithm/AbstractMazeGeneratorAlgorithm.java
View file

@ -1,20 +0,0 @@
package ch.fritteli.maze.generator.algorithm;
import ch.fritteli.maze.generator.model.Maze;
import org.jetbrains.annotations.NotNull;
import java.util.Random;
public abstract class AbstractMazeGeneratorAlgorithm implements MazeGeneratorAlgorithm {
@NotNull
protected final Maze maze;
@NotNull
protected final Random random;
protected AbstractMazeGeneratorAlgorithm(@NotNull final Maze maze, @NotNull final String algorithmName) {
this.maze = maze;
this.random = new Random(maze.getRandomSeed());
this.maze.setAlgorithm(algorithmName);
}
}

5
src/main/java/ch/fritteli/maze/generator/algorithm/MazeGeneratorAlgorithm.java
View file

@ -1,5 +0,0 @@
package ch.fritteli.maze.generator.algorithm;
public interface MazeGeneratorAlgorithm {
void run();
}

11
src/main/java/ch/fritteli/maze/generator/algorithm/RandomDepthFirst.java
View file

@ -10,13 +10,20 @@ import org.jetbrains.annotations.Nullable;
import java.util.Deque; import java.util.Deque;
import java.util.LinkedList; import java.util.LinkedList;
import java.util.Random;
public class RandomDepthFirst extends AbstractMazeGeneratorAlgorithm { public class RandomDepthFirst {
@NotNull
private final Maze maze;
@NotNull
private final Random random;
@NotNull @NotNull
private final Deque<Position> positions = new LinkedList<>(); private final Deque<Position> positions = new LinkedList<>();
public RandomDepthFirst(@NotNull final Maze maze) { public RandomDepthFirst(@NotNull final Maze maze) {
super(maze, "Random Depth First"); this.maze = maze;
this.random = new Random(maze.getRandomSeed());
} }
public void run() { public void run() {

312
src/main/java/ch/fritteli/maze/generator/algorithm/Wilson.java
View file

@ -1,312 +0,0 @@
package ch.fritteli.maze.generator.algorithm;
import ch.fritteli.maze.generator.model.Direction;
import ch.fritteli.maze.generator.model.Maze;
import ch.fritteli.maze.generator.model.Position;
import ch.fritteli.maze.generator.model.Tile;
import io.vavr.Tuple2;
import io.vavr.collection.Iterator;
import io.vavr.collection.Seq;
import io.vavr.collection.Stream;
import io.vavr.collection.Vector;
import io.vavr.control.Option;
import org.jetbrains.annotations.NotNull;
import org.jetbrains.annotations.Nullable;
import java.util.ArrayList;
import java.util.EnumSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
/**
* An implementation of <a href="https://en.wikipedia.org/wiki/Maze_generation_algorithm#Wilson's_algorithm">Wilson's Algorithm</a>.
*/
public class Wilson extends AbstractMazeGeneratorAlgorithm {
public Wilson(@NotNull final Maze maze) {
super(maze, "Wilson");
}
@Override
public void run() {
final MyMaze myMaze = new MyMaze(this.maze.getWidth(), this.maze.getHeight());
// 1. Initialization: pick random location, add to maze
final Position position = myMaze.getRandomAvailablePosition(this.random).get();
myMaze.setPartOfMaze(position);
// 2. while locations-not-in-maze exist, repeat:
final List<MyMaze.Path> pths = new ArrayList<>();
Position startPosition;
while ((startPosition = myMaze.getRandomAvailablePosition(this.random).getOrNull()) != null) {
final MyMaze.Path path = myMaze.createPath(startPosition);
while (true) {
final Position nextPosition = path.nextRandomPosition(this.random);
if (path.contains(nextPosition)) {
path.removeLoopUpTo(nextPosition);
} else {
path.append(nextPosition);
if (myMaze.isPartOfMaze(nextPosition)) {
myMaze.setPartOfMaze(path);
pths.add(path);
break;
}
}
}
}
applyToMaze(pths, maze);
solve(maze);
// 1. pick random location not in maze
// 2. perform random walk until you reach the maze (*)
// 3. add path to maze
// (*): random walk:
// 1. advance in random direction
// 2. if loop with current path is formed, remove loop, continue from last location before loop
}
private void applyToMaze(@NotNull final List<MyMaze.Path> pths, @NotNull final Maze maze) {
pths.forEach(path -> {
final Iterator<Direction> moves = Stream.ofAll(path.path)
.sliding(2)
.flatMap(poss -> poss.head().getDirectionTo(poss.get(1)));
Position position = path.path.getFirst();
while (moves.hasNext()) {
Tile tile = maze.getTileAt(position).get();
final Direction move = moves.next();
tile.digTo(move);
position = position.move(move);
maze.getTileAt(position).forEach(t -> t.digTo(move.invert()));
}
});
Direction direction = determineDirectionForDigging(maze.getStart());
Tile t = maze.getStartTile();
this.digTo(t, direction);
direction = determineDirectionForDigging(maze.getEnd());
t = maze.getEndTile();
this.digTo(t, direction);
// seal all walls, mark all as visited
for (int x = 0; x < maze.getWidth(); x++) {
for (int y = 0; y < maze.getHeight(); y++) {
maze.getTileAt(x, y).forEach(tile -> {
Stream.of(Direction.values())
.forEach(d -> {
if (tile.hasWallAt(d)) {
tile.preventDiggingToOrFrom(d);
} else {
tile.digFrom(d);
}
});
});
}
}
}
@Nullable
private Direction determineDirectionForDigging(@NotNull final Position position) {
if (position.y() == 0) {
return Direction.TOP;
}
if (position.x() == 0) {
return Direction.LEFT;
}
if (position.y() == this.maze.getHeight() - 1) {
return Direction.BOTTOM;
}
if (position.x() == this.maze.getWidth() - 1) {
return Direction.RIGHT;
}
return null;
}
private void digTo(@NotNull final Tile tile, @NotNull final Direction direction) {
tile.enableDiggingToOrFrom(direction);
tile.digTo(direction);
}
private void solve(@NotNull final Maze maze) {
EnumSet<Direction>[][] remainingDirs = new EnumSet[maze.getWidth()][maze.getHeight()];
for (int x = 0; x < remainingDirs.length; x++) {
for (int y = 0; y < remainingDirs[x].length; y++) {
remainingDirs[x][y] = EnumSet.allOf(Direction.class);
}
}
Position p = maze.getStart();
final Direction direction = this.determineDirectionForDigging(p);
remainingDirs[p.x()][p.y()].remove(direction);
LinkedList<Position> solution = new LinkedList<>();
solution.add(p);
while (!p.equals(maze.getEnd())) {
final Tile tile = maze.getTileAt(p).get();
EnumSet<Direction> dirs = remainingDirs[p.x()][p.y()];
dirs.removeIf(tile::hasWallAt);
if (dirs.isEmpty()) {
solution.pop();
p = solution.peek();
} else {
final Direction nextDir = dirs.iterator().next();
final Position nextPos = p.move(nextDir);
solution.push(nextPos);
remainingDirs[p.x()][p.y()].remove(nextDir);
remainingDirs[nextPos.x()][nextPos.y()].remove(nextDir.invert());
p = nextPos;
}
}
solution.forEach(s -> maze.getTileAt(s).forEach(Tile::setSolution));
}
private static class MyMaze {
private final int width;
private final int height;
private final boolean[][] partOfMaze;
private final boolean[] completeColumns;
MyMaze(final int width, final int height) {
this.width = width;
this.height = height;
this.partOfMaze = new boolean[this.width][this.height];
for (int x = 0; x < this.width; x++) {
this.partOfMaze[x] = new boolean[this.height];
}
this.completeColumns = new boolean[this.width];
}
boolean isPartOfMaze(final int x, final int y) {
return this.partOfMaze[x][y];
}
boolean isPartOfMaze(@NotNull final Position position) {
return this.isPartOfMaze(position.x(), position.y());
}
void setPartOfMaze(final int x, final int y) {
this.partOfMaze[x][y] = true;
this.checkCompleteColumn(x);
}
void setPartOfMaze(@NotNull final Position position) {
this.setPartOfMaze(position.x(), position.y());
}
void setPartOfMaze(@NotNull final Path path) {
path.path.forEach(this::setPartOfMaze);
}
void checkCompleteColumn(final int x) {
if (this.completeColumns[x]) {
return;
}
for (int y = 0; y < this.height; y++) {
if (!this.isPartOfMaze(x, y)) {
return;
}
}
this.completeColumns[x] = true;
}
Option<Position> getRandomAvailablePosition(@NotNull final Random random) {
final Seq<Integer> allowedColumns = Vector.ofAll(this.completeColumns)
.zipWithIndex()
.reject(Tuple2::_1)
.map(Tuple2::_2);
if (allowedColumns.isEmpty()) {
return Option.none();
}
final int x = allowedColumns.get(random.nextInt(allowedColumns.size()));
final boolean[] column = partOfMaze[x];
final Seq<Integer> allowedRows = Vector.ofAll(column)
.zipWithIndex()
.reject(Tuple2::_1)
.map(Tuple2::_2);
if (allowedRows.isEmpty()) {
return Option.none();
}
final int y = allowedRows.get(random.nextInt(allowedRows.size()));
return Option.some(new Position(x, y));
}
public Path createPath(@NotNull final Position position) {
return new Path(position);
}
private class Path {
@NotNull
private final List<Position> path = new LinkedList<>();
Path(@NotNull final Position position) {
this.path.add(position);
}
@NotNull
Position nextRandomPosition(@NotNull final Random random) {
final Direction direction = this.getRandomDirectionFromLastPosition(random);
return this.path.getLast().move(direction);
}
boolean contains(@NotNull final Position position) {
return this.path.contains(position);
}
void removeLoopUpTo(@NotNull final Position position) {
while (!this.path.removeLast().equals(position)) {
}
this.path.add(position);
}
public void append(@NotNull final Position nextPosition) {
this.path.add(nextPosition);
}
@NotNull
private Direction getRandomDirectionFromLastPosition(@NotNull final Random random) {
final EnumSet<Direction> validDirections = this.getValidDirectionsFromLastPosition();
if (validDirections.isEmpty()) {
throw new IllegalStateException("WE MUST NOT GET HERE! analyze why it happened!!!");
}
if (validDirections.size() == 1) {
return validDirections.iterator().next();
}
final Direction[] directionArray = validDirections.toArray(Direction[]::new);
final int index = random.nextInt(directionArray.length);
return directionArray[index];
}
@NotNull
private EnumSet<Direction> getValidDirectionsFromLastPosition() {
final Position fromPosition = this.path.getLast();
final EnumSet<Direction> validDirections = EnumSet.allOf(Direction.class);
if (this.path.size() > 1) {
final Position prevP = this.path.get(this.path.size() - 2);
fromPosition.getDirectionTo(prevP)
.forEach(validDirections::remove);
}
boolean canLeft = fromPosition.x() > 0;
boolean canRight = fromPosition.x() < width - 1;
boolean canUp = fromPosition.y() > 0;
boolean canDown = fromPosition.y() < height - 1;
if (!canLeft) {
validDirections.remove(Direction.LEFT);
}
if (!canRight) {
validDirections.remove(Direction.RIGHT);
}
if (!canUp) {
validDirections.remove(Direction.TOP);
}
if (!canDown) {
validDirections.remove(Direction.BOTTOM);
}
return validDirections;
}
@Override
public String toString() {
return Stream.ofAll(this.path)
.map(position -> "(%s,%s)".formatted(position.x(), position.y()))
.mkString("Path[", "->", "]");
}
}
}
}

3
src/main/java/ch/fritteli/maze/generator/model/Direction.java
View file

@ -1,14 +1,11 @@
package ch.fritteli.maze.generator.model; package ch.fritteli.maze.generator.model;
import org.jetbrains.annotations.NotNull;
public enum Direction { public enum Direction {
TOP, TOP,
RIGHT, RIGHT,
BOTTOM, BOTTOM,
LEFT; LEFT;
@NotNull
public Direction invert() { public Direction invert() {
return switch (this) { return switch (this) {
case TOP -> BOTTOM; case TOP -> BOTTOM;

36
src/main/java/ch/fritteli/maze/generator/model/Maze.java
View file

@ -3,7 +3,6 @@ package ch.fritteli.maze.generator.model;
import io.vavr.control.Option; import io.vavr.control.Option;
import lombok.EqualsAndHashCode; import lombok.EqualsAndHashCode;
import lombok.Getter; import lombok.Getter;
import lombok.Setter;
import lombok.ToString; import lombok.ToString;
import org.jetbrains.annotations.NotNull; import org.jetbrains.annotations.NotNull;
@ -22,9 +21,6 @@ public class Maze {
private final Position start; private final Position start;
@Getter @Getter
private final Position end; private final Position end;
@Getter
@Setter
private String algorithm;
public Maze(final int width, final int height) { public Maze(final int width, final int height) {
this(width, height, System.nanoTime()); this(width, height, System.nanoTime());
@ -38,11 +34,7 @@ public class Maze {
this(width, height, randomSeed, new Position(0, 0), new Position(width - 1, height - 1)); this(width, height, randomSeed, new Position(0, 0), new Position(width - 1, height - 1));
} }
public Maze(final int width, public Maze(final int width, final int height, final long randomSeed, @NotNull final Position start, @NotNull final Position end) {
final int height,
final long randomSeed,
@NotNull final Position start,
@NotNull final Position end) {
if (width <= 1 || height <= 1) { if (width <= 1 || height <= 1) {
throw new IllegalArgumentException("width and height must be >1"); throw new IllegalArgumentException("width and height must be >1");
} }
@ -79,12 +71,7 @@ public class Maze {
/** /**
* INTERNAL API. Exists only for deserialization. Not to be called from user code. * INTERNAL API. Exists only for deserialization. Not to be called from user code.
*/ */
private Maze(@NotNull final Tile[][] field, private Maze(@NotNull final Tile[][] field, final int width, final int height, @NotNull final Position start, @NotNull final Position end, final long randomSeed) {
final int width,
final int height,
@NotNull final Position start,
@NotNull final Position end,
final long randomSeed) {
this.field = field; this.field = field;
this.width = width; this.width = width;
this.height = height; this.height = height;
@ -93,25 +80,6 @@ public class Maze {
this.end = end; this.end = end;
} }
/**
* INTERNAL API. Exists only for deserialization. Not to be called from user code.
*/
private Maze(@NotNull final Tile[][] field,
final int width,
final int height,
@NotNull final Position start,
@NotNull final Position end,
final long randomSeed,
@NotNull final String algorithm) {
this.field = field;
this.width = width;
this.height = height;
this.randomSeed = randomSeed;
this.algorithm = algorithm;
this.start = start;
this.end = end;
}
@NotNull @NotNull
public Option<Tile> getTileAt(@NotNull final Position position) { public Option<Tile> getTileAt(@NotNull final Position position) {
return this.getTileAt(position.x(), position.y()); return this.getTileAt(position.x(), position.y());

18
src/main/java/ch/fritteli/maze/generator/model/Position.java
View file

@ -1,12 +1,10 @@
package ch.fritteli.maze.generator.model; package ch.fritteli.maze.generator.model;
import io.vavr.control.Option;
import lombok.With; import lombok.With;
import org.jetbrains.annotations.NotNull; import org.jetbrains.annotations.NotNull;
@With @With
public record Position(int x, int y) { public record Position(int x, int y) {
@NotNull
public Position move(@NotNull final Direction direction) { public Position move(@NotNull final Direction direction) {
return switch (direction) { return switch (direction) {
case BOTTOM -> this.withY(this.y + 1); case BOTTOM -> this.withY(this.y + 1);
@ -15,20 +13,4 @@ public record Position(int x, int y) {
case TOP -> this.withY(this.y - 1); case TOP -> this.withY(this.y - 1);
}; };
} }
@NotNull
public Option<Direction> getDirectionTo(@NotNull final Position position) {
final int xDiff = position.x - this.x;
final int yDiff = position.y - this.y;
return switch (xDiff) {
case -1 -> Option.when(yDiff == 0, Direction.LEFT);
case 0 -> switch (yDiff) {
case -1 -> Option.some(Direction.TOP);
case 1 -> Option.some(Direction.BOTTOM);
default -> Option.none();
};
case 1 -> Option.when(yDiff == 0, Direction.RIGHT);
default -> Option.none();
};
}
} }

270
src/main/java/ch/fritteli/maze/generator/renderer/html/HTMLRenderer.java
View file

@ -6,109 +6,108 @@ import org.jetbrains.annotations.NotNull;
public class HTMLRenderer implements Renderer<String> { public class HTMLRenderer implements Renderer<String> {
private static final String POSTAMBLE = """ private static final String POSTAMBLE = "<script>"
<script> + "let userPath = [];"
let userPath = []; + "const DIR_UNDEF = -1;"
const DIR_UNDEF = -1; + "const DIR_SAME = 0;"
const DIR_SAME = 0; + "const DIR_UP = 1;"
const DIR_UP = 1; + "const DIR_RIGHT = 2;"
const DIR_RIGHT = 2; + "const DIR_DOWN = 3;"
const DIR_DOWN = 3; + "const DIR_LEFT = 4;"
const DIR_LEFT = 4; + "function getCoords(cell) {"
function getCoords(cell) { + " return {"
return { + " x: cell.cellIndex,"
x: cell.cellIndex, + " y: cell.parentElement.rowIndex"
y: cell.parentElement.rowIndex + " };"
}; + "}"
} + "function distance(prev, next) {"
function distance(prev, next) { + " return Math.abs(prev.x - next.x) + Math.abs(prev.y - next.y);"
return Math.abs(prev.x - next.x) + Math.abs(prev.y - next.y); + "}"
} + "function direction(prev, next) {"
function direction(prev, next) { + " const dist = distance(prev, next);"
const dist = distance(prev, next); + " if (dist === 0) {"
if (dist === 0) { + " return DIR_SAME;"
return DIR_SAME; + " }"
} + " if (dist !== 1) {"
if (dist !== 1) { + " return DIR_UNDEF;"
return DIR_UNDEF; + " }"
} + " if (next.x === prev.x) {"
if (next.x === prev.x) { + " if (next.y === prev.y + 1) {"
if (next.y === prev.y + 1) { + " return DIR_DOWN;"
return DIR_DOWN; + " }"
} + " return DIR_UP;"
return DIR_UP; + " }"
} + " if (next.x === prev.x + 1) {"
if (next.x === prev.x + 1) { + " return DIR_RIGHT;"
return DIR_RIGHT; + " }"
} + " return DIR_LEFT;"
return DIR_LEFT; + "}"
} + "(function () {"
(function () { + " const labyrinthTable = document.getElementById(\"labyrinth\");"
const labyrinthTable = document.getElementById("labyrinth"); + " const labyrinthCells = labyrinthTable.getElementsByTagName(\"td\");"
const labyrinthCells = labyrinthTable.getElementsByTagName("td"); + " const start = {x: 0, y: 0};"
const start = {x: 0, y: 0}; + " const end = {"
const end = { + " x: labyrinthTable.getElementsByTagName(\"tr\")[0].getElementsByTagName(\"td\").length - 1,"
x: labyrinthTable.getElementsByTagName("tr")[0].getElementsByTagName("td").length - 1, + " y: labyrinthTable.getElementsByTagName(\"tr\").length - 1"
y: labyrinthTable.getElementsByTagName("tr").length - 1 + " };"
}; + " for (let i = 0; i < labyrinthCells.length; i++) {"
for (let i = 0; i < labyrinthCells.length; i++) { + " let cell = labyrinthCells.item(i);"
let cell = labyrinthCells.item(i); + " cell.onclick = (event) => {"
cell.onclick = (event) => { + " let target = event.target;"
let target = event.target; + " const coords = getCoords(target);"
const coords = getCoords(target); + " if (coords.x === end.x && coords.y === end.y) {"
if (coords.x === end.x && coords.y === end.y) { + " alert(\"HOORAY! You did it! Congratulations!\")"
alert("HOORAY! You did it! Congratulations!") + " }"
} + " if (userPath.length === 0) {"
if (userPath.length === 0) { + " if (coords.x === start.x && coords.y === start.y) {"
if (coords.x === start.x && coords.y === start.y) { + " userPath.push(coords);"
userPath.push(coords); + " target.classList.toggle(\"user\");"
target.classList.toggle("user"); + " }"
} + " } else {"
} else { + " const dir = direction(userPath[userPath.length - 1], coords);"
const dir = direction(userPath[userPath.length - 1], coords); + " switch (dir) {"
switch (dir) { + " case DIR_UNDEF:"
case DIR_UNDEF: + " return;"
return; + " case DIR_SAME:"
case DIR_SAME: + " userPath.pop();"
userPath.pop(); + " target.classList.toggle(\"user\");"
target.classList.toggle("user"); + " return;"
return; + " default:"
default: + " if (userPath.find(value => value.x === coords.x && value.y === coords.y)) {"
if (userPath.find(value => value.x === coords.x && value.y === coords.y)) { + " return;"
return; + " } else {"
} else { + " switch (dir) {"
switch (dir) { + " case DIR_UP:"
case DIR_UP: + " if (target.classList.contains(\"bottom\")) {"
if (target.classList.contains("bottom")) { + " return;"
return; + " }"
} + " break;"
break; + " case DIR_RIGHT:"
case DIR_RIGHT: + " if (target.classList.contains(\"left\")) {"
if (target.classList.contains("left")) { + " return;"
return; + " }"
} + " break;"
break; + " case DIR_DOWN:"
case DIR_DOWN: + " if (target.classList.contains(\"top\")) {"
if (target.classList.contains("top")) { + " return;"
return; + " }"
} + " break;"
break; + " case DIR_LEFT:"
case DIR_LEFT: + " if (target.classList.contains(\"right\")) {"
if (target.classList.contains("right")) { + " return;"
return; + " }"
} + " break;"
break; + " }"
} + " userPath.push(coords);"
userPath.push(coords); + " target.classList.toggle(\"user\");"
target.classList.toggle("user"); + " return;"
return; + " }"
} + " }"
} + " }"
} + " };"
}; + " }"
} + "})();"
})(); + "</script></body></html>";
</script></body></html>""";
private HTMLRenderer() { private HTMLRenderer() {
} }
@ -136,42 +135,33 @@ public class HTMLRenderer implements Renderer<String> {
} }
private String getPreamble(@NotNull final Maze maze) { private String getPreamble(@NotNull final Maze maze) {
return """ return "<!DOCTYPE html><html lang=\"en\">" +
<!DOCTYPE html> "<head>" +
<html lang="en"> "<title>Maze " + maze.getWidth() + "x" + maze.getHeight() + ", ID " + maze.getRandomSeed() + "</title>" +
<head> "<meta charset=\"utf-8\">" +
<title>Maze %dx%d, ID %d, Algorithm %s</title> "<style>" +
<meta charset="utf-8"> "table{border-collapse:collapse;}" +
<style> "td{border:0 solid black;height:1em;width:1em;cursor:pointer;}" +
table{border-collapse:collapse;} "td.top{border-top-width:1px;}" +
td{border:0 solid black;height:1em;width:1em;cursor:pointer;} "td.right{border-right-width:1px;}" +
td.top{border-top-width:1px;} "td.bottom{border-bottom-width:1px;}" +
td.right{border-right-width:1px;} "td.left{border-left-width:1px;}" +
td.bottom{border-bottom-width:1px;} "td.user{background:hotpink;}" +
td.left{border-left-width:1px;} "</style>" +
td.user{background:hotpink;} "<script>" +
</style> "let solution = false;" +
<script> "function toggleSolution() {" +
let solution = false; "let stylesheet = document.styleSheets[0];" +
function toggleSolution() { "if(solution){" +
let stylesheet = document.styleSheets[0]; "stylesheet.deleteRule(0);" +
if (solution) { "}else{" +
stylesheet.deleteRule(0); "stylesheet.insertRule(\"td.solution{background-color:lightgray;}\", 0);" +
} else { "}" +
stylesheet.insertRule("td.solution{background-color:lightgray;}", 0); "solution = !solution;" +
} "}" +
solution = !solution; "</script>" +
} "</head>" +
</script> "<body>" +
</head> "<input id=\"solutionbox\" type=\"checkbox\" onclick=\"toggleSolution()\"/><label for=\"solutionbox\">show solution</label>";
<body>
<input id="solutionbox" type="checkbox" onclick="toggleSolution()"/>
<label for="solutionbox">show solution</label>"""
.formatted(
maze.getWidth(),
maze.getHeight(),
maze.getRandomSeed(),
maze.getAlgorithm()
);
} }
} }

1
src/main/java/ch/fritteli/maze/generator/renderer/json/Generator.java
View file

@ -23,7 +23,6 @@ class Generator {
JsonMaze generate() { JsonMaze generate() {
final JsonMaze result = new JsonMaze(); final JsonMaze result = new JsonMaze();
result.setId(String.valueOf(this.maze.getRandomSeed())); result.setId(String.valueOf(this.maze.getRandomSeed()));
result.setAlgorithm(this.maze.getAlgorithm());
result.setWidth(this.maze.getWidth()); result.setWidth(this.maze.getWidth());
result.setHeight(this.maze.getHeight()); result.setHeight(this.maze.getHeight());
final List<List<JsonCell>> rows = new ArrayList<>(); final List<List<JsonCell>> rows = new ArrayList<>();

4
src/main/java/ch/fritteli/maze/generator/renderer/pdf/Generator.java
View file

@ -34,7 +34,7 @@ class Generator {
final PDDocument pdDocument = new PDDocument(); final PDDocument pdDocument = new PDDocument();
final PDDocumentInformation info = new PDDocumentInformation(); final PDDocumentInformation info = new PDDocumentInformation();
info.setTitle("Maze %sx%s, ID %s (%s)".formatted(this.maze.getWidth(), this.maze.getHeight(), this.maze.getRandomSeed(), this.maze.getAlgorithm())); info.setTitle("Maze %sx%s, ID %s".formatted(this.maze.getWidth(), this.maze.getHeight(), this.maze.getRandomSeed()));
pdDocument.setDocumentInformation(info); pdDocument.setDocumentInformation(info);
final PDPage puzzlePage = new PDPage(new PDRectangle(pageWidth, pageHeight)); final PDPage puzzlePage = new PDPage(new PDRectangle(pageWidth, pageHeight));
final PDPage solutionPage = new PDPage(new PDRectangle(pageWidth, pageHeight)); final PDPage solutionPage = new PDPage(new PDRectangle(pageWidth, pageHeight));
@ -233,7 +233,7 @@ class Generator {
if (position.equals(previousPosition)) { if (position.equals(previousPosition)) {
continue; continue;
} }
if (tileAtPosition.exists(Tile::isSolution)) { if (tileAtPosition.map(Tile::isSolution).getOrElse(false)) {
return position; return position;
} }
} }

7
src/main/java/ch/fritteli/maze/generator/serialization/AbstractMazeInputStream.java
View file

@ -4,7 +4,6 @@ import ch.fritteli.maze.generator.model.Maze;
import org.jetbrains.annotations.NotNull; import org.jetbrains.annotations.NotNull;
import java.io.ByteArrayInputStream; import java.io.ByteArrayInputStream;
import java.io.IOException;
public abstract class AbstractMazeInputStream extends ByteArrayInputStream { public abstract class AbstractMazeInputStream extends ByteArrayInputStream {
@ -15,7 +14,7 @@ public abstract class AbstractMazeInputStream extends ByteArrayInputStream {
public abstract void checkHeader(); public abstract void checkHeader();
@NotNull @NotNull
public abstract Maze readMazeData() throws IOException; public abstract Maze readMazeData();
public byte readByte() { public byte readByte() {
final int read = this.read(); final int read = this.read();
@ -26,10 +25,6 @@ public abstract class AbstractMazeInputStream extends ByteArrayInputStream {
return (byte) read; return (byte) read;
} }
public int readByteAsInt() {
return 0xff & this.readByte();
}
public int readInt() { public int readInt() {
int result = 0; int result = 0;
result |= (0xff & this.readByte()) << 24; result |= (0xff & this.readByte()) << 24;

100
src/main/java/ch/fritteli/maze/generator/serialization/CommonTileHandler.java
View file

@ -1,100 +0,0 @@
package ch.fritteli.maze.generator.serialization;
import ch.fritteli.maze.generator.model.Direction;
import ch.fritteli.maze.generator.model.Tile;
import lombok.experimental.UtilityClass;
import org.jetbrains.annotations.NotNull;
import java.lang.reflect.Constructor;
import java.lang.reflect.InvocationTargetException;
import java.util.EnumSet;
/**
* Binary format description of a {@link Tile}.<br>
* A tile is stored in one byte:
* <ul>
* <li>bits 0..2: always 0</li>
* <li>bit 3: 1=solution, 0=not solution</li>
* <li>bits 4..7: encode walls</li>
* </ul>
* The values for bits 4..7 are as follows:
* <pre>
* decimal hex bin border
* 0 0 0000 no border
* 1 1 0001 top
* 2 2 0010 right
* 3 3 0011 top+right
* 4 4 0100 bottom
* 5 5 0101 top+bottom
* 6 6 0110 right+bottom
* 7 7 0111 top+right+bottom
* 8 8 1000 left
* 9 9 1001 top+left
* 10 a 1010 right+left
* 11 b 1011 top+right+left
* 12 c 1100 bottom+left
* 13 d 1101 top+bottom+left
* 14 e 1110 right+bottom+left
* 15 f 1111 top+right+bottom+left
* </pre>
*/
@UtilityClass
public class CommonTileHandler {
private final byte TOP_BIT = 0b0000_0001;
private final byte RIGHT_BIT = 0b0000_0010;
private final byte BOTTOM_BIT = 0b0000_0100;
private final byte LEFT_BIT = 0b0000_1000;
private final byte SOLUTION_BIT = 0b0001_0000;
public byte getBitmaskForTile(@NotNull final Tile tile) {
byte bitmask = 0;
if (tile.hasWallAt(Direction.TOP)) {
bitmask |= TOP_BIT;
}
if (tile.hasWallAt(Direction.RIGHT)) {
bitmask |= RIGHT_BIT;
}
if (tile.hasWallAt(Direction.BOTTOM)) {
bitmask |= BOTTOM_BIT;
}
if (tile.hasWallAt((Direction.LEFT))) {
bitmask |= LEFT_BIT;
}
if (tile.isSolution()) {
bitmask |= SOLUTION_BIT;
}
return bitmask;
}
@NotNull
public Tile getTileForBitmask(final byte bitmask) {
final EnumSet<Direction> walls = EnumSet.noneOf(Direction.class);
if ((bitmask & TOP_BIT) == TOP_BIT) {
walls.add(Direction.TOP);
}
if ((bitmask & RIGHT_BIT) == RIGHT_BIT) {
walls.add(Direction.RIGHT);
}
if ((bitmask & BOTTOM_BIT) == BOTTOM_BIT) {
walls.add(Direction.BOTTOM);
}
if ((bitmask & LEFT_BIT) == LEFT_BIT) {
walls.add(Direction.LEFT);
}
final boolean solution = (bitmask & SOLUTION_BIT) == SOLUTION_BIT;
return createTile(walls, solution);
}
@NotNull
private Tile createTile(@NotNull final EnumSet<Direction> walls, boolean solution) {
try {
final Constructor<Tile> constructor = Tile.class.getDeclaredConstructor(EnumSet.class, Boolean.TYPE);
constructor.setAccessible(true);
return constructor.newInstance(walls, solution);
} catch (@NotNull final NoSuchMethodException | InstantiationException | IllegalAccessException |
InvocationTargetException e) {
throw new RuntimeException("Can not deserialize Tile from maze data.", e);
}
}
}

10
src/main/java/ch/fritteli/maze/generator/serialization/v1/MazeInputStreamV1.java
View file

@ -3,7 +3,6 @@ package ch.fritteli.maze.generator.serialization.v1;
import ch.fritteli.maze.generator.model.Maze; import ch.fritteli.maze.generator.model.Maze;
import ch.fritteli.maze.generator.model.Tile; import ch.fritteli.maze.generator.model.Tile;
import ch.fritteli.maze.generator.serialization.AbstractMazeInputStream; import ch.fritteli.maze.generator.serialization.AbstractMazeInputStream;
import ch.fritteli.maze.generator.serialization.CommonTileHandler;
import org.jetbrains.annotations.NotNull; import org.jetbrains.annotations.NotNull;
public class MazeInputStreamV1 extends AbstractMazeInputStream { public class MazeInputStreamV1 extends AbstractMazeInputStream {
@ -14,9 +13,6 @@ public class MazeInputStreamV1 extends AbstractMazeInputStream {
@Override @Override
public void checkHeader() { public void checkHeader() {
// 00 0x1a magic
// 01 0xb1 magic
// 02 0x01 version
final byte magic1 = this.readByte(); final byte magic1 = this.readByte();
if (magic1 != SerializerDeserializerV1.MAGIC_BYTE_1) { if (magic1 != SerializerDeserializerV1.MAGIC_BYTE_1) {
throw new IllegalArgumentException("Invalid maze data."); throw new IllegalArgumentException("Invalid maze data.");
@ -34,10 +30,6 @@ public class MazeInputStreamV1 extends AbstractMazeInputStream {
@NotNull @NotNull
@Override @Override
public Maze readMazeData() { public Maze readMazeData() {
// 03..10 random seed number (long)
// 11..14 width (int)
// 15..18 height (int)
// 19.. tiles
final long randomSeed = this.readLong(); final long randomSeed = this.readLong();
final int width = this.readInt(); final int width = this.readInt();
final int height = this.readInt(); final int height = this.readInt();
@ -50,7 +42,7 @@ public class MazeInputStreamV1 extends AbstractMazeInputStream {
for (int y = 0; y < height; y++) { for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) { for (int x = 0; x < width; x++) {
final byte bitmask = this.readByte(); final byte bitmask = this.readByte();
tiles[x][y] = CommonTileHandler.getTileForBitmask(bitmask); tiles[x][y] = SerializerDeserializerV1.getTileForBitmask(bitmask);
} }
} }

10
src/main/java/ch/fritteli/maze/generator/serialization/v1/MazeOutputStreamV1.java
View file

@ -3,16 +3,12 @@ package ch.fritteli.maze.generator.serialization.v1;
import ch.fritteli.maze.generator.model.Maze; import ch.fritteli.maze.generator.model.Maze;
import ch.fritteli.maze.generator.model.Tile; import ch.fritteli.maze.generator.model.Tile;
import ch.fritteli.maze.generator.serialization.AbstractMazeOutputStream; import ch.fritteli.maze.generator.serialization.AbstractMazeOutputStream;
import ch.fritteli.maze.generator.serialization.CommonTileHandler;
import org.jetbrains.annotations.NotNull; import org.jetbrains.annotations.NotNull;
public class MazeOutputStreamV1 extends AbstractMazeOutputStream { public class MazeOutputStreamV1 extends AbstractMazeOutputStream {
@Override @Override
public void writeHeader() { public void writeHeader() {
// 00 0x1a magic
// 01 0xb1 magic
// 02 0x02 version
this.writeByte(SerializerDeserializerV1.MAGIC_BYTE_1); this.writeByte(SerializerDeserializerV1.MAGIC_BYTE_1);
this.writeByte(SerializerDeserializerV1.MAGIC_BYTE_2); this.writeByte(SerializerDeserializerV1.MAGIC_BYTE_2);
this.writeByte(SerializerDeserializerV1.VERSION_BYTE); this.writeByte(SerializerDeserializerV1.VERSION_BYTE);
@ -20,10 +16,6 @@ public class MazeOutputStreamV1 extends AbstractMazeOutputStream {
@Override @Override
public void writeMazeData(@NotNull final Maze maze) { public void writeMazeData(@NotNull final Maze maze) {
// 03..10 random seed number (long)
// 11..14 width (int)
// 15..18 height (int)
// 19.. tiles
final long randomSeed = maze.getRandomSeed(); final long randomSeed = maze.getRandomSeed();
final int width = maze.getWidth(); final int width = maze.getWidth();
final int height = maze.getHeight(); final int height = maze.getHeight();
@ -35,7 +27,7 @@ public class MazeOutputStreamV1 extends AbstractMazeOutputStream {
for (int x = 0; x < width; x++) { for (int x = 0; x < width; x++) {
// We .get() it, because we want to crash hard if it is not available. // We .get() it, because we want to crash hard if it is not available.
final Tile tile = maze.getTileAt(x, y).get(); final Tile tile = maze.getTileAt(x, y).get();
final byte bitmask = CommonTileHandler.getBitmaskForTile(tile); final byte bitmask = SerializerDeserializerV1.getBitmaskForTile(tile);
this.writeByte(bitmask); this.writeByte(bitmask);
} }
} }

87
src/main/java/ch/fritteli/maze/generator/serialization/v1/SerializerDeserializerV1.java
View file

@ -1,5 +1,6 @@
package ch.fritteli.maze.generator.serialization.v1; package ch.fritteli.maze.generator.serialization.v1;
import ch.fritteli.maze.generator.model.Direction;
import ch.fritteli.maze.generator.model.Maze; import ch.fritteli.maze.generator.model.Maze;
import ch.fritteli.maze.generator.model.Tile; import ch.fritteli.maze.generator.model.Tile;
import lombok.experimental.UtilityClass; import lombok.experimental.UtilityClass;
@ -7,17 +8,38 @@ import org.jetbrains.annotations.NotNull;
import java.lang.reflect.Constructor; import java.lang.reflect.Constructor;
import java.lang.reflect.InvocationTargetException; import java.lang.reflect.InvocationTargetException;
import java.util.EnumSet;
/** /**
* Header bytes are: * <pre>
* decimal hex bin border
* 0 0 0000 no border
* 1 1 0001 top
* 2 2 0010 right
* 3 3 0011 top+right
* 4 4 0100 bottom
* 5 5 0101 top+bottom
* 6 6 0110 right+bottom
* 7 7 0111 top+right+bottom
* 8 8 1000 left
* 9 9 1001 top+left
* 10 a 1010 right+left
* 11 b 1011 top+right+left
* 12 c 1100 bottom+left
* 13 d 1101 top+bottom+left
* 14 e 1110 right+bottom+left
* 15 f 1111 top+right+bottom+left
* </pre>
* ==&gt; bits 0..2: always 0; bit 3: 1=solution, 0=not solution; bits 4..7: encode walls
* ==&gt; first bytes are:
* <pre> * <pre>
* byte hex meaning * byte hex meaning
* 00 0x1a magic * 00 0x1a magic
* 01 0xb1 magic * 01 0xb1 magic
* 02 0x01 version (0x00 -> dev, 0x01 -> stable) * 02 0x01 version (0x00 -> dev, 0x01 -> stable)
* 03..10 random seed number (long) * 03..06 width (int)
* 11..14 width (int) * 07..10 height (int)
* 15..18 height (int) * 11..18 random seed number (long)
* 19.. tiles * 19.. tiles
* </pre> * </pre>
* Extraneous space (poss. last nibble) is ignored. * Extraneous space (poss. last nibble) is ignored.
@ -28,6 +50,12 @@ public class SerializerDeserializerV1 {
final byte MAGIC_BYTE_2 = (byte) 0xb1; final byte MAGIC_BYTE_2 = (byte) 0xb1;
final byte VERSION_BYTE = 0x01; final byte VERSION_BYTE = 0x01;
private final byte TOP_BIT = 0b0000_0001;
private final byte RIGHT_BIT = 0b0000_0010;
private final byte BOTTOM_BIT = 0b0000_0100;
private final byte LEFT_BIT = 0b0000_1000;
private final byte SOLUTION_BIT = 0b0001_0000;
/** /**
* Serializes the {@code maze} into a byte array. * Serializes the {@code maze} into a byte array.
* *
@ -66,4 +94,55 @@ public class SerializerDeserializerV1 {
throw new RuntimeException("Can not deserialize Maze from maze data.", e); throw new RuntimeException("Can not deserialize Maze from maze data.", e);
} }
} }
@NotNull
private Tile createTile(@NotNull final EnumSet<Direction> walls, boolean solution) {
try {
final Constructor<Tile> constructor = Tile.class.getDeclaredConstructor(EnumSet.class, Boolean.TYPE);
constructor.setAccessible(true);
return constructor.newInstance(walls, solution);
} catch (@NotNull final NoSuchMethodException | InstantiationException | IllegalAccessException |
InvocationTargetException e) {
throw new RuntimeException("Can not deserialize Tile from maze data.", e);
}
}
byte getBitmaskForTile(@NotNull final Tile tile) {
byte bitmask = 0;
if (tile.hasWallAt(Direction.TOP)) {
bitmask |= TOP_BIT;
}
if (tile.hasWallAt(Direction.RIGHT)) {
bitmask |= RIGHT_BIT;
}
if (tile.hasWallAt(Direction.BOTTOM)) {
bitmask |= BOTTOM_BIT;
}
if (tile.hasWallAt((Direction.LEFT))) {
bitmask |= LEFT_BIT;
}
if (tile.isSolution()) {
bitmask |= SOLUTION_BIT;
}
return bitmask;
}
@NotNull
Tile getTileForBitmask(final byte bitmask) {
final EnumSet<Direction> walls = EnumSet.noneOf(Direction.class);
if ((bitmask & TOP_BIT) == TOP_BIT) {
walls.add(Direction.TOP);
}
if ((bitmask & RIGHT_BIT) == RIGHT_BIT) {
walls.add(Direction.RIGHT);
}
if ((bitmask & BOTTOM_BIT) == BOTTOM_BIT) {
walls.add(Direction.BOTTOM);
}
if ((bitmask & LEFT_BIT) == LEFT_BIT) {
walls.add(Direction.LEFT);
}
final boolean solution = (bitmask & SOLUTION_BIT) == SOLUTION_BIT;
return createTile(walls, solution);
}
} }

3
src/main/java/ch/fritteli/maze/generator/serialization/v2/MazeInputStreamV2.java
View file

@ -4,7 +4,6 @@ import ch.fritteli.maze.generator.model.Maze;
import ch.fritteli.maze.generator.model.Position; import ch.fritteli.maze.generator.model.Position;
import ch.fritteli.maze.generator.model.Tile; import ch.fritteli.maze.generator.model.Tile;
import ch.fritteli.maze.generator.serialization.AbstractMazeInputStream; import ch.fritteli.maze.generator.serialization.AbstractMazeInputStream;
import ch.fritteli.maze.generator.serialization.CommonTileHandler;
import org.jetbrains.annotations.NotNull; import org.jetbrains.annotations.NotNull;
public class MazeInputStreamV2 extends AbstractMazeInputStream { public class MazeInputStreamV2 extends AbstractMazeInputStream {
@ -59,7 +58,7 @@ public class MazeInputStreamV2 extends AbstractMazeInputStream {
for (int y = 0; y < height; y++) { for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) { for (int x = 0; x < width; x++) {
final byte bitmask = this.readByte(); final byte bitmask = this.readByte();
tiles[x][y] = CommonTileHandler.getTileForBitmask(bitmask); tiles[x][y] = SerializerDeserializerV2.getTileForBitmask(bitmask);
} }
} }

3
src/main/java/ch/fritteli/maze/generator/serialization/v2/MazeOutputStreamV2.java
View file

@ -4,7 +4,6 @@ import ch.fritteli.maze.generator.model.Maze;
import ch.fritteli.maze.generator.model.Position; import ch.fritteli.maze.generator.model.Position;
import ch.fritteli.maze.generator.model.Tile; import ch.fritteli.maze.generator.model.Tile;
import ch.fritteli.maze.generator.serialization.AbstractMazeOutputStream; import ch.fritteli.maze.generator.serialization.AbstractMazeOutputStream;
import ch.fritteli.maze.generator.serialization.CommonTileHandler;
import org.jetbrains.annotations.NotNull; import org.jetbrains.annotations.NotNull;
public class MazeOutputStreamV2 extends AbstractMazeOutputStream { public class MazeOutputStreamV2 extends AbstractMazeOutputStream {
@ -46,7 +45,7 @@ public class MazeOutputStreamV2 extends AbstractMazeOutputStream {
for (int x = 0; x < width; x++) { for (int x = 0; x < width; x++) {
// We .get() it, because we want to crash hard if it is not available. // We .get() it, because we want to crash hard if it is not available.
final Tile tile = maze.getTileAt(x, y).get(); final Tile tile = maze.getTileAt(x, y).get();
final byte bitmask = CommonTileHandler.getBitmaskForTile(tile); final byte bitmask = SerializerDeserializerV2.getBitmaskForTile(tile);
this.writeByte(bitmask); this.writeByte(bitmask);
} }
} }

80
src/main/java/ch/fritteli/maze/generator/serialization/v2/SerializerDeserializerV2.java
View file

@ -1,5 +1,6 @@
package ch.fritteli.maze.generator.serialization.v2; package ch.fritteli.maze.generator.serialization.v2;
import ch.fritteli.maze.generator.model.Direction;
import ch.fritteli.maze.generator.model.Maze; import ch.fritteli.maze.generator.model.Maze;
import ch.fritteli.maze.generator.model.Position; import ch.fritteli.maze.generator.model.Position;
import ch.fritteli.maze.generator.model.Tile; import ch.fritteli.maze.generator.model.Tile;
@ -8,9 +9,29 @@ import org.jetbrains.annotations.NotNull;
import java.lang.reflect.Constructor; import java.lang.reflect.Constructor;
import java.lang.reflect.InvocationTargetException; import java.lang.reflect.InvocationTargetException;
import java.util.EnumSet;
/** /**
* Header bytes are: * <pre>
* decimal hex bin border
* 0 0 0000 no border
* 1 1 0001 top
* 2 2 0010 right
* 3 3 0011 top+right
* 4 4 0100 bottom
* 5 5 0101 top+bottom
* 6 6 0110 right+bottom
* 7 7 0111 top+right+bottom
* 8 8 1000 left
* 9 9 1001 top+left
* 10 a 1010 right+left
* 11 b 1011 top+right+left
* 12 c 1100 bottom+left
* 13 d 1101 top+bottom+left
* 14 e 1110 right+bottom+left
* 15 f 1111 top+right+bottom+left
* </pre>
* ==&gt; bits 0..2: always 0; bit 3: 1=solution, 0=not solution; bits 4..7: encode walls ==&gt; first bytes are:
* <pre> * <pre>
* byte hex meaning * byte hex meaning
* 00 0x1a magic * 00 0x1a magic
@ -34,6 +55,12 @@ public class SerializerDeserializerV2 {
final byte MAGIC_BYTE_2 = (byte) 0xb1; final byte MAGIC_BYTE_2 = (byte) 0xb1;
final byte VERSION_BYTE = 0x02; final byte VERSION_BYTE = 0x02;
private final byte TOP_BIT = 0b0000_0001;
private final byte RIGHT_BIT = 0b0000_0010;
private final byte BOTTOM_BIT = 0b0000_0100;
private final byte LEFT_BIT = 0b0000_1000;
private final byte SOLUTION_BIT = 0b0001_0000;
/** /**
* Serializes the {@code maze} into a byte array. * Serializes the {@code maze} into a byte array.
* *
@ -72,4 +99,55 @@ public class SerializerDeserializerV2 {
throw new RuntimeException("Can not deserialize Maze from maze data.", e); throw new RuntimeException("Can not deserialize Maze from maze data.", e);
} }
} }
@NotNull
private Tile createTile(@NotNull final EnumSet<Direction> walls, boolean solution) {
try {
final Constructor<Tile> constructor = Tile.class.getDeclaredConstructor(EnumSet.class, Boolean.TYPE);
constructor.setAccessible(true);
return constructor.newInstance(walls, solution);
} catch (@NotNull final NoSuchMethodException | InstantiationException | IllegalAccessException |
InvocationTargetException e) {
throw new RuntimeException("Can not deserialize Tile from maze data.", e);
}
}
byte getBitmaskForTile(@NotNull final Tile tile) {
byte bitmask = 0;
if (tile.hasWallAt(Direction.TOP)) {
bitmask |= TOP_BIT;
}
if (tile.hasWallAt(Direction.RIGHT)) {
bitmask |= RIGHT_BIT;
}
if (tile.hasWallAt(Direction.BOTTOM)) {
bitmask |= BOTTOM_BIT;
}
if (tile.hasWallAt((Direction.LEFT))) {
bitmask |= LEFT_BIT;
}
if (tile.isSolution()) {
bitmask |= SOLUTION_BIT;
}
return bitmask;
}
@NotNull
Tile getTileForBitmask(final byte bitmask) {
final EnumSet<Direction> walls = EnumSet.noneOf(Direction.class);
if ((bitmask & TOP_BIT) == TOP_BIT) {
walls.add(Direction.TOP);
}
if ((bitmask & RIGHT_BIT) == RIGHT_BIT) {
walls.add(Direction.RIGHT);
}
if ((bitmask & BOTTOM_BIT) == BOTTOM_BIT) {
walls.add(Direction.BOTTOM);
}
if ((bitmask & LEFT_BIT) == LEFT_BIT) {
walls.add(Direction.LEFT);
}
final boolean solution = (bitmask & SOLUTION_BIT) == SOLUTION_BIT;
return createTile(walls, solution);
}
} }

78
src/main/java/ch/fritteli/maze/generator/serialization/v3/MazeInputStreamV3.java
View file

@ -1,78 +0,0 @@
package ch.fritteli.maze.generator.serialization.v3;
import ch.fritteli.maze.generator.model.Maze;
import ch.fritteli.maze.generator.model.Position;
import ch.fritteli.maze.generator.model.Tile;
import ch.fritteli.maze.generator.serialization.AbstractMazeInputStream;
import ch.fritteli.maze.generator.serialization.CommonTileHandler;
import org.jetbrains.annotations.NotNull;
import java.io.IOException;
import java.nio.charset.StandardCharsets;
public class MazeInputStreamV3 extends AbstractMazeInputStream {
public MazeInputStreamV3(@NotNull final byte[] buf) {
super(buf);
}
@Override
public void checkHeader() {
// 00 0x1a magic
// 01 0xb1 magic
// 02 0x03 version
final byte magic1 = this.readByte();
if (magic1 != SerializerDeserializerV3.MAGIC_BYTE_1) {
throw new IllegalArgumentException("Invalid maze data.");
}
final byte magic2 = this.readByte();
if (magic2 != SerializerDeserializerV3.MAGIC_BYTE_2) {
throw new IllegalArgumentException("Invalid maze data.");
}
final int version = this.readByte();
if (version != SerializerDeserializerV3.VERSION_BYTE) {
throw new IllegalArgumentException("Unknown maze data version: " + version);
}
}
@NotNull
@Override
public Maze readMazeData() throws IOException {
// 03..06 width (int)
// 07..10 height (int)
// 11..14 start-x (int)
// 15..18 start-y (int)
// 19..22 end-x (int)
// 23..26 end-y (int)
// 27..34 random seed number (long)
// 35 length of the algorithm's name (unsigned byte)
// 36..+len name (bytes of String)
// +len+1.. tiles
final int width = this.readInt();
final int height = this.readInt();
final int startX = this.readInt();
final int startY = this.readInt();
final int endX = this.readInt();
final int endY = this.readInt();
final long randomSeed = this.readLong();
final int algorithmLength = this.readByteAsInt();
final String algorithm = new String(this.readNBytes(algorithmLength), StandardCharsets.UTF_8);
final Tile[][] tiles = new Tile[width][height];
for (int x = 0; x < width; x++) {
tiles[x] = new Tile[height];
}
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
final byte bitmask = this.readByte();
tiles[x][y] = CommonTileHandler.getTileForBitmask(bitmask);
}
}
final Position start = new Position(startX, startY);
final Position end = new Position(endX, endY);
return SerializerDeserializerV3.createMaze(tiles, width, height, start, end, randomSeed, algorithm);
}
}

85
src/main/java/ch/fritteli/maze/generator/serialization/v3/MazeOutputStreamV3.java
View file

@ -1,85 +0,0 @@
package ch.fritteli.maze.generator.serialization.v3;
import ch.fritteli.maze.generator.model.Maze;
import ch.fritteli.maze.generator.model.Position;
import ch.fritteli.maze.generator.model.Tile;
import ch.fritteli.maze.generator.serialization.AbstractMazeOutputStream;
import ch.fritteli.maze.generator.serialization.CommonTileHandler;
import org.jetbrains.annotations.NotNull;
import java.nio.charset.StandardCharsets;
public class MazeOutputStreamV3 extends AbstractMazeOutputStream {
@Override
public void writeHeader() {
// 00 0x1a magic
// 01 0xb1 magic
// 02 0x03 version
this.writeByte(SerializerDeserializerV3.MAGIC_BYTE_1);
this.writeByte(SerializerDeserializerV3.MAGIC_BYTE_2);
this.writeByte(SerializerDeserializerV3.VERSION_BYTE);
}
@Override
public void writeMazeData(@NotNull final Maze maze) {
// 03..06 width (int)
// 07..10 height (int)
// 11..14 start-x (int)
// 15..18 start-y (int)
// 19..22 end-x (int)
// 23..26 end-y (int)
// 27..34 random seed number (long)
// 35 length of the algorithm's name (unsigned byte)
// 36..+len name (bytes of String)
// +len+1.. tiles
final long randomSeed = maze.getRandomSeed();
final AlgorithmWrapper algorithm = this.getAlgorithmWrapper(maze.getAlgorithm());
final int width = maze.getWidth();
final int height = maze.getHeight();
final Position start = maze.getStart();
final Position end = maze.getEnd();
this.writeInt(width);
this.writeInt(height);
this.writeInt(start.x());
this.writeInt(start.y());
this.writeInt(end.x());
this.writeInt(end.y());
this.writeLong(randomSeed);
this.writeByte(algorithm.length());
this.writeBytes(algorithm.name());
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
// We .get() it, because we want to crash hard if it is not available.
final Tile tile = maze.getTileAt(x, y).get();
final byte bitmask = CommonTileHandler.getBitmaskForTile(tile);
this.writeByte(bitmask);
}
}
}
@NotNull
private AlgorithmWrapper getAlgorithmWrapper(@NotNull final String algorithm) {
final byte[] bytes = algorithm.getBytes(StandardCharsets.UTF_8);
if (bytes.length < 256) {
// Phew, that's the easy case!
return new AlgorithmWrapper(bytes, (byte) bytes.length);
}
// Let's use a very primitive, brute-force approach
int strLen = Math.min(255, algorithm.length());
int len;
byte[] name;
do {
name = algorithm.substring(0, strLen).getBytes(StandardCharsets.UTF_8);
len = name.length;
strLen--;
} while (len > 255);
return new AlgorithmWrapper(name, (byte) len);
}
private record AlgorithmWrapper(@NotNull byte[] name, byte length) {
}
}

92
src/main/java/ch/fritteli/maze/generator/serialization/v3/SerializerDeserializerV3.java
View file

@ -1,92 +0,0 @@
package ch.fritteli.maze.generator.serialization.v3;
import ch.fritteli.maze.generator.model.Maze;
import ch.fritteli.maze.generator.model.Position;
import ch.fritteli.maze.generator.model.Tile;
import lombok.experimental.UtilityClass;
import org.jetbrains.annotations.NotNull;
import java.io.IOException;
import java.lang.reflect.Constructor;
import java.lang.reflect.InvocationTargetException;
/**
* Header bytes are:
* <pre>
* byte hex meaning
* 00 0x1a magic
* 01 0xb1 magic
* 02 0x03 version (0x00 -> dev, 0x01, 0x02 -> deprecated, 0x03 -> stable)
* 03..06 width (int)
* 07..10 height (int)
* 11..14 start-x (int)
* 15..18 start-y (int)
* 19..22 end-x (int)
* 23..26 end-y (int)
* 27..34 random seed number (long)
* 35 length of the algorithm's name (number of bytes of the Java String) (unsigned byte)
* 36..(36+len) algorithm's name (bytes of the Java String) (byte...)
* 36+len+1.. tiles
* </pre>
* Extraneous space (poss. last nibble) is ignored.
*/
@UtilityClass
public class SerializerDeserializerV3 {
final byte MAGIC_BYTE_1 = 0x1a;
final byte MAGIC_BYTE_2 = (byte) 0xb1;
final byte VERSION_BYTE = 0x03;
/**
* Serializes the {@code maze} into a byte array.
*
* @param maze The {@link Maze} to be serialized.
* @return The resulting byte array.
*/
@NotNull
public byte[] serialize(@NotNull final Maze maze) {
final MazeOutputStreamV3 stream = new MazeOutputStreamV3();
stream.writeHeader();
stream.writeMazeData(maze);
return stream.toByteArray();
}
/**
* Deserializes the byte array into an instance of {@link Maze}.
*
* @param bytes The byte array to be deserialized.
* @return An instance of {@link Maze}.
*/
@NotNull
public Maze deserialize(@NotNull final byte[] bytes) throws IOException {
final MazeInputStreamV3 stream = new MazeInputStreamV3(bytes);
stream.checkHeader();
return stream.readMazeData();
}
@NotNull
Maze createMaze(@NotNull final Tile[][] field,
final int width,
final int height,
@NotNull final Position start,
@NotNull final Position end,
final long randomSeed,
@NotNull final String algorithm) {
try {
final Constructor<Maze> constructor = Maze.class.getDeclaredConstructor(
Tile[][].class,
Integer.TYPE,
Integer.TYPE,
Position.class,
Position.class,
Long.TYPE,
String.class
);
constructor.setAccessible(true);
return constructor.newInstance(field, width, height, start, end, randomSeed, algorithm);
} catch (@NotNull final NoSuchMethodException | IllegalAccessException | InstantiationException |
InvocationTargetException e) {
throw new RuntimeException("Can not deserialize Maze from maze data.", e);
}
}
}

5
src/main/resources/maze.schema.json
View file

@ -6,7 +6,6 @@
"additionalProperties": false, "additionalProperties": false,
"required": [ "required": [
"id", "id",
"algorithm",
"width", "width",
"height", "height",
"start", "start",
@ -18,10 +17,6 @@
"type": "string", "type": "string",
"description": "64 bit precision signed integer value. Transmitted as string, because ECMAScript (browsers) don't normally handle 64 bit integers well, as the ECMAScript 'number' type is a 64 bit signed double value, leaving only 53 bits for the integer part, thus losing precision." "description": "64 bit precision signed integer value. Transmitted as string, because ECMAScript (browsers) don't normally handle 64 bit integers well, as the ECMAScript 'number' type is a 64 bit signed double value, leaving only 53 bits for the integer part, thus losing precision."
}, },
"algorithm": {
"type": "string",
"description": "The name of the algorithm used to generate the maze."
},
"width": { "width": {
"type": "integer", "type": "integer",
"minimum": 1 "minimum": 1

44
src/test/java/ch/fritteli/maze/generator/algorithm/WilsonTest.java
View file

@ -1,44 +0,0 @@
package ch.fritteli.maze.generator.algorithm;
import ch.fritteli.maze.generator.model.Maze;
import ch.fritteli.maze.generator.renderer.text.TextRenderer;
import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;
class WilsonTest {
@Test
void foo() {
// arrange
final Maze maze = new Maze(10, 10, 0);
final Wilson wilson = new Wilson(maze);
// act
wilson.run();
// assert
final String textRepresentation = TextRenderer.newInstance().render(maze);
assertThat(textRepresentation).isEqualTo("""
╷ ╶─────┬─────┬───┬─┐
│ │ │ │ │
│ ╷ ╶─┬─┴─┬─╴ ╵ ╷ │ │
│ │ │ │ │ │ │
│ └─┐ │ ╶─┼─┬─┬─┘ │ │
│ │ │ │ │ │ │ │
│ ╷ │ └─╴ │ ╵ ╵ ╶─┘ │
│ │ │ │ │
├─┴─┘ ╷ ┌─┴───┐ ╷ ╶─┤
│ │ │ │ │ │
│ ╷ ┌─┘ └───╴ │ └─┬─┤
│ │ │ │ │ │
├─┴─┘ ┌───╴ ╷ └─┐ ╵ │
│ │ │ │ │
│ ╶─┬─┴─╴ ┌─┘ ╶─┘ ╶─┤
│ │ │ │
├─╴ ├─╴ ┌─┘ ╶─┐ ╶───┤
│ │ │ │ │
├───┴─╴ └─┐ ╶─┴───┐ │
│ │ │ │
└─────────┴───────┘ ╵""");
}
}

6
src/test/java/ch/fritteli/maze/generator/serialization/v1/SerializerDeserializerV1Test.java
View file

@ -13,8 +13,6 @@ class SerializerDeserializerV1Test {
new RandomDepthFirst(expected).run(); new RandomDepthFirst(expected).run();
final byte[] bytes = SerializerDeserializerV1.serialize(expected); final byte[] bytes = SerializerDeserializerV1.serialize(expected);
final Maze result = SerializerDeserializerV1.deserialize(bytes); final Maze result = SerializerDeserializerV1.deserialize(bytes);
assertThat(result.getAlgorithm()).isNull();
expected.setAlgorithm(null);
assertThat(result).isEqualTo(expected); assertThat(result).isEqualTo(expected);
} }
@ -24,8 +22,6 @@ class SerializerDeserializerV1Test {
new RandomDepthFirst(expected).run(); new RandomDepthFirst(expected).run();
final byte[] bytes = SerializerDeserializerV1.serialize(expected); final byte[] bytes = SerializerDeserializerV1.serialize(expected);
final Maze result = SerializerDeserializerV1.deserialize(bytes); final Maze result = SerializerDeserializerV1.deserialize(bytes);
assertThat(result.getAlgorithm()).isNull();
expected.setAlgorithm(null);
assertThat(result).isEqualTo(expected); assertThat(result).isEqualTo(expected);
} }
@ -35,8 +31,6 @@ class SerializerDeserializerV1Test {
new RandomDepthFirst(expected).run(); new RandomDepthFirst(expected).run();
final byte[] bytes = SerializerDeserializerV1.serialize(expected); final byte[] bytes = SerializerDeserializerV1.serialize(expected);
final Maze result = SerializerDeserializerV1.deserialize(bytes); final Maze result = SerializerDeserializerV1.deserialize(bytes);
assertThat(result.getAlgorithm()).isNull();
expected.setAlgorithm(null);
assertThat(result).isEqualTo(expected); assertThat(result).isEqualTo(expected);
} }
} }

46
src/test/java/ch/fritteli/maze/generator/serialization/v2/SerializerDeserializerV2Test.java
View file

@ -1,46 +0,0 @@
package ch.fritteli.maze.generator.serialization.v2;
import ch.fritteli.maze.generator.algorithm.RandomDepthFirst;
import ch.fritteli.maze.generator.algorithm.Wilson;
import ch.fritteli.maze.generator.model.Maze;
import ch.fritteli.maze.generator.model.Position;
import org.junit.jupiter.api.Test;
import java.io.IOException;
import static org.assertj.core.api.Assertions.assertThat;
class SerializerDeserializerV2Test {
@Test
void testSerializeDeserializeTiny() throws IOException {
final Maze expected = new Maze(2, 2, 255, new Position(0, 0), new Position(1, 1));
new RandomDepthFirst(expected).run();
final byte[] bytes = SerializerDeserializerV2.serialize(expected);
final Maze result = SerializerDeserializerV2.deserialize(bytes);
assertThat(result.getAlgorithm()).isNull();
expected.setAlgorithm(null);
assertThat(result).isEqualTo(expected);
}
@Test
void testSerializeDeserializeMedium() throws IOException {
final Maze expected = new Maze(20, 20, -271828182846L);
new Wilson(expected).run();
final byte[] bytes = SerializerDeserializerV2.serialize(expected);
final Maze result = SerializerDeserializerV2.deserialize(bytes);
assertThat(result.getAlgorithm()).isNull();
expected.setAlgorithm(null);
assertThat(result).isEqualTo(expected);
}
@Test
void testSerializeDeserializeLarge() throws IOException {
final Maze expected = new Maze(200, 320, 3141592653589793238L);
new Wilson(expected).run();
final byte[] bytes = SerializerDeserializerV2.serialize(expected);
final Maze result = SerializerDeserializerV2.deserialize(bytes);
assertThat(result.getAlgorithm()).isNull();
expected.setAlgorithm(null);
assertThat(result).isEqualTo(expected);
}
}

40
src/test/java/ch/fritteli/maze/generator/serialization/v3/SerializerDeserializerV3Test.java
View file

@ -1,40 +0,0 @@
package ch.fritteli.maze.generator.serialization.v3;
import ch.fritteli.maze.generator.algorithm.RandomDepthFirst;
import ch.fritteli.maze.generator.algorithm.Wilson;
import ch.fritteli.maze.generator.model.Maze;
import ch.fritteli.maze.generator.model.Position;
import org.junit.jupiter.api.Test;
import java.io.IOException;
import static org.assertj.core.api.Assertions.assertThat;
class SerializerDeserializerV3Test {
@Test
void testSerializeDeserializeTiny() throws IOException {
final Maze expected = new Maze(2, 2, 255, new Position(0, 0), new Position(1, 1));
new RandomDepthFirst(expected).run();
final byte[] bytes = SerializerDeserializerV3.serialize(expected);
final Maze result = SerializerDeserializerV3.deserialize(bytes);
assertThat(result).isEqualTo(expected);
}
@Test
void testSerializeDeserializeMedium() throws IOException {
final Maze expected = new Maze(20, 20, -271828182846L);
new Wilson(expected).run();
final byte[] bytes = SerializerDeserializerV3.serialize(expected);
final Maze result = SerializerDeserializerV3.deserialize(bytes);
assertThat(result).isEqualTo(expected);
}
@Test
void testSerializeDeserializeLarge() throws IOException {
final Maze expected = new Maze(200, 320, 3141592653589793238L);
new Wilson(expected).run();
final byte[] bytes = SerializerDeserializerV3.serialize(expected);
final Maze result = SerializerDeserializerV3.deserialize(bytes);
assertThat(result).isEqualTo(expected);
}
}