17.3 复杂性理论
17.3 复杂性理论
下面要介绍的程序的前身是由 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.com
import java.awt.*;
import java.awt.event.*;
import java.applet.*;
import java.util.*;
class Beast {
int
x, y, // Screen position
currentSpeed; // Pixels per second
float currentDirection; // Radians
Color color; // Fill color
FieldOBeasts field; // Where the Beast roams
static final int GSIZE = 10; // Graphic size
public 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 front
if(seen.size() > 0) {
// Gather data on those you see
int 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 down
currentSpeed =
(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 system
try {
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 this
if(x > originX) {
return 0;
}
else
return (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 pixels
static int
halfFieldOfView = (int)(
(fieldOfView * 360) / (2 * Math.PI)),
xExtent = 0,
yExtent = 0,
numBeasts = 50,
maxSpeed = 20; // Pixels/second
boolean 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 文件中设置下述程序片标志：
<applet
code=FieldOBeasts
width=640
height=480>
<param name=xExtent value = "640">
<param name=yExtent value = "480">
</applet>
``` java