/* * SimEvol shows "bugs" adapting to a harsh environment. * Copyright (C) 1998 Scott Maxwell * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License * as published by the Free Software Foundation; either version 2 * of the License, or (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. * * You can reach me at s-max@pacbell.net. */ /* * SimEvol -- Simulated evolution. By Scott Maxwell. * // Based on one of A.K. Dewdney's "Computer Recreations" * \\// columns in _Scientific American_. [date?] * XX * * Bugs evolve to maximize their ability to gather food in an abstract * environment. They begin as "jitterbugs," spinning 'round and 'round * and not getting much to eat. After one or more boom-and-bust * cycles, however, they evolve to travel in straight lines and turn * comparatively rarely. This way they're always travelling to new * regions of the screen, making it more likely that they'll encounter * the sparsely distributed food (the purple stuff -- bacteria -- is * the food). * * The green bugs are old enough to reproduce, the red bugs are strong * enough to reproduce, and the yellow bugs are both. (Bugs will only * flash yellow and then give birth immediately.) Grey bugs, by the * way, are neither old enough nor strong enough to reproduce. */ // Stuff to do: // (*) A bug: food collects on the right and bottom edges. // (*) Display current population size somewhere. // (*) Show the average values of all 6 genes. // (*) Sanity checking (e.g., what happens if the graph is too small // to contain the text?). // (*) Figure out why I have to sleep() the thread in order to get // changes to show! // (*) Speed it up. It would be nice to start showing results of // selection pressure within 1 minute on a typical machine (whatever // "typical" means). Eliminating the sleep() might help. // (*) It might be neat to have a "split screen"; one half would be // food-rich and one half would be normal. (Bugs wouldn't be allowed // to cross over.) This would show bugs evolving to move straight in // the normal half, where there was selection pressure, but remaining // "jitterbugs" in the food-rich half, where selection pressure was // absent. Possibly optional. // (*) Might be interesting if it were more expensive to be better. // Bring in everything I'll need, and then some! import java.awt.*; import java.applet.*; import java.awt.image.*; import java.awt.event.*; import java.util.*; // Applet-wide settings. Soon to be made modifiable using applet // parameters. class SimEvolSettings { private static Applet applet = null; // Need this for getParameter(). // (Re)set all settings to their defaults as supplied by the // applet's context or (in the future) on the command line. Can't // do this before init(), damn it. public static void setToDefaults(Applet theApplet) { applet = theApplet; width = stoi("Width", width); height = stoi("Height", height); foodEnergy = stoi("FoodEnergy", foodEnergy); initialBugEnergy = stoi("InitialBugEnergy", initialBugEnergy); strongEnough = stoi("StrongEnough", strongEnough); oldEnough = stoi("OldEnough", oldEnough); initialPopulationSize = stoi("InitialPopSize", initialPopulationSize); } // Utility mfn to parse and return a named parameter. Currently // does not attempt to get values from the command line. private static int stoi(String paramName, int dflt) { if (applet == null) // "Never happens." return 0; // Should throw an exception; too lazy just now. try { final String s = applet.getParameter(paramName); if (s != null) // Parameter set; get value and use it. return new Integer(s).intValue(); // Else parameter not set, so drop through and return // dflt. } catch (NullPointerException e) { // Running standalone, not as an applet // (getParameter() threw this). Do nothing here; // instead, drop through and return dflt. } return dflt; } // Width and height of the bugs' world (in pixels). private static int width = 256; private static int height = 256 + 50; public static int getWidth() { return width; } public static int getHeight() { return height; } public static void setWidth(int w) { width = w; } public static void setHeight(int h) { height = h; } // Number of "energy points" a bug gets for eating food. private static int foodEnergy = 40; public static int getFoodEnergy() { return foodEnergy; } public static void setFoodEnergy(int e) { foodEnergy = e; } // How much energy each bug in the initial population gets. private static int initialBugEnergy = 100; public static int getInitialBugEnergy() { return initialBugEnergy; } public static void setInitialBugEnergy(int e) { initialBugEnergy = e; } // How strong a bug must be (in food energy units) to reproduce, // and how old (in clock ticks). A bug may reproduce only if both // conditions are met. private static int strongEnough = 1000; private static int oldEnough = 800; public static int getStrongEnough() { return strongEnough; } public static int getOldEnough() { return oldEnough; } public static void setStrongEnough(int x) { strongEnough = x; } public static void setOldEnough(int x) { oldEnough = x; } // Number of bugs in the initial population. private static int initialPopulationSize = 10; public static int getInitialPopulationSize() { return initialPopulationSize; } public static void setInitialPopulationSize(int sz) { initialPopulationSize = sz; } } // Here's something I hate about Java's obsessive object-orientation. // Like a plain function would be so bad. class IntRand { // Return a random int in the range [0, max). public static int rand(int max) { return (int) (Math.random() * max); } } // A simple graph that scrolls to the left each time a new data point // is added. It also displays a textual percentage. class ScrollingGraph extends Canvas { final Color bgColor = Color.darkGray; final Color fgColor = Color.lightGray; final String label; // What to put before the percentage. final int width; // Graph width. final int height; // Graph height. final int scrollStep; // Number of pixels to scroll per data point. int last = -1; // Last y-value plotted. double lastPct = 0.0; // Last percentage. Image img; // Offscreen buffer we draw into. Graphics gImg; // The GC from img. FontMetrics fm; // Font metrics for the font used in img/gImg. // Create img and gImg if they don't already exist. If we can't // create them for any reason, return false, else return true. private boolean makeImage() { if (img != null) return true; img = createImage(width, height); if (img == null) return false; gImg = img.getGraphics(); if (gImg == null) { img = null; return false; } gImg.setFont(new Font("SansSerif", Font.BOLD, 12)); fm = gImg.getFontMetrics(); if (fm == null) { img = null; gImg = null; return false; } reset(); return true; } // XOR-draw the text saying what percentage we're at now. private void drawText(double pct) { // pct is a percentage in the range [0.0, 1.0]. Scale // this to [0.0, 100.0] and get the part before the // decimal point and up to two digits after. Then display // this, preceded by the label we were given in the ctor. // Stuff like this really makes me miss sprintf()! final int before = (int) (pct * 100); final int after = (int) (pct * 100 * 100) % 100; final String lbl = label + ": " + before + "." + after + " %"; try { final int sw = fm.stringWidth(lbl); gImg.setXORMode(bgColor); gImg.drawString(lbl, width / 2 - sw / 2, height / 2 + fm.getHeight() / 2); gImg.setPaintMode(); } catch (java.lang.NullPointerException e) { System.out.println("Not ready yet in drawText()."); } } // Ctor. Takes width and height, plus the amount we should scroll // horizontally on each update. public ScrollingGraph(String lbl, int w, int h, int ss) { label = lbl; width = w; height = h; scrollStep = ss; setSize(w, h); } // Start over. public void reset() { last = -1; lastPct = 0.0; if (!makeImage()) return; // Blank the graph. gImg.setColor(bgColor); gImg.fillRect(0, 0, width, height); drawText(lastPct); } // Add a new data point; this is a decimal percentage in the range // [0.0, 1.0]. public void addDataPoint(double percent) { if (percent > 1.0) percent = 0.0; else if (percent < 0.0) percent = 0.0; if (!makeImage()) return; final int curr = height - (int) (0.5 + height * percent); if (last == -1) // First time. last = curr; else drawText(lastPct); // Undraw old text (XOR). // Blit everything scrollStep pixels to the left. gImg.copyArea(scrollStep, 0, width - scrollStep, height, -scrollStep, 0); // Blank the newly vacated area. gImg.setColor(bgColor); gImg.fillRect(width - scrollStep, 0, width, height); // Draw the new segment representing the point. gImg.setColor(fgColor); // gImg.drawLine(width - scrollStep, last, width - 1, curr); gImg.fillRect(width - scrollStep, curr, scrollStep, height); drawText(percent); // Draw new text (XOR). // Show the result. repaint(); last = curr; lastPct = percent; } // AWT update callback. public void update(Graphics g) { paint(g); } // AWT paint callback. public void paint(Graphics g) { if (makeImage()) g.drawImage(img, 0, 0, this); } } // Ugh! A bug! class Bug { private final int X_CHANGE [] = { 0, 2, 2, 0, -2, -2 }; private final int Y_CHANGE [] = { -2, -1, 1, 2, 1, -1 }; // A bug is a square with this dimension. private final int SIZE = 2; private int energy = 0; // My energy level; when <= 0, I'm dead! private int x = 0; // My x-location. private int y = 0; // My y-location. private int w = 0; // Width of the world (in pixels). private int h = 0; // Height of the world (in pixels). private int age = 0; // Number of clock-ticks I've been alive. private int dir = 0; // My current direction; I turn relative to it. // My genome and a table, built from gene[] by setProbs(), that // makes it easier to decide how I'll move. private int gene [] = new int [6]; private double probs [] = new double [6]; private final Graphics g; // The GC in which I render myself. // Various bug colors. Make these settings? private final static Color strongBugColor = Color.red; private final static Color weakBugColor = Color.lightGray; private final static Color oldBugColor = Color.green; private final static Color strongAndOldBugColor = Color.yellow; // Colors for non-dead bugs -- order matters! See bugColor(). final static Color colorTbl [] = { weakBugColor, strongBugColor, oldBugColor, strongAndOldBugColor }; // Get the average value of probs[0] for all bugs in the Vector; // this is the average probability that a bug will go straight on // any given turn. This can't be set. static public double getAvgStraightness(Vector bugs) { final long n = bugs.size(); if (n == 0) return 0.0; double sum = 0.0; for (int i = 0; i < n; ++i) sum += ((Bug) (bugs.elementAt(i))).probs[0]; return sum / n; } // Reveal my energy level and my age to anyone who's interested. public int getEnergy() { return energy; } public int getAge() { return age; } // The one and only ctor: tell the bug where to display itself and // what its boundaries are. It would be interesting to set up two // playfields (maybe just by physically separating the bugs within // one playfield) and make one playfield much richer in food than // the other. The bugs in one half would evolve to move in // straight lines (or perish); in the other half, they wouldn't. public Bug(Graphics g_, int w_, int h_) { g = g_; w = w_; h = h_; age = 0; // If I'm being created from breed(), these will change // shortly. energy = SimEvolSettings.getInitialBugEnergy(); x = IntRand.rand(w - SIZE); y = IntRand.rand(h - SIZE); // Initial direction and genome. dir = IntRand.rand(6); for (int i = 0; i < 6; ++i) gene[i] = IntRand.rand(5) % 2; setProbs(); } // Meiotically (and asexually) breed two daughters. One // effectively replaces me in place (by changing my genome); the // other is really new and is returned to the caller. Both are // based on the parent, though, except for being changed by // mutate() and sharing the mother's energy. public Bug breed() { // Create a new daughter in the same world-location as me, // with a random direction, and split my energy between // myself and the daughter. Bug b; do { b = new Bug(g, w, h); } while (b.dir == dir); b.energy = energy /= 2; b.x = x; b.y = y; // Copy genome into first daughter, with a random change. for (int i = 0; i < 6; ++i) b.gene[i] = gene[i]; b.mutate(); // I become my own other daughter (replacing myself in // place). mutate(); age = 0; return b; } // Build probs[] from gene[]; this must be done whenever any // element of gene[] has changed. We compute the sum of all // 2^gene[i], then figure out the "share" each gene contributes to // that sum. That share then becomes the relative probability // that we'll turn in that offset from the current direction. A // bug that moves in a straight line has gene[0] contributing the // most to its probabilities, since that means that a turn in // direction 0 (== no turn) is the most likely. Also see move(). // It might be faster to scale this into the range [0, 10000] and // then directly index into that table in move(). private void setProbs() { double pow2 [] = new double [6]; double denom = 0.0; // Sum the probabilities. for (int i = 0; i < 6; i++) denom += (pow2[i] = Math.pow(2.0, gene[i])); // Avoid division by zero (I think this can't happen). if (denom == 0.0) denom = 0.000001; // Map each genome's share into [0.0, 1.0]. probs[0] = pow2[0] / denom; for (int i = 1; i < 5; ++i) { double temp = pow2[i] / denom; // Again, avoid division by zero. if (temp == 0.0) temp = 0.000001; probs[i] = probs[i - 1] + temp; } probs[5] = 1.0; } // This is a bug's "timeslice." It might be interesting to // rewrite this code to use true Java threads, rather than this // approach, which amounts to cooperative multitasking. Return // false if I die, true otherwise. public boolean tick(SimEvolCanvas canvas) { ++age; hide(canvas); move(canvas); --energy; if (energy > 0) show(); return (energy > 0); } // Make a small change to a single site in my genome. Maybe it // would be interesting to make no mutation a possibility -- say, // half of the time you don't mutate at all. How much of an // effect would this have on the rate of evolution? I could // probably arrange that with settings (say, by allowing the user // to specify three integer weights for each of decrement-by-one, // no-change, and increment-by-one). private void mutate() { final int site = IntRand.rand(6); gene[site] += (Math.random() < 0.5) ? -1 : 1; setProbs(); } // Figure out what color I should show() myself in. This makes no // sense if energy <= 0, so no promises are made about the return // value in that case. private Color bugColor() { return colorTbl[ ((energy >= SimEvolSettings.getStrongEnough()) ? 1 : 0) + ((age >= SimEvolSettings.getOldEnough()) ? 2 : 0) ]; } // Hide myself. If I live, I'll be show()n again. private void hide(SimEvolCanvas canvas) { g.setColor(canvas.getWorldBackground()); g.fillRect(x, y, SIZE, SIZE); } // Show myself. private void show() { g.setColor(bugColor()); g.fillRect(x, y, SIZE, SIZE); } // Turn (or not), move, and eat any food at the new location. private void move(SimEvolCanvas canvas) { // Randomly select a new direction and turn in that // direction. final double p = Math.random(); for (int i = 0; i < 6; ++i) if (p < probs[i]) { dir = (dir + i) % 6; break; } // Update my location based on my new direction. x += X_CHANGE[dir]; y += Y_CHANGE[dir]; // Handle "border crossings." The C version did this and // the move itself with arrays because that was faster; I // don't know whether it would be faster in Java (since // Java must check array accesses). Should try it. if (x < 0) x = w - SIZE - 1; else if ((x + SIZE) >= w) x = 0; if (y < 0) y = h - SIZE - 1; else if ((y + SIZE) >= h) y = 0; // Eat! Eat! You grow skinny! final int xlim = x + SIZE; final int ylim = y + SIZE; for (int xx = x; xx < xlim; ++xx) for (int yy = y; yy < ylim; ++yy) if (canvas.eatFoodAt(xx, yy)) energy += SimEvolSettings.getFoodEnergy(); } } // The Canvas in which the simulation runs. This actually controls // the simulation to some extent, which is a correctable design // mistake (it was just convenient for the first hack). class SimEvolCanvas extends Canvas implements Runnable { private final int nPixels; // Eventually these should be settable without recompiling (?). private final int InitialFood; private final int FoodPerTurn; private static Color bgColor = Color.black; private static Color foodColor = Color.magenta; // A Vector of BitSets: food[x][y] remembers whether there is a // food bacterium at (x, y). We do this rather than reading the // Canvas directly because it's much faster: the best readPixel() // I could come up with takes 0.2 sec on my machine! The // Vector/BitSet combination may be slow, but it's not *that* // slow. BTW, it may be faster to use a single BitSet and index // into it as x * y or something. private BitSet food = new BitSet(); // A Vector of Bugs. private Vector bugs = new Vector(); // The Thread that runs me (null when I'm stopped), and a lock // object for it. private Thread kickMe = null; private final Object kickMeLock = new Object(); // The Image that fills me. private Image img = null; private final int width; private final int height; // The GC for img. private Graphics gImg = null; // Graph we periodically update. private final ScrollingGraph graph; // The enclosing applet. private final Applet applet; // Ctor. public SimEvolCanvas(Applet app, int w, int h, ScrollingGraph g) { applet = app; width = w; height = h; nPixels = w * h; graph = g; InitialFood = nPixels / 100; FoodPerTurn = Math.min(1, nPixels / (256 * 256)); setSize(w, h); } // AWT update callback. public void update(Graphics g) { paint(g); } // AWT paint callback. All the drawing takes place in the // offscreen Image img, which I just blit onto myself. static boolean snapped = false; public void paint(Graphics g) { // On the first paint() (only), make the frame fit around // me if there is one. if (!snapped) { snapped = true; if (SimEvolFrame.instance != null) { final Insets insets = SimEvolFrame.instance.getInsets(); SimEvolFrame.instance.setSize( insets.left + SimEvolSettings.getWidth() + insets.right, insets.top + SimEvolSettings.getHeight() + insets.bottom ); } } if (img != null) // Not initialized yet? May be impossible. g.drawImage(img, 0, 0, this); } // Thread entry point. This does the real work. public void run() { // Create the offscreen image and get a graphics context // for it. I can't do this setup within init(). gImg = null; while (true) { if (img == null) img = createImage(width, height); if (img != null) { gImg = img.getGraphics(); if (gImg != null) break; } // Couldn't get one or both; let any other threads run // briefly and then try again. synchronized (kickMeLock) { if (kickMe == null) return; try { kickMe.sleep(100); } catch(InterruptedException e) { } } } // OK, the real work starts here. while (true) { int tm = 0; // Simulation time (in simulated clock ticks). // Blank everything and set up for an initial run. reset(); sowSeed(); createInitialPopulation(); // Until everyone dies (if ever), advance the // simulation by one tick. while (bugs.size() != 0) { // Periodically issue a status update. This will // be nicer once I've added more GUI controls. if ((tm % 100) == 0) { double avgStraightness = Bug.getAvgStraightness(bugs); graph.addDataPoint(avgStraightness); // System.out.println(avgStraightness); Frame f = SimEvolFrame.instance; if (f != null) { String title = "SimEvol " + tm + " " + bugs.size(); f.setTitle(title); } else { final long straight = Math.round(avgStraightness * 10000); String status = "# Bugs: " + bugs.size() + " Straightness: " + (straight / 100.00) + "%" + " Clock: " + tm; applet.showStatus(status); } if (false) // Spit out some debugging/tracing info. { System.out.print(tm + " " + bugs.size() + ":"); for (int i = 0; i < bugs.size(); ++i) { Bug bug = (Bug) (bugs.elementAt(i)); System.out.print(" (" + bug.getEnergy() + " " + bug.getAge() + ")"); } System.out.println(""); } } ++tm; // Drop some food in, move everyone, let 'em // breed, and update the display. for (int i = 0; i < FoodPerTurn; ++i) randFood(); moveBugs(); breedBugs(); repaint(); synchronized (kickMeLock) { if (kickMe == null) return; try { // Flush queued graphics events. kickMe.sleep(5); // Limits me to 200/sec! // getToolkit().sync(); // Doesn't seem to help. } catch(InterruptedException e) { } } } } } // Start running. public void start() { synchronized (kickMeLock) { if (kickMe == null) kickMe = new Thread(this); kickMe.start(); } } // Stop running. public void stop() { synchronized (kickMeLock) { if (kickMe != null) { kickMe.stop(); kickMe = null; } } } // If there's food at (x, y), erase it and return true. Else // return false. public boolean eatFoodAt(int x, int y) { if (!food.get(x * height + y)) return false; plot(x, y, bgColor); food.clear(x * height + y); return true; } // Return the background color for the bugs' world (which is not // necessarily the background color for the Canvas). public Color getWorldBackground() { return bgColor; } // Plot a single point in the given color. private void plot(int x, int y, Color color) { gImg.setColor(color); gImg.fillRect(x, y, 1, 1); } // Reset the simulation. public void reset() { // Blank it out. gImg.setColor(bgColor); gImg.fillRect(0, 0, width, height); graph.reset(); // Kill all the bugs. bugs.removeAllElements(); // Destroy all the food. food = new BitSet(); } // Add food (a bacterium) to a random location. private void randFood() { final int x = IntRand.rand(width); final int y = IntRand.rand(height); plot(x, y, foodColor); food.set(x * height + y); } // Scatter some food into the world for the initial population. private void sowSeed() { for (int i = 0; i < InitialFood; ++i) randFood(); } // Just as it says. private void createInitialPopulation() { bugs.removeAllElements(); // Also done in reset(), unnecessarily. for (int i = 0; i < SimEvolSettings.getInitialPopulationSize(); ++i) { bugs.addElement(new Bug(gImg, width, height)); repaint(); } } // Give each bug its timeslice, and clean up any that die. private void moveBugs() { Stack deadBugs = new Stack(); final int n = bugs.size(); // Let each bug move, and remember which ones died. for (int i = 0; i < n; ++i) if (!((Bug) bugs.elementAt(i)).tick(this)) deadBugs.push(new Integer(i)); // Reap any dead bugs. while (!deadBugs.empty()) bugs.removeElementAt(((Integer) deadBugs.pop()).intValue()); } // Let all bugs meeting the criteria breed. private void breedBugs() { final int n = bugs.size(); for (int i = 0; i < n; ++i) { Bug bug = (Bug) bugs.elementAt(i); if ((bug.getEnergy() >= SimEvolSettings.getStrongEnough()) && (bug.getAge() >= SimEvolSettings.getOldEnough())) { // We always add the new bugs at the end, so this // doesn't affect the traversal. bugs.addElement(bug.breed()); } } } // Takes 0.2 sec on my machine! // private int readPixel(int x, int y) // { // if (img == null) // return -1; // // final long before = System.currentTimeMillis(); // PixelGrabber pg = new PixelGrabber(img, x, y, 1, 1, false); // // while (true) // { // try // { // pg.grabPixels(); // SLOW (about 0.2 seconds)! // break; // } // catch (java.lang.InterruptedException ie) // { // System.out.println("Interrupted (" + ie + ") ...."); // continue; // } // } // final long after = System.currentTimeMillis(); // // final int color = (pg.getPixels() instanceof byte[]) // ? ((byte[]) (pg.getPixels()))[0] // : ((int[]) (pg.getPixels()))[0]; // // System.out.println("(" + x + ", " + y + "): " + color // + " " + (after - before)); // // return color; // } } // The main applet class. public class SimEvol extends Applet { private boolean initialized = false; // Guard redundant calls to init(). private SimEvolCanvas canvas = null; // The view onto the CA. // Ctor. public SimEvol() {} // Called by the browser to perform one-time initialization. public void init() { // Gracefully handle multiple calls to this method. if (initialized) return; initialized = true; SimEvolSettings.setToDefaults(this); final int w = SimEvolSettings.getWidth(); final int h = SimEvolSettings.getHeight(); setSize(w, h); // First row (just the canvas itself). final int graphHeight = 50; setLayout(new BorderLayout(0, 0)); final ScrollingGraph graph = new ScrollingGraph("Avg Straightness", w, graphHeight, 4); graph.setSize(w, graphHeight); add(graph, BorderLayout.NORTH); canvas = new SimEvolCanvas(this, w, h - graphHeight, graph); canvas.setSize(w, h - graphHeight); add(canvas, BorderLayout.CENTER); enableEvents(AWTEvent.MOUSE_EVENT_MASK); } // Start simulatin'. public void start() { canvas.start(); } // Whoa, Nelly! public void stop() { canvas.stop(); } // In case we're not running in in a Web browser. public static void main(String args[]) { SimEvolFrame frame = new SimEvolFrame(); } } // Only used when the SimEvol applet is not running in a Web browser. // A singleton. class SimEvolFrame extends Frame { public static SimEvolFrame instance = null; // Ctor. public SimEvolFrame() { super("Simulated Evolution"); instance = this; SimEvol applet = new SimEvol(); add(applet); applet.init(); setSize(SimEvolSettings.getWidth(), SimEvolSettings.getHeight()); applet.start(); enableEvents(AWTEvent.WINDOW_EVENT_MASK); show(); } public void processWindowEvent(WindowEvent e) { if (e.getID() == Event.WINDOW_DESTROY) System.exit(0); super.processWindowEvent(e); } }