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

[Sasha Hart]

This is GREAT!

Do you have anything informal you may report (e.g. about 
performance or the applications of the technique)?

Do you have any cool game logs to show off? 

Can I have one too? ;)

[Christopher Allen's doc]

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

I put the reference at the bottom of the page. [1]

This chapter describes Staddon's (example) computational model of
spatial search and compares it to aspects of performance in ants,
badgers, rats, monkeys, dogs, etc.  (Unfortunately, no small
children were compared). Although it is a fairly simple hillclimbing
algorithm it does a decent job of wandering around, grabbing food,
and learning about the locations of food (in my implementation).
Staddon claims that adjustment of one parameter (between-node flow
rate, basically) looks like superior "traveling salesman"
performance or apparent spatial insight in monkeys.

My implementation was not really fast. Grid size can really kill the
speed. Multiply a big grid by multiple individuals and it gets
worse. However, it is easy to have many individuals share and update
the same map to save resources (as a bonus it looks cool). One big
grid is in effect multiple small grids

The gain is obviously not as big as reducing the grid size a
lot. This being the case, there is another suggestion I have for
running it more quickly (other than being an optimizing
smarty-pants) and that is using a sparser network. To elaborate, it
is a completely optional property of this model that nodes should be
arranged in a grid. They could be linked any way you like (a nice
feature). You basically treated this in talking about mapping the
CAs onto the world. Your proposal was to use one-dimensional CAs -
it is possible to have cells which are distributed oddly and/or
linked arbitrarily. (Not sure about the performance difference,
urgh).

My example: a dragon could ignore spaces between population centers
and maintain nodes for each one, storing information about how many
virgins it ate there, but ignoring the likely virginless spaces in
between.  Of course, the more arbitrary you make the node layout,
the less pathfinding the algorithm does; and as links between nodes
define basically how it generalizes, inappropriate links will
generate bizarre generalizations (e.g. if cities are too far apart,
and they are modeled as adjacent, then a lot of virgins in one might
inappropriately stimulate a raid around the other, and the dragon
might fly back and forth many many times as he climbed the
gradient). So boring areas should get _some_ representation. (I
guess alternately you could have an implementation which scaled down
the flow based on connection strengths, which is a little bit into
neural net territory).

In an obvious sense algorithms like A* provide what is probably
better pathfinding for cheaper, particularly since making this model
run mazes (although entirely doable) entails having it maintain node
linkages. If you wanted the critters to be *smart* you would
probably be faced not only with intelligent management of the "flow"
(local averaging which spreads values across nodes) but also of the
density of nodes and connectivity between them. I wouldn't take this
that far for a game.

> 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:

You're right ahead of me - I was about to suggest sticking together
the hill climbing and the CAs. Not only that, this duplicates what I
said above about map sharing. It's cool - I still have concerns
about the constable running around just like a badger looking for
peanuts (just kidding). But seriously, with the right rules this
would even let your constables hang out in hot spots when they have
nothing else nearby to handle. If (for example) players tend to
commit a crime a lot in a place, the density of constables goes
up. If (for example) players make a great big diversion, but within
a few nodes, then the constables run over en masse and the players
have an easier time cracking the safe (or what have you).

This is great, but if you want the constables to really zip in and
collar the criminals, you are at the mercy of the flow rate. If the
flow rate is high you miss some of the other stuff. I don't know
what to say about this, my head is still swimmy.

[1] Staddon, J.E.R. (2001). Adaptive Dynamics. pp. 280-309.
Cambridge, Mass: The MIT Press. 

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