Dungeon 119
What we need here is a Strategy. Well, not so much need. Want.
Here we are, a cold sunny Saturday. We’re at the end of the sixth tranche of Dung articles and still going strong. It’s really time to start working on non-combat fun, since combat is now almost impossible to get into, but before moving along, I want to try a technical idea.
The story idea is that I’d like to have different styles of monster behavior. I’d like them to be able to get angry. Perhaps if you do attack a monster, monsters within range go into a rage and no longer keep their distance. Perhaps there is one kind of monster that keeps its distance, but if you follow it, it leads you to the WayDown. Perhaps there is another kind that leads you into traps.
One way of putting it would be that different monsters have different behavior strategies. There is a software design pattern called Strategy (q.v.) that is just the thing one needs for this. Another related term is “pluggable behavior”, the point being that depending on what’s appropriate, a different behavior is “plugged in” at run time.
Our monster motion is a prime candidate for this kind of thing, because it all comes down to this:
function GameRunner:playerTurnComplete()
if self.requestNewLevel then
self:createLevel(12)
self.requestNewLevel = false
else
self.playerCanMove = false
self.monsters:move()
self.playerCanMove = true
end
end
function Monsters:move()
for i,m in ipairs(self.table) do
m:chooseMove()
end
end
function Monster:chooseMove()
-- return true if in range of player
if self:isDead() then return false end
local range = self:manhattanDistanceFromPlayer()
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
GameRunner tells the Monsters collection to move the monsters, it tells each monster to choose a move, and they (presently) select a move based on our new manhattan distance-based decision tree.
Recall that we used to have a more aggressive kind of motion, which was random beyond distance 10 and otherwise “move toward avatar”. This meant that if you got within 10 tiles of a monster, it would attack you if it possibly could.
Clearly we used to have one strategy for monsters, and now we have another. If one were going to name them, one might choose terms like “peace-loving” or “diffident” versus “aggressive” or “hunter-killer”. One might, in other words, name the strategies.
You could argue that, yes, a pluggable or strategy approach to monster behavior would be a sensible design, and it’s too bad that we didn’t put that in just now when we instead removed the old way and replaced it with the new. But now that that has been done, there’s no call to do it now, unless we have a story that takes us back into that code.
And you’d probably be right, in a real product development situation. We’d have a deadline, and we’d want to go as fast as safely possible, and that means that we defer refactoring until a time when it will clearly help us. And, truth be told, even then we could put in a lot of if statements selecting behavior before it would seem like a good idea to use pluggable behavior,
Except, no. First of all, as I think we’re about to see, converting to pluggable behavior when you only have one behavior is a very small effort, and, second, we are here to simulate “real” development, so if we have to make up an opportunity to try something, we’ll do it.
So let’s get down to it.
What do we want?
We want to somehow change our current monster behavior approach (lower-case strategy) so that all the motion decisions are partitioned off separately, and so that, in the future, we could plug in a different strategy either at monster creation, or even during the monster’s lifetime.
What is the thing called in object-oriented programming that does things this? Oh, yeah, a class. So what we want to do is build a class that manages our current behavior on behalf of a single monster.
It’s pretty clear where this thing goes:
function Monster:chooseMove()
-- return true if in range of player
if self:isDead() then return false end
local range = self:manhattanDistanceFromPlayer()
local method = self:selectMove(range)
self[method](self)
return range <= 10
end
Now that code could use a little refactoring. Depending on how you count, it includes at least two and maybe three or more ideas. Let’s start by refactoring to make those ideas more explicit.
As we look at that code, we see that it is arguably a bit too clever. If has a guard clause that exits if the monster is dead, returning the necessary false to say that it’s not in range. (We use that result to decide whether to display the monster’s attribute sheet.) Then the code gets the range and caches it to use later, then uses it to select the movement method, and then it executes that method. Finally, it uses the cached value.
Why did I cache that value? I didn’t want to compute it twice. That’s not a great reason to do something like that. Sure, it saves a couple of fetches and a bit of arithmetic, but really, this is the 21st century and we don’t need to chase cycles.
But wait. Do we want to return the monster’s previous range, or range after moving? Arguably we want to check after moving. Either way, it’ll change the system behavior only slightly if we don’t cache it. Let’s do this:
function Monster:chooseMove()
-- return true if in range of player
if self:isDead() then return false end
self:executeMoveStrategy()
return self:manhattanDistanceFromPlayer() <= 10
end
function Monster:executeMoveStrategy()
local method = self:selectMove(self:manhattanDistanceFromPlayer())
self[method](self)
end
Now the motion behavior is separated from the range stuff. We could quibble about whether we should be checking for dead, but since dead monsters are probably not going to move, it can be said that the decision belongs up there. Otherwise there’d be duplication.
This was a pure refactoring, and the tests and game run. Commit: break out monster movement into its own method.
Now let’s create a class to contain all this behavior and use it,
I’m going to create it incrementally and we’ll use the failure of tests and, perhaps, the game, to guide the moves.
First, I modify the method above this way:
function Monster:executeMoveStrategy()
local mover = CalmMonsterStrategy(self)
mover:execute()
end
function Monster:calmExecute()
local method = self:selectMove(self:manhattanDistanceFromPlayer())
self[method](self)
end
I’ve declared the name of the class, and its entry method, execute. And I’ve saved the old code from executeMoveStrategy in a new method calmExecute, which we’ll use in a moment and then remove in another moment.
Now the class:
-- CalmMonsterStrategy
-- RJ 20210313
CalmMonsterStrategy = class()
function CalmMonsterStrategy:init(monster)
self.monster = monster
end
function CalmMonsterStrategy:execute()
self.monster:calmExecute()
end
I just call back to the calmExecute that I left lying there.
Pure refactoring, tests and game run. Commit: first implementation, CalmMonsterStrategy.
No, really. We should ship this. Now let’s move the plugging in up where it belongs:
function Monster:initAttributes()
local health = CharacterAttribute(self:roll(self.mtEntry.health))
local strength = CharacterAttribute(self:roll(self.mtEntry.strength))
local speed = CharacterAttribute(self:roll(self.mtEntry.speed))
local attrs = { _health=health, _strength=strength, _speed=speed }
self._characterSheet = CharacterSheet(attrs)
self._mover = CalmMonsterStrategy(self)
end
function Monster:executeMoveStrategy()
self._mover:execute()
end
Tests run, game runs. Commit: monsters get CalmMonsterStrategy at init.
I don’t like the name _mover. Should be _movementStrategy. Rename. Tests and game run. Commit: rename _mover to _movementStrategy.
Why am I committing all these times? Because every one of these tiny steps leaves the game working. We could spread this work over days or weeks if we needed to. And each step takes longer to write up than it does to do.
Let’s do some real work. We’ll move calmExecute out of Monster:
function Monster:calmExecute()
local method = self:selectMove(self:manhattanDistanceFromPlayer())
self[method](self)
end
That becomes:
function CalmMonsterStrategy:execute()
self:calmExecute()
end
function CalmMonsterStrategy:calmExecute()
local method = self.monster:selectMove(self.monster:manhattanDistanceFromPlayer())
self.monster[method](self.monster)
end
You see what we’re doing. We’re moving over one method at a time, delegating everything back to the methods still left in Monster. This is weird, but it’s totally incremental. Every one of these moves can be made and the system left in the new state.
We can refactor the above:
function CalmMonsterStrategy:execute()
local method = self.monster:selectMove(self.monster:manhattanDistanceFromPlayer())
self.monster[method](self.monster)
end
That’s just “Inline Method” refactoring.
Now this may feel rather silly, doing these one step at a time. And it feels silly to me, too, except that I can be sure that this way I can stop at any point and I am far less likely to make a mistake than if I were to try to do it in a lump.
We need to think about what we want to move, and what we want to leave over in Monster. The simple answer, not necessarily easy, is that we want everything about the strategy over here, and everything about the monster over there. So the selectMove, we want.
function CalmMonsterStrategy:execute()
local method = self:selectMove(self.monster:manhattanDistanceFromPlayer())
self.monster[method](self.monster)
end
function CalmMonsterStrategy: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
That move, however, breaks a couple of tests, since we’re moving behavior away from where the test expects it. This is why we have tests, and why they irritate us sometimes.
1: Select makeRandom at long range -- Tests:362: attempt to call a nil value (method 'selectMove')
2: Select moveTowardAvatar range 4-10 -- Tests:368: attempt to call a nil value (method 'selectMove')
Those tests are this:
_:test("Select makeRandom at long range", function()
local method = Monster:selectMove(15)
_:expect(method).is("makeRandomMove")
end)
_: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 freely grant that I was not anticipating this issue. I’m not surprised that some tests broke, but I am mildly irritated that I’ll have to change these. However, I can do that simply by changing the class that we call.
_:test("Select makeRandom at long range", function()
local method = CalmMonsterStrategy:selectMove(15)
_:expect(method).is("makeRandomMove")
end)
_:test("Select moveTowardAvatar range 4-10", function()
local method
method = CalmMonsterStrategy:selectMove(10)
_:expect(method, "range 10").is("moveTowardAvatar")
method = CalmMonsterStrategy:selectMove(4)
_:expect(method, "range 4").is("moveTowardAvatar")
method = CalmMonsterStrategy:selectMove(3)
_:expect(method, "range 3").is("maintainRange")
method = CalmMonsterStrategy:selectMove(2)
_:expect(method, "range 2").is("moveAwayFromAvatar")
method = CalmMonsterStrategy:selectMove(1)
_:expect(method, "range 1").is("moveTowardAvatar")
method = CalmMonsterStrategy:selectMove(0)
_:expect(method, "range 0").is("moveAwayFromAvatar")
end)
Even without a Replace function that I trust, that took moments. Test run, game runs. Commit: Move selectMove to CalmMonsterStrategy.
Again we should ship it.
Now what about the selected moves, from here:
function CalmMonsterStrategy: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
Those seem to me not to be germane to a particular strategy, so as such, I think we’ll leave them there for now. However, their names vary oddly, and that seems likely to be confusing. Let’s rename them so they are more clearly all of a kind.
I think I’ll just let them all start with move for now, though I’m tempted to … in fact, yes … let’s rename them all to basicMoveEtc, to make it even more clear that they are primitive movers to be called.
function CalmMonsterStrategy:selectMove(range)
if range > 10 then
return "basicMoveRandomly"
elseif range >= 4 then
return "basicMoveTowardPlayer"
elseif range == 3 then
return "basicMaintainRangeToPlayer"
elseif range == 2 then
return "basicMoveAwayFromPlayer"
elseif range == 1 then
return "basicMoveTowardPlayer"
else
return "basicMoveAwayFromPlayer"
end
end
Now I’ll group those methods in Monster, before I forget
Tests and game run. Commit: CalmMonsterStrategy in full play.
I think we’re done here, but I did notice something odd during testing. I cornered one monster and then pressed the “Flee” button repeatedly, which doesn’t move the princess but does let the monsters move. Another monster approached, and stopped three cells away from me on my right. When I repeatedly pressed “Flee”, that monster never moved I would have expected it to move diagonally, from three o’clock toward 2 or 4, which are also cells that are at distance three from the player.
I’m going to put some prints into the maintain range code to see what happens.
function Monster:basicMaintainRangeToPlayer()
local dungeon = self.runner:getDungeon()
local tiles = dungeon:availableTilesAtDistanceFromPlayer(self.tile)
print("maintain ", #tiles)
self.tile = self.tile:validateMoveTo(self,tiles[math.random(1,#tiles)])
end
When I get some monsters positioned at 3 tiles away (manhattan), the print says “maintain 1”, telling me that it’s probably only finding the original location. Weird, I thought that was well tested.
Oh that’s the wrong method. Interesting. It should be:
availableTilesSameDistanceFromPlayer
The tests check to be sure that function works, but there’s no test to be sure Monster calls it. And it didn’t.
Changed and now we get this nice hovering behavior:
Commit: fix bug in same distance logic.
I’m about done for this morning, but let’s see if we might have tested for this problem. The defect was in this method:
function Monster:basicMaintainRangeToPlayer()
local dungeon = self.runner:getDungeon()
local tiles = dungeon:availableTilesSameDistanceFromPlayer(self.tile)
self.tile = self.tile:validateMoveTo(self,tiles[math.random(1,#tiles)])
end
This method, as written, embeds the random selection right in it. This is compact and correct–and hard to test. There are three methods with this same basic shape:
function Monster:basicMaintainRangeToPlayer()
local dungeon = self.runner:getDungeon()
local tiles = dungeon:availableTilesSameDistanceFromPlayer(self.tile)
self.tile = self.tile:validateMoveTo(self,tiles[math.random(1,#tiles)])
end
function Monster:basicMoveAwayFromPlayer()
local dungeon = self.runner:getDungeon()
local tiles = dungeon:availableTilesFurtherFromPlayer(self.tile)
self.tile = self.tile:validateMoveTo(self,tiles[math.random(1,#tiles)])
end
function Monster:basicMoveTowardPlayer()
local dungeon = self.runner:getDungeon()
local tiles = dungeon:availableTilesCloserToPlayer(self.tile)
self.tile = self.tile:validateMoveTo(self,tiles[math.random(1,#tiles)])
end
I suspect that if we remove this duplication, we’ll find something that we can test. But removing the duplication is tricky. We can start by passing a dungeon to each of those methods:
function CalmMonsterStrategy:execute(dungeon)
local method = self:selectMove(self.monster:manhattanDistanceFromPlayer())
self.monster[method](self.monster, dungeon)
end
Of course we need to pass that in now:
function Monster:executeMoveStrategy()
self._movementStrategy:execute(self:getDungeon())
end
function Entity:getDungeon()
return self.runner:getDungeon()
end
This lets me do this:
function Monster:basicMaintainRangeToPlayer(dungeon)
local tiles = dungeon:availableTilesSameDistanceFromPlayer(self.tile)
self.tile = self.tile:validateMoveTo(self,tiles[math.random(1,#tiles)])
end
function Monster:basicMoveAwayFromPlayer(dungeon)
local tiles = dungeon:availableTilesFurtherFromPlayer(self.tile)
self.tile = self.tile:validateMoveTo(self,tiles[math.random(1,#tiles)])
end
function Monster:basicMoveTowardPlayer(dungeon)
local tiles = dungeon:availableTilesCloserToPlayer(self.tile)
self.tile = self.tile:validateMoveTo(self,tiles[math.random(1,#tiles)])
end
This is better on its own account, but still isn’t giving me anything more testable. I think what we need to do here is to break out the selection of the tile collection to be moved among, and only then choose a random one. That would change the agreed protocol between the CalmMonsterStrategy and the Monster. This is, however, suggesting to me that maybe we do want to move the basicMove... methods down to the strategy. The only issue with that will be that we’ll want all the basics available to all the strategies, any of which may want to use any or all of them. And since the strategies, for now, seem to be going to be different classes, where would the basics live?
Of course the strategies could be functions, since there’s really only the one entry point, execute, all living in one big strategy class, or living separately but following their own rules. And there are surely other ways.
Be all that as it may, we’ve done enough programming and writing for a Saturday, so let’s commit this: Movement Strategies are passed a Dungeon in execute, and sum up.
Summary
Another good day. We’ve moved the strategic elements of monster motion over to a new class, and it should be easy to see that we could quickly create another strategy class and plug it into any monster, at any time. We could quite readily make a Raging Ghost, or suddenly let the smell of Monster blood anger all the monsters nearby.
And maybe we will.
We made the move in a large number of tiny steps. We could have shipped the product at any time. We did eight commits in under two hours, and could have done a couple more.
We did find one pre-existing defect, by chance, and it has identified a gap in our testing, and in our testability. I’ve made a note to address that, and perhaps we will. In any case, the actual defect was readily fixed.
A good day. And I wish you one as well.