Dung[eon] 4: Dung it is.
Most of what I did yesterday was dreck, detritus, dung. Not very good at all. I plan to revert today and figure out a new plan.
I went off the rails yesterday on the adjacency thing. The basic idea was to find all the rooms that are adjacent, that is, close together on one edge, with enough edge overlapping, for values of “close” and “enough”. Having worked on detecting adjacency for a while, I decided to color contiguous areas of the dungeon in different colors, to get a sense of how connected the maze was, or was not.
The adjacency code that I wrote was simply wrong. It worked well on a side at a time, but you could position things far away but aligned near an edge, and they’d get shown as adjacent when they weren’t. I’m not quite capable of saying exactly how to position rooms so they’d appear to my broken code to be adjacent, but the program found them all over.
Further, based on looking at nearly any map, it’s clear that even after we do connect all the rooms that are recursively adjacent, there will be big segments of the maze that aren’t connected. A glance at our canonical maze will make it clear that there are separate “islands” and “continents” that are not connected.
Oh, and just for fun, here’s a picture of the work I’m throwing away. In this picture the red rooms are all believed to be directly adjacent to room 1. Not recursively adjacent, directly. Side by side. I think not.
I need to revert. I have a commit called “rooms are numbered”. I’m reverting to there.
I feel so free and unburdened. Or something.
Now I am sure we’re going to use an adjacency checker to decide whether two rooms can have a doorway between them. But … what about those separate islands and continents?
I know that the official solution to this problem is large, with Delaunay Triangles and tree trimming and insertion of redundant paths. We could look that stuff up, and TDD all the algorithms, and apply them. But honestly, though that might be the thing to do for a product, I’d find it tedious. As I look at that numbered picture, I really want to see how much is recursively adjacent to room number 1.
I think we’ll go that way. So, back into adjacency. Consider two rectangles, side by side, very close together (for values of “very”). We want to call them adjacent if their overlap is large enough to accommodate a doorway, that is, some arbitrary number.
So for side-to-side, in pseudocode, it seems to me that we want something like this:
if myEast is close enough to hisWest or myWest is close enough to hisEast then
if the length of our height overlap is sufficient then
we overlap
Now for the overlap, we don’t need to consider whether he’s to our left or right. We just need to consider the lower and upper y coordinates of each room, and I think it goes like this:
min(myHi,hisHi)-max(myLo,hisLo) > sufficient
Why do I think that? Because I drew a bunch of pictures and thought about it. Why does that make me right? Based on the record so far, it doesn’t. Nonetheless, that’s my plan. And for the north south adjacency, the same rule applies, checking the right-left values rather than the high low ones.
My revert leaves me with no tests for adjacency. I think that’s a good thing. And I think I’ll start with the overlap this time.
Oh, here’s a bummer. My revert took away the Room:fromCorners creation method. I want that back, it’ll make the tests much easier. Easy enough, since it’s in the previous article. Hold on, I’ll be right back.
Well, that’s amusing. I described the test but not the implementation. And it’s gone now. Well, here’s the test:
_:test("room from corners", function()
local r = Room:fromCorners(450,450,550,550)
checkCorners(r, 450,450,550,550)
local r1 = Room:fromCorners(451,451,550,550)
checkCorners(r1, 451,451,550,550)
end)
We’ll go from there. This seems close:
function Room:fromCorners(xSW, ySW, xNE, yNE)
local cx = (xSW+xNE)/2
local cy = (ySW+yNE)/2
local w = (xNE-xSW)/2
local h = (yNE-ySW)/2
return Room(cx,cy,w,h)
end
I expect some trouble from fractions, because I had some last time. The test says:
8: room from corners xLo -- Actual: 475.0, Expected: 450
And so on. Hm, tell the truth, I’m not seeing the bug. Oh, duh. Why did I divide the width and height by two??
That’s better. But this fails:
1: create 25 rooms -- Tests:17: attempt to call a nil value (global 'createRooms')
I remember that, the test needs to refer to Rooms, since we moved the createRooms function.
_:test("create 25 rooms", function()
local rooms = Room:createRooms(25)
_:expect(#rooms).is(25)
end)
Ah yes, kept that one for history. OK, my tests are green and I have fromCorners to make my job easier.
It’s not often that we create a method just to aid in our testing, but it’s not so uncommon as to be rare. We could have built a function into our testing code to do the job, but it made more sense to me to add it to the real class. That way it has a chance of being dealt with if things change, and anyway it just feels like a class method to me.
On to overlap: Here’s my first cut, no assertions yet:
local s = Room:fromCorners(100,100,200,200)
local n = Room:fromCorners(150,201, 175, 301)
So room n is north of room s, and its x coordinates overlap by 25, if I’m not mistaken. Now what would we like to say to the room to get this answer? Horizontal overlap? North-South overlap? X overlap? Hm I like X overlap, it’s less ambiguous.
_:test("compute overlap", function()
local s = Room:fromCorners(100,100,200,200)
local n = Room:fromCorners(150,201, 175, 301)
local overlap = s:xOverlap(n)
_:expect(overlap).is(25)
end)
Now for my min/max thing. There are only a few ways to get that wrong …
local min = math.min
local max = math.max
function Room:xOverlap(aRoom)
sLo,xx,sHi,xx = unpack(self:corners())
rLo,xx,rHi,xx = unpack(aRoom:corners())
return min(sHi,rHi)-max(sLo,rLo)
end
So far so good. Let’s test a few more cases:
_:test("compute overlap", function()
local s = Room:fromCorners(100,100,200,200)
local n = Room:fromCorners(150,201, 175, 301)
local overlap = s:xOverlap(n)
_:expect(overlap).is(25)
n = Room:fromCorners(75,201, 110, 201)
overlap = s:xOverlap(n)
_:expect(overlap).is(10)
n = Room:fromCorners(185,201, 250,201)
overlap = s:xOverlap(n)
_:expect(overlap).is(15)
end)
These all pass. Now for the other case. This is tedious, and I’m sure I could do it right without tests. So I’ll test. Momentary increase in will power, I guess. Probably a glitch.
I sure do have trouble doing these without drawing a picture. How about this first test:
_:test("compute y overlap", function()
local w = Room:fromCorners(100,100,200,200)
local e = Room:fromCorners(201,100, 201,250)
local overlap = w:yOverlap(e)
_:expect(overlap).is(50)
end)
So, maybe this:
function Room:yOverlap(aRoom)
xx,sLo,xx,sHi = unpack(self:corners())
xx,rLo,xx,rHi = unpack(aRoom:corners())
return min(sHi,rHi)-max(sLo,rLo)
end
Test says no:
10: compute y overlap -- Actual: 100.0, Expected: 50
Draw a picture, innit?
That’s what I intended. The coordinates I typed in, well, no.
_:test("compute y overlap", function()
local w = Room:fromCorners(100,100,200,200)
local e = Room:fromCorners(201,100, 301,150)
local overlap = w:yOverlap(e)
_:expect(overlap).is(50)
end)
I’ll do a couple more …
_:test("compute y overlap", function()
local w = Room:fromCorners(100,100,200,200)
local e = Room:fromCorners(201,100, 301,150)
local overlap = w:yOverlap(e)
_:expect(overlap).is(50)
e = Room:fromCorners(49,175,99,275)
overlap = w:yOverlap(e)
_:expect(overlap).is(25)
e = Room:fromCorners(201,225, 250,275)
overlap = w:yOverlap(e)
_:expect(overlap).is(0)
end)
I got tricky there with that last one. Here’s the picture:
And the test result surprised me for a moment:
10: compute y overlap -- Actual: -25.0, Expected: 0
So that won’t do, will it? I think we should make sure that our overlap values never go negative. And, if I’m honest with myself, I need more tests. They’re rather a pain to do but there you are.
local min = math.min
local max = math.max
function Room:xOverlap(aRoom)
sLo,xx,sHi,xx = unpack(self:corners())
rLo,xx,rHi,xx = unpack(aRoom:corners())
return max(min(sHi,rHi)-max(sLo,rLo),0)
end
function Room:yOverlap(aRoom)
xx,sLo,xx,sHi = unpack(self:corners())
xx,rLo,xx,rHi = unpack(aRoom:corners())
return max(min(sHi,rHi)-max(sLo,rLo),0)
end
That makes my existing tests green. Let me mention this explicitly:
local min = math.min
local max = math.max
This is a common Lua idiom. It copies the function pointer math.min into the local variable min. This saves one table lookup to find min in math, and it makes the following code a bit easier to read. Both are good things, so I thought I’d try it to see if I like it. And I do.
I’ll do a couple more boxes now, off in space.
_:test("compute x overlap", function()
local s = Room:fromCorners(100,100,200,200)
local n = Room:fromCorners(150,201, 175, 301)
local overlap = s:xOverlap(n)
_:expect(overlap).is(25)
n = Room:fromCorners(75,201, 110, 201)
overlap = s:xOverlap(n)
_:expect(overlap).is(10)
n = Room:fromCorners(185,201, 250,201)
overlap = s:xOverlap(n)
_:expect(overlap).is(15)
n = Room:fromCorners(400,400,450,450)
overlap = s:xOverlap(n)
_:expect(overlap).is(0)
end)
_:test("compute y overlap", function()
local w = Room:fromCorners(100,100,200,200)
local e = Room:fromCorners(201,100, 301,150)
local overlap = w:yOverlap(e)
_:expect(overlap).is(50)
e = Room:fromCorners(49,175,99,275)
overlap = w:yOverlap(e)
_:expect(overlap).is(25)
e = Room:fromCorners(201,225, 250,275)
overlap = w:yOverlap(e)
_:expect(overlap).is(0)
e = Room:fromCorners(1,1, 10,10)
overlap = w:yOverlap(e)
_:expect(overlap).is(0)
end)
Tests all green. Commit: added Room fromCorners, xOverlap, yOverlap.
Stack
One more thing and then I think I’ll call it a morning.
I still intend to color in the islands and continents, just to get a sense of what a naive connection algorithm might do. Our dungeon is pretty dense and it might be OK.
To do the coloring, I’ll need either to write a recursive algorithm, or to use a stack of discovered adjacent rooms, and when one room’s complete, process the one on the top of the stack, implementing the recursion iteratively. I plan to do the latter, because recursion is tricky and because I want to.
So I’ll need a stack, and I propose to implement it now.
This seems like enough test:
_:test("stack", function()
local s = Stack()
s:push(2)
s:push("a")
local a = s:pop()
local two = s:pop()
_:expect(a).is("a")
_:expect(two).is(2)
end)
Maybe pop again to get nil? Yeah.
_:test("stack", function()
local s = Stack()
s:push(2)
s:push("a")
local a = s:pop()
local two = s:pop()
local n = s:pop()
_:expect(a).is("a")
_:expect(two).is(2)
_:expect(n).is(nil)
end)
OK, I’m goin in:
-- Stack
-- RJ 20201105
Stack = class()
function Stack:init()
self.s = {}
end
function Stack:push(item)
table.insert(self.s,item)
end
function Stack:pop()
return table.remove(self.s)
end
Tests run. That wasn’t too hard, was it?
Note that table.remove removes the last item and returns it, and returns nil if the table is empty. Sweet.
Commit: Stack implemented.
It’s still early but I think I’ll call it a morning. I feel that I could do the adjacency stuff but for some reason I’m a bit whipped and/or knackered.
Let’s quickly sum up.
Summuperation
Yesterday I went down a rathole and worked a long time. Curiously, I felt that I was doing OK. More often, when I’m in trouble, I have a very solid inkling about it, which I ignore. Yesterday, I didn’t even realize that my adjacency was wrong.
Today, I was careful with my testing, and had the advantage of having thought a bit more about adjacency and overlap. Still, I managed to surprise myself with the results of an overlap calculation that was clear off the map. I think we’ve got that covered now, with our max(z, 0) addition.
Less progress than the apparent but unreal progress of yesterday, but it seems to be real progress this time.
See you soon!