Dung 7: A Mistake! He Made a Mistake!
My recursive pathfinder doesn’t work as I thought it did. This cannot endure.
Careful readers will remember that when I added the secondary paths to the neighbors calculation, it briefly started showing all paths as secondary. I reported that I didn’t understand why, but that reversing the order of two operations fixed it. That turns out not the be the case.
Reversing the order masked the problem. I think I can explain what’s going on, and I’ve fixed it once, so I’m sure I can fix it again this morning.
We’ve created a passel of rooms and spread them out just far enough so that they don’t overlap. Then, starting at room 1, a recursive routine checks all rooms to see if any are neighbors. If they are, it colors them and recurs, finding their neighbors. Along the way, we save a “Neighbor” object containing the two rooms found to be neighbors, for use later.
To visualize how this was working, I loop over all the Neighbor instances, drawing a line between the two room centers. This makes a nice tree showing all the possible transitions between rooms. (We have yet to build actual doors and such.)
That part worked fine. Then I decided to modify the function so that when the search finds a path to a room that has already been visited, it stores the Neighbor instance with a “secondary” marker in it. I display those in a different color. Each secondary link represents a loop in the path, and since loops are considered good in roguelike games, I was planning to use at least some of them in the game.
However, the algorithm as written doesn’t do what I thought it did. Here’s why. At each level of recursion, we consider all possible neighbors of the current room. Among those is the room we just came from. So we’ll look at it, and see that it has been visited … and we’ll file a secondary link right on top of the primary we just created. I think there are other instances where we might duplicate a secondary on top of a primary but that case ensures that we already have them all. We’ll also find legitimate secondaries: that part works as intended.
When this defect first appeared, I had chanced to put two calls in an order that caused all the duplicate secondaries to wind up at the end of the list, which colored all the paths in the secondary color. Reversing those two statements caused the secondaries to move up in the list, so that the primaries were drawn last, and the map colors looked right. But the data structure, the Neighbors table, is still flat wrong.
What we need to do is to check the table of Neighbors to be sure that we don’t enter a path twice. To make that easier, I have two ideas:
- Always create the Neighbor element with its two rooms in the same order, lower room number in room1, higher in room2. This will make it easier to check whether the path already exists.
- Keep the Neighbors in a hash table rather than an array. Last night after watching the Baby Yoda eat the some of the last remaining offspring of the Frog Lady, I built a fix on my other iPad, using an array. It was fast enough, but a hash table will surely be faster, and easier code to write.
After that, perhaps not today, I want to see about putting actual doors or hallways between adjacent rooms, on the big map. We’ll need to draw expanded rooms during game play, and the information as to where the doors go comes from the overlap in the neighbor calculation. I thought about that, and did a little refactoring in that direction, again on the other iPad.
Today, I’m starting over. I’m no fool: I have the other iPad’s code moved over if I need it, but my plan is not to need it. If I do use it, I’ll mention the fact.
Here goes:
Fixing Secondaries
Honestly, I think we need a test for this, since I’ve demonstrated yet again that tests are helpful, by showing what happens when I don’t have them. I have in mind a very simple set of rooms, like three, all adjacent. Our recursion should quickly find all three, 1,2,3, so we should have two primary neighbor entries, 1-2 and 2-3, and one secondary, 3-1.
_:test("primary and secondary paths", function()
local r1 = Room:fromCorners(200,200,300,300)
local r2 = Room:fromCorners(200,100, 250,199)
local r2 = Room:fromCorners(251,100, 300,199)
end)
I think this is one room with two adjacent rooms beneath it. I want to be sure of that, so I’m going to briefly patch the setup to create this same arrangement. The first thing I notice is that defining r2 twice is not ideal.
_:test("primary and secondary paths", function()
local r1 = Room:fromCorners(200,200,300,300)
local r2 = Room:fromCorners(200,100, 250,199)
local r3 = Room:fromCorners(251,100, 300,199)
end)
The second thing I notice is that all the rooms are numbered 666, the default number if no number is provided. This hasn’t been important up until now. All the real rooms get numbers. For this test, it is important.
local r1 = Room:fromCorners(200,200,300,300)
r1.number = 1
local r2 = Room:fromCorners(200,100, 250,199)
r2.number = 2
local r3 = Room:fromCorners(251,100, 300,199)
r3.number = 3
(I fumbled that once, too, doing r1 twice and not r2. Not a good sign.)
OK, that looks as I intended. And the graph looks right, too, but it isn’t. We’ll find that out as soon as we build out the test.
Here is our offending function:
function Room:colorNeighborsIn(rooms, aColor)
self:setColor(aColor)
for i,r in ipairs(rooms) do
if r:isNeighbor(self) then
if r:getColor() ~= aColor then
-- must recur first for secondary neighbors to work
r:colorNeighborsIn(rooms, aColor)
table.insert(Neighbors, Neighbor:primary(self, r))
else
table.insert(Neighbors, Neighbor:secondary(self, r))
end
end
end
end
We can call it in the tests and if it works, their should be 3 links in Neighbors. (I’m not happy that that’s a global, but that’s not our concern just now.)
_:test("primary and secondary paths", function()
local r1 = Room:fromCorners(200,200,300,300)
r1.number = 1
local r2 = Room:fromCorners(200,100, 250,199)
r2.number = 2
local r3 = Room:fromCorners(251,100, 300,199)
r3.number = 3
local rooms = {r1,r2,r3}
local col = color(255,0,0)
Room:colorNeighborsIn(rooms, col)
_:expect(#Neighbors).is(3)
end)
The result surprises me:
16: primary and secondary paths -- Room:131: attempt to perform arithmetic on a nil value (field 'h')
Room:131 is here:
function Room:halfHeight()
return self.h/2
end
I wonder who called that, and how we got a nil h value. The call turns out to be from the function north or south, trying to get the north or south wall of one of the rooms, to decide adjacency. But why isn’t it set? Possibly fromCorners, which is a test-only feature, has been setting up rooms improperly?
function Room:fromCorners(xSW, ySW, xNE, yNE)
local cx = (xSW+xNE)/2
local cy = (ySW+yNE)/2
local w = (xNE-xSW)
local h = (yNE-ySW)
return Room(cx,cy,w,h)
end
That looks OK. Let’s add some asserts:
_:test("primary and secondary paths", function()
local r1 = Room:fromCorners(200,200,300,300)
r1.number = 1
_:expect(r1.h).is(100)
local r2 = Room:fromCorners(200,100, 250,199)
r2.number = 2
_:expect(r2.h).is(99)
local r3 = Room:fromCorners(251,100, 300,199)
r3.number = 3
_:expect(r3.h).is(99)
local rooms = {r1,r2,r3}
local col = color(255,0,0)
Room:colorNeighborsIn(rooms, col)
_:expect(#Neighbors).is(3)
end)
The asserts all succeed and we still get the error. This is weird: I hate when a simple plan doesn’t come together. Must look more carefully at the code and perhaps put some traps in it.
Oh. colorNeighborsIn isn’t a class method. It should be sent to r1. And because of that Neighbors global, we have to init it.
_:test("primary and secondary paths", function()
local r1 = Room:fromCorners(200,200,300,300)
r1.number = 1
_:expect(r1.h).is(100)
local r2 = Room:fromCorners(200,100, 250,199)
r2.number = 2
_:expect(r2.h).is(99)
local r3 = Room:fromCorners(251,100, 300,199)
r3.number = 3
_:expect(r3.h).is(99)
local rooms = {r1,r2,r3}
local col = color(255,0,0)
Neighbors = {}
r1:colorNeighborsIn(rooms, col)
_:expect(#Neighbors).is(3)
end)
And finally, the error I wanted:
~~~lua16: primary and secondary paths – Actual: 6, Expected: 3
Now to fix it. Here's our method:
~~~lua
function Room:colorNeighborsIn(rooms, aColor)
self:setColor(aColor)
for i,r in ipairs(rooms) do
if r:isNeighbor(self) then
if r:getColor() ~= aColor then
-- must recur first for secondary neighbors to work
r:colorNeighborsIn(rooms, aColor)
table.insert(Neighbors, Neighbor:primary(self, r))
else
table.insert(Neighbors, Neighbor:secondary(self, r))
end
end
end
end
Now I’m not entirely fond of the fact that we don’t even check to see if we are comparing to the room in question. Could fix that here or in isNeighbor. I think the latter is better:
function Room:isNeighbor(aRoom)
local doorWidth = 10
return (self:nsCloseEnough(aRoom) and self:xOverlap(aRoom)>doorWidth) or
(self:ewCloseEnough(aRoom) and self:yOverlap(aRoom)>doorWidth)
end
We’ll add this check:
function Room:isNeighbor(aRoom)
if self == aRoom then return false end
local doorWidth = 10
return (self:nsCloseEnough(aRoom) and self:xOverlap(aRoom)>doorWidth) or
(self:ewCloseEnough(aRoom) and self:yOverlap(aRoom)>doorWidth)
end
That should have no effect on our test. And it doesn’t.
Now we have a few steps here to fix this.
First, we want the rooms in a neighbor instance to be stored in room number order.
function Neighbor:init(room1, room2, isPrimary)
self.isPrimary = isPrimary
self.room1 = room1
self.room2 = room2
if room1.number > room2.number then
self.room2,self.room1 = room1,room2
end
end
Next, we want to store new Neighbors only if the paths don’t match. So we have to condition our table insertions here:
function Room:colorNeighborsIn(rooms, aColor)
self:setColor(aColor)
for i,r in ipairs(rooms) do
if r:isNeighbor(self) then
if r:getColor() ~= aColor then
-- must recur first for secondary neighbors to work
r:colorNeighborsIn(rooms, aColor)
table.insert(Neighbors, Neighbor:primary(self, r))
else
table.insert(Neighbors, Neighbor:secondary(self, r))
end
end
end
end
function Room:colorNeighborsIn(rooms, aColor)
self:setColor(aColor)
for i,r in ipairs(rooms) do
if r:isNeighbor(self) then
if r:getColor() ~= aColor then
-- must recur first for secondary neighbors to work
r:colorNeighborsIn(rooms, aColor)
self:insertNewNeighbor(Neighbors, Neighbor:primary(self, r))
else
self:insertNewNeighbor(Neighbors, Neighbor:secondary(self, r))
end
end
end
end
function Room:insertNewNeighbor(neighbors, neighbor)
table.insert(neighbors,neighbor)
end
This is just an Extract Method refactoring, no functional change. Test still the same? Yes.
Now I want to do a data structure change here but it seems to me it would be best to make this work correctly first and then do the change. Then I’ll be sure that my basic scheme of not duplicating entries will do the job.
So:
function Room:insertNewNeighbor(neighbors, neighbor)
if self:neighborNotPresent(neighbors,neighbor) then
table.insert(neighbors,neighbor)
end
end
We’re seeing a lot of feature envy here, a Room fiddling about with Neighbors and their tables. This is a new object trying to be born. But we’re on a mission.
Even part way through that I don’t like the not in the middle of the function name. Going to flip it.
function Room:neighborPresent(neighbors,neighbor)
for i,n in ipairs(neighbors) do
if n:matches(neighbor) then return true end
end
return false
end
And we need matches:
function Neighbor:matches(aNeighbor)
return self.room1.number == aNeighbor.room1.number and self.room2.number == aNeighbor.room2.number
end
I could probably compare the rooms for equality here, but that for now I prefer this. We can back it down if it works, but since I’m going away from the linear search we won’t need it.
I expect my test to run now. Surprisingly (I never expect very firmly) it does run. Now we can check for the results. I expect 1,2 and 2,3 primary and 1,3 secondary. This will be a bit messy.
Actually … a glance at the screen drawing, which is still drawing the same three rooms, shows me that all three paths are yellow, or secondary. So … there’s something afoot.
I guess immediately what the bug is: We need to table the room before we recur, or the other guy will find it first.
function Room:colorNeighborsIn(rooms, aColor)
self:setColor(aColor)
for i,r in ipairs(rooms) do
if r:isNeighbor(self) then
if r:getColor() ~= aColor then
self:insertNewNeighbor(Neighbors, Neighbor:primary(self, r))
r:colorNeighborsIn(rooms, aColor)
else
self:insertNewNeighbor(Neighbors, Neighbor:secondary(self, r))
end
end
end
end
Now the drawing looks good, so I feel sure the test can be elaborated fully:
_:test("primary and secondary paths", function()
local r1 = Room:fromCorners(200,200,300,300)
r1.number = 1
_:expect(r1.h).is(100)
local r2 = Room:fromCorners(200,100, 250,199)
r2.number = 2
_:expect(r2.h).is(99)
local r3 = Room:fromCorners(251,100, 300,199)
r3.number = 3
_:expect(r3.h).is(99)
local rooms = {r1,r2,r3}
local col = color(255,0,0)
Neighbors = {}
r1:colorNeighborsIn(rooms, col)
_:expect(#Neighbors).is(3)
local n12 = Neighbors[1]
local n23 = Neighbors[2]
local n13 = Neighbors[3]
_:expect(n12.room1.number).is(1)
_:expect(n12.room2.number).is(2)
_:expect(n12.isPrimary).is(true)
_:expect(n23.room1.number).is(2)
_:expect(n23.room2.number).is(3)
_:expect(n23.isPrimary).is(true)
_:expect(n13.room1.number).is(1)
_:expect(n13.room2.number).is(3)
_:expect(n13.isPrimary).is(false)
end)
This test runs, making me quite sure that I’ve got it working this time. And the pictures look good.
Now my original plan was to use Neighbors, not as an array, but as a hash table, so that we could check in our insertNew code more quickly. However, if I do this, it’s going to badly break this test, and it will slightly break the drawing code.
It’s nearly time for Sunday breakfast, so I think we’ll wrap this up.
Commit: Neighbors no longer contains spurious pairs. Now let’s quickly sum up.
Summm
I gave myself permission not to test the recursive algorithm, because it wasn’t clear to me how to test it. And, initially, when it was simple, it worked. It correctly built a spanning tree among all the rooms that were adjacent.
When I extended it to include secondary paths, I thought it worked but wasn’t clear why. When it failed during some simple change, I thought reversing two calls fixed it. (In fact, it made it worse).
Finally, yesterday, I realized that it wasn’t working at all. That came about, if I recall, when I was experimenting with using Lua metatables to make objects printable, which by default they are not.
I devised today’s fix yesterday, but rebuilt it today, with the aid of a test. Most of the extra effort was in the testing, though I did discover another real defect, which was that the swapped order of things didn’t work, it just failed in a more hidden fashion. Swapping the statements back made everything OK again.
If there’s a lesson here, it would be to test the hell out of anything as tricky as a recursive tree searching algorithm. I’ll try to use this experience to ratchet up, once again, my inclination to test. I don’t think I’ve ever regretting testing something, and I’ve frequently regretted not testing, or not testing enough.
You’d think I’d learn. But just remember, when you point your finger at me, three fingers are pointing back at you.
Other learnings include:
- Making things printable as a matter of course might be a useful thing to do;
- Making things comparable, at least for equality, could be useful;
So, a good morning, and I think I get a few slices of bacon as a reward.
See you next time!