Kotlin 116: Collision. Maybe Cycling.
We’re like ten articles in on a video game with no video. This is rather interesting. I’ll try to explain why.
Normally, when I’ve done my replica video games, SpaceWar, Asteroids, Space Invaders, I’ve started with something on the screen and then evolved the game on the screen. It has always seemed to me that there just wasn’t much room for TDD when the whole game is about what’s on the screen. In this game, yet another asteroids, I’ve been intentionally avoiding drawing the game on the screen, and instead am using tests to determine that my objects are doing what they should. If this works, one day soon I’ll connect the objects to the screen and there it’ll be, ship and asteroids sailing about.
Probably it won’t go that smoothly, but it feels to me that it’ll be close. If, or should I say when it works, what I’ll have is a game where the behavior of the objects is rather fully tested and where I have much greater confidence than I might otherwise have that things are actually doing what I intend.
The other way can work, and in my examples it has worked well. But it has always seemed, in those examples, that I had no real choice but to debug by eye. this approach gives me a choice. It’s good to have more than one way to accomplish something.
Let’s get to it.
Flyers
Yesterday I spiked a couple of versions of code to scan a collection of objects for collisions, so now I have some code that runs on a native collection and does that job. But I am confident that we’ll be happier if we make a collection of our own, containing a native collection. So let’s get to it. I’ll test drive its creation, starting with getting it created, then putting some objects into it, and then implementing the collision method on it.
I get this far …
@Test
fun `create flyers instance`() {
val flyers = Flyers()
val a = FlyingObject.asteroid(Vector2(100.0,100.0), Vector2(50.0,50.0))
flyers.add(a)
val s = FlyingObject.ship(Vector2(100.0, 150.0))
flyers.add(s)
}
I realize at this point that I’m imagining this object just having add and remove, and possibly not even remove, if we make it manage the collisions internally. That’s going to be a negotiation between some kind of game object and this one, which I am viewing as a smart collection of objects but not the game. We’ll see. Anyway this is more than enough to get started. I’ll add a check for a method count to tell us how many objects there are. We may only need it here, for testing.
assertThat(flyers.size).isEqualTo(2)
IDEA wants to help me create the FLyers class. Working together we’ll get this:
class Flyers {
private val flyers = mutableListOf<FlyingObject>()
fun add(flyer: FlyingObject) {
flyers.add(flyer)
}
val size get() = flyers.size
}
We are green. Commit: Class Flyers initial implementation.
Let’s just replicate that test and do collisions.
@Test
fun `collision detection`() {
val flyers = Flyers()
val a = FlyingObject.asteroid(Vector2(100.0,100.0), Vector2(50.0,50.0))
flyers.add(a)
val s = FlyingObject.ship(Vector2(100.0, 150.0))
flyers.add(s)
assertThat(flyers.size).isEqualTo(2)
val colliders = flyers.colliders()
assertThat(colliders.size).isEqualTo(2)
}
I’ve decided that the Flyers class doesn’t want to understand much about what’s going on with its contents, so I’ll have it return the set of colliders that it creates. Whoever calls for that, the game I suppose, can ask to have those removed (we’ll do that shortly), send them messages, replace them with fireworks, whatever.
IDEA realizes that I have no colliders method.
I begin with the double loop that I consider to be more readable:
fun colliders(): Set<FlyingObject> {
val colliding = mutableSetOf<FlyingObject>()
for (f1 in flyers ){
for (f2 in flyers) {
if (f1.collides(f2)) {
colliding.add(f1)
colliding.add(f2)
}
}
}
return colliding
}
Test. Green. Commit: Flyers colliders returns all objects colliding with another object.
Now, we know that this scheme compares every item against every other, performing 4 checks where only two are necessary in this case. The other algorithm was faster but less clear. Let’s plug it in now.
fun colliders(): Set<FlyingObject> {
val colliding = mutableSetOf<FlyingObject>()
var ct = 0
for (i in 0 until flyers.size-1){
val f1 = flyers[i]
for (j in i until flyers.size) {
val f2 = flyers[j]
ct += 1
if (f1.collides(f2)) {
colliding.add(f1)
colliding.add(f2)
}
}
}
print(ct)
return colliding
}
I want a stronger test for this, so I’ll copy the data over from my spike, into a new test.
@Test
fun `stringent colliders`() {
val p1 = Vector2(100.0,100.0)
val p2 = Vector2(500.0, 500.0)
val flyers = Flyers()
val v = Vector2.ZERO
val a0 = FlyingObject.asteroid(p1,v) // yes
flyers.add(a0)
val m1 = FlyingObject(p1, v, Vector2.ZERO, 10.0) // yes
flyers.add(m1)
val s2 = FlyingObject.ship(p1) // yes
flyers.add(s2)
val a3 = FlyingObject.asteroid(p2,v) // no
flyers.add(a3)
val a4 = FlyingObject.asteroid(p2,v) // no
flyers.add(a4)
val colliders = flyers.colliders()
assertThat(colliders.size).isEqualTo(3)
}
This test passes. Commit: faster colliders but harder to read.
I would like this one to be easier to understand:
fun colliders(): Set<FlyingObject> {
val colliding = mutableSetOf<FlyingObject>()
for (i in 0 until flyers.size-1){
val f1 = flyers[i]
for (j in i until flyers.size) {
val f2 = flyers[j]
if (f1.collides(f2)) {
colliding.add(f1)
colliding.add(f2)
}
}
}
return colliding
}
Improving …
What could we do that would make this easier to understand? What if we produced the indices of the pairs to check and then used them? We’ll try that, at some small cost in efficiency.
fun colliders(): Set<FlyingObject> {
val colliding = mutableSetOf<FlyingObject>()
indicesToCheck().forEach { p ->
if (flyers[p.first].collides(flyers[p.second])) {
colliding.add(flyers[p.first])
colliding.add(flyers[p.second])
}
}
return colliding
}
That would work if we could generate the indices. I get close to that and then realize that if I can generate pairs of indices I can generate pairs of FlyingObject, so I wind up with this:
private fun pairsToCheck(): List<Pair<FlyingObject, FlyingObject>> {
val pairs = mutableListOf<Pair<FlyingObject,FlyingObject>>()
flyers.indices.forEach() {
i -> flyers.indices.minus(0..i).forEach() {
j -> pairs.add(flyers[i] to flyers[j]) }
}
return pairs
}
fun colliders(): Set<FlyingObject> {
val colliding = mutableSetOf<FlyingObject>()
pairsToCheck().forEach { p ->
if (p.first.collides(p.second)) {
colliding.add(p.first)
colliding.add(p.second)
}
}
return colliding
}
I freely grant that I found the code for pairsToCheck on stack overflow. But it is short and sweet and pretty easy to understand, plus nicely encapsulated on its own.
And it passes the tests. Let’s go with it.
Commit: fancy pair-generating colliders algorithm.
We could just about create a game loop here. Let’s create a new test class for Game.
@Test
fun `create game`() {
val game = Game()
}
Just to show that I can write a tiny test if I want to. Demands a class:
class Game {
}
Green. Could commit if I wanted to. I don’t want to. Let’s create a little game here, and maybe even run it.
class GameTest {
@Test
fun `create game`() {
val game = Game()
val asteroid = FlyingObject.asteroid(Vector2(100.0, 100.0), Vector2(50.0, 50.0))
val ship = FlyingObject.ship(Vector2(1000.0, 1000.0))
game.add(asteroid)
game.add(ship)
assertThat(game.colliderCount()).isEqualTo(0)
}
}
- Aside
- One irritating aspect of doing video games with tests is the math you have to do to compute answers like distances and necessary time delays. It’s not really hard, and we could have a tool to help us.
I’m working toward game play. In the test above, the asteroid is traveling at a velocity of, oh, I don’t know, sqrt(5000) about 70.7106 if Siri is correct, toward the ship at location 1000,1000.
I wish I had done this in a vertical or horizontal line. Default kill radii are 400 for the asteroid, 100 for the ship, 500 total. Our distance now is about 1270 units, so we need to travel about 1270-500, or 770, call it a dozen moves to get in kill range.
Therefore first implement add and colliderCount() on Game:
class Game {
val flyers = Flyers()
fun add(fo: FlyingObject) {
flyers.add(fo)
}
fun colliderCount(): Int = flyers.colliders().size
}
Test, expecting to pass. Yes. Now have the game cycle a dozen steps at a sixtieth. (We could go in one big step but why not this. (We’ll find my mistake in a moment.))
@Test
fun `create game`() {
val game = Game()
val asteroid = FlyingObject.asteroid(Vector2(100.0, 100.0), Vector2(50.0, 50.0))
val ship = FlyingObject.ship(Vector2(1000.0, 1000.0))
game.add(asteroid)
game.add(ship)
assertThat(game.colliderCount()).isEqualTo(0)
for (i in 1..12) game.cycle(1.0/60.0)
assertThat(game.colliderCount()).isEqualTo(2)
}
Game needs to know cycle. And so does Flyers:
class Game ...
fun cycle(seconds: Double) = flyers.cycle(seconds)
class Flyers ...
fun cycle(seconds: Double) {
flyers.forEach { flyer -> flyer.cycle(seconds)}
}
I think this might work. If not, we’ll need to do a bit of printing to find out why not. Test.
Well, no, FlyingObject.cycle has this look:
fun cycle(drawer: Drawer, seconds: Double, deltaTime: Double) {
drawer.isolated {
update(deltaTime)
draw(drawer)
}
}
I either need to call update, or to deal with the absence of a drawer, and of seconds. For purposes of this test, let’s just call update throughout.
With those changes in place, the test fails. Let’s check where the asteroid is:
for (i in 1..12) game.update(1.0/60.0)
val x = asteroid.position.x
val y = asteroid.position.y
assertThat(x).isEqualTo(100.0+12*50.0)
assertThat(y).isEqualTo(100.0+12*50.0)
assertThat(game.colliderCount()).isEqualTo(2)
I note with some joy that if the velocity is 50,50 we can check x and y separately and simply. I note with only some surprise that the results are this:
for (i in 1..12) game.update(1.0/60.0)
val x = asteroid.position.x
val y = asteroid.position.y
assertThat(x).isEqualTo(100.0+12*50.0)
assertThat(y).isEqualTo(100.0+12*50.0)
assertThat(game.colliderCount()).isEqualTo(2)
I needed to move for 12 seconds, not 12 60ths. Clever boy. Let’s fix that:
for (i in 1..12*60) game.update(1.0/60.0)
Test again. LOL. Forgot the error factor:
expected: 700.0
but was: 700.0000000004366
You’d think they’d let me slide for that, but no. OK …
for (i in 1..12*60) game.update(1.0/60.0)
val x = asteroid.position.x
val y = asteroid.position.y
assertThat(x).isEqualTo(100.0+12*50.0, within(0.1))
assertThat(y).isEqualTo(100.0+12*50.0, within(0.1))
assertThat(game.colliderCount()).isEqualTo(2)
And we are green: the two objects have collided.
Excuse me while I run naked in the streets shouting Eureka!
What we have just seen, witnessed with our own eyes, is that the game, iterating in 60ths of a second, has moved the asteroid in the indicated direction and that, having moved it, our two objects are now colliding even though they were not colliding when we started.
This is excellent progress. We’ll want to sort out the issue with the Drawer, and we’ll want to decide whether the game checks for colliders or whether Flyers automatically returns them. I am leaning toward the former. In fact, let’s think about this for a moment …
Maybe flyers shouldn’t know about colliders at all. Maybe, instead, it should just know how to produce pairs that meet a provided criterion, and Game should know about the criterion.
Yes, after a brief walk down the hall, I think that Flyers shouldn’t know any methods of its contents. In principle it could have a collection of any type. (In what follows I do not plan to convert it to a more open type, but I do think we should remove those methods.)
Let’s start with update. We’ll change Game’s update:
fun update(deltaTime: Double) = flyers.perform { it.update(deltaTime)}
I’m positing the method perform on Flyers:
fun perform(f: (FlyingObject)->Unit) {
flyers.forEach(f)
}
The tests run and I can remove Flyers.update. It seems that the method perform “should” be called forEach. Can I give it that name? Yes. Test, green, commit: Implement Flyers.forEach and use to remove update from Flyers.
Now how about colliders? Generalizing that function:
fun colliders(): Set<FlyingObject> {
val colliding = mutableSetOf<FlyingObject>()
pairsToCheck().forEach { p ->
if (p.first.collides(p.second)) {
colliding.add(p.first)
colliding.add(p.second)
}
}
return colliding
}
We’ll want to pass in a lambda taking two parameters, each a FlyingObject, returning a boolean. We want to return the individual objects from each pair such that the lambda returns true.
I’m quite sure how to do this.
Let’s try to create the lambda inside colliders first:
fun colliders(): Set<FlyingObject> {
val areColliding =
{f1:FlyingObject,f2: FlyingObject ->
f1.collides(f2)}
val colliding = mutableSetOf<FlyingObject>()
pairsToCheck().forEach { p ->
if (areColliding(p.first, p.second)) {
colliding.add(p.first)
colliding.add(p.second)
}
}
return colliding
}
This should run. It does. Now let’s extract everything after assigning the areColliding:
fun colliders(): Set<FlyingObject> {
val areColliding = { f1: FlyingObject, f2: FlyingObject -> f1.collides(f2) }
return pairsSatisfying(areColliding)
}
fun pairsSatisfying(pairCondition: (FlyingObject, FlyingObject) -> Boolean): MutableSet<FlyingObject> {
val pairs = mutableSetOf<FlyingObject>()
pairsToCheck().forEach { p ->
if (pairCondition(p.first, p.second)) {
pairs.add(p.first)
pairs.add(p.second)
}
}
return pairs
}
IDEA extract method and a bit of renaming and we have that. Now let’s move the colliders method over to game. Will IDEA do that? Not offhand, but I can:
class Game ...
fun colliderCount(): Int = colliders().size
private fun colliders(): Set<FlyingObject> {
val areColliding = { f1: FlyingObject, f2: FlyingObject -> f1.collides(f2) }
return flyers.pairsSatisfying(areColliding)
}
Test. Oops. I have tests assuming that colliders exists on Flyers. I can fix them both by changing them to refer to game, I think:
@Test
fun `collision detection`() {
val game = Game()
val a = FlyingObject.asteroid(Vector2(100.0,100.0), Vector2(50.0,50.0))
game.add(a)
val s = FlyingObject.ship(Vector2(100.0, 150.0))
game.add(s)
assertThat(game.flyers.size).isEqualTo(2)
val colliders = game.colliders()
assertThat(colliders.size).isEqualTo(2)
}
Test … that one’s OK, do the other …
@Test
fun `stringent colliders`() {
val p1 = Vector2(100.0,100.0)
val p2 = Vector2(500.0, 500.0)
val game = Game()
val v = Vector2.ZERO
val a0 = FlyingObject.asteroid(p1,v) // yes
game.add(a0)
val m1 = FlyingObject(p1, v, Vector2.ZERO, 10.0) // yes
game.add(m1)
val s2 = FlyingObject.ship(p1) // yes
game.add(s2)
val a3 = FlyingObject.asteroid(p2,v) // no
game.add(a3)
val a4 = FlyingObject.asteroid(p2,v) // no
game.add(a4)
val colliders = game.colliders()
assertThat(colliders.size).isEqualTo(3)
}
We’re nearly at 500 lines here and just about 3 hours in, so let’s lift our heads and sum up.
Summary
We’ve accomplished two things. We have a rudimentary Game object that can add flying objects and find colliders. Supporting that Game (and written first) we have the Flyers object, which is a smart collection containing flying objects, although it scarcely knows what type they are.
The Flyers collection can perform any function on each flyer by providing forEach. And it can produce pairs satisfying any condition, using its method pairsSatisfying(lambda).
Our tests have accomplished this scenario:
- Create a game with an asteroid moving at 50x50, and a ship, far away from it.
- Cycle the game 720 times, which moves the asteroid close enough to the ship to kill it.
- Show that both the asteroid and the ship are returned as having collided.
Ladies, gentlemen, others, brothers, sisters and siblings, what we have here is nearly a game.
Today’s experience has made me think, only vaguely so far, about the provision of a Drawer and such. I have this in FlyingObject, which is a bit troubling:
fun cycle(drawer: Drawer, seconds: Double, deltaTime: Double) {
drawer.isolated {
update(deltaTime)
draw(drawer)
}
}
What we saw this morning was that the update cycle and the drawing cycle need to be separate, at least for testing purposes. We may find that we want the game to first update everyone and then, perhaps only if it happens to have a Drawer, draw everyone. That would also give it a chance to remove anything that’s destroyed, and to put fireworks in its place, if we offer such visual effects.
That remains to be seen, but our experience here is suggesting that separation.
I think what I’ll do next, though perhaps not tomorrow, since that’s Sunday, when I often have a truncated session terminated by bacon, but next or soon, we’ll make the game we just implemented draw itself on the screen.
For now, I think Game and Flyers have turned out rather nicely. So nicely that we’ll admire them below. See you next time!
class Game {
val flyers = Flyers()
fun add(fo: FlyingObject) = flyers.add(fo)
fun colliderCount(): Int = colliders().size
fun colliders() = flyers.pairsSatisfying { f1, f2 -> f1.collides(f2) }
fun update(deltaTime: Double) = flyers.forEach { it.update(deltaTime)}
}
class Flyers {
private val flyers = mutableListOf<FlyingObject>()
fun add(flyer: FlyingObject) {
flyers.add(flyer)
}
private fun pairsToCheck(): List<Pair<FlyingObject, FlyingObject>> {
val pairs = mutableListOf<Pair<FlyingObject, FlyingObject>>()
flyers.indices.forEach() { i ->
flyers.indices.minus(0..i).forEach() { j ->
pairs.add(flyers[i] to flyers[j])
}
}
return pairs
}
fun pairsSatisfying(
pairCondition: (FlyingObject, FlyingObject) -> Boolean
): MutableSet<FlyingObject> {
val pairs = mutableSetOf<FlyingObject>()
pairsToCheck().forEach { p ->
if (pairCondition(p.first, p.second)) {
pairs.add(p.first)
pairs.add(p.second)
}
}
return pairs
}
fun forEach(f: (FlyingObject)->Unit) = flyers.forEach(f)
val size get() = flyers.size
}
P.S. I’m not sure about pairsSatisfying as a name, since it doesn’t return pairs but items. But flyersSatisfyiingArbitraryConditionPairwise seems a bit long.