A Geological Inquiry: Grounding Herodotus's Theory

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:

1. Download Io
2. 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.
3. In the base Io directory, run the following commands:
   • make
   • sudo make install
   • sudo make linkInstall
   • make testaddons
4. 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.

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.