Tuesday, May 27, 2014

Imaginary Graph Traversal Woes

So we worked on Imaginary some more. Unsurprisingly, the part that was supposed to be easier was surprisingly hard.

As part of the change Glyph and I are working on, we needed to rewrite the code in the presentation layer that shows a player what exits exist from a location. The implementation strategy we chose to fix looking at stuff involved passing a lot more information to this presentation code and teaching the presentation code how to (drumroll) present it.

Unfortunately, we ran into the tiny little snag that we haven't actually been passing the necessary information to the presentation layer! Recall that Imaginary represents the simulation as a graph. The graph is directed and most certainly cyclic. To avoid spending all eternity walking loops in the graph, Imaginary imposes a constraint that when using obtain, no path through the graph will be returned as part of the result if the target (a node) of the last link (a directed edge in the graph path) is the source (a node) of any other link in the path.

If Alice is in room A looking through a door at room B then the basic assumption is that she should be able to see that there is a door in room B leading to room A (there are several different grounds on which this assumption can be challenged but that's a problem for another day). The difficulty we noticed is that in this scenario, obtain gets to the path Alice -> room A -> door -> room B -> door and then it doesn't take the next step (door -> room A) because the next step is the first path that qualifies as cyclic by Imaginary's definition: it includes room A in two places.

Having given this a few more days thought, I'm curious to explore the idea that the definition of cyclic is flawed. Perhaps Alice -> room A -> door -> room B -> door -> room A should actually be considered a viable path to include in the result of obtain? It is cyclic but it represents a useful piece of information that can't easily be discovered otherwise. Going any further than this in the graph would be pointless because obtain is already going to make sure to give back paths that include all of the other edges away from room A - we don't need duplicates of those edges tacked on after the path has gone to room B and come back again.

Though there are other narrower solutions as well, such as just making the presentation layer smart enough to be able to represent Alice -> room A -> door -> room B -> door correctly even though it hasn't been directly told that the door from room B is leading back to room A. This would have a smaller impact on Imaginary's behavior overall. I'm not yet sure if avoiding the big impact here makes the most sense - if obtain is omitting useful information then maybe fixing that is the best course of action even if it is more disruptive in the short term.

Tuesday, May 20, 2014

De-cruft (Divmod Imaginary Update)

Over the weekend Glyph and I had another brief hack session on Imaginary. We continued our efforts towards fixing the visibility problem I've described over the last couple of posts. This really was a brief session but we took two excellent steps forward.

First, we made a big chunk of progress towards fixing a weird hack in the garment system. If you recall, I previously mentioned that the way obtain works in Imaginary now, the system will find two links to a hat someone is wearing. In a previous session, Glyph and I removed the code responsible for creating the second link. This was a good thing because it was straight-up deletion of code. The first link still exists and that's enough to have a path between an observer and a hat being worn by someone nearby.

The downside of this change is that the weird garment system hack was getting in the way of that remaining link being useful. The purpose of the hack was to prevent hats from showing up twice in the old system - once for each link to them. Now, with only one link, the hack would sometimes prevent the hat from even showing up once. The fix was fairly straightforward. To explain it, I have to explain annotations first.

As I've mentioned before, Imaginary represents a simulation as a graph. One powerful tool that simulation developers have when using Imaginary is that edges in the graph can be given arbitrary annotations. The behavior of simulation code will be informed by the annotations on each link along the path through the graph the simulation code is concerned with. Clear as mud, right?

Consider this example. Alice and Bob are standing in a room together. Alice is wearing a pair of white tennis shoes. Alice and Bob are standing in two parts of the room which are divided from each other by a piece of red tinted glass. A realistic vision simulation would have Bob observing Alice's shoes as red. Alice, being able to look directly at those same shoes without an intervening piece of tinted glass, perceives them as white. In Imaginary, for Bob to see the tennis shoes, the vision system uses obtain to find the path from Bob to those shoes. The resulting path necessarily traverses the Idea representing the glass - the path looks very roughly like Bob to glass to Alice to shoes. The glass, being concerned with the implementation of tinting for the vision system, annotates the link from itself to Alice with an object that participates in the vision simulation. That object takes care of representing the spectrum which is filtered out of any light which has to traverse that link. When the vision system shows the shoes to Bob, the light spectrum he uses to see them has been altered so that he now perceives them as red.

Clearly I've hand-waved over a lot of details of how this works but I hope this at least conveys the very general idea of what's going on inside Imaginary when a simulation system is basing its behavior on the simulation graph. Incidentally, better documentation for how this stuff works is one of the things that's been added in the branch Glyph and I are working on.

Now, back to hats. The hack in the garment system annotates links between clothing and the person wearing that clothing. The annotation made the clothing invisible. This produced a good effect - when you look around you, you're probably not very interested in seeing descriptions of your own clothing. Unfortunately, this annotation is on what is now the only link to your clothing. Therefore, this annotation makes it impossible for you to ever see your own clothing. You could put it on because when you're merely holding it, it doesn't receive this annotation. However, as soon as you put it on it vanishes. This poses some clear problems: for example, you can never take anything off.

The fix for this was simple and satisfying. We changed the garment system so that instead of annotating clothing in a way that says "you can't see this" it annotates clothing in a way that merely says "you're wearing this". This is very satisfying because, as you'll note, the new annotation is a much more obviously correct piece of information. Part of implementing a good simulation system in Imaginary is having a good model for what's being simulated. "Worn clothing is worn clothing" sounds like a much better piece of information to have in the model than "Worn clothing can't be seen". There's still some polish to do in this area but we're clearly headed in the right direction.

By comparison, the second thing we did is ridiculously simple. Before Imaginary had obtain it had search. Sounds similar (well, maybe...) and they were similar (well, sort of...). search was a much simpler, less featureful graph traversal API from before Imaginary was as explicitly graph-oriented as it is now. Suffice it to say most of what's cool about Imaginary now wasn't possible in the days of search. When obtain was introduced, search was re-implemented as a simple wrapper on top of obtain. This was neat - both because it maintained API compatibility and because it demonstrated that obtain was strictly more expressive than search. However, that was a while ago and search is mostly just technical baggage at this point. We noticed there were only three users of search left (outside of unit tests) and took the opportunity to delete it and update the users to use obtain directly instead. Hooray, more code deleted.

Oh, and I think we're now far enough beneath the fold that I can mention that the project has now completed most of a migration from Launchpad to github (the remaining work is mostly taking things off of Launchpad). Thanks very much to ashfall for doing very nearly all the work on this.

Monday, May 12, 2014

Seeing Things Right (Divmod Imaginary Update)

Earlier this month I wrote about how Glyph and I have been trying to fix a bug in Imaginary. Since then we've worked on the problem a little more and made some excellent progress.

If you recall, the problem involved being shown articles of clothing as though they were lying on the floor rather than being worn by nearby people. I mentioned that our strategy to fix this was to make the "look at something" action pay attention to more of the structure in the simulation graph.

That's just what Glyph and I did when we got together to work on this some more last week.

The version of the "look at something" action in trunk operates in two steps. First, it searches around the player in the simulation graph for an object satisfying a few simple criteria:

  • The object is something that can be seen at all - for example, a chair or a shirt, not the wind or your rising dread at the scritch scritch scritch noise that always seems to be coming from just out of your field of vision.
  • The object is something the player's senses actually allow them to see - for example, objects not draped in a cloak of invisibility, objects not sitting in a pitch black room.
  • The object answers to the name the player used in the action - "look at hat" will not consider the Sears tower or a passing dog.
  • The object is reasonably nearby (which I'll just hand-wave over for now).

Having found one and only one object satisfying all of these criteria (behavior for the case where zero or more than one result are found produce another outcome), the action proceeds to the second portion of its implementation. It invokes a method that all objects capable of being seen are contractually obligated to provide, a method called visualize which is responsible for representing that thing to the player doing the looking. The most common implementation of that method is a stack of special-cases:

  • is the thing a location? if so, include information about its exits.
  • does the thing have a special description? if so, include that.
  • is the thing in good condition or bad condition? include details about that.
  • is the thing wearing clothing? if so, include details about those.
  • is the thing a container and open? if so, include details about all the things inside it.

Much of this logic is implemented using a plugin system so, while somewhat gross, it at least holds with some of Imaginary's goals of generality. However, it has some problems beyond just being gross. One of those problems is that the full path from the player doing the looking to all of the things that appear in the visualize method's result is not known. This is because the path is broken in half: that from the player to the direct target (whatever something names) and that from the direct target to each of the (for lack of a better word) indirect targets (if Bob looks at Alice then Alice is a target of the action but so is the axe Alice is holding behind her back, Alice's hat, etc). And in most cases the problem is even worse because the second part - the path from the direct target to each of the indirect targets - is ignored. Breaking up the path or ignoring part of it like this has problematic consequences.

If Alice is carrying that axe behind her back and Bob looks at her, unless you know the complete path through the simulation graph from Bob to the axe then you can't actually decide whether Bob can see the axe or not: is Bob standing in front of Alice or behind her?

The idea that Glyph and I are pursuing to replace the visualize method solves this problem, cuts down significantly on the grossness involved (that is, on the large amount of special-case code), and shifts what remaining grossness there is to a more suitable location - the presentation layer (where, so far as I can tell, you probably do want a lot of special-case code because deciding exactly how best to present information to people is really just a lot of special cases).

Perhaps by now you're wondering how this new idea works.

As I've mentioned already, the core of the idea is to consider the full path between the player taking the action and the objects (direct and indirect) that end up being targets of the action.

An important piece of the new implementation is that instead of just collecting the direct target and then acting on it, we now collect both the direct target and all of the indirect targets as well. We also save the path to all of these targets. So, whereas before resolve_target (the method responsible for turning u"something" into some kind of structured object, probably an object from the simulation graph) would just return the object representing Alice, it now returns the path from Bob to Alice, the path from Bob to Alice's hat, the path from Bob to Alice's axe, the path from Bob to the chair Alice is sitting in, and so forth.

With all this extra information in hand, the presentation layer can spit out something both nicely formatted and correct like:

Alice is here, wearing a fedora, holding one hand behind her back.
Or, should it be more appropriate to the state of the simulation:
Alice is here, her back turned to you, wearing a fedora, holding an axe.

Of course, we haven't implemented the "holding something behind your back" feature of the "holding stuff" system yet so Imaginary can't actually reproduce this example exactly. And we still have some issues left to fix in the branch where we're working on fixing this bug. Still, we've made some more good progress - both on this specific issue, on documentation to explain how the core Imaginary simulation engine works, and on developing useful idioms for simulation code that has yet to be written.

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.