17.3 复杂性理论

下面要介绍的程序的前身是由Larry O’Brien原创的一些代码，并以由Craig Reynolds于1986年编制的“Boids”程序为基础，当时是为了演示复杂性理论的一个特殊问题，名为“凸显”（Emergence）。

这儿要达到的目标是通过为每种动物都规定少许简单的规则，从而逼真地再现动物的群聚行为。每个动物都能看到看到整个环境以及环境中的其他动物，但它只与一系列附近的“群聚伙伴”打交道。动物的移动基于三个简单的引导行为：

(1) 分隔：避免本地群聚伙伴过于拥挤。

(2) 方向：遵从本地群聚伙伴的普遍方向。

(3) 聚合：朝本地群聚伙伴组的中心移动。

更复杂的模型甚至可以包括障碍物的因素，动物能预知和避免与障碍冲突的能力，所以它们能围绕环境中的固定物体自由活动。除此以外，动物也可能有自己的特殊目标，这也许会造成群体按特定的路径前进。为简化讨论，避免障碍以及目标搜寻的因素并未包括到这里建立的模型中。

尽管计算机本身比较简陋，而且采用的规则也相当简单，但结果看起来是真实的。也就是说，相当逼真的行为从这个简单的模型中“凸显”出来了。

程序以组合到一起的应用程序／程序片的形式提供：

  1. //: FieldOBeasts.java
  2. // Demonstration of complexity theory; simulates
  3. // herding behavior in animals. Adapted from
  4. // a program by Larry O'Brien lobrien@msn.com
  5. import java.awt.*;
  6. import java.awt.event.*;
  7. import java.applet.*;
  8. import java.util.*;
  10. class Beast {
  11.   int
  12.     x, y,            // Screen position
  13.     currentSpeed;    // Pixels per second
  14.   float currentDirection;  // Radians
  15.   Color color;      // Fill color
  16.   FieldOBeasts field; // Where the Beast roams
  17.   static final int GSIZE = 10; // Graphic size
  19.   public Beast(FieldOBeasts f, int x, int y,
  20.       float cD, int cS, Color c) {
  21.     field = f;
  22.     this.x = x;
  23.     this.y = y;
  24.     currentDirection = cD;
  25.     currentSpeed = cS;
  26.     color = c;
  27.   }
  28.   public void step() {
  29.     // You move based on those within your sight:
  30.     Vector seen = field.beastListInSector(this);
  31.     // If you're not out in front
  32.     if(seen.size() > 0) {
  33.       // Gather data on those you see
  34.       int totalSpeed = 0;
  35.       float totalBearing = 0.0f;
  36.       float distanceToNearest = 100000.0f;
  37.       Beast nearestBeast =
  38.         (Beast)seen.elementAt(0);
  39.       Enumeration e = seen.elements();
  40.       while(e.hasMoreElements()) {
  41.         Beast aBeast = (Beast) e.nextElement();
  42.         totalSpeed += aBeast.currentSpeed;
  43.         float bearing =
  44.           aBeast.bearingFromPointAlongAxis(
  45.             x, y, currentDirection);
  46.         totalBearing += bearing;
  47.         float distanceToBeast =
  48.           aBeast.distanceFromPoint(x, y);
  49.         if(distanceToBeast < distanceToNearest) {
  50.           nearestBeast = aBeast;
  51.           distanceToNearest = distanceToBeast;
  52.         }
  53.       }
  54.       // Rule 1: Match average speed of those
  55.       // in the list:
  56.       currentSpeed = totalSpeed / seen.size();
  57.       // Rule 2: Move towards the perceived
  58.       // center of gravity of the herd:
  59.       currentDirection =
  60.         totalBearing / seen.size();
  61.       // Rule 3: Maintain a minimum distance
  62.       // from those around you:
  63.       if(distanceToNearest <=
  64.          field.minimumDistance) {
  65.         currentDirection =
  66.           nearestBeast.currentDirection;
  67.         currentSpeed = nearestBeast.currentSpeed;
  68.         if(currentSpeed > field.maxSpeed) {
  69.           currentSpeed = field.maxSpeed;
  70.         }
  71.       }
  72.     }
  73.     else {  // You are in front, so slow down
  74.       currentSpeed =
  75.         (int)(currentSpeed * field.decayRate);
  76.     }
  77.     // Make the beast move:
  78.     x += (int)(Math.cos(currentDirection)
  79.                * currentSpeed);
  80.     y += (int)(Math.sin(currentDirection)
  81.                * currentSpeed);
  82.     x %= field.xExtent;
  83.     y %= field.yExtent;
  84.     if(x < 0)
  85.       x += field.xExtent;
  86.     if(y < 0)
  87.       y += field.yExtent;
  88.   }
  89.   public float bearingFromPointAlongAxis (
  90.       int originX, int originY, float axis) {
  91.     // Returns bearing angle of the current Beast
  92.     // in the world coordiante system
  93.     try {
  94.       double bearingInRadians =
  95.         Math.atan(
  96.           (this.y - originY) /
  97.           (this.x - originX));
  98.       // Inverse tan has two solutions, so you
  99.       // have to correct for other quarters:
  100.       if(x < originX) {  
  101.         if(y < originY) {
  102.           bearingInRadians += - (float)Math.PI;
  103.         }
  104.         else {
  105.           bearingInRadians =
  106.             (float)Math.PI - bearingInRadians;
  107.         }
  108.       }
  109.       // Just subtract the axis (in radians):
  110.       return (float) (axis - bearingInRadians);
  111.     } catch(ArithmeticException aE) {
  112.       // Divide by 0 error possible on this
  113.       if(x > originX) {
  114.           return 0;
  115.       }
  116.       else
  117.         return (float) Math.PI;
  118.     }
  119.   }
  120.   public float distanceFromPoint(int x1, int y1){
  121.     return (float) Math.sqrt(
  122.       Math.pow(x1 - x, 2) +
  123.       Math.pow(y1 - y, 2));
  124.   }
  125.   public Point position() {
  126.     return new Point(x, y);
  127.   }
  128.   // Beasts know how to draw themselves:
  129.   public void draw(Graphics g) {
  130.     g.setColor(color);
  131.     int directionInDegrees = (int)(
  132.       (currentDirection * 360) / (2 * Math.PI));
  133.     int startAngle = directionInDegrees -
  134.       FieldOBeasts.halfFieldOfView;
  135.     int endAngle = 90;
  136.     g.fillArc(x, y, GSIZE, GSIZE,
  137.       startAngle, endAngle);
  138.   }
  139. }
  141. public class FieldOBeasts extends Applet
  142.     implements Runnable {
  143.   private Vector beasts;
  144.   static float
  145.     fieldOfView =
  146.       (float) (Math.PI / 4), // In radians
  147.     // Deceleration % per second:
  148.     decayRate = 1.0f,
  149.     minimumDistance = 10f; // In pixels
  150.   static int
  151.     halfFieldOfView = (int)(
  152.       (fieldOfView * 360) / (2 * Math.PI)),
  153.     xExtent = 0,
  154.     yExtent = 0,
  155.     numBeasts = 50,
  156.     maxSpeed = 20; // Pixels/second
  157.   boolean uniqueColors = true;
  158.   Thread thisThread;
  159.   int delay = 25;
  160.   public void init() {
  161.     if (xExtent == 0 && yExtent == 0) {
  162.       xExtent = Integer.parseInt(
  163.         getParameter("xExtent"));
  164.       yExtent = Integer.parseInt(
  165.         getParameter("yExtent"));
  166.     }
  167.     beasts =
  168.       makeBeastVector(numBeasts, uniqueColors);
  169.     // Now start the beasts a-rovin':
  170.     thisThread = new Thread(this);
  171.     thisThread.start();
  172.   }
  173.   public void run() {
  174.     while(true) {
  175.       for(int i = 0; i < beasts.size(); i++){
  176.         Beast b = (Beast) beasts.elementAt(i);
  177.         b.step();
  178.       }
  179.       try {
  180.         thisThread.sleep(delay);
  181.       } catch(InterruptedException ex){}
  182.       repaint(); // Otherwise it won't update
  183.     }
  184.   }
  185.   Vector makeBeastVector(
  186.       int quantity, boolean uniqueColors) {
  187.     Vector newBeasts = new Vector();
  188.     Random generator = new Random();
  189.     // Used only if uniqueColors is on:
  190.     double cubeRootOfBeastNumber =
  191.       Math.pow((double)numBeasts, 1.0 / 3.0);
  192.     float colorCubeStepSize =
  193.       (float) (1.0 / cubeRootOfBeastNumber);
  194.     float r = 0.0f;
  195.     float g = 0.0f;
  196.     float b = 0.0f;
  197.     for(int i = 0; i < quantity; i++) {
  198.       int x =
  199.         (int) (generator.nextFloat() * xExtent);
  200.       if(x > xExtent - Beast.GSIZE)
  201.         x -= Beast.GSIZE;
  202.       int y =
  203.         (int) (generator.nextFloat() * yExtent);
  204.       if(y > yExtent - Beast.GSIZE)
  205.         y -= Beast.GSIZE;
  206.       float direction = (float)(
  207.         generator.nextFloat() * 2 * Math.PI);
  208.       int speed = (int)(
  209.         generator.nextFloat() * (float)maxSpeed);
  210.       if(uniqueColors) {
  211.         r += colorCubeStepSize;
  212.         if(r > 1.0) {
  213.           r -= 1.0f;
  214.           g += colorCubeStepSize;
  215.           if( g > 1.0) {
  216.             g -= 1.0f;
  217.             b += colorCubeStepSize;
  218.             if(b > 1.0)
  219.               b -= 1.0f;
  220.           }
  221.         }
  222.       }
  223.       newBeasts.addElement(
  224.         new Beast(this, x, y, direction, speed,
  225.           new Color(r,g,b)));
  226.     }
  227.     return newBeasts;
  228.   }
  229.   public Vector beastListInSector(Beast viewer) {
  230.     Vector output = new Vector();
  231.     Enumeration e = beasts.elements();
  232.     Beast aBeast = (Beast)beasts.elementAt(0);
  233.     int counter = 0;
  234.     while(e.hasMoreElements()) {
  235.       aBeast = (Beast) e.nextElement();
  236.       if(aBeast != viewer) {
  237.         Point p = aBeast.position();
  238.         Point v = viewer.position();
  239.         float bearing =
  240.           aBeast.bearingFromPointAlongAxis(
  241.             v.x, v.y, viewer.currentDirection);
  242.         if(Math.abs(bearing) < fieldOfView / 2)
  243.          output.addElement(aBeast);
  244.       }
  245.     }
  246.     return output;
  247.   }
  248.   public void paint(Graphics g)  {
  249.     Enumeration e = beasts.elements();
  250.     while(e.hasMoreElements()) {
  251.       ((Beast)e.nextElement()).draw(g);
  252.     }
  253.   }
  254.   public static void main(String[] args)   {
  255.     FieldOBeasts field = new FieldOBeasts();
  256.     field.xExtent = 640;
  257.     field.yExtent = 480;
  258.     Frame frame = new Frame("Field 'O Beasts");
  259.     // Optionally use a command-line argument
  260.     // for the sleep time:
  261.     if(args.length >= 1)
  262.       field.delay = Integer.parseInt(args[0]);
  263.     frame.addWindowListener(
  264.       new WindowAdapter() {
  265.         public void windowClosing(WindowEvent e) {
  266.           System.exit(0);
  267.         }
  268.       });
  269.     frame.add(field, BorderLayout.CENTER);
  270.     frame.setSize(640,480);
  271.     field.init();
  272.     field.start();
  273.     frame.setVisible(true);
  274.   }
  275. } ///:~

尽管这并非对Craig Reynold的“Boids”例子中的行为完美重现，但它却展现出了自己独有的迷人之外。通过对数字进行调整，即可进行全面的修改。至于与这种群聚行为有关的更多的情况，大家可以访问Craig Reynold的主页——在那个地方，甚至还提供了Boids一个公开的3D展示版本：

http://www.hmt.com/cwr/boids.html

为了将这个程序作为一个程序片运行，请在HTML文件中设置下述程序片标志：

  1. <applet
  2. code=FieldOBeasts
  3. width=640
  4. height=480>
  5. <param name=xExtent value = "640">
  6. <param name=yExtent value = "480">
  7. </applet>