Sunday, October 19, 2008

What is Tale Anyway?

So, I've been working on this project that's currently called Tale for nearly a decade now. The notion is to build an interesting, fun, humorous, immersive, narrative virtual reality. If you're into such things, it's more succinctly called a distributed, web-based MUD. I don't intend to go into detail about how Tale is like a MUD and unlike a MUD. This article is intended to explore some of the novel aspects of Tale.

Gameplay

Tale's landing page, tale.im, is the game. You click play and the game begins. There won't be a lengthy sign up and character creation process; everyone starts as a ghost in Limbo or gets straight back to playing from wherever they left off. To start playing, you just click or type "start" and you're consciousness is installed in a standard-issue resident of Dya, the Tale world. From there you can start doing whatever it is you like doing most: socializing, exploring, fighting, building, or getting into character.

Playing Tale is like many things you're probably already familiar with. It's like chatting with friends with an Instant Message client, or IRC, or opening a Terminal and issuing commands. MUDs in general combine the social aspects of chatting with friends, with a virtual world simulator and its own narrative and commands. Some MUDs lean in favor of socialization and others on gameplay. Tale favors neither, allowing you to gracefully shift between mostly chatting and mostly playing. Since the game is in a web-browser instead of a specialized chat application or old-fashioned command terminal, Tale can alternate among coherent interactive modes like entering quotes to say aloud like "hello, world!", entering action commands like "go north", typing quick commands with single keys for mini-games like "p" for "parry", "r" for riposte, "f" for feint if you're fencing, or browsing through menus to discover commands visually.

Already in Instant Message and IRC clients, you might be familiar with commands like "/me laughs" (that you can use in AIM) or "/nick cowbert" (that you can use to chose a name in IRC). If you use Vim, you might already be familiar with colon commands like ":w". If you use FireFox's incremental search feature, you know that you can use single-quote and slash to start searching for text as you type, alternating between single-key command mode into a full-line command mode.

Tale's input field will accept similar commands depending on whether you're mostly chatting, mostly playing, or performing quick, expert actions. If you're mostly chatting, you'll be able to issue commands with the slash "/" prefix like /go north, and when you're mostly playing you'll be able to chat with a quote prefix like "hi. If you're in an expert mode where you're, say, navigating a yacht on the high-sea with discrete arrow key and letter key commands, you can start entering a chat or command with the same keys.

Narration

Each player in the Tale world has a narrator. This is the charming fellow who listens to your commands and tells you how the story unfolds in response. The narrator is a program that keeps track of what you already know and what you're likely to be interested in and interprets the events occurring around your character like, "Joe says 'hi'.", into just that kind of textual prose, as well as taking your commands and plugging them into the simulator in the selfsame event objects. The ideas of "events" and "things" are central to how Tale works behind the scenes, but it suffices to say that if you are "Elbereth" and you're talking to "Glorfiniel", the narrator would translate events like:

Elbereth Say "Hello" to Gorlfiniel
Glorfiniel Say "Hi" to Glorfiniel

…to story-like narrative accounting for various linguistic and cognitive assumptions that you regularly make — "You say, 'Hello', to Glorfiniel and she says, 'Hi', back.". There is a lot of room for making the narrator more and more interesting as Tale development continues, but there's code in Tale already that creates reasonable paragraphs from a stream of events, accounting for pronouns and such, but still sounds fairly robotic.

Having a complex narrator serves many purposes in Tale. First, it makes the game immersive. It also relieves the burden of creating lots of static content, which is one of the limiting factors that ultimately ends with most games feeling rather shallow. A complex narrator can also abstract the tired MUD practice of BATTLE SPAM, where lines upon lines of discrete hits and jabs rapidly scroll up the chat buffer.

The most subtle benefit of the narrator is that it can introduce a significant burden for programmers seeking to automate their characters, often called "botting". "botting" tends to diminish the quality of gameplay for non-programmer players. With the narrator in our arsenal, we can engage in an arms race with "botters", continuously evolving the narrator to deter botting without banning the practice outright. This incentive structure could be a lot of fun for everyone.

Beyond the Narrative

The narrative is the centerpiece of Tale gameplay. However, unlike a Telnet or Teletype MUD, Tale is not strictly text-based. Since the game takes place in a web browser, we intend to take advantage of the opportunity to add icons, maps, inventory visualizations, sounds, and atmosphere and lighting changes to punctuate the narrative.

Among other things, we're planning to use "parametric" graphics to underscore the narrative. For example, if you're in a sailing or flying vessel, or riding a rabbit around the Tale world, your ride will have a parametric icon. We're using SVG graphic manipulation on the server-side to render permutations of layers from "macro" graphics to produce customized versions of each ride and vessel. The parameters include things like the genetic domain of your steed (Is it descended from an elephant? Did the Narwhal bless it with a tusk?), and the installed rigging on your Zeppelin. The two Ride macro graphics have around 100 layers each.

Inspired by Josh Lewis's old blog site, we intend to mix up the style sheet colors on the page slowly and subtly to reflect the time of day and lighting of your surroundings as you explore the world. Each face of the world has its own color scheme and different parts of the world are lit by the 20-sided Sun and various celestial dice, at times filtered through dappled shade, or illuminated by magma and mana. Using alpha-translucent PNG renderings of SVG graphics, and subtly tuning the foreground and background colors of the entire page, we'll gradually modify the mood of the narration.

And there's Music! The musical selection you experience as you roam the world will vary based on what face of Dya you're travelling on and the tension level of the narrative: safety, adventure, battle, and peril. Chris Pasillas has composed six brilliant themes and variations for Tale and is currently rendering them. The game uses a variation of Scott Shiller's SoundManager library that's been ported to operate as a Chiron JavaScript module. (The largest distinctions are that the Flash bridge code has been factored into its own module, and the API has been simplified. It's a complete rewrite using SM2 as an MTASC reference.)

Engine

The Tale engine is a real-time clock-based event-driven simulation. Every event can trace its cause to a tick of the world clock, which for the time being is imagined to be once per second. The difference between a player character and a non-player character (NPC or MOB in the MUD parlance) is that a non-player character generates a progression of commands on demand using a Python generator that yields Event or Verb object trees in response to observations about their environment and their current state, and a player character has a queue of the same kind of Event or Verb trees. This means that invoking a command in Tale does not render an immediate physical response from the world's engine. Rather, a command is translated by the narrator into an Event and it's enqueued to be invoked when the world clock ticks and visits everything that's not busy or waiting, in the whole world. This levels the playing field between people with nearly instantaneous Internet connections to the Tale server with those who have up to one clock tick worth of lag. It also, in a sense, regulates a certain "conservation of energy" law throughout the world, permitting game mechanics to be tuned more accurately and fairly.

World

Feature Number One in Tale is the data structure we've chosen to model the world. This data-structure underpins it's potential consistency, algorithmic subtlety, performance, scalability, and distributability. This data-structure conveniently models a world of arbitrary size, scope, and detail and provides the scaffolding for engine effort minimization for event propagation, abstraction, and synthesis.

So, what is it? Well, nothing new really: it's a tree. Depending on the scope and particular region of application, its children have 0, 4, 6, or 9 branches on each node. Most of the world is simply a quadtree. Each node has four children, one for each quadrant. The top of the quadtree has a bounding box that encompasses exactly all of contained, square region, and for purposes of Tale, conceptually encompasses all of the air-space above that region. A room is a leaf of the quadtree: a node through which players travel with a unit width and height. Each node is an abstraction of all of its contained rooms, containing the sum of its rooms contents. Roaming the quadtree, each player can divine it surroundings by analyzing the contents and events occurring in its own room, and then those events and contents of each of the more abstract rooms that contain it all the way up to the root of the world tree. Each room is directly connected to its parent and children, and traversing linearly across the plane of the world uses tree traversal algorithms where you zoom in and out of the quadtree to find your destination.

Among the algorithmic possibilities that the quadtree provides a scaffold for, we can provide multi-scale gameplay, the same inspiration behind the recently released, Spore. The most mundane way this might be applied would be to have larger scale creature roam the world in abstract bounding boxes, like a Fire Drake that would move from 16x16 room to 16x16 room. Room abstractions could also be used for flight or sea navigation, since one travels higher and faster with that medium, somewhat negating the mundane obstacles of the world floor. As an eagle, one might move about the world by zooming in and out instead of traversing in cardinal directions. Also, more abstract forms of gameplay might take place entirely on room abstractions. For example, melee would occur in 1x1 rooms, ranged attack (missiles and magic) in 8x8, tactics at 32x32 with 4x4 tiles, strategy at 256x256 with region-sized tiles, and politics at larger yet. Taking a moment to step out of a first-person player experience, garnering increasingly abstract political support from larger social organizations, gameplay could scale from thief to Queen).

Another algorithmic possibility is maintenance of the world's physical invariants, like global distribution and availability of various resources. Using abstractions to redistribute resources absolutely throughout the world would make it possible to keep the weight of gold throughout the world constant. This would prevent the most common physical inflation problems that most MUDs suffer.

The other major implication is that the quadtree permits entire branches of the world to run on independent servers with minimal cross-talk. During my last year at Cal Poly, Ryan Witt engaged his distributed computing team at Caltech to implement a Distributed Hash Table (Chord) for Tale and we extensively discussed the implications of the quadtree for purposes of distribution for scale and redundancy. Ryan and I are now roommates working at FastSoft. The topic of distributed computing comes up from time to time, even though we still need to get a vertical gameplay stack working on a single system before we begin implementing distribution.

Events

One problem Shawn Tice (who needs his own home page, because he's too awesome not to have one at this juncture) and I struggled with when we were coding up the second Python rendition of the quadtree was event management. The general notion has always been that events would escalate up the quadtree to a scope that contains all objects that can notice the event, then each object would have an opportunity to respond to the event by visiting each node in their room's "scope chain". The borrowed notion of a scope chain, in this case, means the containing room and the transitive closure† on its parents. Events would each have an "impact" attribute and each object would have a "sense" attribute. So, each time the world ticks, a bottom up visitation of the world would calculate the minimum impact that an event would need to have to be noticed by the one thing in that branch of the world with the highest sensitivity. This would be performed for all of the senses in parallel: visual, aural, olfactory, thermal, thaumaturgical, social, and such. All objects that can have effect events would have senses. For example, a wall can hear a sound so that it can echo it. Most events would also be directed, so they can only propagate in one of the cardinal directions: north, south, east, or west.

However, as you may have already had an inkling of suspicion, this quadtree-based event propagation model isn't actually realistic, and adding realism would nullify the performance and scalability benefits of the system. For example, with the described event propagation system, if you were standing in a room off-center of a quadtree, as at (2, 2) of a 4x4 quadtree, an sound that is loud enough to carry to room (3, 3) might not be loud enough to carry to room (1, 1). The sound would have to be loud enough to carry to (0, 0) before (1, 1) would hear it at all. So, to guarantee that events radiate the same distance in every direction, you need to propagate events laterally, not merely along the quadtree abstraction scope. However, radiating events laterally defeats the performance benefits of restricting perceptible events to those along the scope chain.

So, there was a trade off between performance and realism. Then we remembered we were writing a game. Thinking back to the original Zelda, we observed that each tile of the screen was analogous to a room in Tale, and that every screen in Zelda was analogous to one of the nodes in its abstract node scope chain. That is, there was some parent room that contains about 30 of the rooms Link walked around in. When he got to the edge of the screen, he was no less privy to what was going on in the neighboring room than he was on the opposite side of the screen. So, we decided that the same abstraction would be sufficient for Tale, except that in Tale, the opportunity for zooming in and out around your character was much more profound; we could provide zoom perspectives for every binary order of magnitude.

Frameworks

The current underlying technologies include Python, Twisted, AJAX, Comet, and Lighttpd. In the past, I dabbled with C++ and Boost, including an iostream system that decoupled input and output, had reasonable variable names, and supported VT100 stream functors, but that code branch has been abandoned since 2002. In addition, the project has inspired the creation of frameworks that I'm calling Chiron (a JavaScript module system), and Python on Planes (a system for persistent HTTP route and responder trees).

Parting Words

So, Tale is a pretty massive undertaking. When I started this project, I had no idea that good ideas took so much more time to implement than paltry ones, but that lesson's learned. To meet at least one of my New Year resolutions (that is, one of the milestones for Tale), I'm cutting back scope in the short term in order to get the project up and running by January. A lot of this design, if not all of its powerful implication, I plan to realize by then. This weekend, I've been working on sewing the quadtree, the Dyan world design, and the Narrator into a single piece. As always, I'm looking for people who are willing to volunteer to set themselves up with commit access to Tale so that, in the absence of time to spend on the project (which I know none of us have), a sufficient body of people can randomly wake up in a cold sweat with a bad idea and have nothing between them and implementing it for Tale!


The excessively precise term transitive closure, in this case, means the room's parent, grandparent, great-grand-parent, ad nauseam. Ad nauseam, in this case, means, "until you retch from nausea or meet Adam and Eve: whichever comes first."

No comments: