Sunday, May 4, 2014

Update on Divmod Imaginary

Recently Glyph and I have been tinkering with Imaginary. For anyone reading who doesn't know, Imaginary is the current iteration of the project which is the reason the Twisted project started. It's a simulation kernel geared towards the construction multiplayer adventure-style games - imagine something in the ballpark of Zork or CircleMUD or a piece of interactive fiction.

The last time I worked on Imaginary I was trying to understand a bug that I thought was in the new "obtain" system. I made some progress, mostly on documenting how the "obtain" system works, but I eventually got lost in the tall grass trying to understand how exactly the implementation led to the bug and what an appropriate fix might be. It was nice to get some of that documentation written but I eventually found myself making no progress and got frustrated and gave up.

So it is very nice to have Glyph participating again (he did write the "obtain" system in the first place, after all).

"But wait," I hear you ask, "what is this obtain thing?"

As I mentioned, Imaginary is a simulation kernel. One of its primary responsibilities is to provide an object model for the representation of the simulation scenario. Another is to offer tools for interacting with that object model. "obtain" is the name of one of the central APIs Imaginary offers. It lets an application developer using Imaginary find objects in the simulation. For example, when the weather system in your simulation decides it is time to rain on the plains in Spain it relies on "obtain" to find any actors (or inanimate objects) on those plains in order to drop some water on them.

So, the problem? Imagine that Alice and Bob are in a room together. Alice is wearing a fedora hat. When Bob looks around the room he sees Alice is there. He may also see that Alice is wearing a hat. The bug is that Bob will see the hat as if it were sitting on the floor instead of on Alice's head.

Put another way, the world would be described to Bob like this:

You are in a room. Alice is here. A fedora hat is here.

When a more correct description would be more like this:

You are in a room. Alice is here. She is wearing a fedora hat.

This had me quite stumped. I was chasing graph nodes and graph edges through various graph traversal functions. There's quite a bit of extra data associated with each node and edge, mostly for describing what useful simulation behavior each as (for example, defining what happens if the object ever gets wet because it has started raining) and having to sort through all of this didn't make the job any easier. I eventually concluded the graph traversal logic was just wrong in some terribly subtle way and gave up.

After a long break, Glyph and I took a look at this code together (initally at PyCon 2014 and a couple times since as well). We started out just by going over the basics of how the graph traversal code works and why it's useful for it to work this way. This turned out to be a really good idea as it pointed out some misunderstandings I had about the intent of the system. Glyph also had the great insight that we should actually be paying more attention to the application code using obtain rather than the implementation of obtain itself. This was great because it looks like the real culprit is mostly that application code. It's getting back lots of useful results and then misinterpreting them.

The misinterpretation goes something like this.

  • To describe Bob's surroundings to him, the "look" action does an "obtain" call on Bob's location. It specifies that only results for visible things should be returned from the call.
  • "obtain" walks around the simulation graph and discovers that Alice exists and from Alice discovers there's a fedora. Because of quirks in the way hats are implemented it actually discovers the fedora twice via different edges in the graph (this is perhaps also a bug but not one I'm going to try to discuss now).
  • The "look" action inspects the graph nodes that came back from the "obtain" call. When inspecting the fedora for the first time it notices it is being worn by Alice and doesn't try to present it as if it were simply present in the room. When inspecting the fedora for the second time, though, it forgets this. And this is where the bug arises.

My mistake was thinking that the fedora being present twice was a bug in "obtain". This is a necessary feature, though. While we'll probably go and fix the bug with hats that makes the fedora show up twice, the "look" action could have the same problem in other situation. For example, a mirror in the room might let Bob see both Alice and the hat in two places. It needs to be able to keep the graph paths to objects straight to present cases like this correctly.

So far we haven't implemented the solution to this problem completely. We have a pretty good start, though, involving making the "look" action more explicitly operate on paths instead of only the objects at the *end* of each path. And actually understanding all the pieces of the bug helps a lot.

No comments:

Post a Comment