Reactive Agent Planner for TADS-3 version 1.2 --------------------------------------------- Steve Breslin (versim@hotmail.com) Based on RAP 1.0 for Tads-2, by Nate Cull (nate@natecull.org), and adopted with permission. This file is the combined effort of Cull and Breslin. --------- The files --------- This document is properly part of a ZIP archive, which contains: t3rapDocs.txt - Documentation (this file) t3rapKer.t - RAP 1.3 Kernel & support (TADS-3 source) t3rapPlan.t - RAP 1.3 Standard Planbase (TADS-3 source) t3rapTest.t - RAP 1.2 Simple Test Game (TADS-3 source) t3rapTest.t3m - Makefile for the testgame (.t3m build directives) t3rapGoto.t - Optional "go to" command (TADS-3 source) t3rapOrder.t - Optional orders module (TADS-3 source) t3knowledge.t - Required by t3rapOrder.t (TADS-3 source) notes - to-do list, etc. (text file) Contents: Introduction <== RAP is good: introductory How-to <== how to plug it in: basic The Planbase <== expanding and customizing: intermediate The Algorithm <== an apology (explanation): for the curious Alice's New Planner <== Nate Cull's initial manual: a fun read ------------- Introduction: ------------- Tads-3 Reactive Agent Planner (t3RAP) is a Tads-3 port and substantial expansion and revision of Nate Cull's original Tads-2 module RAP. Another port of RAP is available in Inform/Platypus. RAP enables you to define a complex goal for a RAP-enabled Actor, such as "acquire the treasure," and the NPC will resolve a plan for meeting this goal by breaking it into sub-goals. In this way, it finds an action which leads towards the achievement of the main goal. Or, in fancy words, it provides NPC (and PC) actors an API and customizable planbase for a goal-oriented backwards-chaining action-resolver algorithm. In short, it helps you create smarter NPCs by automating complex goal-oriented behaviors. With the provided planbase, RAP: * gives NPCs the ability to traverse a map without specifying individual movements; just indicate a destination and the NPC will go there. A built-in map scanning function generates movement plans from existing code with no extra effort. Everything that the dijkstra-based algorithms can do, RAP can do, and much besides. (The optional Goto module provides an interface for the player to use the same functionality with a "go to" command.) * performs not only map crawling, but key-hunting, object acquisition (and requests for objects directed at other actors: "Can I have x please?"), unlocking and locking, and opening and closing, etc. * is easily customizable and modifiable, and can be scaled up to arbitary situations, if you wish to customize the user-friendly planbase. Actors can be assigned plans to cook some lunch, enter conversation, get dressed; the sky is the limit. If a particular RAP plan is too limited for your NPC, you can create a new one easily, or implement a complete algorithm in an action step. It's very simple to use the basic planbase provided, but you can be as creative as you want, easily. * can be modified to make different actors execute plans differently. One actor might hunt for a key to the locked door, while another might try to find another way around the door. Also, it is quite easy to modify the planbase to allow objects to return customized plans. * provides full support for full realtime and "pseudo-turn-based realtime," for a couple alternate "feels" for actor automation. * allows the PC to command NPC's to perform complex RAP actions. (This is capability is provided by the optional Orders module.) Currently, built-in learning ability is in development. In the current version, "fog-of-war" is implemented for testing; just #define __KNOWLEDGE in the t3rapKer.t file, and include the provided knowledge module. A simpler route is for RAP actors to assume total omniscience of the state of all objects. That's believable with regards to map-crawling for an actor who knows the area well, but an actor who instantly knows everything probably needs to be dumbed down a bit. (You can modify plans accordingly, rather easily.) However, RAP commands initiated by the PC are subject to the PC's own knowledge-checking (as determined by the standard library parser and resolver). RAP has no time sense, memory or look-ahead ability. RAP-actors follow plans in a rigid, one-step-at-a-time mentality, without considering consequences or making future predictions. Consequently, RAP actors don't automatically know how to coordinate, though plans for limited Rapper coordination and cooperation might work. These limitations are unlikely to be lifted in the forseeable future. All simple circularity problems can be avoided by properly ordering the steps in a given plan, or by sophisticating plans as necessary. If you have any problems or questions, post a message on the rec.arts.int-fiction newsgroup, or email Steve Breslin at the address at the top of this document. (This manual is designed with new programmers in mind, so if you're having trouble with this manual, it's most likely the fault of the author. So do please let Steve Breslin know if you're having trouble.) ----------------- How to use t3rap: ----------------- Add the two t3rap source files, t3rapKer.t (the kernel) and t3rapPlan.t (the planbase), to the project window in workbench, or otherwise include them in your makefile or build directives. Likewise include any of the optional modules provided, if you wish. Then, to RAP-enable your NPC, define it as a "Rapper" class as well as whatever actor class you're using (probably Person). If you want to use the automatic map-navigation capability, make a call to rMapHandler.rBuildMap(), preferably by a PreinitObject. (See the sample/testgame for an example of this.) Define whatever special plans or actions you need to make up your game's planbase, or simply use the standard planbase. Take a look at the header notes to the t3rapPlan.t file, to familiarize yourself with the rSteps available in the standard planbase. Then, whenever you want your NPC to begin its RAP-automated behavior, call its rAnimate() method with a top-level goal (rStep and parameter), e.g.: Bob.rAnimate(rIn, GoalRoom); Or define Bob.myPlan and Bob.myParam, and call Bob.callAnimateDaemon(); (If you want a Rapper to perform one single step towards a specified goal, you can call rapAct(rStep, parameter).) Either realtime or "pseudo-turn-based realtime" RAP actions are very to use; simply set rSwitchableAnimateDaemon on any RAP actor to rRTAnimateDaemon or rPseudoRTAnimateDaemon, before calling rAnimate or callAnimateDaemon. By default Rapper defines rSwitchableAnimateDaemon to rAnimateDaemon, which is simple turn-based: all animated RAP actors will take a turn each player turn (that is, each daemon cycle). You can speed up processing (greatly, on average) by switching libGlobal.rCachePlanPath to true. Then, when a Rapper's animation process is called, it will try to use a previously cached plan path, if possible, rather than calculating the path again from scratch. (If the action is no longer actionable, a new plan path is calculated as normal.) RAP is normally fast enough that this level of optimization is not necessary, but you might find use for this option if your game's usage of RAP is very extensive or complicated. --------------------------------------- Expanding and customizing the planbase: --------------------------------------- This is the fun part, which you'll probably find of principle interest. Most of your efforts will probably involve customizing and inventing rStep objects, the building-blocks of the planbase. (The planbase is comprised of the definitions and interrelations of these rStep objects.) An rStep object represents a state, such as "being in some place" (rIn) or "unlocking something" (rUnlocked) and an action and/or plan relevant to the achievement of that state, and so encapsulates three main user-customizable methods: rTrue(a, p), rAction(a, p), and rPlans(a, p). You will notice that each one of these takes two arguments, 'a' (for actor), and 'p' (for parameter). rTrue(a, p) returns either true or nil, based on whether the rStep's state is currently satisfied. rAction(a, p) defines an action to execute whenever any plan reaches this rStep with an rDo opcode. rPlans(a, p) returns a list of plan-lists, in the form: [ [, , , // At least one plan-list. Note that , , ...], // each 'entry' has three elements. [...] // Optional additional plan-lists ] The opcode can be either 'rBe' or 'rDo': rBe means "if this state/rStep is not already true, consider the available plans for making this rStep come true"; rDo means "execute the rAction() routine defined by the given rStep." rPlans are the most complicated part, so let's discuss them first. First let's look at the method call: rPlans(a, p). The 'a' (for actor) is simply the RAP-enabled actor performing this plan. The parameter is the object which is currently relevant to the rStep. For rIn, the parameter is the place to be in; for rUnlocked, the parameter is the thing to be unlocked. You may have already recognized that any rStep's rPlans will involve other rSteps. (Plans within plans! What a tangled web we... eh, ahem.) Think of the rStep as a goal, and its rPlans as an ordered list of sub-goals for achieving the goal represented by the rStep. Also note that rPlans can return different plans based on the arguments ('actor' and 'parameter'). All of this will get much clearer as we look at some examples. So... An example: ----------- Let's look at part of an rStep defined by the standard planbase, singling out the rPlans() method: rClosed: rStep rPlans(a, p) { return ( [ [rBe, rReachable, p, rDo, rClosed, p] ] ); } This rStep represents a goal or state -- "making p closed" -- and a plan for the realization of this goal or state: specifically, "'p' being reachable, then closing 'p'." rReachable is another rStep, which produces a plan for "making 'p' reachable". With the rAction(a, p) method, rClosed looks like this: rClosed: rStep rPlans(a, p) { return ( [ [rBe, rReachable, p, rDo, rClosed, p] ] ); } rAction(a, p) { nestedActorAction(a, Close, p); } Whenever an rDo opcode is reached, the method rAction(a, p) is called in the rStep in question. So in the example immediately above, when the second step in the plan is reached, the method rClosed.rAction(a, p) is called. rAction(a, p) is pretty simple; one thing to consider is that, like rPlans, rActions can vary, based on the actor or parameter involved. rTrue(a, p) is simpler still. It returns either a true or nil value, based on whether or not the rStep in question is currently being satisfied. So rClosed.rTrue(a, p) simply returns true if the p in question is not open, and nil if it is open. So here's the full definition of rClosed: rClosed: rStep name = 'rClosed' rTrue(a, p) { return (!p.isOpen); } rPlans(a, p) { return ( [ [rBe, rReachable, p, rDo, rClosed, p] ] ); } rAction(a, p) { nestedActorAction(a, Close, p); } ; The purpose of rTrue(a, p) is to tell the RAP planning engine when a condition (i.e., goal, rStep) is being met, so that it won't attempt to pursue any conditions that are already being satisfied. Remember that rBe entries will have the kernel evaluate the plan for the given rStep. rDo entries will have the kernel execute the rAction() for the given rStep. Another example: ---------------- Let's turn to a more complicated example, the rStep rUnlocked. We use this example to discuss variable numbers of plan entries, and also to show how to handle things when the rStep needs to address the actor 'a' plus two objects. Without further ado: rUnlocked: rStep rPlans(a, p) { local r = []; if (p.keyList) { // add a separate plan for each p.keyList entry for (local i = 1 ; i <= p.keyList.length() ; i++) { if (p.keyList[i].location) r += [ [ rBe, rHave, p.keyList[i], rBe, rReachable, p, rDo, rUnlocked, [p, p.keyList[i]] ] ]; } return r; } else /* Many keyless unlockables will want to customize this * plan. This is only a simple default. */ return( [ [ rBe, rReachable, p, rDo, rUnlocked, p ] ] ); } rAction(a, p) { // either p = [object, key] or p = object if (p.ofKind(List)) nestedActorAction(a, UnlockWith, p[1], p[2]); else nestedActorAction(a, Unlock, p); } The normal plan for unlocking an object would be to have its key, be in a place where it can be reached, and perform an unlock action on the object. Since the object may have more than one key in its keyList we have a separate plan for each key. If the object has many keys we'll return many plans; if the object has but one key, we have but one plan. So as you can see, the particular plan (or plans) returned can be tailored to the specific situation, as determined by the actor and parameter. Often, one object for the parameter is what is needed. Sometimes, no objects are relevant, in which case 'p' is never evaluated. Sometimes, two objects are relevant. In such cases, you can make 'p' a two-element list, as we do with the final rDo step, above. In the final example we will further explore this. One last example: ----------------- Some plans need to consider two parameters not only in the rAction method, but also in the rTrue and rPlans methods. We have a special type of rStep Class for this, rStep2P, that is, rStep with two parameters. Let's look at the definition of rObjIn: rObjIn: rStep2P name = 'rObjIn' rTrue(a, p) { // p = [obj, location] return (p[1].isIn(p[2])); } rPlans(a, p) { // p = [obj, location] local ret = []; if (p[2].isIn(p[1])) ret =+ [ rBe, rHold, p[2] ]; return ( [ ret + [ rBe, rHave, p[1], rBe, rReachable, p[2], rDo, rObjIn, p ] ] ); } rAction(a, p) { // p = [obj, location] nestedActorAction(a, PutIn, p[1], p[2]); } ; In this example, p[1] is the object to be put in location p[2]. The only real complication comes in when p[2] is in p[1] (which is the reverse of what we want). In this case, the actor must take p[2] first, or else we'll get a "circularly in" message when the actor tries to put p[1] in p[2]. Otherwise, this is just an example of how two-element parameter steps are implemented. Final note: ----------- As of version 1.3 of the planbase, Classes, Lists, Vectors, and anonymous functions can be passed as parameters to the RAP processor. This allows you to have a RAP-actor try to find any light source, with a simple rAnimate(rHave, Light); -- where Light is the superclass of all light sources in the game; or you can have an actor try to place any object in a list into a treasure box, by animating him with: rAnimate(rObjIn, [[treasure1, treasure2, treasure3], treasureBox]); Note that if one of the treasures is put in the treasureBox, this goal is satisfied; this directive does not mean "put all of the list," but means "put any of the list" in the treasureBox. With this new functionality, the RAP processor no longer calls rTrue or rPlans directly, but calls rIsTrue and rGetPlans. These are service functions which unpack Classes, Lists, Vectors, and anonymous functions into game-objects, and return a complex plan, comprised of a plan for each of the game-objects in the given Class, List, etc. If you're customizing rSteps, please note: rStep and rStep2P unpack the information differently, so if you want an rStep which is designed to take two parameters (as explained above), be sure to use the rStep2P class instead of just the rStep class. That's it for the planbase. If you're comfortable with the above overview, you're now an official RAP power-user; just peruse the standard planbase to familiarize yourself with the available rSteps. Now that we've covered all the concepts of the planbase, let's have... A review: --------- Just for review, and a spot of fun, let's write a new rStep, one which gets the RAP-actor to find and greet another actor (e.g., find and greet the player character). Let's begin with the planbase: our goal is to greet another actor. So we want to 1) get into the room where the target actor is, whichever room that is, then 2) perform an action which greets that target actor. The first is going to be an rBe type goal/condition, and the second is an rDo action. So the plan should return this: [ [rBe, rIn, p.location, // using rIn from the standard planbase. rDo, rGreet, p] // we'll need to define some rGreet rAction. ] Now we can write the rTrue check and rAction for rGreet. Altogether this would come out as: rGreet: rStep rPlans(a, p) { return( [ [rBe, rIn, p.location, rDo, rGreet, p] ] ); } rAction(a, p) { if (gPlayerChar.canSee(a)) "\n<> turns to <> and says, \"Hi!\"\n"; actorsGreeted += [[a,p]]; // record that a has greeted p } actorsGreeted = [] // records two-element lists: [greeter, greeted] rTrue(a, p) { return(actorsGreeted.indexOf([a,p]) != nil); } ; To animate our RAP-actor, we could call rGreet directly: .rAnimate(rGreet, ), e.g., Bob.rAnimate(rGreet, me). Or we could call rGreet as part of a more elaborate plan defined by another rStep. For example: [ [rBe, rHave, goldenBanana, rBe, rGreet, me] ] Note that in the latter case we wouldn't use rDo for the opcode, but rather rBe, as rDo would call rGreet.rAction directly, instead of going through the rGreet.rPlans. Note also that in the other rStep we would want to include in the rTrue() method a call to rGreet.rTrue(): rTrue(a,p) { return (goldenBanana.isIn(a) && rGreet.rTrue(a, me)); } Further ideas for customizing plans: ------------------------------------ We have already seen an example that checks object properties in making plans: the rUnlocked rStep adds a plan for each key on the object's keyList. An rStep could also return special plans based on the identity of an Actor, or on some property defined by the Actor. For example, the rStep could return one plan "if (a == gPlayerChar)", and another plan for NPC's. Another technique would be for objects to define customized plans. This is rather like how the rIn plan works, since each room object actually defines its own plan-list for being in the room. But for another example, consider the rPlans definition of rOpen from the standard planbase: rOpen: rStep rPlans(a, p) { /* First we check if there's a custom plan defined by the * object. */ if (p.propDefined(&rOpenCustomPlan)) { /* If the custom plan two takes arguments, we assume it * wants to know (a, p). */ if (p.getPropParams(&rOpenCustomPlan)[1] == 2) { return p.rOpenCustomPlan(a, p); } /* We assume otherwise that the custom plan is a list, so * we just return its value. */ return p.rOpenCustomPlan; } /* There's no custom plan defined by the object. Proceed with * our default plan: if it's locked, we first get the key. */ if (p.isLocked) return ( [ [rBe, rUnlocked, p, rDo, rOpen, p] ] ); return ( [ [rBe, rReachable, p, rDo, rOpen, p] ] ); } Obviously, the same technique could be used for custom plans defined by the actor. ["The battle" demo game uses the above to allow the gate to define a custom plan for opening it.] Remember that RAP rStep methods are methods like any other, so you can put any method calls or code there; they need not deal exclusively with plans, although that is all they are designed for. It is for example possible to call another RAP action, even on another RAP-actor, set up another rAnimate daemon, exit RAP processing entirely, or anything else you need. But keep in mind that rTrue and rPlans are called before an action is resolved, similar to how verify is called during conventional action resolution; so it is normally a bad idea to change game state during these phases of RAP-action resolution. Once rAction is reached, the RAP process has decided on an action, and is not just querying this or that plan while looking for an action; so feel free to change game state however you like from within an rAction method. Theory of the planbase: ----------------------- The concept of a 'planbase' is a little amorphous. In reality there is not so much a single simple planbase as an API for an actor, given a goal involving a conditional relationship between objects, to determine what is the best strategy to invoke. The most relevant thing to consult may be either the actor, the condition, or one or more objects. This is one reason that 'a' and 'p' values get passed through the planbase. Remarks on looping: ------------------- Note that the order of plan entries is important: the Rapper will make sure to satisy the first one first, if any fail. So for example, it is vitally important, for opening a door with a key, that it *first* gets hold of the key, *then* goes to where the door is, not the other way around. If this were reversed, that is, if the plan for opening a door were [[rBe, rReachable, myDoor, rBe, rUnlocked, myDoor]], the Rapper would go to the door, then take a step towards the key, but upon thereby leaving the door, i.e., failing to satisfy the first condition, he would return to the door. This two-turn cycle would repeat. Because RAP conditions are ordered or "sequenced," care must be taken in figuring out the appropriate order. Some seemingly simple goals are conducive to loops, and so require extra care. Going through a door, locking it, and continuing on your way -- this is not as simple as it sounds. For example, if you have a map like this: doorD \/ [start]---||---[roomX]---[roomY]---[finish] Say your Actor begins at 'start', and wants to move through the door, lock it, and proceed to the 'finish' room. There is no simple way to write this in a plan. The Actor must be in roomX before locking the door, so we might (mistakenly) begin a plan like: [[rBe, rIn, roomX, rBe, rLocked, doorD, ... But now if we want the Actor to continue on to 'finish': [[rBe, rIn, roomX, rBe, rLocked, doorD, rBe, rIn, finish]] the Actor will get to roomY, but no further. Upon reaching roomY, it will no longer be in roomX, and so the first entry of the plan will intervene: the Actor will try to accomplish the first step of the plan that is currently unfulfilled, so the Actor will return to roomX. RAP can easily accomplish this task; we'd write a slightly more sophisticated plan thus: rPlans(a, p) { if (a.location == start) return ([[rBe, rIn, roomX]]); return ( [ [rBe, rLocked, doorD, rBe, rIn, finish] ] ); } Note that the player could keep the Rapper from reaching 'finish' by continuously unlocking the door: the door must be locked before the Rapper will enter 'finish'. This can be overridden by further sophisticating the above rPlans() method. A more sophisticated way get the Actor to lock doors behind it might be to use AgendaItems in addition to using RAP: an agenda item for locking the door could fire when the NPC enters roomX. The demo game "the battle" experiments with this technique somewhat. Another problem you may run into is when a RAP action fails a verify or check stage of the action. The actor will not realize that the action is impossible, and will try but fail the action. Worse, the next time their RAP process is called, they'll resolve to perform the same action again, which will fail again, and again, etc. The best way to avoid this is to sophisticate your plans sufficiently, to make them aware of the necessary preconditions for an action, such that if something cannot be done, it shouldn't be tried. Back during early development of the planbase, we realized that a loop occurs when an actor tries to "put A on B" when B is currently on A: "Bob can't do that because B is on A." The solution was to check that B is not contained by A, and if it is, try to take B before putting A on it. If B can't be taken, the plan will not work, but at least poor Bob won't be caught in a looping action. ----------------------------- An apology for the algorithm: ----------------------------- You don't really need to know this, unless you're working on the kernel, but you may find it spiritually uplifting or otherwise interesting nevertheless. This will give you a theoretical overview of how the kernel works, but for the actual procedure, we refer you to the code itself, which we hope you'll find sufficiently commented. RAP starts with a goal and then works backwards, building a tree of options until one of the branches connects with a currently actionable action. This is called "backwards chaining". In more detail: We start with a goal we want to fulfill. We figure out what is the last thing we need to do to make that goal happen. We add that to the tree of goals that we're trying to achieve. Then we repeat the process: for each "last thing" or sub-goal, we figure out a sub-sub-goal, a next-last thing. We repeat this recursively until 1) we reach an action step (in which case we've found a valid path to our goal) or 2) we're out of options (in which case we're blocked somehow, either because our planbase isn't sophisticated enough, or because it's currently impossible to achieve our goal). If at any point we find that we are calling for a goal that we have already put on the stack to achieve, we disregard it (this culls out loops). (We can do this indescriminate of what branch the redundant goal appears in.) Further, when we find a satisfied goal, we remove other plans to satisfy the same goal; that is, if we find a goal is satisfied in one way, we remove all the other goals registered by the goal's parent's child-plans. (This culls out unnecessary actions; we call this "nephew killing" because of the way the plan stack is structured: we're removing the child-plans of sibling-plans.) You can optionally utilize the rPlanPathCache, which uses a previously cached action path where possible, rather than recalculating the entire path again each turn. Otherwise, RAP repeats its backward-chaining process every single move, in case something relevant to the goal-path has changed between moves. You may nevertheless be surprised by the efficiency of the algorithm, considering what it does. Still, while some pains have been taken to optimize the calculation speed, if you're passing Classes or Lists as parameters, and the plans require RAP to calculate sense-connection or some other non-trivial library calculation, RAP can produce noticable slow-down, even on modern machines. If we were to try forward-chaining instead, we might try every possible immediately-doable action, project all their consequences forwards, and repeat until we reached the goal state. But because in practical IF models there are many more ways forward than there are backward, we do backward-chaining instead. (Thus, the vast majority of currently doable actions which are irrelevant to the goal are not even considered.) Finally, note that intervening events can stimey the projected goal-path, so RAP-actor activity does not necessarily imply that the goal is in fact reachable. For posterity, Nate Cull's much more beautiful explanation of all this is here provided: =================== Alice's New Planner =================== A Confused Sort of Introduction to RAP Planbase Programming for Looking-Glass Girls and other Ordinary People ----------------------------------------------------------- [Steve's note: Originally, the dog in the testgame was named Rap. With some hesitation, I changed his name to Rupert, because I am extremely easily confused. Anyway, consider the character "Rap" in the following dialogue the same character as Rupert from the testgame.] RAP thinks backwards. Which is by and large a good thing, because we all generally think backwards, even when we think we're thinking forwards. Confused? Alice was. "Let me explain," said Rap, a rather large brown dog who happened to be sitting between the Dormouse and the Mock Turtle. "When I say I think backwards, what I really mean is, when I get up in the morning I don't start out by thinking of the first thing I am going to do. When you get up in the morning, do you first think about putting on your dress and tying your shoelaces, or do you think about the bright sunny day and how much fun it will be to play in the garden?" Alice wrinkled her eyebrows. "I don't know. I generally do both." "Ah," said the Dormouse sleepily, "but that's because you're a Looking-Glass girl, and so you can do things the wrong way round and all at once. Here in TADS-land, we generally only do one thing at a time and so we have to make it count." "Exactly," said Rap. "So whenever I think, I do it simply and logically and start from the top. I start with a GOAL, which is what I want to accomplish, and then work out how to make that happen. Sometimes I can see immediately what to do -" "That would be an ACTION," sighed the Dormouse. " - but otherwise, I have to look for other things to do " - "SUBGOALS" " - and which themselves have things to do to make them happen " "CONDITIONS, PARAMETERS" "- and so on, reasoning backwards, all the way - " "BACKWARDS CHAINING" snores the Dormouse, who seems entirely asleep by now. " - until eventually I come up with one simple ACTION, which I do. Like this!" With which Rap threw a lump of sugar at the sleeping Dormouse, who lazily opened his eyes and continued speaking as if he had never fallen asleep. "- and there you have it," said the Dormouse. "Perfectly logical. Backwards is forwards. The proper way to do things." "But," said Alice, "I don't understand. How does this help me write adventure games?" The Mock Turtle sighed sadly and unfolded a blackboard from his shell. "Because it gives," he muttered as he scribbled. "Your NPCs. A mind of their own. This," he murmured, almost out of breath, "Is your brain. This. Is your brain. On RAP. Or rather, Rap's brain. On himself. Any questions?" And this is what the Mock Turtle wrote: rHappy: rCond sdesc = "rHappy" rTrue(a,p) { return (a.isCarrying(ball) and a.isIn(startroom)); } rPlans(a,p) = [ [rBe, rHave, ball, rBe, rIn, startroom] ] ; Alice shook her head. "That doesn't look like TADS code to me! All those square brackets! I must be dreaming about LISP or something equally horrid, and I won't have it! I shall pinch myself and wake up right now!" "No," growled Rap, "You're still in TADS-land. We're just using the list structure. You have read your TADS manual, haven't you?" Alice blushed at this, because she _had_ read her TADS manual, but had forgotten all the bits that came after "#include ." So she nodded primly and said nothing. "I will be using TADS list structures a great deal," said Rap firmly, "in fact almost everything that is in my head is expressed as a list, so please pay attention." The Mock Turtle scowled and rapped on his blackboard-shell. "Shall we begin?" he said. "This, harumph, young lady, is the top level of your friend Rap's brain, vacant as it is right now. Translated into Looking-Glass English it says this: 'You are happy if you are in the room "startroom" and carrying the ball. Otherwise, you are unhappy. (And you don't want to be unhappy, though that is something you will be told elsewhere.) 'You want to be happy? Here's how. First be carrying the ball. Second, be in the room "startroom'. And don't bother doing anything else, because that's all you need to be happy.' "As you can see from his rather simple value system, Rap is a refugee from the '60s. Pity you missed that decade, eh what?" Hearing this, the Dormouse wriggled in his sleep and began snoring, "All you need is the ball, yay yay yay, all you need is the baaaall..." before falling into the teapot with a sploshy gurgle. Alice ignored him. "I can understand the rTrue method", she said somewhat uncertainly, "at least I believe I can. That tells me whether or not I am currently happy. I'm quite familiar with the isIn and isCarrying methods because Mr Dodgson (after teaching me mathematics) has been showing me how to use the adv[3].t class library. And I can assume that Rap wants to be happy because there is a method call somewhere telling him so. "But what is a plan? And why is it laid out like that with all those brackets? What is an rBe? What does it all mean?" At this the Dormouse (who had been gurgling quietly in the bottom of the teapot) poked his head above water and sang softly, "Ah-bees make ah-honey, they ah-live in ah-hive, to rBe or not 2rBe, ah, that's why we're rLive" until Rap pushed his whiskers back into the pot and and leaned both forepaws on the lid. "rBe," said the Mock Turtle seriously, "is a RAP opcode. All RAP classes and methods begin with an r. And I know you are going to ask me what an opcode is - " "I wasn't," said Alice, who was feeling contrariwise, but the Turtle ignored her. " - so perhaps it is time I introduced you to the RAP plan syntax, which goes like this: Plan group :- [ [ <-- one parallel plan opcode, condition, parameter, {opcode, condition, parameter,} <--- one step {opcode...} ] [opcode, condition, parameter..] <-- an alternative parallel plan [...] <-- etcetera ] " "I once met an etcetera," said the Dormouse from the teapot. "He was dating an elipsis, but they broke up. She ran off with a much older opcode." Everyone ignored him, especially the Turtle. "AS YOU CAN SEE," he frowned, "each Plan Group may actually be a set of PARALLEL PLANS. And each Parallel Plan may actually be a sequence of STEPS. (Please ignore the curly brackets - they're just there to indicate repetition. If this were a proper syntax diagram they would be square brackets, but I'm using those already to show TADS list structures, so I had to be creative.)" "Curly brackets, squiggly wiggly, repetition, ad infinity," muttered the Dormouse and then shut up hurriedly before anyone could throw something at him. "AS I WAS SAYING," harumphed the Turtle, "our friend Rap's rHappy plan is very simple because he has only ONE parallel plan - to be in Startroom while holding the ball - and only TWO steps in that plan." "So the first step would be rBe, rHave, ball and the second is rBe, rIn, startroom ?" asked Alice, curiously. "I must say, you have very nice whitespace formatting," remarked Rap, "for a Looking-Glass girl." "I've been practicing with the Caterpillar," said Alice. "But that's right, is it? I've read Rap's top-level Plan properly?" "Yes, indeed," nodded the Turtle. "You've read it right, all right." "Read, write, read, write," sang the Dormouse, blowing tea bubbles absently in his sleep, "sequential planning's dead, I don't know my name so I'll backwards chain, until I get out of bed." "Some of us," growled Rap, "have better things to do than make bad nursery rhymes. I know I do. I have a plan for my next action right here." "Ah," said Alice, who was starting to catch on, but slowly because her head still hurt from all this backwards talk, "so Rap takes each step in sequence, right? First he picks up the ball, then he goes to the Startroom?" "Not precisely," whined Rap, fishing in the teapot with one paw, while the Dormouse dodged dreamily. "STEPS are not exactly ACTIONS. They're not things I DO, and they're not exactly in SEQUENCE." "But the Turtle said - " "They're CONDITIONS, and they're arranged in order of PRIORITY," finished Rap, withdrawing his paw from the Dormouse's teapot and licking it. "What's the difference?" "If they were STEPS, I would take first one, and then the other, right? I would always _pick up the ball_, and then always follow that with _going to the startroom_. Right?" "Yes, of course," said Alice, who was a very logical girl and couldn't understand why everyone else was being so strange. "But then," said the Dormouse, emerging from the teapot and shaking his whiskers furiously, "we should all be back writing sequential, procedural, algorithmic code, and right back where we started. Doing things forwards. When as I said, backwards is the only proper way to do anything." Saying which, he washed his whiskers from the outside in, brushed his coat from the tail up, and promptly curled up inside the large bubbling Klein Bottle marked -EM KNIRD-. "Exactly," said Rap. "If I did everything forwards, I should be very dumb indeed. Supposing I was already holding the ball. Why should I want to pick it up again? Or supposing I was halfway to the Startroom when a frumious Bandersnatch came galumphing out of nowhere and snatched it away? They do, you know. They're a menace. If I were only following a sequence of STEPS, I would keep going as if nothing had happened. Which would be quite silly indeed, don't you agree? And certainly something that the standard TADS library could implement quite easily without introducing _me_ into the picture." "I see," said Alice doubtfully, less and less sure all the time that she did, but not willing to admit it. "So every CONDITION in one Parallel Plan has to be satisfied in order, and if it is it acts like a sequence of steps, but if one condition fails, you go back and repeat it?" "More or less," agreed the Turtle, "more or less. Each CONDITION in a STEP specifies something which must be true (such as the ball being carried by Rap, or him being in the Startroom). If that Condition is true, then Rap keeps going, checking out the next condition, and so on. In that way it is a little like a sequence of actions. But if it's false, then it becomes a GOAL for Rap to _make_ that condition become true." "Loag, noitidnoc, loag, noitidnoc," sang the Dormouse from within the Klein Bottle, but nobody could make any sense at all of him this time so they didn't even bother to reply. "Hmm," said Alice, even more doubtfully, but getting a little smarter each time she thought about this. "And of course, Rap then looks up THAT goal as a Condition in his - what do you call your, er - " "My PLANBASE," barked Rap. "- your Planbase -" "Which, as its name indicates, is a database of Plans," put in the Turtle. "(Implemented as the rPlans methods of the entire set of rCond and rAction objects in the game file. But I digress.)" ".od ouy ,seY" sang the Dormouse. ".od ouy ,seY" " - you look up that goal in your Planbase," continued Alice determinedly, "and find all the Parallel Plans for THAT Condition. And if that Condition isn't true -" "I scan each plan in parallel. Which is why they're called Parallel Plans," finished Rap. "Could you explain that part, please, Mr Turtle," asked Alice. "I don't think we've covered that." "He scans each plan in parallel And each plan he scans, it's clear as a bell And he scans each step in each plan as well Until a condition fails, then it all goes to h - " "AHEM!" shouted Rap and the Turtle together at the Dormouse, who had crawled out of the Klein Bottle and was now blinking at them from a few weeks south of Last Tuesday. "I only meant - " said the Dormouse meekly - "That's precisely your problem," snapped the Turtle. "A Dormouse shouldn't _mean_. It should _be_." "That's demeaning," murmured the Dormouse from Next Week. "Oh, do stop messing up the continuum like that. You know it's already far too wrinkly. Anyway - " "What the Turtle is trying to say," said the Dormouse, now fully awake and dropping back into the table's gravity well with a faint splatter of Hawking radiation, "is that Rap evaluates each Parallel Plan in a Plan Group IN PARALLEL. That is, for each Parallel Plan (for a particular goal that he's trying to make true, remember) he looks at each Condition in sequence. Continuing to the next Condition if it's true, or creating a new GOAL for that condition if it's not." "So he creates a kind of Tree of Goals, then," said Alice, whose forehead was getting almost as wrinkly as the continuum, though still a lot cleaner. "A Goal Tree? Or a Stack? That sounds horribly AI-ish. Does it take a lot of computational resources to store this tree? And won't it expand to infinity? And break the universe or something?" "Heavens no, child," said the Turtle, glancing at the Dormouse, who nodded. "It's perfectly safe. We've taken steps to stop that sort of thing. We remove duplicate goals from the stack, so it won't explode. And then there's the rIf opcode -" " - which you still haven't talked about - " "- but I'll get to that in time. Anyway, Rap recalculates the Goal Stack (it's really a stack, not a tree, though the list of active goals tends to grow a bit like a tree) - " "An upside down tree," murmured the Dormouse, falling asleep again, "with its root at the top. But of course you knew that already." "Yes, we did. So anyway, let's just say that Rap is quite good enough at keeping track of his goals and things, and that he DOES evaluate each Plan in Parallel. And within each Plan, he goes through it step by step, looking at each Condition -" "But why does he look at multiple plans at once?" said Alice, whose head was starting to spin, just like Linda Blair. "He can only do one thing at a time, surely?" "Ah, but he can THINK about lots of things at once. Let me demonstrate," said the Turtle. "With another Plan from Rap's planbase. This one is for moving between rooms. A very typical IF thing to want to do, and in fact what Rap's author first wrote him for." "Hey," said the Author, "leave me out of this, okay?" The Turtle ignored him and scribbled on his blackboard-shell again: rIn(actor, param) { if (param == startroom) return ( [ [rBe, rIn, room2, rDo, rGo, startroom] ] ); else if (param == room2) return ( [ [rBe, rIn, startroom, rDo, rGo, room2] [rBe, rIn, room3, rDo, rGo, room2] [rBe, rIn, room4, rDo, rGo, room2] ] ); } Alice looked dubiously at the board, which looked like nonsense, but being a well-brought-up young Looking-Glass girl she felt it was her duty to make _some_ sense of it all. "I suppose," she said slowly, "I can work out some of this. This seems to be two Plan Groups for Being In two rooms. The first one is simple enough. It tells Rap how to get to Startroom -" "Not GET TO," growled Rap. "How to BE IN. There's a difference. It's a Condition, not an Action." "As I'm a Dormouse," yawned the Dormouse, "not a Do-mouse. I practice Being, not Doing. It's much healthier." " - how to Be In Startroom," Alice corrected herself. "By... let me see. First, Being In the room 'Room2'. Which I suppose must be next to Startroom on the map in RAPTEST.T." "It is," growled Rap. "Very good, Looking-Glass girl." "And then it does an.. oh, my. rDo rGo startroom? I don't believe I've met the rDo opcode yet." "We will, in just a minute - " said the Turtle. "Though they're not very nice," said the Dormouse. "Opcodes, I mean. Just ask the etcetera." " - after you finish working this out. You can, can't you?" "Well, I _think_ so. I should imagine it means that Rap will Do an Action. Which would be Going to the room Startroom. Right?" "Very good," said the Turtle, pulling a second blackboard from his shell and writing on it: RAP Opcodes: ------------ rBe condition param <---- make this condition true (create a goal) rIf condition param <---- check this condition, but don't make it true (used for optimisation). [This is unavailable in t3rap.] rDo action param <---- do an action (this ends goal scanning) "I see," said Alice, for about the umpteenth time. "So rBe is the main Condition opcode. rIf is sort of like rBe, only it doesn't make a goal. Where would I want to use that?" "The author hasn't really thought about that," said the Dormouse, blowing more tea-bubbles. "Have you?" "Er, no. But it's there if you want to use it. For optimisation and stuff. It prunes the goal tree. But you don't really need to use it at all, generally. Um, will you let me out of that tea-bubble?" "Sorry." The bubble popped, and the Author disappeared. " - And rDo forces an Action to be made. What do you mean by ending goal scanning?" "Just what it sounds like, my dear." "It sounds painful." "Well, it's not really. It just means that as soon as Rap finds an Action that he can do, he does it. And then his move is over, and the Player gets a move, and all sorts of game state gets updated, and such, and then Rap can take another move and so on and so on. This means that when Rap is evaluating multiple parallel plans, he does the first Action that he can find - " "That sounds sensible." "- which means that generally, he chooses the shortest path between two rooms, or the shortest sequence of actions that leads to the goal he wants. Which, as you say, is generally sensible." Alice wrinkled her nose. "Are there any cases when it wouldn't be?" "I don't know that, either," said the Author. "So let's just say that it's sensible and leave it at that." "Then I think I understand. Now, suppose I take a look at the second Plan Group there. The one for Room2. (What silly names these rooms all have!)" "They're very sensible names," growled Rap, batting at the Author's tea bubble with one paw. The Author winced. "Everything's numbers, when you take it apart." "Like you did with the White Rabbit's wristwatch," said the Dormouse sleepily. "Only you couldn't get the numbers back in again right. That's why we keep repeating this conversation." "ANYWAY," continued Alice, "I can see there really ARE three Parallel Plans here. We're trying to Be In Room2, but there are three different ways to do it: Either: [rBe, rIn, startroom, rDo, rGo, room2] Or: [rBe, rIn, room3, rDo, rGo, room2] Or even: [rBe, rIn, room4, rDo, rGo, room2] "Yes indeed," said the Turtle approvingly. "And Rap tries all of these at once. Each one creates either an Action or a goal. And so on. And the first goal that produces an Action wins." "I really do think I'm getting it," said Alice excitedly. "So there are three ways to get to Room2 -" "As you'd expect in a room with three entrances," put in Rap. " - and the first one is to be in Startroom and then go to Room2, and the second is to be in Room3 and go to Room2, and so on. Yes, it all makes sense." "Oh dear," the Dormouse whispered, "It's starting to make sense to her. That means she must be starting to wake up. And you know what that means..." "Wait, please!" cried Alice, jumping to her feet, who was a bright little Looking-Glass girl who had been around the dream clock a few times and knew just how these things worked. "If you're all going to vanish away _just_ when it's all making sense I shall be _very_ annoyed. Because all this will go out of my head and straight back into Looking-Glass land when I wake up. And I shall cry and bang my head on my pillow and I shall give myself a splitting headache faster than you can type YOMIN ME WITH A FROTZED GRUE. So please answer my last few questions right now!" "Very well," said the Mock Turtle, who was looking at his watch and hurriedly packing up his blackboard-shells without trying to look as if he was hurrying. "What else do you need to know?" "Conditions. Actions. Parameters. What are they and how do I use them? I know how do do a Plan Group, I think. I use the rPlans method. But what about all the rest of it, tying it into my TADS code?" The Turtle picked up the Klein Bottle, shook it a few times, and wrote some glowing letters in the continuum: Conditions ---> rCond objects truth method ---> rTrue(actor, param) plan method ---> rPlans(actor, param) Actions ---> rAct objects action method ---> rAction(actor, param) "These are the basics. Actor is a parameter to all the methods because, well, you know how all TADS verbs pass the actor, it's just a TADSy kind of thing to do. RAP is almost always associated with an actor, so we pass that in case it's useful. Param is a parameter to the action or condition, and yes, that's the one we haven't yet talked about. The reason why is it's very simple. "A Parameter can be anything at all. Any Object class, primitive type, or even a List (so you can have multiple parameters in a Condition or Action if you really want)." Alice shuddered. For some reason, she still didn't want to think about any more Lists than she had to. "I'll try to forget that," she said. "But I understand now. A Condition and an Action both need an Opcode and a Parameter. Like, for example: rDo rGo startroom is an rDo Opcode, an rGo Action, and a Parameter which is an Object Reference to the room 'startroom'. And this is all returned somewhere inside the rIn Condition's rPlans method. Right?" "Right," said Rap, carefully preening his coat and fastening his bowtie without trying to look like he was doing either. "And it's all a TADS list. So, I can use any kind of TADS tricks I like to create that list, right? Like this: rDo, rGo, x where x is a local variable in my rPlans method. Or any kind of object property. Or anything. Right?" "Right," said the Dormouse, carefully folding up the teapot and packing it away into a passing tea-bubble, taking very special care not to pop it. "And... I could even generate new Plans at runtime, by modifying the rPlans method to do all kinds of calculations... or I could maybe create plans at compile time, maybe by scanning the map with some kind of scanning routine..." "Hrrmmph," said the Mock Turtle, looking at his watch. "Oh, my goodness, is that the time? We really must be - " "No!" cried Alice. "I remember now. You still haven't told me about that automatic map building routine! You simply _can't_ vanish away and not have told me about that!" "Sorry," said the Dormouse, folding up the last of the continuum into his tea-bubble. "Can't. Rules, you know. Sheer physics. Space. Time. Out of. Etcetera. Elipsis. But if you really want to know more - " "Yes?" shouted Alice, into the by now very black and empty darkness. "Read the source," said a hollow voice. "And who made _you_ an authority?" said Alice, turning angrily towards the voice. There was an awkward pause. "Ah. Because I'm the, you know, thing, author." "And that's the last straw." said Alice. "I refuse to be talked to by a talking tea-bubble. This whole conversation has been one piece of nonsense piled upon another! I should pop you right now!" "Er. No, you really don't want to - " POP. "Oops," said Alice.