Dungeon 121
I think today I’ll try some pathfinding. And, yes, I have a story asking for it.
The story is this:
Make it possible for monsters to lead the player to things of interest. For example, perhaps pink ghosts always move toward the WayDown. Or perhaps they move toward secret doors or special treasures. The monsters should follow the ideal path from wherever they start to the target.
Easy to say, not that easy to do. If we search for pathfinding, we find Dijkstra’s algorithm, the A* algorithm, and a few others. A* seems to be the one of choice.
I see three possible courses of action for this story.
First, I happen to have a Codea program that computes a path between two tiles on a grid, with obstacles in some of the tiles. I don’t seem to have left a comment as to what algorithm it uses. It looks to me, at first glance, to be Dijkstra. We could plug that into our dungeon program.
Second, there are Lua algorithms available on the net, implementing A*, and probably Dijkstra. We could grab one of those and plug it in.
Third, we could start from scratch and implement a new version, using TDD of course.
Of those three. I like the first one because the code is pretty clean and looks like I wrote it, and I like that about code. It only has a couple of tests. I remembered that I had written this, but I don’t remember any details of when or why, and there seem to be no articles on my site about it. Curious to think that I’d do something and not write it up, but there you are.
I don’t like the second idea because it would be unknown code, it would have to be adapted, it wouldn’t have tests in the form that I like, and I wouldn’t even know whether it was free of defects. And I don’t like adapting outside code anyway.
I like the third idea, building it from scratch, because we’re sure to learn something. But it might take longer than picking up the code that I already have. It’s not easy to say that for sure, though, because the code I have has custom-made cells and grid objects, so adapting would be tricky.
I guess the learning opportunity here is to show how I might TDD an existing algorithm. OK, we’ll do that.
Implementing A-Star in the Dungeon
Narrator (v.o.): No, he won’t.
I’ll use A-Star–which is usually spelled A*, but that requires me to remember to escape the star–because I’ve not done it before and it is probably faster than the Dijkstra algorithm. I’ll work from the Wikipedia article.
Here’s the Wikipedia code:
function reconstruct_path(cameFrom, current)
total_path := {current}
while current in cameFrom.Keys:
current := cameFrom[current]
total_path.prepend(current)
return total_path
// A* finds a path from start to goal.
// h is the heuristic function. h(n) estimates the cost to reach goal from node n.
function A_Star(start, goal, h)
// The set of discovered nodes that may need to be (re-)expanded.
// Initially, only the start node is known.
// This is usually implemented as a min-heap or priority queue rather than a hash-set.
openSet := {start}
// For node n, cameFrom[n] is the node immediately preceding it on the cheapest path from start
// to n currently known.
cameFrom := an empty map
// For node n, gScore[n] is the cost of the cheapest path from start to n currently known.
gScore := map with default value of Infinity
gScore[start] := 0
// For node n, fScore[n] := gScore[n] + h(n). fScore[n] represents our current best guess as to
// how short a path from start to finish can be if it goes through n.
fScore := map with default value of Infinity
fScore[start] := h(start)
while openSet is not empty
// This operation can occur in O(1) time if openSet is a min-heap or a priority queue
current := the node in openSet having the lowest fScore[] value
if current = goal
return reconstruct_path(cameFrom, current)
openSet.Remove(current)
for each neighbor of current
// d(current,neighbor) is the weight of the edge from current to neighbor
// tentative_gScore is the distance from start to the neighbor through current
tentative_gScore := gScore[current] + d(current, neighbor)
if tentative_gScore < gScore[neighbor]
// This path to neighbor is better than any previous one. Record it!
cameFrom[neighbor] := current
gScore[neighbor] := tentative_gScore
fScore[neighbor] := gScore[neighbor] + h(neighbor)
if neighbor not in openSet
openSet.add(neighbor)
// Open set is empty but goal was never reached
return failure
I don’t think we’ll try to build any special priority queues or the like. We don’t run this algorithm often, and iPads are blindingly fast anyway.
Narrator (v.o.): See, he’s changing direction!
After looking at the Wikipedia article a bit, I turn back to searching and find an interesting article from Red Blob Games. At first glance, the Red Blob article is interesting, because it starts with a simple breadth-first approach, then goes to Dijkstra, and then to A-Star.
This interest me for two reasons. First of all, I like an incremental approach to things, so it’s nifty when an article follows that style. Second, I’m thinking suppose we take that same incremental approach, and the simple breadth-first approach works well enough. Why not stop there? We’re not running these paths often. I’d rather warm up the iPad’s chip a bit and keep the code simpler.
The breadth-first approach works roughly like this, as I understand it right now.
Create an ever-expanding “frontier”, by stepping one step at a time from the existing frontier to cells not yet stepped on. Have each cell know which cell it came from. Repeat until the whole map has been scanned. At this point, each map cell knows where you should go if you want to get to the staring point. Since the frontier expands breadth-first, the path to every point will be as short as possible.
We could short-circuit this algorithm as soon as we find a target location. For example if we want to tell a ghost how to get to the WayDown, we expand from the WayDown until we hit the ghost’s Tile. At that point, we don’t need to expand further.
Our grid is 85x64, only 5440 cells, and many of them aren’t floor. I suspect that breadth-first will suffice.
Here’s why we consider options
When I walked in here this morning, I thought I was going to adapt or write the A-Star algorithm. That would certainly be possible, probably take a morning or two. But a bit of reading and a tiny bit of thinking, plus the hint from Red Blob that the advanced algorithms are just enhancements of breadth-first set me on a simpler path that may work.
I should rename this section “NOT Implementing A-Star…”
Breadth-First Instead
Nice, we haven’t even started and the problem is already getting simpler. How call we do this?
We could keep track of this information in the Tiles, but we may want more than one path. So let’s instead create a new small object, a Cell, to serve as our path. As I understand the algorithm at this moment, we’ll just create a Cell at the target, with a null pointer to “previous”. Then, for every legal neighbor of that cell, we’ll create a new Cell, pointing back to it, and add those to a queue of cells to search next. We’ll want not to add any cells that have already been added: the first time we encounter one is the best time.
When the queue is empty, we’re done. Every accessible cell should have a pointer in it, and any cell with no pointer can’t be reached.
Now there are a couple of ways to represent this. My first thought it with pointers between cells, but another possibility is to have a parallel table of cells, with each entry being the “previous” cell if there is one.
Now in the advanced algorithms, there’s other information in the cells, one or more estimates of distance. To me, that suggests objects, and I don’t really like structures that look like tables but represent some other thing. So cells.
Basically our algorithm maps the whole dungeon, unless we short-circuit. So let’s call our basic output a Map. A map will be a structure that mirrors the Dungeon’s Tile structure, with indexes x and y like the Dungeon class, 85x64 or whatever the dungeon happens to be.
The hard part here will be testing. We’ll have to figure out some kind of easy way to generate test grids and maps. We may wind up with some test doubles here, to allow us to work more easily than by setting up actual dungeons. We’ll want to start with some predictable input-output pairs.
Let’s just start.
Begin With a Test
-- Pathfinder
-- RJ 20210315
function testPathfinder()
CodeaUnit.detailed = false
_:describe("Pathfinder", function()
local runner
local room
_:before(function()
end)
_:after(function()
end)
_:test("Hookup", function()
_:expect(3).is(2)
end)
end)
end
Hookup test fails. Replace. But with what?
I decide to create an array of FakeMapTiles, which will stand in for the tiles upon which our Map will be based.
_:test("Initial Test Tiles", function()
local tiles = FakeMapTile:create(10,5)
_:expect(#tiles).is(10)
_:expect(#tiles[1]).is(5)
end)
That’s easily done:
FakeMapTile = class()
function FakeMapTile:create(maxX,maxY)
local tiles = {}
for x = 1,maxX do
tiles[x] = {}
for y = 1, maxY do
tiles[x][y] = FakeMapTile(x,y)
end
end
return tiles
end
function FakeMapTile:init(x,y)
self.x = x
self.y = y
end
Test runs. Now I need a Dungeon to manage these tiles for me. The real Dungeon class is too big. I’ll fake this one too.
_:test("Initial Dungeon", function()
local dungeonClass = FakeMapDungeon
local tiles = FakeMapTile:create(10,5)
local dungeon = dungeonClass(tiles)
_:expect(#dungeon.tiles).is(10)
end)
Trivial test to keep the TDD flame alive. Implementation:
FakeMapDungeon = class()
function FakeMapDungeon:init(tiles, runner, player)
self.tiles = tiles
end
Now let’s create a Map. That will drive out a Map class and a MapCell class, I expect:
_:test("Initial Map", function()
local dungeonClass = FakeMapDungeon
local tiles = FakeMapTile:create(50,50)
local dungeon = dungeonClass(tiles)
local map = Map(dungeon)
_:expect(Map:cell(1,1).previous).is(nil)
_:expect(Map:call(50,50).previous).is(nil)
end)
I’m reaching a bit further but it doesn’t seem too far. I expect we’ll take the dungeon, and init our MapCells, one for each dungeon tile, setting their previous all to nil.
Implementing … I get this far:
Map = class()
function Map:init(dungeon)
self.dungeon = dungeon
self:initCells()
end
function Map:initCells()
end
I realize at this point that I would really like some help from the dungeon here. Yes, I can rip the guts out of the dungeon and the tiles to get the information I need, but it would be better if the dungeon would do the job for me.
For now, I’ll do it with some gut-ripping. That will tell me more about what I really want from the Dungeon and Tile objects.
function Map:initCells()
local tiles = self.dungeon.tiles -- Sorry, Demeter!
self.cells = {}
for x = 1,#tiles do
self.cells[x] = {}
for y = 1, #tiles[1] do
self.cells[x][y] = MapCell(dungeon,x,y)
end
end
end
This should drive out MapCell.
3: Initial Map -- PathFinder:55: attempt to call a nil value (global 'MapCell')
And:
MapCell = class()
function MapCell:init(x,y,dungeon)
self.x = x
self.y = y
self.dungeon = dungeon
end
Now, I suspect we could grab the dungeon Tile right now rather than fetch it as needed. But I feel it’s best to leave things dynamic rather than cache them, until I’m sure what’s up. But we can be pretty sure that the dungeon isn’t going to be changing underneath this guy.
I think maybe what we should test now is generating the frontier, which means we need a starting point and a function to build the frontier.
_:test("One Frontier Step", function()
local dungeonClass = FakeMapDungeon
local tiles = FakeMapTile:create(50,50)
local dungeon = dungeonClass(tiles)
local map = Map(dungeon)
Map:start(10,10)
_:expect(Map:queue()[1]).is(Map:get(10,10))
Map:step()
_:expect(#Map:queue()).is(4)
end)
Let me explain this one a bit. Create a dungeon as usual, and a Map. Tell the map to start at 10,10. That should set the map’s queue to the MapCell at 10,10. We check that. Then we tell the Map to step. We’re going to allow only horizontal or vertical steps, so there should now be four elements in the queue.
This is a bit big, but I think we’ll do fine. I’m not sure if we’ll do a queue object or just fake it.
Test will fail on start:
Wait, my first test broke. Have I jumped ahead too far? Yes. forgot to do cell. And I’ll use it in the other test.
function Map:cell(x,y)
return self.cells[x][y]
end
Curiously, I’m getting this:
3: Initial Map -- PathFinder:73: attempt to index a nil value (field 'cells')
_:test("One Frontier Step", function()
local dungeonClass = FakeMapDungeon
local tiles = FakeMapTile:create(50,50)
local dungeon = dungeonClass(tiles)
local map = Map(dungeon)
Map:start(10,10)
_:expect(Map:queue()[1]).is(Map:cell(10,10))
Map:step()
_:expect(#Map:queue()).is(4)
end)
And we have …
Map = class()
function Map:init(dungeon)
self.dungeon = dungeon
self:initCells()
end
function Map:initCells()
local tiles = self.dungeon.tiles -- Sorry, Demeter!
self.cells = {}
for x = 1,#tiles do
self.cells[x] = {}
for y = 1, #tiles[1] do
self.cells[x][y] = MapCell(dungeon,x,y)
end
end
end
function Map:cell(x,y)
return self.cells[x][y]
end
I don’t see how this breaks … oh. Upper case Map. Refers to the class. Silly boy!
_:test("Initial Map", function()
local dungeonClass = FakeMapDungeon
local tiles = FakeMapTile:create(50,50)
local dungeon = dungeonClass(tiles)
local map = Map(dungeon)
_:expect(map:cell(1,1).previous).is(nil)
_:expect(map:cell(50,50).previous).is(nil)
end)
_:test("One Frontier Step", function()
local dungeonClass = FakeMapDungeon
local tiles = FakeMapTile:create(50,50)
local dungeon = dungeonClass(tiles)
local map = Map(dungeon)
map:start(10,10)
_:expect(map:queue()[1]).is(map:cell(10,10))
map:step()
_:expect(#map:queue()).is(4)
end)
Now I get what I expect:
4: One Frontier Step -- PathFinder:45: attempt to call a nil value (method 'start')
function Map:start(x,y)
self:addQueue(self:cell(x,y))
end
I expect the first check to pass, and to fail looking for step.
I had to change more “Map” to “map”. I think naming the class and the variable the same except for caps wasn’t wise. I’ll make this work, then see about changing it.
Well, no, there’s addQueue missing also.
function Map:addQueue(cell)
table.insert(self.queue, cell)
end
That adds at the end.
function Map:addQueue(cell)
table.insert(self.queue, cell)
end
function Map:step()
local cell = self:removeQueue()
local neighbors = cell:neighbors()
for i,n in ipairs(neighbors) do
self:addQueue(n)
end
end
function Map:removeQueue()
table.remove(self.queue, 1)
end
Now I expect to fail looking for neighbors.
4: One Frontier Step -- PathFinder:46: attempt to call a table value (method 'queue')
There I go again, naming a member variable and a function the same.
I rename the var to q.
function Map:addQueue(cell)
table.insert(self.q, cell)
end
function Map:removeQueue()
table.remove(self.q, 1)
end
function Map:queue()
return self.q
end
function Map:start(x,y)
self.q = {}
self:addQueue(self:cell(x,y))
end
Test tells me I need this:
function Map:removeQueue()
return table.remove(self.q, 1)
end
I forgot to return the value. Unlike Ruby, Lua returns nil unless you say otherwise.
Now I’m back on track:
4: One Frontier Step -- PathFinder:95: attempt to call a nil value (method 'neighbors')
Cell needs to return its neighbors. And we should consider what to do with the edges.
Oh this is interesting. What I want to do is take the neighboring cells local indices, (1,0), (0,1), (-1,0), (0,-1), and return the cells at those indices. But the Cell doesn’t know the Map, it only knows the dungeon. So we have to give it the map as well.
In doing this, I note that I have the parameters out of order during creation. A test would have discovered this had I not noticed. Anyway …
function Map:initCells()
local tiles = self.dungeon.tiles -- Sorry, Demeter!
self.cells = {}
for x = 1,#tiles do
self.cells[x] = {}
for y = 1, #tiles[1] do
self.cells[x][y] = MapCell(x,y, self, self.dungeon)
end
end
end
And now … OK, this was a lot of code to write in one go:
function MapCell:getLegalCell(x,y)
if x > 0 and y > 0 and x <= #self.map.tiles and y <= #self.map.tiles[1] then
return self.map:cell(x,y)
else
return nil
end
end
function MapCell:neighborIndices()
return { vec2(0,1), vec2(1,0), vec2(0,-1), vec2(-1,0) }
end
function MapCell:neighbors()
local near = {}
for i,nxy in ipairs(self:neighborIndices()) do
n = self:getLegalCell(self.x+nxy.x, self.y+nxy.y)
if n then
table.insert(near,n)
end
end
return near
end
function MapCell:neighborIndices()
return { vec2(0,1), vec2(1,0), vec2(0,-1), vec2(-1,0) }
end
It might work. Let’s see.
4: One Frontier Step -- PathFinder:111: attempt to get length of a nil value (field 'tiles')
Right. It’s not tiles.
function MapCell:getLegalCell(x,y)
if x > 0 and y > 0 and x <= #self.map.cells and y <= #self.map.cells[1] then
return self.map:cell(x,y)
else
return nil
end
end
We should be asking the map this question anyway, and in due time, it’ll ask the dungeon.
Test runs, though. Good time to change that check for legal:
function MapCell:getLegalCell(x,y)
return self.map:getLegalCell(x,y)
end
function Map:getLegalCell(x,y)
if x < 1 or y < 1 or x > #self.cells or y > #self.cells[1] then
return nil
else
return self:cell(x,y)
end
end
I expect this to continue to work.
It does. Now let’s refine the test:
_:test("One Frontier Step", function()
local dungeonClass = FakeMapDungeon
local tiles = FakeMapTile:create(50,50)
local dungeon = dungeonClass(tiles)
local map = Map(dungeon)
map:start(10,10)
_:expect(map:queue()[1]).is(map:cell(10,10))
map:step()
_:expect(#map:queue()).is(4)
local queue = map:queue()
_:expect(queue).has(map:cell(9,10))
_:expect(queue).has(map:cell(10,9))
_:expect(queue).has(map:cell(11,10))
_:expect(queue).has(map:cell(10,11))
end)
I expect this to run also. It does. Now, we need to set up our cells to point back to each other, and, I think, to include a distance figure, which will increase with each step. (This will be a Manhattan distance, by the way.)
I’ll just extend this last test a bit more:
_:test("One Frontier Step", function()
local dungeonClass = FakeMapDungeon
local tiles = FakeMapTile:create(50,50)
local dungeon = dungeonClass(tiles)
local map = Map(dungeon)
map:start(10,10)
_:expect(map:queue()[1]).is(map:cell(10,10))
map:step()
_:expect(#map:queue()).is(4)
local queue = map:queue()
_:expect(queue).has(map:cell(9,10))
_:expect(queue).has(map:cell(10,9))
_:expect(queue).has(map:cell(11,10))
_:expect(queue).has(map:cell(10,11))
_:expect(map:cell(9,10).parent).is(map:cell(10,10))
_:expect(map:cell(10,11).distance).is(1)
end)
Neither of those last two expects will run.
function Map:start(x,y)
self.q = {}
local c = self:cell(x,y)
c.distance = 0
c.parent = nil
self:addQueue(c)
end
This will probably get pushed into MapCell …
function Map:step()
local cell = self:removeQueue()
local neighbors = cell:neighbors()
for i,n in ipairs(neighbors) do
self:addQueue(n, cell)
end
end
The add will need to know the previous cell.
function Map:addQueue(cell, parent)
if parent then
cell.parent = parent
cell.distance = 1 + parent.distance
end
table.insert(self.q, cell)
end
Tests run.
I think that last function should defer to cell:
function Map:addQueue(cell, parent)
cell:setParent(parent)
table.insert(self.q, cell)
end
And:
function MapCell:setParent(parent)
self.parent = parent
if parent then
self.distance = 1 + parent.distance
end
end
Tests run. Oddly, when I wrote this;
self.distance = 1 + ((parent and parent.distance) or 0)
The test failed, with 2 rather than 1. I don’t see why, telling me that a) I’m getting tired, and b) that code is too clever to live.
I think I’m ready to run the whole algorithm on my test map and check some distances.
I think I’ll do a new test for this, but with the same setup.
_:test("Full Loop", function()
local dungeonClass = FakeMapDungeon
local tiles = FakeMapTile:create(50,50)
local dungeon = dungeonClass(tiles)
local map = Map(dungeon)
map:start(10,10)
map:run()
_:expect(map:cell(8,10).distance).is(2)
end)
Run should, if I’m not mistaken, just step until the queue is empty,
function Map:run()
while #self.q > 0 do
self:step()
end
end
Could it be this easy? Surely not.
No. It loops forever. This does not please me. But why is it failing? Ah, because we redo cells that are done.
We should only do cells who have no distance already set. Which tells me I probably need to set the start cell’s distance to 0.
function Map:getLegalCell(x,y)
if x < 1 or y < 1 or x > #self.cells or y > #self.cells[1] then
return nil
else
return self:cell(x,y)
end
end
This needs to be changed to return nil if the cell is already set up. I’d really prefer to make the cells as visited or done, rather than fiddle with their distance to determine whether they’ve been used. Costs me a member variable but I don’t mind.
function MapCell:init(x,y,map,dungeon)
self.x = x
self.y = y
self.map = map
self.dungeon = dungeon
self.visited = false
end
function Map:getLegalCell(x,y)
if x < 1 or y < 1 or x > #self.cells or y > #self.cells[1] then
return nil
else
local cell = self:cell(x,y)
if cell.visited then return nil else return cell end
end
end
function Map:step()
local cell = self:removeQueue()
cell.visited = true
local neighbors = cell:neighbors()
for i,n in ipairs(neighbors) do
self:addQueue(n, cell)
end
end
If anything it’s working worse now. Doesn’t return, can’t exit the program. I really wish I had committed a while back.
I’ll ignore the last test.
OK, everything else works. All I can think of is that I must be revisiting cells. I suspect I need a break. Let’s at least review the code first.
function Map:step()
local cell = self:removeQueue()
cell.visited = true
local neighbors = cell:neighbors()
for i,n in ipairs(neighbors) do
self:addQueue(n, cell)
end
end
Ah. One thing that happens here is that we could find a neighbor twice. Imagine the first step, which finds (9,10) and (10,9) each of those will find (9,9) as a neighbor. As it stands, they’ll each add it, because it’s not visited. So we have to mark visited when we add to the queue, not when we remove.
function MapCell:setParent(parent)
self.parent = parent
self.visited = true
if parent then
self.distance = 1 + parent.distance
end
end
function Map:addQueue(cell, parent)
cell:setParent(parent)
table.insert(self.q, cell)
end
function Map:step()
local cell = self:removeQueue()
local neighbors = cell:neighbors()
for i,n in ipairs(neighbors) do
if not cell.visited then
self:addQueue(n, cell)
end
end
end
This looks right to me, but my head is spinning a bit.
Well, the first test returns 0, not 4. So my step isn’t right. I’m going to back out all the visited stuff.
OK, first test runs, second ignored. Commit: PathFinder in progress. Tests run, not installed.
OK, now I have a safe revert point.
Let’s try a safer test, just a few calls to step, checking queue size.
I’ll probably have to draw a picture to see what should happen.
_:test("A few steps", function()
local dungeonClass = FakeMapDungeon
local tiles = FakeMapTile:create(50,50)
local dungeon = dungeonClass(tiles)
local map = Map(dungeon)
map:start(10,10)
map:step()
_:expect(#map:queue()).is(4)
map:step()
_:expect(#map:queue()).is(6)
end)
I did draw a picture.
5: A few steps -- Actual: 7, Expected: 6
Something didn’t get removed, or something was added twice. I’ll dump the queue to find out, I guess.
5: A few steps -- Actual: 7, Expected: 6
1 11 10
2 10 9
3 9 10
4 10 12
5 11 11
6 10 10
7 9 11
The original cell, 10,10 shouldn’t be there. We started with it, so it has been visited. Since we always call addQueue, I can check and set visited there.
function Map:addQueue(cell, parent)
if cell.visited then return end
cell.visited = true
cell:setParent(parent)
table.insert(self.q, cell)
end
The test runs now. The dump looks good. I’m going to unignore the run and see what happens now.
The test runs correctly so far.
_:test("Full Loop", function()
local dungeonClass = FakeMapDungeon
local tiles = FakeMapTile:create(50,50)
local dungeon = dungeonClass(tiles)
local map = Map(dungeon)
map:start(10,10)
map:run()
_:expect(map:cell(8,10).distance).is(2)
end)
So that’s good news. Let’s check some more values:
_:expect(map:cell(50,50).distance).is(80)
Correct.
_:expect(map:cell(1,1).distance).is(18)
That’s also correct.
I reckon they all are. Shall we check them all?
_:test("Full Loop", function()
local dungeonClass = FakeMapDungeon
local tiles = FakeMapTile:create(50,50)
local dungeon = dungeonClass(tiles)
local map = Map(dungeon)
map:start(10,10)
map:run()
_:expect(map:cell(8,10).distance).is(2)
_:expect(map:cell(50,50).distance).is(80)
_:expect(map:cell(1,1).distance).is(18)
for x = 1,50 do
for y = 1,50 do
local d = map:cell(x,y).distance
local e = math.abs(x-10) + math.abs(y-10)
_:expect(d).is(e)
end
end
end)
We’re getting the distances all right. There are no obstacles yet. It’s 1 PM, and lunch will be here shortly. Let’s break.
In fact, let’s wrap up: I have scanning to do this afternoon, won’t have time to code.
Summary
Well, this has been interesting. I started thinking I’d probably do an A-Star algorithm, and that it’d likely take me a couple of sessions. I decided to start with breadth-first, and it’s going to take a couple of sessions, but the bulk of it is done. We’ll need to teach our cells to recognize obstacles, and we’ll have to devise a test, which may or may not be a pain.
I think the code is decent, with a bit of feature envy left in it. We’ll look at that next time.
And I did get off track there for a bit, but realized it (finally) and reverted to a good point. I then wrote a simpler test. I had bitten off the whole thing and told the search to run, but had not correctly handled skipping already done nodes. The result was to add all the nodes forever, or thereabouts.
The visitation implementation the second time was much simpler and more obviously correct. And actually correct.
So far so good!
We’ll leap on this again tomorrow!