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
上一页
下一页