| Documentation | Web Resources |
The Destiny Project has as its overarching goal the creation of a computer-based gaming environment (the Destiny Engine). The environment must be capable of sustaining any number of believable "worlds". A particular requirement is that non-player (computer-managed) characters be distinguishable from player (human-managed) characters only with great difficulty. Difficult though this requirement is to address (hence its attraction to us), it is only one of several difficult problems that must be solved to create a believable and immersive game environment.
At the present time, the gap between what biologists and neurologists know about how the brain and other nervous system components work and what philosophers and linguists can justifiably deduce about how people think and communicate is vast. The various techniques used by game designers to supply "artificial intelligence" to computer-run opponents are so lamentably poor that an average 9-year old child has no difficulty determining and exploiting their deficiencies. Basically, we (as humans) have no knowledge of how we actually think, nor are we able to construct a sustainably plausible imitation, even in the limited experiential medium of a computer game.
The pieces of the Destiny Engine so far developed are written in C++ and Java. C++ is arguably the most potent widely-available computer language on the face of the planet. Because the Destiny Project is likely to require 20 years, give or take a decade, to make significant progress toward its lofty goals we make every effort to reduce dependencies on language and computing platform. One of the unfortunate consequences, for onlookers at least, is that we don't tend to make glitzy user interfaces to our stuff because such an effort would only have to be thrown away a few years later.
As a note of purely historical interest, we should say that the Destiny Engine (and project) got its name from early discussions between Bill and Chris as to the role of the storyteller in a role-playing game context. In the truly impressive multi-player online games of that time (such as Ultima Online), story lines were kept moving by a veritable army of behind-the-scenes storytellers (or "Dungeon Masters", as we used to call them).
The discussion first centered on the notion of a Quest, some deed that must be done (e.g. "Bring the sword of the ancient queens to the sacred grove of elder oaks."). How are people prevented from giving up on quests, or simply not taking them up in the first place? Okay, we thought, what if characters were kept on track by a Quest entity of limited powers and intelligence that attached itself impalpably to a character or characters. Its goal is to use its limited powers to bring about a specific event or condition (i.e. the sword of the ancient queens being physically present at the grove). Its powers might involve manipulation of the characters personal characteristics, or influence the reactions of those around them. Extra luck, strength, well-being, or popularity when the character is making progress toward the Quest's goal, and maybe less than usual of those properties when the character is not making enough progress toward the Quest's goal. Of course, it's always possible that the Quest will give up in frustration and leave to seek another host.
Well and good, but involving story lines are not made of a quest alone. We need an entity, we speculated, that had more knowledge and intelligence with broader goals, a Destiny that would spawn quests as needed to further its goals but had no other power to influence the course of events in the world. Involving stories would quite naturally evolve from a system of two or more at-least-partially conflicting Destinies, and it would help if they had the sorts of goals that could never realistically be completed. As an example, consider the possible interplay between "Good must triumph over Evil", "Evil must triumph over Good", and "Biodiversity must be preserved". Naturally, the game engine must manage the activities of the various Destinies, and it was a short step from there to naming the game engine the Destiny Engine.
The problem space of the Destiny Project is vast. There's only so much we can work on at any given time. What we're working on at the moment are:
How does an individual organize their experience of entities and events into classes? How are classes defined in memory? How are classes used to interpret subsequent experiences? How are subsequent experiences used to refine the definition of classes?
What makes me recognize that object as a dog? as brown? as an animal? How do I decide that a vehicle is a sports car? How do I learn what a new word means (such as "eat", or "amalgam")? How do I use experience to define or redefine the boundaries of what it means to eat? When I hear that someone has made an amalgam, how do I use my idea of what an amalgam is to form an understanding, to inform subsequent thinking, to know what questions about the activity might be appropriate?
All of us are aware of being reminded of some things by other things. The reminding process is an important generative function in any creative activity. It is also used in the critical process of forming and using analogies. Past work focused on algorithms for assembling knowledge (remembering) that were specific to the notion of answering a query, but those algorithms do not come close to the power and generality of the "reminding" process as humans use it.
We are currently looking into using feedback with neural networks to model the "spreading activation" notion of how reminding occurs. According to this notion, being made aware of several things also makes us aware of other things, and those other things of still more things. When awareness converges from two or more "directions" in this flow of associations, thoughts can suddenly "leap to mind".
Another current focus is an implementation of an entity's ability to plan a sequence of actions to achieve a goal state. This begins from the ability to define a goal. With a foundation of Bill's work on general expressions and Chris' work on generic quantities, we define a goal state both in terms of a testable Boolean assertion and a distance expression. The Boolean assertion allows the entity to determine at any time whether it has achieved the goal. The distance expression is used to evaluate the difference between any two world-states in terms of their proximity to a world-state in which the goal is satisfied. Paths may then be planned for traversing the high-dimensionality world state space from the current world-state to a world-state in which the goal is achieved.
Here we describe some of the areas that have received our intense focus in the past year or two. These subjects will usually be described in the notebook or (occasionally) in somewhat more formal and expository "white papers". The other thing that these subjects have in common is that we have developed computer programs which incorporate our ideas about them. Other subjects (such as those in the next section) are the subject of speculation, musing, or even designs, but have not had programs developed for them.
The physical layout of a "world" can be mapped, but which features of the world to include and which to leave out depends on the purposes for which the map is to be used. Our solution is to define a map with multiple layers, one layer for elevation information, one for terrain type, one for roads and paths, and so on. For maximum flexibility, not all layers are required, because some games might not need them. We have developed a multi-layer map class with which each available layer registers itself. Algorithms operating on the map can test whether a particular layer type is present, and condition their processing accordingly.
Layers can be implemented in several ways, transparent to the algorithms operating on them. In particular, we have cell-based layers for properties such as terrain type and elevation that pertain to all areas of the map, and sparse layers which are efficient representations for linear features such as roads and waterways. There are designs (but no code) for scale-independent area representations, which we expect will supplant the use of cell-based layers.
We have implemented half a dozen or so algorithms for path finding that take account of terrain, changes in elevation, and means of conveyance. In final form, of course, these will run based on each character's (perhaps faulty) knowledge of the world, not on the world map itself.
Later, we plan to combine the multi-layer map idea with the associative memory classes, augmenting the map model of the world with a knowledge base about the world, which we are calling an "almanac".
A multi-layer map is a truly wonderful way of representing a rich, complex set of data about the physical layout of a world, but all that data is tedious to enter. Unless, of course, you can use a graphic editor that lets you raise mountains, deepen oceans, paint and fill with terrain types, lay out roads, cover areas with water, build bridges, excavate tunnels, et cetera. So we built one. It's not overly slick and polished because for us it's just a way to lay the groundwork (so to speak) for the stuff that really interests us (path planning and knowledge modeling), but it's much better than typing a bunch of text into map files.
It is no secret that human memory is much more about relationships, or associations, between things than it is about things themselves. Computer memory is only about things and not relationships. We have developed a relatively simple model of memory that efficiently maintains associations between things, while storing facts about the things. Sufficient overhead is maintained to support the efficient recall of related facts, a mode of operation in which more frequently used facts are recalled more easily than seldom-used facts, and a model of forgetting.
Once we had a reasonably good associative memory, one of the next questions was what to do with it. We built a user interface for putting knowledge into an associative memory, then turned our attention to developing a way to recall knowledge from an associative memory and organize it to answer a query, such as "Which engineers own white cars?". Our solution involved using the associative properties of the associative memory to efficiently recall facts related to the subjects of the query, then storing them in a differently organized working memory. This working memory was designed so that storing information in it built a web of knowledge with the strands representing the relationships between things, and the things themselves at the nodes where strands were joined. If this sounds intriguing, we have a white paper on the subject with more of the details.
We paid particular attention to following is-a relationships in constructing the web of knowledge. Nobody is a generic engineer. Instead, they're civil engineers, software engineers, railroad engineers, etc. Likewise, nobody owns a generic white car. Chris owns a specific white vehicle which is a Civic which is a Honda which is a car.
Arising out of the work on associative memories is the class for representing a generic quantity in an item of knowledge. Humans don't worry about whether a number they remember is an integer, fixed point, or floating point number, but computers have to, so a class was created to bridge the gap by providing the notion of a generic number, including all the usual mathematical, logical, and comparison operations. This idea was further extended to include strings of characters, and we call this even-more-generic thing a quantity.
Bill has developed classes which implement the general notion of expressions: logical expressions, mathematical expressions, comparisons, et cetera. These expressions can be combined or segmented in various ways to generate other expressions, evaluated with respect to a set of values for the variables contained in the expressions, or simplified.
An associated directed graph is composed of nodes (places) connected by arcs (one-directional paths from one node to another). Data objects (structures containing additional information) can then be associated with individual nodes or arcs. An early implementation by Bill was converted by Chris to use the Standard Template Library. The associated directed graph is the foundation for some kinds of map layers, and is also the base class for the working memory class developed for assembling knowledge in response to a query.
Other areas have been the subject of extended speculation or brainstorming, but haven't made it into code yet. Details of our thoughts on these subjects can be found in the Notes.
Notes, scribbles, hand-drawn diagrams. It's all here for the brave and adventurous.
Divided into several folios for your downloading convenience.
| Folio 1 | June 1996 to May 1997 | Outline, Events, Spells |
| Folio 2 | June 1997 to July 1997 | Terrain, Map Display |
| Folio 3 | July 1997 to January 1998 | Barriers, Map Editor |
| Folio 4 | January 1998 to September 1998 | Thought and Memory |
| Folio 5 | October 1998 to November 1998 | Queries, Emotions |
| Folio 6 | November 1998 to December 1998 | Queries, Emotions, Paths |
| Folio 7 |
January 1999 to February 1999 |
Describing Paths |
| Folio 8 | February 1999 to March 1999 | Roads, Events, Entities, Semantic Catagorization |
| Folio 9 | March 1999 to May 1999 | Networks for Categorization & Language, Spreading Activation Recall |
| Folio 10 | May 1999 to July 1999 | Spreading Activation Recall, Game Engine Notes, Character Movement on the Map |
| Folio 11 | July 1999 to | Planning |
Not very exciting, but lays out the directory structure we agreed on for organizing the parts of the Destiny Project.
A hefty piece of work that documents the generic quantity class, its operators, types, and functions, as well as notes about the internal implementation.
This is Chris' original exploration of the notion of associative memory. Though parts of it seem naive to us now, it does introduce the concepts behind our associative memory model, the structure of the memory classes, and the kinds of knowledge that can be represented in the model.
Thought and Memory are the two ravens who sit on Odin's shoulders.
This document explains the concept of a working memory, where knowledge from an associative memory is gathered and linked together to answer a particular query or perform some task. It assumes one has already read "Thought and Memory".
The "Working Memory" document was written at a time when Chris was specifically working out a way to assemble knowledge with which to answer a conjunctive query (a question involving only "and" clauses, such as "What's black and white and read all over?"). Since that time, the knowledge assembly algorithm described in the document has been extensively modified to accomodate negations and disjunctions ("or"s and "not"s). A forthcoming document will explain the new algorithm, which involves constructing trees to represent the logical structure of the query. Particularly tricky was the adaptation of the cardinality-based priority scheme to ensure that processing remains efficient. Until that document appears, details can be found in Folio 6 of the Project Notebook.
These are really just a few notes we scribbled down to remind ourselves of things later. The casual visitor is likely to be disappointed at the lack of detail.
Some of the factors that make a game world seem more real.
A few definitions, along with notes on how we want to fit the concepts into the Destiny Project.
A simple game idea that Bill came up with a couple of years back. It is still invoked from time to time when either of us wants to bring the discussion back from abstruse theoretical realms into the game engine development realm.
Natural Language Grammatical Inference with Recurrent Neural Networks, Steve Lawrence, C. Lee Giles, Sandiway Fong, NEC Research Institute
Turing Machines are Recurrent Neural Networks, Heikki Hyötyniemi, Helsinki University of Technology
Emoticons: The Unofficial Smiley Dictionary (We had the notion that the relatively small set of commonly-used emoticons would represent those emotions that people most often wanted to convey during communication via a medium that offers few emotional cues.)
Boids, possibly the best starting point for information about flocking and other artificial life algorithms
Steven Woodcock writes an annual set of articles describing the use of AI in game development for Game Developer magazine (see Gamasutra, below) and hosts a site devoted to related topics and resources
John E. Laird hosts a game research web site
PC AI magazine has many AI resources, including research papers and sample applications
AAAI, the American Association for Artificial Intelligence, has many publications related to AI, but you must be a member to access their archive so the site is pretty useless for the merely curious
Gamasutra, Game Developer magazine's home site
FGN, the Future Games Network
Game Development Search Engine and home of Developer Quest eMagazine
Game Developer Net covers all aspects of game development