Dungeon - 2
Today, I think, separation of the primeval blob of rooms.
While I dither internally over the possible downfall of democracy, I’ll dither over this little dungeon experiment. I remain kind of convinced that this won’t go well, but it could just be residual concern over the state of reality. At any rate, our mission this morning will be to spread out the blob of rooms that our random room-drawing algorithm produces.
As you can see in the picture, offline I added in colored display of test results. I also put that feature into my Codea CUBase file, which can be used to create new projects that use CodeaUnit. And, as was intended, running the tests reminds me that I wanted to look at those intersection tests to make sure they were reasonable.
Having refreshed my memory from yesterday, I guess we wanted the rectangle intersection thing to use in separation, since we want at least to be separated from any rectangle that overlaps ours. OK, might be a good idea, we’ll see. Anyway, the test:
_:test("rooms intersect", function()
_:expect(2, "check all these for proper CENTER handling").is(3)
local r1,r2,r3,r4, r5
r1 = Room(100,100, 20, 20)
r2 = Room(120,100, 20,20)
_:expect(r1:intersects(r2)).is(true)
r3 = Room(130,130, 20,20)
_:expect(r1:intersects(r3), "room3").is(false)
r4 = Room(119,100,20,20)
_:expect(r1:intersects(r4), "room4").is(true)
r5 = Room(121,100,20,20)
_:expect(r1:intersects(r5), "room5").is(false)
end)
There’s the handy expectation that I set at the beginning to force a red bar. I think I’ll comment the rooms with their bounds. Hey, how about if a room could tell us its bounds, that would be nice: we could actually check to see if we get what I expect.
An issue here is this: Suppose that we have a rectangle centered at (1,1) and its width, height is (2,3). What are its bounds. The y bounds seem easy: should be 0 and 2, so that the rectangle is three high, 0,1,2 with one nicely centered.
What about the x bounds? If it’s to be two units wide, does it cover x = 1,2, or 0,1? Or, if you’re all about arithmetic, does it span from 0.5 to 1.5?
What I’ve decided in the actual code is this:
function Room:intersects(aRoom)
return intersectCorners(self:corners(), aRoom:corners())
end
function intersectCorners(corners1, corners2)
x1lo, y1lo, x1hi, y1hi = unpack(corners1)
print(x1lo," ",y1lo," ",x1hi," ",y1hi)
x2lo, y2lo, x2hi, y2hi = unpack(corners2)
print(x2lo," ",y2lo," ",x2hi," ",y2hi)
if y1lo > y2hi or y2lo > y1hi then return false end
if x1lo > x2hi or x2lo > x1hi then return false end
return true
end
function Room:corners()
local hw = self:halfWidth()
local hh = self:halfHeight()
return {self.x - hw, self.y - hh, self.x + hw, self.y + hh}
end
function Room:halfWidth()
return math.ceil(self.w/2)
end
function Room:halfHeight()
return math.ceil(self.h/2)
end
This code forces integer results on the bounds of the box, the corners function, by using the ceiling of half the width and height of the rectangle in question.
I am obsessing over this because of some kind of concern about getting the pixels in the right place, left over from the Invaders program, where pixel collisions were a thing. In that program, all the screen stuff was bitmaps, and I knew their actual width and height, and whether any given pixel was supposed to be on or off.
This may not be necessary here at all. What if we just let the computer do the arithmetic, so that a 2x3 rectangle centered at 1,1 spans 0-2 in x and -0.5 through 1.5 in y? What if we just ignored the fractional pixels?
You’re probably thinking I’m off my nut here.
Yes. Yes, I am. Let’s just let the math do what the math does. So first, I’ll change the code and see what breaks.
function Room:halfWidth()
return self.w/2
end
function Room:halfHeight()
return self.h/2
end
Running the tests … they all still pass, but I think I’d like to check to be sure I like the particulars.
Progress report:
_:test("rooms intersect", function()
local r1,r2,r3,r4, r5
r1 = Room(100,100, 20, 20)
checkCorners(r1, 90,90,110,110)
r2 = Room(120,100, 20,20)
checkCorners(r2, 110, 90, 130, 110)
_:expect(r1:intersects(r2)).is(true)
r3 = Room(130,130, 20,20)
_:expect(r1:intersects(r3), "room3").is(false)
r4 = Room(119,100,20,20)
_:expect(r1:intersects(r4), "room4").is(true)
r5 = Room(121,100,20,20)
_:expect(r1:intersects(r5), "room5").is(false)
end)
function checkCorners(room, a,b,c,d)
local aa,bb,cc,dd = unpack(room:corners())
_:expect(aa,"xLo").is(a)
_:expect(bb,"yLo").is(b)
_:expect(cc,"xHi").is(c)
_:expect(dd,"yHi").is(d)
end
I wrote this handy check function and am calling it, putting in my hand-calculated values and checking the computer ones. (I don’t really calculate those ones by hand, I do it in my head, except for the hard ones.)
So the first two rooms. r1 extends up to x = 110, with y from 90 to 110. And r2 goes from x = 110, with y from 90 to 110. So these two rooms share part of a wall:
if y1lo > y2hi or y2lo > y1hi then return false end
if x1lo > x2hi or x2lo > x1hi then return false end
The current intersection code says they do not intersect. But why? Because these comparisons are strict. In the case in hand, we have x1hi = x2lo = 110. Had x2lo been a tiny fraction more, they’d not have intersected. Let’s make that our next test instead of whatever’s there.
r3 = Room(120.01,110, 20,20)
_:expect(r1:intersects(r3), "room3").is(false)
That passes, they do not intersect, as intended. Let’s next test what would happen had r2’s dimensions been just a bit smaller.
r4 = Room(120,100,19.99,19.99)
_:expect(r1:intersects(r4), "room4").is(false)
Now I think I’m happy. What about the current r5 test:
r5 = Room(121,100,20,20)
_:expect(r1:intersects(r5), "room5").is(false)
That’s redundant now that the others are tighter. I’ll remove that one.
All green. What about that other test, for the odd numbers:
_:test("odd size rooms intersect", function()
local r1,r2
r1 = Room(100,100,5,5) -- 98-102
r2 = Room(105,105,5,5) -- 103-107
_:expect(r1:intersects(r2)).is(true)
end)
That’s still passing, but the comments are wrong, and we have a new checkCorners that we can use to make our comment executable:
_:test("odd size rooms intersect", function()
local r1,r2
r1 = Room(100,100,5,5)
checkCorners(r1, 97.5, 97.5, 102.5, 102.5)
r2 = Room(105,105,5,5)
checkCorners(r2, 102.5, 102.5, 107.5, 107.5)
_:expect(r1:intersects(r2)).is(true)
end)
So that’s nice. I’d like to talk now about why I’ve been so obsessive about this trivial issue when the code “clearly works”.
Obsession
This rectangle intersection code clearly works. Why did I obsess over it so much, and test it so carefully? I have some good reasons and some other reasons.
First, I expect the rectangle intersection issue to be critical for what comes next, spreading out the rooms. I understand the room-spreading algorithm at best vaguely, and I expect to make mistakes implementing it. I would like those mistakes not to be compounded by something slightly wrong with one of the key functions I plan to use.
Second, the rectangle intersection notion is a bit odd:
If your lower is higher than his higher then you don’t intersect, and if his lower is higher than your higher you also don’t intersect.
That’s backward logic and it’s easy to get wrong.
Third, the code I wrote still doesn’t communicate as well as it might:
function intersectCorners(corners1, corners2)
x1lo, y1lo, x1hi, y1hi = unpack(corners1)
x2lo, y2lo, x2hi, y2hi = unpack(corners2)
if y1lo > y2hi or y2lo > y1hi then return false end
if x1lo > x2hi or x2lo > x1hi then return false end
return true
end
Since it doesn’t communicate as well as I’d like, it deserves more tests.
Furthermore, I’m terrible at visualizing geometry with numbers attached and getting it right, and I’ve gone through three different models of rectangles in just two articles: half width integer, half-width integer ceiling, and plain old floating half width. That’s enough to make anyone think they could be wrong.
Penultimately, my mind is contaminated by the work I did on Invaders to get the pixel bitmaps to line up. Whether that was well done or not, it left me with uncertainty in this new situation.
Finally, I’m trying to get into the mode of thinking in terms of tests for at least the parts of this program that can be tested. So I’m focusing there perhaps harder than I normally would.
You decide which of those reasons are good and which are other.
Now then …
Can we work on separation, please?
Long ago in 1986, there was a program called Boids, that simulated flocking behavior. What was cool about it was that it created really nice flocking behavior by considering only three rules for individual birds, with no central coordination. The rules were:
- Steer to stay sufficiently separated;
- Steer in the general direction of the flock;
- Steer toward the center of the flock.
Depending on the weights you apply to these rules, you get different sorts of flocking, most of which look quite natural.
What is done in some dungeon programs is to use the separation behavior idea from Boids to separate our overlapping rooms just enough. And when I say “some dungeon programs”, I mean this one.
Based on my rough understanding of the ideas here, my plan is this:
For each room, find all the rooms that intersect it. Push the room away from the intersecting rooms, perhaps proportionately to how close they are. Repeat until there are no rooms with intersecting rooms.
This will be done iteratively (obviously) and I plan to do it slowly enough that we can watch it on the screen.
I mention “perhaps proportionately to how close they are”. The algorithms you find on line tend to adjust a vector for the movement this way:
v += neighbor.pos - me.pos
After this is added up, it’s normalized, but it seems to me that this rule gives greater weight to the neighbors who are further away. A neighbor right on top of me would have almost no impact. So I think that we need to consider the distance, inversely.
Oh, yay, I found an article that agrees with me. Check out the separate function.
// Separation
// Method checks for nearby boids and steers away
PVector separate (ArrayList<Boid> boids) {
float desiredseparation = 25.0f;
PVector steer = new PVector(0, 0, 0);
int count = 0;
// For every boid in the system, check if it's too close
for (Boid other : boids) {
float d = PVector.dist(position, other.position);
// If the distance is greater than 0 and less than an arbitrary amount (0 when you are yourself)
if ((d > 0) && (d < desiredseparation)) {
// Calculate vector pointing away from neighbor
PVector diff = PVector.sub(position, other.position);
diff.normalize();
diff.div(d); // Weight by distance
steer.add(diff);
count++; // Keep track of how many
}
}
// Average -- divide by how many
if (count > 0) {
steer.div((float)count);
}
// As long as the vector is greater than 0
if (steer.mag() > 0) {
// First two lines of code below could be condensed with new PVector setMag() method
// Not using this method until Processing.js catches up
// steer.setMag(maxspeed);
// Implement Reynolds: Steering = Desired - Velocity
steer.normalize();
steer.mult(maxspeed);
steer.sub(velocity);
steer.limit(maxforce);
}
return steer;
}
I’m goin in. We want a function that separates our rooms, that we can call iteratively until it’s done. Can we TDD this? Let’s try. Here are two rooms, square root of two apart:
_:test("separation", function()
local r1 = Room(100,100,5,5)
local r2 = Room(101,101,5,5)
local d = vec2(100,100):dist(vec2(101,101))
_:expect(d).is(1.414, .05)
end)
Let’s assume a function … that what? We could go top down, writing a function stepApart that takes a collection of rooms and iterates over them. Or we could go more bottom up and compute the impact vector of one room on another. Let’s do that. I’m usually more inclined to go top down but this time that feels like it’d be a long time before anything really worked.
I think I want to push my distance calculation into the Room class:
_:test("separation", function()
local r1 = Room(100,100,5,5)
local r2 = Room(101,101,5,5)
local d = r1:dist(r2)
_:expect(d).is(1.414, .05)
end)
function Room:dist(aRoom)
return self:center():dist(aRoom:center())
end
function Room:center()
return vec2(self.x,self.y)
end
That feels like some progress. Now I’m going to sketch some code here just to get a feeling for where this goes:
given Room me
adjustment = 0
n = 0
for him in all the rooms
if he isn't me then
adjustment += his normalized impact
n = n + 1
end
adjustment = adjustment/n
me.center += adjustment
Something like that. So I want normalized impact. Stealing from that page I linked to, that’s the normalized vector from him to me, divided by his distance.
So …
_:test("separation", function()
local r1 = Room(100,100,5,5)
local r2 = Room(101,101,5,5)
local d = r1:dist(r2)
_:expect(d).is(1.414, .05)
local adj = r1:impactOf(r2)
_:expect(adj).is(vec2(0,0))
end)
I’m not sure what this should return. I think it should be the vector (1,1) divided by its length (1.414) so that’s (.707,.707). I may be quite wrong. So to implement:
function Room:impactOf(aRoom)
return (self:center()-aRoom:center())/self:dist(aRoom)
end
And the test says:
4: separation -- Actual: (-0.707107, -0.707107), Expected: (0.000000, 0.000000)
Yes. makes sense. I wonder if I have a handler for approximate vectors in CodeaUnit, like I do for floats. I don’t think I do. And I do not. So, for now:
_:test("separation", function()
local r1 = Room(100,100,5,5)
local r2 = Room(101,101,5,5)
local d = r1:dist(r2)
_:expect(d).is(1.414, .05)
local adj = r1:impactOf(r2)
checkVector(adj, vec2(-0.707, -0.707))
end)
function checkVector(v1,v2)
_:expect(v1.x).is(v2.x,0.05)
_:expect(v1.y).is(v2.y,0.05)
end
So that works well enough. I’m going to commit, “utility room functions” and then I’m going in.
I think I’ve got enough foundation here to write my separation code. This will surely be interesting, and probably a disaster. But I’ll learn something, hopefully something more than “don’t ever do that again”.
Our draw function is this:
function draw()
if CodeaUnit then showCodeaUnitTests() end
pushMatrix()
pushStyle()
rectMode(CENTER)
for i,r in ipairs(Rooms) do
r:draw()
end
popStyle()
popMatrix()
end
If we were to wait a half second and then do one separation cycle, we’d probably have a nice video of the screen being destroyed. So …
function draw()
if CodeaUnit then showCodeaUnitTests() end
pushMatrix()
pushStyle()
rectMode(CENTER)
for i,r in ipairs(Rooms) do
r:draw()
end
separate()
popStyle()
popMatrix()
end
function separate()
if ElapsedTime - ET > 0.5 then
ET = ElapsedTime
doOneSeparation()
end
end
And …
function doOneSeparation()
for i,r in ipairs(Rooms) do
local ints = intersectors(r1,Rooms)
local adj = vec2(0,0)
for j,s in ipairs(ints) do
adj = adj + r:impactOf(s)
end
adj = adj/#ints
r:moveBy(adj)
end
end
Loop over all rooms, get the room’s intersectors, for those get the adjustment, sum up the adjustments, divide by however many there are, and move the room that much.
Might work. Another function to write and a method on Room.
function Room:moveBy(aVector)
self.x = self.x + aVector.x
self.y = self.y + aVector.y
end
That’s the easy one … and …
function intersectors(room, rooms)
local result = {}
for i,r in ipairs(rooms) do
if room:intersects(r) then
table.insert(result,r)
end
end
return result
end
This might work. I’m gonna run it.
Main:48: attempt to index a nil value (local 'room')
stack traceback:
Main:48: in function 'intersectors'
Main:35: in function 'doOneSeparation'
Main:29: in function 'separate'
Main:21: in function 'draw'
Oh cute, I said r1 in the call to intersectors. Try:
function doOneSeparation()
for i,r in ipairs(Rooms) do
local ints = intersectors(r,Rooms)
local adj = vec2(0,0)
for j,s in ipairs(ints) do
adj = adj + r:impactOf(s)
end
adj = adj/#ints
r:moveBy(adj)
end
end
The result of running this is so fast that I can’t make a video of it. Here’s a picture of the screen a half second after the program starts:
All the rooms just vanish. I wonder where they went. Let’s see if we can test our two rooms in this test:
_:test("separation", function()
local r1 = Room(100,100,5,5)
local r2 = Room(101,101,5,5)
local d = r1:dist(r2)
_:expect(d).is(1.414, .05)
local adj = r1:impactOf(r2)
checkVector(adj, vec2(-0.707, -0.707))
end)
I should be able to call my doOneSeparation function from here.
_:test("separation", function()
local r1 = Room(100,100,5,5)
local r2 = Room(101,101,5,5)
local d = r1:dist(r2)
_:expect(d).is(1.414, .05)
local adj = r1:impactOf(r2)
checkVector(adj, vec2(-0.707, -0.707))
local others = { r2 }
doOneSeparation(r1,others)
_:expect(r1:center()).is(vec2(100,100))
end)
It surely won’t be where it was, but you’d hope it wouldn’t be far off. However:
4: separation -- attempt to index a nil value
But where?
Oh, well, doOneSeparation doesn’t work the way I think it does. Let’s refactor:
function doOneSeparation()
for i,r in ipairs(Rooms) do
separateOneRoom(r,Rooms)
end
end
function separateOneRoom(room, rooms)
local ints = intersectors(room,rooms)
local adj = vec2(0,0)
for j,s in ipairs(ints) do
adj = adj + room:impactOf(s)
end
adj = adj/#ints
room:moveBy(adj)
end
Now I have a function more like what the test wants:
_:test("separation", function()
local r1 = Room(100,100,5,5)
local r2 = Room(101,101,5,5)
local d = r1:dist(r2)
_:expect(d).is(1.414, .05)
local adj = r1:impactOf(r2)
checkVector(adj, vec2(-0.707, -0.707))
local others = { r2 }
separateOneRoom(r1,others)
_:expect(r1.x, "x").is(100)
_:expect(r1.y, "y").is(100)
end)
That fails as I’d hope it would:
4: separation x -- Actual: 99.292893218813, Expected: 100
4: separation y -- Actual: 99.292893218813, Expected: 100
I’m not sure about that but 99.29 + 0.707 is a lot like 100, so this might be good. Now back to the main show.
_:test("separation", function()
local r1 = Room(100,100,5,5)
local r2 = Room(101,101,5,5)
local d = r1:dist(r2)
_:expect(d).is(1.414, .05)
local adj = r1:impactOf(r2)
checkVector(adj, vec2(-0.707, -0.707))
local others = { r2 }
separateOneRoom(r1,others)
_:expect(r1.x, "x").is(99.27,0.05)
_:expect(r1.y, "y").is(99.27,0.05)
end)
I don’t think I’ve changed anything that should fix that explosion behavior, but let’s see what it does. Right, they all still vanish. Oh, what about that intersection thing? I’m not tossing out the room I’m checking. That will cause it to move itself infinity squares in some direction. Let’s try this:
function intersectors(room, rooms)
local result = {}
for i,r in ipairs(rooms) do
print(i,r)
if r ~= room and room:intersects(r) then
table.insert(result,r)
end
print("after", i, r)
end
return result
end
Now the behavior is slightly less bizarre, they move a time or two and then all disappear. Also, the separation logic never stops. Let’s give it a maximum number of cycles, which we can also use to conveniently give it just one. And maybe drive it from touch rather than the clock.
In fact let’s just move it to touched and belay the counter and display loop for now.
function touched(touch)
if touch.state == ENDED then doOneSeparation() end
end
I think this thing is looping forever. The behavior is a bit random as well. This is why we don’t take big leaps. Lunch time is coming up, we need to at least learn something.
Let’s check that the intersectors isn’t returning the source guy:
_:test("intersectors does not contain original", function()
local r1 = Room(100,100,5,5)
local r2 = Room(101,101,5,5)
local all = {r1,r2}
local int = intersectors(r1, all)
_:expect(int).has(r2)
_:expect(int).hasnt(r1)
end)
This passes. So I’m pretty sure I’m not moving myself away based on how close I am to myself. However … if two rectangles are really close, the impact vector could still be quite significant, divided by distance, which could be quite small. I want to take out that divide and just move by the normalized amounts, which should be very small. So small that I’ll probably need to bump them up a bit.
function Room:impactOf(aRoom)
return (self:center()-aRoom:center())
end
With just this change I’ll try again.
(I should be giving up soon, recognizing that this was too big a bite for some reason, probably a stilly one. But not yet. I’m on the trail …)
I did see an incremental movement, but it’s still acting as if it’s in an infinite loop: Codea returns to source mode slowly, and sometimes I have to terminate it and restart.
I added a print:
function separateOneRoom(room, rooms)
local ints = intersectors(room,rooms)
print(#ints, " intersectors")
local adj = vec2(0,0)
for j,s in ipairs(ints) do
adj = adj + room:impactOf(s)
end
adj = adj/#ints
room:moveBy(adj)
end
This prints how many intersectors there are each time do do a room. (We are doing all rooms.) The results are interesting. Sometimes, the first time I touch, I get a series of small counts for intersectors. The second time, the counts are all quite large.
However, somehow in all this, some tests have broken as well.
4: separation -- Actual: -1.0, Expected: -0.707
4: separation -- Actual: -1.0, Expected: -0.707
4: separation x -- Actual: 99.0, Expected: 99.27
4: separation y -- Actual: 99.0, Expected: 99.27
Oh, I took out the divide by distance, which changes the answers here:
_:test("separation", function()
local r1 = Room(100,100,5,5)
local r2 = Room(101,101,5,5)
local d = r1:dist(r2)
_:expect(d).is(1.414, .05)
local adj = r1:impactOf(r2)
checkVector(adj, vec2(-0.707, -0.707))
local others = { r2 }
separateOneRoom(r1,others)
_:expect(r1.x, "x").is(99.27,0.05)
_:expect(r1.y, "y").is(99.27,0.05)
end)
It’s a bit past time to go for lunch, and I’m clearly lost. I should revert but I’m not going to, at least not until I look at this with fresh eyes.
No. Have some guts, Ron. Revert it is. Done. All that stuff, washed away, tears in the rain.
I’m not sure if I’ll close this article, or continue after lunch. We’ll find out soon.
Later …
Well, I’ve had lunch, done some reading, and had a little siesta. Let’s take another look at this thing, and try some TDD on it while we’re at it.
Where are we?
Here’s the most recent test:
_:test("separation", function()
local r1 = Room(100,100,5,5)
local r2 = Room(101,101,5,5)
local d = r1:dist(r2)
_:expect(d).is(1.414, .05)
local adj = r1:impactOf(r2)
checkVector(adj, vec2(-0.707, -0.707))
end)
The definition of impactOf is:
function Room:impactOf(aRoom)
return (self:center()-aRoom:center())/self:dist(aRoom)
end
I think that’s wrong according to what I’ve read. We need to normalize the vector pointing away, not just scale it. Let’s also check it for not being right on top of us, and leave out the division by dist for now:
function Room:impactOf(aRoom)
local d = self:dist(aRoom)
if d == 0 then return vec2(0,0) end
return (self:center()-aRoom:center()):normalize()
-- used to divide by dist to adjust impact
end
This still returns the same (-0.707, -0.707) that we had before. That’s because hmm normalizing amounts to dividing a vector by its length. So this isn’t much of a change, really. Makes me wonder what else has been going on.
In any case I’m going to continue this time with TDD. Let’s try accumulating (and averaging) the impact of more than one neighbor. And let’s start by finding neighbors from a collection, including those who intersect with us, and not including ourselves.
_:test("intersectors", function()
local r1 = Room(100,100,5,5)
local r2 = Room(101,101,5,5)
local r3 = Room(99,99,5,5)
local r4 = Room(106,106,5,5)
local all = {r1,r2,r3,r4}
local int = r1:intersectors(all)
_:expect(int).hasnt(r1)
_:expect(int).hasnt(r4)
_:expect(int).has(r2)
_:expect(int).has(r3)
end)
We’ll leave it to a room to identify its intersectors:
function Room:intersectors(rooms)
local int = {}
for i,r in ipairs(rooms) do
if self ~= r and self:intersects(r) then
table.insert(int,r)
end
end
return int
end
That works. Can you feel, as I can, that this is going better than last time? This so often happens. “When you find you’re on a hole, stop digging.”
Let’s test the combined impact of a collection:
_:test("combined impact", function()
local r1 = Room(100,100,5,5)
local r2 = Room(101,101,5,5)
local r3 = Room(99,99,5,5)
local r4 = Room(106,106,5,5)
local all = {r1,r2,r3,r4}
local v = r1:combinedImpactOf(all)
_:expect(v).is(vec2(10,10))
end)
I think this combined impact is going to be zero, and we’ll probably want to change the test or add one, but for now, I’m pretty sure it isn’t (10,10).
function Room:combinedImpactOf(rooms)
local imp = vec2(0,0)
for i,r in ipairs(rooms) do
imp = imp + self:impactOf(r)
end
return imp/#rooms
end
We add them up and average them. Let’s see what the test says:
6: combined impact -- Actual: (-0.176777, -0.176777), Expected: (10.000000, 10.000000)
That number doesn’t remind me of anything. Oh. We forgot to do the intersect. That’s a bug:
function Room:combinedImpactOf(allRooms)
local rooms = self:intersectors(allRooms)
local imp = vec2(0,0)
for i,r in ipairs(rooms) do
imp = imp + self:impactOf(r)
end
return imp/#rooms
end
That’s surely better. How better is it?
6: combined impact -- Actual: (0.000000, 0.000000), Expected: (10.000000, 10.000000)
That’s what I expected. But let’s get a real result. We have one where we want to go diagonally southwest to get away from it, and one where we want to go diagonally northeast, and they cancel out. Let’s add one to force us southeast, maybe like this:
_:test("combined impact", function()
local r1 = Room(100,100,5,5)
local r2 = Room(101,101,5,5)
local r3 = Room(99,99,5,5)
local r4 = Room(106,106,5,5)
local r5 = Room(99,101,5,5)
local all = {r1,r2,r3,r4,r5}
local v = r1:combinedImpactOf(all)
checkVector(v, vec2(0.707,-0.707))
end)
Hm, we get:
6: combined impact x -- Actual: 0.23570226039552, Expected: 0.707
6: combined impact y -- Actual: -0.23570226039552, Expected: -0.707
What have I missed? I’m going to try just r1 and r5 alone, manually, and see if I get what I expect. And I do. Now I also expect that the sum of all three of our matches is also (0.707,-0.707), so it seems to me that the value I get should be 1/3 of that. Oh, you mean it should be 0.235 … like it was?
Yeah, so that was actually right. :)
This is an interesting value of tests. Sometimes they surprise you into figuring out what you’ve done and what the impact is. But you can get so used to being wrong that it’s a surprise when you’re right. Does that happen to you? Anyone? Bueller?
OK, it happens to me.
So now we have a convenient function, Room:combinedImpactOf that tells us how much to move a room based on the impact of all the other rooms. The function limits its attention to rooms that intersect the room in question.
It seems to me that we can now write a function that will move all the rooms in a collection. And by golly, I’m gonna write it and run it on the big picture.
Can I reasonably write a test for this? It would require more thinking than I’m up for. Let’s just code this baby up.
I’d like the function to return the number of rooms that it moved. That might be useful for knowing when to stop.
Oh. As soon as I start to write this I realize I want at least one more method, one that adjusts a room given the combined impact of a collection of possibly intersecting rooms. That, we can TDD. In fact, I’ll just add a check to our most recent test, something like this:
_:test("combined impact", function()
local r1 = Room(100,100,5,5)
local r2 = Room(101,101,5,5)
local r3 = Room(99,99,5,5)
local r4 = Room(106,106,5,5)
local r5 = Room(99,101,5,5)
local all = {r1,r2,r3,r4,r5}
local v = r1:combinedImpactOf(all)
checkVector(v, vec2(0.235,-0.235))
r1:moveAwayFrom(all)
checkVector(r1:center(), vec2(100,100)-v)
end)
We started at 100,100, we calculated we should move by v, let’s see if we did. So:
function Room:moveAwayFrom(rooms)
local v = self:combinedImpactOf(rooms)
local pos = self:center() + v
self.x = pos.x
self.y = pos.y
end
Oh. Should be +v:
_:test("combined impact", function()
local r1 = Room(100,100,5,5)
local r2 = Room(101,101,5,5)
local r3 = Room(99,99,5,5)
local r4 = Room(106,106,5,5)
local r5 = Room(99,101,5,5)
local all = {r1,r2,r3,r4,r5}
local v = r1:combinedImpactOf(all)
checkVector(v, vec2(0.235,-0.235))
r1:moveAwayFrom(all)
checkVector(r1:center(), vec2(100,100)+v)
end)
Test runs. Now I can do my do ‘em all function:
-- class method
function Room:adjustAll(rooms)
for i,room in ipairs(rooms) do
room:moveAwayFrom(rooms)
end
end
And I can put it in touched and see what happens.
function touched(touch)
if touch.state == ENDED then
Room:adjustAll(Rooms)
end
end
Now I can test this by touching the screen to see what happens. I think I’ll reduce the room count to 20 first.
Disappointingly, this seems to do much as it did before, moving most of the rectangles clear off screen.
Let’s do a call to this new function inside our TDD, see what happens.
Ah. I put an example set of rooms on the screen and ran the program. Here’s what we see:
They move apart as one might expect … until they separate, at which point they vanish? Why? Division by zero, perhaps?
function Room:combinedImpactOf(allRooms)
local rooms = self:intersectors(allRooms)
local imp = vec2(0,0)
for i,r in ipairs(rooms) do
imp = imp + self:impactOf(r)
end
return imp/#rooms
end
No intersections, divide by zero. Which apparently doesn’t explode quite as one might like. I’ll bet that’s it tho. Let’s fix that:
function Room:combinedImpactOf(allRooms)
local rooms = self:intersectors(allRooms)
if #rooms == 0 then return vec2(0,0) end
local imp = vec2(0,0)
for i,r in ipairs(rooms) do
imp = imp + self:impactOf(r)
end
return imp/#rooms
end
Now let’s see what we see.
There we go. Now I’m going to try it with a random batch. It’ll take a bunch of moves. Did I put in that thing that counts how many were moved? I don’t remember. Anyway, first the manual test.
Ha! Take that!
Starting here:
After lots of taps, we end up here:
It works!
Commit: separation works. Let’s sum up.
Summing Up
Well. That was interesting. I suspect the screen disappearing was always due to something like the divide by zero, but we’ll never know now. We know that the last problem (so far) was due to that. I also wonder why I can divide by zero without an error arising but it seems that I can.
The first time around, I really didn’t see good ways to TDD further than the low-level routines that I did test. Second time around, I had a better sense of what the overall structure would be, and that led me to a way of breaking it down such that I could test each additional step, up until the last one.
So, reverting was good, and while it might have been better to go sooner, the afternoon’s effort only took 60 or 90 minutes and we have code we can almost be proud of.
I call that good. See you next time. If you want me to export the code for this, let me know, otherwise I’ll hold off.