Dungeon 6
Today I think I need to deal with tiling, or decide that we can do without it.
Last night was the weekly Zoom Ensemble, where a few colleagues get together to chat and work on code. We’re working on a roguelike dungeon that one of the members has been building. Working on that one brings up a topic that our dungeon here will need to deal with in one way or another.
The basic deal with one of these games is that there’s a large map, but you only typically see one room, the room you are in. It’s a sort of zoomed in view of the map, showing just the one room. (Not all games do this, but it’s a pretty common practice.)
In the zoomed view, you see a stylized floor, typically tiled, surrounded by a different texture representing walls, and showing other key items such as doors, treasure boxes, your player, and, well, keys. It is common for the floors to be tiled, and for player motion to be limited to the tiling, perhaps one square per move, perhaps one half. The game the Ensemble is working on uses one half. For each hit of an arrow key, the player moves half a tile.
The issue I’m concerned about is this tiling. I hope to convince myself here that I can ignore it. My concern is this: in the big map, that we’re currently working on, rooms are not on integer coordinates, because the separation logic sums the forces on each room and adjusts it accordingly, and that sum doesn’t necessarily move you an exact integer in x or y.
You may recall that I put in code to push rooms to integer positions after the separation was complete, and it interfered with connections, plus occasionally seemed to make two rooms seem to have a common wall on the map. Normally you can see both rooms’ walls separately.
I changed that function to rounding: it had used ceil. That change seemed to result in less coverage in the path finding, perhaps because sometimes rooms would round to be further away than the “close enough” value of 3. Changing that to 5 seems to have improved things.
function Room:setAllToInteger(rooms)
for i,r in ipairs(rooms) do
r:setToInteger()
end
end
function Room:setToInteger()
self.x = (self.x + 0.5)//1
self.y = (self.y + 0.5)//1
end
With this in place, the path finding seems generally to find at least 40 of the 50 rooms and usually more. So now the rooms are all tidily arranged on integer coordinates and the map looks decent. I think my tiling worries can be dismissed–and probably could have been dismissed without this experiment.
If we only show one room at a time on the zoomed map, we can tile the room appropriately without regard to any oddities of its position in the big map. Probably this whole concern was a red herring.
However.
I believe that when a concern arises with our design or code, suggesting that something very wrong might happen in the future, we ought to take a little time to deal with it. It’s possible that a design mistake now can really mess things up in the future, so when we get that feeling, I like to give it a little space in my mind.
But, Ron, that contradicts your preferred style of doing a design that’s good enough for now, with the confidence that you can refactor to a better design in the future. Yes, it does go against that style.
Decisions we make in life are rarely simple, cut and dried1, answer obvious, move on. We often make decisions that way, but we often get bitten by them later. There are many forces acting on most decisions, and we need to try to keep them in balance.
So my practice is to give concerns enough thought space to provide a good reason to let them wait, or to deal with them now. I don’t want to build complex software for a future need that may not arise. But I am happy to build simple software whose design seems likely to endure, and to be extended as needed.
I think I could dismiss the tiling concern even without the rounding of rooms to unit coordinates. But with that rounding in place, which was a couple of lines of code, that concern goes away.
So, we give a concern a decent look, while trying not to get bogged down, and to trust our refactoring. It’s a balance and we have to find it, and continually adjust it as we go.
Now there is one other thing on my mind, since we’re talking about rounding.
The rooms’ dimensions are random in some range. Since room centers are now integers, some rooms’ walls will be on integral addresses as well, and some will be on half-integers. I think I’d like the room width and height always to be even numbers, so that the walls are always on integer bounds as well. This is probably not necessary, but the fractional values have certainly made testing confusing if nothing else.
Let’s see about forcing the width and height to even values:
function Room:init(x,y,w,h)
self.number = 666
self.color = color(0,255,0,25)
self.x = x or math.random(WIDTH//4,3*WIDTH//4)
self.y = y or math.random(HEIGHT//4,3*HEIGHT//4)
self.w = w or math.random(WIDTH//20,WIDTH//10)
self.h = h or math.random(HEIGHT//20,WIDTH//10)
end
If we double those divisors and then double the random integer, we should get only even values for w and h. We could TDD that, and I guess we should. This should do it:
_:test("rooms have even width and height", function()
for i = 1,100 do
local r = Room()
_:expect(r.w%2).is(0)
_:expect(r.h%2).is(0)
end
end)
That test fails 88 times out of 100. Of course every run will be different. Let’s do the change:
function Room:init(x,y,w,h)
self.number = 666
self.color = color(0,255,0,25)
self.x = x or math.random(WIDTH//4,3*WIDTH//4)
self.y = y or math.random(HEIGHT//4,3*HEIGHT//4)
self.w = w or math.random(WIDTH//40,WIDTH//20)*2
self.h = h or math.random(HEIGHT//40,WIDTH//20)*2
end
And now the test passes. Fixed 88 bugs with two lines of code. Amazing.
Better commit, we’ve done some stuff. Commit: room centers and walls are integers.
In testing that, I did roll one random set of rooms where room 1 was only connected to one other room. If that happens in the game, we’ll have to do something, either roll up a whole new dungeon or pick another cell to start from. I feel sure we can worry about that later.
I do have one more little thing. I thought I’d done it in an article, but I must have done it on the other iPad in the tv room. Our present path-finding algorithm does not enter rooms twice. It builds a spanning tree without loops. The code is this:
function Room:colorNeighborsIn(rooms, aColor)
self:setColor(aColor)
for i,r in ipairs(rooms) do
if r:isNeighbor(self) and r:getColor() ~= aColor then
table.insert(Neighbors, Neighbor(self, r))
r:colorNeighborsIn(rooms, aColor)
end
end
end
If a room is already colored aColor, it has been entered before, and its subtree has already been created, so we do not do it again. (If we did, bad things would happen, infinite loops, sky falling, and so on.) However, in that case we have just discovered another path to that same room. Since dungeons with a few loops in them are considered to be more interesting, let’s keep track of those links as well.
To do that, I plan to add a new Neighbor object for this new path, and to make that instance draw itself in a different color.
Right now, this is Neighbor:
function Neighbor:init(room1, room2)
self.room1 = room1
self.room2 = room2
end
function Neighbor:draw()
pushStyle()
pushMatrix()
stroke(255,0,0)
resetMatrix()
line(self.room1.x, self.room1.y, self.room2.x, self.room2.y)
popStyle()
popMatrix()
end
We could pass in a color. But instead, why not just tell the neighbor whether it is a primary or secondary neighbor, and let it display as it will. We’ll add factory methods just for grins:
Neighbor = class()
-- class methods
function Neighbor:primary(room1, room2)
return Neighbor(room1,room2,true)
end
function Neighbor:secondary(room1, room2)
return Neighbor(room1,room2,false)
end
-- instance methods
function Neighbor:init(room1, room2, isPrimary)
self.isPrimary = isPrimary
self.room1 = room1
self.room2 = room2
end
function Neighbor:draw()
pushStyle()
pushMatrix()
if self.isPrimary then
stroke(255,0,0)
else
stroke(255,255,0)
end
resetMatrix()
line(self.room1.x, self.room1.y, self.room2.x, self.room2.y)
popStyle()
popMatrix()
end
Then call primary in our existing code:
function Room:colorNeighborsIn(rooms, aColor)
self:setColor(aColor)
for i,r in ipairs(rooms) do
if r:isNeighbor(self) and r:getColor() ~= aColor then
table.insert(Neighbors, Neighbor:primary(self, r))
r:colorNeighborsIn(rooms, aColor)
end
end
end
That works as before, of course. Now let’s do our secondaries. If the room is a neighbor and already colored, we want to do a secondary neighbor entry:
function Room:colorNeighborsIn(rooms, aColor)
local neighbor
self:setColor(aColor)
for i,r in ipairs(rooms) do
if r:isNeighbor(self) then
if r:getColor() ~= aColor then
neighbor = Neighbor:primary(self, r)
r:colorNeighborsIn(rooms, aColor)
else
neighbor = Neighbor:secondary(self,r)
end
table.insert(Neighbors, neighbor)
end
end
end
This generates a fine result:
Commit: secondary neighbor paths created.
Now a little story goes with that code just above. I originally put a table.insert call in both branches of the inner if, since the two calls are different and I didn’t see why I should create a temp. With it that way, the entire path was yellow on the map, not mostly red as it should be. I was confused, but fortunately my other iPad still had last night’s solution, which was a bit different but the important difference was clear: it didn’t call table.insert until after the recursive call to colorNeighborsIn. If we haven’t drawn the path yet, everything looks like a secondary.
I think now I can put it back as I had it, except like this:
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
r:colorNeighborsIn(rooms, aColor)
table.insert(Neighbors, Neighbor:primary(self, r))
else
table.insert(Neighbors, Neighbor:secondary(self, r))
end
end
end
end
I’ve put the recursive call above the creation of the neighbor. And it works fine. Which way of writing it is more expressive or otherwise better? I can’t say that I have a big preference. There’s sequential coupling in here, though, in that the recursive call has to be done before reporting the table insertion. I’m not sure why, to be honest, but it’s clearly the case. If we reverse those two lines we get this:
So it must be as above. Somehow we wind up with a mess of secondary Neighbors at the end of the table, and they cover up all the red wires. Maybe I’ll draw a picture and try to understand it.
I also think I’ll comment that code, because I don’t see how to make it more expressive of the need.
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
Fact is, this works. I think I’ll back away slowly. Commit again: minor refactoring of colorNeighborsIn.
That’s enough for a Saturday morning. Let’s quickly sum up and GTHO.
Summing Up
I started the morning with a concern about room positions and sizes, and whether I could tile them OK. I convinced myself on the one hand that I could, but also that I’d prefer to have the rooms have center and walls on integer coordinates. With some rounding and adjusting of values, I made that happen.
Hm, I note in passing that there are tests that create rooms on fractional boundaries. Those should have a look taken, but I’m not up for that today. I’ll mark one of them to ignore:
_:ignore("NO MORE FRACTIONS? intersect bug", function()
local r1 = Room:fromCorners(517.5,359.5,632.5,450.5)
local r2 = Room:fromCorners(612.5,450.0, 713.5,540.0)
_:expect(r1:intersects(r2)).is(true)
end)
Commit: reminder test.
OK, right. Where was I? Oh yes. I thought a bit about how I deal with worries like the tiling one. I like to worry about them in the presence of the code, because often the code can answer questions about how things really are, or can be readily changed to avoid the concern.
I don’t want to spend a lot of time in speculation, but I’m always looking forward as I work. I try not to build for the future, but I do think about the future.
Then I put in a secondary Neighbor notion to put loops back into the path. That got me in a bit of trouble until I realized that I had to do the path recursion before entering the Neighbor connection. I’m still not sure why that’s the case.
But now we have secondary neighbor connections and we can judiciously allow of those to cut doors, creating loops in the maze. That should be good.
And that’s the morning. See you next time!
-
What does cut and dried mean, anyway. Fish? Tobacco? Remind me to look it up. ↩