Dungeon 124
I want to get a creature to lead us to the WayDown. And I feel the need to improve the campground. Also St. Gertude. And, as often happens, we don’t go where I expect. Neat outcome, thoughl
It came to my attention late yesterday that in addition to it being St Patrick’s day, it was also St Gertrude’s day. This is important because St Gertrude is the patron saint of cats. I made sure that Kitty was aware of the special day, and she signified her satisfaction by behaving exactly as she does on any other day.
I have what I think is an interesting idea for the creature that leads to the WayDown. Rather than making it a monster, perhaps it could be a cloud of vapor that drifts toward the WayDown. If there were other such clouds, the player might not realized the significance and usefulness right away.
We’re not at a point where we can build that creature quite yet, but we’ll keep it in mind as an idea.
Campground
Constant readers know that I recommend refactoring an area only when we’re working in an area. That goes to one of my personal fears about product development, namely that “they” will become dissatisfied with progress and do something abrupt and unpleasant. Among the things I’d do to help ensure consistent progress would be to avoid going on refactoring quests into parts of the code that aren’t undergoing change.
In these articles, of course, I’ll refactor most anything, because the point of these articles is to share our discovery of how to do things when they do arise, so one opportunity is as good as another.
Right now, however, all the dice are rolling the same way. I want to build a test creature that follows the path to the WayDown, and building a new creature involves the classes GameRunner, Tile, Monsters, Monster, and probably Dungeon, as well as Map and MapCell. That’s a lot. It’s too much.
I tried to bang in a test monster yesterday and got tangled up in all those classes. Something needs to be done about the mess.
Somewhere yesterday I was reading about “god objects”, objects that become central to an application, knowing everything about what’s going on. These objects wind up as centers for communication and discovery, and tend to become a sort of trash can for all kinds of useful but incoherent methods.
The dungeon creation is all part of GameRunner at present, and could be–and probably should be–moved off to another factory class of some kind. I think that’s a lower priority than improving the moment-to-moment interactions in the running game, however.
One of the problems with god classes is that everyone uses them, so it’s difficult to move things. We’ll do what we can to leave things properly connected, even if we have to do more forwarding.
“Remind you of anyone?”
– Craig Ferguson
Indeed. GameRunner is our god object and it’s at the center of a mess.
Yesterday evening, I was imagining how the Dung program might be improved by refactoring. I think that Tile could be called upon to handle more of our needs, and that since almost all it needs to do is access other tiles, Tiles could hold a Dungeon instance instead of the GameRunner they now hold. And the Dungeon’s availableThisAndThat methods can probably be improved.
So, ‘nuff said, today we’re going to look at improving these things.
Give Tile a Dungeon
As things stand today, Dungeon instances are created and destroyed as needed. Tiles stay in existence because GameRunner has them as a member variable.
function GameRunner:createTiles()
self.tiles = {}
for x = 1,self.tileCountX+1 do
self.tiles[x] = {}
for y = 1,self.tileCountY+1 do
local tile = Tile:edge(x,y, self)
self:setTile(tile)
end
end
end
function GameRunner:setTile(aTile)
self:getDungeon():setTile(aTile)
end
function GameRunner:getDungeon()
return Dungeon(self.tiles, self, self.player)
end
function Dungeon:setTile(aTile)
assert(not TileLock, "attempt to set tile while locked")
local pos = aTile:pos()
self.tiles[pos.x][pos.y] = aTile
end
There is something bizarre about this: for each tile that is placed into the tiles arrays, we create a new instance of Dungeon, that just does the subscripting, tosses the tile into the arrays, and goes away.
Let’s change that so that we always use the same Dungeon instance.
function GameRunner:getDungeon()
if not self.dungeon then
self.dungeon = Dungeon(self.tiles, self, self.player)
end
return self.dungeon
end
Now if we’re going to do this, we should really have the Dungeon more engaged in the creating and clearing, which presently go like this:
function GameRunner:createTiles()
self.tiles = {}
for x = 1,self.tileCountX+1 do
self.tiles[x] = {}
for y = 1,self.tileCountY+1 do
local tile = Tile:edge(x,y, self)
self:setTile(tile)
end
end
end
function GameRunner:clearTiles()
for i,row in ipairs(self.tiles) do
for j,tile in ipairs(row) do
tile:clearVisible()
end
end
end
There’s a rather long pause here, as I think. The nice thing about letting Dungeon instances be created dynamically is that when we do something weird with the tiles, like clear them all, we get a fresh Dungeon to look at them. The shape of the tiles array is always the same, but we can create a new one as above in the createTiles method.
If I cache the Dungeon instance and then call createTiles, the Dungeon instance will still hold the old tiles.
Let’s work toward this:
When we create a new Dungeon, it will create the tiles. We’ll not save the tiles in GameRunner, only the Dungeon. When we create a new level, we’ll probably create a new Dungeon at that time.
This seems like a big change to me. And I feel like it’s going to get worse before it gets better. When I get those feelings, there are a few possibilities, in my experience.
It’s possible that I’m picking up this ball of string at the wrong point. When you tug at the right point, the ball begins to untangle, but when you tug at the wrong point, the tangle gets worse. Sometimes, you accept that, if tightening one part makes another part get loose, but as a rule, you’re tugging the wrong part.
It’s possible that we’ll just have to work through everything, and in fact make a lot of things worse, or at least more strange, until we’re done.
I lean toward the first notion: if it seems hard, I’m trying to do the wrong thing and will benefit from doing something else first. But what?
Revert. Caching the Dungeon adds no real value but increases complexity.
Let’s look at the available methods in Dungeon:
function Dungeon:availableTilesCloserToPlayer(aTile)
local desiredDistance = self:manhattanToPlayer(aTile) - 1
return self:availableTilesAtDistanceFromPlayer(aTile, desiredDistance)
end
function Dungeon:availableTilesFurtherFromPlayer(aTile)
local desiredDistance = self:manhattanToPlayer(aTile) + 1
return self:availableTilesAtDistanceFromPlayer(aTile, desiredDistance)
end
function Dungeon:availableTilesCloserToTile(tile1, tile2)
local desiredDistance = self:manhattanBetween(tile1,tile2) - 1
return self:availableTilesAtDistanceFromTile(tile1,tile2, desiredDistance)
end
function Dungeon:availableTilesFurtherFromTile(tile1, tile2)
local desiredDistance = self:manhattanBetween(tile1,tile2) + 1
return self:availableTilesAtDistanceFromTile(tile1,tile2, desiredDistance)
end
function Dungeon:availableTilesSameDistanceFromPlayer(aTile)
local desiredDistance = self:manhattanToPlayer(aTile)
return self:availableTilesAtDistanceFromPlayer(aTile, desiredDistance)
end
function Dungeon:availableTilesAtDistanceFromPlayer(startingTile, desiredDistance)
local targetTile = self:playerTile()
return self:availableTilesAtDistanceFromTile(startingTile, targetTile, desiredDistance)
end
function Dungeon:availableTilesAtDistanceFromTile(startingTile, targetTile, desiredDistance)
local pos = startingTile:pos()
local result = {}
for i, delta in ipairs(self:neighborOffsets()) do
local t = self:getTile(pos + delta)
local d = self:manhattanBetween(t, targetTile)
if d == desiredDistance and (t:isRoom() or t:isEdge()) then
table.insert(result, t)
end
end
if #result == 0 then
result = {startingTile}
end
return result
end
These methods are not tested other than here:
_:test("Dungeon helps monster moves", function()
local tiles, x1,x2
local dungeon = Runner:getDungeon()
dungeon:setTestPlayerAtPosition(vec2(30,30))
local monsterTile = dungeon:getTile(vec2(34,34))
_:expect(dungeon:manhattanToPlayer(monsterTile)).is(8)
tiles = dungeon:availableTilesCloserToPlayer(monsterTile)
x1,x2 = dungeon:getTile(vec2(33,34)), dungeon:getTile(vec2(34,33))
_:expect(tiles).has(x1)
_:expect(tiles).has(x2)
tiles = dungeon:availableTilesFurtherFromPlayer(monsterTile)
x1,x2 = dungeon:getTile(vec2(35,34)), dungeon:getTile(vec2(34,35))
_:expect(tiles).has(x1)
_:expect(tiles).has(x2)
tiles = dungeon:availableTilesSameDistanceFromPlayer(monsterTile)
x1,x2 = dungeon:getTile(vec2(33,35)), dungeon:getTile(vec2(35,33))
_:expect(tiles).has(x1)
_:expect(tiles).has(x2)
end)
That’s not impressive. Testing all those, as we see above, is kind of a pain.
However, all those methods come down to the one at the bottom:
function Dungeon:availableTilesAtDistanceFromTile(startingTile, targetTile, desiredDistance)
local pos = startingTile:pos()
local result = {}
for i, delta in ipairs(self:neighborOffsets()) do
local t = self:getTile(pos + delta)
local d = self:manhattanBetween(t, targetTile)
if d == desiredDistance and (t:isRoom() or t:isEdge()) then
table.insert(result, t)
end
end
if #result == 0 then
result = {startingTile}
end
return result
end
If we could test that, and then test that the others make the right calls to it, we’d have some pretty solid testing in place. Meanwhile, we have fairly decent testing now, since the few tests above do all come down to this method.
The method is still difficult to test, because it generates neighbors for the starting tile inside itself.
Think, Ron! Think!
OK. This isn’t really a problem for dungeons or tiles. It is a pure geometry problem.
Given a collection of positions, plus a starting one and ending one, return all the positions that are a desired distance from the ending one, and if there are none, return a collection containing only the starting one.
Then, of course, we have another smaller problem: given a collection of positions, convert that to a collection of the tiles at those positions.
Let’s see if we can refactor this method to be more like that idea. If it turns out not to help, we’re at a clean slate and we can just revert back out.
Refactor Toward Primitives
We’re going to refactor this method to get closer to primitives, in this case, position vectors. (I foresee some small chance that we’ll wind up creating a Position class. We’ll see.)
We begin with:
function Dungeon:availableTilesAtDistanceFromTile(startingTile, targetTile, desiredDistance)
local pos = startingTile:pos()
local result = {}
for i, delta in ipairs(self:neighborOffsets()) do
local t = self:getTile(pos + delta)
local d = self:manhattanBetween(t, targetTile)
if d == desiredDistance and (t:isRoom() or t:isEdge()) then
table.insert(result, t)
end
end
if #result == 0 then
result = {startingTile}
end
return result
end
Let’s note that neighborOffsets is this collection of vectors:
function Dungeon:neighborOffsets()
return {
vec2(-1,-1), vec2(0,-1), vec2(1,-1),
vec2(-1,0), vec2(1,0),
vec2(-1,1), vec2(0,1), vec2(1,1)
}
end
So instead of fetching the tiles let’s use the vectors:
My first attempt doesn’t feel right. Revert.
What I ran into was that the function is deciding whether the tiles are in range, and also whether they are room or edge. (The edge, I think, shouldn’t be accepted: we can’t move to an edge.) So I’ll remove that:
Ah. When I do, all the tests break:
2: Dungeon helps monster moves -- Actual: table: 0x28f754d40, Expected: Tile[33][34]: edge
That’s because in that test, the tiles in the dungeon are all Edges. I add this to the test:
for row = 1,#tiles do
for col = 1,#tiles[row] do
tiles[row][col]:testSetRoom()
end
end
That sets the whole dungeon to Room. The test runs. No harm done. Commit: improve dungeon helps monster moves test.
Now back to refactoring.
In a language with better table handling, I might be thinking something like this:
- create the possible positions.
- select the positions at correct range
- map to tiles
- select room tiles
- return the collection or { start }
Let’s just do that. How about this:
function Dungeon:availableTilesAtDistanceFromTile(startingTile, targetTile, desiredDistance)
local start = startingTile:pos()
local target = targetTile:pos()
local choices = self:neighborOffsets()
local posResults = self:selectOffsetsAtDistance(choices, tgt, desiredDistance)
local tileResults = self:convertPosToTile(posResults)
local finalResults = self:selectRoomTiles(tileResults)
return #finalResults > 0 and finalResults or { startingTile }
end
That’s not quite right. We need not the offsets, but the positions. So, how about this:
function Dungeon:availableTilesAtDistanceFromTile(startingTile, targetTile, desiredDistance)
local start = startingTile:pos()
local target = targetTile:pos()
local offsets = self:neighborOffsets()
local choices = self:mapOffsetsToPostions(offsets, start)
local posResults = self:selectOffsetsAtDistance(choices, tgt, desiredDistance)
local tileResults = self:mapPosToTile(posResults)
local finalResults = self:selectRoomTiles(tileResults)
return #finalResults > 0 and finalResults or { startingTile }
end
We can code these smaller methods readily:
function Dungeon:mapOffsetsToPositions(offsets,pos)
local result = {}
for i,offset in ipairs(offsets) do
table.insert(result, pos + offset)
end
return result
end
After fixing a few typos, I have this:
function Dungeon:availableTilesAtDistanceFromTile(startingTile, targetTile, desiredDistance)
local start = startingTile:pos()
local target = targetTile:pos()
local offsets = self:neighborOffsets()
local choices = self:mapOffsetsToPositions(offsets, start)
local posResults = self:selectOffsetsAtDistance(choices, target, desiredDistance)
local tileResults = self:mapPosToTile(posResults)
local finalResults = self:selectRoomTiles(tileResults)
return #finalResults > 0 and finalResults or { startingTile }
end
function Dungeon:mapOffsetsToPositions(offsets,pos)
local result = {}
for i,offset in ipairs(offsets) do
table.insert(result, pos + offset)
end
return result
end
function Dungeon:selectOffsetsAtDistance(offsets, tgt, desiredDistance)
local result = {}
for i, offset in ipairs(offsets) do
if manhattan(offset,tgt) == desiredDistance then
table.insert(result,offset)
end
end
return result
end
function Dungeon:mapPosToTile(positions)
local result = {}
for i, pos in ipairs(positions) do
table.insert(result, self:getTile(pos))
end
return result
end
function Dungeon:selectRoomTiles(tiles)
local result = {}
for i, tile in ipairs(tiles) do
if tile:isRoom() then
table.insert(result,tile)
end
end
return result
end
Now at this point, we need to ask ourselves: is this better? It’s more code: 31 lines more, counting the blank lines. It’s slower, four loops over the collections rather than one. Four times as many inserts, table creations, and so on.
My answer is yes, and I’ve committed: refactor available in dungeon.
YMMV. I prefer this because the top level code is more clear to me, and because the individual operations are faster and more atomic.
Also, I admit, because I just did it and I feel good about how it went.
However, I set out to move more toward primitives and we’re not there yet. All these operations are taking place in the Dungeon class. None of them actually belongs there.
But where do they belong? Well, if I had my druthers, they’d be methods or functions on arrays. Arrays in Lua are just tables meeting certain criteria. So I’d have the methods on table.
I really don’t want to monkey-patch Lua tables, however.
Let’s try something. I’m at a commit point, so I can try to build a collection class.
Collection
I just typed in these tests and methods with about two typos and no other errors:
-- Collection
-- RJ 20210318
function testCollection()
CodeaUnit.detailed = false
_:describe("Collection", function()
_:before(function()
end)
_:after(function()
end)
_:test("Test Select", function()
local tab = {10,9,8,7,6,5,4,3,2,1}
local c = Collection(tab)
local sel = c:select(function(x)
return x < 5
end)
local contents = sel:contents()
_:expect(#contents).is(4)
_:expect(contents).has(1)
_:expect(contents).has(2)
_:expect(contents).has(3)
_:expect(contents).has(4)
end)
_:test("Test Map", function()
local tab = {10,9,8,7,6,5,4,3,2,1}
local c = Collection(tab)
local map = c:map(function(x)
return vec2(x,x)
end)
local contents = map:contents()
_:expect(#contents).is(10)
_:expect(contents).has(vec2(1,1))
_:expect(contents).has(vec2(10,10))
end)
end)
end
Collection = class()
function Collection:init(tab)
self.tab = tab
end
function Collection:select(f)
local result = {}
for i,e in ipairs(self.tab) do
if f(e) then
table.insert(result,e)
end
end
return Collection(result)
end
function Collection:map(f)
local result = {}
for i,e in ipairs(self.tab) do
table.insert(result,f(e))
end
return Collection(result)
end
function Collection:contents()
return self.tab
end
The Collection class now understands select and map, and can return its contents. We could use this class in our Dungeon. Let’s commit Collection and then see what it does to Dungeon. We may not like it.
Commit: Collection class with select and map.
Using Collection
We’ll do this in two passes. First this, using Collection in each sub-function and converting back to array:
function Dungeon:availableTilesAtDistanceFromTile(startingTile, targetTile, desiredDistance)
local start = startingTile:pos()
local target = targetTile:pos()
local offsets = self:neighborOffsets()
local choices = self:mapOffsetsToPositions(offsets, start)
local posResults = self:selectOffsetsAtDistance(choices, target, desiredDistance)
local tileResults = self:mapPosToTile(posResults)
local finalResults = self:selectRoomTiles(tileResults)
return #finalResults > 0 and finalResults or { startingTile }
end
-- supporting maps and selects
function Dungeon:mapOffsetsToPositions(offsets,pos)
local offsets = Collection(offsets):map(function(o) return o + pos end)
local results = offsets:contents()
return results
end
function Dungeon:selectOffsetsAtDistance(offsets, tgt, desiredDistance)
local selected = Collection(offsets):select(function(o) return manhattan(o,tgt) == desiredDistance end)
return selected:contents()
end
function Dungeon:mapPosToTile(positions)
local mapped = Collection(positions):map(function(p) return self:getTile(p) end)
return mapped:contents()
end
function Dungeon:selectRoomTiles(tiles)
local selected = Collection(tiles):select(function(t) return t:isRoom() end)
return selected:contents()
end
This runs, passes all the tests. Done by rote.
Now, however, we can inline all these methods. We could do it by rote, saving and renaming, but let’s try to do it directly. We’ll start with a Collection and unwrap it at the end.
function Dungeon:availableTilesAtDistanceFromTile(startingTile, targetTile, desiredDistance)
local start = startingTile:pos()
local target = targetTile:pos()
local offsets = Collection(self:neighborOffsets())
local choices = offsets:map(function(o) return o + start end)
local posResults = choices:select(function(o) return manhattan(o,target) == desiredDistance end)
local tileResults = posResults:map(function(p) return self:getTile(p) end)
local roomResults = tileResults:select(function(t) return t:isRoom() end)
local finalResults = roomResults:contents()
return #finalResults > 0 and finalResults or { startingTile }
end
That runs. We can now remove all those helper methods.
Commit: Use Collection select and map in Dungeon.
Let’s reflect about this.
Reflection: Is This Too Weird?
Most modern languages these days include equivalents to our new select and map functions. We put them on a class of our own, namely Collection. That means that to use them, we have to prewrap our tables and unwrap them at the end. It is tempting to extend Lua tables to include these operations. However, I’m a bit reluctant to do that. I wonder why.
- Monkey Patching
- There’s always risk to monkey patching system classes, in that our patches might not work later on when things change. We could, however, ensure that didn’t happen, with suitable tests.)
- Non-Array Tables
- Lua tables are only sometimes arrays. They also act as hash tables. Often, we know that we’ve built arrays, and we rely on that fact. (That may not be a good decision.) If we add our functions to Lua tables, we would have to make them work on general tables. That’s quite possible, but we’d have to worry about whether we preserve the array properties, especially with select. And we’d lose the ability to use
#to get table length. (Maybe we can live without that.)
Whether or not we move this capability into Lua tables, there is the somewhat odd syntax we have to use to define the selection or mapping function, such as
choices:select(function(o) return manhattan(o,target) == desiredDistance end)
All this may be a bit weird, depending on what you’re used to. But it’s all nicely encapsulated into Collection, and the use of Collection in Dungeon is all down to one method.
I’m going to let this live. We’ll see whether we use the idea elsewhere or not, and I think I’ll experiment with plugging this into Lua tables. That would allow us to remove our Collection class entirely, and reduce our method above by two lines, the wrapping and unwrapping.
Oh Heck, Let’s Do It Now
There’s an issue: we can’t really add a function to all tables. Each table instance has its own metatable, and it seems there’s no way around that. We can, however, implement free-standing functions.
I’ll try that.
Map is easy:
_:test("Test table map", function()
local tab = {10,9,8,7,6,5,4,3,2,1}
local mapped = map(tab,function(x)
return vec2(x,x)
end)
_:expect(#mapped).is(10)
_:expect(mapped).has(vec2(1,1))
_:expect(mapped).has(vec2(10,10))
end)
function map(tab,f)
local r = {}
for k,v in ipairs(tab) do
r[k] = f(v)
end
return r
end
Select is more interesting. On an array, we’d normally expect select to pack up the array into consecutive indices. On a hash table, we’d expect to see the original keys and values.
Unless we either require, implicitly, that our select only works on arrays, or we go to great lengths, we’re stuck with our select returning a sparse table. I don’t see a truly satisfactory solution to this dilemma.
For now, I don’t plan to use this capability but I’d like to finish the attempt. Let’s do two functions.
_:test("Test table array select", function()
local tab = {10,9,8,7,6,5,4,3,2,1}
local sel = arraySelect(tab, function(x)
return x < 5
end)
_:expect(#sel).is(4)
_:expect(sel).has(1)
_:expect(sel).has(2)
_:expect(sel).has(3)
_:expect(sel).has(4)
end)
function arraySelect(tab,f)
local r = {}
for i,v in ipairs(tab) do
if f(v) then
table.insert(r,v)
end
end
return r
end
That’s fine. And:
_:test("Test table tableSelect", function()
local tab = {1,2,3,4,5,6,7,8,9,10}
local sel = tableSelect(tab, function(x) return x%2==1 end)
_:expect(sel[1]).is(1)
_:expect(sel[2]).is(nil)
_:expect(sel[3]).is(3)
end)
function tableSelect(tab,f)
local r = {}
for k,v in pairs(tab) do
if f(v) then
r[k] = v
end
end
return r
end
Those work as expected. We’ll leave them there for now … but they could be used in our Dungeon availableDooDah method instead of collection.
No, I can’t resist. Let’s do. First commit: table operations map, arraySelect, tableSelect.
function Dungeon:availableTilesAtDistanceFromTile(startingTile, targetTile, desiredDistance)
local start = startingTile:pos()
local target = targetTile:pos()
local offsets = self:neighborOffsets()
local choices = map(offsets, function(o) return o + start end)
local posResults = arraySelect(choices, function(o) return manhattan(o,target) == desiredDistance end)
local tileResults = map(posResults, function(p) return self:getTile(p) end)
local finalResults = arraySelect(tileResults, function(t) return t:isRoom() end)
return #finalResults > 0 and finalResults or { startingTile }
end
Tests and game run fine. Collection is now redundant, remove those tests, leave the table ones, and commit: dungeon available checks now use table map and arraySelect.
This has been fun and educational, but also long. Let’s wrap up.
Wrapping Up
I’ve taken an odd step today, adding some more advanced table features, mapping and selection, the latter sometimes called filtering, and using those functions in one location, the Dungeon’s central code for finding available tiles to which to move.
It might be desirable to add those functions to table, so that we’d say table.map(... instead of just map(..., but I’m not sure whether I like that better, perhaps for clarity, or worse, for patching a system table. Either way, nothing of import would change.
More “modern” languages, like Python, include even more capabilities and functions, such as slicing. For now, we’ll stick with these, but we may find it desirable to add a couple of additional functions as time goes on. If we do, the pressure will increase to prefix them with table, or a prefix of our own, just to keep them classified.
I’m not happy with the need for both arraySelect and tableSelect. Probably we’d do well to use only the latter, but that would require us to check a lot of code for use of # and ipairs. We could make # work, I think. I might experiment with that offline. If I do, I’ll report in.
To my taste, what I’ve done today is an improvement. It simplified the code in an important location, and offers opportunities elsewhere. The implementation is a tiny bit deeper in the bag of tricks, but passing functions is a very Lua thing to do, even though we’ve not done it much. So we’ll do well to get used to it, and to look for other opportunities.
The tests served well: they were sufficient to test the new method.There still are too few tests for the other users of our bottom-most avail, but they seem solid sans tests.
That’ll do for today. See you next time!