45. Maps, Camera and Fog¶
From Maze on, the games of this book live on maps: a grid of tiles that the rules think in, and a picture of it that the drawing scales. This chapter covers the maps themselves, written as text or drawn in an editor, what spreads over them (land owned, services that reach, power that flows), the isometric view of a map, the camera that shows a part of a world larger than the screen, and what one side of a strategy game knows of the map: the fog of war and the minimap.
A grid of tiles: TileMap, Cell and Direction¶
Package tile · introduced in 25. Maze · source: TileMap, Cell, Direction
What it is for. Columns and rows of squares, each holding one value, usually an enum of the game such as WALL or DOT. The rules of a maze game, a puzzle or a strategy game live on such a map, in whole cells; only the drawing knows how many pixels a tile has. A Cell is a column and a row; a Direction is one of UP, LEFT, DOWN, RIGHT.
How it works. The map has no edges of its own: step(col, row, direction) over the right edge arrives at the left. A maze with walls all round never notices, and a row without walls at its ends becomes a tunnel from one side to the other (chapter 25). get and set outside the map are an error that names the cell and the map's size.
The order of Direction is a rule of its own: when two ways are equally good, the one listed first wins (up, left, down, right). A choice then never depends on chance or on the order of a loop somewhere else, and two runs of Maze with the same input are the same game.
| Method | What it does |
|---|---|
new TileMap<>(width, height, fill) |
A map filled with one value |
get(col, row), set(col, row, tile), contains(col, row) |
One tile |
step(col, row, direction) |
The neighbour, over the edge on the far side |
count(test), cells(test) |
How many tiles, and which: the dots still to eat |
copy() |
A fresh map for each level, all its dots in place |
mask(col, row, same, outside) |
Which neighbours belong together, as four bits: the picture of a wall piece |
TileMap.read(rows, legend) |
A map from the lines of a data file, a letter per tile |
Maps as text. TileMap.read takes lines such as row XX..XX from a TextData file, the second word of each a row, and a legend from letters to tiles. Every row must have the same length, and every letter must be in the legend; an error names the line and the column, as maze.txt:7: column 12: 'Q' is not a tile. Maze and Blast write their maps this way (chapter 25).
Pitfall: # is a comment
TextData drops everything after # on a line, so # cannot stand for a tile in a map written as text. Maze uses X for its walls.
Walls that join up. mask gives sixteen values, one per shape a wall piece can take: alone, an end, a corner, a straight piece, a T, a cross. Choosing a tile's picture from its neighbours this way is called autotiling, and it is how Maze draws its walls from one letter (chapter 25).
/**
* 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;
}
Walking corridors: Walker¶
Package tile · introduced in 25. Maze · source: Walker
What it is for. Something that walks the corridors of a tile map: the muncher and the ghosts of Maze, the bombers of Blast. It moves from the centre of one tile to the centre of the next, and only at a centre may it turn or stop, so it always stays in the middle of a corridor and never cuts a corner into a wall. Between two centres it can only go on, or turn round at once (turnAround).
When to choose it. For movement in four directions along corridors, the way of maze and arena games. Units of a strategy game that walk freely in eight directions follow a flow field instead; a body with gravity moves with a TileCollider.
How it works. Positions are in tiles: the centre of column 3, row 5 is (3, 5), and a walker halfway to the right of it is at (3.5, 5). walk(distance, map, steering) walks so many tiles and asks a Steering at every centre it reaches which way to go on. The steering knows the walls, the keys or the plan; the walker does not. The player's steering is a key that waits: a turn pressed before the corner is kept until the corner comes (chapter 25); a ghost's steering is its target and the rules of its mode.
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;
}
previousX() and previousY() are the position before the last walk, for drawing between steps; over an edge, both move to the far side together.
The land a side owns: Territory¶
Package tile · introduced in 32. Colony · source: Territory
What it is for. The land inside a border made of circles: the storehouse claims the land around it, every lookout tower more. A building may stand only inside. Claims overlap, and a tower that burns down gives back only what no other claim still holds.
When to choose it. For any land that is owned by being near something: a settlement's border, the reach of a city's services, the area a tower guards. Who sees what is a different question, answered by the fog of war.
How it works. Every tile counts the claims that hold it; it is inside while the count is above zero. release counts down, so nothing has to find out which other claim also covers a tile. A circle is dc² + dr² ≤ r² + r: with r² alone, single tiles stick out at the four ends. version counts the changes, so a picture of the border is made again only when it moved.
public final class Territory {
private record Claim(int col, int row, int radius) {
}
private final int cols;
private final int rows;
private final int[] claims;
private final Map<Integer, Claim> byId = new TreeMap<>();
private int version;
public Territory(int cols, int rows) {
this.cols = cols;
this.rows = rows;
this.claims = new int[cols * rows];
}
/** Claims every tile within {@code radius} of {@code col}, {@code row}, under the number {@code id}. */
public void claim(int id, int col, int row, int radius) {
if (byId.containsKey(id)) throw new IllegalArgumentException("claim " + id + " exists");
Claim claim = new Claim(col, row, radius);
byId.put(id, claim);
mark(claim, 1);
}
/** Gives back the land of claim {@code id}, where no other claim holds it. */
public void release(int id) {
Claim claim = byId.remove(id);
if (claim == null) throw new IllegalArgumentException("no claim " + id);
mark(claim, -1);
}
private void mark(Claim claim, int by) {
int r = claim.radius();
for (int row = Math.max(0, claim.row() - r); row <= Math.min(rows - 1, claim.row() + r); row++) {
for (int col = Math.max(0, claim.col() - r); col <= Math.min(cols - 1, claim.col() + r); col++) {
int dc = col - claim.col();
int dr = row - claim.row();
if (dc * dc + dr * dr <= r * r + r) claims[row * cols + col] += by;
}
}
version++;
}
public boolean inside(int col, int row) {
return col >= 0 && row >= 0 && col < cols && row < rows && claims[row * cols + col] > 0;
}
| Method | What it does |
|---|---|
claim(id, col, row, radius), release(id) |
Claims the land in a circle under a number; gives it back |
inside(col, row) |
True if any claim holds the tile |
border(col, row), border() |
A tile inside next to one outside; all of them, for the posts |
size(), has(id), ids() |
How much land; which claims there are, for saving |
version() |
Counts every change |
Places that reach a circle: Coverage¶
Package tile · introduced in 33. Town · source: Coverage
What it is for. How well the tiles of a map are served by places that reach a circle around them: schools, fire stations, water towers, parks. A tile knows how many places reach it, and how close the nearest one is, as a strength from 1 on the place itself to almost 0 at the edge of its reach.
When to choose it. When reach adds up or fades with distance: land value that rises near a park, happiness that counts how many homes a school reaches. When it only matters whether a tile is inside, and claims must be given back one by one, Territory fits better.
How it works. add walks the square around the circle and counts every tile whose middle lies within the radius, keeping the strongest strength. A strength cannot be taken back out of a maximum, so there is no remove: the game clears the coverage and adds every place again when something changed, or once a month. For a map of 64 × 64 tiles and a few dozen places that costs nothing.
public final class Coverage {
private final int cols;
private final int rows;
private final int[] counts;
private final float[] strengths;
public Coverage(int cols, int rows) {
if (cols <= 0 || rows <= 0) throw new IllegalArgumentException("empty map");
this.cols = cols;
this.rows = rows;
this.counts = new int[cols * rows];
this.strengths = new float[cols * rows];
}
/** Forgets every place. */
public void clear() {
Arrays.fill(counts, 0);
Arrays.fill(strengths, 0);
}
/** A place on tile {@code col}, {@code row} that reaches {@code radius} tiles around. */
public void add(int col, int row, double radius) {
add(col + 0.5, row + 0.5, radius);
}
/**
* A place whose middle is at {@code col}, {@code row} in tiles, which need not be the middle of a
* tile: a building of two tiles by two has its middle on the corner between them.
*/
public void add(double col, double row, double radius) {
int r = (int) Math.ceil(radius);
int c0 = Math.max(0, (int) Math.floor(col - r));
int c1 = Math.min(cols - 1, (int) Math.ceil(col + r));
int r0 = Math.max(0, (int) Math.floor(row - r));
int r1 = Math.min(rows - 1, (int) Math.ceil(row + r));
for (int y = r0; y <= r1; y++) {
for (int x = c0; x <= c1; x++) {
double distance = Math.hypot(x + 0.5 - col, y + 0.5 - row);
if (distance > radius) continue;
int i = y * cols + x;
counts[i]++;
float strength = (float) (1 - distance / (radius + 1));
if (strength > strengths[i]) strengths[i] = strength;
}
}
}
/** How many places reach a tile; 0 off the map. */
public int count(int col, int row) {
return contains(col, row) ? counts[row * cols + col] : 0;
}
/** True if any place reaches a tile. */
public boolean covered(int col, int row) {
return count(col, row) > 0;
}
/** How close the nearest place is: 1 on it, falling towards 0 at the edge of its reach, 0 out of reach. */
public double strength(int col, int row) {
return contains(col, row) ? strengths[row * cols + col] : 0;
}
| Method | What it does |
|---|---|
clear() |
Forgets all places |
add(col, row, radius) |
A place on a tile; add(double col, double row, radius) for the middle of a building of several tiles |
count(col, row), covered(col, row) |
How many places reach a tile; whether any does |
strength(col, row) |
1 on the place, falling towards 0 at the edge of its reach, 0 outside |
Networks that carry: SupplyGrid¶
Package tile · introduced in 33. Town · source: SupplyGrid
What it is for. A network of tiles that carries something from where it is made to where it is used: power from plants through lines and buildings to homes, water through pipes. Tiles that carry are conductors; some are sources that put an amount in, others loads that take an amount out.
When to choose it. Whenever something flows through what the player builds and runs short when there is too little: power, water, gas, data. Something carried by people or vehicles, one piece at a time, is a road network instead (RoadNetwork).
How it works. solve finds the networks, groups of conductors that touch along an edge (not across a corner), with a flood fill. In each network it serves the loads in the order a breadth-first flood from all its sources reaches them, until the network's sources run dry. So a town that builds more than its plant can feed loses power at the far end, where the player is looking, and not here and there at random. A load is served wholly or not at all; a load or source on a tile that does not conduct is made a conductor.
public final class SupplyGrid {
private final int cols;
private final int rows;
private final boolean[] conducts;
private final double[] sources;
private final double[] loads;
private final int[] network;
private final boolean[] supplied;
private final int[] queue;
private double supply;
private double demand;
private double served;
private int networks;
/** The networks with a source come first: numbers below this one. */
private int fed;
public SupplyGrid(int cols, int rows) {
if (cols <= 0 || rows <= 0) throw new IllegalArgumentException("empty map");
this.cols = cols;
this.rows = rows;
int n = cols * rows;
conducts = new boolean[n];
sources = new double[n];
loads = new double[n];
network = new int[n];
supplied = new boolean[n];
queue = new int[n];
}
/** Forgets every conductor, source and load. */
public void clear() {
Arrays.fill(conducts, false);
Arrays.fill(sources, 0);
Arrays.fill(loads, 0);
Arrays.fill(network, -1);
Arrays.fill(supplied, false);
supply = demand = served = 0;
networks = fed = 0;
}
/** A tile that carries. */
public void conductor(int col, int row) {
conducts[row * cols + col] = true;
}
/** A tile that puts {@code amount} into its network; added to what the tile puts in already. */
public void source(int col, int row, double amount) {
int i = row * cols + col;
conducts[i] = true;
sources[i] += amount;
}
/** A tile that takes {@code amount} out of its network; added to what the tile takes already. */
public void load(int col, int row, double amount) {
int i = row * cols + col;
conducts[i] = true;
loads[i] += amount;
}
/** Finds the networks and serves the loads, nearest to a source first. */
public void solve() {
Arrays.fill(network, -1);
Arrays.fill(supplied, false);
supply = demand = served = 0;
networks = fed = 0;
int n = cols * rows;
for (int i = 0; i < n; i++) {
supply += sources[i];
demand += loads[i];
}
// Each network with a source: flood from all its sources at once, serving loads as they are reached.
for (int start = 0; start < n; start++) {
if (sources[start] <= 0 || network[start] >= 0) continue;
int id = networks++;
double left = 0;
int head = 0;
int tail = 0;
// First the whole network, to know what its sources make...
queue[tail++] = start;
network[start] = id;
while (head < tail) {
int i = queue[head++];
left += sources[i];
tail = spread(i, id, tail);
}
// ...then from the sources outwards, in breadth-first order of distance from the nearest source.
int[] order = breadthFromSources(id, tail);
for (int k = 0; k < tail; k++) {
int i = order[k];
if (loads[i] <= 0) continue;
if (loads[i] <= left + 1e-9) {
left -= loads[i];
supplied[i] = true;
served += loads[i];
}
}
}
fed = networks;
// Networks without a source are networks too, for network().
for (int start = 0; start < n; start++) {
if (!conducts[start] || network[start] >= 0) continue;
int id = networks++;
int head = 0;
int tail = 0;
queue[tail++] = start;
network[start] = id;
while (head < tail) tail = spread(queue[head++], id, tail);
}
}
| Method | What it does |
|---|---|
clear(), then conductor, source, load |
Describes the network anew, once per survey |
solve() |
Finds the networks and serves the loads |
supplied(col, row) |
A load that got what it asked for |
connected(col, row) |
A tile in a network with a source, served or not: "no power" or "not enough power"? |
network(col, row), networks() |
Which network a tile belongs to, how many there are |
supply(), demand(), served() |
All sources, all loads, what was served: the numbers for the bar at the top |
Test: the far end goes dark first
@Test
void thePlantFeedsTheNearestHomesFirst() {
// A plant of 5 at the left end of a line of ten tiles, a home of 2 on every other tile.
SupplyGrid power = new SupplyGrid(12, 3);
power.clear();
for (int col = 0; col < 10; col++) power.conductor(col, 1);
power.source(0, 1, 5);
for (int col = 2; col < 10; col += 2) power.load(col, 1, 2);
power.solve();
assertTrue(power.supplied(2, 1));
assertTrue(power.supplied(4, 1));
assertFalse(power.supplied(6, 1), "5 feeds two homes of 2, not three");
assertFalse(power.supplied(8, 1));
assertTrue(power.connected(8, 1), "connected, but the plant is too small");
assertEquals(5, power.supply());
assertEquals(8, power.demand());
assertEquals(4, power.served());
}
Maps from an editor: TiledMap¶
Package tiled · introduced in 27. Jump · source: TiledMap, TiledObject, TiledProperties, TmxReader
What it is for. Levels drawn in Tiled, the free map editor, read from its own TMX format. A maze of 28 × 31 is fine as text; a level of 200 × 30 tiles in three layers, with enemies, coins and doors, wants to be painted with the tiles' pictures under the mouse. Jump, Towers and Sands draw their maps in Tiled.
When to choose it. When a map is large, has several layers, or has things placed freely on it. A small grid of a few kinds of tiles reads more easily as text, and can be changed in any editor.
What it reads. Orthogonal maps that are not infinite, with:
- tile layers: a grid of global tile ids (gids) per layer, 0 for empty, encoded as CSV or Base64, uncompressed, zlib or gzip. The top bits of a gid say whether the tile is flipped;
gid(col, row)takes them off,flips(col, row)gives them. - tilesets, in the map or in their own
.tsxfile next to it: an image cut into tiles, starting at afirstGid. A tile can have a class (in older Tiled versions a type), such assolidorcoin, properties and an animation. - object layers: things placed freely, start, enemies, the goal. Each
TiledObjecthas a class, a box in the map's pixels and properties. An object that shows a tile is placed by Tiled at its bottom left corner; the reader has already turned that into the top left, so all objects are alike. - properties on the map, the layers, the objects and the tiles, read with a fallback in the type the game expects:
string,number,integer,bool(true,yesor1). A map made before a property existed still works.
Errors name the file and the line, as in level1.tmx:12: ..., because the reader works element by element with SAX, which knows where it is.
/** The tile layer called {@code name}; an error naming the map if there is none. */
public TileLayer layer(String name) {
for (TileLayer layer : layers) {
if (layer.name().equals(name)) return layer;
}
throw new DataException(source + ": no tile layer \"" + name + "\"");
}
/** The objects of the object layer called {@code name}; an error naming the map if there is none. */
public List<TiledObject> objects(String name) {
for (ObjectGroup group : objectGroups) {
if (group.name().equals(name)) return group.objects();
}
throw new DataException(source + ": no object layer \"" + name + "\"");
}
/** The tileset a gid belongs to; empty for 0 or a gid of no set. */
public Optional<Tileset> tileset(int gid) {
int tile = gid & TILE_BITS;
for (Tileset set : tilesets) {
if (set.contains(tile)) return Optional.of(set);
}
return Optional.empty();
}
/** What the tileset says about a gid's tile; empty if it says nothing. */
public Optional<TileInfo> info(int gid) {
int tile = gid & TILE_BITS;
return tileset(tile).map(set -> set.tiles().get(tile - set.firstGid()));
}
/** The class of a gid's tile, such as {@code "solid"}; {@code ""} for none and for empty cells. */
public String type(int gid) {
return info(gid).map(TileInfo::type).orElse("");
}
/**
* A tile layer as a {@link TileMap} of the game's own tiles: {@code tiles} turns each gid (0 for an
* empty cell) into what the rules know, usually by its {@link #type class}.
*/
public <T> TileMap<T> tiles(String layer, IntFunction<T> tiles) {
TileLayer source = layer(layer);
TileMap<T> map = new TileMap<>(width, height, null);
for (int row = 0; row < height; row++) {
for (int col = 0; col < width; col++) map.set(col, row, tiles.apply(source.gid(col, row)));
}
return map;
}
From map to rules. The rules do not want gids. map.tiles("ground", gid -> ...) turns a layer into a TileMap of the game's own tiles, usually by the tile's class, and the objects of a layer become the game's things by their class (chapter 27). Whatever is only a picture stays in the drawing.
Test: a map with objects
@Test
void objectsHaveAClassABoxAndProperties() {
TiledMap map = TiledMap.load(TiledMapTest.class, "small.tmx");
List<TiledObject> things = map.objects("things");
assertEquals(3, things.size(), "the coin tile's collision box is no object of the map");
TiledObject start = things.get(0);
assertEquals("start", start.type());
assertEquals(16, start.centerX(), 1e-9);
TiledObject walker = things.get(1);
assertEquals("walker", walker.type(), "class, as Tiled 1.9 wrote it");
assertEquals("left", walker.properties().string("direction", "right"));
assertEquals("two\nlines", walker.properties().string("note", ""));
TiledObject coin = things.get(2);
assertEquals(2, coin.gid());
assertEquals(16, coin.y(), 1e-9, "a tile object stands on its y: turned into the top");
}
The isometric view: IsoProjection¶
Package iso · introduced in 33. Town · source: IsoProjection
What it is for. A tile map seen from a corner and from above: every square tile becomes a diamond twice as wide as high, and things on it show two walls and a roof. The rules stay flat and square, in the same tile units as every other map of the engine; only the drawing turns.
When to choose it. For city builders, strategy games and role-playing games where buildings should look like buildings. It costs more than a flat map in the drawing: things must be sorted (DepthSort), and the visible part of the map is no longer a rectangle of tiles.
How it works. A point of the world, height above the ground, lies at originX + (x − y) · halfWidth / tile, originY + (x + y) · halfHeight / tile − height of the picture, the plane in which the whole map is drawn. The camera moves over that picture as over any big world. The way back works for points on the ground, which is all a mouse click needs: col and row find the tile under a point of the picture.
public final class IsoProjection {
private final double tile;
private final double halfWidth;
private final double halfHeight;
private final double originX;
private final double originY;
private final int columns;
private final int rows;
private final double above;
private IsoProjection(double tile, double tileWidth, double tileHeight, double originX, double originY,
int columns, int rows, double above) {
if (tile <= 0 || tileWidth <= 0 || tileHeight <= 0) throw new IllegalArgumentException("empty tile");
this.tile = tile;
this.halfWidth = tileWidth / 2;
this.halfHeight = tileHeight / 2;
this.originX = originX;
this.originY = originY;
this.columns = columns;
this.rows = rows;
this.above = above;
}
/**
* The projection of a map of {@code columns} × {@code rows} tiles of {@code tile} world units, each
* drawn as a diamond of {@code tileWidth} × {@code tileHeight}, placed so that the whole map lies in the
* picture from (0, 0) to ({@link #width()}, {@link #height()}). The top corner of the map, tile (0, 0),
* sits {@code above} units below the top, so that the tallest building on it still fits.
*/
public static IsoProjection forMap(int columns, int rows, double tile, double tileWidth, double tileHeight,
double above) {
if (columns <= 0 || rows <= 0) throw new IllegalArgumentException("empty map");
return new IsoProjection(tile, tileWidth, tileHeight, rows * tileWidth / 2, above, columns, rows, above);
}
/**
* A projection with its world origin at {@code originX}, {@code originY} of the picture and no map
* around it: for drawing one building into a picture of its own, with (0, 0) at its top corner.
*/
public static IsoProjection at(double tile, double tileWidth, double tileHeight, double originX, double originY) {
return new IsoProjection(tile, tileWidth, tileHeight, originX, originY, 0, 0, 0);
}
/** Where a point of the world, {@code height} above the ground, lies in the picture. */
public double pictureX(double x, double y) {
return originX + (x - y) * halfWidth / tile;
}
public double pictureY(double x, double y, double height) {
return originY + (x + y) * halfHeight / tile - height;
}
/** The point of the ground that lies at a point of the picture: the way back, for the mouse. */
public double worldX(double pictureX, double pictureY) {
double across = (pictureX - originX) / halfWidth * tile; // x - y
double down = (pictureY - originY) / halfHeight * tile; // x + y
return (down + across) / 2;
}
public double worldY(double pictureX, double pictureY) {
double across = (pictureX - originX) / halfWidth * tile;
double down = (pictureY - originY) / halfHeight * tile;
return (down - across) / 2;
}
/** The column and row of the tile whose diamond holds a point of the picture; may lie off the map. */
public int col(double pictureX, double pictureY) {
return (int) Math.floor(worldX(pictureX, pictureY) / tile);
}
public int row(double pictureX, double pictureY) {
return (int) Math.floor(worldY(pictureX, pictureY) / tile);
}
The projection is affine, so it is also a transform for the graphics. Under ground(h) a rectangle of the world is drawn as the diamond it covers, at height h: lawns, roofs, shadows. Under frontWall(x, y) and sideWall(x, y) a wall is drawn as if it faced the viewer, with its windows and door, and Java2D shears it into place (chapter 33).
| Method | What it does |
|---|---|
IsoProjection.forMap(cols, rows, tile, tileWidth, tileHeight, above) |
The projection of a whole map, with room above it for the tallest building |
IsoProjection.at(tile, tileWidth, tileHeight, originX, originY) |
A projection without a map, for drawing one building into a picture of its own |
pictureX(x, y), pictureY(x, y, height) |
Where a point of the world lies in the picture |
worldX(px, py), worldY(px, py), col(px, py), row(px, py) |
The point of the ground, and the tile, under a point of the picture |
ground(height), frontWall(x, y), sideWall(x, y) |
Transforms for drawing flat things, front walls and side walls |
visible(left, top, width, height, margin) |
The columns and rows to look at for a view, with margin rows below it for tall things |
width(), height() |
The size of the picture of the whole map: the camera's world |
Tip: zoom with the camera's view
The camera works in the picture's units. A view drawn twice as large is a camera with half the view, drawn under g.scale(2, 2), with the mouse divided by 2 before the camera converts it. Sprites then cache themselves at the larger size, so the close view stays sharp (chapter 33).
Test: the way there and back
@Test
void aPointOfTheGroundGoesToThePictureAndBack() {
// 40 × 40 tiles of 16 units, diamonds of 32 × 16, 100 units of room above the map.
IsoProjection iso = IsoProjection.forMap(40, 40, 16, 32, 16, 100);
assertEquals(40 * 32, iso.width());
assertEquals(40 * 16 + 100, iso.height());
// The top corner of the map is in the middle at the top, below the room for towers.
assertEquals(640, iso.pictureX(0, 0));
assertEquals(100, iso.pictureY(0, 0, 0));
// One tile along x: half a diamond to the right and down; along y: to the left and down.
assertEquals(656, iso.pictureX(16, 0));
assertEquals(108, iso.pictureY(16, 0, 0));
assertEquals(624, iso.pictureX(0, 16));
// A height lifts the point straight up.
assertEquals(108 - 30, iso.pictureY(16, 0, 30));
// And back: the middle of tile (5, 7) is found in the middle of its diamond.
double x = iso.pictureX(5.5 * 16, 7.5 * 16);
double y = iso.pictureY(5.5 * 16, 7.5 * 16, 0);
assertEquals(5.5 * 16, iso.worldX(x, y), 1e-9);
assertEquals(7.5 * 16, iso.worldY(x, y), 1e-9);
assertEquals(5, iso.col(x, y));
assertEquals(7, iso.row(x, y));
}
What covers what: DepthSort¶
Package iso · introduced in 33. Town · source: DepthSort
What it is for. The order in which the things of an isometric view are drawn, so what stands in front covers what stands behind: the painter's algorithm for things of any size. For things of one tile, sorting by x + y would do; a building of three tiles by two breaks that rule, and a tree behind its end would be drawn over its wall.
How it works. Each thing is a footprint, a rectangle of the ground, and a box in the picture. A lies behind B if A ends before B begins along x, or along y. That rule only orders things that touch in the picture, so the sort compares only things whose boxes overlap, found by a sweep along the picture's x, and draws them in topological order, the smallest x + y first among those that are free. Things behind each other both ways, a cycle no order can draw right, fall back to x + y. sorted() empties the sort for the next frame and reuses its objects.
public final class DepthSort<T> {
private static final class Item<T> {
double x0, y0, x1, y1;
double left, top, right, bottom;
double key;
int index;
T thing;
int[] after = new int[4]; // the items that must be drawn after this one
int afterCount;
int before; // how many items must be drawn before this one
}
private final List<Item<T>> items = new ArrayList<>();
private final List<Item<T>> spare = new ArrayList<>();
private Item<T>[] byLeft;
private final List<T> order = new ArrayList<>();
private final PriorityQueue<Item<T>> free =
new PriorityQueue<>(Comparator.<Item<T>>comparingDouble(i -> i.key).thenComparingInt(i -> i.index));
/**
* A thing with its footprint from ({@code x0}, {@code y0}) to ({@code x1}, {@code y1}) in world units,
* and the box it covers in the picture, from {@code left}, {@code top} to {@code right}, {@code bottom}.
*/
public void add(double x0, double y0, double x1, double y1, double left, double top, double right,
double bottom, T thing) {
Item<T> item = spare.isEmpty() ? new Item<>() : spare.removeLast();
item.x0 = x0;
item.y0 = y0;
item.x1 = x1;
item.y1 = y1;
item.left = left;
item.top = top;
item.right = right;
item.bottom = bottom;
item.key = x0 + x1 + y0 + y1;
item.index = items.size();
item.thing = thing;
item.afterCount = 0;
item.before = 0;
items.add(item);
}
/** How many things wait to be sorted. */
public int size() {
return items.size();
}
/** True if footprint A must be drawn before footprint B: A ends before B begins along x or along y. */
public static boolean behind(double ax0, double ay0, double ax1, double ay1,
double bx0, double by0, double bx1, double by1) {
boolean aFirst = ax1 <= bx0 || ay1 <= by0;
boolean bFirst = bx1 <= ax0 || by1 <= ay0;
return aFirst && !bFirst;
}
/**
* The things in the order to draw them, back to front. The sort is empty afterwards; the list is reused
* by the next call.
*/
@SuppressWarnings("unchecked")
public List<T> sorted() {
order.clear();
int n = items.size();
if (byLeft == null || byLeft.length < n) byLeft = new Item[Math.max(16, n * 2)];
for (int i = 0; i < n; i++) byLeft[i] = items.get(i);
Arrays.sort(byLeft, 0, n, Comparator.comparingDouble(i -> i.left));
// Only things whose boxes overlap in the picture can cover each other.
for (int i = 0; i < n; i++) {
Item<T> a = byLeft[i];
for (int j = i + 1; j < n && byLeft[j].left < a.right; j++) {
Item<T> b = byLeft[j];
if (b.top >= a.bottom || a.top >= b.bottom) continue;
if (behind(a.x0, a.y0, a.x1, a.y1, b.x0, b.y0, b.x1, b.y1)) link(a, b);
else if (behind(b.x0, b.y0, b.x1, b.y1, a.x0, a.y0, a.x1, a.y1)) link(b, a);
}
}
for (Item<T> item : items) if (item.before == 0) free.add(item);
boolean[] done = new boolean[n];
int drawn = 0;
while (drawn < n) {
Item<T> next = free.poll();
if (next == null) {
// A cycle: draw the nearest-to-the-back of what is left and go on.
for (Item<T> item : items) {
if (!done[item.index] && (next == null || item.key < next.key)) next = item;
}
}
if (done[next.index]) continue;
done[next.index] = true;
drawn++;
order.add(next.thing);
for (int k = 0; k < next.afterCount; k++) {
Item<T> later = items.get(next.after[k]);
if (--later.before == 0 && !done[later.index]) free.add(later);
}
}
free.clear();
for (Item<T> item : items) item.thing = null;
spare.addAll(items);
items.clear();
return order;
}
| Method | What it does |
|---|---|
add(x0, y0, x1, y1, left, top, right, bottom, thing) |
A thing with its footprint in world units and its box in the picture |
sorted() |
All things, back to front; empties the sort |
DepthSort.behind(...) |
The rule for two footprints, for a test of your own |
Put only what stands into the sort. Flat things (lawns, car parks, roads) are drawn before it, with the ground; a building of several parts is one item, its parts ordered inside its own picture.
A world larger than the screen: Camera¶
Package camera · introduced in 27. Jump; the mouse, a view below a bar and a camera the player moves in 30. Towers · source: Camera
What it is for. The part of a world larger than the screen that is shown: a view of the screen's logical size whose top left corner lies somewhere in a world of, say, 2400 × 400. The game draws the world shifted by the camera's position. The camera never shows anything outside the world: at its edges it stops, and a world smaller than the view is centred.
Two ways to move it.
- It follows a target, usually the player:
follow(x, y, seconds)in each step. Two rules make the scrolling calm. A dead zone in the middle of the view, in which the target may move without the camera moving at all, so a player who jumps on the spot does not shake the world. And smoothing: once the target leaves the dead zone, the camera closes a part of the distance per second (catchUp), worked out so it is the same at 60 or 120 steps a second.jumpToputs the target in the middle at once, at the start of a level. - The player moves it, by keys, by the mouse at the edge of the screen or by dragging the minimap:
moveBy(dx, dy)in each step, also with 0, 0 when nothing moves, so that the drawing between steps does not drift.
public final class Camera {
private double viewWidth;
private double viewHeight;
private final double worldWidth;
private final double worldHeight;
private double deadWidth;
private double deadHeight;
/** The part of the remaining distance the camera closes per second, 0 … 1; 1 follows at once. */
private double catchUp = 0.99;
private double x;
private double y;
private double previousX;
private double previousY;
/** Where the view's top left corner lies on the screen: (0, 0) unless a status bar takes the top. */
private double screenLeft;
private double screenTop;
public Camera(double viewWidth, double viewHeight, double worldWidth, double worldHeight) {
if (viewWidth <= 0 || viewHeight <= 0 || worldWidth <= 0 || worldHeight <= 0) {
throw new IllegalArgumentException("empty view or world");
}
this.viewWidth = viewWidth;
this.viewHeight = viewHeight;
this.worldWidth = worldWidth;
this.worldHeight = worldHeight;
}
/** The box in the middle of the view in which the target moves without the camera following. */
public Camera deadZone(double width, double height) {
deadWidth = Math.clamp(width, 0, viewWidth);
deadHeight = Math.clamp(height, 0, viewHeight);
return this;
}
/**
* How fast the camera catches up once the target has left the dead zone: the part of the distance it
* closes in one second. 0.99 leaves 1 % after a second, 0.5 is a slow drift; 1 sticks to the target.
*/
public Camera catchUp(double partPerSecond) {
catchUp = Math.clamp(partPerSecond, 0, 1);
return this;
}
/** Puts the target in the middle of the view at once, without scrolling: at the start, after a jump. */
public void jumpTo(double targetX, double targetY) {
x = clampX(targetX - viewWidth / 2);
y = clampY(targetY - viewHeight / 2);
previousX = x;
previousY = y;
}
/** One update step: moves towards the target if it has left the dead zone. */
public void follow(double targetX, double targetY, double seconds) {
previousX = x;
previousY = y;
double wantedX = x + outside(targetX - (x + viewWidth / 2), deadWidth / 2);
double wantedY = y + outside(targetY - (y + viewHeight / 2), deadHeight / 2);
// The part left after this step is (1 - catchUp) per second, so (1 - catchUp)^seconds of it:
// the same speed at 60 or at 120 steps a second.
double part = catchUp >= 1 ? 1 : 1 - Math.pow(1 - catchUp, seconds);
x = clampX(x + (wantedX - x) * part);
y = clampY(y + (wantedY - y) * part);
}
/** How far {@code offset} lies beyond {@code half} on either side of the middle; 0 inside. */
private static double outside(double offset, double half) {
if (offset > half) return offset - half;
if (offset < -half) return offset + half;
return 0;
}
private double clampX(double left) {
if (worldWidth <= viewWidth) return (worldWidth - viewWidth) / 2;
return Math.clamp(left, 0, worldWidth - viewWidth);
}
private double clampY(double top) {
if (worldHeight <= viewHeight) return (worldHeight - viewHeight) / 2;
return Math.clamp(top, 0, worldHeight - viewHeight);
}
The mouse in the world. A strategy game asks where a click lies in the world. worldX(screenX) and worldY(screenY) answer, for the camera after the last step, where the rules live. placedAt(left, top) says where the view lies on the screen, below a bar of 22 units for example; shows(x, y) is true when a point of the screen lies in the view and not on the bar beside it (chapter 30).
/**
* Where a point of the screen, such as the mouse, lies in the world: the camera's position plus the
* point's place in the view. Screen coordinates are those of the canvas, logical, so the window's size,
* the black bars and the render mode are already taken care of ({@code Mouse}). The answer is for the
* camera after the last step, where the rules live; the picture may lag a fraction of a step behind.
*/
public double worldX(double screenX) {
return x + screenX - screenLeft;
}
public double worldY(double screenY) {
return y + screenY - screenTop;
}
/** Where a point of the world is drawn on the screen, between the last two steps. */
public double screenX(double worldX, double alpha) {
return worldX - x(alpha) + screenLeft;
}
public double screenY(double worldY, double alpha) {
return worldY - y(alpha) + screenTop;
}
/** True if a point of the screen lies in the view, not on a bar beside it. */
public boolean shows(double screenX, double screenY) {
return screenX >= screenLeft && screenX < screenLeft + viewWidth
&& screenY >= screenTop && screenY < screenTop + viewHeight;
}
A view that changes its size. When the canvas widens on a wide screen, the view grows with it: resize(width, height) gives the camera a new view size and keeps the middle of the view where it was, as far as the edges allow. A game calls it in every update step with the size the screen has now; a size that has not changed changes nothing (chapter 30).
/**
* Gives the view a new size, e.g. when the canvas {@linkplain eu.amadeos.gameengine.swing.GameCanvas#logicalWidth()
* widens} on a wide screen. The middle of the view stays where it was, as far as the edges of the world
* allow; a size that has not changed changes nothing. Call it before {@link #moveBy} or {@link #follow}
* in an update step.
*/
public void resize(double width, double height) {
if (width <= 0 || height <= 0) throw new IllegalArgumentException("empty view");
if (width == viewWidth && height == viewHeight) return;
double middleX = x + viewWidth / 2;
double middleY = y + viewHeight / 2;
double previousMiddleX = previousX + viewWidth / 2;
double previousMiddleY = previousY + viewHeight / 2;
viewWidth = width;
viewHeight = height;
deadWidth = Math.min(deadWidth, width);
deadHeight = Math.min(deadHeight, height);
x = clampX(middleX - width / 2);
y = clampY(middleY - height / 2);
previousX = clampX(previousMiddleX - width / 2);
previousY = clampY(previousMiddleY - height / 2);
}
Drawing. x(alpha) and y(alpha) give the camera between its last two positions, for the frame. sees(left, top, width, height, alpha) is true when a box of the world is at least partly in view: a map of 64 × 64 tiles draws only the 33 × 26 or so the camera sees (chapter 27).
Depth: Parallax¶
Package camera · introduced in 27. Jump · source: Parallax
Backgrounds that scroll slower than the world, the further away they are: distant mountains, nearer hills, clouds. Each layer is one sprite, repeated side by side as far as the view needs and drawn seamlessly, and moved by a part of the camera's way, its factor: 0 stays still like the sky, 0.2 creeps along like mountains on the horizon, 1 moves with the world. A second, usually smaller factor moves it vertically, so the horizon stays where it is. draw(g, camera.x(alpha), camera.y(alpha)) before the world draws all layers, the furthest first. Cut a background with much empty sky into bands, and make the solid ones opaque (chapter 27).
What a side sees: FogOfWar and FogPainter¶
Package fog · introduced in 31. Sands · source: FogOfWar, FogPainter
What it is for. What one side knows of the map. Every tile is in one of three states: unseen (nobody of this side has looked there: black, the shroud), seen (someone looked once, but nobody looks now: the ground is known and dimmed, enemies there are not shown) and visible (a unit or building of this side sees it now). Each side has a fog of its own. In Sands the computer opponent plays by its fog as the player does, with one exception: it knows where the enemy's buildings are.
How it works. Each step, the game calls begin(), then look(col, row, radius) for everything of the side that sees, then end(). Looking marks the tiles within the radius as visible and as seen for ever. The circles are worked out once per radius and kept as lists of offsets, so a hundred units looking cost a hundred loops over a few dozen tiles each, without a square root. version() changes whenever a tile changes its state, so the picture of the fog and the minimap are drawn again only then.
public final class FogOfWar {
public enum State { UNSEEN, SEEN, VISIBLE }
private final int width;
private final int height;
private final boolean[] seen;
/** The step in which a tile was last looked at; it is visible if that is the current step. */
private final int[] lookedAt;
/** What {@link #lookedAt} said at the end of the step before, to find the tiles that changed. */
private final boolean[] wasVisible;
private final Map<Integer, int[]> circles = new HashMap<>();
private int step = 1;
private int version;
private boolean everything;
public FogOfWar(int width, int height) {
if (width <= 0 || height <= 0) throw new IllegalArgumentException("empty map");
this.width = width;
this.height = height;
this.seen = new boolean[width * height];
this.lookedAt = new int[width * height];
this.wasVisible = new boolean[width * height];
}
/** A new step: what was visible is visible only if someone looks again. */
public void begin() {
step++;
}
/** Everything within {@code radius} tiles of the middle of {@code col}, {@code row} is visible now. */
public void look(int col, int row, int radius) {
for (int offset : circle(radius)) {
// An offset packs the column and the row into one int: 16 bits each, with a sign.
int c = col + (short) (offset >> 16);
int r = row + (short) offset;
if (c < 0 || r < 0 || c >= width || r >= height) continue;
int i = r * width + c;
lookedAt[i] = step;
if (!seen[i]) {
seen[i] = true;
version++;
}
}
}
/** The end of a step: tiles that came into sight or went out of it change the version. */
public void end() {
for (int i = 0; i < lookedAt.length; i++) {
boolean now = lookedAt[i] == step;
if (now != wasVisible[i]) {
wasVisible[i] = now;
version++;
}
}
}
/** The tiles of a circle, as offsets from its middle tile: those whose middles lie within the radius. */
private int[] circle(int radius) {
return circles.computeIfAbsent(radius, r -> {
int[] offsets = new int[(2 * r + 1) * (2 * r + 1)];
int n = 0;
for (int dr = -r; dr <= r; dr++) {
for (int dc = -r; dc <= r; dc++) {
// A little more than r, so the circle of 1 is the tile and its four sides and corners.
if (dc * dc + dr * dr <= r * r + r) offsets[n++] = (dc << 16) | (dr & 0xFFFF);
}
}
return Arrays.copyOf(offsets, n);
});
}
| Method | What it does |
|---|---|
visible(col, row), seen(col, row), state(col, row) |
What the side knows of a tile |
revealAll(on) |
The whole map visible: a cheat, or the end of a game |
seenAsText(), restoreSeen(text) |
The tiles seen so far, one bit per tile as Base64, for a save file; what is visible needs no saving |
Soft edges. Drawn tile by tile, the fog would show the grid: a staircase at the edge of everything a unit sees. FogPainter gives each corner of a tile a state, the darkest of the four tiles that meet there, and shades the tile smoothly from corner to corner, with a little noise that frays the edge like a real fog. Three states at four corners make 3⁴ = 81 kinds of tile, and that is all there are: each is drawn once as a sprite and copied after that, the same trick as the 32 turned copies of a turret. Taking the darkest tile at a corner means the fog reaches half a tile into what is visible, never the other way: nothing that stands on a hidden tile shows through (chapter 31).
painter.render(g, fog, fromCol, fromRow, toCol, toRow) draws the fog over the tiles in view, after the world and before the marks that must stay readable. Runs of black tiles are filled as one rectangle, rounded to the screen's pixels exactly as drawSeamless rounds, so no line of pixels shows between the black and a soft tile.
What the player saw of the enemy, a building as it was when someone last looked, is the game's business: Sands keeps ghosts of enemy buildings in the seen fog (chapter 31).
The map in a corner: Minimap¶
Package minimap · introduced in 31. Sands · source: Minimap
What it is for. The whole map, small, in a corner of the screen: a pixel per tile, the things on it as dots, and a box that shows what the camera sees. A click on it moves the camera there.
How it works. The picture is an image of exactly one pixel per tile. The game paints a tile with paint(col, row, rgb) when it changes, which is seldom (crystal gone, a building up, fog lifted), and render(g) draws that image scaled into the minimap's box with hard edges in every frame. Scaling an image of 64 × 64 pixels into a box of 112 × 112 units is a small copy; drawing 4,096 rectangles in every frame would not be. The dots (dot), buildings in their true size (box) and the camera's view (view) are drawn over it in every frame, because they move.
/** True if a point of the screen lies on the minimap. */
public boolean contains(double screenX, double screenY) {
return screenX >= x && screenX < x + width && screenY >= y && screenY < y + height;
}
/** Where in the world a point of the minimap lies, in the world's units. */
public double worldX(double screenX) {
return (screenX - x) / width * columns * tile;
}
public double worldY(double screenY) {
return (screenY - y) / height * rows * tile;
}
/** Where on the screen a point of the world is shown. */
public double screenX(double worldX) {
return x + worldX / (columns * tile) * width;
}
public double screenY(double worldY) {
return y + worldY / (rows * tile) * height;
}
contains(x, y) tells whether a point of the screen lies on the minimap, and worldX, worldY where in the world it points: the camera moves there with a left click, a right click can send the chosen units. A map that is not square keeps its proportions and is centred in the box. Draw the minimap in the overlay, so it stays sharp in pixel mode.
An isometric map in a corner: DiamondMinimap¶
Package iso · introduced in 33. Town · source: DiamondMinimap
The minimap of an isometric map: the whole map as a small diamond, turned like the view. It is the picture of the IsoProjection, scaled down, so the camera's view is a plain box on it and a click on it is a point of the picture to move the camera to: camera.jumpTo(minimap.pictureX(x), minimap.pictureY(y)). The tiles are an image of one pixel per tile, as in Minimap, drawn through a transform that turns each pixel into a little diamond; paint(col, row, rgb) when a tile changes, render(g) and view(g, camera, alpha, colour) in the overlay, dot for things that move. Town also uses it, without a camera, for the previews on the choice of a mission.
public final class DiamondMinimap {
private final IsoProjection iso;
private final double x;
private final double y;
private final double scale;
private final int columns;
private final int rows;
private final BufferedImage image;
private final int[] pixels;
private final AffineTransform tiles;
private final Path2D.Double outline = new Path2D.Double();
private final Rectangle2D.Double rectangle = new Rectangle2D.Double();
private final BasicStroke thin = new BasicStroke(0.8f);
private boolean dirty = true;
/**
* The minimap of the map of {@code iso}, {@code width} wide with its top left corner at {@code x},
* {@code y} of the screen; its height follows from the map. The room above the map is left out.
*/
public DiamondMinimap(IsoProjection iso, double x, double y, double width) {
if (iso.columns() <= 0) throw new IllegalArgumentException("the projection has no map");
this.iso = iso;
this.columns = iso.columns();
this.rows = iso.rows();
this.scale = width / iso.width();
this.x = x;
this.y = y - iso.originY() * scale;
this.image = new BufferedImage(columns, rows, BufferedImage.TYPE_INT_ARGB);
this.pixels = new int[columns * rows];
// Pixel (col, row) of the image is tile (col, row): the projection's ground, scaled into the box.
double t = iso.tile();
AffineTransform place = new AffineTransform(scale, 0, 0, scale, this.x, this.y);
place.concatenate(iso.ground(0));
place.concatenate(AffineTransform.getScaleInstance(t, t));
this.tiles = place;
outline.moveTo(screenX(0, 0), screenY(0, 0));
outline.lineTo(screenX(columns * t, 0), screenY(columns * t, 0));
outline.lineTo(screenX(columns * t, rows * t), screenY(columns * t, rows * t));
outline.lineTo(screenX(0, rows * t), screenY(0, rows * t));
outline.closePath();
}
/** The colour of one tile, {@code 0xRRGGBB}; drawn with the next {@link #render}. */
public void paint(int col, int row, int rgb) {
int i = row * columns + col;
int argb = 0xFF000000 | rgb;
if (pixels[i] == argb) return;
pixels[i] = argb;
dirty = true;
}
/** The map, a diamond of little diamonds with hard edges. */
public void render(Graphics2D g) {
if (dirty) {
image.setRGB(0, 0, columns, rows, pixels, 0, columns);
dirty = false;
}
Object before = g.getRenderingHint(RenderingHints.KEY_INTERPOLATION);
g.setRenderingHint(RenderingHints.KEY_INTERPOLATION, RenderingHints.VALUE_INTERPOLATION_NEAREST_NEIGHBOR);
g.drawImage(image, tiles, null);
if (before != null) g.setRenderingHint(RenderingHints.KEY_INTERPOLATION, before);
}
/** The diamond's edge, for a frame around it. */
public Path2D.Double outline() {
return outline;
}
/** A thing at a point of the world, as a square of {@code size} screen units. */
public void dot(Graphics2D g, double worldX, double worldY, double size, Color colour) {
g.setColor(colour);
rectangle.setRect(screenX(worldX, worldY) - size / 2, screenY(worldX, worldY) - size / 2, size, size);
g.fill(rectangle);
}
/** The box of what the camera sees; the camera moves over the projection's picture. */
public void view(Graphics2D g, Camera camera, double alpha, Color colour) {
double left = x + camera.x(alpha) * scale;
double top = y + camera.y(alpha) * scale;
g.setStroke(thin);
g.setColor(colour);
rectangle.setRect(left, top, camera.viewWidth() * scale, camera.viewHeight() * scale);
g.draw(rectangle);
}