[MUD-Dev] Skotos Cellular Automata Simulation System - a Technical Summary (LONG)

Christopher Allen ChristopherA at skotos.net
Tue Apr 30 17:07:53 New Zealand Standard Time 2002


We are in the process of updating all of our Skotos "Technical
Systems" documents as we are now recruiting and training more
StoryBuilders for our games.

These Technical System documents are basically internal documents
like the ones we released here at MUD-Dev on proximity:

   http://kanga.nu/archives/MUD-Dev-L/2000Q2/msg00414.php

and on bulk:

   http://kanga.nu/archives/MUD-Dev-L/2000Q2/msg00701.php

With the recent discussions on the topic of using simulations in
online games, here is the one on Simulations and Cellular Automata.

We would like to eventually make this available on our web site at:

   http://www.skotos.net/articles

...so any quotes, references, comments or criticisms would be
appreciated.

------------------------------------------------------------------------
.. Christopher Allen                                 Skotos Tech Inc. ..
..                           1512 Walnut St., Berkeley, CA 94709-1513 ..
.. <http://www.Skotos.net>               o510/647-2760  f510/647-2761 ..



The Skotos Cellular Automata Simulation System - A Tech Summary
===============================================================
(c)2002 by Skotos Tech Inc. <http://www.skotos.net>

DRAFT 4/30/2002 -- Please send comments to ChristopherA at skotos.net

---++ No Man is an Island

   "No man is an island, entire of itself;
   every man is a piece of the continent, a part of the main;
   if a clod be washed away by the sea, Europe is the lesser, as well
         as if a promontorie were,
   as well as if a manor of thy friends or of thine owne were;
   any man's death diminishes me, because I am involved in mankind;
   and therefore never send to know for whom the bell tolls;
   it tolls for thee."
   -- John Donne (circa 1623)

Simulations are one of the most powerful tools available to game
designers. They've already been used successfully by single-player
games like *The Sims* and *SimCity*, but are just now coming into
use for online worlds.

By defining rules and initial starting conditions, game designers
can create constantly expanding worlds that have more variety and
variability than is possible in a static game design. In addition,
simulations can allow players to act upon the world in certain
specifically defined ways and thus have real impact upon their game
worlds. (See "The Dynamic Dilemma" under
http://www.skotos.net/articles/TTnTtopical.shtml#engineering for
more discussion on static v. dynamic game design.)

Over the last decade and a half a lot of thinking has gone into the
ideas of simulations in online games. However, despite their success
in the single-player genre, simulations have not yet been
successfully released for multiplayer use.


---+++ Problems Addressed by Simulations

Implementing a simulation under a game world can address a number of
problems. These include problems where players have too much impact
on the world or in game balance, or have insufficient impact on the
world.  Either kind of problem can break suspension of disbelief,
and solving these problems can also make a game more complex and
interesting.


---++++ Problems of Attenuation

As the only truly volitional beings in a game world, players have
far more impact on things like economics then they would in the real
world.  Combined with some out-of-character dynamics of game
worlds--such as the relative anonymity of players and the lack of
real consequences--players can completely off-balance a game world.

For example, it has long been recognized that it is difficult to
have a realistic economy in a game world--even a simple supply and
demand system doesn't work effectively because players will behave
differently online than they would in a real economy. More complex
simulations can attenuate player effects on supply and demand by
simulating many NPC actions using a more ideal model, thus
mitigating some of the player effects of economy by reducing them to
a fraction of the economic whole.


---++++ Problems of Amplification

Conversely, in most other areas players have far less of an impact
upon the world than they desire. Worlds don't tend to change, either
due to player action or in spite of it, and this lack of change can
break the suspension of disbelief required for an online world.

Simulations allow a world to change over time. Biological
simulations can modify populations through birth, aging, and
death. Ecological simulations fuel the creation, repair, and
consumption of items. A carefully built changeable world feels more
real over time than a fixed world.

Raph Koster, long ago on MUD-dev, approached the same issue from a
different direction when he said: "The expectation we found was that
every effort must result in a reward." A changing world offers a
reward for players of a game, because they can feel that they've had
a real impact.


---++ Simulation Approaches

There are a variety of simulation approaches. The most important for
online games are:

   * Autonomous Agents
   * Evolutionary Algorithms
   * Neural Networks
   * Heightmaps & Hill Climbing
   * Cellular Automata


---+++ Autonomous Agents

An autonomous agent is a software program, that, when given a goal,
will attempt to accomplish that goal without requiring the
supervision by a human. An autonomous agent can ask for and receive
advice, offered in human terms, when stuck, but otherwise would be
doing its business within a computer's world.

Agents can be characterized by a number of different properties.

Some relate to general issues of how they achieve goals:
   * Reactivity: the ability to selectively sense and act
   * Autonomy: goal-directedness, proactive, and self-starting behavior

Some relate to how they interact with humans and agents:
   * Collaborative behavior: the ability to work in concert with other
     agents to achieve a common goal
   * Knowledge-level communication ability: the ability to communicate
     with persons and other agents with language more resembling human-
     like 'speech acts' than typical symbol-level program-to-program
     protocols
   * Personality: the capability to manifest the attributes of a
     'believable' character such as emotion

Some relate to experience:
   * Inferential capability: the ability to act on abstract task
     specification using prior knowledge of general goals and preferred
     methods to achieve flexibility; goes beyond the information given,
     and may have explicit models of self, user, situation, and/or other
     agents.
   * Temporal continuity: persistence of identity and state over long
      periods of time
   * Adaptivity: the ability to learn and improve with experience

Some relate to other issues:
   * Mobility: being able to migrate in a self-directed way from one
     host platform to another.

There are a wide variety of different autonomous agent approaches.
However, the subset which is sometimes called a "deliberative agent"
is quite useful in game simulations. A deliberative agent is one
that possesses an explicitly represented, symbolic model of the
world, and that makes decisions via some form of reasoning (for
example about what actions to perform).

An example might be a Merchant, who has an internal model of his
customers, and varies his prices accordingly.


---+++ Evolutionary Algorithms

Evolutionary algorithms try and apply Darwinian evolutionary ideas
to simulations. They've been around for more than thirty years, but
have only become particularly popular in the last few decades. Types
of evolutionary algorithms include: genetic algorithms, genetic
programming, evolution strategies, and evolutionary programming.
Problems being attacked by evolutionary algorithms include automatic
programming, optimization, machine learning, economics, operations
research, evolutionary studies, learning studies, and of course
ecology, population genetics, and social systems.

Genetic algorithms are good examples of the entire programming
paradigm.  These algorithms are built upon populations of
individual. Each individual represents a possible solution to a
given problem in the form of a string of symbols, known as the
genome. Together all of the individuals sum the "search space",
which is all of the possible solutions to a problem. The problems
which genetic algorithms are being used upon tend to have such large
search spaces that they could not be exhaustively searched.

Once the entire search space has been defined, the following
procedure is used for a genetic algorithm:

   1. Randomly or heuristically generate an initial population of
     individuals.
   2. Begin stepping through "generations" during which you:
      a. Mutate individuals.
      b. Evaluate each individual based on a predefined "fitness
         function".
      c. Select individuals for the next generation based on their
         fitness, most commonly in proportion to their fitness.


---+++ Neural Networks

The basic idea of a neural network is to create an analogous
structure to the human brain in electronics (an artificial neural
network) or in biology (a biological neural network). Numerous
processing units (neurons) are highly interconnected via weighted
connections (synapses), whose weights are adjusted based on data
input. Neural networks have been around for over 50 years, but only
practically used for the last 20 or so.

Neural networks typically learn behavior by seeing data and
weighting synapse connections based upon that data. Sometimes this
is done on the fly, as with the financial market neural networks
which have been created, while in other behavior is purposefully
taught before the neural net is put to use.

Pattern recognition, game playing, and data prediction are some of
the most obvious uses of neural networks, but they have actually
received wide applicability in a number of industries.


---+++ Heightmaps & Hill Climbing

A fairly simple hill climbing algorithm acts as the basis of the
simulation in _The Sims_. Each sim has a number of needs (hunger,
sleep, entertainment, interaction, etc) which are represented within
the sim by scalar fields. Each object within the world which can
fulfill a need (refrigerator, bed, television, neighbor, etc)
projects a vector field.  The vector fields offer stronger
attraction to sims whose related scalar needs are greater and lesser
attraction to sims whose related scalar needs are smaller.

Together, all of these vector fields form a sort of
three-dimensional map (or heightmap) for each sim. Simple hill
climbing algorithms can be used to navigate the map, with
pathfinding or timeout mechanisms being used to get out of local
loops.

_The Sims_ uses heightmaps created via an entirely arbitrary
methods-- the maps are generated based on specific values pre-stored
within the objects themselves. _Staddon_ uses a variation of the
idea where the vector fields are created within objects on a
per-character basis based upon experience. If a player finds that an
object meets his needs, it's value is increased, while if it does
not, it is decreased. This can create enormous overhead if each
character has their own set of vector fields for every object in a
game, but allows for an experience-based algorithm which a
pre-defined vector field does not support; in some ways its similar
to the learning experienced as part of neural nets.


---+++ Cellular Automata

Another significant approach to simulation is known as "cellular
automata", or CA. The most well-known CA simulation is "Conway's
Game of Life" -- using only three simple rules it has proven to have
very dynamic and interesting behaviors that have kept computer
scientists interested for decades.

The cellular automata technique of simulation differs from the other
techniques because it is discrete, regular, and synchronous. These
properties makes it easier to implement on a computer.

A cellular automata is made up of a regular array (known as a
"lattice") consisting of points (known as "cells") that can have one
of a finite number of states. The state of each cell in the lattice
is updated according to a "local rule", causing the state of the
entire lattice to advance in discrete time steps (each known as a
"generation").

All cells on the lattice are updated synchronously; that is, the
state of a cell at a given time depends only on its own state one
time step previously, and the states of its nearby neighbors at the
previous time step.


---++++ Conway's Game of Life

In "Conway's Game of Life" the simulation is played on rectangular
lattice, each cell having one of two states - alive or dead. Each
cell has eight neighbors (known as "adjacent cells"), arranged at
the eight cardinal directions.

There are three simple local rules which determine the state of a
cell based on the previous generation:
   * If the cell is alive, and it has 0, 1, 4, 5, 6, 7, or 8 living
     neighbors, the cell dies (0, 1 neighbors: of loneliness; 4 thru 8:
of
     overcrowding) in the next generation.
   * If the cell is alive, and it only has 2 or 3 living neighbors, the
     cell continues to be alive into the next generation.
   * If the cell is dead, but has exactly three living neighbors, in the
     next generation it will be alive (birth).

In spite of these simple rules, extremely complex behaviors have
been found in the game of life, including: repeating patterns of
living cells; simple patterns that grow into huge, complex ones;
patterns that appear to move (gliders and spaceships); patterns that
generate a continuous stream of moving patterns (glider guns); and
even some very complex patterns that appears to replicate
themselves.


---++++ CAs in SimCity

It is not very well known, but the very popular game _SimCity_ and
its sequels use cellular automata for most of the underlying models
that make up the simulation of a city.

The SimCity simulation is made up of many different CAs, each a
separate lattice, each with local rules, but all interlinked. For
instance, the local rule for the pollution CA lattice makes a
polluted cell diffuse its pollution into adjacent cells until the
pollution is so diffused that it is totally gone from the lattice. A
different CA lattice containing the information about SimCity's
factories adds pollution to the individual cells in the pollution CA
lattice. Yet another lattice, the crime CA, is influenced by the
constant pollution in the pollution CA and raises the chance of a
crime in that cell accordingly.

Each of the local rules and each of the rules between lattices is
very simple, yet together can result in very realistic and
non-deterministic behaviors. For instance, a city planner in Detroit
modeled a neighborhood that he was having problems with inside of
SimCity, and discovered that what happened in the SimCity simulation
was exactly what happened in real life. This gave him the ability to
test some different ideas using the same initial conditions without
having to physically tear down houses.

SimCity, in its sequels and follow-on products like SimEarth, shows
the power of cellular automata to simulate very complex systems.


---++++ Weaknesses of Cellular Automata

In spite of the success of cellular automata simulations like
SimCity, cellular automata as a simulation technique is not
perfect. Cellular automata designers find that very small tweaks in
the rules that you would think would have little effect can have
huge effects in the outcome. Also, the regularity and synchronicity
of CAs may add unrealistic effects.

For instance, even the way the simulation iterates through the cells
(e.g. left to right repeatedly, or back and forth, or a more complex
iterative technique) can have effects on the behaviors of the
simulation. The size and shape of the cells (e.g. rectangles,
hexagons), the number of adjacent neighbors, etc. will all result in
non-obvious behaviors.

Thus when designing a simulation, a CA designer will try many
different local rules until they begin to see the behaviors they
want. However, these rules often contain many tweaks to compensate
for behaviors caused by the CA technique itself. The result is that
CA simulations are not verifiable -- they have the behaviors that
they have because designers kept trying until they saw the behavior
they wanted. Unplanned but realistic behaviors are rarely accurate.

CAs are also very vulnerable to runaway effects. You may run a
realistic-seeming simulation a 100 times, but the 101st time it may
have a runaway disaster that is entirely unrealistic. When you play
a game like SimCity, you just play the game again, but in an ongoing
game world this might not be possible -- constant tweaking and
forward testing is probably required.


---++ Summary of the Skotos CA Simulation System

---+++ Problems Addressed by Skotos CA Simulation System

SkotOS has a simple cellular automata engine that can be used by the
game designer to add complexity and richness to a world. This CA
system can also be used for global variable storage, or storage of
simple scalar field simulations.

The CA Engine has a number of limitations, and it is not optimized
for speed. However, it should be sufficient for simple biological,
ecological, and economic systems in a game world.


---+++ Creation of Lattices

To create a cellular automata simulation, the game designer creates
an XML object that describes a two-dimensional lattice. This lattice
may have an arbitrary height and width, though the most common types
are square (i.e., 32x32 cells) or one dimensional (i.e., 1x128
cells). You generally should not go above 64x64 unless you really
know what you're doing. A single improperly designed 128x128 lattice
can slow the machine to a crawl.


---++++ Additional Attributes

Each lattice also has a number of additional, mandatory attributes:

   * *Delay* - How often your CA iterates.
   * *Left, Right, Top, and Bottom Conditions* - Define what happens
     when a cell is read from off the edge of the lattice. Options are:
      * _Mirror_ - The edge wraps around and the cell from the opposite
        side of the lattice is read.
      * _Fixed_ - The edge is set to a fixed value.
      * _Differential_ - The cells beyond the border different from the
        cells on the border by a fixed amount, 0 being a common choice.
   * *Left, Right, Top, and Bottom Values* - Variables that relate to
     the conditions. They do not need to be set for mirror, but must be
     for fixed and differential.
   * *Iteration-Rule* - The rule that is applied to each cell in each
     iteration to determine the new value of the cell in the next
     generation.

In addition, each cell within the lattice will have a
value. Typically the range 0 to 255 is used, though technically any
values are possible.  At current these cell values are set through
in-game methods.


---+++ Methods

The iteration-rule is the heart of the method which is used to
determine how a CA evolves over generations. It is run once for each
cell in each generation. It is written in a language called MERRY,
which is a sandboxed version of LPC, which is in turn is an
object-oriented interpreted language variant of C.

MERRY has a number of special purpose functions available to it. It
can easily look up values of other cells in the lattice and can even
look up values in other lattices. For example, the variable $ne is
always equal to the northeastern cell from the cell which is
currently being iterated over. There is a level of abstraction here
to take into account complexities of the simulation, such as the
edges. The variable $ne will always do the right thing for any cell,
based on how the edge condition variables are set.


---+++ Adjusting Simulations

All adjustments to cells in a simulation are done through
command-line options. Four properties can be set to start
simulations, stop simulations, run a simulation through a single
iteration (while it's stopped) and clear all the cells of a
simulation. Each is done by setting the value "1" in the appropriate
property (stop, start, clear, iterate):

   > +setprop test:simulation:life stop 1
   Done.

   > +setprop test:simulation:life iterate 1
   Done.

   > +setprop test:simulation:life iterate 1
   Done.

Setting cell values in a CA is done through a similar method, using the
property "point(x, y)":

   > +setprop test:simulation:life point(10,10) 128

The x and y values both originate at the top left, going right and down.

Cell values are most typically viewed through the web developer
interface, where the object includes a graphical grayscale map showing
the cell values of the entire lattice.


---+++ Example: Life CA Simulation

The following object is a fairly simple, functional example of a CA in
the Skotos System representing Conway's Game of Life:

<object id="OBJ(test:cellular:life)">
  <context/>
  <SkotOS:CANode width="32" height="32" delay="5" left-condition="wrap"
  left value="0" right-condition="wrap" right-value="0" top-
  condition="wrap" top-value="0" bottom-condition="wrap" bottom-
  value="0" iteration-rule="int count;

/* count the number of non-zero (live) neighbours */
count = !!$nn  + !!$ne + !!$ee + !!$se +
        !!$ss + !!$sw + !!$ww + !!$nw;

if ($cell) {
  /* if we're alive we stay alive with 2 or 3 neighbours */
  if (count == 2 || count == 3) {
    return 128;
  }
  return 0;
}
if (count == 3) {
  /* if we are dead, precisely 3 resurrects us */
  return 128;
}
return 0;" state="">
    <Notes:Notes/>
  </SkotOS:CANode>
</object>

In the example, the SkotOS:CANode line specifies all the standard info,
including width, height, and all the edge conditions. It ends with the
iteration-rule, which runs through a number of lines following. They're
very simple. During each generation:

   1. A count is made of nearby cells for each cell.
   2. If a cell exists and it has two or three living neighbors, it
      remains alive (a value of 128).
   3. If a cell exists and it has any other number of living neighbors,
      it dies (a value of 0).
   4. If a cell is dead and has three neighbors, it resurrects.

Although the above object creates the CA, it does not populate the
lattice. As noted above, this is done in-game, typically with the
+setprop command. Typicaly within a game, cell values will be defined
based on objects and actions within the game.


---+++ Example: Heat Diffusion

The following very simple diffusion has an interesting starting position
based upon the conditions of the four sides, which are all different
values. It models heat diffusion. Lighting a point up causing it to
spread out to nearby cells in future generations:

<object id="OBJ(test:cellular:diffusion)">
  <context/>
  <SkotOS:CANode width="64" height="64" delay="10" left-
    condition="fixed" left-value="255" right-condition="fixed" right-
    value="0" top-condition="fixed" top-value="128" bottom-
    condition="differential" bottom-value="0"
    iteration-rule="
    return (4 + $nn + $ne + $ee + $se + $ss +
    $sw + $ww + $nw) / 8;" state="">
    <Notes:Notes/>
  </SkotOS:CANode>
</object>


---+++ Example: Layered CAs

CAs become very powerful when you layer multiple lattices. This is done
by creating multiple CAs which may be layered on top of each other and
which influence each other in simple ways. Layering lattices is simplest
if you have created multiple lattices that are identically sized.
However, you can also create differently sized lattices and transform
them.

The following example is a bit of MERRY code which influences one CA
(crime) based upon another CA (wealth). Each CA exists on its own, and
is not included here. We assume that each CA has its own method for
distributing information through multiple generations (probably each of
crime and wealth diffuse to nearby areas by some simple method).

What the below code does is constantly read the two CAs and adjust crime
based on wealth.

/*
** Object:   GothamCity:CA:Daemon
** Script:   merry:lib:mainloop
** Purpose:  Loop endlessly, slowly letting wealth influence crime
*/

/* we presume these two Cellular Automata exist and work correctly */

$crimesim  = $object(GothamCity:CA:Crime);
$wealthsim = $object(GothamCity:CA:Wealth);

/* loop for eternity */
while (TRUE) {
  /* the crime CA is 32 x 32 */
  for ($x = 1; $x <= 32; $x ++) {
    for ($y = 1; $y <= 32; $y ++) {
      int wealth_x, wealth_y;
      int crime, wealth;
      int delta_crime;

      /* wealth CA is 8 x 8: transform coordinates */
      wealth_x = ($x / 4); wealth_y = ($y / 4);
      /* points are read using the derived property point(x, y) */
      wealth = Get($wealthsim, "point(" + wealth_x + ", " +
                                          wealth_y + ")");
      /* wealth ranges from 0 to 255 */
      if (wealth < 64) {
        /* poverty increases crime */
        delta_crime = 1;
      } else if (wealth < 192) {
        /* middle class living: no effect */
        delta_crime = 0;
      } else {
        /* but significant wealth decreases it */
        delta_crime = -1;
      }

      /* now modify the crime simulation */
      crime = Get($crimesim, "point(" + $x + ", " + $y + ")");
      crime = crime + delta_crime;
      /* make sure we don't go out of range */
      if (crime < 0) {
        crime = 0;
      } else if (crime > 255) {
        crime = 255;
      }
      /* write the new value back */
      Set($crimesim, "point(" + $x + ", " + $y + ")", crime);

      /* done with this point: sleep for 0.1 seconds */
      $delay(0.1);
    }
  }
  /* one full sweep done: sleep a little longer and then go again */
  $delay(60);
}

As you'll note, the entire process is accomplished through two very
simple MERRY functions: Get, which reads a property from an object, and
Set, which sets a property in an object.


---+++ Example: Integrated CAs

Once you have created a CA, or possibly multiple layers of CAs, you may
have some nice, interesting programs, but they're not too useful unless
you can tie them in to your game. There are two general ways to do this:
a geographic correlation and an arbitrary correlation.

When you make a geographic correlation you lay out your game map on a
two-dimensional grid. There doesn't necessarily have to be a one-to-
one-correlation between rooms in the game and points on the grid--
instead, you might skip multiple grid points, which would be a perfectly
valid way to represent rooms that are large are far apart.

For example, assume that you have a simple map for a game of five rooms
laid out as follows:

   A ---- B ---- C
   |             |
   D ----------- E

In this situation you would probably lay out a geographic correlation as
follows:

   |A|0,0|
   |B|1,0|
   |C|2,0|
   |D|0,1|
   |E|2,1|

This type of geographic correlation is most useful if you wish
information to diffuse between different cells. However, it starts to
break down if your map is three-dimensional or if there are multiple
locations within your game where there are blockages preventing movement
between adjacent areas on your grid.

For example, Castle Marrach is a complex three-dimensional location.
Worse, there are multiple choke points (such as the Bridge between the
two Baileys) and multiple places where, even at the same levels, you
can't get between nearby locations (such as the second floor of the
Outer Bailey, which is broken up into three, totally discrete sections).
In order to use a geographic-correlated lattices for Castle Marrach you
would have to create a large number of lattices for each simulation,
each using the same iteration rules, and then use daemons to pass
information back and forth between the different lattices. For example,
you would have a ground floor Inner Bailey lattice and a ground floor
Outer Bailey lattice, and the daemon would pass information through the
chokepoint of the Great Bridge. Likewise you would have a multitude of
lattices for that second floor, and each would pass information up and
down the stairs, but not between each other. This all seems somewhat
doable, but a fair amount of work.

An arbitrary correlation would work better in some regards for a complex
geographic situation like Castle Marrach. In this case you create a one-
dimensional lattice and then arbitrarily assign each room in the game to
a cell. You can not do diffusion in this sort of model, but you can
constantly iterate through an algorithm for each room. For example you
could have functions within the game which increased the crime value of
a cell when a crime occurs, and a CA function which slowly decreases
that function over time. Then, constables in a game could constantly
look for the CA cell with the highest crime value, then do a breadth
search to find the shortest path to the crime locale.


---++++ Accessing Values in Integrated Lattices

Once you've created lattices and integrated them into your game, they
exist as standard game object properties, thus accessing their values is
fairly simple. In all likelihood, each room in your game has a property
that holds the grid coordinate in the lattice associated with that room.
In my example above, room A would probably have a property which held
the value "0,0". This property has a standard name (i.e., "ca_value").

Then, to make use of the value the CA is holding and act accordingly,
all you have to do is:
   1. Look up the x,y coordinate in the standard property.
   2. Use that result to look up the cell value in the CA.
   3. Take action based upon that result.

Assume that you wanted to build a constable who always went toward
crime, and your map was simple enough that you could use geographic
correlation. You might do the following:
   1. Underlie your gameworld with a grid for a crime CA.
   2. Have a simple diffusion function in the crime CA which slowly
      spreads word of a crime to nearby cells.
   3. Have criminal actions increase the crime value of their current
      cell.
      a. You'd do this by building a script into criminal actions.
      b. This script would look up the x,y coordinate of the current
         room.
      c. Then it would increase the crime value of the cell associated
         with the room.
   4. Have constables always move toward the most crime.
      a. They would look up the object names of the rooms connected to
         all the exits.
      b. Then look up the grid coordinate for each of those objects.
      c. Then look up the cell value for each of those grid coordinates.
      d. Then select the cell value, and thus the exit, with the highest
         value.
   5. Because crime diffuses, hill-climbing toward the greatest crime
      value will inevitably lead constables to the crime.

A very similar method could be used to allow battles (or even talking)
to attract monsters in a combative game. A number of simulations that
direct CNPC movement or action could be imagined.

Economic simulations could also be easily created with this method, with
buying, selling, and even stealing all changing the economics of an
area.


---++ State of Development

The Skotos CA Simulation is currently complete, as described above. It
has not yet been integrated into any of the Skotos games yet, and thus
some of the last discussion is partially speculative, but theoretically
sound.

Some additional work on CAs could improve the ease of use for
developers:
   * A library could be created providing a number of special purpose
     functions for the whole lattice, for instance "max", "min",
"median",
     "average", etc.
   * A library could also automate lattice transformations to make it
     simpler to map lattices of different sizes to each other.
   * An API should clarify how SkotOS World Objects read and write to
     CAs.

Some additional abilities within a CA could add complexity, including:
   * A generation_count which determines how many generations a CA has
     been running for.
   * generation_start_method and generation_end_method which define
     additional actions to be taken before or after the
iteration_method.
   * A generation_interval, which defines how often this lattice's
     iteration_method should be called in comparison to other
     iteration_method's in the same simulation (adjusted by the order of
     the lattice). By default, every cell will get executed once per
     generation. However, a particular lattice could be updated every
     other generation with a generation_interval of 2, and the
     iteration_method's would do half the cells during each normal
     generation.
   * A simulation_generation_heartbeat, which describes how often the
     simulation should be executed in real time.


---+++ Open Issues in the CA Simulation System

   * There may need to be an edge_method which is executed when an
     attempt is made to obtain the value of an edge cell.
   * Timing issues remain an open question, particularly with how reads
     and writes from SkotOS World Objects might interact with
generations
     being processed.
   * A sufficiently large simulation might require CAs to be run on a
     separate process or server, which would require a new communication
     method.
   * Is inheritance useful for simulations? If so, how would it be
     applied?


---++ Bibliography

Simulation for the Social Scientist (Nigel Gilbert and Klaus G.
Troitzsch):
<http://www.uni-koblenz.de/~kgt/Learn/Textbook/Book.html>

Seeing Around Corners - The Atlantic Monthly: The new science of
artificial societies suggests that real ones are both more predictable
and more surprising than we thought.
<http://theatlantic.science.printthis.clickability.com/pt/printThis?clic
k
Map=printThis&fb=Y&url=http%3A//www.theatlantic.com/issues/2002/04/rauch
.htm&title=The%20Atlantic%20%7C%20April%202002%20%7C%20Seeing%20Around%2
0Corners%20%7C%20Rauch&random=0.8727591629914607&partnerID=58&expire=>

International Society for Artificial Life
<http://alife.org/>

Edge of Chaos Cellular Automata:
<http://kal-el.ugr.es/~louis/cosi/cellularAutomata.html>



_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev



More information about the MUD-Dev mailing list