Robot 45
There is a sticky note on my desk needing attention. Let’s attend to it. I have a small concern. Also: smaller steps pay off.
The note, as best as I can make out, says “tix frosbds fav multific faos, venive dups”. I’m pretty sure that means “Fix knowledge for multiple facts, remove dups”. Be that as it may, we do have an issue to deal with that sounds like that one.
The current storage for facts in the Knowledge class is a simple last in first out list: when a new fact comes in, we push it onto the front of a table,and when we look for facts and a given x,y, we search from the front of the table. So far that works find, but the size of that table grows without bound.
My initial plan, since a fact has x, y, and a string like “LOOK” or “OBSTACLE” or “ROBOT”, was to store facts in a dictionary indexed by x, containing a dictionary indexed by y, containing the string. That would actually work just fine … for now.
In fact, it works so closely to correctly that I think we’ll do it.
Knowledge
The germane bits of Knowledge are these:
Knowledge = class()
function Knowledge:init()
self.facts = {}
end
function Knowledge:addFactAt(content, x,y)
self:privateaddFactAt(Fact(x,y,content))
end
function Knowledge:factAt(x,y)
for i,fact in ipairs(self.facts) do
if fact.x == x and fact.y == y then return fact.content end
end
return nil
end
function Knowledge:factCount()
return #self.facts
end
function Knowledge:privateaddFactAt(aFact)
table.insert(self.facts, 1, aFact)
end
Insert at the beginning, search from the beginning.
Let’s replace the Knowledge store, a simple table, with something better. And let’s TDD that something better as a separate class. Let’s call it XYStore.
XYStore
We write a trivial test:
_:test("XYStore", function()
local store = XYStore()
end)
Which requires:
1: XYStore -- XYStore:17: attempt to call a nil value (global 'XYStore')
We parry that attack with:
XYStore = class()
The test attacks again:
_:test("XYStore", function()
local store = XYStore()
store:save(11,31,"something")
local what = store:fetch(11,31)
_:expect(what).is("something")
end)
In the spirit of the simplest thing, I respond with:
function XYStore:save(x,y,s)
self._s = s
end
function XYStore:fetch(x,y)
return self._s
end
Take that! I cry. The test desires to force me to do some work, and it attacks again:
_:test("XYStore", function()
local store = XYStore()
store:save(11,31,"something")
store:save(23,45,"other")
local what = store:fetch(11,31)
_:expect(what).is("something")
end)
OK, enough fooling around, let’s do the thing.
function XYStore:init()
self._xxx = {}
end
function XYStore:save(x,y,s)
local xDict = self._xxx[x] or {}
xDict[y]=s
self._xxx[x] = xDict
end
function XYStore:fetch(x,y)
local xDict = self._xxx[x] or {}
return xDict[y]
end
I feel confident that the test is vanquished, but in a vain attempt to find me out, it attacks one more time:
_:test("XYStore", function()
local store = XYStore()
store:save(11,31,"something")
store:save(23,45,"other")
local what = store:fetch(11,31)
_:expect(what).is("something")
_:expect(store:fetch(23,45)).is("other")
_:expect(store:fetch(666,666)).is(nil)
end)
My code resists the attack. I think XYStore is done.
But then the test attacks from an unexpected direction!
_:test("XYStore", function()
local store = XYStore()
store:save(11,31,"something")
store:save(23,45,"other")
local what = store:fetch(11,31)
_:expect(what).is("something")
_:expect(store:fetch(23,45)).is("other")
_:expect(store:fetch(666,666)).is(nil)
_:expect(store:itemCount()).is(2)
end)
A hit, a palpable hit! But I rally and respond:
function XYStore:itemCount()
local count = 0
for _k,xD in pairs(self._xxx) do
for _l,s in pairs(xD) do
count = count + 1
end
end
return count
end
I feel that I am surely victorious. But the test tries one more time:
_:test("count empty", function()
local store = XYStore()
_:expect(store:itemCount()).is(0)
end)
I run the test with my left hand, showing contempt for the test. I am victorious at last.
Now let’s plug XYStore into Knowledge. But first, commit: XYStore saves single items under x and y keys.
Knowledge Upgrade
We surely have enough tests involving knowledge to plug this in without new ones.
function Knowledge:addFactAt(content, x,y)
self:privateaddFactAt(Fact(x,y,content))
end
We’ll continue to save the fact instance. We’re here to reproduce function, not to change it.
function Knowledge:addFactAt(content, x,y)
self.facts:store(x,y,Fact(x,y,content))
end
And:
function Knowledge:factAt(x,y)
for i,fact in ipairs(self.facts) do
if fact.x == x and fact.y == y then return fact.content end
end
return nil
end
This becomes:
function Knowledge:factAt(x,y)
local fact = self.facts:fetch(x,y) or Fact(x,y,nil)
return fact.content
end
And:
function Knowledge:factCount()
return #self.facts
end
This becomes:
function Knowledge:factCount()
return self.facts:itemCount()
end
This gets removed:
function Knowledge:privateaddFactAt(aFact)
table.insert(self.facts, 1, aFact)
end
This has no callers and gets removed:
function Knowledge:dump()
for i,f in ipairs(self.facts) do
print(f)
end
end
We test. Everything breaks. We have said ‘store’ here, and the XYStore uses save. This is a hint that store is the better term and we change XYStore and its tests to match.
We are green. The game plays correctly, and facts grow rapidly but not insanely. Remember that in a radius 8 circle there are almost 200 cells to inspect, and since we include a “LOOK” item for each empty cell, we’ll have a storage memory of almost 200 items per scan. That’s better than thousands, but it’s still enough to make us wonder a bit.
Anyway, we’ve done what we planned, so commit: Knowledge uses XYStore, reducing storage requirements substantially.
I mentioned a concern in the article blurb.
Concern
The game supposedly includes other Robots in addition to our own. Those Robots are supposed to show up on our radar … and it is possible that that Robot would be “on top of” something else in the world. It could be in a Pit, for example.
The way things stand now, only the Pit or the Robot could appear in our Knowledge. On the Robot side, that might not even be noticed … but on the World side, if a Robot fell into a Pit (and if there was a way out of a Pit, perhaps after a delay), it’s likely that the Pit would be erased by the Robot, and then when the Robot moved … no more pit.
My current plan is to burn that bridge when we come to it. We are storing things inside Fact objects, which could be enhanced to allow for Robot plus something else, or some such thing. So I conclude “we’re not in big trouble, guys!”
Let’s sum up. We’ve actually seen a little lesson or two here.
Summary
There’s no question that we could have plugged a dictionary directly into Knowledge, and used it the same as we do in XYStore, and made Knowledge work in the new only one thing at a place fashion. But had we done so, while the tests we have would have served to get the job done, I think the job would have been a bit harder … and TDDing the separate XYStore was straightforward and simpler, and plugging it in was simple as well.
We changed a somewhat large step, plug a more complex store into Knowledge into two smaller steps, create a more complex store, and plug the existing new store into Knowledge. The two smaller steps went quite smoothly, and the second step fed back to the first, with “store is a better word than save”.
Smaller steps. Absolutely always better? Perhaps not, but that’s the way to bet.
Soon, I think I’ll be doing something completely different. And I am still open to ideas from all three of my readers.
See you next time!