<!-- MHonArc v2.4.4 -->
<!--X-Subject: [MUD-Dev] cellular automata as universe models -->
<!--X-From-R13: Xnzrf Ivyfba <wjvyfbaNebpurfgre.ee.pbz> -->
<!--X-Date: Sun, 13 Sep 1998 16:27:11 -0700 -->
<!--X-Message-Id: 98091318192402.04290@d185d1e96 -->
<!--X-Content-Type: text/plain -->
<!--X-Head-End-->
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<html>
<head>
<title>MUD-Dev message, [MUD-Dev] cellular automata as universe models</title>
<!-- meta name="robots" content="noindex,nofollow" -->
<link rev="made" href="mailto:jwilson#rochester,rr.com">
</head>
<body background="/backgrounds/paperback.gif" bgcolor="#ffffff"
text="#000000" link="#0000FF" alink="#FF0000" vlink="#006000">
<font size="+4" color="#804040">
<strong><em>MUD-Dev<br>mailing list archive</em></strong>
</font>
<br>
[ <a href="../">Other Periods</a>
| <a href="../../">Other mailing lists</a>
| <a href="/search.php3">Search</a>
]
<br clear=all><hr>
<!--X-Body-Begin-->
<!--X-User-Header-->
<!--X-User-Header-End-->
<!--X-TopPNI-->
Date:
[ <a href="msg01039.html">Previous</a>
| <a href="msg01041.html">Next</a>
]
Thread:
[ <a href="msg01061.html">Previous</a>
| <a href="msg01046.html">Next</a>
]
Index:
[ <A HREF="author.html#01040">Author</A>
| <A HREF="#01040">Date</A>
| <A HREF="thread.html#01040">Thread</A>
]
<!--X-TopPNI-End-->
<!--X-MsgBody-->
<!--X-Subject-Header-Begin-->
<H1>[MUD-Dev] cellular automata as universe models</H1>
<HR>
<!--X-Subject-Header-End-->
<!--X-Head-of-Message-->
<UL>
<LI><em>To</em>: <<A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A>></LI>
<LI><em>Subject</em>: [MUD-Dev] cellular automata as universe models</LI>
<LI><em>From</em>: James Wilson <<A HREF="mailto:jwilson#rochester,rr.com">jwilson#rochester,rr.com</A>></LI>
<LI><em>Date</em>: Sun, 13 Sep 1998 16:43:15 -0400</LI>
<LI><em>Reply-To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI>
</UL>
<!--X-Head-of-Message-End-->
<!--X-Head-Body-Sep-Begin-->
<HR>
<!--X-Head-Body-Sep-End-->
<!--X-Body-of-Message-->
<PRE>
Hi all, I've been thinking about how one might use cellular
automata to model a universe. By 'cellular automata', I mean a
set of nodes where a given node's state changes are completely
determined by a set of neighboring nodes. (The research community
uses the term a little more carefully than I do. Purists, please forgive
my insolence.)
The application to a virtual universe might look like this:
nodes represent spatial locations.
state changes of any objects within those locations are changes
in node state.
nodes are neighbors of spatially proximate nodes.
the CA constraint that state changes are determined entirely
by a node's current state and the states of its neighbors means
that a node may not directly alter the state of a non-neighbor node.
For instance, if the world graph is
node A <--> node B <--> node C
then events in node A cannot directly impact node C. (They can,
however, propagate into B and thence into C.)
Note that this constraint is orthogonal to one's execution model, i.e.
one can implement an event-based or a polling model inside each
node to determine state changes. In this post I am writing about
event-based examples, but all can be adapted to polling systems
as well.
The advantage of this system is that synchronization *might* become
trivial; since each node's state changes only depend on neighboring
nodes, one must only synchronize overlapping sets of nodes. The system
as a whole may remain mostly parallel. One might be thus able to rule out
deadlocks entirely by synchronizing inter-node access properly.
For instance, off the top of my head, suppose you have some set of worker
threads operating upon your node graph. As threads become available,
they scan the graph for nodes with pending events. (Alternatively, events
in a queue can be associated with a node, which the thread then tries to
lock as follows.) If a node, A, has a pending event and is not currently
locked, the thread then checks to see if all of A's neighbors are unlocked; if
any are, the thread gives up on A (and its event) and tries another node.
Otherwise, if all of A's neighbors can be locked, the thread then proceeds to
execute whatever needs to be executed within the scope of node A. (The
issue of event duration, which I harp upon so much, is of course still with
us.) The thread then unlocks the nodes and tries again. In this system,
deadlocks are (I think) impossible; threads do not block waiting for locked
nodes, but move on to other pending events under the assumption that the events
which require the locked nodes will be serviced promptly by some other thread
when they come free. (This is analogous to something I suggested a while back
in the latest lockless-db exchange: if one can know beforehand the set
of objects an event will operate upon, one can lock them all before the
start of the event and free them at its end. The CA constraint guarantees
this knowledge.)
The CA constraint does introduce some obstacles to user scripting. First,
objects cannot simply save references to one another, as the objects might
then migrate into remote nodes, in which case access would violate the CA
constraint (and thus break any synchronization model that relies on it). Also,
inspection of objects must be confined to the node which is the site of the
inspecting event, and its direct neighbors.
For instance, this would rule out a script which accessed every player
object in turn (assuming the players are not all in the same node). Also
illegal would be a (naive) implementation of a homing device which is
connected by a reference to a remote tracking object. However, both of
these can be implemented in a CA model by propagating events through
the node graph (assuming the graph is connected). Possibly there are effects
which cannot be emulated by propagation, and there is an efficiency
consideration - direct references are much more efficient than broadcasting
messages to lots and lots of nodes. Another problem would be handling
objects so large they span multiple nodes - does a gigantic warship move
atomically from node to node, or does its prow come in first, then its
foredeck, etc? (The solution to this might have some interesting ramifications -
perhaps fog in one area would then envelop different portions of the ship
at different times as it moves into the foggy area.)
As a 'realism' constraint, there is a real-world parallel; namely, information
and thus causality cannot propagate faster than the speed of light, so there
is no instantaneous causality across remote areas of space. (Quantum
correspondences don't let you out of this either, unfortunately, but that's
highly OT. *heh*) Perhaps one could loosen the correspondence between
spatial locations and nodes - allowing mobile nodes, wormholes, dynamic
changes to the node graph, and the like - without breaking the underlying
synchronization model.
To be perverse: at one extreme, each object could be a single mobile node,
but this would obviate any gains realized by serializing groups of spatially
local objects, and seriously complicate the process by which events inspect
their environment.. At the other extreme, nodes could be so large that
serialization of their state changes would be tantamount to serializing the
whole db, which of course is an option but one I am interested in avoiding.
The useful case is where nodes are large enough to conveniently serialize
db state changes while not terribly inconveniencing script writers.
The node and its neighbors would have to be understood as the 'environment'
available to an event, and script writers would need to work under the
assumption that information from outside this local environment is unavailable.
This is essentially the same constraint that human users of VR environments
(and real world systems) operate under; that is, one's responses are determined
by one's internal logic (mind, instincts, physical laws, etc) and one's
immediate environment (through sensory data or physical interactions). I'm not
sure how this constraint could translate into a scripting system, however. One
would need to remove direct references and proxy all object accesses through
the environment; how could this be done efficiently?
James
</PRE>
<!--X-Body-of-Message-End-->
<!--X-MsgBody-End-->
<!--X-Follow-Ups-->
<HR>
<ul compact><li><strong>Follow-Ups</strong>:
<ul>
<li><strong><A NAME="01046" HREF="msg01046.html">[MUD-Dev] Re: cellular automata as universe models</A></strong>
<ul compact><li><em>From:</em> Joel Kelso <joel#ee,uwa.edu.au></li></ul>
</UL></LI></UL>
<!--X-Follow-Ups-End-->
<!--X-References-->
<!--X-References-End-->
<!--X-BotPNI-->
<UL>
<LI>Prev by Date:
<STRONG><A HREF="msg01039.html">[MUD-Dev] Re: [off-topic] news!</A></STRONG>
</LI>
<LI>Next by Date:
<STRONG><A HREF="msg01041.html">[MUD-Dev] Re: Admin: Unsubscriptions</A></STRONG>
</LI>
<LI>Prev by thread:
<STRONG><A HREF="msg01061.html">[MUD-Dev] PCCTS->ANTLR</A></STRONG>
</LI>
<LI>Next by thread:
<STRONG><A HREF="msg01046.html">[MUD-Dev] Re: cellular automata as universe models</A></STRONG>
</LI>
<LI>Index(es):
<UL>
<LI><A HREF="index.html#01040"><STRONG>Date</STRONG></A></LI>
<LI><A HREF="thread.html#01040"><STRONG>Thread</STRONG></A></LI>
</UL>
</LI>
</UL>
<!--X-BotPNI-End-->
<!--X-User-Footer-->
<!--X-User-Footer-End-->
<ul><li>Thread context:
<BLOCKQUOTE><UL>
<LI><STRONG>[MUD-Dev] Re: Marian's Tailor vs. Psychopaths</STRONG>, <EM>(continued)</EM>
<ul compact>
<ul compact>
<ul compact>
<LI><strong><A NAME="01089" HREF="msg01089.html">[MUD-Dev] Re: Marian's Tailor vs. Psychopaths</A></strong>,
Adam Wiggins <a href="mailto:adam#angel,com">adam#angel,com</a>, Mon 21 Sep 1998, 23:10 GMT
<UL>
<LI><strong><A NAME="01090" HREF="msg01090.html">[MUD-Dev] Re: Marian's Tailor vs. Psychopaths</A></strong>,
Jo Dillon <a href="mailto:emily#thelonious,new.ox.ac.uk">emily#thelonious,new.ox.ac.uk</a>, Tue 22 Sep 1998, 08:18 GMT
</LI>
</UL>
</LI>
</ul>
</ul>
</ul>
</LI>
<LI><strong><A NAME="01062" HREF="msg01062.html">[MUD-Dev] MOSIX: Multi-computer Operating System for unIX</A></strong>,
J C Lawrence <a href="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</a>, Fri 18 Sep 1998, 19:06 GMT
<LI><strong><A NAME="01061" HREF="msg01061.html">[MUD-Dev] PCCTS->ANTLR</A></strong>,
J C Lawrence <a href="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</a>, Thu 17 Sep 1998, 19:06 GMT
<LI><strong><A NAME="01040" HREF="msg01040.html">[MUD-Dev] cellular automata as universe models</A></strong>,
James Wilson <a href="mailto:jwilson#rochester,rr.com">jwilson#rochester,rr.com</a>, Sun 13 Sep 1998, 23:27 GMT
<UL>
<LI><strong><A NAME="01046" HREF="msg01046.html">[MUD-Dev] Re: cellular automata as universe models</A></strong>,
Joel Kelso <a href="mailto:joel#ee,uwa.edu.au">joel#ee,uwa.edu.au</a>, Tue 15 Sep 1998, 01:14 GMT
<UL>
<LI><strong><A NAME="01047" HREF="msg01047.html">[MUD-Dev] Re: cellular automata as universe models</A></strong>,
James Wilson <a href="mailto:jwilson#rochester,rr.com">jwilson#rochester,rr.com</a>, Tue 15 Sep 1998, 02:01 GMT
</LI>
</UL>
</LI>
</UL>
</LI>
<LI><strong><A NAME="01037" HREF="msg01037.html">[MUD-Dev] [off-topic] news!</A></strong>,
Travis Casey <a href="mailto:efindel#polaris,net">efindel#polaris,net</a>, Sun 13 Sep 1998, 22:27 GMT
<UL>
<LI><strong><A NAME="01038" HREF="msg01038.html">[MUD-Dev] Re: [off-topic] news!</A></strong>,
J C Lawrence <a href="mailto:claw#kanga,nu">claw#kanga,nu</a>, Sun 13 Sep 1998, 22:31 GMT
</LI>
</UL>
</LI>
</UL></BLOCKQUOTE>
</ul>
<hr>
<center>
[ <a href="../">Other Periods</a>
| <a href="../../">Other mailing lists</a>
| <a href="/search.php3">Search</a>
]
</center>
<hr>
</body>
</html>