Overview of Ariadne's Thread

Taking its name from a Greg Egan novel, Permutation City is a free-source Quake 3 Arena mod which will serve as a cultural visualization tool. The tool will allow Permutation City users to:

• create their own avatar (design or choose their own skin for their character)
• walk around and explore (default will be 3rd-person mode)
• go into rooms that have artists performing -- with streaming audio
• pick up items related to the experience
• chat with other avatars
• discover secrets

In short, we see Q3A as a post-browser platform, and for its modification we'll use this list as our informal requirements.

First-iteration work products:

• project dictionary (7/28/2000)
• object model (7/22/2000)
• agent collaboration model (7/22/2000)
• system interface models (7/22/2000)
• object interaction graphs (linked in the project dictionary; 7/28/2000)

Development Methodology

We are also using this project to customize Fusion, an object-oriented development method well-suited to simulation work. A method helps to manage the complexity involved. We begin with the text, then add our experience in using it, and call it eFusion.

eFusion is divided into three parts: analysis, design, and implementation. There is no formal requirements phase. The initial requirements are submitted as a natural language document emphasizing what the system does. They do not have to be complete since our development process is iterative. Therefore, we have:

1. Analysis
   1. a specification of what the system does
   2. result: formalized requirements, verified to avoid errors (especially crucial at the early stage of development)
2. Design
   1. choosing how the system operations are performed by interacting objects (to satisfy the analysis)
   2. result: an object-oriented architecture of the system
3. Implementation
   1. coding, profiling, review (inspection and testing)
   2. result: a coded solution that satisfies the requirements

Fusion draws upon "formal methods" to check for completeness and consistency at the end of each phase: quality improves because testing is built-in.

eFusion thus provides a direct route from a requirements definition through to a programming language implementation. Its systematic approach not only provides the traditional benefits of a method but also enhances the strengths and shores up the weaknesses of object-oriented programming.

The objective is to develop a cultural visualization tool using the Q3A and RealPlayer SDKs. We have already gathered the initial requirements in the "what list" above. Now the challenge is to propose a solution in terms of an object-based model.

Brainstorming

The first step towards developing the model is to identify candidates for classes and relationships from the requirements. Class candidates are important nouns, and sources of relationships include verbs of action, communication, association, and containment. These are recorded in a project dictionary, a central repository of terms, concepts, and their definitions. The dictionary plays a central role in cross-checking the model for completeness and consistency, and it is updated throughout the process.

During this "brainstorming", it helps to consider the user interface and ask, What other requirements are needed to achieve the project's goals? A simple sketch may reveal some implied requirements.

Now we are ready to develop the object-based model. Just as an object has data and behavior, the system has structure and behavior; and this step in the Analysis phase reflects that:

1. brainstorming:
   1. begin project dictionary
   2. sketch GUI
2. develop the object-based model:
   1. describe system structure
   2. describe system behavior
3. check all models

System Structure

To describe system structure, we diagram object models, which are graphical representations of the classes and their relationships. They also show cardinalities (the numbers involved; "one" is assumed if none given), conditions (invariants and predicates), and attributes. However, the models do not show temporal order or data flow: they are not procedural; instead, the object models reflect the static structure of the information in the system.

(The object models should be inspected for mutual consistency and completeness against the requirements. But do not try to get them perfect now, for they will change as the analysis progresses. While there are definite steps, analysis is iterative and incremental because decisions are continually subject to review and revision as all the implications of the requirements become clear.)

System Behavior

With a working description of the system structure behind us, we are ready to describe its behavior. We use an agent collaboration model and a two-part system interface model to define the input-output communication of the system. This is not the internal messaging between objects; the focus here is on agents, active entities that communicate via events. (Note that agents should not be confused with objects, nor events with relationships.) The system itself is an agent, and the events it receives are system operations, which can change its state and cause the output of other events.

The system operations (input) and their events (output) comprise the interface of the system. The other agents comprise its environment; if these agents are not truly outside the system, the system does not interact with its environment and is a simulation. The system interface is also useful for dealing with concurrency, in which the agents are concurrent processes that need to have compatible interfaces.

To describe the system's behavior, identify agents from the requirements, and then collect what events (e.g, phrases describing what_action_is_desired) are involved and identify those which are system operations. All are entered in the project dictionary and shown in the agent collaboration model.

These findings are then used in the two parts of the system interface model: the operation model and the life-cycle model. The operation model characterizes the effect of each system operation: the state changes it causes and the output events it sends. It is expressed as a series of schemata, with each schema of the form:

Operation:	(name)
Description:	(text)
-------------------------------------------------
Reads:		(items)
Changes:	(items)
Sends:		(agents & events)
Assumes:	(pre-conditions)
Result:		(post-conditions)

The operation model uses the object model as a visual aid to its development. The emphasis is still on what the system operations do to the system. Therefore, the model does not specify the intermediate states of the system during the operation, for such states are dependent on the implementation details. There is no flow control. (The operation model represents how the events change the state of the system, represented by the object model.)

The second part of the system interface model is the life-cycle model. Its pseudocode groups the system operations and events and proposes a sequence for each "scenario" of agent collaboration. This will make it a useful guide for Implementation, which is more convenient when it is event-driven.

Checks

The final step in the Analysis phase is checking the models. They must be complete and consistent in order to be good enough for the Design phase. The text details three sets of exit criteria on p. 60:

1. completeness against requirements
2. simple consistency
3. semantic consistency

In summary, the Analysis phase of eFusion follows:

1. brainstorming:
   1. begin project dictionary
   2. sketch GUI
2. develop the object-based model:
   1. describe system structure:
      • object model(s)
   2. describe system behavior:
      • agent collaboration model
      • system interface models: operation model and life-cycle model
3. checks and balances:
   1. check all models according to exit criteria
   2. begin reviewing Pitfalls

This outline clarifies Fusion's approach and simplifies its steps toward describing system behavior. The work products of the phase formalize the requirements and specify what the system does. With the exit criteria met, the Design phase can begin.

The Design phase uses software structures to satisfy the abstractions from the Analysis -- objects and subsystems, their behaviors and relationships -- without diminishing the viability of the overall model. That is, we will have choices to make.

One choice already made for us is the implementation language: Visual C++. Although the language is often not chosen until the next phase, there are two advantages to knowing this now. First, we may be able to use language-specific features in order to model the system's behavior more fully. Second, we will have a better idea of what designs can or cannot be implemented easily in the language -- and make our choices accordingly.

Still, the Design influences the system's runtime structure more than does the language, which is largely just static code. The purpose of Design is to define how the system's functionality, largely captured in the operation model, is implemented -- while preserving the class descriptions and relationships captured in the object model.

In the Design phase, there are four types of models:

1. object interaction graphs depict the functional definition of system operations -- i.e, behavior;
2. visibility graphs show the class reference structures;
3. class descriptions are the header files that provide the foundation for Implementation;
4. inheritance graphs identify class commonalities.

During their development, the project dictionary and the other Analysis work products are updated and refined as needed.

Object Interaction Graphs

For each schema in the operation model (i.e, for each system operation), we construct an OIG. This is a graphical representation of the sequences of messages between design objects. It includes a natural language narrative. It also captures the skeletal structure of the algorithms that satisfy the operation model and enables experiments with alternative designs (such as choosing a different controller).

Development of OIGs involves four steps:

1. identify the relevant objects (start with the Reads, Changes, Sends clauses of the schema);
2. from these, determine the controller, which receives the request to invoke the system operation;
3. determine messages between objects -- decide how objects interact to carry out the system operation;
4. record these interactions on the OIG.

This is followed by refinement -- alternative designs and hierarchical method decomposition, which can reduce the complexity of an OIG: if an OIG is hard to draw, it will be too hard to code -- and checking.

First iteration: We have linked the OIGs to the project dictionary. We have postponed further Design until the next iteration in the development cycle. This is because we have the luxury of the SDK code: "Why talk in the abstract when we can talk in the concrete?" The OIGs in their present form will serve quite nicely as event-driven guidelines to learning and using the SDKs.

The Q3A mod source (1.29h) will serve as the initial code base. (There does not appear to be a GNU/gcc version at this time. However, thanks to the Q3A virtual machine, a mod developed on w98 will run on Mac and Linux -- unchanged.) The code is written with C structs and global functions which can be extended with C++ classes and methods.

Together provides a useful overview of the code. This modeler generates a UML class diagram -- a diagram of data structures and their relationships. The "whiteboard edition" is free (beer not speech) but doesn't have printing. It's a Java app, so it runs on several platforms -- and likes a lot of memory. The downside: the global functions do not appear on the diagram because Together expects C++ class methods instead. The upside: Together allows the developer to navigate the source code using a class tree or the diagram -- click on a class/struct "box" (or a variable), and its source code appears in the editor. Even better: change a struct or variable in the diagram, and the source code is automatically changed -- and vice versa.

The source includes Hello-World instructions for the Visual C++ IDE. The Standard Edition of VC++ is fine to start with -- and upgrading it to the Professional Edition is cheaper than buying the PE outright. Beginning Visual C++ 6 is a good introduction to both C++ and VC++.

The full-featured game itself is needed for mod testing. Mod development sites:

• The Backburner (how to add avatar types, console commands, and menu selections)
• Code3Arena (detailed tutorials)
• Q3 Center
• Quake Style
• Bot Building 101
• poison powerup
• console commands

(More details to follow. Continue reviewing Pitfalls in the meantime.)

News sites:

• Planet Quake
• Q3A (updates, such as Point Release 1.31)
• Blue's News (hardware details)
• GliNUx Quake Server Pages

Object-Oriented Development, The Fusion Method, Derek Coleman et al. (1994; ISBN: 0-13-338823-9)

Pitfalls of Object-Oriented Development, Bruce F. Webster (1995; ISBN: 1-55851-397-3)

Last modified: 5/25/2001