Sunday, November 19, 2006

Imaginary (An architectural overview)

View from 20 klicks




Imaginary is going to be a simulation engine. Simulation engine is used here to refer to any software library which is capable of modelling (not necessarily in a manner which mirrors reality) interactions between a number of systems (not necessarily systems taken from reality). Some examples of such systems are physical interaction between different objects, chemical change in a material due to the introduction or removal of energy, and alterations in the propagation of electromagnetic radiation by intermediate transmission substrates.




Behaviors implemented by a single system must be specified completely and in detail in order to achieve somewhat predictable outputs for a given set of inputs. Likewise, interaction between different systems needs to be specified somehow. Explicitly defining the interactions of each system with every other system requires N! such definitions, where N represents the total number of systems. As N increases, N! increases prohibitively more quickly, preventing a large number of systems from being supported.
An important aspect of a successful implementation of a simulation engine is avoidance of this combinatorial explosion.




Currently, it would be most accurate to call Imaginary part of a research project for exploring possible ways to implement a simulation engine. It is the 5th or 6th (or perhaps 7th or 8th, depending on how you count) generation implementation by the team of developers involved in the project.




What it can do now is support multiuser interaction in a single persistent world, accept and parse a limited number of commands for interacting with the world, and transmit a limited amount of information to each user when an observable part of the world changes somehow.



Containing Framework




In its current incarnation, Imaginary is a Mantissa offering. Mantissa offerings are beyond the scope of this post, but you can read a bit about them on the Divmod Wiki or in previous blog entries of mine. If you are interested in Imaginary, then you can probably skip that for now. The salient points are simply that:



  • Imaginary ignores signup because it's taken care of.


  • Imaginary uses Axiom for persistence because that's what Mantissa encourages.


  • Imaginary uses Twisted for networking.




Taking Action




User interaction is close to the primary purpose of Imaginary. The results of the simulation need to be exposed, and changes to the state of the simulation world must be enactable by users. The current user input system for Imaginary is a simple text based interface exposed over SSH. Text input is parsed into higher level structures known as actions. Actions define their own parsing rules and are associated with code for inspecting or manipulating the game world.




Examples of actions are opening or closing a container, picking up or dropping an object, speaking, moving around, or examining some aspect of the world. When an action has completed, observers are notified using the event system. Sometimes, the implementation of an action is responsible for emitting these events. Other times, the game system which the action has interacted with will emit them. However, actions are not always successful. An object may be too heavy to be taken or a container may already already be in the state into which opening or closing it would have put it. These are some of the simpler cases which Imaginary can handle: the implementation of the action handles exceptions from the game system it is manipulating and emits the appropriate event (for example, instead of broadcasting that Alice has lifted a boulder above her shoulders, it would broadcast that Alice struggles and strains but is unable to budge the boulder).




Certain actions can result in more complex interactions. For example, movement between two locations involves two events being broadcast: one to the observers at the location being vacated, one to the observers at the location being occupied. To deal failures with this kind of action, other projects have often adopted the look before you leap approach: the action implementation can perform checks to determine if the actions is going to fail; if it is, it can take care to broadcast only a failure event to the location the user attempted to leave (not broadcasting any event to the destination location, since no observable change has occurred there). The drawback to this solution is that it requires the movement action to be completely aware of every interaction which might prevent the movement from succeeding.




Instead, Imaginary's action system uses a transactional event broadcasting mechanism. When the movement action begins, the departure event is broadcast at the location being vacated. Next, the action invokes the actual code in the movement system (or containment system). If the movement is not actually possible, this will raise an exception, preventing further action code from running and causing the entire action to be aborted. Events broadcast as part of an aborted action are not sent to observers. If the containment system allows the movement, the action continues to execute, resulting in an arrival event being broadcast to the destination. Once the action has finished running without aborting, all of the events it emitted are delivered to observers.



The Observable World




I've mentioned events above quite a bit. Events are the basic unit of information which moves around an Imaginary world. When someone walks into a room, if you can see it happen, it is because you received an event that described the change in the state of the world. If you can't see it happen, the event has failed to reach you for some reason. If you're in a dark room, for example, events which convey visual information may be unavailable to you.




Blindfolds, colored glass boxes, parabolic dishes and other world features which modify the propagation of an event are implemented by giving objects an opportunity to wrap a proxy around an event as it propagates. When an event is finally observed, it may have several layers of proxying wrapped around it which change what the observer actually perceives. A red glass box may make red items inside it invisible and make green items appear black. The red and green balls rolling around inside the box are unaware of the visible light red/yellow/blue color system, though. This leaves the implementation of colored balls simple and unfettered by all of the complications which may arise between the balls themselves and other actors in the world which observe or manipulate them.



Graph Traversal




Many of the concepts discussed above rely on what should probably be considered the core of Imaginary: a set of APIs which allow the object graph representing the simulation world to be queried and traversed in a structured way. All physical objects in the simulation world are represented by an instance of a class named Thing. Thing has a couple important methods: links and findProviders.




links defines the relationships a Thing has with other Things in the world. Everything is linked to itself and its location. Boxes, for example, are also linked to their contents. A room with a door is linked to the room into which the door leads. The implementation of links is extensible using a feature of Axiom called powerups. This is reminiscent of the Componentized idea from previous iterations of the research project.




findProviders implements a breadth-first, depth- and interface-limited search of a Thing's links. It also applies proxies as it traverses the object graph. This method supports both the action system and the event system in a major way. The input parser uses it to resolve string names into concrete object references. The event broadcast system uses it to find observers who should receive events.



Get Involved






  • You can read more in the Reality archives: http://twistedmatrix.com/pipermail/reality/


  • You can check out the code: svn co svn+ssh://divmod.org/svn/Divmod/trunk Divmod


  • You can join us on IRC in #imagination on irc.freenode.net


Thursday, November 16, 2006

Tuesday, November 7, 2006

Reading List for September/October

The Space Opera Renaissance. Edited by David G. Hartwell and Kathryn Cramer.

This is a collection of shorts. The stated goal of the work is to offer a definition of the term space opera by way of example.

The opening volley consists of these four stories:

The Star Stealers. Edmond Hamilton.
The Prince of Space. Jack Williamson.
Enchantress of Venus. Leigh Brackett.
The Swordsmen of Varnis. Clive Jackson.

I suppose because I am just a little kid, the first two of these nearly turned me off the entire book. They are absolutely typical of the worst stereotypes conjured to my mind by the label of space opera. The names are strange. The plots are contrived while being uninteresting recasts of stories from other genres of fiction. The characters are flat. To be fair, these are stories from 1929 and 1931 respectively. They are pioneering works in the genre of science fiction overall. Still, literary precedents and contextual considerations aren't enough to save them for me. Fortunately I pressed on. Brackett's story, written in 1949, is much more enjoyable. It has a historic feel similar to that of the previous two, and the setting is completely implausible as a science fiction setting, but the writing is well done and the story is actually interesting. It feels like a space adventure. The Swordsmen of Varnis is short and silly, more an extended joke than an example of space opera, or even science fiction. I'm not sure why it was included. However, at a page and a half it's not much of a disruption.

The next three stories are taken from the 60s:

The Game of Rat and Dragon. Cordwainer Smith.
Empire Star. Samuel R. Delany.
Zirn Left Unguarded, the Jenghik Palace in Flames, Jon Westerley Dead. Robert Sheckley.

Just moving forward a decade or two gives a striking change in the level of refinement of the science involved as compared to the first four. The Game of Rat and Dragon has quite an interesting premise and carries it through in an enjoyable style, but doesn't have much of a story. On the other end of the spectrum, the much longer Empire Star involves a very involved sequence of events and follows three characters over a much longer span of time. The universe Delany reveals is subtle and not fully explained, which is certainly part of what grabbed my interest as I read it. Shekley's story is as mystifying as the title might suggest. Perhaps he was making references which simply went over my head, but I basically found the story, if it can be called that, incomprehensible.

The 70s and 80s are carried by the following:

Temptation. David Brin.
Ranks of Bronze. David Drake.
Weatherman. Lois McMaster Bujold.
A Gift from the Culture. Iain M. Banks.

Temptation, Weatherman, and A Gift from the Culture each share their setting with at least one full length novel by the same author. Many people, I'm sure, are familiar with the Uplift and Culture series. I haven't read either of them myself but I suspect I will in the near future. The characters in Temptation were not particularly appealing (they weren't even humanoid, which always makes it tough to decide if their motivations are nonsensical or just incomprehensible - not fun either way, really), but the setting seems interesting. In stark contrast, Weatherman's character development, though brief, was very good, and made more interesting by the fact that the protagonist, Miles Vorkosigan is not a particularly likable fellow. I've heard a lot about Banks' Culture universe, so I would have gotten around to his novels eventually. The Culture doesn't appear much in this short, at least not directly, so I'm not sure how it compares to the rest of the works in this universe. The story was enjoyable though, and well written. Ranks of Bronze is a stand-alone, and has the distinction of being the only science fiction I can think of which includes a legion of Roman centurions (Hmm, Dr Who must have visited the Roman empire at some point, but I can't recall a specific episode).

The 90s is much more of a mixed bag:

Orphans of the Helix. Dan Simmons.
The Well Wishers. Colin Greenland.
Escape Route. Peter F. Hamilton.
Ms. Midshipwoman Harrington. David Weber.
Aurora in Four Voices. Catherine Asaro.
Ring rats. R. Garcia y Robertson.
The Death of Captain Future. Allen Steele.

If you like Hyperion, I guess you'll like Simmons' short story set in the same universe, post-Aeneanism. I mostly found Hyperion to be frustrating, confusing, and often pointless (though perhaps not entirely without redeeming virtues). Orphans of the Helix is okay, but also strikes me as similarly pointless. The Well Wishers also doesn't do much for me. The setting is strange but very uninteresting (which is somewhat intentional, I think, but that doesn't make me enjoy it any more) and the characters fairly flat. Little action takes place during the story as well, which one ultimately learns is a mystery (just in time to learn the resolution). Escape Route is somewhat hard scifi, reminiscent of some of Niven's work. Unfortunately, some of the prose is as obtuse as Niven's. About half the characters are also truly stupid, to a degree which stretches credibility (hmm, another similarity to Niven). It is enjoyable in the way that many hard scifi stories are enjoyable: some cool gadgets makes up for most or all of the other shortcomings. The Death of Capture Future might be more interesting to someone who has read anything about Captain Future before. Since I haven't, it didn't interest me too much. I related to roughly none of the characters, particularly the protagonist, who catches some unlucky breaks and deals with this by being a completely unlikable jackass.

Weber's story reminds me very strongly of Walter Jon Williams' Dread Empire's Fall. They are both serious space opera territory: big fleets zooming through space, classic naval military organizations, battles fought over vast distances between major stellar empires. This is the other kind of story which space opera often summons to my mind.

Ring Rats also has some of this feel to it. The story and setting are totally different from those of Ms. Midshipwoman Harrington, but it has the same feel of big events happening around individual people. In space.

I'm going to skip the last 15 stories since this post is pretty long already. There is some good stuff towards the end, though. If you haven't guessed, the collection is ordered chronologically, so the later stuff is from the late 90s up to the present. One of the stories features a monk, an anthropomorphic (literally) ferret, and the psychological equivalent of a VLA telescope. Another follows most of the life of a cowardly Kzin (set in known space, not by Niven) and his rise to power. Another about the love affair between an adolescent girl and the fledgling AI she (first unintentionally, then intentionally) helps raise to the level of sentience and self-awareness.

There's definitely some good stuff in here. I heartily recommend it to any scifi fan. If you think you may be a space opera junkie, then this is a must read.