25. Maze¶
Swarm's insects flew wherever their curves took them. In Maze, nobody flies: the muncher and four ghosts walk the corridors of a maze, from tile to tile, and they can only turn where two corridors cross. The muncher eats the dots; the ghosts hunt it. Four large dots, the energizers, turn the tables for a few seconds: the ghosts turn blue and flee, and the muncher may eat them.
The original came from an arcade hall in 1980, and its ghosts are famous for seeming to think. They do not. Each one follows a rule of a single line, and the rules are cleverly different. This chapter builds the pieces that rule, and the ones that a real computer player needs: a map of tiles, walking on it, ghosts as state machines, and the search for a way through a maze, from breadth-first search to A*.
What you will learn
- Tile maps: a level as rows of letters in a text file, read with errors that name the line and the column
- Walking on a grid: from the centre of one tile to the next, turning only at centres, and keys that are kept until the way is open
- State machines: a ghost is always in exactly one mode, and a table says which changes are allowed
- Four characters from one rule: the tile each ghost aims at, and the greedy choice at every crossing
- Breadth-first search: a wave of distances from a goal, and the way home downhill from anywhere
- A*: the cheapest way, when some tiles cost more than others, and a computer player that fears the ghosts
- Autotiling: the picture of a wall from its neighbours, sixteen pieces from four bits
The complete game is in amade-maze-game.
The rules¶
- The maze is 27 tiles wide and 30 high. The muncher walks its corridors; the arrow keys choose the way at the next crossing. Back the way it came works at once.
- A dot is worth 10 points, an energizer 50. When all 240 are eaten, the next level begins, a little faster.
- Four ghosts hunt the muncher, each in its own way. They leave their house in the middle one after the other. Now and then they all scatter to their own corners for a few seconds, then hunt again.
- A ghost that touches the muncher costs a life. Three lives, and an extra one at 10,000 points.
- After an energizer the ghosts turn blue for six seconds, fewer in later levels: they are slow and wander aimlessly. A blue ghost touched is eaten, for 200, 400, 800 and 1,600 points one after the other. Its eyes fly back to the house, and it comes out again.
- Twice a level, after 70 and 170 dots, a fruit appears below the house for a few seconds: a cherry worth 100 points in the first level, more in later ones.
- At both ends of the middle row, a tunnel leads to the other side. Ghosts are slow in it; the muncher is not.
Step 1: A map of tiles¶
Every game so far had its own grid: the cells of Mines, the bricks of Bricks, the field of Snake. Maze needs one with more in it, and so will Blast, Jump, Towers and Sands, so the grid moves into the engine. A TileMap is columns and rows of tiles, each holding one value, usually an enum:
public final class TileMap<T> {
private final int width;
private final int height;
private final Object[] tiles;
public TileMap(int width, int height, T fill) {
if (width <= 0 || height <= 0) throw new IllegalArgumentException("empty map");
this.width = width;
this.height = height;
this.tiles = new Object[width * height];
Arrays.fill(tiles, fill);
}
public int width() {
return width;
}
public int height() {
return height;
}
public boolean contains(int col, int row) {
return col >= 0 && col < width && row >= 0 && row < height;
}
@SuppressWarnings("unchecked")
public T get(int col, int row) {
return (T) tiles[index(col, row)];
}
public void set(int col, int row, T tile) {
tiles[index(col, row)] = tile;
}
private int index(int col, int row) {
if (!contains(col, row)) {
throw new IndexOutOfBoundsException("(" + col + ", " + row + ") is outside " + width + " × " + height);
}
return row * width + col;
}
/** The cell one step from {@code col}, {@code row}: over an edge, it is on the far side. */
public Cell step(int col, int row, Direction direction) {
return new Cell(Math.floorMod(col + direction.dx, width), Math.floorMod(row + direction.dy, height));
}
step makes the map a field without edges, like the field of Rocks: a step over the right edge arrives on the left. A maze with walls all round never notices. A row that has no wall at its ends becomes a tunnel, without a line of code for it.
The maze is a text file¶
Chapter 24 put the stages of Swarm into a text file; a maze belongs in one even more, because it can be drawn as text. One letter per tile, one line per row:
row XXXXXXXXXXXXXXXXXXXXXXXXXXX
row X............X............X
row X.XXXX.XXXXX.X.XXXXX.XXXX.X
row XoXXXX.XXXXX.X.XXXXX.XXXXoX
...
row XXXXXX.XX_XXX-XXX_XX.XXXXXX
row XXXXXX.XX_XHHHHHX_XX.XXXXXX
row TTTTTT.___XHHHHHX___.TTTTTT
...
muncher 13 22 left
ghost red 13 11 left
ghost pink 13 14 up
corner red 24 -3
release cyan 5
fruit 13 16
X is a wall, . a dot, o an energizer, _ an empty floor, T the tunnel, - the door of the ghosts' house and H its inside. # would have been the obvious letter for a wall, but TextData reads everything after a # as a comment. The maze is 27 tiles wide, an odd number on purpose: the middle column is a whole column, so the door, the house and the muncher's start lie on it, not between two.
The engine reads the rows; the game says what the letters mean:
/**
* Reads a map from lines such as {@code row X..X}: the second word of each line is a row, one letter per
* tile, and {@code legend} says what each letter stands for. All rows must be equally long. An error
* names the line and the column, as {@code maze.txt:7: column 12: 'Q' is not a tile}.
*/
public static <T> TileMap<T> read(List<TextData.Line> rows, Map<Character, T> legend) {
if (rows.isEmpty()) throw new IllegalArgumentException("a map needs at least one row");
int width = rows.getFirst().word(1).length();
TileMap<T> map = new TileMap<>(width, rows.size(), null);
for (int row = 0; row < rows.size(); row++) {
TextData.Line line = rows.get(row);
String text = line.word(1);
if (line.size() > 2) throw line.error("a row is one word, without spaces");
if (text.length() != width) {
throw line.error("the row has " + text.length() + " tiles, the first has " + width);
}
for (int col = 0; col < width; col++) {
T tile = legend.get(text.charAt(col));
if (tile == null) throw line.error("column " + col + ": '" + text.charAt(col) + "' is not a tile");
map.set(col, row, tile);
}
}
return map;
}
@Test
void aMapIsReadFromRowsOfLetters() {
TileMap<Tile> map = map("""
row XXXXX
row X._.X
row XXXXX
""");
assertEquals(5, map.width());
assertEquals(3, map.height());
assertEquals(Tile.DOT, map.get(1, 1));
assertEquals(Tile.FLOOR, map.get(2, 1));
assertEquals(2, map.count(t -> t == Tile.DOT));
assertEquals(List.of(new Cell(1, 1), new Cell(3, 1)), map.cells(t -> t == Tile.DOT));
}
@Test
void aWrongLetterOrALengthIsAnErrorNamingTheLine() {
var unknown = assertThrows(TextData.DataException.class, () -> map("""
row XXXXX
# a comment line still counts
row X.Q.X
"""));
assertEquals("test.txt:3: column 2: 'Q' is not a tile", unknown.getMessage());
var length = assertThrows(TextData.DataException.class, () -> map("row XXXXX\nrow XXXX\n"));
assertEquals("test.txt:2: the row has 4 tiles, the first has 5", length.getMessage());
}
Maze reads the rest of the file and checks what a maze needs to be playable. The last check is the interesting one: every dot must be reachable from the muncher's start, or the level can never be cleared. It uses breadth-first search, which comes in step 5; for now it is enough that a dot walled off by a slip of the keyboard is found at once:
/** Reads a maze; every mistake is an error that names the file and the line. */
public static Maze read(List<TextData.Line> lines) {
List<TextData.Line> rows = new ArrayList<>();
Start muncher = null;
Map<Kind, Start> ghosts = new EnumMap<>(Kind.class);
Map<Kind, Cell> corners = new EnumMap<>(Kind.class);
Map<Kind, Double> release = new EnumMap<>(Kind.class);
Cell fruit = null;
List<TextData.Line> places = new ArrayList<>();
for (TextData.Line line : lines) {
switch (line.keyword()) {
case "row" -> rows.add(line);
case "muncher" -> {
muncher = new Start(cell(line, 1), direction(line, 3));
places.add(line);
}
case "ghost" -> {
ghosts.put(kind(line), new Start(cell(line, 2), direction(line, 4)));
places.add(line);
}
case "corner" -> corners.put(kind(line), cell(line, 2));
case "release" -> release.put(kind(line), line.number(2));
case "fruit" -> {
fruit = cell(line, 1);
places.add(line);
}
default -> throw line.error("\"" + line.keyword() + "\" is not a line of a maze");
}
}
TileMap<Tile> tiles = TileMap.read(rows, Tile.LEGEND);
TextData.Line last = lines.getLast();
if (muncher == null) throw last.error("the muncher has no start");
if (fruit == null) throw last.error("the fruit has no place");
for (Kind kind : Kind.values()) {
if (!ghosts.containsKey(kind)) throw last.error("the " + name(kind) + " ghost has no start");
if (!corners.containsKey(kind)) corners.put(kind, ghosts.get(kind).cell());
release.putIfAbsent(kind, 0.0);
}
for (TextData.Line line : places) {
Cell at = line.keyword().equals("ghost") ? cell(line, 2) : cell(line, 1);
if (!tiles.contains(at.col(), at.row()) || tiles.get(at) == Tile.WALL) {
throw line.error("(" + at.col() + ", " + at.row() + ") is not inside the maze");
}
}
List<Cell> doors = tiles.cells(tile -> tile == Tile.DOOR);
if (doors.size() != 1) throw rows.getFirst().error("a maze needs one door, not " + doors.size());
Cell door = doors.getFirst();
if (!tiles.get(door.next(Direction.UP)).corridor() || tiles.get(door.next(Direction.DOWN)) != Tile.HOUSE) {
throw rows.get(door.row()).error("the door needs a corridor above it and the house below");
}
// Every dot must be reachable, or a level can never be cleared.
DistanceMap reach = DistanceMap.search(tiles, (col, row) -> tiles.get(col, row).corridor(), muncher.cell());
for (Cell dot : tiles.cells(Tile::food)) {
if (reach.distance(dot) == DistanceMap.UNREACHABLE) {
throw rows.get(dot.row()).error("column " + dot.col() + ": the muncher cannot reach this dot");
}
}
return new Maze(tiles, muncher, ghosts, corners, release, fruit, door);
}
@Test
void mistakesInTheFileNameTheLine() {
assertEquals("maze.txt:10: \"blue\" is not a ghost (red, pink, cyan, orange)",
assertThrows(TextData.DataException.class, () -> read(SMALL.replace("ghost pink", "ghost blue")))
.getMessage());
assertEquals("maze.txt:9: (0, 0) is not inside the maze",
assertThrows(TextData.DataException.class, () -> read(SMALL.replace("red 4 1", "red 0 0")))
.getMessage());
assertEquals("maze.txt:2: column 4: the muncher cannot reach this dot",
assertThrows(TextData.DataException.class, () -> read(SMALL.replace("Xo.....oX", "Xo.X.X.oX")))
.getMessage(), "walled off: this level could never be cleared");
}
Each level plays on a copy of the tiles (maze.tiles()), from which the muncher eats the dots; the next level gets a fresh copy with all its dots.
Step 2: Walking on a grid¶
Snake jumped from cell to cell. The muncher must glide, at 7.6 tiles a second, and still keep to the corridors exactly: a muncher half a tile into a wall, because a key came a moment late, looks broken. The rule that makes both possible is old: positions are in tiles, and turns happen only at the centre of a tile. The centre of the tile in column 3, row 5 is the point (3, 5); halfway to the right of it is (3.5, 5). Between two centres, a walker can only go on, or turn round.
The four ways get an enum of their own. Its order matters, as we will see with the ghosts: when two ways are equally good, the first one wins.
public enum Direction {
UP(0, -1), LEFT(-1, 0), DOWN(0, 1), RIGHT(1, 0);
/** One step in this direction, in columns and rows; rows count downwards, as on the screen. */
public final int dx;
public final int dy;
Direction(int dx, int dy) {
this.dx = dx;
this.dy = dy;
}
public Direction opposite() {
return switch (this) {
case UP -> DOWN;
case LEFT -> RIGHT;
case DOWN -> UP;
case RIGHT -> LEFT;
};
}
public boolean horizontal() {
return dx != 0;
}
/** The angle on the screen, for drawing: 0 to the right, π/2 downwards. */
public double angle() {
return Math.atan2(dy, dx);
}
}
A Walker moves a distance along its heading. Whenever it reaches a centre on the way, it asks a Steering which way to go on; it does not know about walls, keys or targets itself. A step of 1/120 second covers less than a tenth of a tile, but the eyes of an eaten ghost are fast, and a long step at a slow frame must not skip a centre, so the walk goes centre by centre:
public final class Walker {
/** The decision at the centre of a tile. */
@FunctionalInterface
public interface Steering {
/**
* The way to go on from the centre of {@code col}, {@code row}, walking in {@code heading} so far
* ({@code null} if standing); {@code null} to stop here. Only return ways that are open.
*/
Direction choose(int col, int row, Direction heading);
}
private double x;
private double y;
private double previousX;
private double previousY;
/** The way it walks; {@code null} while it stands at a centre. */
private Direction heading;
public Walker(double x, double y, Direction heading) {
place(x, y, heading);
}
/**
* Walks {@code distance} tiles, asking {@code steering} at every centre it reaches, and returns the
* distance actually walked: less if it stopped. Steps over an edge of the map arrive on the far side.
*/
public double walk(double distance, TileMap<?> map, Steering steering) {
previousX = x;
previousY = y;
double left = distance;
while (left > 0) {
if (atCentre()) {
heading = steering.choose(col(), row(), heading);
if (heading == null) break;
}
boolean horizontal = heading.horizontal();
int sign = heading.dx + heading.dy;
double along = horizontal ? x : y;
// The next centre ahead: the next whole number in the walking direction.
double centre = sign > 0 ? Math.floor(along) + 1 : Math.ceil(along) - 1;
double gap = Math.abs(centre - along);
double step = Math.min(gap, left);
double now = step == gap ? centre : along + sign * step;
if (horizontal) x = now;
else y = now;
left -= step;
wrap(map.width(), map.height());
}
return distance - left;
}
The arithmetic of "the next centre ahead" is one line: moving towards larger numbers, it is the next whole number above; moving towards smaller ones, the next below. Arriving there, the position is set to that whole number exactly, so no rounding error can pile up over a game.
@Test
void aWalkerTurnsOnlyAtTheCentreOfATile() {
Walker walker = new Walker(1, 1, Direction.RIGHT);
walker.walk(1.5, MAP, wanting(Direction.DOWN));
assertEquals(2.5, walker.x(), 1e-9, "no way down at column 2: on to the right");
assertEquals(1, walker.y());
walker.walk(1.0, MAP, wanting(Direction.DOWN));
assertEquals(3, walker.x(), 1e-9, "at the centre of column 3 it turned");
assertEquals(1.5, walker.y(), 1e-9);
assertEquals(Direction.DOWN, walker.heading());
assertEquals(1.5, walker.walk(5, MAP, wanting(Direction.DOWN)), 1e-9, "a wall: it stops after 1.5");
assertEquals(3, walker.y());
assertNull(walker.heading());
}
@Test
void turningRoundNeedsNoCentre() {
Walker walker = new Walker(1, 1, Direction.RIGHT);
walker.walk(0.3, MAP, wanting(null));
walker.turnAround();
walker.walk(0.5, MAP, wanting(null));
assertEquals(0.8, walker.x(), 1e-9);
assertEquals(Direction.LEFT, walker.heading());
}
Through the tunnel, the walker leaves at one edge and arrives at the other. Its previous position moves with it, so drawing between two steps still sees a short step, not a jump back across the screen; the painter clips the maze, and the muncher disappears into the tunnel and comes out of the other side.
A key that waits¶
The player's steering is where the game becomes pleasant to play. Nobody can press a key at the exact moment the muncher passes a crossing. So the wanted way is kept: at every centre, the muncher takes it if it is open, else goes on, else stops at the wall. Only the opposite way is taken at once, between centres too:
/** One step: {@code wanted} is the way the player asks for, {@code null} for none. */
void move(double distance, TileMap<Tile> tiles, Direction wanted) {
this.tiles = tiles;
this.wanted = wanted;
if (wanted != null && walker.heading() == wanted.opposite()) walker.turnAround();
walked += walker.walk(distance, tiles, steering);
if (walker.heading() != null) facing = walker.heading();
}
/** At a centre: the wanted way if it is open, else on, else stop at the wall. */
private Direction choose(int col, int row, Direction heading) {
if (wanted != null && open(col, row, wanted)) return wanted;
if (heading != null && open(col, row, heading)) return heading;
return null;
}
private boolean open(int col, int row, Direction way) {
return tiles.get(tiles.step(col, row, way)).corridor();
}
@Test
void theMuncherEatsTheDotsItPasses() {
seconds(0.25, null);
assertEquals(List.of(new Event.DotEaten(new Cell(12, 22)), new Event.DotEaten(new Cell(11, 22))),
events(Event.DotEaten.class), "left from the start, one dot per tile");
assertEquals(2 * Field.DOT_POINTS, game.score());
assertEquals(Tile.FLOOR, game.tiles().get(12, 22));
assertEquals(238, game.dotsLeft());
}
@Test
void aKeyPressedEarlyIsKeptUntilTheWayIsOpen() {
// At the start, up is a wall; one tile to the left, the way up opens, and the muncher takes it.
seconds(0.1, Direction.UP);
assertEquals(Direction.LEFT, game.muncher().walker().heading());
seconds(0.3, Direction.UP);
assertEquals(12, game.muncher().walker().col());
assertEquals(Direction.UP, game.muncher().walker().heading());
}
In the scene, the last arrow key pressed is the wanted way, and it stays until another is pressed or a new round begins:
/**
* A game. The last arrow key pressed is the way the player wants to go; the muncher takes it at the
* next crossing where it is open, so a key may come a little early.
*/
final class PlayScene implements Scene {
private final Game game = new Game(seeds.getAsLong());
private Direction wanted;
PlayScene() {
effects.clear();
effects.react(game.events(), true); // "Ready!" and the tune
}
@Override
public void update(double seconds) {
if (controls.wasPressed(Action.PAUSE)) {
scenes.push(new PauseScene());
return;
}
// The first four actions are the directions, in the same order.
for (Direction d : Direction.values()) {
if (controls.wasPressed(Action.values()[d.ordinal()])) wanted = d;
}
game.update(seconds, wanted);
effects.react(game.events(), true);
effects.update(seconds);
for (Event event : game.events()) {
if (event instanceof Event.Ready) wanted = null; // a new round: forget the old key
if (event instanceof Event.GameOver(GameResult result)) {
scenes.replace(new OverScene(game, result));
// The presenter lives on the Swing thread: hand the result over there.
Consumer<GameResult> listener = onGameOver;
ui.execute(() -> listener.accept(result));
}
}
}
@Test
void aKeyIsKeptUntilTheMuncherCanTurn() {
MazeGame.PlayScene play = play();
seconds(Field.FIRST_READY_SECONDS + 0.05);
assertEquals(Game.Phase.PLAYING, play.game().phase());
tap(KeyEvent.VK_UP); // up is a wall at the start: the key waits
assertEquals(Direction.UP, play.wanted());
assertEquals(Direction.LEFT, play.game().muncher().walker().heading());
seconds(0.3);
assertEquals(Direction.UP, play.game().muncher().walker().heading(), "up at the next crossing");
assertEquals(12, play.game().muncher().walker().col());
}
Step 3: Ghosts as state machines¶
A ghost waits in the house, bobbing up and down. It leaves through the door. Outside, it scatters to its corner or hunts the muncher, by turns. After an energizer it is blue, and if it is eaten, its eyes fly home and go back into the house, from where it leaves again. Seven modes, and the rules of each are different: how fast it walks, how it chooses its way, whether it is dangerous.
Swarm solved a similar problem with components: an insect was what it had. A ghost is simpler, and stricter: it is always in exactly one mode, and only some changes make sense. Eaten while already flying home? Blue while still in the house? Such combinations are the classic bugs of this kind of game, and they show up as strange sights minutes later. A finite state machine writes the allowed changes down, as a table, and refuses everything else at once:
stateDiagram-v2
direction LR
[*] --> HOUSE
HOUSE --> LEAVING
LEAVING --> SCATTER
LEAVING --> CHASE
LEAVING --> FRIGHTENED
SCATTER --> CHASE
CHASE --> SCATTER
SCATTER --> FRIGHTENED
CHASE --> FRIGHTENED
FRIGHTENED --> SCATTER
FRIGHTENED --> CHASE
FRIGHTENED --> EATEN
EATEN --> ENTERING
ENTERING --> LEAVINGpublic final class StateMachine<S extends Enum<S>> {
private final Map<S, EnumSet<S>> allowed;
private S state;
private S previous;
private double seconds;
private BiConsumer<S, S> onChange = (from, to) -> { };
public StateMachine(S initial) {
this.allowed = new EnumMap<>(initial.getDeclaringClass());
this.state = initial;
this.previous = initial;
}
/** Allows the changes from {@code from} to each of {@code to}. */
@SafeVarargs
public final StateMachine<S> allow(S from, S... to) {
EnumSet<S> targets = allowed.computeIfAbsent(from, s -> EnumSet.noneOf(s.getDeclaringClass()));
for (S s : to) targets.add(s);
return this;
}
/** Called after each change with the old and the new state: to start a sound, turn round, reset a timer. */
public StateMachine<S> onChange(BiConsumer<S, S> listener) {
this.onChange = listener;
return this;
}
public boolean canChange(S to) {
EnumSet<S> targets = allowed.get(state);
return targets != null && targets.contains(to);
}
/** Changes to {@code to}, which must be allowed from the current state. */
public void to(S to) {
if (!canChange(to)) throw new IllegalStateException("not allowed: " + state + " → " + to);
previous = state;
state = to;
seconds = 0;
onChange.accept(previous, to);
}
/** Lets time pass in the current state. */
public void update(double seconds) {
this.seconds += seconds;
}
@Test
void onlyTheAllowedChangesHappen() {
List<String> changes = new ArrayList<>();
StateMachine<Mode> ghost = new StateMachine<>(Mode.WAIT)
.allow(Mode.WAIT, Mode.HUNT)
.allow(Mode.HUNT, Mode.FLEE)
.allow(Mode.FLEE, Mode.HUNT, Mode.HOME)
.allow(Mode.HOME, Mode.WAIT)
.onChange((from, to) -> changes.add(from + " → " + to));
ghost.to(Mode.HUNT);
ghost.update(2.5);
assertEquals(2.5, ghost.seconds(), "time in the state");
ghost.to(Mode.FLEE);
assertEquals(0, ghost.seconds(), "a new state starts at zero");
assertEquals(Mode.HUNT, ghost.previous());
ghost.to(Mode.HOME);
assertFalse(ghost.canChange(Mode.FLEE));
var error = assertThrows(IllegalStateException.class, () -> ghost.to(Mode.FLEE));
assertEquals("not allowed: HOME → FLEE", error.getMessage(), "eaten twice: a bug, found at once");
assertTrue(ghost.is(Mode.HOME));
assertEquals(List.of("WAIT → HUNT", "HUNT → FLEE", "FLEE → HOME"), changes);
}
The ghost's table is the diagram above, written in Java:
/** What a ghost is doing. */
public enum Mode {
/** Waiting in the house, bobbing up and down. */
HOUSE,
/** On its way out of the house, to the tile in front of the door. */
LEAVING,
/** Off to its own corner of the maze. */
SCATTER,
/** Hunting the muncher, each ghost in its own way. */
CHASE,
/** Blue after an energizer: slow, aimless, and good to eat. */
FRIGHTENED,
/** Eaten: only the eyes are left, and they fly home. */
EATEN,
/** The eyes go through the door into the house, to come back to life. */
ENTERING
}
private final StateMachine<Mode> mode = new StateMachine<>(Mode.HOUSE)
.allow(Mode.HOUSE, Mode.LEAVING)
.allow(Mode.LEAVING, Mode.SCATTER, Mode.CHASE, Mode.FRIGHTENED)
.allow(Mode.SCATTER, Mode.CHASE, Mode.FRIGHTENED)
.allow(Mode.CHASE, Mode.SCATTER, Mode.FRIGHTENED)
.allow(Mode.FRIGHTENED, Mode.SCATTER, Mode.CHASE, Mode.EATEN)
.allow(Mode.EATEN, Mode.ENTERING)
.allow(Mode.ENTERING, Mode.LEAVING)
.onChange(this::changed);
The listener does one thing, and it is a piece of game design from the original: a hunting ghost that changes its mind turns round at once. Everywhere else a ghost may never turn back, so a sudden turn of all four is a signal the player learns to read: the ghosts just changed from scattering to hunting, or an energizer took effect.
/** A hunting ghost that changes its mind turns round at once: the player sees the change coming. */
private void changed(Mode from, Mode to) {
boolean roaming = from == Mode.SCATTER || from == Mode.CHASE;
if (roaming && to != Mode.EATEN) walker.turnAround();
}
Scatter and chase¶
Who decides when the ghosts scatter? A schedule, the same for all, counted from the start of the round. While the energizer works, the schedule waits:
/**
* Seconds of scattering and hunting, by turns: scatter 7, hunt 20, scatter 7, hunt 20, scatter 5, hunt 20,
* scatter 5, then hunt until the end of the round. Scattering gives the player room to breathe.
*/
static final double[] SCHEDULE = {7, 20, 7, 20, 5, 20, 5};
/** Scatter and chase by turns; while the energizer works, the schedule waits. */
private void schedule(double seconds) {
if (frightLeft > 0) {
frightLeft -= seconds;
if (frightLeft <= 0) {
frightLeft = 0;
for (Ghost ghost : ghosts.values()) ghost.follow(scheduled());
events.add(new Event.FrightOver());
}
return;
}
scheduleTime += seconds;
if (scheduleStep < Field.SCHEDULE.length && scheduleTime >= Field.SCHEDULE[scheduleStep]) {
scheduleStep++;
scheduleTime = 0;
for (Ghost ghost : ghosts.values()) ghost.follow(scheduled());
}
}
/** What the ghosts outside should be doing now: even steps of the schedule scatter, odd ones chase. */
Ghost.Mode scheduled() {
return scheduleStep % 2 == 0 && scheduleStep < Field.SCHEDULE.length ? Ghost.Mode.SCATTER : Ghost.Mode.CHASE;
}
@Test
void theGhostsLeaveTheHouseOneAfterTheOtherAndScatterThenHunt() {
seconds(0.5, null);
assertEquals(Ghost.Mode.LEAVING, game.ghost(Kind.PINK).mode(), "pink at once");
assertEquals(Ghost.Mode.HOUSE, game.ghost(Kind.CYAN).mode());
seconds(5, null);
assertEquals(Ghost.Mode.LEAVING, game.ghost(Kind.CYAN).mode(), "cyan after five seconds");
assertEquals(Ghost.Mode.SCATTER, game.ghost(Kind.RED).mode());
game.putMuncher(13, 22, null); // out of harm's way, for the test
for (int i = 0; i < 2 * 120 && game.ghost(Kind.RED).mode() == Ghost.Mode.SCATTER; i++) {
Direction before = game.ghost(Kind.RED).walker().heading();
steps(1, null);
if (game.ghost(Kind.RED).mode() == Ghost.Mode.CHASE) {
assertEquals(before.opposite(), game.ghost(Kind.RED).walker().heading(), "the turn shows the change");
}
}
assertEquals(Ghost.Mode.CHASE, game.ghost(Kind.RED).mode(), "after seven seconds the hunt begins");
}
The speed depends on the mode too, and in the hunting modes on the tile: the tunnel slows the ghosts down, which makes it the muncher's escape route.
/** How fast a ghost walks now, in tiles per second. */
double speed(Ghost ghost) {
double pace = Field.pace(level);
return switch (ghost.mode()) {
case HOUSE, LEAVING -> Field.HOUSE_SPEED;
case EATEN, ENTERING -> Field.EYES_SPEED;
case FRIGHTENED -> Field.FRIGHTENED_SPEED * pace;
case SCATTER, CHASE -> tiles.get(ghost.walker().cell()) == Tile.TUNNEL
? Field.TUNNEL_SPEED * pace : Field.GHOST_SPEED * pace;
};
}
/** Speeds in the first level, in tiles per second; later levels are faster. */
public static final double MUNCHER_SPEED = 7.6;
public static final double GHOST_SPEED = 7.2;
/** Blue ghosts are slow, and so is everybody in the tunnel, except the muncher. */
public static final double FRIGHTENED_SPEED = 4.4;
public static final double TUNNEL_SPEED = 3.8;
/** The eyes of an eaten ghost fly home fast. */
public static final double EYES_SPEED = 14;
/** Waiting in the house, bobbing up and down, and leaving it. */
public static final double HOUSE_SPEED = 3.2;
Step 4: Four characters, one rule¶
Here is how a ghost chooses its way. At the centre of a tile, it looks at the open ways except back, and takes the one whose next tile is nearest to its target tile, as the crow flies. That is all. It does not search the maze, it does not plan; it is greedy, and it can be fooled by a wall between it and its target.
/** At the centre of a tile: which way now? */
private Direction choose(int col, int row, Direction heading) {
Cell here = new Cell(col, row);
return switch (mode.state()) {
case HOUSE -> bob(col, row, heading);
case LEAVING -> {
if (!here.equals(maze.doorstep())) yield maze.toDoorstep().downhill(col, row);
// Out of the house while the others are blue: blue too. Back to life after being eaten: not.
boolean blue = game.frightened() && mode.previous() == Mode.HOUSE;
mode.to(blue ? Mode.FRIGHTENED : game.scheduled());
yield Direction.LEFT;
}
case EATEN -> {
if (!here.equals(maze.doorstep())) yield maze.toDoorstep().downhill(col, row);
mode.to(Mode.ENTERING);
yield Direction.DOWN;
}
case ENTERING -> {
if (!here.equals(maze.house())) yield maze.toHouse().downhill(col, row);
mode.to(Mode.LEAVING);
yield maze.toDoorstep().downhill(col, row);
}
case FRIGHTENED -> wander(col, row, heading);
case SCATTER -> towards(col, row, heading, corner());
case CHASE -> towards(col, row, heading, kind.target(game, this));
};
}
/**
* The rule of the arcade: never back the way it came; of the other open ways, the one whose next tile is
* nearest to the target, as the crow flies. Of equally near ones, the first of up, left, down, right.
*/
private Direction towards(int col, int row, Direction heading, Cell target) {
Direction best = null;
long bestDistance = Long.MAX_VALUE;
for (Direction d : Direction.values()) {
if (heading != null && d == heading.opposite()) continue;
Cell next = game.tiles().step(col, row, d);
if (!game.tiles().get(next).corridor()) continue;
long distance = distanceSquared(next, target);
if (distance < bestDistance) {
best = d;
bestDistance = distance;
}
}
return best != null ? best : heading.opposite(); // a dead end: the only way is back
}
The modes differ only in what happens at a centre. In the house the ghost bobs between the walls. Leaving, flying home and entering, it follows a way found once for the whole maze (step 5). Blue, it takes a random open way. Scattering, its target is its own corner, which lies outside the maze, so it never arrives and circles the block nearest to it. Hunting, the target depends on the ghost, and this is where the characters come from:
public enum Kind {
/** Goes straight for the muncher. */
RED,
/** Aims four tiles ahead of the muncher, to cut it off. */
PINK,
/** Aims past the muncher, as far again as the red ghost is from a point two tiles ahead of it. */
CYAN,
/** Hunts like red while far away, but runs to its corner when it comes within eight tiles. */
ORANGE;
/** The tile this ghost aims at while it hunts. */
Cell target(Game game, Ghost self) {
Muncher muncher = game.muncher();
Cell at = muncher.walker().cell();
Direction facing = muncher.facing();
return switch (this) {
case RED -> at;
case PINK -> ahead(at, facing, 4);
case CYAN -> {
Cell pivot = ahead(at, facing, 2);
Cell red = game.ghost(RED).walker().cell();
yield new Cell(2 * pivot.col() - red.col(), 2 * pivot.row() - red.row());
}
case ORANGE -> Ghost.distanceSquared(self.walker().cell(), at) > 8 * 8 ? at : self.corner();
};
}
private static Cell ahead(Cell at, Direction facing, int tiles) {
return new Cell(at.col() + facing.dx * tiles, at.row() + facing.dy * tiles);
}
}
The red ghost follows the muncher. The pink one aims four tiles ahead of it, so it comes from the front and the two of them close in from both sides. The cyan one uses red's position: it takes the point two tiles ahead of the muncher and doubles the way from red to that point, so it is dangerous when red is near and wanders when red is far. The orange one hunts like red, but as soon as it comes within eight tiles, it turns to its corner, so it seems to lose interest.
@Test
void eachGhostAimsAtATileOfItsOwn() {
Game game = new Game(1);
game.putMuncher(13, 22, Direction.LEFT);
game.putGhost(Kind.RED, 13, 11, Direction.LEFT, Ghost.Mode.CHASE);
game.putGhost(Kind.ORANGE, 25, 1, Direction.LEFT, Ghost.Mode.CHASE);
assertEquals(new Cell(13, 22), Kind.RED.target(game, game.ghost(Kind.RED)), "the muncher itself");
assertEquals(new Cell(9, 22), Kind.PINK.target(game, game.ghost(Kind.PINK)), "four tiles ahead of it");
// Two tiles ahead is (11, 22); red is 11 tiles above that, so cyan aims 11 tiles below it.
assertEquals(new Cell(9, 33), Kind.CYAN.target(game, game.ghost(Kind.CYAN)));
assertEquals(new Cell(13, 22), Kind.ORANGE.target(game, game.ghost(Kind.ORANGE)), "far away: hunts");
game.putGhost(Kind.ORANGE, 13, 19, Direction.LEFT, Ghost.Mode.CHASE);
assertEquals(new Cell(0, 31), Kind.ORANGE.target(game, game.ghost(Kind.ORANGE)), "close: off to its corner");
}
@Test
void atACrossingAGhostTakesTheWayNearestItsTargetButNeverBack() {
Game game = new Game(1);
game.skipReady();
game.putMuncher(6, 22, null);
// At (6, 5) the ways lead up, down and right; left is back. The muncher is far below.
game.putGhost(Kind.RED, 6, 5, Direction.RIGHT, Ghost.Mode.CHASE);
game.update(STEP, null);
assertEquals(Direction.DOWN, game.ghost(Kind.RED).walker().heading());
// In its corner up right while scattering, the same ghost at the same crossing goes up.
game.putGhost(Kind.RED, 6, 5, Direction.RIGHT, Ghost.Mode.SCATTER);
game.update(STEP, null);
assertEquals(Direction.RIGHT, game.ghost(Kind.RED).walker().heading(), "towards (24, -3): right is nearer than up");
}
Behind the scenes: why the ghosts do not search
A ghost with A* (step 6) would always find the shortest way to the muncher, and four of them would trap it in a few seconds. The greedy rule is weaker on purpose. It makes mistakes the player can learn and use: a ghost on the other side of a wall goes the wrong way, a ghost aiming ahead of the muncher can be led past it, the orange one always gives up. Good game characters are not the cleverest possible; they are the ones whose behaviour a person can read. In the original, pink's rule had a small slip: facing up, it aimed four tiles up and four to the left, from an overflow in the arcade's arithmetic. Players have used it for forty years. Ours aims straight.
Step 5: Breadth-first search, the way home¶
An eaten ghost's eyes must fly back to the door of the house, from wherever they are, by a shortest way. The greedy rule would get them lost behind walls. What they need is a real search, and the simplest one is breadth-first search: start at the goal with distance 0; give each open neighbour distance 1; give each of their unvisited open neighbours distance 2; and so on, a wave that spreads through the corridors until it has filled them all. It is the flood fill of chapter 10, with a counter.
public final class DistanceMap {
/** The distance of a tile no way leads to. */
public static final int UNREACHABLE = Integer.MAX_VALUE;
private final int width;
private final int height;
private final int[] distance;
private int visited;
private DistanceMap(int width, int height) {
this.width = width;
this.height = height;
this.distance = new int[width * height];
Arrays.fill(distance, UNREACHABLE);
}
/** The distances to the nearest of {@code goals} over the tiles {@code open} lets one enter. */
public static DistanceMap search(TileMap<?> map, Passable open, Cell... goals) {
DistanceMap result = new DistanceMap(map.width(), map.height());
int[] queue = new int[map.width() * map.height()];
int head = 0;
int tail = 0;
for (Cell goal : goals) {
int index = goal.row() * map.width() + goal.col();
if (result.distance[index] == UNREACHABLE) {
result.distance[index] = 0;
queue[tail++] = index;
}
}
while (head < tail) {
int index = queue[head++];
int col = index % map.width();
int row = index / map.width();
for (Direction d : Direction.values()) {
Cell next = map.step(col, row, d);
int n = next.row() * map.width() + next.col();
if (result.distance[n] != UNREACHABLE || !open.test(next.col(), next.row())) continue;
result.distance[n] = result.distance[index] + 1;
queue[tail++] = n;
}
}
result.visited = tail;
return result;
}
The queue is an array of tile numbers, as in Mines: head is where the wave is, tail where it will be. Each tile goes into the queue once, so the search takes as many steps as there are tiles, 291 corridors here, a few microseconds.
The result answers the question for every tile at once, and that is its strength. Search once, from the goal, and from anywhere the way home is simply downhill: to the neighbour with the smaller number.
/**
* The first step from {@code col}, {@code row} on a shortest way to a goal: towards the neighbour with
* the smallest distance. {@code null} at a goal, or where no way leads. Of equally good steps, the first
* in the order of {@link Direction} wins.
*/
public Direction downhill(int col, int row) {
int here = distance(col, row);
Direction best = null;
int bestDistance = here;
for (Direction d : Direction.values()) {
int next = distance(Math.floorMod(col + d.dx, width), Math.floorMod(row + d.dy, height));
if (next < bestDistance) {
best = d;
bestDistance = next;
}
}
return best;
}
@Test
void theWaveCountsTheStepsToTheGoalFromEveryTile() {
DistanceMap home = DistanceMap.search(MAZE, DistanceMapTest::open, new Cell(4, 3));
assertEquals(0, home.distance(4, 3));
assertEquals(2, home.distance(3, 2));
assertEquals(3, home.distance(3, 1), "down and round the corner");
assertEquals(5, home.distance(7, 1), "round the wall, not through it");
assertEquals(9, home.distance(1, 5));
assertEquals(DistanceMap.UNREACHABLE, home.distance(3, 7), "walled in");
// Downhill from anywhere is a shortest way home.
Cell at = new Cell(0, 5);
int steps = 0;
for (Direction d; (d = home.downhill(at.col(), at.row())) != null; steps++) at = MAZE.step(at.col(), at.row(), d);
assertEquals(new Cell(4, 3), at);
assertEquals(home.distance(0, 5), steps);
assertNull(home.downhill(3, 7));
}
The maze never changes, so the maps for the eyes are made once, when the maze is read. A ghost flying home may pass the door, so walls are all that stop the wave:
// A ghost flying home may pass the door, and nothing stops it but walls.
this.toDoorstep = DistanceMap.search(tiles, (col, row) -> tiles.get(col, row) != Tile.WALL, doorstep);
this.toHouse = DistanceMap.search(tiles, (col, row) -> tiles.get(col, row) != Tile.WALL, house);
Four ghosts, three uses: the eyes go downhill to the doorstep, then down the second map into the house; and a ghost leaving the house goes downhill to the doorstep too, the same map as the eyes.
@Test
void anEnergizerTurnsTheHuntersBlueAndTheyAreWorthMoreAndMore() {
game.putMuncher(3, 22, Direction.LEFT);
game.putGhost(Kind.RED, 20, 28, Direction.LEFT, Ghost.Mode.CHASE);
seconds(0.3, null);
assertEquals(List.of(new Event.EnergizerEaten(new Cell(1, 22), 6)), events(Event.EnergizerEaten.class));
assertEquals(Ghost.Mode.FRIGHTENED, game.ghost(Kind.RED).mode());
assertEquals(Direction.RIGHT, game.ghost(Kind.RED).walker().heading(), "turned round at once");
assertEquals(Ghost.Mode.HOUSE, game.ghost(Kind.ORANGE).mode(), "still waiting in the house");
// Two blue ghosts walk into the muncher.
game.putMuncher(4, 28, Direction.RIGHT);
game.putGhost(Kind.RED, 7, 28, Direction.LEFT, Ghost.Mode.FRIGHTENED);
game.putGhost(Kind.PINK, 10, 28, Direction.LEFT, Ghost.Mode.FRIGHTENED);
seconds(1.5, null);
assertEquals(List.of(200, 400), events(Event.GhostEaten.class).stream().map(Event.GhostEaten::points).toList());
assertTrue(game.ghost(Kind.RED).eyes());
}
@Test
void theEyesFlyHomeAndTheGhostComesOutAgain() {
game.putMuncher(1, 25, Direction.RIGHT);
game.putGhost(Kind.RED, 25, 28, Direction.LEFT, Ghost.Mode.FRIGHTENED);
game.ghost(Kind.RED).eaten();
List<Ghost.Mode> modes = new ArrayList<>();
for (int i = 0; i < 12 * 120 && game.ghost(Kind.RED).mode() != Ghost.Mode.SCATTER; i++) {
steps(1, null);
Ghost.Mode mode = game.ghost(Kind.RED).mode();
if (modes.isEmpty() || modes.getLast() != mode) modes.add(mode);
}
assertEquals(List.of(Ghost.Mode.EATEN, Ghost.Mode.ENTERING, Ghost.Mode.LEAVING, Ghost.Mode.SCATTER), modes);
assertEquals(new Cell(13, 11), game.ghost(Kind.RED).walker().cell(), "out of the door");
}
Step 6: A*, the computer player¶
The title screen needs a player. Its first question is "where is the nearest dot?", and breadth-first search answers it: one wave from the muncher's tile, then the dot with the smallest number. Nearest by steps, not as the crow flies; in a maze, the dot behind the wall is far away.
The second question is harder: "how do I get there without meeting a ghost?" All steps are no longer equal. A step next to a hunting ghost is a bad step, and a longer way round may be better. Breadth-first search cannot weigh steps; it only counts them. The algorithm for this is A* (Hart, Nilsson and Raphael, 1968), and it is the most used search in games.
A* keeps a border of tiles it has reached, and always continues from the most promising one: the tile with the smallest g + h, where g is the cost of the way to it so far, and h a guess of the cost still to come. The guess is the number of steps if there were no walls, the Manhattan distance. Two properties make it work. Every tile costs at least 1, so the guess is never too high; a search with such a guess finds a cheapest way, always. And the guess pulls the search towards the goal: where breadth-first search spreads evenly in all directions, A* reaches out in the direction of the goal and only spreads where walls force it to.
public static Path find(TileMap<?> map, Cell from, Cell to, Cost cost) {
int width = map.width();
int size = width * map.height();
double[] g = new double[size];
Arrays.fill(g, Double.POSITIVE_INFINITY);
int[] cameFrom = new int[size];
Direction[] cameBy = new Direction[size];
boolean[] closed = new boolean[size];
// The border of the search, cheapest g + h first; of equal ones, the one nearer the goal.
PriorityQueue<Open> border = new PriorityQueue<>((a, b) -> a.f() != b.f()
? Double.compare(a.f(), b.f()) : Double.compare(a.h(), b.h()));
int start = from.row() * width + from.col();
int goal = to.row() * width + to.col();
g[start] = 0;
border.add(new Open(start, guess(map, from, to), guess(map, from, to)));
int visited = 0;
while (!border.isEmpty()) {
int index = border.poll().index();
if (closed[index]) continue; // an older, dearer entry of a tile seen again
closed[index] = true;
visited++;
if (index == goal) return path(map, cameFrom, cameBy, start, goal, g[goal], visited);
int col = index % width;
int row = index / width;
for (Direction d : Direction.values()) {
Cell next = map.step(col, row, d);
int n = next.row() * width + next.col();
if (closed[n]) continue;
double through = g[index] + cost.enter(next.col(), next.row());
if (through >= g[n]) continue; // no better than a way known already (or a wall)
g[n] = through;
cameFrom[n] = index;
cameBy[n] = d;
double h = guess(map, next, to);
border.add(new Open(n, through + h, h));
}
}
return new Path(List.of(), List.of(), Double.POSITIVE_INFINITY, visited);
}
/** The steps without walls, across and along, the short way round over the edges. Never too many. */
static double guess(TileMap<?> map, Cell a, Cell b) {
int dx = Math.abs(a.col() - b.col());
int dy = Math.abs(a.row() - b.row());
return Math.min(dx, map.width() - dx) + Math.min(dy, map.height() - dy);
}
Three details. The border is a PriorityQueue, so taking the cheapest tile costs a logarithm, not a look at all of them. A tile can be reached a second time by a cheaper way; instead of finding and changing its old entry, the search adds a new one and skips the old one when it comes up (closed). And of two tiles with the same g + h, the one nearer to the goal goes first, which saves a lot of work in corridors where many ways are equally long.
@Test
void aStarFindsAShortestWayAndLooksAtFewerTiles() {
Cell from = new Cell(1, 1);
Cell to = new Cell(7, 1);
AStar.Path path = AStar.find(MAZE, from, to, AStarTest::steps);
DistanceMap wave = DistanceMap.search(MAZE, DistanceMapTest::open, to);
assertEquals(wave.distance(from), path.cost(), "as short as breadth-first search finds");
assertEquals(path.steps().size() + 1, path.cells().size());
assertEquals(from, path.cells().getFirst());
assertEquals(to, path.cells().getLast());
assertEquals(Direction.RIGHT, path.first());
assertTrue(path.visited() < wave.visited(), path.visited() + " tiles against " + wave.visited());
}
@Test
void dangerMakesTheLongerWayCheaper() {
// Through the tunnel, or along the row: the row is shorter, but a ghost sits in it.
Cell from = new Cell(2, 5);
Cell to = new Cell(6, 5);
assertEquals(Direction.RIGHT, AStar.find(MAZE, from, to, AStarTest::steps).first());
AStar.Path safe = AStar.find(MAZE, from, to, (col, row) ->
col == 4 && row == 5 ? 50 : steps(col, row));
assertEquals(Direction.LEFT, safe.first(), "the long way round, over the edge");
assertEquals(List.of(new Cell(2, 5), new Cell(1, 5), new Cell(0, 5), new Cell(8, 5), new Cell(7, 5),
new Cell(6, 5)), safe.cells());
}
How much does the guess save? From the muncher's start, measured:
| Goal | Steps | Breadth-first search looks at | A* looks at |
|---|---|---|---|
| (20, 22), on the same row | 7 | 291 tiles | 8 tiles |
| (6, 19), up and left | 10 | 291 | 11 |
| (25, 28), the corner down right | 18 | 291 | 22 |
| (1, 1), the far corner | 33 | 291 | 149 |
Breadth-first search always fills the whole maze; that is what makes its one search good for every tile. A* looks at little more than the way itself when the way is direct, and at half the maze when the walls send it round. Both take microseconds here. On the maps of Towers and Sands, with thousands of tiles and hundreds of units, the difference decides whether the game runs at all.
The pilot¶
Each time the muncher reaches a new tile, the pilot makes a plan: the goal by breadth-first search, the way by A*, with tiles near hunting ghosts made expensive. The corridor in front of a ghost costs too, because that is where it is going:
/** The way the pilot wants to go in this step. */
public Direction steer(Game game, double seconds) {
distracted -= seconds;
if (distracted <= 0 && random.nextDouble() < DISTRACTIONS * seconds) distracted = DISTRACTION;
if (game.phase() != Game.Phase.PLAYING) {
planned = null;
return null;
}
Cell at = game.muncher().walker().cell();
if (!at.equals(planned)) {
planned = at;
way = plan(game, at);
}
return way;
}
private Direction plan(Game game, Cell at) {
TileMap<Tile> tiles = game.tiles();
wave = DistanceMap.search(tiles, (col, row) -> tiles.get(col, row).corridor(), at);
Cell goal = goal(game, wave);
if (goal == null) return null;
boolean careful = distracted <= 0;
path = AStar.find(tiles, at, goal, (col, row) -> {
if (!tiles.get(col, row).corridor()) return Double.POSITIVE_INFINITY;
return careful ? 1 + danger(game, col, row) : 1;
});
return path.first();
}
/** A blue ghost nearby while the blue lasts; else the nearest dot, by the steps to it. */
private static Cell goal(Game game, DistanceMap wave) {
Cell best = null;
int bestDistance = DistanceMap.UNREACHABLE;
if (game.frightLeft() > 2) {
for (Ghost ghost : game.ghosts()) {
if (ghost.mode() != Ghost.Mode.FRIGHTENED) continue;
Cell cell = ghost.walker().cell();
int distance = wave.distance(cell);
if (distance <= HUNT_RANGE && distance < bestDistance) {
best = cell;
bestDistance = distance;
}
}
if (best != null) return best;
}
for (Cell dot : game.tiles().cells(Tile::food)) {
int distance = wave.distance(dot);
if (distance < bestDistance) {
best = dot;
bestDistance = distance;
}
}
return best;
}
/**
* The cost of being near a hunting ghost: high next to it, less two or three tiles away, and the
* corridor ahead of it, where it is going, costs too.
*/
public static double danger(Game game, int col, int row) {
double cost = 0;
TileMap<Tile> tiles = game.tiles();
for (Ghost ghost : game.ghosts()) {
if (!ghost.dangerous()) continue;
Cell at = ghost.walker().cell();
int dx = Math.abs(at.col() - col);
dx = Math.min(dx, tiles.width() - dx);
int steps = dx + Math.abs(at.row() - row);
if (steps <= 1) cost += NEAR;
else if (steps <= 3) cost += CLOSE;
Direction heading = ghost.walker().heading();
if (heading == null) continue;
for (int i = 0; i < AHEAD && tiles.get(at = tiles.step(at.col(), at.row(), heading)).corridor(); i++) {
if (at.col() == col && at.row() == row) cost += CLOSE;
}
}
return cost;
}
The pilot is not good. It sees danger only a few tiles away, and the pink and cyan ghosts, which come from the front, catch it between two of them. It also looks away now and then, as in Swarm. It clears the first level in about half its games and loses its last life within two minutes, which is what the title screen needs:
@Test
void thePilotClearsALevelAndLosesItsLivesInTheEnd() {
int best = 0;
int levels = 0;
int ended = 0;
for (long seed = 1; seed <= 5; seed++) {
Game game = new Game(seed);
Pilot pilot = new Pilot(game.seed());
for (int i = 0; i < 10 * 60 * 120 && game.phase() != Game.Phase.OVER; i++) {
game.update(STEP, pilot.steer(game, STEP));
}
System.out.println("seed " + seed + ": " + game.score() + " points, level " + game.level() + ", " + game.phase());
if (game.phase() == Game.Phase.OVER) ended++;
best = Math.max(best, game.score());
levels = Math.max(levels, game.level());
}
assertTrue(best >= 5000, "best " + best);
assertTrue(levels >= 2, "reached level " + levels);
assertEquals(5, ended, "every game ends within ten minutes, so the title shows the end too");
}
Step 7: Eating and meeting¶
The game's step puts the pieces together. The muncher walks and eats; then it meets the ghosts; then the ghosts walk; then it meets them again:
/** One step of {@code seconds}; {@code wanted} is the way the player asks for, {@code null} for none. */
public void update(double seconds, Direction wanted) {
events.clear();
phaseTime += seconds;
switch (phase) {
case READY -> {
if (phaseTime >= readySeconds()) phase(Phase.PLAYING);
}
case PLAYING -> play(seconds, wanted);
case DYING -> {
if (phaseTime >= Field.DYING_SECONDS) loseLife();
}
case CLEARED -> {
if (phaseTime >= Field.CLEARED_SECONDS) {
level++;
startLevel(false);
}
}
case OVER -> {
}
}
}
private void play(double seconds, Direction wanted) {
if (pause > 0) {
pause -= seconds;
return;
}
roundTime += seconds;
schedule(seconds);
muncher.move(Field.MUNCHER_SPEED * Field.pace(level) * seconds, tiles, wanted);
eat();
if (meet()) return;
for (Ghost ghost : ghosts.values()) ghost.update(seconds, this);
if (meet()) return;
fruit(seconds);
if (dotsLeft == 0) {
phase(Phase.CLEARED);
events.add(new Event.LevelCleared(level));
}
}
Eating is a look at the muncher's tile, the nearest centre. An energizer starts the blue time and resets the points for ghosts to 200:
/** What lies on the muncher's tile is eaten. */
private void eat() {
Cell at = muncher.walker().cell();
Tile tile = tiles.get(at);
if (tile.food()) {
tiles.set(at.col(), at.row(), Tile.FLOOR);
dotsLeft--;
dotsEaten++;
if (tile == Tile.DOT) {
addPoints(Field.DOT_POINTS);
events.add(new Event.DotEaten(at));
} else {
addPoints(Field.ENERGIZER_POINTS);
frightLeft = Field.frightened(level);
ghostsEaten = 0;
for (Ghost ghost : ghosts.values()) ghost.frighten();
events.add(new Event.EnergizerEaten(at, frightLeft));
}
for (int after : Field.FRUIT_AFTER) {
if (dotsEaten == after && fruitsShown < Field.FRUIT_AFTER.length) {
fruitsShown++;
fruit = Fruit.of(level);
fruitLeft = Field.FRUIT_SECONDS;
events.add(new Event.FruitShown(fruit));
}
}
}
if (fruit != null && at.equals(maze.fruit())) {
addPoints(fruit.points);
events.add(new Event.FruitEaten(fruit, at, fruit.points));
fruit = null;
}
}
Why meet twice? The muncher and a ghost walking towards each other close the gap by 15 tiles a second together, an eighth of a tile per step. Tested only after both moved, they could be 0.55 tiles apart before the step and 0.55 tiles apart the other way round after it, and pass through each other. Tested after each one moves, the gap is never more than one walker's step:
/**
* The muncher meets the ghosts near it: a blue one is eaten, a hunting one catches it. Tested before and
* after the ghosts move, so two that walk towards each other never pass through each other.
*/
private boolean meet() {
double mx = muncher.walker().x();
double my = muncher.walker().y();
for (Ghost ghost : ghosts.values()) {
double dx = Math.abs(ghost.walker().x() - mx);
dx = Math.min(dx, tiles.width() - dx); // through the tunnel too
double dy = ghost.walker().y() - my;
if (dx * dx + dy * dy >= Field.CATCH_DISTANCE * Field.CATCH_DISTANCE) continue;
if (ghost.mode() == Ghost.Mode.FRIGHTENED) {
int points = Field.GHOST_POINTS << Math.min(ghostsEaten, 3);
ghostsEaten++;
ghost.eaten();
addPoints(points);
pause = Field.EATEN_PAUSE;
events.add(new Event.GhostEaten(ghost.kind(), ghost.walker().x(), ghost.walker().y(), points));
} else if (ghost.dangerous()) {
phase(Phase.DYING);
events.add(new Event.Caught(mx, my));
return true;
}
}
return false;
}
@Test
void aHuntingGhostCatchesTheMuncherAndTheRoundStartsAgain() {
game.putMuncher(4, 28, Direction.RIGHT);
game.putGhost(Kind.RED, 7, 28, Direction.LEFT, Ghost.Mode.CHASE);
seconds(0.5, null);
assertEquals(1, events(Event.Caught.class).size());
assertEquals(Game.Phase.DYING, game.phase());
seconds(Field.DYING_SECONDS + 0.1, null);
assertEquals(Game.Phase.READY, game.phase());
assertEquals(Field.START_LIVES - 1, game.lives());
assertEquals(new Cell(13, 22), game.muncher().walker().cell(), "back at the start");
assertEquals(Ghost.Mode.HOUSE, game.ghost(Kind.PINK).mode());
}
The rest is as in the earlier games: the rules report events, and the same seed plays the same game:
public sealed interface Event {
/** A level begins, or a round after a lost life: "Ready!". */
record Ready(int level, boolean newGame) implements Event {
}
record DotEaten(Cell at) implements Event {
}
/** The ghosts turn blue for so many seconds. */
record EnergizerEaten(Cell at, double seconds) implements Event {
}
/** The ghosts are no longer blue. */
record FrightOver() implements Event {
}
/** The muncher ate a blue ghost; its eyes fly home. */
record GhostEaten(Kind kind, double x, double y, int points) implements Event {
}
record FruitShown(Fruit fruit) implements Event {
}
record FruitEaten(Fruit fruit, Cell at, int points) implements Event {
}
/** A ghost caught the muncher. */
record Caught(double x, double y) implements Event {
}
record LevelCleared(int level) implements Event {
}
record ExtraLife(int lives) implements Event {
}
record GameOver(GameResult result) implements Event {
}
}
@Test
void theSameSeedPlaysTheSameGame() {
Game a = new Game(7);
Game b = new Game(7);
Pilot pa = new Pilot(7);
Pilot pb = new Pilot(7);
for (int i = 0; i < 90 * 120; i++) {
a.update(STEP, pa.steer(a, STEP));
b.update(STEP, pb.steer(b, STEP));
}
assertEquals(a.score(), b.score());
assertEquals(a.muncher().walker().x(), b.muncher().walker().x());
assertEquals(a.ghost(Kind.CYAN).walker().y(), b.ghost(Kind.CYAN).walker().y());
}
Step 8: Drawing the maze¶
The maze has 459 wall tiles. Drawn as 459 blue squares, it looks like a spreadsheet. Arcade mazes are drawn as outlines: thin walls with rounded corners, the corridors between them wider than the walls. The picture of a wall tile depends on its neighbours: a wall with neighbours left and right is a straight horizontal piece, one with neighbours right and below is a corner, one alone is a pillar. Four neighbours, each a wall or not: four bits, sixteen pieces. Choosing the piece from the bits is called autotiling, and the engine computes the bits:
/**
* Which of the four neighbours {@code same} accepts, as four bits: 1 up, 2 left, 4 down, 8 right (the
* bit of a {@link Direction} is {@code 1 << ordinal}). Neighbours outside the map count as {@code outside}.
* Sixteen values, one per shape a wall piece can take: the classic way to choose the picture of a tile
* from its neighbours, called <i>autotiling</i>.
*/
public int mask(int col, int row, Predicate<? super T> same, boolean outside) {
int mask = 0;
for (Direction d : Direction.values()) {
int c = col + d.dx;
int r = row + d.dy;
boolean match = contains(c, r) ? same.test(get(c, r)) : outside;
if (match) mask |= 1 << d.ordinal();
}
return mask;
}
@Test
void theMaskSaysWhichNeighboursAreWalls() {
TileMap<Tile> map = map("""
row XXX_
row X.X_
row X___
""");
// Up 1, left 2, down 4, right 8.
assertEquals(8 | 4, map.mask(0, 0, t -> t == Tile.WALL, false), "a corner: right and down");
assertEquals(2 | 4, map.mask(2, 0, t -> t == Tile.WALL, false), "a corner: left and down");
assertEquals(1, map.mask(2, 1, t -> t == Tile.WALL, false), "the end of a wall: only up");
assertEquals(1 | 4, map.mask(0, 1, t -> t == Tile.WALL, false), "a straight piece, up and down");
assertEquals(1 | 2 | 4 | 8, map.mask(0, 0, t -> t == Tile.WALL, true), "outside counts as wall here");
}
A game with tile pictures would now pick one of sixteen images per wall. Ours draws them as shapes: each piece is a small square with arms, and all pieces together become one Java2D Area, which merges them into the outline of every wall. Where four walls form a block, the gap between their arms is filled, so thick walls are solid:
/**
* The walls as one shape, in tiles. Each wall tile is a square smaller than the tile, with an arm
* towards each neighbour that is a wall too, as {@link TileMap#mask} tells; where four walls meet in a
* block, the gap between their arms is filled. All pieces together, made into one {@link Area}, give
* the outline of every wall, with the corridors wider than the walls.
*/
static Shape wallShape(Maze maze) {
TileMap<Tile> tiles = maze.tiles();
Path2D.Double pieces = new Path2D.Double();
double a = INSET;
double b = 1 - INSET;
double e = 0.01; // pieces overlap a little: shapes that only touch may keep a seam
for (int row = 0; row < tiles.height(); row++) {
for (int col = 0; col < tiles.width(); col++) {
if (tiles.get(col, row) != Tile.WALL) continue;
int mask = tiles.mask(col, row, tile -> tile == Tile.WALL, false);
pieces.append(new Rectangle2D.Double(col + a, row + a, b - a, b - a), false);
if ((mask & 1) != 0) pieces.append(new Rectangle2D.Double(col + a, row - e, b - a, a + 2 * e), false);
if ((mask & 2) != 0) pieces.append(new Rectangle2D.Double(col - e, row + a, a + 2 * e, b - a), false);
if ((mask & 4) != 0) pieces.append(new Rectangle2D.Double(col + a, row + b - e, b - a, a + 2 * e), false);
if ((mask & 8) != 0) pieces.append(new Rectangle2D.Double(col + b - e, row + a, a + 2 * e, b - a), false);
// Right, down and the tile diagonally between them are walls: a block, no gap at the corner.
boolean block = (mask & 8) != 0 && (mask & 4) != 0 && tiles.get(col + 1, row + 1) == Tile.WALL;
if (block) pieces.append(new Rectangle2D.Double(col + b - e, row + b - e, 2 * a + 2 * e, 2 * a + 2 * e), false);
}
}
return new Area(pieces);
}
Merging a thousand rectangles into one shape takes a moment, about 20 milliseconds; that happens once, when the game starts. Drawing the shape with its outline, antialiased, at full screen size would cost several milliseconds in every frame, so the walls are a Sprite drawn in code, cached at the screen's size as in chapter 21. A second sprite has white edges, for the flashing of a cleared maze. The dots are drawn every frame, as small squares without antialiasing (chapter 24 showed what antialiasing costs for straight edges):
/** @param alpha how far the time is between the last two update steps, 0 to 1 */
void paint(Graphics2D g, Game game, Effects effects, double alpha) {
Object smoothing = g.getRenderingHint(RenderingHints.KEY_ANTIALIASING);
g.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_OFF);
g.setColor(Color.BLACK);
g.fill(screen);
boolean flashing = game.phase() == Game.Phase.CLEARED && (int) (game.phaseTime() * 4) % 2 == 1;
(flashing ? flash : walls).draw(g, left, top);
dots(g, game, effects);
g.setRenderingHint(RenderingHints.KEY_ANTIALIASING, smoothing);
Shape clip = g.getClip();
g.clip(field); // the tunnel's ends: whoever goes in disappears at the edge
if (game.fruit() != null) {
fruits[game.fruit().ordinal()].draw(g, x(game.maze().fruit().col()) - ACTOR / 2,
y(game.maze().fruit().row()) - ACTOR / 2);
}
boolean ghostsShown = switch (game.phase()) {
case READY, PLAYING -> true;
case DYING -> game.phaseTime() < 0.5;
case CLEARED, OVER -> false;
};
if (ghostsShown) {
for (Ghost ghost : game.ghosts()) drawGhost(g, game, ghost, effects, alpha);
}
drawMuncher(g, game, alpha);
g.setClip(clip);
}
The muncher and the ghosts are sprites drawn in code too: the muncher in four directions with four mouth openings, a ghost body in two skirt positions, and the eyes, which look where the ghost goes, as a sprite of their own on top. An eaten ghost is only eyes:
/** A ghost's body by its mode, its skirt waving, and its eyes looking where it goes. */
private void drawGhost(Graphics2D g, Game game, Ghost ghost, Effects effects, double alpha) {
Walker walker = ghost.walker();
double x = x(between(walker.previousX(), walker.x(), alpha)) - ACTOR / 2;
double y = y(between(walker.previousY(), walker.y(), alpha)) - ACTOR / 2;
int skirt = (int) (effects.time() * 8) % 2;
if (ghost.mode() == Ghost.Mode.FRIGHTENED) {
boolean flashing = game.frightLeft() < Field.FLASH_SECONDS && (int) (effects.time() * 6) % 2 == 0;
(flashing ? white : blue)[skirt].draw(g, x, y);
return;
}
if (!ghost.eyes()) bodies[ghost.kind().ordinal()][skirt].draw(g, x, y);
Direction looking = walker.heading() != null ? walker.heading() : Direction.UP;
eyes[looking.ordinal()].draw(g, x, y);
}
The mouth opens and closes with the distance walked, not with the time: a muncher stopped at a wall keeps its mouth still. Score, level, lives and the fruit of the level are the overlay, left and right of the maze:
/** Score and level left and right of the maze, the lives and the level's fruit below them, the points. */
void status(Graphics2D g, Game game, Effects effects) {
double margin = painter.left;
g.setFont(label);
g.setColor(GOLD);
centred(g, msg.get("hud.score"), margin / 2, 40);
centred(g, msg.get("hud.level"), Field.WIDTH - margin / 2, 40);
g.setFont(score);
g.setColor(CHALK);
centred(g, msg.format("hud.points", game.score()), margin / 2, 64);
centred(g, msg.format("hud.points", game.level()), Field.WIDTH - margin / 2, 64);
int waiting = game.lives() - (game.phase() == Game.Phase.OVER ? 0 : 1);
for (int i = 0; i < waiting; i++) painter.life().draw(g, margin / 2 - 33 + i * 22, Field.HEIGHT - 40);
for (int level = Math.max(1, game.level() - 3); level <= game.level(); level++) {
painter.fruit(Fruit.of(level)).draw(g, Field.WIDTH - margin / 2 + 24 - (game.level() - level) * 22,
Field.HEIGHT - 40);
}
g.setFont(points);
g.setColor(CYAN);
for (int i = 0; i < Effects.LABELS; i++) {
double age = effects.time() - effects.labelTime[i];
if (age < 0 || age > Effects.LABEL_SECONDS) continue;
centred(g, Integer.toString(effects.labelPoints[i]), painter.x(effects.labelX[i]),
painter.y(effects.labelY[i]) + 4);
}
if (game.phase() == Game.Phase.READY) {
g.setFont(label);
g.setColor(GOLD);
centred(g, msg.get("play.ready"), Field.WIDTH / 2, painter.y(game.maze().fruit().row()) + 5);
}
}
Sounds and music come from the events, as in Swarm. The wail of blue ghosts is music: it loops on the mixer's music voice until the blue time ends.
/** Shows and, if {@code audible}, plays what happened in the last step; the music too. */
void react(List<Event> events, boolean audible) {
for (Event event : events) {
switch (event) {
case Event.Ready(int level, boolean newGame) -> {
if (audible && newGame) mixer.playMusic(music.start, false);
}
case Event.DotEaten dot -> {
munchUp = !munchUp;
if (audible) mixer.play(munchUp ? sounds.munchUp : sounds.munchDown);
}
case Event.EnergizerEaten energizer -> {
if (audible) {
mixer.play(sounds.energizer);
mixer.playMusic(music.frightened, true);
}
}
case Event.FrightOver over -> mixer.stopMusic();
case Event.GhostEaten(var kind, double x, double y, int points) -> {
label(x, y, points);
if (audible) mixer.play(sounds.ghostEaten);
}
case Event.FruitShown shown -> {
}
case Event.FruitEaten(var fruit, var at, int points) -> {
label(at.col(), at.row(), points);
if (audible) mixer.play(sounds.fruitEaten);
}
case Event.Caught caught -> {
mixer.stopMusic();
if (audible) mixer.play(sounds.caught);
}
case Event.LevelCleared cleared -> {
mixer.stopMusic();
if (audible) mixer.playMusic(music.cleared, false);
}
case Event.ExtraLife life -> {
if (audible) mixer.play(sounds.extraLife);
}
case Event.GameOver over -> {
if (audible) mixer.playMusic(music.over, false);
}
}
}
}
Full screen (F11), the render modes, the frame times (F12), sound, the best scores and the five languages work as in the earlier games, from the same engine classes.
What moved into the engine¶
| From Maze | Engine package | Why |
|---|---|---|
| Tile maps, read from text; the neighbour mask | eu.amadeos.gameengine.tile.TileMap, Cell, Direction |
Levels on a grid: Blast's arena, Jump's levels, the maps of Towers and Sands |
| Walking on a grid | eu.amadeos.gameengine.tile.Walker |
Anything that keeps to corridors and turns only at centres |
| State machines | eu.amadeos.gameengine.ai.StateMachine |
Enemies, units, doors, the phases of a game: anything that is in one state at a time |
| Breadth-first search | eu.amadeos.gameengine.path.DistanceMap |
One goal for many: the way home, flow fields for the units of Towers |
| A* | eu.amadeos.gameengine.path.AStar |
The cheapest way for one: computer players, units with costs per terrain |
What stays in the game: the tiles and their meaning, the maze file, the muncher, the ghosts' modes and targets, the schedule, the pilot, the painter, the sounds and tunes, and the scenes.
Exercises¶
- A maze of your own. Change
maze.txt: move walls, add a second tunnel, put the house elsewhere. Wall off a dot on purpose and read the error. - Pink's slip. Make the pink ghost aim four up and four left when the muncher faces up, as the original did. Can you lead it astray with that?
- Smart eyes, dumb ghosts. Give the red ghost A* towards the muncher instead of the greedy rule. Play a few rounds. Is the game better, or only harder?
- A better pilot. The pilot dies between two ghosts that come from both ends of a corridor. Make the cost of a tile grow with the number of ghosts that can reach it before the muncher can (one breadth-first search per ghost). How far does it get now?
- Count the work. Print
visited()of the pilot's searches during a game. When is A* close to breadth-first search, and why? - The original's dot counters. The arcade let the ghosts leave the house after a number of dots, not after seconds, and sent one out when the player stopped eating for four seconds. Build that, and compare how the start of a level feels.
In the next game, Blast, up to four players share one arena of tiles, with gamepads, and bombs whose flames run along the corridors: timers, events, and chain reactions.