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.

No comments:

Post a Comment