Joe's Landfill

Justifying Blank Space

2008-09-20T16:43:00.005-04:00

An Extended Absence

To all of those coming to this site from my AGDC business cards, I apologize for the dust!

This blog has been idle for some time, though I have been anything but. Over the summer, I toured California, taught a course on game design and development, worked on an iPhone game, enrolled in the Metaplace beta, attended Austin's GDC, and started applying for graduate schools and careers. I've further developed my interests in narrative and games criticism (thanks in no small part to Roger Travis and my sudden, unexpected membership in the IGDA Game Writers' SIG), and I'm working on a blog redesign. I'm also designing a second iPhone game with the inestimably keen Rob Rix.

The coming weeks will see a brand spanking new layout, a retiring of the old, inscrutable essays, and a few hopefully excellent new works. The new theme is "four colors", and the four categories are games criticism, game design, procedural content (especially narrative), and published works (my own). Each color is like a separate blog, but they will be aggregated on the main page. I intend to approach the purity of Action Button, even if my voice is less, shall we say, high-contrast.

So, thank you for visiting, and please come back soon. In the meantime, feel free to leave comments or e-mail.

Rock, Paper, Scissors

2008-04-29T09:00:00.001-04:00

This is an essay in the Rewriting History series. Please read at least Introducing Herodotus and Rewriting History before proceeding.

The challenge

Show the causality features of Thucydides by designing a simulation that "runs itself" for a while after initial user interaction. The simulation is a simple rock/paper/scissors military simulation in the style of Fire Emblem. The player issues commands at the 0th hour of the day, and the enemy responds in kind. The armies of the player and enemy clash hourly as long as daylight and their respective forces hold. While I won't show the line-by-line Erlang code as before, I'll provide the commented Erlang source code for the curious.

A War of Attrition

Since creating a full strategy game was beyond the scope of this exercise, I wanted to focus on two moderately tricky aspects:

Defining a fluent whose value is a function of its past value
Triggering events automatically

This essay will explore each in turn. But first, the rules of the system must be described:

The player and enemy begin with the same number of troops in three categories: Swordsman, Spearman, and Axman.
The player's action at the beginning of each day is to choose how many of each type of unit to include in his advance for that day. He is limited to 50 units per advance.
The enemy employs a psychic, but he is a poor strategist; so he'll send at you the worst possible counter to whatever you send at him, provided he has the troops available.
Once daylight comes (eight hours into the day), the two advances will meet and begin skirmishing.
The two forces will skirmish hourly until one or both sides drop, or until dusk falls.
Swords are strong against axes and weak against spears; axes are strong against spears and weak against swords; and spears are strong against swords and weak against axes.
Combat is resolved "simultaneously" — losses are not sustained until after the hour is over.
Units preferentially attack the units they're strong against, then their own unit type, then their weakness.

Therefore, the units lost in an attack are both a function of one's own forces and the enemy's at the time of the attack. Furthermore, losses occur simultaneously on both sides. This complexity and interdependency has a significant consequence: There is a danger of mutually recursive fluent definitions. Even if there's no infinite recursion, a trivial query might require massive fluent evaluation, as in this example of querying {A, 2}:

Fluent A-0 queries {B, 0} and adds to it
1. Fluent B-0 returns a default value
The result is added to: Fluent A-1 queries {B, 1} and adds to it
1. Fluent B-1 queries {A, 0} and adds to it
  1. Fluent A-0 queries {B, 0} and adds to it
    1. Fluent B-0 returns a default value
The two results above are added to: Fluent A-2 queries {B, 2} and adds to it
1. Fluent B-2 queries {A, 1} and adds to it
  1. Fluent A-1 queries {B, 1} and adds to it
    1. Fluent B-1 queries {A, 0} and adds to it
      1. Fluent A-0 queries {B, 0} and adds to it
        
        Fluent B-0 returns a default value

While this might seem a problem solvable by some optimization or trick, those solutions are hacks — there's no way to support this generally. Simulation designers must be wary of mutually dependent fluents like these. There are two common solutions to this problem, and the correct one depends on your application:

Introduce constants: Do the mutually dependent calculations in a separate History or in a function outside of Herodotus proper. Then, create a new Fluent which, rather than calculating its value dynamically, returns a constant. This is generally only usable if the past is immutable.
Combine fluents: Take the two (or more) mutually dependent Fluents and turn them into a single Fluent that returns the items' respective data. One feature that might help is to use the arbitrary arguments feature to include an indicator of which data should be returned. This is not always an applicable approach, but where it is usable it is very powerful.

The latter approach was chosen for the RPS simulation because it is slightly harder to implement, and this simulation was designed to stress Herodotus/Thucydides. All of the armies correspond to a single fluent selector, with losses being calculated for all three types on both sides in a single fluent which is triggered at each skirmish.

Taking the (Battle)Field

As in the other examples, we'll start by looking at nouns. This simulation involves two Generals (the player and the enemy) and Armies, along with Daylight. It's also important to track the time of the last Skirmish. Finally, the armies have locations: in the Reserve, away from the battle; in the Field, at combat with the enemy; and in Transit, on the way there.

The last thing to consider is the set of verbs: advances, withdrawals, and skirmishes. If skirmishes happen hourly, we'll want to track the time of the last skirmish; and if we want to prevent skirmishing during a withdrawal, we should note withdrawals when they happen.

The armies are expressed in a single Fluent, stored in one big list in the following way:


[{General1Name, 
    [{UnitType1, count}, {UnitType2, count}, ...]
  }, 
 {General2Name, 
    [{UnitType1, count}, ...]
  },
  ...]

So, the fluent that sets up the armies looks like this:


f init_armies:
%We'll express the place nouns as fluent types
  type reserve.
%Grab the army definition from the bindings
  value Armies.
%Use a special function to combine army values
  combine rps:add_armies(Net, Value).

We use rps:add_armies because it handles all kinds of cases where the Net or the Value are undefined, where one or the other is a tuple and not a list, and so on. rps:add_armies is provided by the rps.erl module, which the simulation writer provided alongside the .tsdl file. Thucydides clients (either remote or local) can supply arbitrary extra Erlang modules that are made available to .hql and .tsdl files. It's up to a Thucydides provider to ensure that these are safe to execute.

The rest of the incident used to initialize the armies and the rest of the simulation follows:


f initial_generals:
%"generals" as a fluent type is the list of generals in the fight
  type generals.
%capital-G Generals is a constant list defined in the bindings
%of the incident triggering this fluent.
  value Generals.

%field and transit are the other two army locations
f empty_places:
  type [field, transit].
%Of course erlang funs work in tsdl.
%This makes one empty army for each general in the bindings.
  value lists:map(fun(G) ->
      {G, [{swords, 0}, {spears, 0}, {axes, 0}]}
    end, Generals)
  .

%"withdrawing" marks whether the given general is withdrawing.
f none_withdrawing:
  type {withdrawing, Generals}.
%"persist persist." can be abbreviated like so:
  persist.
  value false.

%"last_skirmish" marks the last time the given two generals sparred.
f no_prior_skirmish:
  type {last_skirmish, Generals, Generals}.
  persist.
%-24 just means "yesterday, before all this started".
  value -24.

%daylight is the current brightness of the battlefield
f daylight:
  type daylight.
%bring a 24-hour value into the 0 to 1 range
%0 means "pitch black"
%1 means "high noon"
  value (12 - abs(12 - (trunc(Now) rem 24))) / 12.0.

i init_rps(Generals, Armies):
%definitions can take lists like these, too!
  set [init_armies, initial_generals, empty_places,
       none_withdrawing, no_prior_skirmish, daylight].

Triggering this initialization incident will look something like this to a local client (if the Thucydides process is called rps_sim):


Bindings = dict:store(
  "Armies",
  [{player, [{swords, 30}, {spears, 30}, {axes, 30}]},
   {enemy,  [{swords, 30}, {spears, 30}, {axes, 30}]}],
    dict:store(
    "Generals", 
    [player, enemy], 
    dict:new()
  )
),
thucydides:trigger(init_rps, Now, Bindings, rps_sim)

For a remote client, the same information is passed, but the dictionary specification is a little different.

Advance Wars

In the remainder of this blog post, we'll look at two uses of the "follow" semantic mentioned in the previous post. A "follow" is a causal linkage from zero or more incidents and conditions to one or more incidents. The structure of a follow is:


follow a_follows_b_or_c_after_5_when_d:

These are (optional) "input event archetypes". When these happen, this is triggered.

  in [b,c]

Optionally, you can include requirements as in incident archetypes. If these don't hold, it doesn't trigger, and the follow will try repeatedly to check them as time goes on. Of course, there's no need to duplicate incident archetype preconditions. The follow will keep trying until it meets the preconditions.

  require d

The follow starts trying to trigger after the "delay" parameter, which defaults to "delay 0."

  delay 5

It tries for a number of time units specified by the "duration" parameter, but will only happen once for each triggering incident. If the conditions aren't met by the time (trigger_time + delay + duration), the trigger fails and the output events don't occur. Duration defaults to "duration 0", meaning it will try only once.

  duration 10

Out is a list of output incidents.

  out [a]

Bindings are seeded based on the input archetype, if any. After this seeding, they're run through the binder functions one at a time. If all the bindings are defined by the time the binder functions are done, the requirements are checked and so on. If there is no input archetype, the binder functions alone are used. A binder function returns a list of {VarName(a string), [PossibleBindings]}. Binder functions are called in-order and each is given all permutations of the possible bindings for the previous binder. Bindings are referred to in the same way as requirements, etc.

  bind get_a_bindings.

Here's an inline binding function.

  bind get_more_a_bindings:
    FavoriteFood = q({{favorite_food, BPerson}, Time}),
    [{"FavoriteFood", [FavoriteFood]}]
    .

Let's presume that "advance" is an incident archetype with bindings for the General, the number of Swordsmen (NSw), the number of Spearmen (NSp), and the number of Axmen (NAx). If a follow is defined in this way, we can express "the enemy advances as soon as the player advances" like this:


follow enemy_advance_follows_player_advance:
  in [advance].
  out [advance].
  bind new_army:
    EnemyNSw = NSp,
    EnemyNSp = NAx,
    EnemyNAx = NSw,
%"enemy" is hardcoded here, but it could certainly
%be the result of a fluent query or something.
    [{"General", [enemy]}, 
     {"OldGeneral", [General]}, 
     {"NSw", [EnemyNSw]}, 
     {"NSp", [EnemyNSp]}, 
     {"NAx", [EnemyNAx]}]
  .
  require advancer_is_player:
    check OldGeneral =:= player.
  require enemy_hasnt_advanced:
    type [transit, field].
    check 
      lists:all(fun({_, Amt}) ->
        Amt =:= 0
      end, units(General, _Val))
    .

Now, as soon as the client code triggers a player advance, the enemy advance will trigger automatically. This works for instantaneous triggers, but what about delayed triggers? For these, Thucydides's conception of time must come into play.

Thucydides stores the "current time" automatically, and can be asked for what it thinks the current time is. The message "progress_time" can be sent to a Thucydides process remotely or locally. This message takes a time delta and the resolution by which to step towards it ("progress_time_to" takes a destination time). Thucydides does no interpolation; such interpolation could be costly since fluents can contain arbitrary code. During progress_time, various follows might be triggered, and the result of the message is the list of incidents that were triggered during that time. Here's an example:


%The time argument can be left out(it will use the current time)
%and so can the bindings, if they're empty.
thucydides:trigger(my_arc, my_sim),
%The default resolution is 1.0, but any number can be used
thucydides:progress_time(5, my_sim).

A more complicated case of following is our rule for saying that a skirmish happens whenever the two armies meet on the field. We need to be careful here to prevent an unnecessary number of skirmishes. This problem of potential duplicate skirmishes is why we introduced the "last_skirmish" fluent above (which is set to Time whenever a skirmish occurs) and the follow that expresses this case looks like this:


follow skirmish_when_armies_meet:
  out [skirmish].
  require last_skirmish_yesterday:
    type {last_skirmish, [Attacker, Defender]}.
%'div' is integer division.  TSDL will automatically
%truncate both arguments.  In this case, we want to make sure that the
%previous skirmish was yesterday or earlier.
    check (Value div 24) < (Time div 24).
%Follows with no input incidents should probably
%use infinite duration, otherwise they'll stop being checked
%and never start being checked again.
  duration infinity.
  bind all_general_combinations:
%Here's another invocation of a custom erlang function.
    {Atks, Defs} = 
      rps_lists:unzipped_combinations(q({generals, Time})),
    [{"Attacker", Atks}, {"Defender", Defs}]
  .

There's more to this simulation, including rules for skirmishes following other skirmishes after an hour, and withdrawals of each side occurring when one or both sides is defeated, or night falls.

Moving On

This ends the Rewriting History series of essays. The switch to Erlang has empowered Herodotus, and the introduction of HQL/TSDL has empowered its users. Many semantic changes have been made: matching is entirely new, follows have been introduced, and simulations now have a concept of the progression of time. Thucydides can be used in whole or in part (with or without follows). Two simulations have been written in Thucydides.

The next series of essays will discuss the development of a small web-based game that will take advantage of Herodotus's unique features. In this game, the user will play as a Seer, using his supernatural powers to help or harm various political bodies by dispatching parties of heroes to fulfill or prevent prophecies, or to preserve or disrupt previous incidents. The strengths of Herodotus will be shown in three ways: player planning will be based on past and possible future events; memories of party and Seer exploits will be held by NPCs; and the events chosen for the future will be a function of the ways that the player has acted and chosen in the past.

Stepping Forward

2008-04-24T23:35:00.003-04:00

This is an essay in the Rewriting History series. Please read at least Introducing Herodotus and Rewriting History before proceeding. This is also a followup to Stepping Back

The Challenge

Create the Thucydides Simulation Definition Language, or TSDL: A language for defining Fluents, Cancels, and Incidents in their archetypal form, along with causal relationships between these archetypes. Incident archetypes defined in such a way should be applicable to a Herodotus history via a Thucydides simulation. This essay will pay special attention to the TADL subset, which doesn't include the aforementioned causal relationships support.

Lingua Franca

To recap, an Incident is a container for some Fluents and some Cancels, occurring at some time, with a given set of bindings. It also has a "type". Its archetype provides functions for defining some of these dynamically. The way this looks in Herodotus is something like:


FluentArcs = [Full, Poorer],
CancelArcs = [CancelDiets],
Requirements = [ReqEnoughMoney],
I = i_arc:new(
  eat_feast,
  main,
  FluentArcs,
  ["Owner", "MealCost"],
  [Requirements],
  [],%no extra input selectors
  CancelArcs
)

This isn't wholly unpleasant, but defining Fluents sort of is:


Full = ?A_FLUENT(
  {me, hunger},
  _Time,
  _Time + 6, %I'm hungry four hours later
  1.0,
  (_Now - _Time) / 6.0,
  lists:max([0.0, _Net - _Value])
),
Tired = ?A_FLUENT(
  ... %more like the above
),
Happy = ?A_FLUENT(
  ... %more like the above
)

The irksome things about this ?A_FLUENT macro are that it's specific to the Erlang implementation, that it's order-dependent, and that it's ugly. Let's try and find a way around using it and the other macros, and make it more readable in the process.


%this defines a fluent "full", which decreases "hunger".
%We'll assume that hunger goes from 0 to 1 and is completely
%removed by the consumption of food.
%if this took an argument, it would be f full(Arg1, Arg2...)
f full:
%this is the fluent type.
%it gets the "Owner" variable from the bindings of the archetype
%in which it's triggered
  type {hunger, Owner}.
%it starts immediately, so the "start" line is omitted.
%it defaults to "start Time."
%it ends effectiveness in six hours. this could default to "end infinity."
  end Time + 6.
%it persists as 1.0. this could default to "persist undefined."
  persist 1.0.
%and its value is the portion remaining of the food at the given time.
%The default is "value true."
  value 
    (Now - Time) / 6.0
  .
%it combines by clipping Net - Value to [0, 1].
%the default is "combine Value."
  combine 
    lists:Max([0.0, Net - Value])
  .

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.

Stepping Back

2008-04-21T11:27:00.008-04:00

This is an essay in the Rewriting History series. Please read at least Introducing Herodotus and Rewriting History before proceeding.

The Challenge

Start moving towards Herodotus-qua-platform. Quit focusing so much on Erlang source code. The last essay was too Erlang-centric, whereas Herodotus and Thucydides are meant to be platforms themselves. Therefore, I'll be moving to a new notation for this essay, and hopefully it will hold.

The Changes

Before going on to the syntax, I'd like to explain some recent changes to the semantics. In the development of the RPS military simulation, I encountered some semantic knots of Herodotus that I thought were worth untangling. Mainly, I looked to simplify, improve, and more completely define the matching rules.

A Match Made in Heaven

The new matching rules are much more strongly defined, and are described below. The match selector is represented by Try and the value to check against by Value.

Atoms

Atoms are indivisible, distinct values, like symbols in Smalltalk or atoms in Lisp. Numbers are also treated as atoms. They are written as atom_name. They match against the three types in the following ways:

Atoms: Try == Value
Tuples: Try matches some V in Value
Lists: Try matches some V in Value

Tuples

Tuples are simple data structures. They are written as {el1, el2, el3} and any element type can be placed in them. Their meaning is roughly "all", and they match against the three types in the following ways:

Atoms: Some T in Try matches Value. This is a minor exception, but it's there for convenience. The other possible behavior is virtually useless.
Tuples: All T in Try match Value
Lists: All T in Try match Value

Lists

Lists are sequences of values. They are written as [el1, el2, el3] and any element type can be placed in them. Their meaning is roughly "any", and they match against the three types in the following ways:

Atoms: Some T in Try matches Value
Tuples: Some T in Try matches Value
Lists: Some T in Try matches Value

These new matching rules have two interesting consequences:

There's no longer any reason to distinguish between type and context. There is now only "context".
Simulation designers have much more control over context definition and selection.

In short, it allowed me to simplify and more easily explain the matching rules, remove a fair amount of closely similar code, reduced the amount of work to be done by a simulation designer in the simple case, and permitted much more complex and interesting queries and definitions at a stroke.

This semantic change is the most significant improvement since the shift to Herodotus/Erlang.

Just Cause

Another semantic addition to the tools available in Herodotus/Thucydides is the concept of causality. A "Follow" is a simulation construct which describes cases where one or more incident archetypes can be triggered based on specific previously triggered archetypes, one or more conditions, or both. A Follow also describes how bindings are obtained for the incident to be triggered and the requirements to be checked. Finally, a Follow encodes some information about when it begins checking said conditions, and for how many units of time.

The semantic of Following is slightly more complex than the above lets on, but this understanding is sufficient to be able to talk about it. Another feature implemented alongside Follows is time. Simulations now maintain a "current time" which can be ticked forward by clients to arbitrary points at arbitrary resolution. Backwards ticking and Follows have not been thoroughly tested and, frankly, the semantic is unclear. I recommend against combining Follows with time travel. If a simulation has need of such a feature, it can be implemented in Herodotus client code.

Syntactically Delicious

What the above semantics, along with past work, indicate is that any syntax for Herodotus must include the following:

Fluent selection and querying
Reasonable operations over dicts, tuples, lists, atoms, and numbers
Fluents, including optional arguments
Cancels
Incidents
History selection

And any syntax which expresses Thucydides must cover the above, plus:

Fluent archetypes
Incident requirements
Incident archetypes
Follows, including binder syntax

So, let's split the work into defining two small, specific languages:

Herodotus Query Language (HQL)
Thucydides Simulation Definition Language (TSDL)

Further, we'll posit that a set of simple operations on dictionaries, tuples, lists, atoms, and numbers is available to all of those languages.

The rationale for splitting the grammar this way is that HQL is meant to be used not just within a simulation or fluent definition, but also independently by client code, and the TSDL is how a client defines a simulation with archetypes, requirements, causality rules, &c. Certainly, a subset of TSDL could be defined which only considers archetypes; this can be called TADL, or Thucydides Archetype Definition Language, and would be useful to client code that doesn't wish to use Thucydides's causality mechanisms. Since Erlang is a little obtuse to the unfamiliar, a set of small, specialized domain-specific languages will be introduced.

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.

Homage à Jones

2008-03-11T18:20:00.004-04:00

This is an essay in the Rewriting History series. Please read at least Introducing Herodotus and Rewriting History before proceeding.

The challenge

Use a simple text-based adventure puzzle to show the basics of Thucydides. The player will be the only actor of import in this world, and there will be a one to one correspondence between player actions and historical events. This game will showcase two features of Thucydides: Archetypes and Requirements.

The puzzle is trivial: The player starts in a treasure room, with a valuable statue on a pressure plate. If the statue is removed, the exit will close immediately. There is also a statue-shaped rock in the room. The player must escape the room with the statue in hand. The actions available to the player are:

look
leave when the door is open
take item when the named item is on the floor and the player's hands are free
lift when an item is on the pressure plate and the player's hands are free
drop (to the floor) when the player is holding something
place (on the pressure plate) when the plate is empty and the player is holding something

Therefore, the solution will be lift; drop; take rock; place; take statue; leave. The following will show how to implement such a puzzle using Thucydides, and sample code will be provided for Thucydides/Erlang.

Setting the Stage

First, the nouns must be examined. This system does no dynamic generation of new actors, so it's sufficient to use the entities suggested by the puzzle description: A door to open and close, a statue and a rock to lift and drop, and a floor, plate, and player to hold items.

Nouns are the items bound into Archetypes to create an Incident when one should occur. The drop command will fill in a Drop Archetype with the dropper and the item to be dropped, for instance.

Now that the nouns are in place, the fluent types should be decided. We should think of the states caused by the interactions of the commands and the nouns. For instance, inventory is a Fluent covering the floor, plate, and player. open is a Fluent covering the door. finished is a Fluent of interest to the game, and is set when the player leaves the room.

Next, the subject of Cancels should be approached. We can imagine that if the door is open, it will be so forever. But when the plate is emptied, the door's openness should be terminated. While it would be possible to express "the door is open" as "the plate is full", this is a less flexible approach that doesn't take into account the fact that there could be other ways to open the door or keep it propped open.

We can make a simple mapping of commands onto Archetypes, so let's do that. That gives us Look, Leave, Take, Lift, Drop, and Place. Leave will set finished. Take will set inventory with the item as value, stacking with an append in the context of the taker(the player) and a delete in the context of the old possessor(the floor). Lift will set inventory as Take did, but will also Cancel the door's open state. Drop is not just Take with reversed arguments; the player can only hold one thing, but the floor can hold many. To keep things simple, rather than give inventories a size, we'll have a special Drop Incident that encodes this idea that a Taker can hold one thing and a Drop destination can hold many. Finally, Place acts like Lift, with the exception that it sets {open, door} rather than cancels it.

The final step in designing such a simple simulation is to look at the preconditions for actions, hinted at in the list of verbs above. Each of those preconditions will be expressed as a Requirement on the corresponding Archetype. Drop and Place both require that the taker's hands are full; Place further requires that the destination is empty; Take and Lift both require that the object is at the corresponding location and that the taker's hands are empty; Leave requires that the exit is open.

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.

Rewriting History

2008-03-08T21:53:00.001-05:00

This is an essay in the Herodotus series. Please read at least Introducing Herodotus before proceeding.

The challenge

Herodotus's Io implementation is slowish, complex, and a little clumsy. It is loosely defined, and that fault has extended to Herodotus as a whole, such that it is difficult to describe the system's actions. Especially prone to this complexity are cancellations, which have extremely loose semantics. Accordingly, Herodotus will for now be defined concretely.

Furthermore, it will be necessary with the release of Metaplace to provide Herodotus as a service for worldbuilders. In pursuit of this goal, I have rewritten Herodotus in Erlang, a concurrency-oriented functional programming language. Functional programming's lack of side effects is a perfect fit for the semantics of Herodotus, where a history is defined as a series of transformations(Incidents) on a base state. As a nice bonus, the speed of Erlang means that Histories with tens of thousands of incidents are now quite feasible, even with the relatively few optimizations that have been performed so far(none of which yet include indexing or caching).

The Specification

Herodotus will continue to have only a few concepts and operations at its core. The Thucydides simulation framework will extend these concepts and handle all the logic of causality, as well as paradox detection and prevention.

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.

Filling in the Blanks: Procedural Glue

2008-02-12T13:31:00.001-05:00

This is an essay in the Herodotus series, and a followup to Designing a Story. Please read at least Introducing Herodotus before proceeding.

A Sticky Situation

At the end of the last essay, we found ourselves with a problem: We had all these simulation constructs, but no clear way to, well, construct them. This essay will shed some light on how stories in Rboehm's style could be built.

Pick and Choose

The fundamental variable unit of a Scene, and therefore of a Quest, is a Goal. If we're looking to build a Asker asks Provider for Item goal, we should probably pick the Item based on the Asker. Let's assume that the only Asker for now is the Farmer, though later we can look at ways to pick those too.

Recall that Characters have desires. In that case, we might want to pick an Item from among those desires. This gives us a nice little object-oriented and time-sensitive way to pick which Item to hunt for. And if all of a Character's needs are satisfied? Then we pick a different Character.


//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.

Designing a Story: Building Narratives from Story Atoms

2008-02-04T21:53:00.001-05:00

This is an essay in the Herodotus series. Please read at least Introducing Herodotus before proceeding.

Rboehme's Quest Generator

Areae's Metaplace is an upcoming virtual world platform, construction kit, and social network. One of the exciting ideas in the days leading up to its launch is the plan by Rboehme and others on the Metaplace forums to write a procedural quest generator. Since this sort of algorithm is precisely what Herodotus was written for, I hope to contribute to the project by providing a Herodotus simulation back-end for it. This essay will also introduce Thucydides, a simulation toolkit for Herodotus.

The Father of History and the Father of Lies

Herodotus, the man, went by an additional epithet: "The Father of Lies". This ignominious label was conferred upon him by his critics who detested his ways of presenting multiple conflicting accounts of a story and his habit of writing on local folklore or third- or fourth-hand reports. Thucydides, a slightly later historian, introduced the "objective" approach to history that historians use today, meaning that he competes for the title of "The Father of History". Since Thucydides's work was more responsible and more restrained, I thought it just that the technology which provided a framework for history and a clear structure for the simulation framework should be called Thucydides.

Thucydides uses the context feature of Fluents and the forwarding mechanism of Io to conceal the inner workings of Herodotus from client programs. A Thucydides SimulationObject triggers an Incident when it is created or destroyed, is uniquely identifiable among other SimulationObjects, and passes on any slot requests such as age or height, parameterized with a time, to the History in which they're defined. What this means is that a lot of duplicated or error-prone Herodotus API can be replaced with the use of these SimulationObjects. Furthermore, it's possible to mix Thucydides and Herodotus code, as long as the user is careful not to violate any assumptions the SimulationObjects might have about whether their represented contexts are still valid, whether their histories still exist, etc.

In this essay, we'll only be considering a single History, and will attempt to show how Thucydides can express Rboehm's Quest Generator.

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.

Workshop Options

2008-02-03T21:22:00.000-05:00

Some background

RIT hosts a yearly summer tech workshop series for pre-high-schoolers called "Kids on Campus". I'll be teaching there this summer.

I traded some e-mails with the development VP of the Metaplace folks, Jason Hable(jason@areae.net). Unfortunately, I couldn't get any additional information about how exactly Metaplace works, or how difficult it would be for first-timers who are also junior high school students or thereabouts. It's worth noting, however, that anecdotal evidence from alpha testers and Areae employees suggests that even non-programmers can build a simple world very easily. I've sent him another e-mail, but in the meantime, I have some loose plans for the workshops I would enjoy teaching:

A Metaplace Of Your Own

Work alone and in small teams(2-4 person) to design and build your own virtual worlds! Metaplace is a toolkit and a social network for making and sharing games, avatar chats, or any other single- or multi-player online world. You can put Metaplaces on your Facebook profile or your personal website, and share them with everyone!

Learning Objectives:

Real game and virtual world design techniques from the games industry!
Exposure to a brand-new way of developing online games
Programming in Metascript, a variation on the Lua scripting language
Sharing Metaplaces with friends and family

Concerns: Not enough information yet. I'm sure that Metaplace will be available, or at least in open beta, by the summer, but without concrete information on how it is to use I don't know how much I want to advocate it.

Game Design 101

Analyze and dissect the board and computer game classics, old and new, to see what makes them tick - and what makes them fun. Work individually or in small teams(2-4 person) to make your own unique board or card game.

Learning Objectives:

Real game design techniques from the games industry!
Survey of trends in board and computer game design
Practice in "paper prototyping", a process used by real game designers to polish their computer games' core gameplay
Exposure to formal methods in game design and the budding field of "ludology".

Concerns: Is there enough of a connection to the "tech" here? I would love to make a whole course out of this, though I could compress it down to four days if I had to for one of the other programming courses.

Game Design and Development with RubyGame

Work in small teams(2-4 person) and make a game from start to finish with the Ruby programming language and the RubyGame framework. Use real-world game design techniques with a real-world programming language!

Learning Objectives:

Real game design techniques from the games industry!
Exposure to many independent games
Programming in Ruby, a popular new programming language
Basics of 2D graphics and animation

Concerns: This is a lot of topic to cover in 9 days. I want to use Ruby instead of something like Flash because Ruby is simple, free, and kids can acquire it easily, plus it can be used for many things besides animation and games. Would this overlap too much with the Flash workshop?

Fun and Board Game Design

A world of board and card games exists beyond Monopoly and Sorry!. Meet fun, interesting board games from Europe and the United States, and work individually and in small teams(2-4 person) to make your own unique board and card games!

Learning Objectives:

Exposure to games such as Icehouse, Kill Doctor Lucky, Settlers of Catan, Carcasonne, and other significant board games
Capturing a theme or feeling and expressing it in a board game
Recognizing the elements of fun and improving on them incrementally with testing

Concerns: I think this is fascinating because I know about these games, but to someone who doesn't know about the really interesting board games, it might not be compelling.

8-Bit Music

Compose your retro magnum opus! Learn how people are using old video game hardware to make fantastic modern music, from techno to hip-hop, from rock and roll to heavy metal, and from classical to country. Choose your weapon - NES or Game Boy - and learn how to write "chiptunes", the first music genre of this generation.

Learning Objectives:

A basic introduction to assembly language programming and computer organization
History of video game systems since 1980
Composing and arranging music with a limited sonic palette, using either textual formats or trackers
Exposure to a broad range of musicians who work with repurposed computer hardware
Moving composed works from software simulation to physical hardware.

Concerns: I think this would be fun, and I have experience with this, but I'm not exactly the world's best musician. I'm also not sure if today's kids have the same nostalgic connection to the music of the older video games as I do.

Spider-Man 3

2008-02-02T11:18:00.000-05:00

The Setting

From Summer of 2006 until Summer of 2007, I worked at Activision's Vicarious Visions studio in Albany, NY. I was hired as a "scripter co-op", where a co-op is something like a paid internship or, to the medical folks out there, an externship. My major program, the Software Engineering program at the Rochester Institute of Technology, requires one cumulative year of co-op for certain high-level courses which are required for graduation. I learned about the job through a faculty connection, and applied with my resume. A month or so later, I heard back, and two days later I provided the answers to the programming and game design tests I'd been given. Soon afterwards, I was interviewed by phone and, though I feel I talked too much, it must have impressed them enough to hire me.

Hard at Work

For the first few months, I worked mainly under Jason Bentley and Gabe So, the only two permanent employees in the group designated to perform mission scripting for the PSP, PS2, and Wii versions of Spider-Man 3. There, I trained incoming co-ops on the all-new toolset being developed for this game, and I also acted as a liaison between the scripting group and the engineering group, learning about and giving requirements for new technologies. Once development came into full swing, I worked on a boss fight(with Doc Connors) and a couple of small in-game cutscenes. Soon, however, I would be placed on a task I was really passionate about: dynamic content.

DMS, the Dynamic Dynamo!

Spider-Man 3's open city gameplay revolves around two sets of random occurrences: the REM, or Random Event Missions such as stopping muggings, helping victims of car accidents, and so on; and the Crime Wave game, where the terrain of New York is a backdrop for a turn-based gang warfare between five factions, including the police. This system runs constantly, even when the player is just running around or doing plot missions. The player can interact with the Crime Wave by performing Crime Patrols at specially marked tokens. These Crime Patrols are series of up to six missions pulled from the Dynamic Mission System, which is a sort of "mad libs" for short plot sequences. Each DMS mission segues into the next by a topical voiceover, and each mission varies in content depending on which gang is in charge in that area. The stage was set for a really interesting bunch of content, and many of the designers on staff, including the concept's original designer, Dax Gazaway, voiced the desire to play a game made entirely of DMS. I was in charge of making the DMS (as the whole system was affectionately known) dream a reality.

I handled object taxonomies, mission templates, placement guidelines, and other aspects of the DMS development. I was the only scripter on DMS for about three months, and was then joined by Wesley Paugh for one or two more. The way, however, that DMS had been sold to the higher-ups was that it would generate 70% of the gameplay time with 20% of the development effort, or some similarly high and low number. This meant that I had one first-year engineer(Jason Batchkoff, who I had to share with cameras) and, after the initial batch of resources, very little art support. But, with the extensive help of design team lead Tim Stellmach, who was responsible for bringing the DMS together, and the assistance of an excellent QA team who handled everything from token placement to exhaustive DMS testing, we were able to complete the system just in the nick of time.

I had a high measure of creative control in this assignment, up to designing the missions and metagame themselves with Tim Stellmach. It was especially high considering that it was my first project in the industry and my first foray into dynamically generated content like this. The frustrations I encountered while working on it fed into my desire to write Herodotus, since I felt the simple mad-lib approach of DMS was not fine-grained enough, and the support for creating a new DMS mission was basically a template into which the new stuff could be copied and pasted. The base mission and trigger systems had never been written with DMS in mind, so my job (and that of my engineer) was as much hacking around system restraints in time to ship as it was actually generating content and features. The 70/20 split of DMS was a double-edged sword. We were vitally important only while we were inexpensive, and there were a couple of times we were concerned about the whole system being cut.

Without lingering too long on the 80+ hour weeks required for the last six or so months of the project, I think that Spider-Man 3's dynamic mission system was an ambitious effort and a great learning experience, in the midst of an entire project of ambitious efforts, new technology, and learning experiences for Vicarious Visions. Regardless of how well it was reviewed, it proved popular with players, and I think the extra variation it offered over Spider-Man 2's wrench-wielding hordes and "save the balloon" missions justified it.

Learning from History: Avoiding the Mistakes of the Past

2008-01-30T09:44:00.001-05:00

This is an essay in the Herodotus series. Please read at least Introducing Herodotus before proceeding.

Regaining perspective

This essay takes a higher-level view than the previous article, A Geological Inquiry. Where the last essay focused on the implementation of a particular traditional simulation in Herodotus, here we examine further the contexts in which this kind of history storage and retrieval can be useful. In particular, this essay will point out some ways in which a game can learn from player history, rather than force the player to repeat his mistakes.

Here are a few ways, inspired by Koster, Perko, others, and my own research, in which collecting player actions can provide useful simulation and gameplay information:

Difficulty scaling: Record a player's deaths or kills, or time spent trying to complete an objective. If it passes some threshold, tone up or down the content to match the player's level. If they need to meet a certain NPC to progress, let the NPC's path cross theirs, or drop more hints. If the player is exploiting a "cheap" tactic, you can weaken the tactic.
Economics: Record a player's purchases and sales, or their drain on particular resources such as certain monster types. Modify local shop prices, spawn rates, etc to reflect the player's influence.
Personalized challenges: Record a player's preferred obstacles and solutions. Tailor the challenges to these types. If they like dungeon crawls, give them more dungeon missions; if they like diplomacy, give them more diplomatic missions. If they solve their jumping puzzles with long jumps more than high jumps, make future platform problems use more long jumps.
Personalized rewards: Record a player's preferred or needed skills and activities. Tailor the rewards to these types. If they like using swords or fire spells, give them more of those where possible in the drop tables. If they've been killing Yetis for two hours looking for a single hide, increase their drop chance. If they linger on the beautiful scenery, give them more chances to see it.

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.

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.

A Geological Inquiry: Grounding Herodotus's Theory

2008-01-27T16:18:00.001-05:00

This is a follow-up to Introducing Herodotus, and expands on that essay with concrete examples. Please read it before proceeding.

The challenge

Create a simple terrain generator to show how even incidents in geological time can "count" as historical occurrences. Also, show an example of how an application's structure might, rather than access and store data directly, make use of various objects wrapping a single history to provide simple, time-centric access to data.

...

Using the library

The current development version of Herodotus is available here. Note that it will change as time goes on. It's written as an addon for a language called Io, and can be installed in the following way:

Download Io
Add the Herodotus, Macrobe, Funktion, and SimpleGraphics folders to Io/addons. These were all written by me, Joe Osborn, in 2007-2008, and I provide them under a BSD license. Macrobe is required for Herodotus, Funktion provides useful simulation mathematics, and SimpleGraphics is a simple GLUT-like toolkit. Other addons required for this sample include OpenGL(and its dependencies Image, Font, and Box), Range, and Random, which are all included with Io. Others can be removed from the Io/addons folder without harm.
In the base Io directory, run the following commands:
- make
- sudo make install
- sudo make linkInstall
- make testaddons

Ensure that the test output looks something like this:


Box        - PASSED
Funktion   - PASSED
Herodotus  - Warning, inverting lowpass or highpass 
stack modes cannot really work properly.  Change the 
definition of inversion to something like "remove it 
from prevFluents"
PASSED
Macrobe    - PASSED
Random     - PASSED
Range      - PASSED
SimpleGraphics - PASSED
Thucydides - PASSED

The warning on Herodotus reflects a temporary design concern, and has no impact on the functionality of this example.

Once Herodotus is working, it should be available in any Io VM. The objects defined in Herodotus are defined in Herodotus/Herodotus/io/. For this example, it doesn't matter where the Inquiry is written, but the finished product will be available at Herodotus/Herodotus/samples/lander-final.io. So, to execute it, run cd Herodotus/Herodotus/sample; io lander-final.io.

Designing the simulation

Simulation design in Herodotus first begins with deciding what it is we want to model. In this case, we choose to model an expanse of lunar terrain marked by mountains and plateaus, subject to damage by occasional impacts. This might appear in a sci-fi game, perhaps a Lunar Lander clone.

Once we've decided what to model, we need to consider how to attach it to the application at large. In this case, a simple heightmap is probably sufficient. So, we know to design our Fluents with locational parameters, and we know to have them output numbers, for the purpose of rendering terrain at specific points. After the initial terrain generation, our inputs are the two kinds of event that can occur: A Landing or a Crash.

Finally, we need to start getting into the nuts and bolts of the simulation. For now, let's do this simply, and only use one fluent type, height. Later, we can introduce Fluents to identify particular mountains or craters, if necessary. But this is to be a bare-bones simulation, so let's treat it as such.

Fluents of type height stack using numerical addition, and are parameterized by h, t, x, and y.

Now that the Fluent alphabet is defined, we can consider the initial state Generator. This Generator will place some random number of mountains and plateaus at varying points inside a 100x100 2D plane. Each mountain is a Gaussian curve placed at a given point(centerX and centerY) and perturbed by a noise function of low amplitude. Each plateau has a plateau height, and is placed on top of a mountain, clipping to a percentage of the mountain's maximum height by means of a special stack mode, "Lowpass". To do this, we will introduce mountains and plateaus fluents to keep track of the mountains and plateaus, rather than relying only on height.

A single stone: `lander-0.io`


//Imports
  Macrobe
  Funktion
  Herodotus
//Create our History
world := History clone
//Define an Incident for placing mountains.
//This will be how we "create" mountains.
PlaceMountain := Incident clone do(
//The mountain information to be used
  mountain ::= nil
//This method is called automatically when the incident occurs.
//It's expected to fill out the Incident's fluents,
//requirements(require), and invariants(dependOn).
  setupFluents := method(
//Establish the context.  This is a predefined Fluent type.
    setFluent(FAppendContext create("mountains", mountain))
//This is a custom fluent of type height,
//with the context being the mountain slot of the parent Incident.
//The x and y arguments are provided after h and t.
    setFluent(Fluent create("height", mountain, h, t, x, y,
//Delegate the calculation of the height to the Gaussian mountain definition.
      mountain value(x, y)
//Use the AddNumber stack mode, which does what it sounds like.
    ) stackBy(AddNumber))
  )
)
//Create a 2D Gaussian curve with default parameters, except for X0 and Y0.
g := Gaussian clone setX0(50) setY0(50)
//We can use the curve itself as the "mountain".
PlaceMountain clone setMountain(g) setTime(0) occurIn(world)

Put the above in a file(such as lander-proto.io) and run io. Now, we can load that file:


Io> doFile("lander-proto.io")
==> true

And we can make queries on world.


Io> world fluentValue("mountains", nil, 0)
==>list(Gaussian_0x3d7330)
Io> world fluentValue("height", nil, 0, 50, 50)
==> 1
Io> world fluentValue("height", nil, 0, 25, 25)
==> 0
Io> world fluentValue("height", nil, 0, 49, 50)
==> 0.3678794411714423

So it looks like our dropoff is way faster than it should be. That's easy enough to fix, so after some experimentation I wound up with this:


g := Gaussian clone
g setAmp(50) 
g setA(0.01) 
g setB(0)
g setC(0.01)
g setX0(50) 
g setY0(50)

So it'll be taller, and less strangely steep. And now our heights look like this:


Io> world fluentValue("height", nil, 0, 50, 50)
==> 50
Io> world fluentValue("height", nil, 0, 49, 50)
==> 49.5024916874584022
Io> world fluentValue("height", nil, 0, 25, 50)
==> 0.0965227068113855
Io> world fluentValue("height", nil, 0, 25, 25)
==> 0.0001863326586039

One mountain in the middle of a landscape is pretty dull, so let's generate a few more like this:


seed := 0
r := Random clone
r setSeed(seed)
r value(0, 9) repeat(i,
  gaussValue := r value(0.001, 0.05)
  g := Gaussian clone
  g setAmp(r value(20, 50)) 
  g setA(gaussValue) 
  g setB(0) 
  g setC(gaussValue) 
  g setX0(r value(0, 100)) 
  g setY0(r value(0, 100))
//This is the only part where Herodotus constructs are involved.  Herodotus
//can integrate smoothly into existing simulation architectures.
  PlaceMountain clone setMountain(g) setTime(i) occurIn(world)
)

Replacing the old mountain generation with the above gets us to Herodotus/Herodotus/samples/lander-0.io. We can run it and make queries like these:


Io> world fluentValue("mountains", nil, 10) map(i, v,
)-> v x0 asString .. ", " .. v y0 asString .. " height: " .. v amp
)-> ) join("\n")
==> 84.4265744090080261, 60.276337037794292 height: 41.4556809491477907
84.725173725746572, 42.3654796788468957 height: 36.3464953214861453
38.4381708223372698, 43.7587209977209568 height: 39.3768234527669847
5.6712975725531578, 96.3662764057517052 height: 46.7531900526955724
47.7665111655369401, 79.1725033428519964 height: 31.5032456396147609

In other words, at time 10 we have a bunch of mountains kicking around, and they add up to form the landscape as a whole. We can see that effect in these queries:


Io> world fluentValue("height", nil, 10, 84, 40)
==> 27.9284088273150353
Io> world fluentValue("height", nil, 10, 84, 60)
==> 41.1351777985938796
Io> world fluentValue("height", nil, 10, 84, 50)
==> 4.617869013365393
Io> world fluentValue("height", nil, 0, 84, 50)
==> 1.7260724122134643
Io> world fluentValue("height", nil, 1, 84, 50)
==> 4.6178690133643858

A visual demonstration of the formation of these mountains is available in Herodotus/Herodotus/samples/lander-vis-demo.io. To execute it, run io lander-vis-demo.io and use the a and d keys to go back and forward in time. Here's what our current simulation looks like at t=3:

As a quick aside, it surely would have been possible to generate our terrain using Perlin noise or another technique. Those techniques can still work with Herodotus! For instance, we could define our height fluent by implementing such an interpolated noise function, or by applying many fluents, each for a single octave of the net noise(or we could use Funktion's Noise object). Instead of a basic mountains fluent, we might define a mountainsInRegion fluent which takes four arguments comprising a rectangle, and returns contiguous regions which have surpassed a threshold value. Or we might run a Generator that introduces mountains by examining the noise for patterns before applying it to the height fluent, and places these mountains as markers for some other game system. The point is, Herodotus is an extremely flexible system, and there's nothing preventing any existing forms of simulation design.

Noisome perturbations: `lander-1.io`

Just because our simulation doesn't use noise from the ground up, so to speak, doesn't mean we can't apply it. Let's modify the height Fluent of the PlaceMountain Incident. This will perturb the height according to a random value. We can easily solve this by adding an additional Fluent to that Incident, with one caveat: The height fluent value calculation must use the same context as this perturbation. If we were to apply the noise separately and read off "all fluents matching this type", it would effect all previously calculated heights at any point, regardless of which mountains were involved. Using contexts to limit the matched fluents breaks the processing into multiple steps, but allows for cleaner fluent definitions. In this particular case, however, speed concerns lead us to keep the perturbation calculation adjacent to the height calculation. Where possible, two Fluents of the same fluent type should be combined if the latter's result relies on the former's, or the dependent fluent type should only be calculated in specific contexts.


  setupFluents := method(
//Establish the context.  This is a predefined Fluent type.
    setFluent(FAppendContext create("mountains", mountain))
//This is a custom fluent of type height,
//with the context being the mountain slot of the parent Incident.
//The x and y arguments are provided after h and t.
    setFluent(Fluent create("height", mountain, h, t, x, y,
//Delegate the calculation of the height to the mountain's Gaussian,
//and perturb by the perlin noise.
      b := mountain gaussian value(x, y)
//An optimization here, since perlin noise is expensive
      if(b > 0.01,
//Vary by up to 30%
         b * (1-(mountain perturbation value(x, y) * 0.3))
        ,
        0
      )
//Use the AddNumber stack mode, which does what it sounds like.
    ) stackBy(AddNumber))
  )
)
Mountain := Object clone do(
  gaussian ::= Gaussian clone
  perturbation ::= Noise2D clone
)
seed := 0
r := Random clone
r setSeed(seed)
//A new Random and seed for the noise to keep the terrain similar
r2Seed := 1
r2 := Random clone
r2 setSeed(r2Seed)
r value(0, 9) repeat(i,
//To get broader, easier to see mountains, we've tweaked the a and c parameters
  gaussValue := r value(0.0001, 0.01)
  g := Gaussian clone
  g setAmp(r value(20, 50)) 
  g setA(gaussValue) 
  g setB(0) 
  g setC(gaussValue) 
  g setX0(r value(0, 100)) 
  g setY0(r value(0, 100))
  
  n := Noise2D clone
  n setSeed(r2 value)
  n setPersistence(r2 value(0, 1))
  n setNumberOfOctaves(4)
  mount := Mountain clone setGaussian(gaussian) setPerturbation(noise)
//This is the only part where Herodotus constructs are involved.  Herodotus
//can integrate smoothly into existing simulation architectures.
  PlaceMountain clone setMountain(mount) setTime(i) occurIn(world)
)

To see this in action, run lander-vis-demo.io again and press 1 to switch to this version(and 0 to return to the former version), which is the same as lander-1.io. If you want to see the intensity at a given point, click on it and the coordinates and intensity will be output to the command line. The interesting thing about this example is the introduction of the Mountain object, which wraps the Gaussian and the Noise2D. This is an example of a context object, and this style of use will be expanded on in an upcoming essay. And here's the image of lander-1 at t=3:

Even it out: `lander-2.io`

First, to make things more interesting, we'll increase the number of mountains by a factor of three. This will give the terrain a bit more character.


r2 setSeed(r2Seed)
(2*r value(0, 9)) repeat(i,
//To get broader, easier to see mountains, we've tweaked the a and c parameters
  gaussValue := r value(0.0001, 0.01)
//...
//This is the only part where Herodotus constructs are involved.  Herodotus
//can integrate smoothly into existing simulation architectures.
//Note that times don't have to be integral!
  PlaceMountain clone setMountain(mount) setTime(i/3) occurIn(world)

On top of that, we'll jump to t=10:

Now, let's place some random number of plateaus:


//...
    ) stackBy(AddNumber))
  )
)

BecomePlateau := Incident clone do(
  mountain ::= nil
  heightFraction ::= .5
  height := method(
    heightFraction * mountain gaussian amp
  )
  setupFluents := method(
    setFluent(FAppendContext create("plateaus", mountain))
    setFluent(Fluent create("height", mountain, h, t, x, y,
//allow a little bit of height variation at the top
      height * (1 - (mountain perturbation value(x,y) * 0.2))
//warning, this clobbers -all- heights in the fluent stack.
//be sure to get heights context-by-context!
    ) stackBy(Lowpass))    
  )
)

Mountain := Object clone do(
//...
      PlaceMountain clone setMountain(mount) setTime(i/3) occurIn(world)
)

r2 value(5, 9) repeat(i,
  mount := world fluentValue("mountains", nil, 10 + i) anyOne
  if(world fluentValue("plateaus", nil, 10 + i) ?contains(mount),
    continue
  )
//Plateau height is a fraction of total height; let's just put it at half.
  BecomePlateau clone setMountain(mount) setHeightFraction(.5) setTime(10 + i) occurIn(world)
)

And here's what the world looks like at t=20

You might expect that the Lowpass stackmode would limit -any- height reading, and not just the "right" ones. In fact, this point returns to the one made earlier about mixing contexts. You're safe, as long as queries on height look something like this:


heightAt := method(x, y,
  history fluentValue(list("mountains", "plateaus", "craters"), nil, time) map(i,v,
    history fluentValue("height", v, time, x, y)
  ) sum
)

In other words, the guideline is something like: match as few fluents at once as possible, and try to match them as precisely as possible. This is especially important if you use Fluents which assume they're only acting within a certain context.

Game Over: `lander-3.io`

Now, it's high time some interactivity were added to this simulation. Since the primary activity in any Lunar Lander-style game is crashing, we're going to model it first. A Crash is an Incident which modifies height in a circle around the impact point, and acts sort of like an upside-down mountain. But craters also have those little rims, so we'll model it with a half-sphere and calculate the rim height from that, with linear dropoff. We'll also add crosshairs(moved with ijkl) to the visualizer and let the space bar trigger a crater of random size being placed at their center.

We approach this by adding a new context object(Crater), a new Incident(CreateCrater) which sets a craters and a height fluent, and some tweaks to the visualizer to create and apply these incidents. The new code is appended to lander-2.io to create lander-3.io:


Crater := Object clone do(
  radius ::= 20
  location ::= vector(0, 0)
  perturbation ::= Noise2D clone
)
CreateCrater := Incident clone do(
  crater ::= nil
  setupFluents := method(
    setFluent(FAppendContext create("craters", crater))
    setFluent(Fluent create("height", crater, h, t, x, y,
      dist := crater location distance(vector(x, y)) abs
      height := if(dist < crater radius,
//sphere part
        xPart := ((x - crater location x) squared)
        yPart := ((y - crater location y) squared)
        -((xPart + yPart - crater radius squared) abs sqrt)
        ,
//rim part
        (crater radius / dist) * (crater radius / 2)
      )
//and a little variation for flavor
      height * (1.1 - crater perturbation value(x, y) * 0.2)
    ) stackBy(AddNumber))
  )
)

So, here is our world at t=20 before a ship crashes:

And then, calamity strikes! Game over!

Wrapping up

To recap, the concepts we covered included:

lander-0.io
- Getting Io and the necessary addons up and running
- Fluent types and contexts
- Using built-in Fluents like FAppendContext
- Defining custom fluents with arguments
- Using non-standard StackModes such as AddNumber
- Defining, creating, and applying Incidents
- Making queries on a History
- Flexibility of the Fluents mechanism
lander-1.io
- When to combine fluents
- Running the visualizer
- Context objects
lander-2.io
- Defining another Incident and context object
- The importance of building the right FluentStack
- Querying a History safely
lander-3.io
- Defining another Incident, context object, and fluent type
- Interactive creation and application of Incidents
lander-vis-demo.io. We didn't go over this explicitly, but it's worth looking at for more examples of using a History.
- Dynamic loading of different Herodotus simulations(setLanderGen())
- Use of SimpleGraphics and OpenGL toolkits
- External fluent caching to make movements between identical time periods fast(goForwardOne() and goBackOne())
- Proper querying of multiple fluent types and the use of context objects(resetContexts() and intensityAt())
- Triggering Incidents as a response to user interaction(crash())

If any of these concepts seem unfamilar, please read over that section again, or send me an e-mail and I'll tweak this essay to make it clearer.

Introducing Herodotus: Procedurally Fathering History

2008-01-21T12:00:00.000-05:00

The challenge

Games based on static content have a number of intrinsic problems:

Choice is illusory. Every choice presented to the player either results in no meaningful branch, or one of a pre-selected, pre-planned number of meaningful branches, so:
Content is impersonal. There is no significant way to customize the game to the player. Automatically scaling difficulty is about as far as you can go with static content, because:
New content is expensive. Since each branch is pre-determined, branches must all be made individually. This is inefficient for content creators, which means that:
Content is finite and fairly sparse. Eventually players will run out of branches to traverse. Therefore:

We should look towards implementing more dynamic games.

Games based on dynamic content can solve the above problems - not just on their initial release, but also incrementally with subscription or microtransaction-based content additions. Here are just a few ways that a move towards truly interactive narratives can improve gameplay:

Choices can be significant and varied. If the atom of choice isn't "which branch of five to take", but "which state the world will be left in", then all gameplay can become like simulation gameplay: really open-ended, really consistent, really expansive. And the actions the player takes will be important. If the player assassinates the opposing faction's leader, a civil war can break out. The death of a monarch is only one possible way to enter a "civil war" scenario, and a "civil war" is only one of the possible outcomes. The player could just as easily have had a nice tea with the opposing leader and signed a truce!
Player actions can lead to customized experiences. If the player shows a tendency to kill Green Blobs instead of Pink Blobs, the game can increase or reduce the respawn rate of Green Blobs; if the player is constantly being killed by Dark Horsemen, the game can make that species weaker. If it's an online game, the background chosen for his character could be integrated into the persistent world's history, and the "Orphan of noble birth" could find his family's heirloom rings, swords, and other finery, or even be granted his title again!
New content is still expensive, but it's worth a lot more! Going back to the civil war example: A system like this makes it easier to add more kinds of choices. Rather than just one time at which the civil war could start, the player can choose when to trigger it, or, in fact, whether to trigger it at all. By making the parameters semantic with respect to the fiction, rather than static with respect to a bunch of game triggers, new combinations of existing content make every piece of added content automatically worth more. Since the available paths through a dynamic setting such as this can increase combinatorially with developer effort, as opposed to linearly, I propose the following challenge:

Design a unified system for expressing the preconditions, invariants, and postconditions of arbitrary incidents. It will be called Herodotus, after the father of history.

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

And here is how a textual game might interpret it:

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 list of incidents. As Perko points out, generating text was never the hard part. But what if we want to generate gameplay with this? Well, that's easy enough, once we grok the following: Any of those incidents could have been triggered by the player. Let's see that sequence again, but with some choice points interleaved:

Goddess of Creation:"Please choose a name, sex, and background."
IncidentType=PersonBorn Person=P730109 Father=P13024 Mother=P12049 Time=1370
Player: Richardson III walked to the Registry of Learning, and swore to devote five years to the study of tactics under a great master.
IncidentType=PersonTrained Person=P730109 Teacher=P10123 Specialty=S7 Time=1383
National News: A war erupts between Eyland and Targon.
IncidentType=WarStarted War=W7 Attacker=N1 Defender=N2 Time=1390
Player: Richardson III asks his father if he can join the army. His father requires that Richardson III prove his resolve by helping him paint a scene of a great past battle, while explaining the tactics of the incident.
IncidentType=PersonJoinsArmy Person=P730109 Army=A7 Reason=R4 Rank=K7 Unit=U512 Time=1391
Player: A battle breaks out near the military school. Richardson III manages to best the commander of the rival unit.
IncidentType=BattleWonByDefender Battle=B18 War=W7 Place=C197 AttackingUnit=U213 DefendingUnit=U512 Time=1396
National News: Richardson III is promoted.
IncidentType=PersonPromoted Person=P730109 Rank=K8 Time=1399

The choice or action points there may seem magical, but I think they can be easily framed in terms of existing game quantities, and are not necessarily more complex than a simulation game such as Civilization or SimCity. By expressing more and more quantities in terms of time-sensitive Fluents in a Herodotus timeline, incident generators can access massive bunches of data. For instance, the trial proposed by Richardson II took into account his own expertise, his son's trained skills, and his son's goal. So, there are two vectors for improving a Herodotus simulation: Increase the number of Incidents, and increase the variety of the Incident Generators, which can present choices to the player or to the NPCs.

Choices and Incident Generators

The first claim in the above paragraph bears some justification. In the parlance of Herodotus simulations, a Choice is any selection of one or more Incidents. Note that Choice is not a concept intrinsic to Herodotus, but a feature of games or simulations written to use it. Choices, in application logic, refer to data from one or more Histories, and might be driven by an underlying simulation ("If the strength of nation A is greater than the strength of nation B, and if A and B are unfriendly, A should start a war with B; otherwise, A should try diplomacy"), player choice followed by system response ("Hit the Diplomat with a Stick"), or even direct player intervention (as in a "choose your own adventure" game). This is what is meant by saying that such Choices are framed in terms of existing game quantities, and that they are no more complex than a standard simulation. Designing simulations is still hard! Herodotus just provides a consistent way to phrase simulations, so that some of the bookkeeping can be handled in a unified and automatic fashion.

An agent which resolves Choices to Incidents is called an Incident Generator, or Generator for short. Any number of Generators could run concurrently, even on a single History, and Generators can be arbitrarily complex.

The next step

This article intentionally ignores such details as how Incidents and Fluents are defined syntactically, as well as the particulars of this implementation of Herodotus. This is to keep me honest and focused on the real dynamic properties of this system, as opposed to getting caught up in how cool it is to geek around with mathematical representations. In the coming days, I'll start talking about how these ideas are expressed in the current implementation of Herodotus as I go through some sample simulations, which I'm going to call "Inquiries".

The first Inquiry will be a simple terrain generator to show how even incidents in geological time can "count" as historical occurrences. I'll also be showing an example of how an application's structure might, rather than access and store data directly, make use of various objects wrapping a single history to provide simple, time-centric access to data.

Finally, this and the following articles can be considered a "Request for Comment". If you have any questions about Herodotus, or suggestions on extending this essay to provide better information, please email me.

Thanks to Melissa Houlroyd, Rob Rix, and Andrew Eaton for their input on constructing this essay.

Additional Herodotus essays are visible in the sidebar at the right.

A Game for the Library: Encouraging Young Infovores

2007-12-20T12:00:00.001-05:00

The challenge

Design a fun way for children to get to know their library, their taste in books, and their own love of learning.

The tools

A computer game played with a simple controller, a library-card-keyed character account, parental assertion of having read books, and a kids' library layout which acts as a kind of Alternate Reality Game(ARG) to the computer interface. Potentially a remotely playable version.

The game

An exploratory, Castle Infinity-style environment with action and puzzles of various sorts, and on-topic books lying about to be found. Sample areas include Dinosaur Land, Robot Factory, Princess Castle, Knights' Barracks, Science Lab, Math Plane, Planetarium, Sportsville, etc. That determines the broad style. The specific genre - fiction, nonfiction, etc - is determined by the sorts of games played in that area. For example, the part of the Robot Factory where assembly takes place is going to lead to nonfiction on robots, and the part where the robots play with the user is in the fiction section.

Finding a book is like finding half a key. In order to progress, they might have to read the book. In-game, they might see an excerpt or introduction, and if they don't like it, they can ask for a different half-a-key. They can also ask for harder or easier reading, which will adjust their level accordingly. Books are picked both on user preference history and Amazon-style 'other users who liked this liked x'. Books aren't just boring keys, though; a book on chemistry might turn into an explosive to be used to clear an obstacle, or a book on dinosaurs could teach you to ride a particular dinosaur in an area. Feedback from this and the ARG will update player level(making new areas accessible), reading level(making new books accessible), etc. The system will also keep track of the books that have been read and the books that the player has enjoyed.

The ARG

The library's layout mirrors the game's layout as much as possible, bringing in characters, landmarks, and color cues from the game world. This helps children find books easily. Reading the book(and getting a parent to sign off on it via a web site or in-game action) ties this back into the computer game. Enjoyment/rating is also provided, and book length is taken into account.

Option: Rather than requiring parental approval, the game can ask comprehension questions based on the content of the book. It might be a good idea to do this anyway as the act of using the 'whole key' of the book.

A possible third part

The player's avatar is playable remotely in a different sort of game which uses the player's character level and 'points' in each area(science, math, space, dinosaurs, princesses, etc). For example, a role-playing game or a different platformer, more focused on point-driven activities like combat or negotiation.

The rewards

Immediate rewards from the enjoyment of a video game
Jumping, defeating enemies, solving puzzles, finding tokens, using tokens
Medium-term rewards from the enjoyment of reading matched to skill level and interest
Longer-term rewards as reading level improves and recommended books satisfy
Interim timing rewards are provided by Trophies: X books read, X areas explored, 15 Wotsits jumped on, X books in each area read, and so on.
Reading lists and accomplishments can be printed out on color certificates suitable for refrigerator posting.
Programs can be established with local schools and businesses to recognize achievement
etc...

Additional thoughts

Character customization. Let's provide 'parts' that can be found or rewarded and used to customize your avatar. In fact, let's borrow as much from Castle Infinity as possible, eh?

Big questions

Should this game be multiplayer? If so, should it be multiplayer across libraries? Should it allow free chat, or just symbol chat or sentence-manufacture? The ESRB says "Experience may change during online play" for a reason...

What about privacy? Is it bad to keep track of the books a kid has read? What if they're encrypted by the library? What if they're encrypted by a user's secret? What if they're stored offsite and encrypted? What if it's opt-in? What if the recommendation system is anonymous? What if books are one-way hashed, so the titles and other data are inaccessible, but each book is still uniquely identifiable? What if they're stored on the library card itself, or on a provided SD card? There are many questions about this that seem need an answer from the ALA. Losing this won't neuter the game, but it will make it less effective.

Can characters be moved from library to library if a player moves? Will there be balance issues between libraries?

How much content will need to be created to keep players of all skill levels from getting bored? See the Lost Garden review of Knytt for more on this. What about player-created or librarian-created content? How much involvement should the makers of this game have in its deployment?

How much violence is reasonable for this game? Mario-level? Less? Should death even be a concept? Again, refer to Knytt and C8.

Inspired by a conversation with Melissa Houlroyd.

Joe's Landfill

Justifying Blank Space

An Extended Absence

Rock, Paper, Scissors

The challenge

A War of Attrition

Taking the (Battle)Field

Advance Wars

Moving On

Stepping Forward

The Challenge

Lingua Franca

Trigger Happy

Stepping Back

The Challenge

The Changes

A Match Made in Heaven

Just Cause

Syntactically Delicious

Herodotus Query Language

Homage à Jones

The challenge

Setting the Stage

Send in the Code

Speak Fluent Erlang

Incident Archetypes

Trigger Action

Mission accomplished!

Rewriting History

The challenge

The Specification

Filling in the Blanks: Procedural Glue

A Sticky Situation

Pick and Choose

About Types

Calculated Character Creation

Designing a Story: Building Narratives from Story Atoms

Rboehme's Quest Generator

The Father of History and the Father of Lies

About the Simulation

In Terms of Herodotus

Location, location, location

Things and Stuff

Goals and Roles

Building Character

Making a Scene

Quest and Answer

Workshop Options

Some background

A Metaplace Of Your Own

Game Design 101

Game Design and Development with RubyGame

Fun and Board Game Design

8-Bit Music

Spider-Man 3

The Setting

Hard at Work

DMS, the Dynamic Dynamo!

Learning from History: Avoiding the Mistakes of the Past

Regaining perspective

Scales of Justice

Supply and demand

Fight or flight

Give the people what they want

But wait, there's more...

A Geological Inquiry: Grounding Herodotus's Theory

The challenge

Using the library

Designing the simulation

A single stone: lander-0.io

Noisome perturbations: lander-1.io

Even it out: lander-2.io

Game Over: lander-3.io

Wrapping up

Introducing Herodotus: Procedurally Fathering History

The challenge

The theory

Fluents

Incidents

Histories

A single stone: `lander-0.io`

Noisome perturbations: `lander-1.io`

Even it out: `lander-2.io`

Game Over: `lander-3.io`