44. Movement, Physics and Collision¶
Things move in a game in a few typical ways: in a straight line at an angle, along a curve someone designed, falling and jumping on tiles, flying on jets, from tile centre to tile centre. Then the game must find out what hit what, often for hundreds of things in every step, and keep track of many things whose behaviour changes while they live. This chapter covers the arithmetic for all of it. Walking on a grid is in chapter 45, finding a way in chapter 46.
None of the classes here needs a screen. They are the rules' tools, and they are tested without one. Only PixelMask uses AWT, to draw its shapes into an image in memory, which works headless on a build server too.
Points and directions: Vector and Angles¶
Package math · introduced in 23. Rocks · source: Vector, Angles
What it is for. A Vector is a point or a direction in the plane: where a ship is, how fast it flies and where to, where its nose points. It is an immutable record; every operation returns a new vector, so a vector can be passed around and kept without anyone changing it behind your back. Angles brings angles into one range and finds the short way round between two of them.
How it works. Angles are radians. Angle 0 points right, along x; because y points down on the screen, a positive angle turns clockwise, and -π/2 points up. Vector.ofAngle(angle, length) makes a vector from an angle, angle() gives it back.
| Method | What it does |
|---|---|
plus, minus, times |
Add, subtract, scale |
length(), lengthSquared() |
The length; squared is enough to compare and needs no root |
normalized(), limited(max) |
Length 1; no longer than max, a speed limit |
dot(other) |
Positive if both point roughly the same way, 0 at a right angle |
rotated(angle), distance(other) |
Turned round the origin; the distance between two points |
Angles.normalize(a) |
The same direction between -π and π |
Angles.difference(from, to) |
How far to turn, the short way: from 170° to -170° is +20° |
Angles.turnTowards(from, to, maxStep) |
Turns by at most maxStep, without overshooting: a turret that follows its target |
/**
* How far to turn from {@code from} to {@code to} the short way round, -π to π: positive is clockwise on
* the screen. From 170° to -170° is +20°, not -340°.
*/
public static double difference(double from, double to) {
return normalize(to - from);
}
Tip: vectors in the hot loop
A Vector is a small record, and the JVM makes short-lived records very cheaply. Classes that run hundreds of times per frame, such as Particles and Outline, still keep plain double fields, because they must create nothing at all.
A field without edges: Wrap¶
Package math · introduced in 23. Rocks · source: Wrap
What it is for. A field on which what leaves on the right comes back on the left: the space of Rocks. Three things change on such a field, and Wrap answers each: a position must be brought back into the field (wrap), the distance between two things is the shortest one, which may lead across an edge (delta, distance), and a thing that sticks out over an edge must be drawn a second time on the other side (forEachCopy).
/**
* The shortest way from {@code from} to {@code to}, perhaps across an edge. On a field 640 wide, from
* x = 630 to x = 10 is +20, not -620.
*/
public Vector delta(Vector from, Vector to) {
double dx = to.x() - from.x();
double dy = to.y() - from.y();
dx -= width * Math.round(dx / width);
dy -= height * Math.round(dy / height);
return new Vector(dx, dy);
}
Drawing between steps. A thing that crossed an edge in the last step must not be drawn flying back across the whole screen. between(previous, current, alpha) interpolates along the short way, which may put it just outside the field, and forEachCopy then draws it on both sides (chapter 23).
On a grid. Tile maps wrap the same way with whole cells: TileMap.step and the searches of DistanceMap and AStar arrive on the far side, which makes the tunnel of Maze (chapter 45).
Curves to fly along: FlightPath¶
Package motion · introduced in 24. Swarm · source: FlightPath
What it is for. A curve designed in advance and flown at an even speed: the swoop of an insect into its formation, the loop of a dive, anything on rails. A path is built from cubic Bézier curves and straight lines:
| Method | What it does |
|---|---|
FlightPath.from(x, y).curveTo(c1x, c1y, c2x, c2y, x, y).lineTo(x, y).build() |
Builds a path: a curve bent by two control points, a line |
at(distance) |
Where one is after flying distance units along it |
angleAt(distance) |
The direction of flight there, for the nose |
length(), start(), end() |
Its length in units, its ends |
mirrored(width), translated(dx, dy) |
The same path mirrored in the middle of a field, or moved: one path for both sides |
When to choose it. When a designer decides how something flies. When the thing decides itself (it chases, it flees), give it a velocity and steer it with Vector and Angles.
How it works. A Bézier curve is easy to compute for a parameter t from 0 to 1, but equal steps of t are not equal steps along the curve: they crowd where the curve bends sharply. Flown by t, an insect would rush and crawl. So the path measures itself once at 48 points per curve, and at finds the t for a distance in that table by binary search (chapter 24).
/** Walks the path in small straight steps and notes the distance flown at each. */
private double[] measure() {
double[] table = new double[curves * SAMPLES + 1];
double lastX = points[0];
double lastY = points[1];
for (int i = 1; i < table.length; i++) {
double u = i / (double) SAMPLES; // curve number plus t
double x = coordinate(u, 0);
double y = coordinate(u, 1);
table[i] = table[i - 1] + Math.hypot(x - lastX, y - lastY);
lastX = x;
lastY = y;
}
return table;
}
/** The parameter at {@code distance}: the curve number plus <i>t</i> within it. */
private double parameterAt(double distance) {
double d = Math.clamp(distance, 0, length());
int i = Arrays.binarySearch(distances, d);
if (i >= 0) return i / (double) SAMPLES;
int after = -i - 1; // the first measured point beyond d
int before = after - 1;
double part = (d - distances[before]) / (distances[after] - distances[before]);
return (before + part) / SAMPLES;
}
Paths are data: Swarm writes them in its stage file, path swoop-left from 300 -20 curve ..., and reads them with TextData.
Grazing: Wander¶
Package motion · introduced in 32. Colony · source: Wander
What it is for. Something that idles around a home: sheep in a pasture, hens in a yard, people on a square. It walks to a spot, stands there for one to four seconds, and walks to the next; frightened, it runs to the far side of its circle at twice the speed.
When to choose it. For life in the picture that the rules do not need to steer. Something that must reach a place follows a path (46); something that flies a set course follows a FlightPath.
How it works. A spot is drawn evenly from the circle: an angle, and a radius times the square root of a random number. Without the root, half of the spots fall in the inner quarter of the circle, and the herd crowds in the middle. The random numbers come from the game's SeededRandom, so grazing repeats in a replay and goes on exactly after loading: state() is six numbers, and restore sets them.
public final class Wander {
private double homeX;
private double homeY;
private final double radius;
private final double speed;
private double x;
private double y;
private double targetX;
private double targetY;
private double pause;
private double pace = 1;
private boolean left;
public Wander(double homeX, double homeY, double radius, double speed) {
if (radius < 0 || speed <= 0) throw new IllegalArgumentException("radius " + radius + ", speed " + speed);
this.homeX = homeX;
this.homeY = homeY;
this.radius = radius;
this.speed = speed;
this.x = homeX;
this.y = homeY;
this.targetX = homeX;
this.targetY = homeY;
}
/** One step: stands or walks; true while it walks. */
public boolean update(double seconds, SeededRandom random) {
if (pause > 0) {
pause -= seconds;
if (pause > 0) return false;
pickSpot(random);
}
double dx = targetX - x;
double dy = targetY - y;
double distance = Math.hypot(dx, dy);
double step = speed * pace * seconds;
if (Math.abs(dx) > 1e-9) left = dx < 0;
if (distance <= step) {
x = targetX;
y = targetY;
pace = 1;
pause = 1 + random.nextDouble() * 3; // one to four seconds of grazing
return false;
}
x += dx / distance * step;
y += dy / distance * step;
return true;
}
/** A spot drawn evenly from the circle: the square root keeps the middle from crowding. */
private void pickSpot(SeededRandom random) {
double angle = random.nextDouble() * 2 * Math.PI;
double r = radius * Math.sqrt(random.nextDouble());
targetX = homeX + Math.cos(angle) * r;
targetY = homeY + Math.sin(angle) * r;
}
| Method | What it does |
|---|---|
new Wander(homeX, homeY, radius, speed) |
Starts at its home |
update(seconds, random) |
One step; true while it walks |
flee(x, y) |
Runs away from a point, to the far side of the circle, twice as fast |
home(x, y) |
Moves the circle; the next spot is in the new one |
x(), y(), walking(), facingLeft() |
For drawing |
state(), restore(state) |
For a save file |
Falling and standing: Body and TileCollider¶
Package physics · introduced in 27. Jump · source: Body, Solidity, TileCollider
What it is for. Things that move through a world of tiles and stand on it: a player, an enemy that walks. A Body is a box with a velocity and what it touched in its last move: onGround, hitCeiling, hitLeft, hitRight, onPlatform. A TileCollider moves bodies and stops them where the tiles are solid. Each tile is one of three Solidity values: EMPTY (air), SOLID (ground and walls) or PLATFORM (holds a body that comes down onto it from above, lets it pass from below, and can be dropped through on purpose).
When to choose it. For a side view with gravity: a platformer. A top-down game on a grid walks with a Walker or follows a flow field; a ball in an open field bounces with Sweep.
How it works. The trick of every platformer: move one axis at a time. First sideways, and if a wall is in the way, stop at it; then up or down, and if the ground is in the way, stand on it. Moved together, a body that falls diagonally onto the corner of a tile cannot tell whether it hit a wall or landed; moved apart, each axis has one answer. Each move looks at every column or row the body's edge passes, not only where it ends up, so a body falling 20 units in a step through tiles of 16 cannot fall through a floor.
public final class TileCollider {
/** What the tile at {@code col}, {@code row} is; asked also for tiles outside the map. */
@FunctionalInterface
public interface Tiles {
Solidity at(int col, int row);
}
/** Visits one tile. */
@FunctionalInterface
public interface CellVisitor {
void visit(int col, int row);
}
/** Edges that lie exactly on a tile border belong to the tile before it, not to the one after. */
private static final double EPSILON = 1e-6;
private final Tiles tiles;
private final double tileWidth;
private final double tileHeight;
public TileCollider(Tiles tiles, double tileWidth, double tileHeight) {
this.tiles = tiles;
this.tileWidth = tileWidth;
this.tileHeight = tileHeight;
}
/**
* Moves the body by its velocity for {@code seconds}: sideways, then up or down. Afterwards its contact
* flags say what it touched, and the velocity towards what it touched is 0.
*
* @param dropThrough true to fall through one-way platforms, e.g. while the player holds down
*/
public void move(Body body, double seconds, boolean dropThrough) {
body.remember();
body.onGround = body.hitCeiling = body.hitLeft = body.hitRight = body.onPlatform = false;
moveX(body, body.vx * seconds);
moveY(body, body.vy * seconds, dropThrough);
if (!body.onGround && body.vy >= 0) standing(body, dropThrough);
}
private void moveX(Body body, double dx) {
int top = row(body.y);
int bottom = row(body.bottom() - EPSILON);
if (dx > 0) {
// Every column the right edge enters, nearest first.
for (int col = col(body.right() - EPSILON) + 1; col <= col(body.right() + dx - EPSILON); col++) {
if (solidInColumn(col, top, bottom)) {
body.x = col * tileWidth - body.width;
body.vx = 0;
body.hitRight = true;
return;
}
}
} else if (dx < 0) {
for (int col = col(body.x) - 1; col >= col(body.x + dx); col--) {
if (solidInColumn(col, top, bottom)) {
body.x = (col + 1) * tileWidth;
body.vx = 0;
body.hitLeft = true;
return;
}
}
}
body.x += dx;
}
private void moveY(Body body, double dy, boolean dropThrough) {
int left = col(body.x);
int right = col(body.right() - EPSILON);
if (dy > 0) {
// Every row the feet enter. A platform holds only from above, and the feet come from above
// whenever they enter its row from the row before.
for (int row = row(body.bottom() - EPSILON) + 1; row <= row(body.bottom() + dy - EPSILON); row++) {
boolean solid = solidInRow(row, left, right);
boolean platform = !dropThrough && platformInRow(row, left, right);
if (solid || platform) {
body.y = row * tileHeight - body.height;
body.vy = 0;
body.onGround = true;
body.onPlatform = !solid;
return;
}
}
} else if (dy < 0) {
for (int row = row(body.y) - 1; row >= row(body.y + dy); row--) {
if (solidInRow(row, left, right)) {
body.y = (row + 1) * tileHeight;
body.vy = 0;
body.hitCeiling = true;
return;
}
}
}
body.y += dy;
}
The collider asks the game what a tile is, through a function (col, row) -> Solidity, also for tiles outside the map. So the tiles can be anything (a TileMap, a Tiled level, a formula), and the game decides what lies beyond the map: usually walls at the sides and air above and below, so a player can fall out of the world.
| Method | What it does |
|---|---|
body.fall(gravity, maxFall, seconds) |
Gravity, up to a speed the eye can follow and the tiles can catch |
collider.move(body, seconds, dropThrough) |
Sideways, then up or down; sets the contact flags and stops the velocity towards what was hit |
collider.forEachCell(body, visitor) |
Every tile the body overlaps: spikes, coins, water |
collider.groundAt(x, body) |
Ground under the body's feet at x: an enemy that turns at a ledge |
body.place(x, y) |
Somewhere at once, at rest, with no gliding there in the drawing |
body.x(alpha), body.y(alpha) |
Between the last two steps, for drawing |
Test: one axis at a time
@Test
void sidewaysFirstThenDownAWallStopsTheRunButNotTheFall() {
TileCollider world = world(
"...X..",
"...X..",
"...X..",
"XXXXXX");
Body body = new Body(30, 10, 10, 14);
body.vx = 2400; // 20 units in this step, 12 of them free
body.vy = 300;
world.move(body, STEP, false);
assertTrue(body.hitRight);
assertEquals(48 - 10, body.x, 1e-9, "against the wall");
assertEquals(0, body.vx, 1e-9);
assertEquals(12.5, body.y, 1e-9, "and still falling along it");
assertFalse(body.onGround);
}
Jumping: Jump¶
Package physics · introduced in 27. Jump · source: Jump
The jump of a platformer, with the three small kindnesses that make it feel right rather than exact: coyote time (a press just after running off a ledge still jumps), a jump buffer (a press just before landing is carried out on landing) and a variable height (letting go while rising cuts the speed, so a tap is a hop and a held button the full jump). Call update(body, pressed, held, seconds) in each step after the last move and before this step's fall; it returns true in the step a jump starts, for the sound.
The speed of a jump follows from the height it should reach: rising at v against gravity g, a body stops at the height v² / 2g. Jump.speedFor(height, gravity) turns "four tiles high" into a speed, and heightOf goes the other way, so the level designer can rely on it and a test can prove every level can be finished (chapter 27). launch(body, speed, cuttable) throws a body up without the button: the bounce off a stomped enemy, a spring.
Flying on jets: Thrusters, drag and Touchdown¶
Package physics · introduced in 28. Hover Cab · source: Thrusters, Touchdown, Body
What it is for. A craft that flies against gravity on jets and has to land: a lunar lander, a flying cab, a jetpack, a helicopter. Thrusters know how hard the jets push, up (the main jet), to the sides and down, and how much fuel they burn; Body.drag is the air that slows the craft; Touchdown decides whether a landing was soft, hard or a crash.
When to choose it. When the player steers by pushing, not by setting a speed: a jet changes the speed a little in every step for as long as it burns. A character that runs and jumps sets its speed at once, with a Jump; a ship in a field without edges turns and pushes with a Vector and needs no gravity.
How it works. fire(body, x, y, fuel, seconds) adds the pushes of the jets that fire to the body's velocity, as accelerations like gravity, and returns the fuel burned, never more than is left: with too little for the whole step, the jets push for the part of the step the fuel lasts. The side and down jets burn in proportion to their push.
public final class Thrusters {
private final double up;
private final double side;
private final double down;
private final double burn;
/**
* Jets pushing up (the main one, under the craft), to the sides and down, and the fuel the main jet burns
* in a second; the side and down jets burn in proportion to their push.
*/
public Thrusters(double up, double side, double down, double burn) {
if (up < 0 || side < 0 || down < 0 || burn < 0) throw new IllegalArgumentException("negative thrust or burn");
this.up = up;
this.side = side;
this.down = down;
this.burn = burn;
}
/**
* Fires the jets for a step: {@code x} -1 pushes left, 1 right; {@code y} -1 pushes up (the main jet),
* 1 down; 0 neither. Returns the fuel burned, at most {@code fuel}; with less fuel left than the step
* needs, the jets push for that part of the step only.
*/
public double fire(Body body, double x, double y, double fuel, double seconds) {
double wanted = rate(x, y) * seconds;
if (wanted <= 0 || fuel <= 0) return 0;
double part = Math.min(1, fuel / wanted);
double time = seconds * part;
body.vx += Math.signum(x) * Math.min(1, Math.abs(x)) * side * time;
if (y < 0) body.vy -= Math.min(1, -y) * up * time;
else if (y > 0) body.vy += Math.min(1, y) * down * time;
return wanted * part;
}
A main jet of about twice gravity feels right: the craft rises about as fast as it falls. Without drag, a push sets the craft drifting until an equal push the other way stops it, which feels like steering soap. drag(perSecond, seconds) takes away that part of the speed each second, smoothly and whatever the step (chapter 28):
/**
* Air: the velocity loses the part {@code perSecond} of itself each second, smoothly, whatever the
* length of the step. Without it a craft that has been pushed drifts on for ever, as in space; with
* {@code 0.5} it has lost about forty percent after a second and is slow after a few.
*/
public void drag(double perSecond, double seconds) {
double keep = Math.pow(1 - perSecond, seconds);
vx *= keep;
vy *= keep;
}
Touchdown.of(vx, vy, soft, hard) grades a landing by the larger of the downward speed and twice the sideways one: sliding onto a deck tips a craft over sooner than sitting down hard. On a moving deck, pass the speed against the deck.
| Method | What it does |
|---|---|
new Thrusters(up, side, down, burn) |
The pushes in units per second per second, and the fuel the main jet burns in a second |
fire(body, x, y, fuel, seconds) |
Fires for a step: x -1 left, 1 right; y -1 up, 1 down; returns the fuel burned |
rate(x, y) |
The fuel a second the jets burn, fired so: for a gauge or a planner |
body.drag(perSecond, seconds) |
Air: the velocity loses that part of itself each second |
Touchdown.of(vx, vy, soft, hard) |
SOFT, HARD or CRASH |
Test: jets that burn what is left
@Test
void theMainJetBeatsGravityUntilTheTankIsEmpty() {
Thrusters jets = new Thrusters(1.5 * GRAVITY, 0.5 * GRAVITY, 0.5 * GRAVITY, 2);
Body cab = new Body(0, 0, 10, 10);
double fuel = 1;
for (int i = 0; i < 60; i++) { // half a second at 120 steps a second
fuel -= jets.fire(cab, 0, -1, fuel, 1 / 120.0);
cab.fall(GRAVITY, 1000, 1 / 120.0);
}
assertEquals(-0.5 * GRAVITY * 0.5, cab.vy, 1e-9, "rising at half a g after half a second");
assertEquals(0, fuel, 1e-9, "two units a second: the tank is empty");
assertEquals(0, jets.fire(cab, 0, -1, fuel, 1 / 120.0), "nothing left to burn");
}
Which collision test?¶
| The things | Use | Because |
|---|---|---|
| Boxes that do not turn, one of them fast: a ball and bricks | Sweep |
Tests the whole way of a step; a fast ball cannot pass through a brick |
| Boxes at rest, or slow: a player and a coin | Box.overlaps |
One comparison per axis |
| Round things, things that turn | Circle |
A circle looks the same at every angle; works across the edge of a Wrap |
| A body against tiles | TileCollider |
Above |
| Shapes that are neither boxes nor circles: a cab and a neon sign, a rock face | PixelMask |
Exact to the pixel, 64 pixels per comparison |
| Many things against many | Grid, then one of the above |
Each thing meets only its neighbours |
Boxes: Box and Sweep¶
Package collision · introduced in 21. Bricks · source: Box, Sweep
A Box is an axis-aligned rectangle, its top left corner at x, y; boxes that only touch do not overlap. Sweep.sweep(moving, dx, dy, target) tests a moving box against one at rest over the whole way of a step and returns where they first touch: the share of the step, 0 to 1, and the face that was hit as a normal, the direction to bounce. Without it, a ball in front of a brick in one step and behind it in the next would pass through ("tunnelling").
The trick is to shrink the moving box to a point and grow the target by the moving box's size (their Minkowski sum). Then the question is only where a straight line enters a rectangle: for each axis, when does the point enter the target's range and when does it leave it?
/**
* The first contact of {@code moving}, moved by {@code dx}, {@code dy} during the step, with
* {@code target}; {@code null} if there is none within the step, or if the boxes already overlap at the
* start (then the caller has to separate them first).
*/
public static Hit sweep(Box moving, double dx, double dy, Box target) {
// The target grown by the moving box: now the moving box is the point (moving.x, moving.y).
double left = target.x() - moving.width();
double right = target.right();
double top = target.y() - moving.height();
double bottom = target.bottom();
double[] x = enterAndLeave(moving.x(), dx, left, right);
double[] y = enterAndLeave(moving.y(), dy, top, bottom);
if (x == null || y == null) return null;
double enter = Math.max(x[0], y[0]);
double leave = Math.min(x[1], y[1]);
if (enter >= leave || enter > 1 || enter < 0) return null;
// The axis entered last is the face that was hit.
if (x[0] > y[0]) return new Hit(enter, dx > 0 ? -1 : 1, 0);
return new Hit(enter, 0, dy > 0 ? -1 : 1);
}
/**
* When a point starting at {@code p} and moving by {@code d} enters and leaves the range
* {@code min..max}, as shares of the step; {@code null} if it never is inside.
*/
private static double[] enterAndLeave(double p, double d, double min, double max) {
if (d == 0) {
// Not moving on this axis: inside the whole time or never.
return p > min && p < max ? new double[]{Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY} : null;
}
double t1 = (min - p) / d;
double t2 = (max - p) / d;
return new double[]{Math.min(t1, t2), Math.max(t1, t2)};
}
A ball that hits a brick early in a step moves on, bounced, for the rest of it, and may hit a second brick in the same step: the game sweeps again with what is left (chapter 21). Boxes that already overlap at the start give no hit; separate them first.
Circles: Circle¶
Package collision · introduced in 23. Rocks · source: Circle
Two circles overlap when their centres are closer than both radii together, compared squared, without a root. overlaps(other, wrap) measures across the edges of a field without edges; contains(x, y) is for a click on a round thing. A turning figure's hit circle is its Outline.radius(), or a little less, so that only a real touch counts.
Exact to the pixel: PixelMask¶
Package collision · introduced in 28. Hover Cab · source: PixelMask
What it is for. Collisions as exact as the pictures, for shapes a box or a circle fits badly: a cab with thin legs, a slanted strut, a round sign, the jagged wall of a cave. A PixelMask says which pixels of a thing are solid, one bit each; two masks collide when they have a solid pixel in the same place.
When to choose it. When players would see the difference: a near miss that a box would count as a hit. For many small things, or things that turn every step, circles are cheaper; a mask is made once and does not turn (keep one per direction or per few degrees, made in advance).
How it works. A row is kept as longs of 64 pixels, the leftmost in the lowest bit. To compare a row of one mask with a row of another, each of its longs is shifted to where it lies in the other row, where it falls into one long or across two, and ANDed: 64 pixels in one instruction. A cab of 32 × 16 pixels against a whole scene costs a few dozen ANDs. firstOverlap also returns the first pixel where both are solid, top row first, to tell what was hit.
/**
* Whether {@code other}, its top left corner at {@code dx}, {@code dy} of this mask, has a solid pixel
* where this one has one. Row by row, each 64 pixels of the other mask are shifted to where they lie in
* this one: they fall into one long of this row, or into two neighbouring ones.
*/
public boolean overlaps(PixelMask other, int dx, int dy) {
return firstOverlap(other, dx, dy) != null;
}
/** The first pixel, in this mask's coordinates, where both masks are solid, top row first; null if none. */
public Point firstOverlap(PixelMask other, int dx, int dy) {
int top = Math.max(0, dy);
int bottom = Math.min(height, dy + other.height);
if (top >= bottom || dx >= width || dx + other.width <= 0) return null;
int q = Math.floorDiv(dx, 64);
int r = Math.floorMod(dx, 64);
for (int y = top; y < bottom; y++) {
int mine = y * words;
int theirs = (y - dy) * other.words;
for (int j = 0; j < other.words; j++) {
long word = other.bits[theirs + j];
if (word == 0) continue;
int k = q + j; // the long of this row the word starts in
if (k >= 0 && k < words) {
long hit = bits[mine + k] & (word << r);
if (hit != 0) return new Point(k * 64 + Long.numberOfTrailingZeros(hit), y);
}
if (r != 0 && k + 1 >= 0 && k + 1 < words) {
long hit = bits[mine + k + 1] & (word >>> (64 - r));
if (hit != 0) return new Point((k + 1) * 64 + Long.numberOfTrailingZeros(hit), y);
}
}
}
return null;
}
The easiest masks to get right are drawn: PixelMask.painted(width, height, g -> ...) fills the same shapes the painter draws into an image without antialiasing, so what is seen is what collides. PixelMask.of(image) takes the opaque pixels of a picture.
| Method | What it does |
|---|---|
PixelMask.painted(w, h, painter), PixelMask.of(image) |
A mask of shapes, or of a picture's pixels with alpha 128 or more |
overlaps(other, dx, dy), firstOverlap(other, dx, dy) |
Whether, and where first, other at dx, dy touches this mask |
anyIn(x, y, w, h) |
Whether a box has a solid pixel: a mask against something that is a box |
solid, set, clear, add(other, dx, dy), count() |
Single pixels; another mask added in |
Test: a round sign is hit only where it is round
@Test
void aRoundSignIsHitOnlyWhereItIsRound() {
// a disc 40 pixels across in a 200 × 100 scene, and a 4 × 4 block flown around it
PixelMask scene = PixelMask.painted(200, 100, g -> g.fill(new Ellipse2D.Double(80, 30, 40, 40)));
PixelMask block = new PixelMask(4, 4);
for (int y = 0; y < 4; y++) for (int x = 0; x < 4; x++) block.set(x, y);
assertTrue(scene.overlaps(block, 98, 48), "the middle of the disc");
assertFalse(scene.overlaps(block, 80, 30), "the corner of its box is empty");
assertFalse(scene.overlaps(block, 120, 48), "beside it");
assertTrue(scene.overlaps(block, 117, 48), "its right edge");
}
Many things: Grid¶
Package collision · introduced in 24. Swarm · source: Grid
What it is for. Finding the things near a place without looking at all things. Testing each of n things against each other costs n² / 2 tests: 40 insects and 2 shots are 80, nothing; 2,000 shots, sparks and units are two million, in every step. With a grid, each thing meets only the few in its neighbourhood.
How it works. Each step, the game empties the grid (clear()) and puts each thing into every cell its circle touches (add(thing, x, y, radius)). A question, forEachNear(x, y, radius, visitor), then visits each thing in the cells around a place, each once; whether a candidate really touches is the caller's test. Choose the cell a little larger than most things, so a thing touches one to four cells. Things outside the field count to the cells at its edge. The entries live in arrays that only grow, so after the first steps, filling and asking create no objects.
public final class Grid<T> {
private final double cellSize;
private final int columns;
private final int rows;
/** Per cell, the first of its entries, or -1. */
private final int[] firstEntry;
/** Per entry, the next entry of the same cell, or -1, and the thing it stands for. */
private int[] nextEntry = new int[64];
private int[] entryItem = new int[64];
private int entries;
private Object[] items = new Object[32];
private int size;
/** Per thing, the number of the last question that visited it: no thing is visited twice. */
private int[] visited = new int[32];
private int question;
public Grid(double width, double height, double cellSize) {
if (width <= 0 || height <= 0 || cellSize <= 0) throw new IllegalArgumentException("empty grid");
this.cellSize = cellSize;
this.columns = (int) Math.ceil(width / cellSize);
this.rows = (int) Math.ceil(height / cellSize);
this.firstEntry = new int[columns * rows];
clear();
}
/** Empties all cells; the game calls it at the start of each step, before it adds the things anew. */
public void clear() {
Arrays.fill(firstEntry, -1);
Arrays.fill(items, 0, size, null);
entries = 0;
size = 0;
}
/** Puts a thing into every cell its area, a circle around {@code x}, {@code y}, touches. */
public void add(T item, double x, double y, double radius) {
if (size == items.length) {
items = Arrays.copyOf(items, 2 * size);
visited = Arrays.copyOf(visited, 2 * size);
}
int index = size++;
items[index] = item;
visited[index] = question;
for (int row = row(y - radius); row <= row(y + radius); row++) {
for (int column = column(x - radius); column <= column(x + radius); column++) {
if (entries == nextEntry.length) {
nextEntry = Arrays.copyOf(nextEntry, 2 * entries);
entryItem = Arrays.copyOf(entryItem, 2 * entries);
}
int cell = row * columns + column;
entryItem[entries] = index;
nextEntry[entries] = firstEntry[cell]; // in front of the cell's other entries
firstEntry[cell] = entries++;
}
}
}
/**
* Visits every thing in the cells that a circle around {@code x}, {@code y} touches, each once: the
* candidates. Whether a candidate really touches is the caller's test. Returns how many were visited.
*/
@SuppressWarnings("unchecked")
public int forEachNear(double x, double y, double radius, Consumer<? super T> visitor) {
question++;
int count = 0;
for (int row = row(y - radius); row <= row(y + radius); row++) {
for (int column = column(x - radius); column <= column(x + radius); column++) {
for (int e = firstEntry[row * columns + column]; e >= 0; e = nextEntry[e]) {
int index = entryItem[e];
if (visited[index] == question) continue; // already met in another cell
visited[index] = question;
count++;
visitor.accept((T) items[index]);
}
}
}
return count;
}
private int column(double x) {
return Math.clamp((long) Math.floor(x / cellSize), 0, columns - 1);
}
private int row(double y) {
return Math.clamp((long) Math.floor(y / cellSize), 0, rows - 1);
}
Besides collisions, the grid answers "who is near?" in general. Sands uses it to push vehicles apart that drive into each other, so that a group spreads out instead of meeting in one point.
A fixed number of things: Pool¶
Package pool · introduced in 23. Rocks · source: Pool
What it is for. A fixed number of reusable objects, such as shots, all made at the start: obtain() takes one (or null when all are in use), release(index) or releaseIf(done) gives it back.
When to choose it. When the capacity is a rule: the ship of the old arcade games could have four shots in the air, no more, and a full pool says so. A game that creates nothing while it runs also gives the garbage collector nothing to do. Where there is no natural limit, a plain list of the game's own objects is simpler, as Towers and Sands keep their shots.
How it works. The objects in use are always the first size() ones. Giving one back moves the last one in use into its place, as Particles does with its rows, so the order changes: walk backwards when you give back while walking, as releaseIf does.
public final class Pool<T> {
private final Object[] items;
private int size;
/** Makes all {@code capacity} objects at once with {@code factory}. */
public Pool(int capacity, Supplier<? extends T> factory) {
if (capacity < 1) throw new IllegalArgumentException("capacity " + capacity);
items = new Object[capacity];
for (int i = 0; i < capacity; i++) items[i] = factory.get();
}
/** Gives all objects back, e.g. for a new game. */
public void clear() {
size = 0;
}
/** The objects in use. */
public int size() {
return size;
}
public int capacity() {
return items.length;
}
public boolean isFull() {
return size == items.length;
}
/** A free object, now in use, as the last one; {@code null} if all are in use. */
@SuppressWarnings("unchecked")
public T obtain() {
return size == items.length ? null : (T) items[size++];
}
/** The object in use at {@code index}, 0 to {@link #size()} - 1. */
@SuppressWarnings("unchecked")
public T get(int index) {
if (index < 0 || index >= size) throw new IndexOutOfBoundsException(index);
return (T) items[index];
}
/** Gives the object at {@code index} back; the last object in use takes its place. */
public void release(int index) {
if (index < 0 || index >= size) throw new IndexOutOfBoundsException(index);
size--;
Object released = items[index];
items[index] = items[size];
items[size] = released; // kept for the next obtain: the pool never forgets an object
}
/** Gives back every object in use that {@code done} says is done; returns how many. */
public int releaseIf(Predicate<? super T> done) {
int released = 0;
for (int i = size - 1; i >= 0; i--) {
if (done.test(get(i))) {
release(i);
released++;
}
}
return released;
}
}
Entities and components¶
Package entity · introduced in 24. Swarm · source: Entity, Entities
What it is for. Things whose behaviour changes while they live. An Entity is little more than a number and a bag of components: a body, a flight along a path, a place in a formation, hit points. What it is and what it does follows from the components it has right now. An insect that leaves the formation to dive gets a flight, and loses it again when it is back; its class never changes, its components do. Each rule, a system, walks over the entities that have the components it needs: the flight system moves whatever flies, insect, shot or ship, and never asks which it is.
When to choose it. When things share behaviour in changing combinations, as the insects, their shots and the fighter of Swarm do. When there are a few kinds of things, each with a fixed set of rules, plain classes are clearer: Towers and Sands keep their creeps, units and buildings as classes of their own, in lists.
How it works. A component is any object, looked up by its class; an entity holds at most one of each class. Entities.create() and entity.destroy() take effect only at flush(), which the game calls once per step after all systems ran, so no system changes the list under another's feet. The entities stay in the order they were made, so systems visit them in the same order in every run, and a game with a fixed seed repeats exactly.
public final class Entities {
/** What a system does with an entity that has both components. */
@FunctionalInterface
public interface Each2<A, B> {
void accept(Entity entity, A a, B b);
}
private final List<Entity> entities = new ArrayList<>();
private final List<Entity> born = new ArrayList<>();
private long nextId = 1;
/** A new entity without components; it joins the others at the next {@link #flush()}. */
public Entity create() {
Entity entity = new Entity(nextId++);
born.add(entity);
return entity;
}
/** Takes in the entities made since the last flush and drops the destroyed ones. */
public void flush() {
entities.removeIf(entity -> !entity.alive());
for (Entity entity : born) {
if (entity.alive()) entities.add(entity);
}
born.clear();
}
/** Every living entity with a component of {@code type}, in the order they were made. */
public <A> void forEach(Class<A> type, BiConsumer<Entity, A> system) {
for (int i = 0; i < entities.size(); i++) {
Entity entity = entities.get(i);
if (!entity.alive()) continue;
A a = entity.get(type);
if (a != null) system.accept(entity, a);
}
}
/** Every living entity with components of both types. */
public <A, B> void forEach(Class<A> typeA, Class<B> typeB, Each2<A, B> system) {
for (int i = 0; i < entities.size(); i++) {
Entity entity = entities.get(i);
if (!entity.alive()) continue;
A a = entity.get(typeA);
if (a == null) continue;
B b = entity.get(typeB);
if (b != null) system.accept(entity, a, b);
}
}
| Method | What it does |
|---|---|
entity.add(component), get(Type.class), has, remove |
The components |
entities.forEach(Type.class, (entity, a) -> ...) |
A system over one component |
entities.forEach(A.class, B.class, (entity, a, b) -> ...) |
A system over entities that have both |
count(Type.class), with(Type.class) |
How many have it; a list of them |
flush(), clear() |
Takes in the new and drops the destroyed; removes all |