Note especially that the ugly _ variables are gone, bindings can be accessed just as if they were variables, and the syntax is a little cleaner overall. Even better, a lot of the definition can be omitted in the common case. Let's show another fluent, which reduces the money in the Owner's bank account:

f poorer:
  type {money, Owner}.
  value
    MealCost
  .
  combine:
    Net - Value
  .

Next, we'll examine the "cancel search", which finds a set of fluents and cancels them. This is provided so that incident archetypes can cancel fluents without necessarily knowing exactly which ones they'll need to cancel beforehand.

%c defines a cancel search
%which detects fluents and
%generates cancels for them.
%in this case, we cancel any diets the Owner is on.
c cancel_diet:
%this binding also comes from the enclosing incident.
  type {diet, Owner}.
%"start 0." and "end Time." are the default values,
%so we can omit them.

A mere two lines, much reduced from the original.

Requirements are another feature provided by Thucydides:

%r defines a requirement - in this case, the Owner
%must have enough money to buy the feast
r req_money_for_feast:
%a "history main." line could be added here, but it's the default
%this gets bindings too.
  type {money, Owner}.
%"start 0." and "end Time." are the defaults.
%There could be an "args []." line in here, but we omit it
%since the list is empty.
%check is the value-checking function; it gets bindings, too.
%the default check function is "check Value == true."
%it's worth mentioning that type, start, and end will all be omitted,
%in which case only the check function will be used.  This is generally
%used to verify properties of the Bindings.
  check Value > MealCost.

This is a sight better than a six-argument ?REQ macro, surely!

The next feature we'll examine is the final element in the TADL subset of TSDL, the Incident Archetype:

%this is an incident archetype definition
i eat_feast(Owner, MealCost): 
%We could say "histories [main].", but that's the default.
%refer to previously defined f_arc "full"
  set full.
  set poorer.
%we could define a new fluent inline with "set new_fluent(Arg): ... end.",
%then defining a fluent as above.
%refer to previously defined cancel
  cancel cancel_diet.
%cancels can be defined inline too: "cancel unwanted_fluents: ... end."
%refer to previously defined req
  require req_money_for_feast.
%requirements can be inline too: "require important_req: ... end."

This lightning tour of TSDL syntax bears some explaining. The basic element of TSDL is the "definition", which can be one of seven types:

q

An HQL query, just like in a .HQL file.

f

A fluent archetype

c

A cancel search

r

A requirement

i

An incident archetype

b

A binder function

follow

A follow definition

We haven't looked at binders and follows yet, but each definition has roughly the same form:

type name(arguments, if applicable):
  parameter value.
  ...
  subdefinition name(arguments, if applicable):
    subdef-param value.
    ...
  end.
  parameter value.
  ...

The distinction between parameters and definitions is straightforward: the former begin immediately and end with a period, and the latter begin after a colon and end automatically (or, in the case of inlined definitions of types f, c, or r, with an end. tag. The end tag can be omitted for the other types when inlined). Sub-definitions can be nested.

The other thing to note is that virtually all of the parameters take functions of (Time, Bindings) as their arguments.

Since the definition of binders and follows have various semantic consequences, we'll leave the discussion of TSDL there for today.

Trigger Happy

Actually triggering incident archetypes, given bindings and time, is done by thucydides:trigger() in the local client interface and a similar message in the remote client interface. Triggering an incident also checks the requirements and triggers any incidents that might follow it at that particular time. Trigger can return three values:

not_met

The requirements for this incident aren't met at the given time.

paradox

Triggering this incident is incompatible with the future state of the world, and would cause a paradox. It isn't triggered.

{ok, TriggeredIncidents}

TriggeredIncidents is the list of incidents that were triggered as a result of triggering the given incident; this can happen if a follow is set up to immediately react to an incident. Follows will be described in a forthcoming article.

Hopefully, TSDL reads more plainly than raw Erlang, even though it incorporates some Erlang syntax. If there are any questions, please e-mail me or leave a comment below.

One more note before continuing on: There is a case where client code might want to use Herodotus directly, ignoring Thucydides outright. However, this is really only useful for local clients (which will be explained below). Even in their case, they will likely make use of Thucydides's incident archetype indexing and triggering mechanisms; so there's no reason to have a Herodotus Incident Definition Language apart from TADL/TSDL.

Herodotus Query Language

The goal of Herodotus Query Language is to provide a compact syntax for defining queries and operations on the results of queries. It has an additional goal of being easy to read and easy to implement. Initially I had thought of a syntax like this:

history-name fluent-type start end args
  

Like that, separated by spaces, where history-name is an optional atom, defaulting to "main"; fluent-type is an atom, a list of fluent-types, or a tuple of fluent-types; start is an optional number, defaulting to zero; end is a number; and args is an optional list of arguments, defaulting to the empty list. Unfortunately, this syntax has some problems: it's not especially compact or easy to read, it's too whitespace-sensitive, and it's not obvious how to perform complex expressions. With a little thinking, I came up with this compact form:

history-name:fluent-type@start--end&args
  

This replaced spaces with symbols, but it still wasn't satisfying because its syntax was so weird. In the end, I decided to go with a subset of Erlang's syntax:

q(history_name, {fluent_type, start, end}, args)
  

With the same optional values as mentioned above. The advantage of this syntax is obvious in this example which finds the net worth of a person named Bill:

NetWorth = q({{value, q({{assets, bill}, 10})}, 10})
  

This compound query can be passed in at-once. To explain: the inner query q({{assets, bill}, 10}) gives the list of item identifiers in the possession of bill at time 10. The outer query finds the value of all of those item identifiers at time 10. This kind of combination of queries is possible with this third syntax, which also lends itself more readily to variable binding and pattern matching.

Herodotus client code comes in two flavors: Local clients and remote clients. Local clients run their own embedded Herodotus process; remote clients connect to a Herodotus server. A local client is written in or bridged to Erlang, and can dynamically create and trigger arbitrary queries. But a remote client can be written in any language, and has to limit these abilities for security reasons. Therefore, HQL statements can be prepared beforehand:

%in local client code:
hql:s(stored_query_1, fun() ->
  %...hql statements...
end)

hql:s(stored_query_2, fun(Arg1, Arg2) ->
  %...hql statements...
end)

%or in a .hql file for local or remote clients:
stored_query_1():
  %...hql statements...
  .

stored_query_2(Arg1, Arg2):
  %...hql statements...
  .
  

Queries stored in such a way are triggered with:

q(stored_query_name, args)
  

Where args is a list. The usage of HQL files for remote clients means that Herodotus server admins can vet the queries that are to be made and ensure that nothing damaging or harmful will be done. Hooks will also be provided to allow some automatic security auditing of HQL queries.

A final note to make on HQL is how HQL queries are invoked. In local client code, they're wrapped in an hql:e() function call, which itself takes a fun as argument. This is similar to Mnesia's transaction function. In remote client code, stored HQL queries are invoked by remote messages.

Send in the Code

First, we'll write a quick and dirty adventure game interface:

%No code!  We're going to use the Erlang shell for I/O, 
%and let our input alphabet be function calls 
%and our outputs be strings.

With that out of the way, we can move on to the interesting parts. I'll only show excerpts here, but here's the whole file. The Herodotus/Erlang implementation also includes this demo, but that's not ready to distribute yet. Now, on to the tasks.

Speak Fluent Erlang

First, we'll look at simply applying Fluents in a Herodotus history. In this example, we create a few Fluents, jam them into an Incident, and trigger that.

%... jones.erl 42-47: reset()
%This macro creates a Fluent with the given type, context,
%start, end, persist-value, value code, and stack code.
%These up the initial state of the room.
%Note that since we know these are the first fluents, we can just
%use the current fluent's value for the new net value in the stack mode.
RockOnFloor = ?FLUENT(inventory, floor, 0, infinity, removed, [rock], _Val),
StatueOnPlate = ?FLUENT(inventory, plate, 0, infinity, removed, [statue], _Val),
EmptyHands = ?FLUENT(inventory, player, 0, infinity, removed, [], _Val),
DoorOpen = ?FLUENT(open, door, 0, infinity, closed, open, _Val),
%Now we put all the Fluents into a list...
Fluents = [RockOnFloor, StatueOnPlate, EmptyHands, DoorOpen],
%And trigger a new incident using those fluents and no cancels.
%We trigger them in the main history of the jones_hero herodotus process.
herodotus:trigger(incident:new(init, Fluents, [], 0), main, jones_hero),
%...

Incident Archetypes

Now that the initial state is set, we can start looking at Thucydides. We want to create five incident archetypes, but we'll only show a couple. The first will be the Look archetype, which has no requirements.

%... jones.erl 65-87: setup_iarc(look)
%This macro creates an 'Adder Fluent Archetype'.  All of the arguments 
%are in the context of a function.  The available vars are 
%(_Time, _Bindings) for the first five code arguments, where
%_Time is the time the Incident is triggered; and 
%(Self, _Now, _Args, _Time, _EndTime) for the sixth code argument.  
%Self is the Fluent being evaluated.
%This macro provides its own stack mode, so that definition isn't shown yet.
%A Fluent Archetype can be 'cloned' into a Fluent, given time and bindings.
%This is similar to the way incident archetypes are cloned into incidents.
%modify times_looked
FA = ?A_ADD(times_looked,
%for the looker - we use bindings for flexibility
            dict:fetch("Looker", _Bindings),
%at the given time
            _Time,
%forever
            infinity,
%if this gets ended somehow, it won't change the value
            persist,
%increment by one
            1),
Fluents = [FA],
%This is primarily for documentation and 
%discovery purposes, and may be removed later
Vars = ["Looker"],
%Look requires nothing in particular
Reqs = [],
%Look doesn't depend on any fluents
ExtraInputs = [],
%Look doesn't cancel anything
Cancels = [],
%Create the archetype
Look = i_arc:new(look, Fluents, Vars, Reqs, ExtraInputs, Cancels),
%Add the archetype to the simulation
simulation:add_iarc(Look, jones_sim)
%...

The second archetype we examine will be Lift, which cancels the {open, [door, plate]} Fluent set initially(or set by Place). We use a list context there, since we assume that the door could potentially be opened by a lever, even if the plate were empty. Really, this is primarily to show the cancellation mechanism - it could just as well have been done with a fluent-set. One example of a place to certainly prefer cancels over simple fluent replacement is when growth changes from linear to exponential, or some similar massive shift like that.

%... jones.erl 132-192: setup_iarc(lift)
%A complete fluent archetype, including stack mode.
TakerAddItem = ?A_FLUENT(
%modify inventory
    inventory,
%of the taker
    dict:fetch("Taker", _Bindings),
%at the given time
    _Time,
%forever
    infinity,
%on cancellation, it's "removed"
    removed,
%the item to be added is the result of a query
    herodotus:value(
%when you make a query from within a fluent, you should provide
%the fluent making the query.
        Self,
%this query is against the inventory of the source.
%we can assume there's only one item in it.
%note that we use _Time, the time the fluent 
%was set, and not _Now, the time it is evaluated
        selector:new(inventory, dict:fetch("Source", _Bindings), _Time),
%no extra args
        [],
%the history is the main history
        main,
%of the jones_hero herodotus process.
        jones_hero
    ),
%and it's merged into the taker's inventory
    fluent:fmerge(_Net, _Val)),
%Now for the next fluent:
SourceRemoveItem = ?A_FLUENT(
%modify inventory
    inventory,
%of the source
    dict:fetch("Source", _Bindings),
%right now
    _Time,
%until forever
    infinity,
%if it is canceled, it will be "returned"
    returned,
%lift the topmost item, whatever that means
    [hd(_Net)],                     
%and subtract it from the old inventory
    fluent:fsubtract(_Net, _Val)
),
%these are the fluents for this archetype
Flus = [SourceRemoveItem, TakerAddItem],
%these are the variables
Vars = ["Taker", "Source",
        "Trigger", "TriggerFluent",
        "TriggeredState", "UntriggeredState"],
%Now for the requirements
SourceHasItem =
%REQ is a macro which creates a Requirement, given three bits of 
%selector information, arguments, and a function to check the 
%value resulting from querying that selector with those args.
    ?REQ(
%Require that the value of the inventory
         inventory,
%of the Source
         dict:fetch("Source", _Bindings),
%at the time of application
         _Time,
%with no extra args
         [],
%contains an item
         is_list(_Val) andalso length(_Val) > 0
    )
,
TakerHandsFree = 
    ?REQ(
%Require that the inventory
         inventory,
%of the taker
         dict:fetch("Taker", _Bindings),
%at the time of application
         _Time,
%with no extra args
         [],
%is empty.
         _Val =:= []
    )
,
%gather the requirements
Reqs = [SourceHasItem, TakerHandsFree],
%no extra dependencies
Extras = [],
%This finds the "door opened by plate" fluents and kills them.
%A_SEL creates a selector archetype, which follows the same
%rules as other archetypes.
TriggerFinder = ?A_SEL(
    dict:fetch("TriggerFluent", _Bindings),
    [dict:fetch("Trigger", _Bindings), dict:fetch("Source", _Bindings)],
    _Time,
    infinity
),
%Gather the cancels
Cancels = [TriggerFinder],
%and create the archetype
Lift = i_arc:new(lift, Flus, Vars, Reqs, Extras, Cancels),
%then add the archetype
simulation:add_iarc(Lift, jones_sim)
%...

Trigger Action

Now it's time to figure out how to trigger these incident archetypes.

%... jones.erl 349: look()
%This asks the simulation jones_sim to trigger the 
%"look" incident in the given history(main)
%at the given time with the given bindings.
%We use special bindings for the player just 
%to show a little more of the Archetype system.
simulation:trigger(look, 
                    main, 
                    current_time(), 
                    dict:store("Looker", player, dict:new()), 
                    jones_sim)

Triggering is simple! This will return ok if it completes successfully, not_met if any requirements are not met, or paradox if a paradox would result from applying that incident. Thucydides handles all of the requirement checking, cancellations, paradox checking, and so on. Also, note that if any non-ok value is returned, the history is as it was before the trigger: a trigger either succeeds or fails, and intermediate states will not pollute other actions.

Mission accomplished!

While Thucydides/Erlang is still unfinished, I'd rather not put it up for download. However, the above examples and the jones.erl file suggest how a simple simulation might look. I plan to eventually replace the archetype definitions and the fluent queries with domain-specific languages, but until I know the capabilities that will need to be supported, I want to stick with this approach.

Something worth noting is that in about one week's worth of total work I've reproduced every feature of Herodotus/Io, only better-defined, faster, and safer. Having the Io version around for comparison definitely helped, but I feel like the Erlang version will scale far, far better.

The next essay will implement a trivial military simulation. Player involvement will be limited to army formation and the issuance of high-level commands, and the outcome of the fight will be decided by Thucydides's rules of causality.

If there are any questions about the new Herodotus or Thucydides, or about the examples in this essay, please post them in the comments.

Herodotus provides:

• Fluents
  • A Fluent is an {id, selector, persistence, bindings, function, stack} tuple.
    • id uniquely identifies this Fluent.
    • Selectors and Matching
      • A selector is a {fluentType, context, start, end} tuple.
      • Selectors are used primarily for defining and querying fluents.
      • Two selectors "match" if their fluentTypes and contexts match.
        • Two single items match if they are identical, or if either is any.
        • A single item is matched by a list if it matches any element of that list.
        • A list is matched by a single item if that item matches any element.
        • A list is matched by another list if every item in the latter matches an item in the former.
    • Persistence
      • When a Fluent is asked to provide a value after its end-time, it will choose what to do based on its persistence value.
      • If the value is persist, then the value of the Fluent at its end-time will be used.
      • If the value is anything else, then the value will be its persistence value.
      • This provides a mechanism to detect the "death" of specific fluents.
    • Bindings
      • When a Fluent is evaluated, it will be provided a dictionary of bindings.
      • These bindings are configuration for the Fluent, and are guaranteed to be static after the Fluent has been created.
      • This provides a way to provide arbitrary additional data to Fluents at creation time.
    • function is a function of Fluent, Time, and Arguments which returns the value of the Fluent at that time.
      • Fluents are evaluated in forward order by their selectors' set_time.
    • stack is a function of Fluent, Time, Arguments, Stack, Net, and Value which returns the new net value after applying this Fluent's Value.
      • A Stack is a list of {Fluent, Selector, Persistence, Value} tuples in backward order by set_time.
      • After they are evaluated, Fluents are "stacked" together using their respective stack functions, in forward order by time.
• Cancels
  • A Cancel prematurely terminates one Fluent.
  • It effectively sets an end_time for that Fluent at the Cancel's set_time.
  • Cancels also maintain a unique id.
  • Cancelling Cancels is a little tricky: if Cancel-cancels are to be supported, then so must Cancel-cancel-cancels and so on. Since the semantic is unclear, Herodotus does not define it. There are two approaches recommended for applications that wish to counter the effect of a Cancel:
    • Remove the Incident which causes the Cancel. This is suitable when you don't mind a destructive change. This is the easiest and most correct solution.
    • Add a new Incident that sets a Fluent which continues the function of the old Fluent. This must act differently depending on the old Fluent's persist value. This has a slightly different meaning, in that the period of time between the Cancel and the Cancel-cancel will act as an irregularity in the function.
• Incidents
  • An Incident is a unit of historical change.
  • A guiding principle is that an Incident is indivisible and immutable. Nothing should ever corrupt an Incident's value, and an Incident being removed should not damage the History in any way.
  • Incidents contain a payload of Fluents and Cancels.
  • Incidents are set at a particular set_time and maintain a unique id.
  • Incidents also mirror the bindings used in their fluents.
  • To aid simulation frameworks or for self-documentation purposes, Incidents can be granted an isa which maps to some Simulation construct. For instance, a particular Instance might have an isa of "birth", while another has "death".
• Histories
  • A History is a named series of Incidents.
  • Histories can have an Incident added to them. This is called Triggering.
  • Histories can have an existing Incident rolled back.
  • Histories can be queried for the list of Fluents that would match a given Selector, post-Cancellation.
  • Histories can be queried for their value given a Selector and optional additional arguments. These additional arguments will be passed on to the Fluents.
  • Histories can be queried for their Incidents matching a given isa.
• Herodotus
  • A Herodotus process maintains a set of Histories.
  • Herodotus provides a complete external interface to these Histories, but prevents direct access.
  • Herodotus also provides a Transaction semantic.
    • A Transaction is opened automatically when a set of Dependencies is provided with an Incident to be triggered.
      • A Dependency is a tuple mapping from an input Selector to an output Selector.
    • Whenever such a set of Dependencies intersects the set of Dependencies of an existing Transaction, the new Incident will be considered part of the existing Transaction.
    • Whenever a value or fluent query on a selector which intersects an existing Transaction's identifier is received, the query will use the corresponding inflight transaction data.
      • An exception will be made for "external" queries, i.e. those that come from outside the system. These will ignore the intermediate data, and are the reason that the Transaction system is in place.
    • Transactions can be completed, at which point the "hypothetical" Incidents will be triggered.
    • Transactions can be aborted, at which point the hypothetical Incidents will be thrown away.
    • Transactions can involve the triggering of Incidents across several Histories.
    • Multiple Transactions can be active at once.

Although it isn't short, the above specification does completely specify the behavior of a Herodotus system. In particular, note the absence of the Requirements present in Herodotus/Io. After much deliberation, I decided that Requirements should be removed from base Herodotus and moved into Thucydides. Thucydides will also provide a superior set of tools for expressing causal relationships and the handling of paradoxes.

A complete specification for Thucydides is still pending. The above was a refinement of the existing implementations of and test cases for Herodotus/Io and Herodotus/Erlang. A similar process must be used to develop the specification for Thucydides, or the result will be either over- or under-engineered. Accordingly, the next few essays will express a series of text-based games, each showcasing an increasingly advanced simulation environment. Bartle's Designing Virtual Worlds will be used as a reference for such "interesting" simulation.

//First, we need some new metadata for goals:
AskForItemGoal := Goal clone do(
  item ::= nil
  asker ::= nil
  askerTypes ::= list("consumer")
  provider ::= nil
  providerTypes ::= list("provider")
)
GiveItemGoal := Goal clone do(
  item ::= nil
  receiver ::= nil
  receiverTypes ::= list("consumer")
  giver ::= nil
  giverTypes ::= list("provider")
)
//Then later, in our goal creator...
createAskForItemGoal := method(asker, provider,
//In Thucydides, this could be:
//asker desires(now)
  currentDesires := history fluentValue("desires", asker, now)
  if((currentDesires == nil) or(currentDesires size == 0),
//This one is no good, pick a different one
//Other conditions for picking different characters could include
//incompatible alignment, national affiliation, location, and so on.
    newAsker := chooseDifferentCharacter(AskForItemGoal askerTypes, list(asker))
    return createAskForItemGoal(newAsker, 
                                provider)
  )
  desiredItems := currentDesires anyOne
//In Thucydides, this could be:
//SimObject clone setCategories(desiredItems) allActiveInAt(h, t)
  actualItem := history fluentValue(desiredItems, nil, now) anyOne
  AskForItemGoal clone setAsker(asker) setProvider(provider) setItem(actualItem)
)
    

And bam! We get an Item for the Quest that's relevant to the Asker. Now, in the supporting infrastructure, we can spawn in such an Item, perhaps in somebody's inventory or on a spawnLocation in some cave. Perhaps Items have some metadata saying what kinds of places they can spawn in.

About Types

This would be a good place to say something about types in Herodotus and in general. Herodotus uses a very simple mechanism for matching types, where the types requested must all be present in the type matched against. For example, [animal, cat] matches [animal], [cat], and [animal, cat], but doesn't match [animal, dog] or [construction-vehicle, cat]. In the future, Herodotus might use a matching system with rankings, but for now, this is how it works. So, if we define a Donut's type to be [item, food, sweet, round, donut], and if we have a Goal which is looking for a [food, sweet], then the Donut will surely match; but if it's looking for [food, meat], there will be no match. That is, unless there's a Donut clone of type [item, food, meat, round, donut]. In the end, the utility of this type system depends on how consistently it's applied.

Calculated Character Creation

Let's move to a slightly more complex topic: the creation of characters expressly for the purpose of a Scene. This occurs when no existing character is available to fill a role, and it could include, for instance, spawning in the particular Kobold carrying the candles required to fulfill the quest; or it could be the visiting diplomat from another nation. The benefit of doing this with Herodotus is twofold:

• Character archetypes can be chosen from a broad pool, based on the quest, and the archetype chosen can influence the experience.
• Spawned characters, if desired, can be implanted along with their own personal history, provided that history doesn't overlap or damage existing timelines.

To clarify the second point a bit, we'll use the example of the visiting diplomat. Instead of just spawning a "diplomat" at the requisite location, we could also place his time of birth, his nation of origin, his service record, and so on; making him effectively a permanent character that had been there all along. This way, he can be used for other quests later on, and a mystery-solving Scene which required finding out the diplomat's history could be created, too. Mid-timestream insertion is currently dangerous in Herodotus. Future versions will make it safe to use as a general technique, but for now, please just be sure that the fluents placed in the middle of a time stream don't violate the preconditions of later fluents or the invariants of prior fluents.

The synthesis of characters is a complex business; and since I'm preparing for GDC next week, this essay will have to stop here. Hopefully, the approach above shows that the fundamental technique is to query the history, then decide what kind of thing to spawn or use. Future articles will, having explored this path a bit, return to the starting-point and evaluate Herodotus as a service; a Herodotus Simulation Language and Herodotus Query Language will be proposed; and the quest generator will be revisited in a more formal framework. Then, we will explore the application of Herodotus to a game called Stranded, designed by Rob Rix and myself.

If any GDC attendees would like to get in touch with me, please send an e-mail.

About the Simulation

As I understand it, Rboehme's basic approach is to define some terms as follows:

Story

A context in which Quests take place.

Quest

A series of Scenes designed to express a unit of Story.

Scene

A setting involving specific sets of necessary, sufficient, and optional goals.

Character

An entity placed at a specific Location, with a Memory of things which have occurred to him before in the short, medium, and long terms. Also includes a list of Goals which can be used to feed the quest generator, as well as a list of likes and dislikes and a list of relationships to other Characters.

Role

Provides a list of Goals that a Character fulfilling that Role can choose from. For instance, a Priest might choose the "Peaceful Resolution" Goal for the "Ender of the Brawl" Role, whereas a Barbarian might choose the "Pacify By Force" Goal. Also includes information about whether the Character is a major, minor, or walk-on personage. These Roles and their Goals drive AI behavior or PC options.

Goal

An abstract Goal (ROLE brings ITEM to ROLE, ROLE compels ROLE to ACTION, ROLE removes ROLES from AREA, etc). Goal slots are filled with Roles provided by the Scene.

For example, in a standard "fetch quest", the first scene, or Start, of the Quest would include the part where the player approaches the NPC and asks for a mission. Its Goal would be ROLE asks ROLE for REQUEST, with the Roles being CUSTOMER and DELIVERYMAN respectively, and the REQUEST being for a particular ITEM. This ITEM would be determined by the CUSTOMER's Location, likes/dislikes, and other attributes. This Goal would be part of the "Customer" Role, and the "Deliveryman" (our player) must wait for it to happen. It might happen as part of conversation, or the distraught NPC might run up to the player and demand help.

In turn, this Scene would seed the Goal for the next Scene: ROLE brings ITEM to ROLE, with DELIVERYMAN and CUSTOMER being the Roles in order this time, and the ITEM being the one previously decided. It is in this next scene, Finish, that the traditional MMO fetch quest takes place as the player completes that goal.

If this seems like a lot of work for a simple fetch quest, that might be excused; but consider that this description is not just one fetch quest, but every fetch quest. By varying the ITEM and its Location (or Owner), or by using an ITEM which requires some special preparation before it can transform into the "true" ITEM, all kinds of fetch quests can be produced. The primary benefit of quest synthesis is that you can script the variation into the objects, rather than into the quest itself.

In terms of an overarching Story, the player's perceived Goal can shift radically from Quest to Quest depending on the Goal used to reach completion at a given Quest. If this Goal is a "failure"-like Goal, that has ramifications on what Quests are available afterwards; if it's a success and a part of a chain, the future Quests themselves continue the theme.

In Terms of Herodotus

Now, we'll rephrase these building blocks of Rboehme's quest simulation as Herodotus constructs, building a quest where a farmer wants a donut from the player. A delicious donut is hidden in the nearby cave, but a passable donut is available on the farm itself. Once we've met the requirements of Herodotus, we'll again recast the simulation as Thucydides entities, just to show how the process works.

We'll build from the simplest components of the system up to the most complex ones.

Location, location, location

First, we'll place the static tokens in the world. A complete implementation would include a large number of Locations for quests to take place in, or Characters to live in, but for now we'll make do with three: Nowhere; a Farm; and a Cave. To implement these in straight Herodotus, we would say something like this:

history := History clone

Location := Object clone
Nowhere := Location clone
CreateNowhere := Incident clone do(
  setFluent(FAppendContext create(list("locations", "nowhere"), Nowhere))
  setTime(0)
)
CreateNowhere occurIn(history)
//And later, in our quest generator...
Farm := Location clone
Cave := Location clone
CreateFarm := Incident clone do(
  setFluent(FAppendContext create(list("locations", "farms"), Farm)) 
  setTime(0) 
)
CreateCave := Incident clone do(
  setFluent(FAppendContext create(list("locations", "caves"), Cave)) 
  setTime(0)
)
CreateFarm occurIn(history)
CreateCave occurIn(history)
  

In Thucydides:

history := History clone
//Go ahead and use this history for all SimObjects
SimObject setHistory(history)

Location := SimObject clone appendCategory("locations") setSpawnTime(0)
Nowhere := Location clone appendCategory("nowhere")
Nowhere spawn
//And later, in our quest generator...
Farm := Location clone appendCategory("farms")
Cave := Location clone appendCategory("caves")
Farm spawn
Cave spawn

From here, we can still do all the usual Herodotus queries on that History; spawn just triggers an Incident, after all.

Things and Stuff

Continuing with the simple pieces, let's consider Items next. Items can provide arbitrarily complex goals, but for now we'll treat Items as tokens to be grabbed. For now, we'll just make two Donuts of differing quality. In raw Herodotus:

Item := Object clone do(
  categories ::= list("items")
)
//And later, in our quest generator...
Donut := Item clone do(
  categories := list("items", "donuts")
//On a scale of 1-10
  baseQuality ::= 5
)
LousyDonut := Donut clone setBaseQuality(2)
TastyDonut := Donut clone setBaseQuality(8)
CreateDonut := Incident clone do(
  donut ::= nil
  loc ::= Nowhere
  setFluent(FAppendContext create(donut categories, donut))
//Establish the donut's start-position and initial quality
  setFluent(FReplaceConstant create("location", donut, loc)
  setFluent(FReplaceConstant create("quality", donut, donut baseQuality)
//Donuts degrade as time goes on.
//If one unit of time is one hour, a donut is absolutely bad
//after 24 time units, or one day.
  setFluent("quality", donut, h, t, 
    ((1 - (t - time)) / 24) max(0)
  ) stackBy(MultiplyNumber)
  setTime(0) 
)
CreateDonut clone do(
  setLocation(Farm) 
  setDonut(LousyDonut)
  occurIn(history)
)
CreateDonut clone do(
  setLocation(Cave)
  setDonut(TastyDonut)
  occurIn(history)
)
  

And in Thucydides:

Item := SimObject clone appendCategory("items")
//And later, in our quest generator...
Donut := Item clone appendCategory("donuts") do(
  setQuality(5)
  setLocation(Nowhere)
//Intrinsics are a list of Fluents that go hand-in-hand
//with a SimObject and are applied as soon as it spawns.
  intrinsics := list(
//Donuts degrade as time goes on.
//If one unit of time is one hour, a donut is absolutely bad
//after 24 time units, or one day.
    Fluent create("quality", self, h, t, 
      ((1 - (t - time)) / 24) max(0)
    ) stackBy(MultiplyNumber)
  )
)
LousyDonut := Donut clone setQuality(2) setLocation(Farm)
TastyDonut := Donut clone setQuality(8) setLocation(Cave)
LousyDonut spawn
TastyDonut spawn
  

The fascinating trick in this example is the way the "setQuality" and "setLocation" calls work. Note that those methods aren't defined on Item or Donut or, indeed, on SimObject! So, how are they resolved?

They are handled by SimObject's forward(), which deals with unrecognized messages, and the rule they use is as follows: If the message starts with "set", remove the "set" and treat the lowercase name as a fluent type. If the object hasn't spawned yet and no time argument is provided, append to the Intrinsic Fluents an FReplaceConstant Fluent with the given fluent type and using the SimObject as context. If the object has spawned already, require a time argument in the first position. If there's a time argument, create and apply a new Incident using an FReplaceConstant Fluent. SimObject's forward mechanism works similarly for messages beginning with "add", "subtract", "multiply", "divide", "append", and "remove". This removes the need for a lot of very similar Herodotus API uses.

Note that these only create one-way links - if you take two SimObjects A and B and perform A appendFriend(B), a fluent of type friend will be created with the context {A} and a result list containing B. The reverse relationship will not hold. If Friendship is always two-way, then it might be reasonable to create a Friendship Relationship and attach both A and B to it via something like Relationship clone appendCategory("friends") setParticipants(list(A, B)) setStrength(0.5). Relationship is a Thucydides SimObject clone which is responsible for maintaining simple relationship statuses between a group of SimObjects. It's very simple, but it provides a nice single point of use. A Relationship's participants, strength, and other slots are, of course, time-based, mutable, and queriable as usual.

Goals and Roles

Here is where we need to think a little more about what we're doing, exactly. A Scene's Goal is a test of whether some conditions are met. There are several ways we can express this:

• An Invariant on a Scene. If a Goal is met, the Scene ends. This means that subsequent Scenes must handle any "mess" that results from a Scene ending abruptly. This is the only way that Herodotus can automatically handle Scene endings.
• A plain Object property of a Scene and of various Roles. As actions are performed and Incidents are generated and added, check to see if any Scene's Goals are met. If so, permit them to terminate gracefully.
• As above, but instead creating a Goal SimObject and associating it through Relationships with a Scene.

The difference between the first two and the last one is whether Goals are mutable during a Scene. This comes down to a question of whether a "changing goal" means "an alternate goal that was always available", "the goal of a new scene triggered by the 'failure' of this scene", or "an actual shift in goals of the same scene". Personally, I think the middle option is the best, and a Quest can potentially be many Scenes in a row, with each Scene having one static set of goals. So, if the goal "shifts" from Player delivers the Letter to the Captain to Player reports to the Captain that the Letter has been destroyed, what actually occurred is that the Goal Player discovers the Letter's destruction was achieved, which ended the first scene and segued into the second scene, which included a primary goal of Player reports to the Captain that the Letter has been destroyed. Fluent-driven objects are powerful, but add complexity. If it's possible to simplify the model by making certain parts static, feel free to do so.

Now then, let's express two Goals: Farmer asks Player to bring him a Donut and Player delivers a Donut to the Farmer

//This is a barebones Goal with a very simple completion check.
//There's no reason Goals couldn't check certain fluent values
//on their Roles, or other arbitrary behavior.
Goal := Object clone do(
  availableTime ::= 0
  satisfiedInAt := method(h, t,
    h fluentValue("satisfied", self, t)
  )
)
AskForItemGoal := Goal clone do(
  item ::= nil
  asker ::= nil
  provider ::= nil
)
GiveItemGoal := Goal clone do(
  item ::= nil
  receiver ::= nil
  giver ::= nil
)
//And later, in our quest generator...
AskForDonutGoal := AskForItemGoal clone do(
  setItem(Donut) 
  setAsker(Farmer) 
  setProvider(Player)
)
GiveDonutGoal := GiveItemGoal clone do(
  setItem(Donut)
  setReceiver(Farmer) 
  setGiver(Player)
)
    

The above example actually looks identical in Thucydides. This is to be expected, since none of this uses Herodotus. Now, just to illustrate a fancier satisfiedInAt condition, we'll show what would happen if the GiveItemGoal were to check for evidence of a Transaction between the giver and receiver involving that item.

Transaction := Object clone do(
  aItem ::= nil
  bItem ::= nil
  aParty ::= nil
  bParty ::= nil
  aItemCost ::= 0
  bItemCost ::= 0
  time ::= 0
)
//...
//This is just an example of a complex goal in GiveItemGoal.
//It could just as easily have been done on the accomplishing side
//by manually setting "goalSatisfied".
  satisfiedInAt := method(h, t,
    h fluentValue("transactions", nil, t) detect(i, v,
//Make sure this transaction is from the giver to the receiver,
//that it involves the right item type, and that it happened after
//the goal became available
      (v aParty == giver) and(
        v bParty == receiver) and(
        v aItem categories containsAll(item categories)) and(
        v time > availableTime
      )
    )
  )
  

And, in Thucydides, a couple of small changes:

Transaction := SimObject clone do(
  appendCategory("transactions")
//These are all static, so we don't need to change them,
//which means they're "real" slots and not Fluent slots.
  aItem ::= nil
  bItem ::= nil
  aParty ::= nil
  bParty ::= nil
  aItemCost ::= 0
  bItemCost ::= 0
//Time is covered by the SimObject.
  //time ::= 0
)

  satisfiedInAt := method(h, t,
//Make sure this transaction is from the giver to the receiver,
//that it involves the right item type, and that it happened after
//the goal became available
    Transaction allActiveInAt(h, t) detect(i, v,
      (v giver == giver) and(
        v receiver == receiver) and(
        v item categories containsAll(item categories)) and(
        v time > availableTime
      )
    )
  )
    

There's not much to be gained in this specific case from using this feature, though, so we'll stick with the simpler version above. As for actually fulfilling these goals, that can be done in places like the hypothetical giveItem() or converseWithNPC(), or some other place. There, too, we can record in the receiving character's inventory fluent the receipt of the good or the bad donut, and even influence their mood based on how good a donut it was.

Next, let's introduce Roles. A Role, for a Scene, includes a set of Goals, a list of characters, and some metadata. In the Scene where an Asker asks a Provider to bring him an Item, the Asker Role would have a single Goal, which is within the Scene's ending goals, and the Provider would have none, except implicitly to be asked about bringing the Item. The Item is chosen from among the likes or needs of the Character fulfilling the Asker Role.

We'll express Roles, too, as static data, and assume that once a Character is set on a Role, he won't switch or lose that Role for the duration of the Scene.

Role := Object clone do(
//Categories are metadata about the sort of role it is.
  categories ::= list()
//The characters slotted into this role.
  characters ::= list()
//Those goals that the characters should want to fulfill
//to properly execute this Role.
  goals ::= list()
)
//And later, in our quest generator...
//Scene one:
DonutAsker := Role clone do(
//This "consumer" category means "someone who takes something in"
  setCategories(list("consumer"))
//In other words, it's the Farmer in this Scene.  Generally, a Category
//is like a meta-Role that spans the whole Scene.
  setCharacters(list(Farmer))
  setGoals(list(AskForDonutGoal))
)
DonutProvider := Role clone do(
//The Provider is "someone who supplies something to a consumer".
  setCategories(list("provider"))
  setCharacters(list(Player))
)
//Scene two:
DonutReceiver := Role clone do(
  setCategories(list("consumer"))
  setCharacters(list(Farmer))
)
DonutGiver := Role clone do(
  setCategories(list("provider"))
  setCharacters(list(Player))
  setGoals(list(GiveDonutGoal))
)
    

Easy enough, and identical in Thucydides, since we assume that Roles are, basically, unchanging tokens.

Building Character

Since this example is already running long, we'll make Characters as simple as possible: a list of desired items and a location. In a full implementation, we'd include personal goals, memories, and so on, but for now we don't want to make it seem like I'm being paid by the word. We'd like Characters to move around and shift their desires, though, so let's go ahead and see that in Herodotus:

Character := Object clone
CreateCharacter := Incident clone do(
//Initial state.
  desires ::= list()
  location ::= Nowhere
  character ::= nil
  setupFluents := method(
//As usual, add the context...
    setFluent(FAppendContext("characters", character))
//Then add the initial state, like desires, and
//link it to the character...
    setFluent(FReplaceList("desires", character, desires))
//Add the location too
    setFluent(FReplaceConstant("location", character, location))
  )
)
//And later, in our quest generator...
Farmer := Character clone
Player := Character clone
//Remember, this is an Incident.
CreateFarmer := CreateCharacter clone do(
//The Farmer wants donuts
  setDesires(list("donuts")) 
//and he lives on the Farm
  setLocation(Farm) 
//and he's represented by Farmer
  setCharacter(Farmer)
)
CreatePlayer := CreateCharacter clone do(
  setLocation(Farm)
  setCharacter(Player)
)
CreateFarmer occurIn(history)
CreatePlayer occurIn(history)
    

In Thucydides:

//Thucydides makes this much smoother
Character := SimObject clone do(
  appendCategory("characters")
  setLocation(Nowhere)
  setDesires(list())
)
//And later, in our quest generator...
Farmer := Character clone do(
//Fluent appending works on a whole list at once, so it uses
//the plural.  Sorry, but it was the easiest way to do it
//with the forwarding mechanism.
  appendDesires(list("donuts"))
  setLocation(Farm)
)
Player := Character clone do(
  setLocation(Farm)
)
Farmer spawn
Player spawn
    

Note the use of "appendDesires", one of the forward-handled methods from before.

Making a Scene

The Scene level is the first place we see tying together all these independent objects. Recall that a Scene has a set of Roles and some Goals, and if certain of those Goals are met the Scene is concluded. Fortunately, scenes are static! There's nothing in a Scene that must vary with time.

Scene := Object clone do(
//The roles appearing in the scene
  roles ::= list()
//The goals that, when any are accomplished, satisfy the scene
  finishGoals ::= list()
//A list of blocks of the form (scene, oldScene, h, t)->bool
  preconditions ::= list()
//Delegate finished status to goals
  satisfiedInAt := method(h, t,
    finishGoals detect(i,v,
      v satisfiedAtIn(h, t)
    )
  )
//Is it valid to segue into this?
  canSegueFromInAt := method(oldScene, h, t,
//If any precondition block forbids it, fail to segue
    preconditions foreach(i,v,
      if(v call(self, oldScene, h, t) not,
        return false
      ))
    )
//Otherwise, segue away
    true
  )
//Pick the roles that match the given categories
  rolesFor := method(categories,
    roles select(i, v, v categories containsAll(categories))
  )
//Set up role characters based on previous scene's roles
  segueFromInAt := method(lastScene, h, t,
//You could do other stuff in this method too, like set fluents
    lastScene roles foreach(i,v,
      rolesFor(v categories) foreach(i2, v2, 
       v2 characters appendSeq(v characters)
      )
    )
  )  
)
//And later, in our quest generator...
SceneOne := Scene clone do(
  setRoles(list(DonutAsker, DonutProvider))
  setGoals(DonutAsker goals)
)
SceneTwo := Scene clone do(
  setRoles(list(DonutReceiver, DonutGiver))
  setGoals(DonutGiver goals)
  setPreconditions(list(
    block(scene, oldScene, h, t,
//Ensure that the question has been asked.
//For now, we only have these two scenes, so it doesn't matter,
//but this way shows how scene chaining like this might be done.
//In other words, "ensure that the goal which was accomplished was
//the ask-for-things goal".
      askGoal := oldScene rolesFor("consumer") first goals first
      h fluentValue("satisfied", askGoal, t)
    )
  ))
)
    

This might be all that's needed of a Scene. The important part is that Scenes are fairly self-sufficient - they look into the previous scene to see if they can execute, and to grab the characters they need for their roles. Note that the item involved between these scenes is encoded into the goals themselves.

At this point, one might be justified in saying that it's sleight of hand to simply provide these "And later..." definitions, but in the next essay, I'll show how these might be generated.

Quest and Answer

A Quest, recall, is a series of Scenes. Since Scenes handle their own entrances, and the change of currentScene over time isn't really important to track, Quest can be fairly simple:

Quest := Object clone do(
//All the Scenes that might show up in this Quest.
  possibleScenes ::= list()
//All the Scenes that count as endpoints for the Quest.
  finaleScenes ::= list()
//The currently active Scene.
  currentScene ::= nil
//The Scenes that have been played.
  completedScenes ::= list()
//Housekeeping.
  init := method(
    setCompletedScenes(list())
    self
  )
//Pick and segue to the next Scene.
  chooseNextSceneInAt := method(h, t, 
//Bail if we're in the middle of a Scene.
    if(currentScene satisfiedInAt(h, t) not, return false)
    if(satisfiedInAt(h, t),
      return true
    )
    available := possibleScenes select(i,v,
  completedScenes contains(v) not and(
   canSegueFromInAt(currentScene, h, t)
  )
 )
    completedScenes append(currentScene)
//We can choose randomly here, but a real implementation
//would be smarter and replace the simple 'canSegue...' with
//some numerical value for how good a match it is.
    next = available anyOne
    next segueFromInAt(currentScene, h, t)
    setCurrentScene(next)
    true
  )
  satisfiedInAt := method(h, t,
    finaleScenes contains(currentScene) and(
      currentScene satisfiedInAt(h, t)
    )
  )
)
//And later, in our quest generator...
DonutQuest := Quest clone do(
  setPossibleScenes(list(SceneOne, SceneTwo))
  setFinaleScenes(list(SceneTwo))
  setCurrentScene(SceneOne)
)
//And somewhere in our game code...
while(
//...
//Try picking the next Scene.
//If it returns true, something happened.
   if(currentQuest chooseNextSceneInAt(h, t),
//Is the quest over?
     if(currentQuest satisfiedInAt(h, t),
//The quest is over!
       startNextQuest()
       ,
//We must have a new scene...
       handleNextScene()
     )
  )
//...
)
 

I say that the currentScene isn't important to track historically because what's important about a Scene happening in a Quest isn't the Scene itself, but the Fluents that are set as the Scene transpires. Also, the stuff in the "game code" section above could be much nicer and written much differently - I just present it as a naive approach to using this kind of data.

So where does Herodotus really come in? That would be in the Character memories, Goal tracking, quest histories, next-Scene picking, Scene conclusion, and so on. Storing this information in Herodotus makes it a lot easier to write fancier quest generators, design better NPC simulations, and provide ays for Character actions to materially change the game world.

In the next essay, we'll look at how to generate these Donut quests and we'll make a simple text-based adventure game using Thucydides.

Thanks to Rboehme and the other participants in the questgen project.

If they all seem a bit similar, that's because they all reflect the basic principle of player-driven content: Record enough information to give players meaningful experiences. Those four categories contain most of the really thrilling features that a system like Herodotus can help provide. Even if a game doesn't use Herodotus for any of the "hard" simulation like politics or economics, employing simple player-tracking metrics can be extremely useful. Imagine: the designer can detect and solve player boredom at runtime! Whether this is an online game, where the data collection is viewed by a human, or an offline game, where the data is acted on by the system, Herodotus provides a unified interface for player data collection, and expresses it in the same way as the simulation's time-based data storage. You can track popular and unpopular items or skills or quests, easy and hard dungeons and monsters, all in a straightforward and consistent way.

Scales of Justice

Easy and Hard settings just don't do it for me anymore. I want to be "Hard", but too often "Hard" just means "we turned up the numbers so it takes five minutes to kill the first enemy." I want to experience content, but "Easy" doesn't feel like a challenge - it doesn't get me involved. Even worse, sometimes I'm in the mood for a masochistic old-school challenge, and sometimes I just want the game equivalent of knitting to pass the time. It's about time to drop the traditional idea of static difficulty levels.

While Herodotus can't scale your game's difficulty for you, it can provide a framework for your own difficulty scaling algorithm. For a platformer such as Super Mario Bros., you might define a kills fluent to keep track of the deaths and killers of various creatures, including the player. The context of such fluents might be something like {victim, killer}, and killers can be things like "Third Goomba collision of World 1-1 at x=14", "Pit fall in World 2-3 at x=30", "Player jumping on head in World 3-1 at x=17", "Shell of Koopa Troopa 2 kicked by Player in World 4-1 at x=9". In other words, a tuple like {actor, action, area, location}. It's easy enough to add a little Incident that sets Fluents like these every time an entity dies. Through the course of a Mario game, that's surely under a thousand Incidents, which is hardly many at all. And once your game has collected this information, it can act on it.

For the Mario example above, we could insert some logic like the following on each player death: "If the player died at roughly the same spot as last time, drop a One-Up out of the sky so that he might find it. If the player died at roughly the same spot for the last five times, see what the most common cause of death was. If it was an enemy, remove or slow down that enemy. If it was a pit, provide a Koopa Troopa flying over that pit to jump on." And so on. Similarly, if we checked Goomba deaths and saw that every Goomba died within a few x-units of its starting position, we might make Goombas move more quickly or change directions more often, or try some other simple machine learning trick. These small modifications would have significant consequences on the difficulty curve of Super Mario Bros., of course, and would have to be carefully tuned to avoid exploitation.

It's worth noting that Gradius has always used a Rank system whereby players with high point totals or powerful weapon loadouts would be presented with tougher challenges at a given point in the stage, or tougher stages, than a weaker player. Zanac, too, gave players with better powerups and more violent approaches a harder time. These are proof that automatic difficulty scaling can still provide an extremely difficult game, and also that difficulty scaling doesn't need to take up much in the way of processing power: both games had strong showings even on the NES.

Where the hard part of automatic difficulty scaling comes in is the way challenges are scaled. Some game systems will need to include data with the challenge itself on how to scale it - for instance, varying difficulties of puzzle for a particular "puzzle" challenge. Others will be able to use algorithmic scaling techniques as described in the Mario example above. Most will fall into a hybrid class where many aspects of difficulty can be modified invisibly and algorithmically, and the rest can be handled as special cases. In any event, Herodotus can provide the information those systems need to do their work, and can receive feedback from those very systems to improve the accuracy of their difficulty predictions.

Supply and demand

In role-playing games such as Suikoden, where a player assembles a fairly large army and outfits them, local economic conditions stand a chance of being strongly impacted by player purchases and sales. But the games don't seem to collect or use much information about player economic activity. Might it not be fun to be able to play a local economy by introducing shortages or surpluses or substitutable goods, and profiting from that?

Herodotus won't simulate your economy, but it can provide you a framework for your own economics algorithms. In the case of sales to and purchases from a merchant, we could provide a trade fluent with a context like {purchaser, seller, good}, as well as a stock fluent with a context like {good, owner, location, amount}, along with a value fluent with context {good, seller, value}. Finally, we want sale-markup and purchase-markup fluents with context {good, buyer, seller} The trade and stock fluents are easy to update on purchases, acquisitions, and sales.

The algorithm for value could look a bit like this: "Start with the good's base value; If we have fewer in stock in this location than a certain threshold, increase the price by a function of that difference; If we have other, similar goods, and a shortage of this good, increase the value of this; If we have a shortage of another similar good, but a surplus of this, reduce the value of this;" and so on. the two -markup fluents could be a function of the relationship between the seller and buyer, the availability of other shops in the area, and so on. In other words, value is the value that the merchant believes an item has, and the -markup fluents are the multipliers he's willing to sell or buy at. For instance, a weapon shop owner might not have interest in a particular herb, or you might have learned that this shop owner really likes that herb; it gives a lot of depth to the choice of whom to sell to or buy from. We should banish the days of selling pounds of zombie flesh at great expense to pie makers, unless it makes narrative sense!

This is a pretty simple strategy, but I think that it could add a lot of depth to what's normally an extremely boring and braindead aspect of a role-playing game. It also provides room for a lot of related systems like bribery, gifts, friendship with and between NPCs, inter-store trades, and so on. I'm reminded of the third chapter of Dragon Quest IV in which the player must tend a weapon shop while his boss is out. Later in that chapter, in a different town, you acquire weapons and give them to your wife, the keeper of your own shop, to sell at a markup. I would have loved to play an entire game of this.

Fight or flight

In Super Mario Bros. 3, there are two main solutions to most levels: Run along the ground or fly through the air. Generally, there are enough choices of level to pick a mainly sky-friendly or a mainly ground-friendly path through a stage, but what if I just want to make a game of flying? Wouldn't it be nice if the game could pick up on my love of flight and provide more flight-surmountable obstacles, and more challenging flight paths?

Herodotus can't redesign your platforms, but - and this will sound familiar - it can provide you with the data your system needs to pick appropriate challenges to your player. By recording takeoff and land fluents, and measuring the time between them, as well as the number of takeoffs, you can get a reasonable idea of the number of times flight was used and for how long.

After collecting various data on this, and comparing it to the expected values, you can start to give more long runway platforms, wider gaps between platforms, more midair obstacles and enemies, and more rewards available only to flyers, as well as more flight powerups. We should let the player play the game he likes! Conversely, if the player never uses flight, we can either encourage him to use it (by providing a well-scaled set of flight challenges) or we can give him stronger platform-jumping and enemy-stomping experiences. Playtest and tune your game forever.

Give the people what they want

Most players of a class-based RPG have had the experience, as a mage, of finding the game's most incredible and overpowered and ridiculous broadsword - and being utterly unable to make anything of it besides a trophy, while your own staff and spellbook are showing the nicks and wear of the last twelve character levels. By weighting loot tables according to what players actually use, we can get rid of a lot of the irksome junk that just gets vendored. We don't need to do this by letting Barbarian enemies drop superior spells; we can just make the items that were going to drop anyway more likely if a party member can use it. That's an old trick, but Herodotus can take it one step further: don't go by player ability only, but also by player preference.

Herodotus can't weight your loot tables, but - all together now - it can provide your game with the data it needs to do so. Or to remove its loot tables entirely, though that's a topic for another article. For now, we can create a preference fluent with a context {item, timesUsed}. Further, an item could be a tuple like {itemID, category, ...}. Whenever an item is used, whenever an enemy is attacked with a skill, &c, an Incident can be triggered (or, if you so desire, several such events can be coalesced into a single Incident) to update the corresponding preference fluent.

When a treasure is opened, or an enemy is slain, or a shopkeeper offers a rare item, this preference fluent can be checked to try and find a suitable item for maximizing player thrill and enjoyment. Or, if you feel like the player should try other things once in a while, you can give him something entirely different. Herodotus doesn't make the rules! It just provides them with the data.

But wait, there's more...

These are just a few techniques for using player data to customize and improve your gameplay. Furthermore, player data collection is just a small subset of the data collection and historically-driven simulation possible with Herodotus. Designing standard narrative systems as interactive simulations - or movements between interactive simulations, as in a string-of-pearls narrative - can vastly improve the narrative structure, and make the act of playing much more natural, personalized and communicative.

One goal of Herodotus is to remove lazy randomness from games.

The theory

By expressing "things which can occur" as incidents to placed in a historical timeline, Herodotus provides a unified means of modifying the game world in response to player, NPC, or intrinsic simulation actions("incident sources"). Incident sources can trigger wholly self-contained incidents according to deterministic or even random criteria, and Herodotus can track the changes to the environment implied by each incident. In fact, queries can be made at any time period, even in the "past".

Herodotus defines three primary concepts: Fluents, Incidents, and Histories. A Fluent is a function of a history, a time, and arbitrary additional parameters, and is associated with one or more "fluent types" and "contexts". In other words, it's "Something which is true for some context at a given time". Fluents are set in groups by Incidents, which also express preconditions and invariants. A History is a series of Incidents, allowing queries into the Fluents which are active at a given time. Queries can be made on fluent types and contexts, and the results that are returned depend on the Fluents involved. The following few sections describe these concepts in greater detail, but those looking for examples can skip ahead.

Fluents

A Fluent is a value parameterized by at least history and time, matching some set of "fluent types" and "contexts". Fluent types represent a category of Fluents. For example, there might be fluent types such as nobles, trade-routes, quantity-of-food, friendliness, neighbors, and so on. The context of a Fluent depends, in some sense, on the type. The context of a fluent of type wars would include at least the information to identify the War involved. A fluent establishing a trade route would have, as its context, the nations and goods involved in the route, perhaps encapsulated in a "Trade" object. In other words, the context is the data required for a Fluent to perform its calculations. When Fluents are queried, the query consists of a set of fluent types and contexts, along with a history and time. All Fluents matching any of the involved fluent types are used if their contexts also appear in the context list, and the Incident triggering them occurred after the given time. Empty lists match "all". One final note on the static properties of Fluents: In Herodotus, Fluents don't have access merely to their own contexts, but also the contexts of their Incidents. This is mainly for convenience, and has no significant impact on the semantics.

Fluents also take dynamic parameters, which consist at least of history, h, and time, t. While a population Fluent might only be parameterized by time for an exponential model, a height fluent for a heightmap-driven terrain could include (x,y) parameters. This is a nice way to reduce the number of Fluents, where applicable. Imagine if each entry in a heightmap had to be embodied by a unique Fluent! In this fashion, not only is efficiency obtained, but the fidelity is improved. Another clever use of t is for a Fluent which "lies latent" until or after a given time. For instance, a fluent may be defined piecewise: Doing nothing for the first 10 time units after starting, then increasing linearly for 100 time units, then increasing exponentially for the next 10 time units, then immediately going to 0. As for the history, h, this is provided so that Fluents can calculate values based on Fluents that match some other criteria. This is an advanced technique which opens up the possibility of infinite loops, so it shouldn't be used except in extreme cases.

When the values of multiple Fluents are to be combined, their respective StackModes are used to combine their results. Example StackModes include simple replacement, numerical addition and subtraction, list appending and removal, and so on. StackModes have access not just to the value of the Fluent which employs them, but also the value of the rest of the stack "underneath", that is, earlier in time. The StackMode can use that value or discard it. A Fluent which relies on previous values to calculate its own might even do most of its heavy lifting through its StackMode. Taking a population model as an example, a Fluent which does a mathematical operation on the "base population" defined by the previously occurring Fluents might return, as its value, the parameters for that operation. Its custom StackMode would then take those parameters and apply the operation to the "prior value", returning the result.

Fluents are the unit of information stored in a History.

Incidents

An Incident is a sort of container for Fluents, used by the application to group and configure related Fluents caused "at once" in time. Incidents also allow for preconditions, which are functions of a History, and invariants, which are functions of a History and a time. Incidents can also terminate previously applied Fluents, and they are further responsible for expressing their own inverses. For instance, the inverse fluent of an Incident which established a trade route between two nations might be the dissolution of that route(the invariant being that there is an accessible land route between those nations; a flood or earthquake might end the contract).

Incidents are created by the application. An application might have a "PersonBorn" incident which sets various fluents related to the birth of a human, and which is configured with properties such as the person's name, parentage, and so on. The application could create several PersonBorn Incidents and trigger them all at various times, choosing which to trigger based on the ages and marital status of the parents and other concerns.

Incidents are the unit of application influence over a History.

Histories

In a sense, a Herodotus History provides a fluent database - it becomes the data store against which the application queries. For instance, questions like "Are there any mountains nearby?" or "What is the height above sea level at (42° 40'N, 73° 45'W)?" can be asked of a History, provided that the Fluents to supply those data have been defined, and that Incidents have triggered them. A History maintains a collection of Incidents which have occurred within it, and verifies that new Incidents can occur according to their prerequisites. When a new Incident is inserted, the History goes through the invariants of prior events and the prerequisites of future events to ensure consistency. If an invariant is violated, the new Incident also sets the violated Incident's inverse fluents.

Herodotus is intentionally very slim. All of the actual shape of the simulation - which Incidents are defined, when Incidents can occur, the resolution of the simulation, and other concerns are left out on purpose so that Herodotus can be as general as possible. It's quite feasible to use Herodotus as a completely static storytelling tool, merely making use of its ability to maintain a story's consistency, or to provide a unified way to check triggers and quantities. It's also possible to use multiple Herodotus Histories, and eventually collapse such a timeline into a single event. For instance, a new History might be created for a random battle in an RPG. The initial Incidents would set up the participants in the battle; subsequent Incidents could be placed for each action chosen by the player or monster. Player and monster stats would be Fluents in this History. Once the battle is over, the History can be analyzed by the application, and based on how well it went, a simpler Incident could be placed in the "real" History. If desired, this Incident could even refer to that History! In this way, the simulation can reach an arbitrary level of detail, yet remain reasonably efficient at each level.

Histories are the distinct stores maintained by Herodotus.

An example

For instance, here is a series of Herodotus incidents:

• IncidentType=PersonBorn Person=P730109 Father=P13024 Mother=P12049 Time=1370
• IncidentType=PersonTrained Person=P730109 Teacher=P10123 Specialty=S7 Time=1383
• IncidentType=WarStarted War=W7 Attacker=N1 Defender=N2 Time=1390
• IncidentType=PersonJoinsArmy Person=P730109 Army=A7 Reason=R4 Rank=K7 Unit=U512 Time=1391
• IncidentType=BattleWonByDefender Battle=B18 War=W7 Place=C197 AttackingUnit=U213 DefendingUnit=U512 Time=1396
• IncidentType=PersonPromoted Person=P730109 Rank=K8 Time=1399

In 1370, Richard Richardson III was born to the well-regarded painter High Duke Richard Richardson II and High Duchess Rachael Greaves-Richardson. At age thirteen, he undertook extensive training in tactics under Swordmaster Silvas. A year after the start of the War of the Black Cyprus in 1390, Richardson joined the Queen's Army at the rank of Commander due to his father's influence, and was assigned to the Ninth Golden Sabre Regiment. When the First Rofon Hills Battle took place in 1396, Richardson's unit defended against the onslaught, which, among other exploits, granted him a promotion to Captain in 1399.

To attain the above goal, all that's required of the application, besides the simulation itself, are random name generators, texts associated with different incident types, and a slightly clever way to display a lis