Dungeon 297

More work on the new event-driven scheme. I hope to get to an interesting problem today.

The “interesting problem” that I have in mind is managing entry to a “tile”. There is no “tile”. Things will have Coordinates and they will “move” by changing their Coordinates, all the while not really knowing what Coordinates actually are. In general, two Things cannot have the same Coordinates, though there are exceptions, such as Loot in a Chest. Live, moving things, in particular, can’t have the same Coordinates. When they try, that is an invitation to combat.

The problem is interesting because of the publish-subscribe style I’m experimenting with here. In the D2 program, too many objects know each other, and it is making things more complicated than I’d like. Entities know the GameRunner, which knows them, and so on. The biggest impact of the D2 complexity is in setting up a test, since Entities need Tiles and Tiles need a Map and Entities generally need a GameRunner, which needs a Dungeon to contain the Map … and so on.

It would surely be possible to rig up a standard testing Dungeon, and perhaps I “should” do that. But I’ve been wondering what I would do if I could start over, so I’m experimenting to find out. This is one of the advantages to doing all this as a sort of hobby … I’m not on the hook to deliver product, only to do things that interest me enough to write an article, ideally one that will help all six of my readers.

But I digress. The publish-subscribe scheme has a queue of messages to be published, and by design, all Things are auto-subscribed to all messages. When one Thing publishes a message, all the Things receive that message. In principle, those Things could respond by publishing a message of their own. If they do, the message is placed in a queue, and after publication of the first message is complete, the next message in the queue is published.

This means that when X sends a message via Q:publish(), that call does not return until the queue is empty. The problem arises when we publish a message asking MonsterThings where they would like to move, assuming that they reply by publishing “I want to move to XY”.

Suppose that MonsterThing A chooses to move to XY, and there is already some Thing in XY that doesn’t allow such a move. We can see that when A publishes “A move to XY”, the Thing already there compares XY to its own Coordinate and wants to deny the move. I’m not sure just how it denies the move but one way or another, someone knows that the move is not OK, and surely we’ll find a good way to deal with that.

But now let’s suppose that MonsterThing A chooses XY and MonsterThing B also chooses XY. and that right now, XY is available. And suppose that all the Monsters are responding to a publication of “MonstersMoveNow”. So A and B will both say they want XY. When it comes time to resolve A’s request, there’s nothing on XY, so no one demurs. Then we get around to B asking, and there is still no one on XY, because A will not get a return and won’t move until it does.

Hell. If you understand the above, you’re smarter than I am. Suffice to say that untangling a conversation via the Q is hard to think about, and therefore it’ll be hard to get right and almost certainly hard to test. Even our current very simple tests are getting interesting, though they are still manageable. See yesterday’s article for those tests.

So, today, I want to work on movement, and if possible, to get to two incompatible Things trying to move to the same Coordinates.

Coordinates

Coordinates are opaque to Things. They have a Coordinates instance, but they don’t know what it means. We’ll push that idea as far as it will go. So for now, I think all we need is for coordinates to be simple numbers. We’ll deal with coordinates that can be drawn in due time.

Since this is just an experiment, I’ve been doing all the tests in a tab called Scenarios, but it seems to have become the tab for the Queue class. So let’s make a new tab for Movement. We’ll sort all this into real classes if and when we must. So far, I’ve kept everything local, though we’ll have to export a Queue shortly.

New tab and tests:

--Movement
-- RJ 20220503

function testMovement()
    
    _:describe("Movement", function()
        
        _:before(function()
        end)
        
        _:after(function()
        end)
        
        _:test("HOOKUP", function()
            _:expect("Foo", "testing fooness").is("Bar")
        end)
        
    end)
end

The hookup should fail. It does. Whee!

We’ll need a Q to talk to. I’ll add a local Q and init it, in before:

        _:before(function()
            Q = GetQueue()
        end)

I’ve just made a design decision that we’ll have a global function GetQueue() to return a fresh Queue. And I’ve decided, no surprise, that globals start with upper case letters. This test will fail looking for GetQueue.

Movement:11: attempt to call a nil value (global 'GetQueue')
stack traceback:
	Movement:11: in field '_before'
	CodeaUnit:44: in method 'test'
	Movement:17: in local 'allTests'
	CodeaUnit:16: in method 'describe'
	Movement:8: in function 'testMovement'
	[string "testMovement()"]:1: in main chunk
	CodeaUnit:139: in field 'execute'
	Main:7: in function 'setup'

Because the failure is in the before, CodeaUnit crashes. We are not surprised at this. We go over to Scenarios and implement this:

function GetQueue()
    return Queue()
end

Now we should get our failing hookup again. And we do.

Now for a real test. This is more difficult than it might be, because we’re beginning to implement the real protocol for doing things. But this is just an experiment, and we can be a bit casual about it, I suppose.

I’ll implement some small classes to hold my ideas, keeping them local to this tab for now.

        _:test("Player Moves", function()
            local c1 = Coordinates(10,10)
            local c2 = Coordinates(11,10)
            local player = Player()
            Q:suscribe(player)
            player:moveTo(c1)
            Q:publish("playerMoveTo", c2)
            _:expect(player:where()).is(c2)
        end)

This seems like a fairly solid sketch of how it might work. The moveTo method and where method are tentative setter and getter. This will fail wanting Coordinates.

1: Player Moves -- Movement:18: attempt to call a nil value (global 'Coordinates')

We code:

local Coordinates = class()

function Coordinates:init(x,y)
    self._x = x
    self._y = y
end

I think that should get me down to Player:

1: Player Moves -- Movement:27: attempt to call a nil value (global 'Player')

And …

local Player = class()

function Player:moveTo(coord)
    self._coord = coord
end

function Player:where()
    return self._coord
end

I implemented more than my test demanded. Sorry about that. I think we probably get the unimplemented message error now.

Well, not with that spelling you don’t:

1: Player Moves -- Movement:38: attempt to call a nil value (method 'suscribe')

        _:test("Player Moves", function()
            local c1 = Coordinates(10,10)
            local c2 = Coordinates(11,10)
            local player = Player()
            Q:subscribe(player)
            player:moveTo(c1)
            Q:publish("playerMoveTo", c2)
            _:expect(player:where()).is(c2)
        end)

Now we get the error I anticipated:

1: Player Moves -- Scenarios:50: Receiver does not support method 'playerMoveTo'.

And we implement:

function Player:playerMoveTo(_)
end

The player ignores this message. But I think it isn’t a good name. Let’s rename:

        _:test("Player Moves", function()
            local c1 = Coordinates(10,10)
            local c2 = Coordinates(11,10)
            local player = Player()
            Q:subscribe(player)
            player:moveTo(c1)
            Q:publish("playerRequestMoveTo", c2)
            _:expect(player:where()).is(c2)
        end)

The test will now fail on the expectation, which will be unclear:

1: Player Moves  -- Actual: table: 0x2866910c0, Expected: table: 0x286692500

Let’s provide a print and equality check for Coordinates.

function Coordinates:__eq(aCoord)
    return self._x == aCoord._x and self._y == aCoord._y
end

function Coordinates:__tostring()
    return "("..self._x..","..self._y..")"
end

I also added a check to the test, mostly to test my __eq:

        _:test("Player Moves", function()
            local c1 = Coordinates(10,10)
            local c2 = Coordinates(11,10)
            local player = Player()
            Q:subscribe(player)
            player:moveTo(c1)
            _:expect(player:where()).is(c1)
            Q:publish("playerRequestMoveTo", c2)
            _:expect(player:where()).is(c2)
        end)

The failure is not]w more clear:

1: Player Moves  -- Actual: (10,10), Expected: (11,10)

Let’s think a moment about this. Maybe two moments. Maybe even more.

I think I’d rather that we were working with a Monster here, because they move on their own, and I don’t want to mix external control into the problem. So rename Player to Monster in this tab. Consider it done, you’ll see the code soon enough.

Here’s the test, which needs to change:

        _:test("Monster Moves", function()
            local c1 = Coordinates(10,10)
            local c2 = Coordinates(11,10)
            local monster = Monster()
            Q:subscribe(monster)
            monster:moveTo(c1)
            _:expect(monster:where()).is(c1)
            Q:publish("playerRequestMoveTo", c2)
            _:expect(monster:where()).is(c2)
        end)

The test is doing the publication. We want Monsters to make their own decisions, and let’s assume they’ll get a message “update”. So …

        _:test("Monster Moves", function()
            local c1 = Coordinates(10,10)
            local c2 = Coordinates(11,10)
            local monster = Monster()
            Q:subscribe(monster)
            monster:moveTo(c1)
            _:expect(monster:where()).is(c1)
            Q:publish("update")
            _:expect(monster:where()).is(c2)
        end)

This will fail for want of update.

1: Monster Moves -- Scenarios:50: Receiver does not support method 'update'.

Upon update, the Monster will make its move request. I decide on this code:

function Monster:update()
    local newCoords = Coordinates(11,10)
    Q:publish("requestMoveTo",self,newCoords)
    self:moveTo(newCoords)
end

We’ll find that we don’t know that method, so implement:

function Monster:requestMoveTo(_)
end

The test will run, I think. And it does. Let’s commit: Initial Movement Test.

The test works, of course, because no one pays attention to the request, and the Monster unilaterally moves anyway.

Let’s create a new test with an Obstacle.

        _:test("Monster Obstructed", function()
            local c1 = Coordinates(10,10)
            local c2 = Coordinates(11,10)
            local monster = Monster()
            Q:subscribe(monster)
            local obstacle = Obstacle()
            Q:subscribe(obstacle)
            obstacle:moveTo(c2)
            monster:moveTo(c1)
            _:expect(monster:where()).is(c1)
            Q:publish("update")
            _:expect(monster:where()).is(c1)
        end)

The obstacle is on c2, so we want it to refuse the move, therefore the monster should wind up still at c1. We need the obstacle class:

2: Monster Obstructed -- Movement:67: attempt to call a nil value (global 'Obstacle')

I give it this much:

local Obstacle = class()

function Obstacle:moveTo(coord)
    self._coord = coord
end

Then test to drive out the rest.

2: Monster Obstructed -- Scenarios:50: Receiver does not support method 'update'.

We’re going to wish that that message were more informative, but for now we know what we need:

function Obstacle:update()
end

The Obstacle ain’t goin nowhere. Test.

2: Monster Obstructed -- Scenarios:50: Receiver does not support method 'requestMoveTo'.

Ah, the rubber approaches the road. Here’s where we have to try to stop the move.

function Obstacle:requestMoveTo(sender,coord)
    if coord == self._coord then
        error("I don't know how to stop him!?!?")
    end
end

Test.

2: Monster Obstructed -- Movement:48: I don't know how to stop him!?!?

OK. Now remove the error line and we have a failing test:

2: Monster Obstructed  -- Actual: (11,10), Expected: (10,10)

Now we face the first interesting question of the morning: How are we going to stop the Monster from completing its move?

As things stand, published message methods do not expect a return value, so we can’t just return false or “I object!”: there’s nowhere for it to be returned to. In addition, because of the way Q works, we have no way to return a value to the original caller, plus the way the queue unwinds is too confusing for words, at least for my words.

But … in this message, we have the object who sent the request. Let’s invent a protocol. When a published message is a “request”, the convention is that we’ll pass the sender, the request information (in this case the coordinate), and methods to accept or decline the test.

For now, we’ll just do decline, as I have no need for acceptance here.

function Obstacle:requestMoveTo(sender,coord, decline)
    if coord == self._coord then
        decline(sender)
    end
end

The code there amounts to a method call on sender, whatever method is in the decline function. We update Monster:

function Monster:update()
    local newCoords = Coordinates(11,10)
    Q:publish("requestMoveTo",self,newCoords, self.refuseMove)
    self:moveTo(newCoords)
end

This will fail calling a nil, because there is no refuseMove.

2: Monster Obstructed -- Movement:48: attempt to call a nil value (local 'decline')

Super. Now we build that method:

function Monster:refuseMove()
    -- not implemented
end

Now I think the test completes, but still fails.

2: Monster Obstructed  -- Actual: (11,10), Expected: (10,10)

Perfect. Now we modify Monster …

function Monster:update()
    self._proposed = Coordinates(11,10)
    Q:publish("requestMoveTo",self,newCoords, self.refuseMove)
    self:moveTo(self._proposed)
end

So we cache the thing we plan to move to, and then, if refused:

function Monster:refuseMove()
    self._proposed = self._coord
end

We set the proposed move to be our original coordinates. Now the test should run. I am mistaken: it does not.

2: Monster Obstructed  -- Actual: (11,10), Expected: (10,10)

I don’t see what went wrong. Did we refuse the move? I’ll add a print.

function Monster:refuseMove()
    print("refused")
    self._proposed = self._coord
end

Unsurprisingly we didn’t get there. But why not? What’s in Obstacle?

function Obstacle:requestMoveTo(sender,coord, decline)
    if coord == self._coord then
        decline(sender)
    end
end

OK, add a print to be sure we declined …

We did not. Print the input coords?

Oh. Standard editing error:

function Monster:update()
    self._proposed = Coordinates(11,10)
    Q:publish("requestMoveTo",self,newCoords, self.refuseMove)
    self:moveTo(self._proposed)
end

Should have been:

function Monster:update()
    self._proposed = Coordinates(11,10)
    Q:publish("requestMoveTo",self, self._proposed, self.refuseMove)
    self:moveTo(self._proposed)
end

Still no go.

After some egregious prints to find out what is going on, I discover that the Q:publish of “requestMoveTo” has returned before the call to obstacle. I was certain that the way that Q worked was to call all the receivers before returning to the sender. That’s clearly not the case.

Apparently I do not understand what I implemented in Queue.

function Queue:publish(methodName,...)
    local event = Event(methodName, ...)
    self:enqueue(event)
    self:dequeue()
end

function Queue:enqueue(event)
    table.insert(self.events, event)
end

function Queue:dequeue()
    if self.publishing then return end
    self.publishing = true
    while #self.events > 0 do
        local event = table.remove(self.events,1)
        local methodName = event:methodName()
        local args = event:args()
        for i,thing in ipairs(self.things) do
            local method = thing[methodName]
            assert(method, "Receiver does not support method '"..methodName.."'.")
            method(thing, table.unpack(args))
        end
    end
    self.publishing = false
end

Sheesh. I don’t see how that can happen. Oh. Yes.

We’re dispatching update. Then Monster enqueues requestMoveTo, which gets enqueued … and the call to dequeue immediately returns, so we return immediately to Monster, so it is too late when the refusal arrives.

I could change the refusal to do a revert, which would jam the old value back. Let’s try that.

function Monster:update()
    self._previous = self._coord
    self:moveTo(Coordinates(11,10))
    Q:publish("requestMoveTo",self, self._coord, self.refuseMove)
end

function Monster:refuseMove()
    self:moveTo(self._previous)
end

This may well work. In fact it does. Commit: Obstacle can revert Monster move.

Time to reflect a bit.

Reflection

I’ve definitely proven that thinking about timing with this event-driven design is difficult, since obviously I can’t do it very well. The scheme is sort of simulating what would happen if all the Things had their own threads. We’d never be sure who was running when, and there would be issues in timing. Even here, we really encountered a timing issue, which was that a Monster Thing’s method ran to completion, even though it contained a publish. Sometimes publish blocks, and sometimes it doesn’t. I think the rule is that the first publish blocks until all the subsequent events are finished, but the subsequent ones do not block and any code following the publish will be executed immediately.

We’d be wise not to take advantage of these facts, and should, I imagine, always assume that the code after a publish will run immediately.

That will lead us to policies like what we just did, which was to reverse the Monster’s action rather than decline it.

At a larger scale, I think we’re beginning to see the dark side of this event-driven idea. It does offer much less object interconnection than our current D2 design, but it may make some operations harder to understand, to test, and possibly to implement. We might find ourselves needing a lot of “undo” kinds of operations.

It’s too soon to say, and if we just don’t think much about how the Q is going to unwind, and deal with what the objects are doing, we can see that things are pretty simple at that level. In the current Monster / Obstacle example:

A monster chooses a move and makes it;
The monster then announces its move;
Interested parties hear about the move;
Any of them can require the Monster to revert the move;
The monster winds up where we think it should.

What’s hard to answer is what the state of the system is between when the monster moves and when the first hearer objects. Will some other objects make decisions based on the new, soon-to-be-reverted coordinates?

We’d have this problem in a multi-threaded system, and it would be even harder to decide. Here, the system is deterministic. It’s just hard to think about.

It’s still early days, and I am still feeling good about this event-driven scheme, but I am a bit more fearful about it than I was. The trick with this scheme will be to do things so that we don’t have to think much if at all about the order of things. If we can do this, it’ll be a super scheme. If we have to think a lot, or we make a lot of mistakes, then it may not be better than what we have in D2.

Our Next Challenge

Our next challenge will be to create two Monsters who want to have the same Coordinates, and to code up the appropriate conflict resolution. Part of that will be figuring out what we want. And the first thing will be to see what it does now.

Begin with a new test.

        _:test("Two Monsters Colliding", function()
            local c1 = Coordinates(10,10)
            local c2 = Coordinates(11,10)
            local c3 = Coordinates(12,10)
            local m1 = Monster()
            Q:subscribe(m1)
            m1:moveTo(c1)
            local m2 = Monster()
            Q:subscribe(m2)
            m2:moveTo(c3)
            Q:publish("update")
            _:expect(m1:where(),"m1 didn't revert").is(c1)
            _:expect(m2:where(),"m2 didn't revert").is(c3)
        end)

Monsters all want to move to (11,10) so this should fail with two errors, I think.

3: Two Monsters Colliding  -- Actual: (11,10), Expected: (10,10)
3: Two Monsters Colliding  -- Actual: (11,10), Expected: (12,10)

Monsters aren’t interested in the request method, but now they need to be:

function Monster:requestMoveTo(sender,coord,decline)
    if coord == self._coord then
        decline(sender)
    end
end

This won’t quite do. We should ignore our own publications.

function Monster:requestMoveTo(sender,coord,decline)
    if sender ~= self and coord == self._coord then
        decline(sender)
    end
end

Let’s run and see what happens. I rather suspect that m1 will be on the square, and m2 will not, but I am far from sure.

3: Two Monsters Colliding m2 didn't revert -- Actual: (11,10), Expected: (12,10)

My expectation is not met. Timing bug in my mind, probably. Let’s see if I can explain what happened.

We know that m1’s update is called before m2, because subscriptions are done in the order received. We should verify that, but I’m pretty sure. So the sequence, let’s see, is:

“update”
m1:update
m1 sets its coord to (11,10)
m1 publishes “request”
m1 update returns with m1 at (11,10)
m2:update
m2 sets to (11,10)
m2 publishes “request”
m2 update returns with m2 at (11,10)
m1’s “request”
m1 sees request is its own, ignores
m2 evaluates m1’s request, finds itself on (11,10)
m2 tells m1 to revert to previous (c1)
m2’s “request”
m1 sees request but is no longer on (11,10)
m2 sees request is its own, ignores
m2 remains on (11,10)

With a little cleanup the test is this:

        _:test("Two Monsters Colliding", function()
            local c1 = Coordinates(10,10)
            local target = Coordinates(11,10)
            local c3 = Coordinates(12,10)
            local m1 = Monster()
            Q:subscribe(m1)
            m1:moveTo(c1)
            local m2 = Monster()
            Q:subscribe(m2)
            m2:moveTo(c3)
            Q:publish("update")
            _:expect(m1:where(),"m1 should have reverted").is(c1)
            _:expect(m2:where(),"m2 should not have reverted").is(target)
        end)

And it runs. Commit: When two monsters try to move to same coordinate, only one succeeds.

I could have said “second one” but in general, we’re not going to know the order in which objects are created.

Should we extend this test to three monsters? Let’s do.

        _:test("Two Monsters Colliding", function()
            local c1 = Coordinates(10,10)
            local c2 = Coordinates(12,10)
            local c3 = Coordinates(11,9)
            local target = Coordinates(11,10)
            local m1 = Monster()
            Q:subscribe(m1)
            m1:moveTo(c1)
            local m2 = Monster()
            Q:subscribe(m2)
            m2:moveTo(c2)
            local m3 = Monster()
            Q:subscribe(m3)
            m3:moveTo(c3)
            Q:publish("update")
            _:expect(m1:where(),"m1 should have reverted").is(c1)
            _:expect(m2:where(),"m2 should have reverted").is(c2)
            _:expect(m3:where(),"m3 should not have reverted").is(target)
        end)

This works as expected, m1 and m2 are set back, and m3 gets the tile. Last come first served, how about that?

Let’s sum up.

Summary

I am pleasantly surprised, which is unusual in this line of work. When multiple movers try to move to the same coordinate, only one of them succeeds and the others are rebuffed. What has made this work, in large part, was the discovery that we have to revert them, because we can’t predict when their setting action will take place. So letting them do it and then take it back made things work.

So far, my sample objects are pleasingly simple. We’ll learn more as we try to trigger combat, to pick up Loot, to open Chests, and to implement more “global” strategies like “move toward the player”. That last one seems most interesting to me just now.

In this case, I think the reversion works well enough to be quite acceptable.

One thing that is worthy of note is that when we receive a published message, that message may contain the publisher object (and in a current case a callback method), and a receiver of that publication can send an object message to the publisher. We’re not requiring that receiving object to publish back. Once you have an object in hand, you can send it a message.

This means that this architecture, whatever it is, is not entirely event driven, or at least not entirely driven from the Queue. It might be interesting to try having the Monsters send back a “revert” publication when they object to what has happened.

Maybe we’ll try that tomorrow. Pushing this idea to its limits is part of the experiment. That said, I’m more interested in something clean that works than I am in something that sticks to a pattern beyond its usefulness.

We’ll see. Still early days. I hope you’ll stop by next time.