Dungeon 117
A bit more on Monster movement. I’m not certain the implementation is correct. After that, I’ll think of something.
I was thinking this morning, before I rolled out of bed, about the Monster movement, and how I might easily keep them circling at about a distance of 3. That had me thinking about their strategy selection code, and I couldn’t remember it in enough detail to be certain, without looking, that it’s correct. And I remembered that I had tested only integer values of the range. So to begin, I want to review that code and enhance its tests.
Aha, just as I feared:
function Monster:selectMove(range)
if range > 10 then
return "makeRandomMove"
elseif range >= 4 then
return "moveTowardAvatar"
elseif range == 3 then
return "maintainRange"
elseif range == 2 then
return "moveAwayFromAvatar"
elseif range == 1 then
return "moveTowardAvatar"
else
return "moveAwayFromAvatar"
end
end
I was thinking in terms of integer breaks in the behavior, and this code only checks exact values less than four, and will otherwise move away. I can fix this readily, of course, but my tests should be robust enough to show the problem.
Here’s the range test:
_:test("Select moveTowardAvatar range 4-10", function()
local method
method = Monster:selectMove(10)
_:expect(method, "range 10").is("moveTowardAvatar")
method = Monster:selectMove(4)
_:expect(method, "range 4").is("moveTowardAvatar")
method = Monster:selectMove(3)
_:expect(method, "range 3").is("maintainRange")
method = Monster:selectMove(2)
_:expect(method, "range 2").is("moveAwayFromAvatar")
method = Monster:selectMove(1)
_:expect(method, "range 1").is("moveTowardAvatar")
method = Monster:selectMove(0)
_:expect(method, "range 0").is("moveAwayFromAvatar")
end)
I guess the good news is that the test drove out the behavior, and the bad news is that a weak test drove out weak behavior. Let’s just improve this test, as it is basically a simple list of input and output values. We might also want to think about a different implementation for the method.
I want to fix all that duplication to make the test easier to write, but it won’t save much and this way is at least clear.
But thinking about how tests drive code, what if we had written something like this instead:
_:test("Check monster moves", function()
checkInterval(10.1, 20,"makeRandomMove")
checkInterval(4.0, 10,"moveTowardAvatar")
checkInterval(2.0, 3.9,"maintainRange")
checkInterval(0.1, 1.9,"moveTowardAvatar")
checkInterval(0, 0,"moveAwayFromAvatar")
end)
I’m not sure in my mind quite what I really want there, but two things become clear to me. First, I’m not sure where the boundaries for the decision really should be, and second, I’m not sure quite what I mean by “checkRange”, whether I should check the end points or values in between, and if the latter, how should they be generated.
To the question of boundaries, I think I need to draw a picture.
I put in the approximate distances of the squares from the center, and then decided whether I wanted to move toward the center, away, or remain the same. Anything outside is toward.
This makes the problem a lot more clear, if not the solution.
I’ll still have to be careful with the values, since they’re all the square root of five and such, but we can work with that.
I did think yesterday about the “Manhattan Distance” between points, which is the sum of the x distance and y distance. (I gather that Manhattan streets are a lot like a grid, unless you include the ones that aren’t.)
I think I want to look at that picture in Manhattan distance.
I thought at first that that might be useful, but we have two different decisions being made for Manhattan distance 2. I wonder if I could recolor the graph so that the decision for each square is equal if the Manhattan distances are equal.
Let’s try.
First I drew this:
That shows my assumed regions of where you should move further, closer, or stay the same, but it left me with the odd situation that to stay at Manhattan distance 3, the monster would have to move diagonally.
Then I drew this one, where I wrote down for each Manhattan distance, what Manhattan distance the monster should move to:
We can read that this way:
- at 0, move away to any cell numbered 1. This just tries to keep the monster and player off the same cell.
- at 1, try to move to 0. This is an attack
- at 2, move to an adjacent 1, setting up for attack.
- at 3, move to another three (diagonally). optionally, don’t move.
- at 4 or higher, move to the next lower number.
Note that adjacent numbers are always right angle moves from the current number, which is nice.
Those rules make some sense, but they may not be easily implemented. What would we have to do? Suppose we assume right angle moves, setting aside the 3 for now. If we know the princess’s coordinates, and some tile’s coordinates, then the Manhattan distance between them is just xt-xp + yt-yp.
So it seems that given a monster at (xm,ym), at Manhattan distance (MD) d, if d is four or higher we want to move to one of the (two) adjacent cells that are at distance d-1. Of course, if they are walls, we can’t move. I’ve chosen to let that happen, which means that sometimes a monster doesn’t move, having unfortunately tried to walk into a wall.
This thinking is making me want to recast this selection logic in terms of MD. Let’s TDD some MD. We have vector position for all cells, so we can probably work at that level and then fetch tiles as needed. Unfortunately, Lua doesn’t provideMD as part of vec2 but that’s no biggie.
_:test("Manhattan Distances", function()
local v1,v2
v1 = vec2(0,0)
v2 = vec2(0,0)
_:expect(manhattan(v1,v2)).is(0)
end)
This demands:
function manhattan(v1,v2)
return 0
end
Yes, “fake it till you make it”. So far so good.
_:test("Manhattan Distances", function()
local v1,v2
v1 = vec2(0,0)
v2 = vec2(0,0)
_:expect(manhattan(v1,v2)).is(0)
v2 = vec2(10,0)
_:expect(manhattan(v1,v2)).is(10)
end)
My thing that makes broken tests display seems not to be working. That does, of course fail:
1: Manhattan Distances -- Actual: 0, Expected: 10
What I’m seeing on the screen is a brief flash of the red test report, then the DO YOU HAVE A TEST FOR THAT? comes up.
I hate when something like this derails me, so I’m going to take a quick look to see why the tests aren’t displaying.
I found a bit of hackery that makes them display if red, but I’m not sure why what was working the other day has stopped today. Anyway, committing that fix: CodeaUnit displays if red or yellow.
Weird. Returning to where we were:
Ah, it may have to do with the size of the display, I ran into that before. And it’s definitely over the edge. A smaller font size fixes it. It’d be nice if I could fix that display to just show the broken ones. Not today. Back to Manhattan.
1: Manhattan Distances -- Actual: 0, Expected: 10
As expected. Let’s code. I’m impatient. Forgive me for going right at this, I’ve been made impatient by the hassle with the tests displaying:
function manhattan(v1,v2)
local abs = math.abs
if #v2 ~= #v1 then return 0 end
local s = 0
for i in ipairs(v1) do
s = s + abs(v2[i]-v1[i])
end
return s
end
This is now generalized to any length of vector. I’ll add a few more tests for clarity.
_:test("Manhattan Distances", function()
local v1,v2
v1 = vec2(0,0)
v2 = vec2(0,0)
_:expect(manhattan(v1,v2)).is(0)
v2 = vec2(10,0)
_:expect(manhattan(v1,v2)).is(10)
v2 = vec2(0,10)
_:expect(manhattan(v1,v2)).is(10)
v2 = vec2(10,10)
_:expect(manhattan(v1,v2)).is(20)
v1 = vec4(0,0,0,0)
v2 = vec4(10,10,10,10)
_:expect(manhattan(v1,v2)).is(40)
end)
I think that’ll do. I’d like to check in the function for the two vectors being of the same type, but there’s no way that I’m aware of to do that, because they don’t respond to #, though they do respond to ipairs
Anyway that’ll do for today’s purposes.
Let’s look at our actual problem and see what we can devise.
Commit: Manhattan Distance defined and tested.
Monsters Decide Strategy Based on Manhattan Distance
That’s our story (and we’re sticking to it). Here, again, is our code of interest:
function Monster:chooseMove()
-- return true if in range of player
if self:isDead() then return false end
local range = self:distanceFromPlayer()
local method = self:selectMove(range)
self[method](self)
return range <= 10
end
function Monster:selectMove(range)
if range > 10 then
return "makeRandomMove"
elseif range >= 4 then
return "moveTowardAvatar"
elseif range == 3 then
return "maintainRange"
elseif range == 2 then
return "moveAwayFromAvatar"
elseif range == 1 then
return "moveTowardAvatar"
else
return "moveAwayFromAvatar"
end
end
How far do we want to go, and how big do we want out steps to be? Well, we want the steps to be small, that’s for sure, since there’s no reason to believe I’ve suddenly become really smart. Let’s TDD a new method, selectManhattanMove().
I think we’ll see about working entirely with the tile positions, which we’ll assume for now are vec2, though that will seem a lot like Primitive Obsession for a while. I think we can dispense with that concern in due time.
No, I have a better idea. We’ll create a new test double. We already have a FakeTile class, but rather than use that one, I want a new one, because it’ll tell me exactly what I need, if anything, on the real Tiles.
So for my first test:
_:test("Monster moves, manhattan", function()
local tm, tp, move
local low = 0.25
local high = 0.75
tp = FakeMTile(30,30)
tm = FakeMTile(29,30)
move = Monster:selectManhattanStep(low)
_:expect(move).is(vec2(1,0))
end)
Notice that I’ve already renamed my new method to selectManhattanStep, to return the step I want to take. Part of the value of TDD is in helping us understand what we want the protocol to be, and I’m still deciding. Let’s see how this feels. Clearly in this case we want to move to the monster.
The test demands the class:
4: Monster moves, manhattan -- Tests:405: attempt to call a nil value (global 'FakeMTile')
FakeMTile = class()
function FakeMTile:init(pos)
self.pos = pos
end
Looking at the class I think I want a vector here, so let’s change the test:
_:test("Monster moves, manhattan", function()
local tm, tp, move
local low = 0.25
local high = 0.75
tp = FakeMTile(vec2(30,30))
tm = FakeMTile(vec2(29,30))
move = Monster:selectManhattanStep(low)
_:expect(move).is(vec2(1,0))
end)
This demands a new method, selectManhattanStep:
function Monster:selectManhattanStep()
return vec2(1,0)
end
Works so far.
tm = FakeMTilw(vec2(31,30))
move = Monster:selectManhattanStep(low)
_:expect(move).is(vec2(-1,0))
Now as I think about implementing this, I think I’d like to have another function, manhattanXY(v2,v1), which is the directed number of blocks north and east. I’ll compute it inline for now.
I get this far:
function Monster:selectManhattanStep()
local md = self:manhattanDistanceToPlayer()
if md == 1 then
local steps = self:manhattanStepsToPlayer()
return steps
end
end
function Monster:manhattanDistanceToPlayer()
return manhattan(self:getPos(), self:getPlayerPos()
end
I note that to get those positions, I have to pull the guts out of the monster, to tile, to pos, and ditto player. Not good. Let’s defer to the tiles:
function Monster:manhattanDistanceToPlayer()
return self.tile:manhattan(self:getPlayerTile())
end
We don’t have getPlayerTile() yet. But wait. Maybe we should defer up to Runner, who could then defer downward.
That might be better. We’re authorized to talk with the GameRunner. But then we’d be in for something like this:
function Monster:selectManhattanStep()
local md = self:manhattanDistanceToPlayer()
if md == 1 then
local steps = self:manhattanStepsToPlayer()
return steps
end
end
function Monster:manhattanDistanceToPlayer()
return self.runner:manhattanDistanceToPlayer()
end
function Monster:manhattanStepsToPlayer()
return self.runner:manhattanStepsToPlayer()
end
I don’t like this running up and down to GameRunner. I like it less and less every time I have to do it. Objects shouldn’t have to call upward, they should call downward, toward more primitive objects, or so it seems to me.
We do have a fundamental issue going on here, which is the way all our objects are linked together. Most everyone knows the Runner, and therefore calls back up to it. That results in extra methods that don’t add capability, just connection, and since I’m human as far as you know, it often induces too much primitive obsession in objects that are high up, instead of deferring downward, just because I get tired of calling calling calling, so I rip the guts out of something instead in a fit of pique. This is not good.
I’ve reverted this last bit, the code in Monster and the test that requires it, which preserves the basic manhattan test committed earlier. Then I’m going to think a bit about a design improvement that will make this job easier.
DungeonTile?
Right now, the GameRunner holds on to at least these things:
- The Tile array
- The list of Monsters
- The Player
- The MusicPlayer
- The crawl floater
Each Tile knows the GameRunner, and its own x,y coordinates, ranging in integers from 1 to something. Each Monster knows the runner, and its current tile. The Player knows the runner, and its current tile.
We’ve started to push some GameRunner functions to Dungeon, which is an ephemeral class that’s mostly used to find open spaces under various conditions like “far away”.
Just musing, what if we made Dungeon not so ephemeral, instead creating it as GameRunner’s only access to the tiles. We could create a new one each time we create a level, if that’s convenient. Once the level is set up, it’s unchanging, in the sense that walls and floors don’t suddenly appear and disappear. We could easily ensure that the Dungeon is, or becomes, read only.
Suppose further that we had a new object, say DungeonTile, that consists of a pointer to the Dungeon and a position, just the x and y coordinate of the tile in question. The tile itself would still contain the rest of the Tile info. Instead of runner, it would know its dungeon, and its kind, room number, visibility details and so on.
(There may be no upside to having the two objects, we’re just thinking. Current Tile isn’t terribly complicated. Still, separating its position out from everything else might have value.)
What if the Dungeon knew directly where the player is? GameRunner knows that now, with a pointer to Player. Dungeon could hold that instead. Maybe we push the knowledge of Monsters down to Dungeon also. If we can find the right division of responsibilities, we can make GameRunner smaller, and Dungeon not too much bigger.
Monsters would pretty obviously know their tile. In making decisions, we now believe that they want to know something like the Manhattan distance to the player, and/or the actual signed values of the vector, that is playerPos - monsterPos kind of thing.
The question a Monster wants to ask, really, is “given that my tile is x,y, what tile should I try to move to? Now it seems to me that the monster wants to own the responsibility to know whether to move to a distance greater than current or less than current (or, in the one case, maybe same as current). But maybe the Dungeon or tiles should decide which tiles are candidates:
A question like “Dungeon, pick a cell with md to the princess one less than mine” might be a reasonable thing to ask.
Or maybe even “Dungeon, moveTowardPlayer”, or “Dungeon, moveAwayFromPlayer”, or “Dungeon, moveSameDistanceFromPlayer”
That seems almost doable, and I don’t think we’d have to force the GameRunner part immediately.
I want to experiment with that last idea a bit. Let’s write a test. Suppose we said this:
_:test("Dungeon helps monster moves", function()
local dungeon = Runner:getDungeon()
dungeon:setPlayerPos(vec2(30,30))
local monsterTile = dungeon:getTile(34,34)
_:expect(dungeon:manhattanToPlayer(monsterTile)).is(8)
end)
That seems reasonable. Note that I’ve sent the player position to Dungeon, which is a bit iffy but also is the minimum info it needs. So …
function Dungeon:setPlayerPosition(pos)
self.playerPos = pos
end
And then:
function Dungeon:manhattanToPlayer(tile)
local tpos = tile:pos()
return manhattan(self.playerPos)
end
I’m having trouble getting the test to run without breaking the game. This is my usual issue with testing around GameRunner, which is that its setup is so intricate that it’s hard to get it right. I thought I had correctly saved and restored everything, but apparently not. Let me dig for a test that works.
Here’s one to try:
_:before(function()
_TileLock = TileLock
TileLock = false
_tweenDelay = tween.delay
tween.delay = fakeTweenDelay
_Runner = Runner
Runner = GameRunner()
Runner:createTiles()
end)
_:after(function()
TileLock = _TileLock
Runner = _Runner
tween.delay = _tweenDelay
end)
That seems to avoid the crash. I thought I had the equivalent but maybe I didn’t. Now the test fails:
2: Dungeon helps monster moves -- Tests:439: attempt to call a nil value (method 'setPlayerPos')
I thought I had implemented that. Oh, I said “position”. Let’s use that.
2: Dungeon helps monster moves -- TestDungeon:112: attempt to index a number value (local 'pos')
There can be no question that I’m tired and distracted. We just had a Sandhill Crane family come through and the child was trapped in the neighbor’s yard, unable to perceive that a chain link fence needed to be jumped or flown over. That got resolved when the neighbor drove the child out the other way, but it hasn’t helped my concentration any.
getTile wants a vector.
_:test("Dungeon helps monster moves", function()
local dungeon = Runner:getDungeon()
dungeon:setPlayerPosition(vec2(30,30))
local monsterTile = dungeon:getTile(vec2(34,34))
_:expect(dungeon:manhattanToPlayer(monsterTile)).is(8)
end)
I’m hopeful for green now. It appears that hope is still not a great strategy:
2: Dungeon helps monster moves -- Tests:451: attempt to index a nil value (local 'v2')
That’s a bad call to manhattan.
function Dungeon:manhattanToPlayer(tile)
return manhattan(tile:pos(), self.playerPos)
end
And the test runs. I’m discernibly tired and not at my sharpest, so I’ll sum up and take a break.
Summary
The current implementation of monster move selection is close enough to working to leave it in, but an early check made it clear that it’s not robust, assuming integer distance values, which is not the case.
That got me thinking about Manhattan distance, however, and I now have a function that computes it, and a function in Dungeon that can tell us the Manhattan distance to the Player (given that we tell it where the Player is, which we’ll do in due time). I’ve got some decent tests for the distance, and a framework for the tests for the actual decision feature, and a fairly good idea of how that’s going to be puused downward, at least to Dungeon if not even further down.
It would be trivial to move manhattan to Tile. In fact, let’s do that now.
We can change this:
function Dungeon:manhattanToPlayer(tile)
return manhattan(tile:pos(), self.playerPos)
end
To, say, this:
function Dungeon:manhattanToPlayer(tile)
return tile:manhattanDistance(self:playerTile())
end
function Dungeon:playerTile()
return self:getTile(self.playerPos)
end
And then:
function Tile:manhattanDistance(aTile)
return manhattan(self:pos(), aTile:pos())
end
That’s nearly good, actually, Commit: manhattan distance pushed down to Tile.
That’s a bit better. I want to talk about what’s going on here.
It became clear that I needed more thinking (“design”) than I presently had in my head, and that the system’s “design” wasn’t helping, at least the way I was using it. So I did a bit more non-coding thinking, which is what you do when you need more thinking.
But I turned very quickly back to writing a test and making it work. Why? Because I’ve learned that my thinking about code isn’t precise enough to ensure that my thoughts won’t go quickly off the rails, just enough to make some of my assumptions about the code, well, how can I best put this, wrong.
So I turn back to code, especially TDD code, as soon as I reasonably can. This tends to solidify the soft spots in the code (and my head), and if I discover that it isn’t quite right, I can always undo or revert. I find that this approach, especially when I’ve got TDD working well, helps me get from idea to good code the fastest.
And that’s why we do TDD, and it’s how we always try to work: we want to get from idea to good code as quickly as possible. Not idea to code: idea to good code.
And we’re getting there. See you next time!