复杂性理论

复杂性理论2007-05-29 yycnet.yeah.net yyc译下面要介绍的程序的前身是由Larry O"Brien原创的一些代码，并以由Craig Reynolds于1986年编制的“Boids”程序为基础，当时是为了演示复杂性理论的一个特殊问题，名为“凸显”（Emergence）。
这儿要达到的目标是通过为每种动物都规定少许简单的规则，从而逼真地再现动物的群聚行为。每个动物都能看到看到整个环境以及环境中的其他动物，但它只与一系列附近的“群聚伙伴”打交道。动物的移动基于三个简单的引导行为：
（1）分隔：避免本地群聚伙伴过于拥挤。
（2）方向：遵从本地群聚伙伴的普遍方向。
（3）聚合：朝本地群聚伙伴组的中心移动。
更复杂的模型甚至可以包括障碍物的因素，动物能预知和避免与障碍冲突的能力，所以它们能围绕环境中的固定物体自由活动。除此以外，动物也可能有自己的特殊目标，这也许会造成群体按特定的路径前进。为简化讨论，避免障碍以及目标搜寻的因素并未包括到这里建立的模型中。
尽管计算机本身比较简陋，而且采用的规则也相当简单，但结果看起来是真实的。也就是说，相当逼真的行为从这个简单的模型中“凸显”出来了。
程序以合成到一起的应用程序／程序片的形式提供：

//: FieldOBeasts.java// Demonstration of complexity theory; simulates // herding behavior in animals. Adapted from// a program by Larry O"Brien lobrien@msn.comimport java.awt.*;import java.awt.event.*;import java.applet.*;import java.util.*;class Beast {intx, y,// Screen positioncurrentSpeed;// Pixels per secondfloat currentDirection;// RadiansColor color;// Fill colorFieldOBeasts field; // Where the Beast roamsstatic final int GSIZE = 10; // Graphic sizepublic Beast（FieldOBeasts f, int x, int y, float cD, int cS, Color c） {field = f;this.x = x;this.y = y;currentDirection = cD;currentSpeed = cS;color = c;}public void step（） {// You move based on those within your sight:Vector seen = field.beastListInSector（this）;// If you"re not out in frontif（seen.size（） > 0） {// Gather data on those you seeint totalSpeed = 0;float totalBearing = 0.0f;float distanceToNearest = 100000.0f;Beast nearestBeast = （Beast）seen.elementAt（0）;Enumeration e = seen.elements（）;while（e.hasMoreElements（）） {Beast aBeast = （Beast） e.nextElement（）;totalSpeed += aBeast.currentSpeed;float bearing = aBeast.bearingFromPointAlongAxis（x, y, currentDirection）;totalBearing += bearing;float distanceToBeast = aBeast.distanceFromPoint（x, y）;if（distanceToBeast < distanceToNearest） {nearestBeast = aBeast;distanceToNearest = distanceToBeast;}}// Rule 1: Match average speed of those // in the list:currentSpeed = totalSpeed / seen.size（）;// Rule 2: Move towards the perceived// center of gravity of the herd:currentDirection = totalBearing / seen.size（）;// Rule 3: Maintain a minimum distance // from those around you:if（distanceToNearest <=field.minimumDistance） {currentDirection = nearestBeast.currentDirection;currentSpeed = nearestBeast.currentSpeed;if（currentSpeed > field.maxSpeed） {currentSpeed = field.maxSpeed;}}} else {// You are in front, so slow downcurrentSpeed = （int）（currentSpeed * field.decayRate）;}// Make the beast move:x += （int）（Math.cos（currentDirection）* currentSpeed）;y += （int）（Math.sin（currentDirection） * currentSpeed）;x %= field.xExtent;y %= field.yExtent;if（x < 0）x += field.xExtent;if（y < 0）y += field.yExtent;}public float bearingFromPointAlongAxis （int originX, int originY, float axis） {// Returns bearing angle of the current Beast// in the world coordiante systemtry {double bearingInRadians = Math.atan（（this.y - originY） / （this.x - originX））;// Inverse tan has two solutions, so you // have to correct for other quarters:if（x < originX） {if（y < originY） {bearingInRadians += - （float）Math.PI;} else {bearingInRadians = （float）Math.PI - bearingInRadians;}}// Just subtract the axis （in radians）:return （float） （axis - bearingInRadians）;} catch（ArithmeticException aE） {// Divide by 0 error possible on thisif（x > originX） {return 0;} elsereturn （float） Math.PI;}}public float distanceFromPoint（int x1, int y1）{return （float） Math.sqrt（Math.pow（x1 - x, 2） + Math.pow（y1 - y, 2））;}public Point position（） { return new Point（x, y）;}// Beasts know how to draw themselves:public void draw（Graphics g） {g.setColor（color）;int directionInDegrees = （int）（（currentDirection * 360） / （2 * Math.PI））;int startAngle = directionInDegrees - FieldOBeasts.halfFieldOfView;int endAngle = 90;g.fillArc（x, y, GSIZE, GSIZE, startAngle, endAngle）;}}public class FieldOBeasts extends Applet implements Runnable {private Vector beasts;static float fieldOfView = （float） （Math.PI / 4）, // In radians// Deceleration % per second:decayRate = 1.0f, minimumDistance = 10f; // In pixelsstatic inthalfFieldOfView = （int）（（fieldOfView * 360） / （2 * Math.PI））,xExtent = 0,yExtent = 0,numBeasts = 50,maxSpeed = 20; // Pixels/secondboolean uniqueColors = true;Thread thisThread;int delay = 25;public void init（） {if （xExtent == 0 && yExtent == 0） {xExtent = Integer.parseInt（getParameter（"xExtent"））;yExtent = Integer.parseInt（getParameter（"yExtent"））;}beasts = makeBeastVector（numBeasts, uniqueColors）;// Now start the beasts a-rovin":thisThread = new Thread（this）;thisThread.start（）;}public void run（） {while（true） {for（int i = 0; i < beasts.size（）; i++）{Beast b = （Beast） beasts.elementAt（i）;b.step（）;}try {thisThread.sleep（delay）;} catch（InterruptedException ex）{}repaint（）; // Otherwise it won"t update}}Vector makeBeastVector（int quantity, boolean uniqueColors） {Vector newBeasts = new Vector（）;Random generator = new Random（）;// Used only if uniqueColors is on:double cubeRootOfBeastNumber = Math.pow（（double）numBeasts, 1.0 / 3.0）;float colorCubeStepSize = （float） （1.0 / cubeRootOfBeastNumber）;float r = 0.0f;float g = 0.0f;float b = 0.0f;for（int i = 0; i < quantity; i++） {int x = （int） （generator.nextFloat（） * xExtent）;if（x > xExtent - Beast.GSIZE） x -= Beast.GSIZE;int y = （int） （generator.nextFloat（） * yExtent）;if（y > yExtent - Beast.GSIZE） y -= Beast.GSIZE;float direction = （float）（generator.nextFloat（） * 2 * Math.PI）;int speed = （int）（generator.nextFloat（） * （float）maxSpeed）;if（uniqueColors） {r += colorCubeStepSize;if（r > 1.0） {r -= 1.0f;g += colorCubeStepSize;if（ g > 1.0） {g -= 1.0f;b += colorCubeStepSize;if（b > 1.0） b -= 1.0f;}}}newBeasts.addElement（new Beast（this, x, y, direction, speed, new Color（r,g,b）））;}return newBeasts;}public Vector beastListInSector（Beast viewer） {Vector output = new Vector（）;Enumeration e = beasts.elements（）;Beast aBeast = （Beast）beasts.elementAt（0）;int counter = 0;while（e.hasMoreElements（）） {aBeast = （Beast） e.nextElement（）;if（aBeast ！= viewer） {Point p = aBeast.position（）;Point v = viewer.position（）;float bearing = aBeast.bearingFromPointAlongAxis（v.x, v.y, viewer.currentDirection）;if（Math.abs（bearing） < fieldOfView / 2） output.addElement（aBeast）;}}return output;}public void paint（Graphics g）{Enumeration e = beasts.elements（）;while（e.hasMoreElements（）） {（（Beast）e.nextElement（））.draw（g）;}}public static void main（String[] args） {FieldOBeasts field = new FieldOBeasts（）;field.xExtent = 640;field.yExtent = 480;Frame frame = new Frame（"Field "O Beasts"）;// Optionally use a command-line argument// for the sleep time:if（args.length >= 1）field.delay = Integer.parseInt（args[0]）;frame.addWindowListener（new WindowAdapter（） {public void windowClosing（WindowEvent e） {System.exit（0）;}}）;frame.add（field, BorderLayout.CENTER）;frame.setSize（640,480）;field.init（）;field.start（）;frame.setVisible（true）;}} ///:~

尽管这并非对Craig Reynold的“Boids”例子中的行为完美重现，但它却展现出了自己独有的迷人之外。通过对数字进行调整，即可进行全面的修改。至于与这种群聚行为有关的更多的情况，大家可以访问Craig Reynold的主页——在那个地方，甚至还提供了Boids一个公开的3D展示版本：
http://www.hmt.com/cwr/boids.html
为了将这个程序作为一个程序片运行，请在HTML文件中设置下述程序片标志：

<appletcode=FieldOBeastswidth=640height=480><param name=xExtent value = "640"><param name=yExtent value = "480"></applet>