More pathfinding, that’s the plan. Testing is likely to be harder than doing.

Before I start, I want to shout out again to Amit Patel’s Red Blob Games, whose article inspired this implementation. I was browsing the site last night and it is amazingly clear and detailed, with references and great examples.

It’s Tuesday, 0925. Late start this morning. If I recall out situation yesterday, we have the breadth-first path-finding computing the correct distance for each cell–though I have some doubts–and the cells should contain the path pointers from the target back to the starting point. (Of course, we can just as well start at our real goal and find a path back to ourselves, in which case the pointers will tell us where to go. Not in the metaphorical sense.)

I do have a small concern. I’m not totally certain that this scheme will find a shortest path. The more advanced approaches, Dijkstra and A-Star, both guarantee a shortest path, and they are more efficient by virtue of checking more likely paths sooner. We’ll see what happens. Frankly, if our path followers were to wander a bit, we might find that to be more natural anyway.

Concerns aside, we still have work to do, including:

  • Build and test the ability to find a path around obstacles. Honestly, given that we just wrote the thing, I am certain that if a path exists, the current code will find it, but we don’t check for obstacles yet, and we need to. Why? Because we want our paths to stay on Room tiles. Walking through the walls just isn’t on.
  • Create the final path in a form we can use in the rest of our code, to guide a monster or whatever. Test that.
  • Plug the code into a monster and see where it goes.

There’s probably more work that we’ll discover, but that will do for now. Let’s begin with obstacles.

Obstacles

Our present objects do consider whether a given cell can be in the path.

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)
        return cell
    end
end

function Map:cell(x,y)
    return self.cells[x][y]
end

We should probably push at least some of that if logic down into the MapCell class or at least ask the cell if it is accessible. Note that returning a nil causes the program not to try to travel on that cell.

Remember that outside the test realm, our pathfinder will be plugged into a real Dungeon class, and that class will know the real tiles, and can determine for us whether entities can enter that cell. We should be careful, in doing this, to emulate the entity rule. If the desired path called for a monster to step over a Spikes, where it’s generally not allowed … well, we could just let it happen, but we need to be aware of what we’re doing.

For now, let’s give the MapCell a member flag accessible that tells us whether we can use the cell in our path. We’ll set that flag directly in our tests, and indirectly as well, as needed.

I should mention …

My thinking isn’t entirely clear here, regarding just what we’ll need down the road. This is common. “Prediction is difficult, especially when it involves the future.” We may make notes about concerns, or we may just suppose that if the issue comes up we’ll see it, but either way, our practice is to do what we know, fully expecting that we’ll need to add to the code, or change it, as time and learning proceed,

For now, a flag, and a test with obstacles.

function MapCell:init(x,y,map,dungeon)
    self.x = x
    self.y = y
    self.map = map
    self.dungeon = dungeon
    self.visited = false
    self.accessible = true
end

function MapCell:setInaccessible()
    self.accessible = false
end

Do I have a test for that? No, not yet. It’s an accessor. I don’t TDD those, and you’re not the boss of me. However, I am about to test it:

        _:test("Obstacle", function()
            local dungeonClass = FakeMapDungeon
            local tiles = FakeMapTile:create(10,10)
            local dungeon = dungeonClass(tiles)
            local map = Map(dungeon)
            for y = 1,9 do
                map:cell(5,y):setInaccessible()
            end
            map:start(1,1)
            map:run()
            local md = manhattan(vec2(1,1),vec2(5,10)) + manhattan(vec2(5,10),vec2(10,1))
            _:expect(map:cell(10,1).distance).is(md)
        end)

I think that should draw a “wall” vertically from 5,1 to 5,9, causing the distance between 1,1 and 10,1 to increase. I expect this test to fail with a 9 as the incorrect answer, because we’re not using the flag yet.

7: Obstacle  -- Actual: 9, Expected: 27.0

Let’s improve the readability a bit here.

        _:test("Obstacle", function()
            local dungeonClass = FakeMapDungeon
            local tiles = FakeMapTile:create(10,10)
            local dungeon = dungeonClass(tiles)
            local map = Map(dungeon)
            for y = 1,9 do
                map:cell(5,y):setInaccessible()
            end
            local start = vec2(1,1)
            local mid = vec2(5,10)
            local stop = vec2(10,1)
            map:start(1,1)
            map:run()
            local md = manhattan(start,mid) + manhattan(mid,stop)
            _:expect(map:cell(stop.x,stop.y).distance).is(md)
        end)

Same result, of course. But now:

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.accessible then
            return cell
        else
            return nil
        end
    end
end

Invasive, we’ll fix that, but does it work? In fact it does. By the way, I should mention that I actually counted the squares on graph paper, though I used the manhattan function in the test. The test was tricky enough to write that I wanted to double-check it. I think it’s better that way, and surely would be a better way to do more tests if we needed more.

I think we don’t need more about obstacles, but I am interested in the path back. What is somewhat interesting about the path is that there are many possible paths of that length. You could go up the side, across the top, down the other side. You could go over to the wall, up the wall, across the top, down the other side of the wall, and over to the corner. They’ll all have the same manhattan distance.

How can we check our back path? Well, it should have 28 elements, and each element should have a manhattan distance of one from the preceding one. The first one should be at 1,10 and the last at 1,1.

What we need is a test:

            local path = map:cell(stop.x,stop.y):path()
            _:expect(#path).is(28)

This drives out path:

7: Obstacle -- PathFinder:107: attempt to call a nil value (method 'path')

And …

function MapCell:path()
    local c = self
    local path = { c }
    repeat
        c = c.parent
        table.insert(path,c)
    until c.parent == nil
    return path
end

We start with our own cell, and keep adding until we’ve added the one with no parent. Test runs.

Extend the test:

            _:expect(#path).is(28)
            local prev
            for i,c in ipairs(path) do
                if i > 1 then
                    _:expect(c:manhattan(prev)).is(1)
                    prev = c
                end
            end

We don’t have manhattan, but that’s a moment’s work:

function MapCell:manhattan(cell)
    return manhattan(self:posVec(),cell:posVec())
end

function MapCell:posVec()
    return vec2(self.x,self.y)
end

I’m expecting this to work. My expectation is not met:

7: Obstacle -- PathFinder:210: attempt to index a nil value (local 'cell')

Looks like I didn’t pass in a cell. And I didn’t:

            _:expect(#path).is(28)
            local prev = path[1]
            for i,c in ipairs(path) do
                if i > 1 then
                    _:expect(c:manhattan(prev)).is(1)
                    prev = c
                end
            end

Test runs. I still don’t know what the path is, but I know it has the right number of steps and each step has manhattan distance of one. Good enough. Except that I’m going to look.

It chose the vertical, horizontal, vertical route, up the side, over the top, down the other side. Works for me.

Now I think we have a working pathfinder. It may not be optimal, but the tests tell us that it is correct.

Now let’s commit: Map can avoid obstacles and return path.

But we do need to enhance our accessibility a bit, both to avoid Demeter violations, and to refer to the actual dungeon for information.

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:isAccessible() then
            return cell
        else
            return nil
        end
    end
end

function MapCell:isAccessible()
    return self.accessible and self.dungeon:cellIsAccessible(self:posVec())
end

Our FakeDungeon will say yes, and our real one will answer as you’ll see in a moment.

function FakeMapDungeon:cellIsAccessible(pos)
    return true
end

Interestingly, this is our first use of the dungeon other than in our rather odd way of generating our cells. That’s fine, it tells us that we only need to add this one method to Dungeon:

function Dungeon:cellIsAccessible(position)
    return self:getTile(position):isRoom()
end

That should work for us. I’d like to plug it in. How can we do this?

Plugging It In

Let’s do this. If you press the Flee button, we’ll calculate a path to the WayDown, and we’ll mark all the relevant tiles somehow. Rose petals or something. Some hack, just to see it work (or fail).

We don’t presently remember where the WayDown is:

function GameRunner:placeWayDown()
    local r1 = self.rooms[1]
    local target = r1:centerTile()
    local tile = self:getDungeon():farawayOpenRoomTile(target)
    WayDown(tile,self)
end

But we can:

function GameRunner:placeWayDown()
    local r1 = self.rooms[1]
    local target = r1:centerTile()
    local tile = self:getDungeon():farawayOpenRoomTile(target)
    self.wayDown = WayDown(tile,self)
end

Oh, wait, I’d better commit my isAccessible stuff. Commit: Dungeon knows if cell is accessible.

Now we have an empty function for fleeing …

function Player:flee()
    
end

Let’s build a path here. The following grotesque hackery is why we just committed:

function Player:flee()
    local map = Map(self.dungeon)
    local me = self:getTile():pos()
    local wd = self.dungeon.wayDown.tile:pos()
    map:start(wd.x,wd.y)
    map:run()
    local path = map:cell(me.x,me.y):path()
    for i,c in ipairs(path) do
        self:markTile(c)
    end
end

This might be right. Now how to mark a tile given a cell?

I’m tempted to lay down healths.

function Player:markTile(mapCell)
    local pos = mapCell:posVec()
    local tile = self.dungeon:getTile(pos)
    tile:addContents(Loot(tile, "Health", 1,1))
end

This seems certain to explode in some horrendous way. It’s clearly a hacked attempt to jam this in. And that’s my intention: I just want to see what happens.

First error:

PathFinder:130: attempt to index a nil value (field 'dungeon')
stack traceback:
	PathFinder:130: in method 'initCells'
	PathFinder:125: in field 'init'
	... false
    end

That’s odd, I was sure I passed in my dungeon. Except, of course, the Player doesn’t have one.

function Player:flee()
    local dungeon = self.runner:getDungeon()
    local map = Map(dungeon)
    local me = self:getTile():pos()
    local wd = self.runner.wayDown.tile:pos()
    map:start(wd.x,wd.y)
    map:run()
    local path = map:cell(me.x,me.y):path()
    for i,c in ipairs(path) do
        self:markTile(c)
    end
end

I also asked runner for the wayDown. Dungeon doesn’t know it. And I think the other method needs improvement similarly:

function Player:markTile(mapCell)
    local pos = mapCell:posVec()
    local dung = self.runner:getDungeon()
    local tile = dung:getTile(pos)
    tile:addContents(Loot(tile, "Health", 1,1))
end

That looks OK, try again.

Player:149: attempt to call a nil value (method 'addContents')
stack traceback:
	Player:149: in method 'markTile'
	Player:141: in field '?'
	Button:58: in method 'performCommand'
	Button:53: in method 'touched'
	GameRunner:368: in method 'touched'
	Main:39: in function 'touched'

That tells me we didn’t get a tile for our Loot. Why not? I’ll resort to some prints, and shortly I’ll give up this trick and get back to sensible behavior. I hope.

Ah, I think we have to do addDeferredContents. There’s no direct add.

hearts in a row

Check that out! I’ll follow the hearts.

hearts lead to WayDown

And check that out!! The hearts lead right to the WayDown, through a few rooms.

This is an outstanding result! Once I wired it up correctly, it worked in situ the very first time. This is why we do TDD. As for speed, the hearts appear instantly. We’ve scanned the whole dungeon starting from the WayDown. There’s not even an early break for finding the princess along the way.

We could, in principle, cache a map like this, and maps to anything else of interest. We could create them on the fly or at the beginning of the game. It just won’t matter: the code is fast enough.

I’m going to commit this as is, and wrap up. Commit: pressing flee draws a path to the WayDown in Health Loots.

Let’s sum up.

Summary

Yesterday’s tests took all the weight. At the end of yesterday, we had a map of cells, each one pointing down the path from that cell to the “start” location. (This makes me want to call start something more like target.)

Today we made quick work of putting in accessibility, and that will be readily extended if we need to. And it was easy to pull out a path and check it for legitimacy.

The current use, in Player, is of course a horrible hack, but it gives us some learning. To make it work, I needed to reach down inside a number of objects to get the necessary info. That tells us that we need some supporting methods so that we don’t have to be so aware of coordinates and such.

We can sort that out when we implement something sensible using the new capability. For now, we have a fun new feature, and a very simple and effective implementation of path finding.

Don’t forget to admire Amit Patel’s Red Blob Games, which has great articles including the one that inspired our current implementation of pathfinding.

See you next time!

D2.zip