THE APPLICATION OF DIRECTED ACYCLIC GRAPHS TO FIRST GENERATION INTERACTIVE FICTION by Paul Munn Senior Project May 1994 Professor Parsons Professor Orr 1: INTRODUCTION 1.1 THE HISTORY AND DEFINITION OF INTERACTIVE FICTION In the time before the desktop (and now even palmtop computers) with graphical user interfaces and the popular point- and-click method of displaying dazzling graphics and digitized sound, computers were hulking, room-sized and then desk-sized brutes housed in large institutions such as the military and the wealthier universities. There they churned along, mulling over various scientific and miliary mathematical problems, their operators ferrying punched cards or paper tape from work desk to the computer room and back again. As the technology slowly became cheaper, more computers were being used at different locations. As more and more researchers at these varied locations began using computers, the need to exchange information between them grew. Around 1970 saw the development of ARPAnet (the Defense Department's network that would many years later become the now- world-sprawling and still-growing Internet) and multi-user telecomputing became a reality. Now, giant and expensive research computers used by a rich university or the government could be shared by users of other, less-powerful computers on that then-small network. Using a PDP-11 computer at the Massachusetts Institute of Technology, a group of young men known as the Dynamic Modelling Group created what may have been the first games playable on ARPAnet: Maze, then Trivia (a game made to test a database system they were using for a project). It was toward the end of this infancy of the computer revolution back in 1977 when the beginning of interactive fiction appeared on ARPAnet. The game was called Adventure, was written by William Crowther, "greatly expanded" by Don Woods before appearing on ARPAnet in early 1977, and then solved by late May. Adventure was the game that would be the basis of all interactive fiction to come. The form of the earliest interactive fiction (IF) is important to note. Early interactive fiction has been called many names: Computer Fantasy Simulations (CFS), Text Adventure Games (TAGs), and the current name for the type of game which Adventure was is interactive fiction. A physical universe of some kind is presented as the player's surroundings and all aspects of the universe -- what the player does, what it looks like, what is around the player -- are narrated to the player, narrated by what some have called "an omniscient "Master of the Dungeon," who rules on each proposed action and relates the consequences." The game revolves around solving puzzles and/or gaining treasures, all of which are set up by the authors. A part of the game program called a parser interpreted the typed commands. Adventure's parser could only understand a "verb noun" command structure such as OPEN BOOK, TAKE LOCKET or ATTACK MONSTER. Later parsers became more advanced. The Dynamic Modellers (Tim Anderson, Marc Blank, Dave Lebling, and Bruce Daniels) worked together on a way to build a better game and after two weeks had developed a game with several obstacles that could be played. From there, they worked nonstop adding to it and altering it until it became the massive program known as "Zork", named after "ZORK," the file name they always used to save their projects under before submitting them to the ARPAnet for wide use in its then-unprotected environment. Infocom was incorporated by several of the Dynamic Modellers in 1979 and later, seeing the success that similar adventures like Zork were having in the software market, the game Zork for its mainframe PDP-10 computer was split into 3 sections and modified to become Zork I, Zork II, and Zork III for personal computers, which appeared in the early 1980s. Infocom produced dozens of text adventure games in varied themes (fantasy, science fiction, mystery, and combinations of these) over its lifetime as an independent software publisher. These years of prolific publishing on Infocom's part, the early to mid 1980s, are referred to as the Golden Age of Interactive Fiction by IF aficionados and the games produced referred to as "First Generation" interactive fiction. The growing abilities of home computers and competition from home video game producers led Infocom, in late 1988, to start producing "illustrated" adventure games, many of them with menu systems to for "better interaction between the player and the computer." The graphical adventure trend has continued to the present day. With computers' graphical and information storage abilities becoming more and more sophisticated for less money, digitized pictures and sounds often accompany actions in present-day adventure games. Most adventure games produced today also have a menu-driven user interface giving the player all of the options up-front in the form of icons, graphical representations of actions and items the player holds. If you wish to use one item on another item, you use your mouse to point to and click on the icons of the action and the objects you wish to act upon. Strictly text-based adventure games are produced only by shareware and similarly independent authors today and there is little space for them in the personal computer software market. A handful of authoring systems exist for this purpose, most of which are script languages or fully functional programming languages permitting varying levels of sophistication. Even fewer shareware or freeware systems exist to produce graphical adventure games. Most games produced by these are simpler versions of the very popular sword-and-sorcery-style games which have become available for personal computers and home video game systems in recent years. 1.1.1 PLOT IN FIRST GENERATION INTERACTIVE FICTION First Generation interactive fiction have traditionally had fixed plots. In text adventure games, it is rare to have more than a couple of ways to accomplish tasks at hand. The game, once solved, has little replay value. The pathways are fixed. Clever authors have, however, made their plots intricate, laden with sub-plots and alternate pathways through the adventure. 1.2 FIRST GENERATION VERSUS SECOND GENERATION Active research is currently going on in another area of interactive fiction hoping to bring about what has been referred to as Second Generation Interactive Fiction. This research is aimed at creating what researchers call Interactive Fantasy, a type of environment created using "a combination of physical modeling, character modeling, and dramatic modeling." Physical modeling is like that of the first-generation IF: a physical universe with which the player may interact is simulated. New simulation research, for example, may focus on how to simulate laws of the physical universe, such as the ability to be able to cut a loaf of bread in half or having the computer recognize that boards lashed together with rope could be used as a raft. Character modeling research involves encoding motives and goals of non-player characters and how those characters will behave because of them. This research is concerned with automating the process of behavior choices to make the characters lifelike and less predictable. Lastly is dramatic modeling, closely related to plot modeling. Dramatic modeling efforts seek to make an interactive fiction story more like literature, possessing rising action, a climax, and relaxing of tension, and plot modeling is an attempt to break the interactive fiction's author's hold on what happens. Plot modeling efforts seek to represent plot as something other than plot branching, where there are dead ends and usually only one way to go through an interactive fiction experience, often one puzzle at a time. The goal of these methods is replayability and flexibility, something approaching the often-mentioned "holodeck" of Paramount's "Star Trek: The Next Generation" series, an area where scenarios are outlined by the user and a scenario of any type is made around him or her with artificially intelligent characters to interact with. Scenarios that the television show's characters have created in the "holodeck" have included battle training exercises, romantic encounters, fencing partners, study sessions with dead scientists, and a poker game with the great Western scientific minds. This paper's research primarily concerns itself with First Generation interactive fiction, text adventures in particular. 1.3 PLOT GRAPHS One way of organizing events in a work of First Generation interactive fiction is use of what is called a plot graph. Carnegie Mellon University, home to The Oz Project, perhaps the most concentrated attempt at interactive fantasy research, is spending some time on working out an effective method of interactive fiction plot representation. Traditional, fixed fictional plots are essentially one event after another with no way to deviate and with no way to get a different set of experiences. The most free-form interactive fiction has been an almost plotless structure involving a "browse-around" world model in which the player enters a virtual universe, manipulates the virtual objects, wanders around, and then exits when ready. A medium level of control and responsiveness is needed. One proposed plotting method for interactive fantasy involves using what Oz researchers refer to as a plot graph. Plot graphs are composed of nodes which are major events and situations and the edges between them, which are, on paper, usually labelled with hints as to how the participant can go from the source node to the destination node. These paths never return to a node twice but may have more than one edge leading away from itself, signifying a divergence in plot path. There are few rules regarding the plot graph. Only when all edges leading into a node have been followed can that node's scene be found. This requires that all events behind those edges leading to the current node must be carried out before that node's events can be carried out. The plot graph is usually drawn so that action proceeds in a left to right manner. A simple illustration of one is below. (A) -> (B) --->_. (ENDING 1) / _. /| START /| / \ / / (C) ----> (D) --> (ENDING 2) This plot graph model allows an author to dictate a general (but not strict) order the scenes will be run. 2: DIRECTED ACYCLIC GRAPHS AND PLOT GRAPHING 2.1 WHAT IS A DIRECTED ACYCLIC GRAPH (DAG)? Implementation of a plot graph in a computer is most easily accomplished using directed acyclic graphs, called DAGs for short. These mathematical structures are exactly what their name says they are. As a graph, they have nodes (usually symbolized by circles or a different but constant geometric form) and edges (lines) leading from one node to another. These lines are labeled to reflect their directed nature, which is to say that an edge can only be traveled in one direction. These graphs are acyclic in that they do not form cycles, which is to say that a node is never returned to by later nodes. A node is therefore never revisited. 2.2 WHAT IS A PLOT DAG? Simply put, a plot DAG is the use of a DAG to implement a plot graph. From the above information, it is easy to see how this is done. Plot DAGs come in two forms, much like Finite State Machines do (a related graph theory construct): the transition-assigned machine, also called a Mealy Machine, because information is output when passing along the edges (in transition) to a new state, and the state-assigned machine, also known as a Moore Machine, in which output is tied to the state. (It is important to note that for every transition-assigned machine, there is an equivalent state-assigned machine.) A plot graph can be made using either of these forms. 2.3 STRUCTURE OF THE CHOSEN MODEL The form I have chosen for the code accompanying this paper is a transition-assigned machine. The nodes or states are places where the exit edges are checked. If the conditions for exit along a particular edge are met, the exiting actions code on that edge is executed and the new node is traveled to, revealing a new set of possible conditions. In this way, states lend themselves to being descriptions of the game state. The choice for a transition-assigned machine was made partly for convenience. It is important to note that the method for transforming a transition-assigned machine to a state-assigned machine involves the creation of more states, something which in almost any programming language implementation requires more data elements and more memory consumption. Also, I felt the transitional model lent itself to the mental formulation of plot models by other authors who will eventually use the system when it is released to the text-adventure programming community. For the most part, the choice was based on personal preference in the area of plot graph conceptualization. 3: TADS AND OBJECT-ORIENTED PROGRAMMING Mike Roberts' TADS (Text Adventure Development System) language version 2.1 was chosen to be the implementation language because of the author's familiarity with it and because it is an object-oriented programming language. It is a full programming language with its own compiler and C-like syntax. Roberts' TADS manual deftly explains the OO paradigm. What is this "new perspective" of object-oriented programming? Basically, it is the view that one takes of data. In a traditional language, you write a series of procedural steps that are applied to a collection of data; code and data are firmly separated. In object- oriented programming, on the other hand, you partition a problem into a set of entities, called objects; each object contains both the data and code that describes its state and behavior. In a simulation, an object in the program usually corresponds directly to an object being modelled. Objects are instances of a general form, called a class. Object-oriented programming consists for the most part of writing classes. Once the class is finished, making instances of it is very easy. You apply the instance to your individual name by overriding certain attributes of the class with new ones that apply to that class alone. For example, in TADS, there is an item class which, among other things, allows its short description to show up in a room description and a long description to be triggered when the player looks at that item (by calling it by the name the author gives it). By instantiating that class into objects, you inherit the properties of that "parent" class, requiring you only to program the changes from the parent class. In our example, this might be setting its short description to "a book", its long description to "This book has FINITE STATE MACHINES written on its spine.", and its location to some other object in your game you have already declared as being derived from the room class. You then would set its noun attribute to 'book' to give the parser something to let the player refer to your book as. The TADS language supports class and object creation and its run-time system permits their interactions. 3.1 TADS AND C: A COMPARISON In terms of syntax, TADS and the ANSI C language are very close. Groupings of code are enclosed in braces and the major looping statements such as for statements and do-while statements are supported. Statements end with a semicolon. The traditional C commenting method of a slash-asterisk (/*) opening a comment and an asterisk-slash (*/) closing a comment are supported for multiline comments. There are a number of differences between TADS and C. The double-slash commenting style for single-line comments familiar to C++ programmers is supported. Assignments are carried out using the Pascal-like colon-equals (:=) symbol and equality is symbolized by a single equals sign (=). Also, any information enclosed in quotation marks will be displayed on the screen when evaluated, eliminating the printf() function and reducing typing for the many lines of description that are often needed in text adventures. In TADS, information not enclosed in braces are called properties. A property that is code (enclosed in braces) is called a method. The author refers to data items - property or method - as attributes. The most significant syntactical difference between the two languages, apart from TADS being an object-oriented language, lies in the use of local variables within methods. In a C compiler, static type checking occurs, meaning, for example, that the variables being passed to functions are checked to see if they are of the correct data type that function requires and that every assignment statement is assigning the proper type of value to the declared data type. In TADS, dynamic type checking occurs, which is to say that assignments and passing of data items to functions is verified at run-time, allowing any data to be sent from one object to another. In TADS, local variables are declared before commands are issued using the "local" keyword. That keyword is the only signal that those are variables specific to that method. No data typing occurs at that time. Data typing is done by assignment statements. The first assignment statement that variable is used in sets that variable's function. Information that can be assigned to an identifier include integers (height := 20;), strings (name := 'Harold';), and lists, which are collections of any data types, though they are almost always used as collections of a single data type (list1 := [0 3 45 75];). Lists are indexed by using brackets and items are numbered from 1 upwards (list1[1] would return the first item in the list). Floating point numbers are not permitted in TADS. The object-oriented nature of TADS has given rise to support for a few other items. TADS supports daemons, which are functions that, once triggered, run every turn until stopped. Fuses, instructions which trigger a certain function after a specified number of turns pass, are also supported. 3.2 HOW TADS WAS USED TO IMPLEMENT THE PLOT DAG The author first wrote a general state class consisting of several data elements (properties) and a single function (method) that references and manipulates those elements (and elements of a special object called "global", used to hold data items that generally do not fit anywhere else) as needed. By instantiating this class, the author created plot DAG nodes for an example game, the TADS plot dag of which is listed in Appendix B. Another component of the TADS language which made plot DAG traversal possible is the daemon. The plotDagDaemon created in the PLOTDAG.T module oversees the traversal of the plot DAG by checking appropriate conditions each turn. This is gone into in more detail in the next section. 4: ANALYSIS OF THE PLOTDAG.T MODULE'S RUN-TIME ACTIVITY We will be viewing pieces of the TADS code in PLOTDAG.T, the plot DAG module listed in Appendix A, as we move along our analysis. #include #include The first statements we see are "#include" statements. These operate identically to the C #include preprocessor directive. The ADV.T file is packaged with TADS and contains the base classes for most adventure items along with the verbs used to manipulate them. The PDSTD.T is a slightly-modified version of the STD.T (standard.t) file also packaged with TADS to set up the daemons and other functions required to run the plot DAG module. The STD.T file is meant to be altered by each author to suit his or her adventure's needs. The ADV.T file is not can be just as easily altered but is usually left alone or manipulated with the modify or replace keywords, which we will see shortly. replace preinit: function { The next item we see is preinit(). You will notice that the keyword replace appears in front of it. This keyword tells the compiler to replace the previously-included version of preinit() with this one. This version of preinit happens to have the original code of the other preinit along with more code. Preinit() is run after successful compilation of the TADS source code but before the binary file is written to secondary storage. Preinit() is very useful to create special lists of items and do other computations before the player ever runs the game to minimize the amount of time the player must spend waiting before the first lines of a description appear. (As TADS does not support dynamic memory allocation in the game, no new objects of any class can be created which was not defined before game play began. As a result, this function can do all of the setup required excepting starting daemons and fuses.) local o,p,q,r; /* These are local variables that are dynamically type-defined. That is, their type can be changed simply by making an assignment statement of a variable of a different type to it. */ // list of lightsources (from ccr-std.t) /* This routine makes a list of objects that are of the class light source. In our sample adventure, DAGE1.T there are no light sources. It is assumed that there is light available. Or that the player has night vision. It is included here to minimize code writing in the future. */ global.lamplist := []; o := firstobj(lightsource); while (o <> nil) { global.lamplist := global.lamplist + o; o := nextobj(o, lightsource); } The local variables for the function are defined by the local keyword. As discussed above, these variables can be set any way desired during the function they are used in. The next loop generates a list of light sources. The firstobj() and nextobj() functions return the first object and next object of a certain class out of all of the objects in the game. // list of states /* These statements develop the list of states stored in the global "catch-all" object. */ global.states := []; o := firstobj(state); while (o <> nil) { global.states := global.states + o; o := nextobj(o, state); } The second loop puts a list of all of the states in the DAG as a property in the global object. This list of objects is used by the plot DAG module's check_paths list. // set each state's parents_max. // set each state's done_actions to all zeroes. /* These statements initialize some of the state's necessary values. It automates the setting of parents_max values for each set by analyzing the structure of the given DAG, freeing the programmer from having to worry about it. */ o := length(global.states); for(p := o; p >= 1; --p) //For all states. { /* Initialize the values for this state before filling them in. */ global.states[p].done_actions := []; global.states[p].parents_cur := 0; global.states[p].parents_max := 0; q := length(global.states[p].child); //Num of children. for(r := 1; r <= q; ++r) //For all child states { global.states[p].child[r].parents_max := global.states[p].child[r].parents_max + 1; global.states[p].done_actions := global.states[p].done_actions + 0; } } This routine moves through the list of states from last to first just established (end nodes of the DAG to the start node) and sets starting values in the DAG. If the list were traversed in forward order, the children of the states already passed through would have values reset. Each state has a set of integers, done_actions composed of the same number of zeroes as there are children (members of the child property list). Each of those children has its parents_max(imum), its property holding the integer number of parents it has (to be compared with parents_cur(rent) as the game progresses), incremented. This way, the programmer need not do the counting. The module does it for him/her. The parents_cur property holds the integer counter of how many parent edges leading to the node have been satisfied. Only when this property is equal to the parents_max can the exit conditions for each exit edge be evaluated. /* Initialize the removal list, reset each time it is emptied. Every turn the daemon executes, any states that have had all exit paths taken no longer need to be checked, so they are placed on this list and deleted after the turn. */ global.states[1].remove_list := []; // Load first state on ns_list. /* The ns_list, which stands for next state list, will hold the current states on the "frontier" of the DAG. That is, these states are the only ones that need to be checked for progress across the DAG. */ global.states[1].ns_list := []; global.states[1].ns_list := global.states[1].ns_list + global.states[1]; The remove_list is used to in the check_paths member method of the state class. The remove_list is initialized to an empty list (denoted by the empty brackets) and is added to after each run-though of the "frontier" of states, which are on next-state list (abbreviated as ns_list) property of the global object. The "frontier" is the set of states that have unmet edge conditions that must be checked every turn by the daemon (which we will see next). At this point, preinit() is finished. /* Sets global.debug_dag to true, referenced by the daemon and the check_paths method of each state. When true, the daemon and check_paths methods display very detailed information about their runs between turns. */ modify global debug_dag = true ; This section of code simply sets the debug_dag property of the global object to the boolean-style logical value of true. This is simply a flag used by several if statements in the module to determine whether verbose debugging messages about the status of the process should be displayed. It is set to true here to aid the users and observers. /* This function was written out of a need to display the states in a list of them repeatedly. This is used by the debugging messages allowed by setting global.debug_dag to true */ dumpStates: function(list) { local a,b; a := length(list); for(b := 1; b <= a; ++b) "<>\ "; } This is used by two of the module's parts, the check_paths method in the state class and the daemon which we will examine next, only when global.debug_dag is set to true. It simply displays the sdesc property of each state, which is a short, one- word description of the state used for this purpose and other debugging purposes only. // The PlotDagDaemon plotDagDaemon: function(parm) { local g,h,i,j,addOk; // variables local to this function g := global.debug_dag; //The debugging flag... This gives us no surprises. These are local variables and a simple assignment of a long-named variable, the debugging flag, to a short local variable. This was done, obviously, to reduce the amount of typing needed. /* These statements go through the ns_list. Note that we do not assign the length to a variable and then use that fixed length as our watch criterion. It is important that we have length(ns_list) re-evaluated for each iteration of the loop as the ns_list[i].check_paths may add items to that list during the loop's iterations. */ for(i := 1; i <= length(global.states[1].ns_list); ++i) This for loop will go through the entire "frontier" of the DAG. It is important to note the reasoning behind the use of the TADS function length(), which returns the number of values within the list, within the loop instead of assigning the length of the list to a local variable and using that. Along this analysis, if the player has satisfied a condition attached to an exit edge, a new state will be added on the end of this frontier. It is therefore important that the new edge be considered for analysis this turn. That is why the length is recalculated after each iteration of the loop. { // This is one of the debugging messages. if(g) "\n#DAEMON# Checking state \"<>\"..."; Here we have the first of many debugging messages we will see in the coming code. This simply outputs the short description property attached to the state being examined. As mentioned earlier, the short description property is set by the game author for each state when the states of the DAG are written. The "#DAEMON#" is included to tell the viewer that the daemon is producing this output, not the normal game. /* We have check_paths return a boolean (true or nil) value that will tell us if the state must be removed from the ns_list (if all of its ways out have been done). */ if(global.states[1].ns_list[i].check_paths(i)) This if appears to be rather complicated. The first part of it, global.states[1], returns the first element of the list contained in global.states. This element has a property called ns_list. This if is telling the computer to trigger the check_paths method contained in the i-th element of the ns_list property of the first element in the global.states list. This kind of nesting and evaluation is handled without complaint from the TADS compiler. This check_paths method, we will see later, returns a logical value. If this value is true, it is the signal that we should remove this state (global.states[1].ns_list[i]) from the frontier. We will see that this only happens when all of the children of a node have been called and no more evaluation of the state is useful. { // Add to the remove_list global.states[1].remove_list += global. states[1].ns_list[i]; if(g) "\n#DAEMON# All done_actions finished. State will be deleted from ns_list."; } else if(g) "\n#DAEMON# All done_actions not done. Keep it on ns_list."; if(g) "\n#DAEMON# Finished checking state \"<>\"."; } The first assignment statement is in the short-notation C vein. It adds the finished state to the list of states to be removed. Either way, the appropriate debugging messages are displayed. Once the loop is done checking if states should be removed from the frontier, the appropriate debugging message is shown. /* Now remove all items in remove_list from the ns_list */ if(length(global.states[1].remove_list) <> 0) We only remove states from the remove_list (stored along with the ns_list property in the first state in the global.states list) if there is anything in it to remove. { if(g) { "\n#DAEMON# Removing done states from the ns_list."; "\n#DAEMON# ns_list: "; dumpStates(global.states[1].ns_list); "\n#DAEMON# remove_list: "; dumpStates(global.states[1].remove_list); } These are debugging messages utilizing dumpStates(), shown above. h := length(global.states[1].remove_list); for(i := 1; i <= h; ++i) global.states[1].ns_list -= global. states[1].remove_list[i]; //Clean out remove list for next deletion go. global.states[1].remove_list := []; if(g) { "\n#DAEMON# after removal..."; "\n#DAEMON# ns_list: "; dumpStates(global.states[1].ns_list); } }// end if anything in remove_list else if(g) "\n#DAEMON# Nothing in remove_list to remove."; We use the C-like "-=" operator as we used the "+=" before and remove every item in the remove_item property from the ns_list property and then clear out remove_item. The debugging messages show the results of these statements. /* Now that we're done removing things, we should process the ns_list so there are no doubles. We don't prevent doubles during the above loop as new conditions may prompt review of the same state again in the turn. */ global.states[1].temp := global.states[1].ns_list; global.states[1].temp := []; //Load first state of ns_list onto temporary list. global.states[1].temp += global.states[1].ns_list[1]; if(g) { "\n#DAEMON# Compacting ns_list to remove duplicates..."; "\n#DAEMON# ns_list before: "; dumpStates(global.states[1].ns_list); } This phase of the daemon is an important one. After the whole frontier has been processed, it is possible that two states have had the same state placed on the frontier. Had we put a safeguard in the previous processing loop to keep a state from placing a state on the list after it had already been looked at earlier, a state could never be placed on the frontier again (to be reconsidered) after a change in events during the process of checking each state for an update -- something that results in a delayed reaction processing of that state. Once the frontier has been checked, however, all duplicates should be removed to reduce redundant processing for the next time around. h := length(global.states[1].ns_list); /* We're looking at the 2nd to the end of the ns_list to see if we'll add it on. */ for(i := 2; i <= h; ++i) { /* If next state is already in temp, don't add it */ addOk := true; for(j := 1; j <= length(global.states[1]. temp); ++j) // Check thru temp { if(global.states[1].ns_list[i] = global.states[1].temp[j]) { addOk := nil; break; } } if(addOk) //We add it on to temp. { global.states[1].temp += global.states[1].ns_list[i]; } } /* At this point, temp is the next interation's ns_list. Make it so. */ global.states[1].ns_list := global.states[1].temp; if(g) { "\n#DAEMON# ns_list after: "; dumpStates(global.states[1].ns_list); } } The method of compacting the ns_list is to create a temporary list, place non-repeating states in that temporary list, then put the temporary list in place of the frontier, ns_list. The daemon's execution is then finished for the turn. Our attention next turns to the state class itself, with a focus first on the properties of that state and then the "workhorse" method within the state, the all-important check_paths method. /* The definition of the state class */ class state: object /* The notation "Reset by author" means the default values set by this class definition must be reset by the author of the states for each game. "Set by preinit" signifies that the preinit method, defined above, will take care of scanning through the DAG at compile time and making the appropriate calculations. */ noun = 'staten' sdesc = "staten" /* The states are given a noun and a ShortDESCription to allow their use with the new verb, STATE, detailed later on. For a player to get information on the plot DAG's specific state, he/she need only type STATE to get that information. This new STATE verb would be commented out of use when an adventure works fine. For this test program, however, the verb is kept. Reset by author. */ It is important to note the difference between the assignment operator := and the = sign used here. In TADS, a property assignment outside of a method uses an equals sign, while an assignment of value within a method uses the colon- equals sign assignment operator. The above code does not generate an error. These values are default values, which will be reset by the author to distinct values for each state. The short description is used in the debugging messages while the noun property is used by the new verb which is later introduced, the state verb. This verb, we will see, will take a single noun as its direct object and return information on that noun's state. child_conditions = [] /* A list of pointers to methods in the state the author defines. These child conditions will only be evaluated for a state if all of the edges leading to it have been traveled. Each method will return a value of true or nil when called. If this value is true, the check_paths may move to the child of that same edge. Reset by author. */ The child_conditions property is a list of pointers to methods within the object (as this is the way in TADS to reference individual methods within objects). The first pointer points to the conditions for passage to the first child, the second pointer in the list points to the conditions for passage to the second child, and so on. A pointer to a method is denoted by the method name with an ampersand (&) in front of it, a traditional C pointer notation. These methods are not meant to deliver messages to the player but must simply return a true or nil logical value corresponding to whether its conditions have been met. The example plot DAG-using adventure's states, displayed in Appendix B, show this in detail. These conditions are only evaluated to see if they are true or nil if and only if all of the edges leading to a node have been satisfied. This supports the main theme of the plot graph, which is forbidding a player from not completing the entire game. child_actions = [] /* A list of pointers to methods in the state the author defines. Upon travel to the new state child[i], child_actions[i] is executed, causing a set of actions to be taken. */ This is also a list of pointers to methods and like the child_conditions list, its members correspond one-to-one with the children. The first actions method corresponds to the first state, the second to the second state, and so on. These actions are carried out only if the conditions for the child have been satisfied. done_actions = [] /* A list of integers, initialized by the preinit function to zeros. When child_actions[i] are executed, done_actions[i] is set to 1. This tells check_paths that we can skip evaluation of this path and possibly add its child to the current traversal of the plot DAG. It is also used to determine if the state has had all children traveled to so it can now be removed from the ns_list (as it's no longer a frontier node). */ We have seen this list of integers before. It was initialized in preinit(). Like the previous two lists, this list corresponds to each state in the child property (shown next). Once the actions have been done on the way to that child, the corresponding integer is set from zero to one, indicating that the set of conditions for that child need not be evaluated any longer. child = [] /* A list of identifiers of the child state objects. These are not pointers to methods but actual object names. Once all criteria for moving to the state is satisfied, this identifier is loaded on the ns_list (stored in the first state) by check_paths (if, we'll find later, it's not already later on the list). Set by author. */ You will notice that the child list is not made up of pointers to methods but of the objects which are the child states themselves. The child state is added to the frontier for consideration if and only if its conditions are satisfied. Conditions are only considered if all of the edges leading to it have been traversed. parents_cur = 0 /* This integer is the total number of parent nodes that have allowed entry to this node at this point in time. Set by preinit. */ parents_max = 0 /* This integer is the total number of parents of this node. When parents_cur = parents_max, this node can be exited. Set by preinit. */ These items the comments explain, are set by preinit(). We have already reviewed that process. They are merely set here to remind the programmer that they exist. /* The following method checks the paths of this state and updates its status. */ check_paths(place) = { local g,i,j,k,l,wantAdd,m; //local variables. g := global.debug_dag; //The debug variable. The first thing one notices is that this method is having a variable passed into it, a local variable it calls place. This is the integer place in the ns_list that this state is in. You will see this used later on in the analysis needed to decide if a child should or should not be added on to the ns_list. These are familiar statements setting aside local variables and saving typing by assigning the debugging flag value to g. /* We can evaluate child_conditions to try and leave this state only when ALL of the edges TO the node have been traveled. */ if(self.parents_cur = self.parents_max) This is the check to see if we can consider leaving this state. If all edges leading to this node are satisfied, we can examine the child_conditions to expand the frontier. { if(g) { "\n#CP# We can leave: all edges to this state are satisfied."; } j := length(self.child_conditions); //Num of ways out of state. if(g) { "\n#CP# State \"<>\" has \ <> child-conditions."; } for(i := 1; i <= j; ++i) //For all ways out: { At this point, it has been determined that all parent edges to this node have been satisfied. This for loop is going to examine all of the possible exit edges from the current state. Expansion of the frontier, that is, the addition of child states to the ns_list, is voted for in the form of the wantAdd logical variable. We also only consider the exit conditions if we haven't exited that way before, that is, if its corresponding don_actions integer is zero. If we find the exit conditions are true, wantAdd is assigned the value true and we will only add the node if it isn't already later on the ns_list. The "#CP#" in front of the debugging statements exists to tell the viewer that these debugging messages are being produced within the individual state's check_paths method. /* The default is that we do NOT want to add the child on to ns_list yet. */ wantAdd := nil; if(g) "\n#CP# Examining edge <>..."; if(self.done_actions[i] = 0) /* If actions haven't been done yet. */ { if(g) "\n#CP# checking conditions..."; if(self.(self.child_conditions[i])) In the process of evaluating this if statement, the method the i-th child_conditions pointer is pointing to is triggered and evaluated, returning true or nil. If true, the conditions are met and we can move on to the i-th child node. // child conditions satisfied? { if(g) "\n#CP# **CONDITIONS NOW SATISFIED!**"; if(g) "\n#CP# Executing edge exit actions..."; //This executes exit actions. self.(self.child_actions[i]); This last statement is functionally similar to the one enclosed in the if just discussed. Since the conditions are met, this one triggers the actions method for the i-th edge being examined. /* Show we're traveling out this edge by setting its corresponding done_actions entry to 1. */ self.done_actions[i] := 1; //Add 1 to child node's p_cur. self.child[i].parents_cur := self.child[i].parents_cur + 1; if(g) "\n#CP# ...finished executing edge exit actions"; // We want to add child on... wantAdd := true; } Setting the i-th done_actions to one indicates that this way has been traveled and its conditions should not be considered the next time around. We also add one to the child's parents_cur property to indicate that this parent edge has been satisfied. else if(g and self.(self. child_conditions[i]) = nil) "\n#CP# conditions not satisfied."; } else { /* We DON'T want to add this child on the ns_list as it was added on earlier. */ if(g) "\n#CP# Actions done already. Skip conditions check. Don't add on again."; } The first else applies to the if asking if the conditions are met. The second else asks if this edge's actions have been done. If they have been done, we don't want to check its conditions or add it. This next segment of code determines if we should add the nominated state onto the frontier to be evaluated. The conditions that could hold us back from doing this are 1) have we nominated the child of the edge being examined (this is a simple one dependent on the wantAdd variable we have already set as desired); 2) if it is already later on the list, we do not want to add it as it will lead to redundant processing and, if a grouping of repetitive states occurred (a cycle in our supposedly-acyclic plot graph), an infinite loop may occur; and 3) if the state to be added happens to be the current state, which would cause an infinite loop. /************************************** * Check if we 1) want to add on * * 2) should add on only if it* * is not already on list. * **************************************/ if(wantAdd) { /* Only put child on ns_list if it is not current state and not later on list. */ if(g) "\n#CP# Can we add child \"<< self.child[i].sdesc>>\" to list?"; k := length(global.states[1].ns_list); if(place < k) /* Not currently at end of list. */ { m := true; //default not add if(g) "\n#CP# ?-currently at item <> out of <>."; /* This not only prevents adding a state existing later on on the list but also prevents a state from adding itself and entering an infinite loop. l = place to start, not place + 1. */ for(l := place; l <= k; l++) { The loop starts at the place that is passed to check_paths and will check it up to the end. The variable m, defined above it, will be a flag as to whether or not we will add this candidate state to the frontier. if(global.states[1].ns_list[l] = self.child[i]) { m := nil; if(g) "\n#CP# ?-found at place <>."; break; } else if(g) "\n#CP# ?-not found at place <>..."; } // end for This loop will abort and m will be set to nil if the candidate state is found at the current or a later spot in the ns_list. else // we're at end of list { /* We are at list's end so we should add this new state on to be processed ONLY if it is not the current one.*/ if(g) "\n#CP# ?-We're at end of list..."; if(self.child[i] = global. states[1].ns_list[place]) { m := nil; if(g) "\n#CP# ?-Can't add itself to list."; } else m := true; } There is a section of code that is never used here, as analysis of the very end of the logged output will show. The check as to whether a state will add itself is never true. In preinit(), a node attempting to add itself will incur the expected penalty of having itself become another parent counted in the parents_max integer. The only way this parent edge can be satisfied is for the frontier to travel from the parent to the child, but the only way out of any state is if all of its parent edges are satisfied. This makes a state with itself as its own child impassible and an easy way to make a dead-end to a game. A state with itself as a child can never be left. Therefore, m will be assigned the true value. if(m) { global.states[1].ns_list := global.states[1].ns_list + self.child[i]; if(g) "\n#CP# Yes, child \"<>\" added to ns_list."; } else if(g) "\n#CP# No, child \"<>\" not added. It is already later on list."; } //end if wantAdd } //end for i } //end if parents_cur = parents_max else { if(g) "\n#CP# Can't leave state: all edges to it are not satisfied."; return(nil); } Here, depending upon m, we either add the child to the frontier list or we do not and an appropriate debugging message is displayed. If it happens that all edges from parents are not satisfied, it is apparent that no children of a state have been traveled to and that the state should stay on the frontier list to be evaluated next turn. We give the appropriate debug message and we immediately leave check_paths and return to the daemon with a nil, sending the message that the state should not be removed from the frontier. /* Return true if all done_actions have been done. */ for(i := 1; i <= j; ++i) if(self.done_actions[i] = 0) return(nil); //All done_actions not done. //All done_actions done. return(true); } //end check_paths The for loop does an analysis to see if all of the children have been traveled to and whether or not this node should be removed from the frontier and signals the daemon as necessary. /* Adjustments for the STATE verb. */ verDoState( actor ) = {} /* verify-direct-object-of-State's blank entry indicates that this state can be a direct object of the STATE verb. */ The verDoState method indicates that this class is able to be used as a direct object of the state verb, which will be described just after the definition of this class is completed. If this method were to return anything, this would not be a valid direct object for that verb. doState( actor ) = /* What to do when the state is a direct object of the STATE verb. */ { local i,j; j := length(self.done_actions); "\bStatus of the <> done_actions of state \"<>\" is: "; for(i := 1; i <= j; ++i) "<>"; j := length(self.child_conditions); "\nThere are <> conditions and they return:"; for(i := 1; i <= j; ++i) { switch(self.(self.child_conditions[i])) { case nil: "\nFALSE"; break; case true: "\nTRUE"; break; default: "\nNot False or True?!"; } } "\nParents_cur = <>, parents_max = <>"; } //end of doState ; //end of state definition The method executed when the object of this class is a direct object of the state verb displays information about the current status of the state object. The done_actions list, the evaluation of each method in the child_conditions list, along with the parents_cur and parents_max integers are displayed as an aid to debugging. /* Add On Verbs: state Display the status of its done_actions array. */ stateVerb: sysverb /* System verb status allows it to be executed without time passing. No real effect on the game. */ verb = 'state' sdesc = "state" doAction = 'State' validDo( actor, obj, seqno ) = { return( true ); } validDoList( actor, prep, dobj ) = { return( true ); } ; //END OF PLOTDAG.T MODULE These statements define the state verb in the TADS language and give it the abilities of a standard TADS verb. This verb is used primarily for debugging purposes, to get a look inside what is going on in the game's plot DAG. There are ways that the data items in the state class could have been merged. In TADS, lists can hold items of different types. We could have merged that child_conditions, child_actions, child, and done_actions lists into one list and used integers as indexes to them, but that would have made it much easier for the programmer to make an error when writing a state. This module was designed for ease of use and a minimum of work on the part of the programmer. 4: THE SAMPLE GAME A simple game has been written to illustrate the use of the PLOTDAG.T module. The states for use in the game are in Appendix B. Through the #include statements at the head of the file, the game brings in the PLOTDAG.T module and the rooms and items that are used in the adventure. The rooms and items are shown in Appendix C. The adventure is just large enough to test the major abilities of the PLOTDAG.T software. There are three rooms known as the alcove, the cave, and the corridor. The alcove is west of the cave and the corridor is south of the cave. Their object names in the game are startroom (the required name for the TADS starting room), cave1, and corridor1. The item objects in the game are a rubber ball (rubberball), a note (note1), a green cube (greencube), a plaque on the cave wall (plaquething), and a blue switch in the cave (caveswitch). The player, to complete this senseless adventure, must do a number of things, all of which are detailed on the plaque in the cave. She must take the ball (which will result in the cube appearing on the spot), flip the cave switch (which will result in the note appearing), put the cube in the alcove (which will result in displaying a congratulatory message), put the note in the corridor (which will give another congratulatory message), and lastly, bring the note, cube, and ball to the alcove to receive a final congratulatory message. The game DAG looks like this: (2) / \ / \ / \ / \ (1) (4) -----> (5) \ / \ / \ / \ / (3) State 1's edge leading to state 2 requires that the ball be in the player's possession. Once that happens, the cube appears. State 1's edge leading to state 3 requires that the switch be turned on and results in the note appearing. State 2's only exit edge requires putting the cube in the alcove and a message is shown. State 3's only exit edge requires the note be put in the corridor and gives another message. State 4's only exit edge requires the player be in the alcove with all of the items and shows a congratulatory message. State 5 has no exit edges. The 2 edges off of state 1 provide a test of examining multiple exits and the multiple edges entering state 4 provide a test of the parents_cur = parents_max check. We will look at the first and fourth states to get an idea of an example DAG. state1: state noun = 'state1' sdesc = "state1" child = [state2 state3] child_conditions = [&cond1 &cond2] child_actions = [&act1 &act2] cond1 = { return(rubberball.location = Me and Me.location = corridor1); //Returns a boolean-style value of true or nil. } cond2 = { return(Me.location = cave1 and caveswitch.isActive = true); } act1 = { greencube.moveInto(Me.location); "\bThe rubber ball glows red for a moment and you hear a soft popping noise. At your feet you see a small green cube."; } act2 = { note1.moveInto(Me.location); "\nYou hear a grinding sound and look up to see a small hole open in the cave ceiling. A small slip of paper floats down from it and lands on the gravel in front of you."; } ; State 1 is an instance of the state class. Since it is declared as being of class state, it inherits all of its base class' properties and methods. Any property or method defined here is either added on or replaces the parent property of the same name. State 1 has its distinctive noun and short description set, along with the lists of conditions and actions. After those lists, the author is required to write the methods to carry out the condition checking and the methods to carry out the actions that need to be done. The conditions methods, c1 and c2 are simply a logical evaluation of these conditions. This is the easiest way of doing such an evaluation. It could be done with a chain of if statements but would have taken many more lines. The actions, however, can be anything the programmer desires. Notice that each of these triggers the moveInto method that is inherited by every object of class item to do the necessary work. The item class is defined in the ADV.T file. The rest of each of them are simple screen output. state4:state noun = 'state4' sdesc = "state4" child = [state5] child_conditions = [&c1] child_actions = [&a1] c1 = { return(greencube.location = Me and note1.location = Me and rubberball.location = Me and Me.location = startroom); } a1 = { "\bYAY!"; } ; State 4 shows no difference from state 1 in the area of providing for parents. Its exit edge's condition is that all items are held by the player and the player is in the alcove. Its exit edge's action is to simply print "YAY" and move on to the child, which happens to be state 5. These states demonstrate the simplicity of using the PLOTDAG.T module to organize fixed plot in first generation interactive fiction. The log of the full run-through of the game is available in Appendix E. 5: PROBLEMS AND POSSIBLE IMPROVEMENTS 5.1 DRAWBACKS OF THE PLOTDAG.T CODE One of the chief speed drawbacks to the code is the large number of comparisons made by the if statements checking the debug_dag variable. On a fast machine, these become trivial, but removing them for a slow machine may make debugging problematic if the author decides to later enhance the plot of the game. Another drawback could surface if a large frontier set occurs during a turn, possibly caused by a wide number of waiting conditions that might happen with simultaneous puzzles. This may cause processing time to become noticeable. 5.2 WHY NOT AN ACTOR CLASS RUN BY ITS OWN DAG? An early formulation of this project aimed to organize actor behavior by using directed acyclic graphs, possibly using plot DAGs. After some thought on the matter, I decided to implement a plot DAG module first and then use that experience to create a class of actor run by a DAG. After completing the PLOTDAG.T module, I attempted to design a DAGactor class as a modification of the standard actor class based on the PLOTDAG.T code. There were several problems I discovered. These problems hinge on an understanding of the benefits of object-oriented programming and what a class is. The goal of object-oriented programming is to write as little code as possible. One writes a class, or general form, of an object containing room for data items and containing all of the code to manipulate those items, code which dictates its behavior when messages are passed to it from the outside. There are then instances of the class made in the form of specific objects, a process also called "instantiation of a class", which we have already seen. These instances, called objects, inherit all of the abilities and room for data items of all of the classes above it in the class hierarchy. When working with a specific object, such as an Actor, making the program execute a starting state method and then move to a child state method instead of a child object creates problems. Note that the state class in PLOTDAG.T was written to have the individual author to not have to supply code for analyzing the state and deciding when to jump to a child state. Each state method inside of DAGactor should likewise be identically defined in order for DAGactors to be a convenience. There is no such thing as a "method class", a method class which, by being instantiated any number of times within an object just as a class can be instantiated several times in the form of objects, can yield identical code. 5.2.1 A SIMPLE SOLUTION: USE ONE PLOT DAG The difficult way of running multiple actors is to create a large plot DAG incorporating all of the needed interactions in the game. This DAG will likely be quite large, but it may be better that all of these situations are housed in one unit instead of many. If there is one director of all of the action, there is less likely to be any kind of conflict. 5.2.2 A COMPLEX SOLUTION: RUNNING MULTIPLE DAGs One solution is to run multiple plot DAGs concurrently, one for each actor or group of actors in addition to the main plot DAG. I have put some thought into an application of this by noting modifications to the daemon and other parts of PLOTDAG.T that might facilitate development of a multi-plot DAG system but I have not implemented it. The simplest way to do multiple DAGs would be to run the daemon from a list of lists. The main list would be comprised of one list of states for each DAG. All of the DAGs' states would be of the same class, but each DAG would have a DAG identification number ascribed to it, which would be used by preinit() to form the global.states list of lists. The first DAG's number would be 1, the second 2, and so on. No DAG ID number could skip a number. The daemon would loop through all of the lists and create a frontier, remove_list, temp list, and other variables for each DAG list within the first element of each DAG contained in global.states. Even at this stage of the development, it is apparent that more information would have to be passed to the check_paths method of each state by the daemon. With this increased complexity will come increased processing costs, but not nearly the costs incurred if we simply change the names of the daemon and the state class along with adding code to the global object, the init(), and preinit() so that N sets of the code run side by side. 5.3 POSSIBLE IMPROVEMENTS A programmer can easily spend many weeks on a programming project refining it to no end. The following are some ideas that I have had regarding this module and its future. The prime addition and by far the most complex would be to implement multiple DAGs. One proposed addition is to add a hint system to the DAG. The hint verb would return a message dependent upon the state of all of the exit edges of all states on the frontier. This would probably require a method of figuring out which state's hints to consider displaying when the player is somewhere in the game, another list composed of hints that become progressively more specific, and provision in preinit() to set flags on the hints so that they will not be disclosed twice. Other authors have made hint systems that use DAG-like structures, but this would marry the hint system to the plot organization system, a desirable combination that would probably result in fewer objects. An important thing to consider is that multiple DAGs could lead to more intelligent-seeming actors. There is nothing that says conditions in a DAG must always involve the player. This actor-control via DAGs is the highest possible outgrowth of a project such as this. BIBLIOGRAPHY Anderson, Tim and Stu Galley. "The History of Zork -- First in a Series." The New Zork Times, Vol. 4(1), Winter 1985.* Eckel, Bruce. C++ Inside and Out. Berkeley: Osborne McGraw Hill, 1993. Gerrard, Mike. "Interview at the end of the Universe." Atari ST User, May 1987.* Graves, David A. "Frequently Asked Questions on rec.arts.int- fiction: Updated 08/31/93." ID: CEy6xy.M56@cup.hp.com.** Hennie, Frederick C. Finite-State Models For Logical Machines. New York: John Wiley & Sons, Inc, 1968. Kelso, Margaret Thomas, Peter Weyhrauch, and Joseph Bates. "Dramatic Presence." December 1992, CMU-CS-92-125, p. 5. Lebling P. David, Marc S. Blank, and Timothy A. Anderson. "Zork: A Computerized Fantasy Simulation Game." IEEE Computer, Vol. 12(4) April 1979, pp. 51-59.* Roberts, Michael J. The Text Adventure Development System, Version 2.0, Author's Manual. High Energy Software: 1992. Scisco, Peter. "Every Picture Tells a Story." Compute, Vol. 11, March 1989, p. 82. APPENDIX A: PLOTDAG.T (the module) // BEGINNING OF THE PLOTDAG.T MODULE /* Welcome to the PLOTDAG.T module, an add-on to the ADV.T and STD.T files which are bundled with TADS v2.1 Written by Paul Munn, April 1994 as Senior Project, advised by Dr. Parsons (Hofstra College of Liberal Arts and Sciences, Computer Science Department) and Professor Orr (New College of Hofstra University), Hofstra University Hempstead, NY 11550-1090 Syntax assistance by Dave Baggett, email: dmb@ai.mit.edu An experienced T.A.D.S. game author for ADVENTIONS. */ #include #include /* The only differences between PDSTD.T and STD.T are plotDagDaemon: function; added in with the other forward declarations of functions and setdaemon(plotDagDaemon, nil); added on to the init() function. */ /* The preinit is executed at compile time, before any game is started. This preinit replaces the standard one by having the standard's lamp list creation along with the states list creation needed by PLOTDAG.T. */ replace preinit: function { local o,p,q,r; /* These are local variables that are dynamically type-defined. That is, their type can be changed simply by making an assignment statement of a variable of a different type to it. */ // list of lightsources (from ccr-std.t) /* This routine makes a list of objects that are of the class light source. In our sample adventure, DAGE1.T there are no light sources. It is assumed that there is light available. Or that the player has night vision. It is included here to minimize code writing in the future. */ global.lamplist := []; o := firstobj(lightsource); while (o <> nil) { global.lamplist := global.lamplist + o; o := nextobj(o, lightsource); } // list of states /* These statements develop the list of states stored in the global "catch-all" object. */ global.states := []; o := firstobj(state); while (o <> nil) { global.states := global.states + o; o := nextobj(o, state); } // set each state's parents_max. // set each state's done_actions to all zeroes. /* These statements initialize some of the state's necessary values. It automates the setting of parents_max values for each set by analyzing the structure of the given DAG, freeing the programmer from having to worry about it. */ o := length(global.states); for(p := o; p >= 1; --p) //For all states. { /* Initialize the values for this state before filling them in. */ global.states[p].done_actions := []; global.states[p].parents_cur := 0; global.states[p].parents_max := 0; q := length(global.states[p].child); //Num of children. for(r := 1; r <= q; ++r) //For all child states { global.states[p].child[r].parents_max := global.states[p].child[r].parents_max + 1; global.states[p].done_actions := global.states[p].done_actions + 0; } } /* Initialize the removal list, reset each time it is emptied. Every turn the daemon executes, any states that have had all exit paths taken no longer need to be checked, so they are placed on this list and deleted after the turn. */ global.states[1].remove_list := []; // Load first state on ns_list. /* The ns_list, which stands for next state list, will hold the current states on the "frontier" of the DAG. That is, these states are the only ones that need to be checked for progress across the DAG. */ global.states[1].ns_list := []; global.states[1].ns_list := global.states[1].ns_list + global.states[1]; /* Much more processing can be added here. Suggestions many have overlooked is counting up the point values for all treasure types and setting the appropriate global values... */ } /* Sets global.debug_dag to true, referenced by the deamon and the check_paths method of each state. When true, the daemon and check_paths methods display very detailed information about their runs between turns. */ modify global debug_dag = true ; /* This function was written out of a need to display the states in a list of them repeatedly. This is used by the debugging messages allowed by setting global.debug_dag to true */ dumpStates: function(list) { local a,b; a := length(list); for(b := 1; b <= a; ++b) "<>\ "; } // The PlotDagDaemon plotDagDaemon: function(parm) { local g,h,i,j,addOk; // variables local to this function g := global.debug_dag; //The debugging flag... /* These statements go through the ns_list. Note that we do not assign the length to a variable and then use that fixed length as our watch criterion. It is important that we have length(ns_list) re-evaluated for each iteration of the loop as the ns_list[i].check_paths may add items to that list during the loop's iterations. */ for(i := 1; i <= length(global.states[1].ns_list); ++i) { // This is one of the debugging messages. if(g) "\n#DAEMON# Checking state \"<>\"..."; /* We have check_paths return a boolean (true or nil) value that will tell us if the state must be removed from the ns_list (if all of its ways out have been done). */ if(global.states[1].ns_list[i].check_paths(i)) { // Add to the remove_list global.states[1].remove_list += global. states[1].ns_list[i]; if(g) "\n#DAEMON# All done_actions finished. State will be deleted from ns_list."; } else if(g) "\n#DAEMON# All done_actions not done. Keep it on ns_list."; if(g) "\n#DAEMON# Finished checking state \"<>\"."; } /* Now remove all items in remove_list from the ns_list */ if(length(global.states[1].remove_list) <> 0) { if(g) { "\n#DAEMON# Removing done states from the ns_list."; "\n#DAEMON# ns_list: "; dumpStates(global.states[1].ns_list); "\n#DAEMON# remove_list: "; dumpStates(global.states[1].remove_list); } h := length(global.states[1].remove_list); for(i := 1; i <= h; ++i) global.states[1].ns_list -= global. states[1].remove_list[i]; //Clean out remove list for next deletion go. global.states[1].remove_list := []; if(g) { "\n#DAEMON# after removal..."; "\n#DAEMON# ns_list: "; dumpStates(global.states[1].ns_list); } }// end if anything in remove_list else if(g) "\n#DAEMON# Nothing in remove_list to remove."; /* Now that we're done removing things, we should process the ns_list so there are no doubles. We don't prevent doubles during the above loop as new conditions may prompt review of the same state again in the turn. */ global.states[1].temp := global.states[1].ns_list; global.states[1].temp := []; //Load first state of ns_list onto temporary list. global.states[1].temp += global.states[1].ns_list[1]; if(g) { "\n#DAEMON# Compacting ns_list to remove duplicates..."; "\n#DAEMON# ns_list before: "; dumpStates(global.states[1].ns_list); } h := length(global.states[1].ns_list); /* We're looking at the 2nd to the end of the ns_list to see if we'll add it on. */ for(i := 2; i <= h; ++i) { /* If next state is already in temp, don't add it */ addOk := true; for(j := 1; j <= length(global.states[1]. temp); ++j) // Check thru temp { if(global.states[1].ns_list[i] = global.states[1].temp[j]) { addOk := nil; break; } } if(addOk) //We add it on to temp. { global.states[1].temp += global.states[1].ns_list[i]; } } /* At this point, temp is the next interation's ns_list. Make it so. */ global.states[1].ns_list := global.states[1].temp; if(g) { "\n#DAEMON# ns_list after: "; dumpStates(global.states[1].ns_list); } } /* The definition of the state class */ class state: object /* The notation "Reset by author" means the default values set by this class definition must be reset by the author of the states for each game. "Set by preinit" signifies that the preinit method, defined above, will take care of scanning through the DAG at compile time and making the appropriate calculations. */ noun = 'staten' sdesc = "staten" /* The states are given a noun and a ShortDESCription to allow their use with the new verb, STATE, detailed later on. For a player to get information on the plot DAG's specific state, he/she need only type STATE to get that information. This new STATE verb would be commented out of use when an adventure works fine. For this test program, however, the verb is kept. Reset by author. */ child_conditions = [] /* A list of pointers to methods in the state the author defines. These child conditions will only be evaluated for a state if all of the edges leading to it have been traveled. Each method will return a value of true or nil when called. If this value is true, the check_paths may move to the child of that same edge. Reset by author. */ child_actions = [] /* A list of pointers to methods in the state the author defines. Upon travel to the new state child[i], child_actions[i] is executed, causing a set of actions to be taken. */ done_actions = [] /* A list of integers, initialized by the preinit function to zeros. When child_actions[i] are executed, done_actions[i] is set to 1. This tells check_paths that we can skip evaluation of this path and possibly add its child to the current traversal of the plot DAG. It is also used to determine if the state has had all children traveled to so it can now be removed from the ns_list (as it's no longer a frontier node). */ child = [] /* A list of identifiers of the child state objects. These are not pointers to methods but actual object names. Once all critera for moving to the state is satisfied, this identifier is loaded on the ns_list (stored in the first state) by check_paths (if, we'll find later, it's not already later on the list). Set by author. */ parents_cur = 0 /* This integer is the total number of parent nodes that have allowed entry to this node at this point in time. Set by preinit. */ parents_max = 0 /* This integer is the total number of parents of this node. When parents_cur = parents_max, this node can be exited. Set by preinit. */ /* The following method checks the paths of this state and updates its status. */ check_paths(place) = { local g,i,j,k,l,wantAdd,m; //local variables. g := global.debug_dag; //The debug variable. /* We can evaluate child_conditions to try and leave this state only when ALL of the edges TO the node have been traveled. */ if(self.parents_cur = self.parents_max) { if(g) { "\n#CP# We can leave: all edges to this state are satisfied."; } j := length(self.child_conditions); //Num of ways out of state. if(g) { "\n#CP# State \"<>\" has \ <> child-conditions."; } for(i := 1; i <= j; ++i) //For all ways out: { /* The default is that we do NOT want to add the child on to ns_list yet. */ wantAdd := nil; if(g) "\n#CP# Examining edge <>..."; if(self.done_actions[i] = 0) /* If actions haven't been done yet. */ { if(g) "\n#CP# checking conditions..."; if(self.(self.child_conditions[i])) // child conditions satisfied? { if(g) "\n#CP# **CONDITIONS NOW SATISFIED!**"; if(g) "\n#CP# Executing edge exit actions..."; //This executes exit actions. self.(self.child_actions[i]); /* Show we're traveling out this edge by setting its corresponding done_actions entry to 1. */ self.done_actions[i] := 1; //Add 1 to child node's p_cur. self.child[i].parents_cur := self.child[i].parents_cur + 1; if(g) "\n#CP# ...finished executing edge exit actions"; // We want to add child on... wantAdd := true; } else if(g and self.(self. child_conditions[i]) = nil) "\n#CP# conditions not satisfied."; } else { /* We DON'T want to add this child on the ns_list as it was added on earlier. */ if(g) "\n#CP# Actions done already. Skip conditions check. Don't add on again."; } /************************************** * Check if we 1) want to add on * * 2) should add on only if it* * is not already on list. * **************************************/ if(wantAdd) { /* Only put child on ns_list if it is not current state and not later on list. */ if(g) "\n#CP# Can we add child \"<< self.child[i].sdesc>>\" to list?"; k := length(global.states[1].ns_list); if(place < k) /* Not currently at end of list. */ { m := true; //default not add if(g) "\n#CP# ?-currently at item <> out of <>."; /* This not only prevents adding a state existing later on on the list but also prevents a state from adding itself and entering an infinite loop. l = place to start, not place + 1. */ for(l := place; l <= k; l++) { if(global.states[1].ns_list[l] = self.child[i]) { m := nil; if(g) "\n#CP# ?-found at place <>."; break; } else if(g) "\n#CP# ?-not found at place <>..."; } // end for } // end if place < k else // we're at end of list { /* We are at list's end so we should add this new state on to be processed ONLY if it is not the current one.*/ if(g) "\n#CP# ?-We're at end of list..."; if(self.child[i] = global. states[1].ns_list[place]) { m := nil; if(g) "\n#CP# ?-Can't add itself to list."; } else m := true; } if(m) { global.states[1].ns_list := global.states[1].ns_list + self.child[i]; if(g) "\n#CP# Yes, child \"<>\" added to ns_list."; } else if(g) "\n#CP# No, child \"<>\" not added. It is already later on list."; } //end if wantAdd } //end for i } //end if parents_cur = parents_max else { if(g) "\n#CP# Can't leave state: all edges to it are not satisfied."; return(nil); } /* Return true if all done_actions have been done. */ for(i := 1; i <= j; ++i) if(self.done_actions[i] = 0) return(nil); //All done_actions not done. //All done_actions done. return(true); } //end check_paths /* Adjustments for the STATE verb. */ verDoState( actor ) = {} /* verify-direct-object-of-State's blank entry indicates that this state can be a direct object of the STATE verb. */ doState( actor ) = /* What to do when the state is a direct object of the STATE verb. */ { local i,j; j := length(self.done_actions); "\bStatus of the <> done_actions of state \"<>\" is: "; for(i := 1; i <= j; ++i) "<>"; j := length(self.child_conditions); "\nThere are <> conditions and they return:"; for(i := 1; i <= j; ++i) { switch(self.(self.child_conditions[i])) { case nil: "\nFALSE"; break; case true: "\nTRUE"; break; default: "\nNot False or True?!"; } } "\nParents_cur = <>, parents_max = <>"; } //end of doState ; //end of state definition /* Add On Verbs: state Display the status of its done_actions array. */ stateVerb: sysverb /* System verb status allows it to be executed without time passing. No real effect on the game. */ verb = 'state' sdesc = "state" doAction = 'State' validDo( actor, obj, seqno ) = { return( true ); } validDoList( actor, prep, dobj ) = { return( true ); } ; //END OF PLOTDAG.T MODULE APPENDIX B: DAGE1.T (the sample game's states) /* DAGEX.T This file contains only the states of the sample program. The #included files will supply the state class referred to and the trivial items such as the rooms and the manipulable items that will appear in them. */ #include "plotdag.t" //class definitions and includes #include "dage1pla.t" //places and items //Set the states... state1: state noun = 'state1' sdesc = "state1" child = [state2 state3] child_conditions = [&cond1 &cond2] child_actions = [&act1 &act2] cond1 = { return(rubberball.location = Me and Me.location = corridor1); //Returns a boolean-style value of true or nil. } cond2 = { return(Me.location = cave1 and caveswitch.isActive = true); } act1 = { greencube.moveInto(Me.location); "\bThe rubber ball glows red for a moment and you hear a soft popping noise. At your feet you see a small green cube."; } act2 = { note1.moveInto(Me.location); "\nYou hear a grinding sound and look up to see a small hole open in the cave ceiling. A small slip of paper floats down from it and lands on the gravel in front of you."; } ; state2: state noun = 'state2' sdesc = "state2" child = [state4] child_conditions = [&c1] child_actions = [&a1] c1 = { return(greencube.location = startroom); } a1 = { "\bOk - Green Cube is in Alcove!"; } ; state3:state noun = 'state3' sdesc = "state3" child = [state4] child_conditions = [&c1] child_actions = [&a1] c1 = { return(note1.location = corridor1); } a1 = { "\bGOOD! Note is in the corridor!"; } ; state4:state noun = 'state4' sdesc = "state4" child = [state5] child_conditions = [&c1] child_actions = [&a1] c1 = { return(greencube.location = Me and note1.location = Me and rubberball.location = Me and Me.location = startroom); } a1 = { "\bYAY!"; } ; state5:state //An impassible state (dead end/win) noun = 'state5' sdesc = "state5" child = [state5] child_conditions = [&c1] child_actions = [&a1] c1 = { return(true); //ERROR!! } a1 = {} ; APPENDIX C: DAGE1PLA.T (the sample game's other objects) /* The PLACes and items of DAGEX.T adventure */ /* ROOMS */ startroom: room sdesc = "stone alcove" ldesc = "This tiny stone alcove is nothing more than a smooth-walled stone box open on the east end." east = cave1 ; cave1: room sdesc = "cave room" ldesc = "This underground cavern is maybe 20 feet tall with small stalactites telling you water must have been here before. The walls are rough but open up to a corridor to the south. To the west is an out-of-place niche. There is an odd, small blue switch on a wall in here. There is a yellow plaque on the north wall." west = startroom south = corridor1 ; corridor1: room sdesc = "south corridor" ldesc = "The rough-walled stone north-south corridor appears to have been sealed off to the south but appears to open out into a cave on the north end." north = cave1 ; /* ITEMS */ rubberball: item noun = 'ball' adjective = 'rubber' 'red' sdesc = "rubber ball" ldesc = "A red ball made of rubber." location = corridor1 ; caveswitch: switchItem noun = 'switch' adjective = 'blue' sdesc = "switch" ldesc = { "This appears to be a small blue switch affixed to a relatively flat part of the cave wall. There don't appear to be any lights in here that it could operate. The switch is "; if(self.isActive) "on."; else "off."; } location = cave1 ; greencube: item noun = 'cube' adjective = 'green' sdesc = "green cube" ldesc = "A small, 3-inch by 3-inch bright green cube made of wood." ; note1: item, readable noun = 'note' 'paper' adjective = 'yellow' sdesc = "slip of yellow paper" ldesc = "This slip of yellow paper seems to be blank." ; plaquething: fixeditem, readable noun = 'plaque' 'placard' adjective = 'yellow' sdesc = "yellow plaque affixed to the north wall" ldesc = "This yellow plaque has a large ATTENTION at its top and says:\nThis plot DAG is arranged as follows:\nSTATE1 has 2 possible exits.\n\t1 - must have rubber ball, the green cube will appear \n\t2 - must turn on cave switch and be there, note will appear\nSTATE2 has 1 possible exit to STATE4. put cube in alcove and \"OK\" message will appear\nSTATE3 has 1 possible exit to STATE4. put note in corridor and \"GOOD\" message will appear \nSTATE4 has 1 possible exit to STATE5. have the cube, ball, and note and be in the alcove. \"YAY\" message will appear." location = cave1 ; APPENDIX D: D1SCRIPT (the script that ran the game) >e to go to the cave room >look at the plaque to get a description of the DAG >s to the corridor >get ball to trigger state1's first edge >get cube >n to the cave >w to the alcove >drop cube to trigger state2's only edge >get cube >e to the cave >turn on the switch to trigger state1's second edge >get note >s to the corridor >drop note to trigger state3's edge >get note >n to the cave >w to the alcove. Now we have all items and trigger state4's edge. >wait to check if the cannot-add-itself to ns_list check works >quit to leave the game >yes to answer the Are You Sure query. APPENDIX E: D1OUT.LOG (the game output) A TADS Adventure Developed with TADS, the Text Adventure Development System. stone alcove This tiny stone alcove is nothing more than a smooth-walled stone box open on the east end. >e cave room This underground cavern is maybe 20 feet tall with small stalactites telling you water must have been here before. The walls are rough but open up to a corridor to the south. To the west is an out-of-place niche. There is an odd, small blue switch on a wall in here. There is a yellow plaque on the north wall. #DAEMON# Checking state "state1"... #CP# We can leave: all edges to this state are satisfied. #CP# State "state1" has 2 child-conditions. #CP# Examining edge 1... #CP# checking conditions... #CP# conditions not satisfied. #CP# Examining edge 2... #CP# checking conditions... #CP# conditions not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state1". #DAEMON# Nothing in remove_list to remove. #DAEMON# Compacting ns_list to remove duplicates... #DAEMON# ns_list before: state1 #DAEMON# ns_list after: state1 >look at the plaque This yellow plaque has a large ATTENTION at its top and says: This plot DAG is arranged as follows: STATE1 has 2 possible exits. 1 - must have rubber ball, the green cube will appear 2 - must turn on cave switch and be there, note will appear STATE2 has 1 possible exit to STATE4. put cube in alcove and "OK" message will appear STATE3 has 1 possible exit to STATE4. put note in corridor and "GOOD" message will appear STATE4 has 1 possible exit to STATE5. have the cube, ball, and note and be in the alcove. "YAY" message will appear. #DAEMON# Checking state "state1"... #CP# We can leave: all edges to this state are satisfied. #CP# State "state1" has 2 child-conditions. #CP# Examining edge 1... #CP# checking conditions... #CP# conditions not satisfied. #CP# Examining edge 2... #CP# checking conditions... #CP# conditions not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state1". #DAEMON# Nothing in remove_list to remove. #DAEMON# Compacting ns_list to remove duplicates... #DAEMON# ns_list before: state1 #DAEMON# ns_list after: state1 >s south corridor The rough-walled stone north-south corridor appears to have been sealed off to the south but appears to open out into a cave on the north end. You see a rubber ball here. #DAEMON# Checking state "state1"... #CP# We can leave: all edges to this state are satisfied. #CP# State "state1" has 2 child-conditions. #CP# Examining edge 1... #CP# checking conditions... #CP# conditions not satisfied. #CP# Examining edge 2... #CP# checking conditions... #CP# conditions not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state1". #DAEMON# Nothing in remove_list to remove. #DAEMON# Compacting ns_list to remove duplicates... #DAEMON# ns_list before: state1 #DAEMON# ns_list after: state1 >get ball Taken. #DAEMON# Checking state "state1"... #CP# We can leave: all edges to this state are satisfied. #CP# State "state1" has 2 child-conditions. #CP# Examining edge 1... #CP# checking conditions... #CP# **CONDITIONS NOW SATISFIED!** #CP# Executing edge exit actions... The rubber ball glows red for a moment and you hear a soft popping noise. At your feet you see a small green cube. #CP# ...finished executing edge exit actions #CP# Can we add child "state2" to list? #CP# ?-We're at end of list... #CP# Yes, child "state2" added to ns_list. #CP# Examining edge 2... #CP# checking conditions... #CP# conditions not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state1". #DAEMON# Checking state "state2"... #CP# We can leave: all edges to this state are satisfied. #CP# State "state2" has 1 child-conditions. #CP# Examining edge 1... #CP# checking conditions... #CP# conditions not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state2". #DAEMON# Nothing in remove_list to remove. #DAEMON# Compacting ns_list to remove duplicates... #DAEMON# ns_list before: state1 state2 #DAEMON# ns_list after: state1 state2 >get cube Taken. #DAEMON# Checking state "state1"... #CP# We can leave: all edges to this state are satisfied. #CP# State "state1" has 2 child-conditions. #CP# Examining edge 1... #CP# Actions done already. Skip conditions check. Don't add on again. #CP# Examining edge 2... #CP# checking conditions... #CP# conditions not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state1". #DAEMON# Checking state "state2"... #CP# We can leave: all edges to this state are satisfied. #CP# State "state2" has 1 child-conditions. #CP# Examining edge 1... #CP# checking conditions... #CP# conditions not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state2". #DAEMON# Nothing in remove_list to remove. #DAEMON# Compacting ns_list to remove duplicates... #DAEMON# ns_list before: state1 state2 #DAEMON# ns_list after: state1 state2 >n cave room #DAEMON# Checking state "state1"... #CP# We can leave: all edges to this state are satisfied. #CP# State "state1" has 2 child-conditions. #CP# Examining edge 1... #CP# Actions done already. Skip conditions check. Don't add on again. #CP# Examining edge 2... #CP# checking conditions... #CP# conditions not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state1". #DAEMON# Checking state "state2"... #CP# We can leave: all edges to this state are satisfied. #CP# State "state2" has 1 child-conditions. #CP# Examining edge 1... #CP# checking conditions... #CP# conditions not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state2". #DAEMON# Nothing in remove_list to remove. #DAEMON# Compacting ns_list to remove duplicates... #DAEMON# ns_list before: state1 state2 #DAEMON# ns_list after: state1 state2 >w stone alcove #DAEMON# Checking state "state1"... #CP# We can leave: all edges to this state are satisfied. #CP# State "state1" has 2 child-conditions. #CP# Examining edge 1... #CP# Actions done already. Skip conditions check. Don't add on again. #CP# Examining edge 2... #CP# checking conditions... #CP# conditions not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state1". #DAEMON# Checking state "state2"... #CP# We can leave: all edges to this state are satisfied. #CP# State "state2" has 1 child-conditions. #CP# Examining edge 1... #CP# checking conditions... #CP# conditions not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state2". #DAEMON# Nothing in remove_list to remove. #DAEMON# Compacting ns_list to remove duplicates... #DAEMON# ns_list before: state1 state2 #DAEMON# ns_list after: state1 state2 >drop cube Dropped. #DAEMON# Checking state "state1"... #CP# We can leave: all edges to this state are satisfied. #CP# State "state1" has 2 child-conditions. #CP# Examining edge 1... #CP# Actions done already. Skip conditions check. Don't add on again. #CP# Examining edge 2... #CP# checking conditions... #CP# conditions not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state1". #DAEMON# Checking state "state2"... #CP# We can leave: all edges to this state are satisfied. #CP# State "state2" has 1 child-conditions. #CP# Examining edge 1... #CP# checking conditions... #CP# **CONDITIONS NOW SATISFIED!** #CP# Executing edge exit actions... Ok - Green Cube is in Alcove! #CP# ...finished executing edge exit actions #CP# Can we add child "state4" to list? #CP# ?-We're at end of list... #CP# Yes, child "state4" added to ns_list. #DAEMON# All done_actions finished. State will be deleted from ns_list. #DAEMON# Finished checking state "state2". #DAEMON# Checking state "state4"... #CP# Can't leave state: all edges to it are not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state4". #DAEMON# Removing done states from the ns_list. #DAEMON# ns_list: state1 state2 state4 #DAEMON# remove_list: state2 #DAEMON# after removal... #DAEMON# ns_list: state1 state4 #DAEMON# Compacting ns_list to remove duplicates... #DAEMON# ns_list before: state1 state4 #DAEMON# ns_list after: state1 state4 >get cube Taken. #DAEMON# Checking state "state1"... #CP# We can leave: all edges to this state are satisfied. #CP# State "state1" has 2 child-conditions. #CP# Examining edge 1... #CP# Actions done already. Skip conditions check. Don't add on again. #CP# Examining edge 2... #CP# checking conditions... #CP# conditions not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state1". #DAEMON# Checking state "state4"... #CP# Can't leave state: all edges to it are not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state4". #DAEMON# Nothing in remove_list to remove. #DAEMON# Compacting ns_list to remove duplicates... #DAEMON# ns_list before: state1 state4 #DAEMON# ns_list after: state1 state4 >e cave room #DAEMON# Checking state "state1"... #CP# We can leave: all edges to this state are satisfied. #CP# State "state1" has 2 child-conditions. #CP# Examining edge 1... #CP# Actions done already. Skip conditions check. Don't add on again. #CP# Examining edge 2... #CP# checking conditions... #CP# conditions not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state1". #DAEMON# Checking state "state4"... #CP# Can't leave state: all edges to it are not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state4". #DAEMON# Nothing in remove_list to remove. #DAEMON# Compacting ns_list to remove duplicates... #DAEMON# ns_list before: state1 state4 #DAEMON# ns_list after: state1 state4 >turn on the switch Okay, it's now turned on. #DAEMON# Checking state "state1"... #CP# We can leave: all edges to this state are satisfied. #CP# State "state1" has 2 child-conditions. #CP# Examining edge 1... #CP# Actions done already. Skip conditions check. Don't add on again. #CP# Examining edge 2... #CP# checking conditions... #CP# **CONDITIONS NOW SATISFIED!** #CP# Executing edge exit actions... You hear a grinding sound and look up to see a small hole open in the cave ceiling. A small slip of paper floats down from it and lands on the gravel in front of you. #CP# ...finished executing edge exit actions #CP# Can we add child "state3" to list? #CP# ?-currently at item 1 out of 2. #CP# ?-not found at place 1... #CP# ?-not found at place 2... #CP# Yes, child "state3" added to ns_list. #DAEMON# All done_actions finished. State will be deleted from ns_list. #DAEMON# Finished checking state "state1". #DAEMON# Checking state "state4"... #CP# Can't leave state: all edges to it are not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state4". #DAEMON# Checking state "state3"... #CP# We can leave: all edges to this state are satisfied. #CP# State "state3" has 1 child-conditions. #CP# Examining edge 1... #CP# checking conditions... #CP# conditions not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state3". #DAEMON# Removing done states from the ns_list. #DAEMON# ns_list: state1 state4 state3 #DAEMON# remove_list: state1 #DAEMON# after removal... #DAEMON# ns_list: state4 state3 #DAEMON# Compacting ns_list to remove duplicates... #DAEMON# ns_list before: state4 state3 #DAEMON# ns_list after: state4 state3 >get note Taken. #DAEMON# Checking state "state4"... #CP# Can't leave state: all edges to it are not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state4". #DAEMON# Checking state "state3"... #CP# We can leave: all edges to this state are satisfied. #CP# State "state3" has 1 child-conditions. #CP# Examining edge 1... #CP# checking conditions... #CP# conditions not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state3". #DAEMON# Nothing in remove_list to remove. #DAEMON# Compacting ns_list to remove duplicates... #DAEMON# ns_list before: state4 state3 #DAEMON# ns_list after: state4 state3 >s south corridor #DAEMON# Checking state "state4"... #CP# Can't leave state: all edges to it are not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state4". #DAEMON# Checking state "state3"... #CP# We can leave: all edges to this state are satisfied. #CP# State "state3" has 1 child-conditions. #CP# Examining edge 1... #CP# checking conditions... #CP# conditions not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state3". #DAEMON# Nothing in remove_list to remove. #DAEMON# Compacting ns_list to remove duplicates... #DAEMON# ns_list before: state4 state3 #DAEMON# ns_list after: state4 state3 >drop note Dropped. #DAEMON# Checking state "state4"... #CP# Can't leave state: all edges to it are not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state4". #DAEMON# Checking state "state3"... #CP# We can leave: all edges to this state are satisfied. #CP# State "state3" has 1 child-conditions. #CP# Examining edge 1... #CP# checking conditions... #CP# **CONDITIONS NOW SATISFIED!** #CP# Executing edge exit actions... GOOD! Note is in the corridor! #CP# ...finished executing edge exit actions #CP# Can we add child "state4" to list? #CP# ?-We're at end of list... #CP# Yes, child "state4" added to ns_list. #DAEMON# All done_actions finished. State will be deleted from ns_list. #DAEMON# Finished checking state "state3". #DAEMON# Checking state "state4"... #CP# We can leave: all edges to this state are satisfied. #CP# State "state4" has 1 child-conditions. #CP# Examining edge 1... #CP# checking conditions... #CP# conditions not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state4". #DAEMON# Removing done states from the ns_list. #DAEMON# ns_list: state4 state3 state4 #DAEMON# remove_list: state3 #DAEMON# after removal... #DAEMON# ns_list: state4 state4 #DAEMON# Compacting ns_list to remove duplicates... #DAEMON# ns_list before: state4 state4 #DAEMON# ns_list after: state4 >get note Taken. #DAEMON# Checking state "state4"... #CP# We can leave: all edges to this state are satisfied. #CP# State "state4" has 1 child-conditions. #CP# Examining edge 1... #CP# checking conditions... #CP# conditions not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state4". #DAEMON# Nothing in remove_list to remove. #DAEMON# Compacting ns_list to remove duplicates... #DAEMON# ns_list before: state4 #DAEMON# ns_list after: state4 >n cave room #DAEMON# Checking state "state4"... #CP# We can leave: all edges to this state are satisfied. #CP# State "state4" has 1 child-conditions. #CP# Examining edge 1... #CP# checking conditions... #CP# conditions not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state4". #DAEMON# Nothing in remove_list to remove. #DAEMON# Compacting ns_list to remove duplicates... #DAEMON# ns_list before: state4 #DAEMON# ns_list after: state4 >w stone alcove #DAEMON# Checking state "state4"... #CP# We can leave: all edges to this state are satisfied. #CP# State "state4" has 1 child-conditions. #CP# Examining edge 1... #CP# checking conditions... #CP# **CONDITIONS NOW SATISFIED!** #CP# Executing edge exit actions... YAY! #CP# ...finished executing edge exit actions #CP# Can we add child "state5" to list? #CP# ?-We're at end of list... #CP# Yes, child "state5" added to ns_list. #DAEMON# All done_actions finished. State will be deleted from ns_list. #DAEMON# Finished checking state "state4". #DAEMON# Checking state "state5"... #CP# Can't leave state: all edges to it are not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state5". #DAEMON# Removing done states from the ns_list. #DAEMON# ns_list: state4 state5 #DAEMON# remove_list: state4 #DAEMON# after removal... #DAEMON# ns_list: state5 #DAEMON# Compacting ns_list to remove duplicates... #DAEMON# ns_list before: state5 #DAEMON# ns_list after: state5 >wait Time passes... #DAEMON# Checking state "state5"... #CP# Can't leave state: all edges to it are not satisfied. #DAEMON# All done_actions not done. Keep it on ns_list. #DAEMON# Finished checking state "state5". #DAEMON# Nothing in remove_list to remove. #DAEMON# Compacting ns_list to remove duplicates... #DAEMON# ns_list before: state5 #DAEMON# ns_list after: state5 >quit In a total of 18 turns, you have achieved a score of 0 points out of a possible 100. Do you really want to quit? (YES or NO) >yes APPENDIX F: Assistance Letter From Dave Baggett From: IN%"dmb@ai.mit.edu" 17-APR-1994 17:51:41.53 To: IN%"NUC2PFM@vaxc.hofstra.edu" CC: Subj: RE: Thanks muchly Dave. Here's the code... Return-path: Received: from life.ai.mit.edu by vaxc.hofstra.edu (PMDF V4.2-11 #3680) id <01HBAGOYRQXS9UOR6R@vaxc.hofstra.edu>; Sun, 17 Apr 1994 17:51:18 EDT Received: from case (case.ai.mit.edu) by life.ai.mit.edu (4.1/AI-4.10) for NUC2PFM@vaxc.hofstra.edu id AA22157; Sun, 17 Apr 94 17:50:53 EDT Received: by case (4.1/AI-4.10) id AA03546; Sun, 17 Apr 94 17:50:50 EDT Date: Sun, 17 Apr 1994 17:50:50 -0400 From: David Baggett Subject: RE: Thanks muchly Dave. Here's the code... To: NUC2PFM@vaxc.hofstra.edu Reply-to: dmb@ai.mit.edu Message-id: <9404172150.AA03546@case> Content-transfer-encoding: 7BIT Here are some things I noticed. My comments are enclosed in $$$ ... $$$ delimiters. Dave ------------------------------------------------------------------------------- class state: object /* Except where set by prenint, these will be reset in the author's defenition of the state. */ child_conditions = [] //The list of ways out of the node. child_actions = [] done_actions = [] //done_actions[i] is 1 when child_conditions[i] // has been done. 0 otherwise. Set by preinit. child = [] //List of identifiers of the child states. parents_cur = 0 //Num of parent nodes that have led to this node. parents_max = 0 //Total num of parent nodes. //When parents_cur = parents_max, we can leave this //node. Both are set by preinit. //Check paths for updates. Not to be reset by author. check_paths = { local i,j; j := length(child_conditions); //Num of ways out of state. $$$ should be self.child_conditions $$$ for(i := 0; i < j; ++i) //For all ways out: $$$ TADS arrays start at 1, not 0 $$$ { if(self.done_actions[i] = 0) //If actions haven't been done yet: { if(self.child_conditions[i] and self.parents_cur = self.parents_max) //If we can go out now: { self.done_actions[i] := 1; //Show we've gone out this way: //Setting done_actions[i] here allows the child_actions //method to reset it if desired (to go in a loop). self.child_actions[i]; //Do the things on the way out: global.states[1].ns_list := global.states[1].ns_list + self.child[i]; //Load child state on list for processing. self.child[i].parents_cur := self.child[i].parents_cur + 1; //Add 1 to num of parents of node that are done. } } else /* Add the child to the list of nodes to be traversed if and only if all of its parents have already been added to the list. */ if(self.parents_cur = self.parents_max) global.states[1].ns_list := global.states[1].ns_list + child[i]; } } ; **** THIS IS THE EXAMPLE STATE (Next line is LINE 1)**** #include "plotdag.t" /* Example plotdag game */ //Set the states... state1: state child = [state2 state3] child_conditions = [cond1 cond2] $$$ if you put method names in arrays, you need to preface them with ampersands. I.e., you should rewrite the above as: child_conditions = [&cond1 &cond2] Then to use a property pointer, you put it in parens. For example, to call the method stored in the first element of child_conditions, you'd do: self.(self.child_conditions[1])( ... ); Put method params where ... is above, if there are any. If the method takes no args, leave the (...) off. $$$ child_actions = [act1 act2] cond1 = { return(rubberball.location = Me); } cond2 = { return(Me.location = cave1 AND caveswitch.isActive = true); } act1 = { greencube.moveInto(Me.location); "\bThe rubber ball glows red for a moment and you hear a soft popping noise. At your feet you see a small green cube."; } act2 = { note1.moveInto(Me.location); "\nYou hear a grinding sound and look up to see a small hole open in the cave ceiling. A small slip of paper floats down from it and lands on the gravel in front of you."; } ; **** THESE ARE THE KINDS OF ERRORS I GET **** tc: the TADS Compiler v2.1.0.0 Copyright (c) 1992 Michael J. Roberts dagex.t, line 11: TADS-302: expected a property name $$$ You will get this error if you have a local variable named the same as a method in the current object. I.e., TADS does not allow: bar = { return nil; } foo = { local bar; // ERROR } You can get this error for other reasons, too, so this might be your problem here. $$$ dagex.t, line 14: TADS-301: expected a symbol dagex.t, line 20: TADS-301: expected a symbol dagex.t, line 26: TADS-301: expected a symbol dagex.t, line 27: TADS-301: expected a symbol dagex.t, line 34: TADS-301: expected a symbol [...mainly same errors applying to other state instantiations...] dagex.t, line 161: TADS-604: undefined object "cond2" (first use: dagex.t, line 9) $$$ You're getting these because you left off the ampersands. Without them, TADS thinks you're trying to make a list of objects, and hence complains when it finds that you've failed to define these objects. $$$ dagex.t, line 161: TADS-604: undefined object "cond1" (first use: dagex.t, line 9) dagex.t, line 161: TADS-604: undefined object "act2" (first use: dagex.t, line 11) dagex.t, line 161: TADS-604: undefined object "act1" (first use: dagex.t, line 11) [...other similar errors...] dagex.t, line 161: TADS-605: undefined symbols found APPENDIX G: ABOUT TADS TADS was written by Michael Roberts of High Energy Software. High Energy Software can be reached by mail at P.O. Box 50422, Palo Alto, California, 94303. They can be reached on CompuServe (user ID 73737,417) or GEnie (user ID M.ROBERTS10). Their CompuServe status allows others on the Internet to send electronic mail to them using the usual userid@compuserve.com method, substitution a period for the comma (making their Internet address 73737.417@compuserve.com). The TADS package is distributed as shareware and is available from the anonymous FTP archive at ftp.gmd.de in the if- archive subdirectory. Several TADS programmers have donated useful modules of their own to the archive at that site so others may use them in their own games. Several full games available at that FTP site have been written using the TADS system. The shareware distribution of TADS includes the compiler, the run-time program, some limited documentation, and the source code to a short playable sample game. The compiler takes the plain .T text file of the TADS program and turns it into a binary .GAM file (if all is well with the source code). The run-time program is then used in conjunction with that .GAM file to play the game. Registration of that TADS system, that is, purchasing a full copy, costs $40 (more if you choose to take advantage of package deals to buy other games TADS-written games and their source code) and gets you a program to transform your .GAM file into a standalone executable (and freely distributable) file, a debugger, and a very informative 239-page author's manual. The author is using a fully-registered version of TADS.