Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
  1. rmmh revised this gist . 5 changed files with 90 additions and 151 deletions.
    View
    175 agents.js
    @@ -162,6 +162,7 @@ Agent.prototype.update = function ()
    this.energy -= 1;
    // Think and choose an action to perform
    + this.updateInputs();
    var action = this.think();
    // Switch on the action
    @@ -330,7 +331,7 @@ Agent.prototype.frontCellPos = function (x, y)
    // compute the absolute cell position
    var frontVec = Vector2.scalarMul(FRONT_VECTORS[this.direction], y);
    var sideVec = Vector2.scalarMul(SIDE_VECTORS[this.direction], x);
    - var cellPos = Vector2.add(this.position, Vector2.add(frontVec, sideVec));
    + var cellPos = frontVec.iadd(sideVec).iadd(this.position);
    // Return the computed cell position
    return cellPos;
    @@ -355,12 +356,13 @@ function AntAgent(connVecs)
    // Store the connection vectors
    this.connVecs = connVecs;
    - // Compile the think function
    - this.think = this.compile();
    -
    - // Initialize the state variables
    - for (var i = 0; i < AntAgent.numStateVars; ++i)
    - this['s' + i] = 0;
    + if (Float64Array) {
    + this.inputs = new Float64Array(AntAgent.numInputs + AntAgent.numStateVars);
    + } else {
    + this.inputs = new Array(AntAgent.numInputs + AntAgent.numStateVars);
    + for (var i = 0; i < AntAgent.numInputs + AntAgent.numStateVars; ++i)
    + this.inputs[i] = 0;
    + }
    }
    AntAgent.prototype = new Agent();
    @@ -432,9 +434,9 @@ AntAgent.addStateInput = function (connVec)
    {
    // Choose a random input
    if (randomInt(0, 1) === 0)
    - var varName = 'i' + randomInt(0, AntAgent.numInputs - 1);
    + var varName = randomInt(0, AntAgent.numInputs - 1);
    else
    - var varName = 'this.s' + randomInt(0, AntAgent.numStateVars - 1);
    + var varName = AntAgent.numInputs + randomInt(0, AntAgent.numStateVars - 1);
    // If the variable is already in the list, skip it
    if (connVec.inputs.indexOf(varName) !== -1)
    @@ -592,31 +594,8 @@ AntAgent.actFunc = function (x)
    }
    }
    -/**
    -Compile a think function for the ant agent
    -*/
    -AntAgent.prototype.compile = function ()
    -{
    - // Generated source string
    - var src = '';
    -
    - /**
    - Add a line of source input
    - */
    - function addLine(str)
    - {
    - if (str === undefined)
    - str = '';
    -
    - src += str + '\n';
    -
    - //dprintln(str);
    - }
    -
    - addLine('\tassert (this instanceof AntAgent)');
    - addLine();
    -
    - // Next cell input index
    +AntAgent.prototype.updateInputs = function ()
    +{
    var cellInIdx = 0;
    // For each horizontal cell position
    @@ -630,112 +609,54 @@ AntAgent.prototype.compile = function ()
    continue;
    // Compute the absolute cell position
    - addLine('\tvar pos = this.frontCellPos(' + x + ', ' + y + ');');
    -
    - addLine('\tif (');
    - addLine('\t\tpos.x >= 0 && pos.y >= 0 &&');
    - addLine('\t\tpos.x < world.gridWidth && pos.y < world.gridHeight)');
    - addLine('\t{');
    - addLine('\t\tvar cell = world.getCell(pos.x, pos.y);');
    - addLine('\t\tvar i' + (cellInIdx + 0) + ' = (cell.agent !== null)? 1:0;');
    - addLine('\t\tvar i' + (cellInIdx + 1) + ' = (cell.type === CELL_WALL)? 1:0;');
    - addLine('\t\tvar i' + (cellInIdx + 2) + ' = (cell.type === CELL_WATER)? 1:0;');
    - addLine('\t\tvar i' + (cellInIdx + 3) + ' = (cell.type === CELL_PLANT)? 1:0;');
    - addLine('\t\tvar i' + (cellInIdx + 4) + ' = (cell.type === CELL_EATEN)? 1:0;');
    - addLine('\t}');
    - addLine('\telse');
    - addLine('\t{');
    - addLine('\t\tvar i' + (cellInIdx + 0) + ' = 0;');
    - addLine('\t\tvar i' + (cellInIdx + 1) + ' = 1;');
    - addLine('\t\tvar i' + (cellInIdx + 2) + ' = 0;');
    - addLine('\t\tvar i' + (cellInIdx + 3) + ' = 0;');
    - addLine('\t\tvar i' + (cellInIdx + 4) + ' = 0;');
    - addLine('\t}');
    + var pos = this.frontCellPos(x, y);
    +
    + var cell = world.getCell(pos.x, pos.y);
    + this.inputs[cellInIdx + 0] = (cell.agent !== null)? 1:0;
    + this.inputs[cellInIdx + 1] = (cell.type === CELL_WALL)? 1:0;
    + this.inputs[cellInIdx + 2] = (cell.type === CELL_WATER)? 1:0;
    + this.inputs[cellInIdx + 3] = (cell.type === CELL_PLANT)? 1:0;
    + this.inputs[cellInIdx + 4] = (cell.type === CELL_EATEN)? 1:0;
    // Increment the cell input index
    cellInIdx += 5;
    }
    }
    - addLine();
    -
    - // For each random input
    - for (var i = 0; i < AntAgent.numRndInputs; ++i)
    - {
    - var inIdx = AntAgent.numCellInputs + i;
    -
    - addLine('\tvar i' + inIdx + ' = randomFloat(-1, 1);');
    - }
    -
    - /**
    - Generate a field input
    - */
    - function genFieldInput(idx, field)
    - {
    - var inIdx = AntAgent.numCellInputs + AntAgent.numRndInputs + idx;
    - addLine('\tvar i' + inIdx + ' = ' + field + ';');
    - }
    + this.inputs[cellInIdx + 0] = randomUnitFloat();
    + this.inputs[cellInIdx + 1] = randomUnitFloat();
    + this.inputs[cellInIdx + 2] = randomUnitFloat();
    + this.inputs[cellInIdx + 3] = randomUnitFloat();
    + this.inputs[cellInIdx + 4] = this.food;
    + this.inputs[cellInIdx + 5] = this.water;
    + this.inputs[cellInIdx + 6] = this.energy;
    +}
    - /**
    - Generate a state variable update computation
    - */
    - function genUpdate(connVec)
    +AntAgent.prototype.think = function ()
    +{
    + var stateOffset = AntAgent.numInputs;
    + for (var i = 0; i < this.connVecs.length; ++i)
    {
    - var src = '';
    -
    - src += 'AntAgent.actFunc(';
    -
    - for (var i = 0; i < connVec.inputs.length; ++i)
    + var accum = 0;
    + var connVec = this.connVecs[i];
    + for (var j = 0; j < connVec.inputs.length; ++j)
    {
    - var input = connVec.inputs[i];
    - var weight = connVec.weights[i];
    -
    - if (i !== 0)
    - src += ' + ';
    -
    - src += input + '*' + weight;
    + accum += this.inputs[connVec.inputs[j]] * connVec.weights[j];
    }
    -
    - src += ')';
    -
    - return src;
    + this.inputs[stateOffset + i] = AntAgent.actFunc(accum);
    }
    - // Compile the input computations
    - genFieldInput(0, 'this.food');
    - genFieldInput(1, 'this.water');
    - genFieldInput(2, 'this.energy');
    - addLine();
    -
    - // Compile the state updates
    - for (var i = 0; i < this.connVecs.length; ++i)
    - addLine('\tthis.s' + i + ' = ' + genUpdate(this.connVecs[i]) + ';');
    - addLine();
    -
    - // Choose the action to perform
    - addLine('\tvar maxVal = -Infinity;');
    - addLine('\tvar action = 0;\n');
    + var actionOffset = stateOffset + AntAgent.numStateVars - NUM_ACTIONS;
    + var maxVal = -Infinity;
    + var action = 0;
    for (var i = 0; i < NUM_ACTIONS; ++i)
    {
    - var stateIdx = AntAgent.numStateVars - NUM_ACTIONS + i;
    -
    - var varName = 'this.s' + stateIdx;
    -
    - addLine('\tif (' + varName + ' > maxVal)');
    - addLine('\t{');
    - addLine('\t\tmaxVal = ' + varName + ';');
    - addLine('\t\taction = ' + i + ';');
    - addLine('\t}');
    + var actionVal = this.inputs[actionOffset + i]
    + if (actionVal > maxVal) {
    + maxVal = actionVal;
    + action = i;
    + }
    }
    - addLine();
    -
    - // Return the chosen action
    - addLine('\treturn action;');
    -
    - // Compile the think function from its source
    - var thinkFunc = new Function(src);
    -
    - // Return the thinking function
    - return thinkFunc;
    -}
    + return action;
    +}
    View
    9 gradient.js
    @@ -119,7 +119,9 @@ function init()
    // Initialize the speed count parameters
    speedCountStartTime = getTimeSecs();
    speedCountStartItrs = 0;
    + speedCountStartUpdates = 0;
    itrsPerSec = 0;
    + updatesPerSec = 0;
    }
    window.addEventListener("load", init, false);
    @@ -135,6 +137,7 @@ function keyDown(event)
    case 38: controls[CTRL_UP] = true; break;
    case 39: controls[CTRL_RIGHT] = true; break;
    case 40: controls[CTRL_DOWN] = true; break;
    + default: return true;
    }
    // Prevent the default key behavior (window movement)
    @@ -153,6 +156,7 @@ function keyUp(event)
    case 38: controls[CTRL_UP] = false; break;
    case 39: controls[CTRL_RIGHT] = false; break;
    case 40: controls[CTRL_DOWN] = false; break;
    + default: return true;
    }
    // Prevent the default key behavior (window movement)
    @@ -259,6 +263,7 @@ function update()
    printStats(
    'time running: ' + timeRunningSecs + 's\n' +
    'iterations/s: ' + itrsPerSec + '\n' +
    + 'agent upd./s: ' + updatesPerSec + '\n' +
    '\n' +
    'ind. count : ' + genAlg.indCount + '\n' +
    'seed inds. : ' + genAlg.seedCount + '\n' +
    @@ -286,6 +291,10 @@ function update()
    itrsPerSec = Math.round(itrCount / SPEED_COUNT_INTERV);
    speedCountStartItrs = world.itrCount;
    speedCountStartTime = getTimeSecs();
    +
    + var updateCount = world.updateCount - speedCountStartUpdates;
    + updatesPerSec = Math.round(updateCount / SPEED_COUNT_INTERV);
    + speedCountStartUpdates = world.updateCount;
    }
    }
    View
    5 utility.js
    @@ -151,6 +151,11 @@ function randomFloat(a, b)
    return rnd;
    }
    +function randomUnitFloat()
    +{
    + return Math.random() * 2 - 1;
    +}
    +
    /**
    Generate a random value from a normal distribution
    */
    View
    12 vector.js
    @@ -46,10 +46,18 @@ Vector2.add = function (v1, v2)
    }
    /**
    +Add a vector to another, modifying it in-place
    +*/
    +Vector2.prototype.iadd = function (v) {
    + this.x += v.x;
    + this.y += v.y;
    + return this;
    +}
    +
    +/**
    Multiply a vector by a scalar
    */
    Vector2.scalarMul = function (v, s)
    {
    return new Vector2(v.x * s, v.y * s);
    -}
    -
    +}
    View
    40 world.js
    @@ -164,6 +164,11 @@ function World()
    this.itrCount = 0;
    /**
    + Total agent update count
    + */
    + this.updateCount = 0;
    +
    + /**
    Last reset iteration
    */
    this.lastResetIt = 0;
    @@ -495,9 +500,11 @@ World.prototype.generate = function (
    {
    // Make the top border a wall
    this.setCell(x, 0, new Cell(CELL_WALL));
    + this.setCell(x, 1, new Cell(CELL_WALL));
    // Make the bottom border a wall
    this.setCell(x, this.gridHeight - 1, new Cell(CELL_WALL));
    + this.setCell(x, this.gridHeight - 2, new Cell(CELL_WALL));
    }
    // For each row
    @@ -505,9 +512,11 @@ World.prototype.generate = function (
    {
    // Make the left border a wall
    this.setCell(0, y, new Cell(CELL_WALL));
    + this.setCell(1, y, new Cell(CELL_WALL));
    // Make the right border a wall
    this.setCell(this.gridWidth - 1, y, new Cell(CELL_WALL));
    + this.setCell(this.gridWidth - 2, y, new Cell(CELL_WALL));
    }
    }
    @@ -547,11 +556,7 @@ Respawn eaten plants
    World.prototype.respawnPlants = function (respawnAll)
    {
    // By default, do not respawn all plants
    - if (respawnAll === undefined)
    - respawnAll = false;
    -
    - // Remaining eaten plants array
    - var eatenPlants = [];
    + respawnAll = !!respawnAll; // undefined -> false
    // For each eaten plant
    for (var i = 0; i < this.eatenPlants.length; ++i)
    @@ -559,9 +564,9 @@ World.prototype.respawnPlants = function (respawnAll)
    var plant = this.eatenPlants[i];
    // If it is not time for this plant to be respawned, skip it
    - if (plant.respawnTime > this.itrCount && !(respawnAll === true))
    + if (plant.respawnTime > this.itrCount && !respawnAll)
    {
    - eatenPlants.push(plant);
    + ++i;
    continue;
    }
    @@ -575,10 +580,11 @@ World.prototype.respawnPlants = function (respawnAll)
    this.availPlants <= this.numPlants,
    'invalid available plant count'
    );
    - }
    - // Update the eaten plants array
    - this.eatenPlants = eatenPlants;
    + // Shift the eaten plant array down
    + this.eatenPlants[i] = this.eatenPlants[this.eatenPlants.length - 1];
    + this.eatenPlants.splice(-1, 1);
    + }
    }
    /**
    @@ -633,7 +639,7 @@ World.prototype.update = function ()
    // Perform a small number of update iterations
    for (var i = 0; i < WORLD_UPDATE_ITR_COUNT; ++i)
    - this.iterate();
    + this.iterate();
    }
    }
    else
    @@ -655,6 +661,7 @@ World.prototype.iterate = function ()
    // Update the agent state
    agent.update();
    + this.updateCount++;
    // If the agent is no longer alive
    if (agent.isAlive() === false)
    @@ -976,21 +983,10 @@ World.prototype.moveAgent = function (agent, x, y)
    {
    // Ensure that the parameters are valid
    assert (agent != null);
    -
    - // If this moves out of the map, deny the movement
    - if (x > this.gridWidth || y > this.gridHeight)
    - return false;
    // Get the ant position
    const pos = agent.position;
    - // Ensure that the agent position is valid
    - assert (
    - pos.x >= 0 && pos.y >= 0 &&
    - pos.x < this.gridWidth && pos.y < this.gridHeight,
    - 'invalid agent position'
    - );
    -
    // Obtain references to the concerned cells
    orig = this.getCell(pos.x, pos.y);
    dest = this.getCell(x, y);
  2. rmmh created this gist .
    View
    741 agents.js
    @@ -0,0 +1,741 @@
    +/*****************************************************************************
    +*
    +* Gradient: an Artificial Life Experiment
    +* Copyright (C) 2011 Maxime Chevalier-Boisvert
    +*
    +* This file is part of Gradient.
    +*
    +* Gradient 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 3 of the License, or
    +* (at your option) any later version.
    +*
    +* Gradient 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 Gradient. If not, see <http://www.gnu.org/licenses/>.
    +*
    +* For more information about this program, please e-mail the
    +* author, Maxime Chevalier-Boisvert at:
    +* maximechevalierb /at/ gmail /dot/ com
    +*
    +*****************************************************************************/
    +
    +//============================================================================
    +// Virtual Agents
    +//============================================================================
    +
    +// Front direction vectors associated with ant directions
    +const FRONT_VECTORS =
    +[
    + new Vector2( 0,-1),
    + new Vector2( 1, 0),
    + new Vector2( 0, 1),
    + new Vector2(-1, 0)
    +];
    +
    +// Side direction vectors associated with ant directions
    +const SIDE_VECTORS =
    +[
    + new Vector2( 1, 0),
    + new Vector2( 0, 1),
    + new Vector2(-1, 0),
    + new Vector2( 0,-1)
    +];
    +
    +// Possible directions
    +const AGENT_DIR_UP = 0;
    +const AGENT_DIR_RIGHT = 1;
    +const AGENT_DIR_DOWN = 2;
    +const AGENT_DIR_LEFT = 3;
    +
    +// Possible actions
    +const ACTION_DO_NOTHING = 0;
    +const ACTION_MOVE_FORWARD = 1;
    +const ACTION_ROTATE_LEFT = 2;
    +const ACTION_ROTATE_RIGHT = 3;
    +const ACTION_CONSUME = 4;
    +const ACTION_REPRODUCE = 5;
    +const ACTION_BUILD = 6;
    +
    +// Total number of possible actions
    +const NUM_ACTIONS = ACTION_REPRODUCE + 1;
    +
    +// Starting food, water and energy quantities
    +const START_FOOD = 250;
    +const START_WATER = 500;
    +const START_ENERGY = 250;
    +
    +// Maximum food and water and energy quantities
    +const MAX_FOOD = 5000;
    +const MAX_WATER = 5000;
    +const MAX_ENERGY = 5000;
    +
    +// Quantities of food and water extracted by consumption
    +const FOOD_CONS_QTY = 250;
    +const WATER_CONS_QTY = 500;
    +
    +// Energy cost to produce offspring
    +const OFFSPRING_COST = START_ENERGY + START_FOOD + 100;
    +
    +// Energy cost to build a wall block
    +const BUILD_COST = 50;
    +
    +/**
    +Base agent class
    +*/
    +function Agent()
    +{
    + // Reset all agent parameters
    + this.reset();
    +}
    +
    +/**
    +Reset the agent's parameters to their initial values
    +*/
    +Agent.prototype.reset = function ()
    +{
    + // Reset the position
    + this.position = new Vector2(0, 0);
    +
    + // Select a random direction for the ant
    + this.direction = randomInt(AGENT_DIR_UP, AGENT_DIR_LEFT);
    +
    + // Reset the sleeping state
    + this.sleeping = false;
    +
    + // Reset the agent's age
    + this.age = 0;
    +
    + // Reset the food amount
    + this.food = START_FOOD;
    +
    + // Reset the water amount
    + this.water = START_WATER;
    +
    + // Reset the energy level
    + this.energy = START_ENERGY;
    +}
    +
    +/**
    +Update the state of the agent
    +*/
    +Agent.prototype.update = function ()
    +{
    + // Increment the agent's age
    + this.age += 1;
    +
    + // If we have food and water
    + if (this.food > 0 && this.water > 0)
    + {
    + // If water is the limiting element
    + if (this.food >= this.water)
    + {
    + assert (
    + this.food > 0,
    + 'no food available'
    + );
    +
    + // Food + water => energy
    + this.energy += this.water;
    + this.food -= this.water;
    + this.water = 0;
    + }
    + else
    + {
    + assert (
    + this.water > 0,
    + 'no water available'
    + );
    +
    + // Food + water => energy
    + this.energy += this.food;
    + this.water -= this.food;
    + this.food = 0;
    + }
    + }
    +
    + // Decrement the energy level, living cost energy
    + this.energy -= 1;
    +
    + // Think and choose an action to perform
    + var action = this.think();
    +
    + // Switch on the action
    + switch (action)
    + {
    + // To do nothing
    + case ACTION_DO_NOTHING:
    + {
    + }
    + break;
    +
    + // To move forward
    + case ACTION_MOVE_FORWARD:
    + {
    + // Attempt to move to the cell just ahead
    + var pos = this.frontCellPos(0, 1);
    + world.moveAgent(this, pos.x, pos.y);
    + }
    + break;
    +
    + // To rotate left
    + case ACTION_ROTATE_LEFT:
    + {
    + // Shift our direction to the left
    + this.direction = Math.abs((this.direction - 1) % 4);
    + }
    + break;
    +
    + // To rotate right
    + case ACTION_ROTATE_RIGHT:
    + {
    + // Shift our direction to the right
    + this.direction = Math.abs((this.direction + 1) % 4);
    + }
    + break;
    +
    + // To consume resources
    + case ACTION_CONSUME:
    + {
    + // Attempt to consume what is in front of us
    + this.consume();
    + }
    + break;
    +
    + // To make offspring
    + case ACTION_REPRODUCE:
    + {
    + // Attempt to reproduce
    + this.reproduce();
    + }
    + break;
    +
    + // To build a wall block
    + case ACTION_BUILD:
    + {
    + // Attempt to build
    + this.build();
    + }
    + break;
    +
    + default:
    + error('invalid agent action');
    + }
    +
    + assert(
    + this.direction >= AGENT_DIR_UP &&
    + this.direction <= AGENT_DIR_LEFT,
    + 'invalid agent direction after update'
    + );
    +}
    +
    +/**
    +Process environmental inputs and choose an action.
    +To be set on each agent
    +*/
    +Agent.prototype.think = function ()
    +{
    + error('think function not set');
    +}
    +
    +/**
    +Test if this agent is still alive
    +*/
    +Agent.prototype.isAlive = function ()
    +{
    + // The ant is alive if it still has energy
    + return (this.energy > 0);
    +}
    +
    +/**
    +Perform the consumption action
    +*/
    +Agent.prototype.consume = function ()
    +{
    + // compute the position of the cell just ahead
    + var pos = this.frontCellPos(0, 1);
    +
    + // If this is a plant we can eat
    + if (
    + this.food + FOOD_CONS_QTY <= MAX_FOOD &&
    + world.eatPlant(pos.x, pos.y) === true)
    + {
    + // Gain food
    + this.food += FOOD_CONS_QTY;
    +
    + // Eating successful
    + return true;
    + }
    +
    + // Otherwise, if this cell is water
    + else if (
    + this.water + WATER_CONS_QTY <= MAX_WATER &&
    + world.cellIsType(pos.x, pos.y, CELL_WATER) === true)
    + {
    + // Gain water
    + this.water += WATER_CONS_QTY;
    +
    + // Consumption successful
    + return true;
    + }
    +
    + // Consumption failed
    + return false;
    +}
    +
    +/**
    +Attempt to produce offspring
    +*/
    +Agent.prototype.reproduce = function ()
    +{
    + // If we do not have enough energy to produce offspring, do nothing
    + if (this.energy < OFFSPRING_COST)
    + return;
    +
    + // Subtract the energy required to produce offspring
    + this.energy -= OFFSPRING_COST;
    +
    + // Produce offspring from this agent
    + genAlg.makeOffspring(this);
    +}
    +
    +/**
    +To build a wall block
    +*/
    +Agent.prototype.build = function ()
    +{
    + // If we do not have enough energy to build a block, do nothing
    + if (this.energy < BUILD_COST)
    + return;
    +
    + // Subtract the energy require to build
    + this.energy -= BUILD_COST;
    +
    + // Get the position of the cell ahead of us
    + pos = this.frontCellPos(0, 1);
    +
    + // Try to build a block at the cell in front of us
    + world.buildBlock(pos.x, pos.y);
    +}
    +
    +/**
    +Compute a cell position relative to our direction
    +*/
    +Agent.prototype.frontCellPos = function (x, y)
    +{
    + // compute the absolute cell position
    + var frontVec = Vector2.scalarMul(FRONT_VECTORS[this.direction], y);
    + var sideVec = Vector2.scalarMul(SIDE_VECTORS[this.direction], x);
    + var cellPos = Vector2.add(this.position, Vector2.add(frontVec, sideVec));
    +
    + // Return the computed cell position
    + return cellPos;
    +}
    +
    +/**
    +@class Ant agent constructor
    +@extends Agent
    +*/
    +function AntAgent(connVecs)
    +{
    + assert (
    + connVecs instanceof Array,
    + 'expected connection vectors'
    + );
    +
    + assert (
    + connVecs.length === AntAgent.numStateVars,
    + 'need connection vectors for each state var'
    + );
    +
    + // Store the connection vectors
    + this.connVecs = connVecs;
    +
    + // Compile the think function
    + this.think = this.compile();
    +
    + // Initialize the state variables
    + for (var i = 0; i < AntAgent.numStateVars; ++i)
    + this['s' + i] = 0;
    +}
    +AntAgent.prototype = new Agent();
    +
    +/**
    +Number of visible cell inputs.
    +
    +Agent's view:
    + F
    + |
    + X X X
    +L- X X X - R
    + X A x
    +
    +8 visible cells x 5 attributes per cell = 40 boolean inputs
    +*/
    +AntAgent.numCellInputs = 40;
    +
    +/**
    +Number of random inputs
    +*/
    +AntAgent.numRndInputs = 4;
    +
    +/*
    +Number of field inputs.
    +3 local properties (food, water, energy).
    +*/
    +AntAgent.numFieldInputs = 3;
    +
    +/*
    +Total number of agent inputs
    +*/
    +AntAgent.numInputs =
    + AntAgent.numCellInputs +
    + AntAgent.numRndInputs +
    + AntAgent.numFieldInputs;
    +
    +/**
    +Number of agent state variables
    +*/
    +AntAgent.numStateVars = 16 + NUM_ACTIONS;
    +
    +/**
    +Maximum number of inputs per connection vector
    +*/
    +AntAgent.maxStateInputs = 8;
    +
    +/**
    +Maximum neural connection weight
    +*/
    +AntAgent.maxWeight = 10.0;
    +
    +/**
    +Minimum neural connection weight
    +*/
    +AntAgent.minWeight = -10;
    +
    +/**
    +Add an input to a state connection vector
    +*/
    +AntAgent.addStateInput = function (connVec)
    +{
    + assert (
    + connVec.inputs.length < AntAgent.maxStateInputs,
    + 'too many inputs'
    + );
    +
    + // Until a new input is added
    + while (true)
    + {
    + // Choose a random input
    + if (randomInt(0, 1) === 0)
    + var varName = 'i' + randomInt(0, AntAgent.numInputs - 1);
    + else
    + var varName = 'this.s' + randomInt(0, AntAgent.numStateVars - 1);
    +
    + // If the variable is already in the list, skip it
    + if (connVec.inputs.indexOf(varName) !== -1)
    + continue;
    +
    + // Add the variable to the inputs
    + connVec.inputs.push(varName);
    +
    + // Choose a random weight for the connection
    + connVec.weights.push(
    + randomFloat(AntAgent.minWeight, AntAgent.maxWeight)
    + );
    +
    + // Break out of the loop
    + break;
    + }
    +}
    +
    +/**
    +Factory function to create a new ant agent
    +*/
    +AntAgent.newAgent = function ()
    +{
    + /**
    + Generate a connection vector for a state variable
    + */
    + function genConnVector()
    + {
    + // Choose the number of connections for this
    + var numInputs = randomInt(1, AntAgent.maxStateInputs);
    +
    + var connVec = {
    + inputs: [],
    + weights: []
    + };
    +
    + // Until all inputs are added
    + for (var numAdded = 0; numAdded < numInputs;)
    + {
    + // Add an input connection
    + AntAgent.addStateInput(connVec);
    +
    + // Increment the number of inputs added
    + ++numAdded;
    + }
    +
    + // Return the connection vector
    + return connVec;
    + }
    +
    + assert (
    + AntAgent.numStateVars >= NUM_ACTIONS,
    + 'insufficient number of state variables'
    + );
    +
    + // Array for the state variable connection vectors
    + var connVecs = new Array(AntAgent.numStateVars);
    +
    + // Generate connections for each state variable
    + for (var i = 0; i < AntAgent.numStateVars; ++i)
    + connVecs[i] = genConnVector();
    +
    + // Create the new agent
    + return new AntAgent(connVecs);
    +}
    +
    +/**
    +Return a mutated version of an agent
    +*/
    +AntAgent.mutate = function (agent, mutProb)
    +{
    + assert (
    + agent instanceof AntAgent,
    + 'expected ant agent'
    + );
    +
    + assert (
    + mutProb >= 0 && mutProb <= 1,
    + 'invalid mutation probability'
    + );
    +
    + // Array of connection vectors
    + var connVecs = [];
    +
    + // For each connection vector
    + for (var i = 0; i < agent.connVecs.length; ++i)
    + {
    + var oldVec = agent.connVecs[i];
    +
    + // Copy the inputs and weights
    + var newVec = {
    + inputs : oldVec.inputs.slice(0),
    + weights: oldVec.weights.slice(0)
    + };
    +
    + // For each mutation attempt
    + for (var j = 0; j < AntAgent.maxStateInputs; ++j)
    + {
    + // If the mutation probability is not met, try again
    + if (randomFloat(0, 1) >= mutProb)
    + continue;
    +
    + // Get the current number of inputs
    + var numInputs = newVec.inputs.length;
    +
    + // If we should remove an input
    + if (randomBool() === true)
    + {
    + // If there are too few inputs, try again
    + if (numInputs <= 1)
    + continue;
    +
    + // Choose a random input and remove it
    + var idx = randomInt(0, numInputs - 1);
    + newVec.inputs.splice(idx, 1);
    + newVec.weights.splice(idx, 1);
    + }
    +
    + // If we should add an input
    + else
    + {
    + // If there are too many inputs, try again
    + if (numInputs >= AntAgent.maxStateInputs)
    + continue;
    +
    + // Add an input to the rule
    + AntAgent.addStateInput(newVec);
    + }
    + }
    +
    + // Add the mutated connection vector
    + connVecs.push(newVec);
    + }
    +
    + // Create the new agent
    + return new AntAgent(connVecs);
    +}
    +
    +/**
    +Neural network activation function.
    +Fast approximation to tanh(x/2)
    +*/
    +AntAgent.actFunc = function (x)
    +{
    + if (x < 0)
    + {
    + x = -x;
    + x = x * (6 + x * (3 + x));
    + return -x / (x + 12);
    + }
    + else
    + {
    + x = x * (6 + x * (3 + x));
    + return x / (x + 12);
    + }
    +}
    +
    +/**
    +Compile a think function for the ant agent
    +*/
    +AntAgent.prototype.compile = function ()
    +{
    + // Generated source string
    + var src = '';
    +
    + /**
    + Add a line of source input
    + */
    + function addLine(str)
    + {
    + if (str === undefined)
    + str = '';
    +
    + src += str + '\n';
    +
    + //dprintln(str);
    + }
    +
    + addLine('\tassert (this instanceof AntAgent)');
    + addLine();
    +
    + // Next cell input index
    + var cellInIdx = 0;
    +
    + // For each horizontal cell position
    + for (var x = -1; x <= 1; ++x)
    + {
    + // For each vertical cell position
    + for (var y = 0; y <= 2; ++y)
    + {
    + // If this is the agent's position, skip it
    + if (x === 0 && y === 0)
    + continue;
    +
    + // Compute the absolute cell position
    + addLine('\tvar pos = this.frontCellPos(' + x + ', ' + y + ');');
    +
    + addLine('\tif (');
    + addLine('\t\tpos.x >= 0 && pos.y >= 0 &&');
    + addLine('\t\tpos.x < world.gridWidth && pos.y < world.gridHeight)');
    + addLine('\t{');
    + addLine('\t\tvar cell = world.getCell(pos.x, pos.y);');
    + addLine('\t\tvar i' + (cellInIdx + 0) + ' = (cell.agent !== null)? 1:0;');
    + addLine('\t\tvar i' + (cellInIdx + 1) + ' = (cell.type === CELL_WALL)? 1:0;');
    + addLine('\t\tvar i' + (cellInIdx + 2) + ' = (cell.type === CELL_WATER)? 1:0;');
    + addLine('\t\tvar i' + (cellInIdx + 3) + ' = (cell.type === CELL_PLANT)? 1:0;');
    + addLine('\t\tvar i' + (cellInIdx + 4) + ' = (cell.type === CELL_EATEN)? 1:0;');
    + addLine('\t}');
    + addLine('\telse');
    + addLine('\t{');
    + addLine('\t\tvar i' + (cellInIdx + 0) + ' = 0;');
    + addLine('\t\tvar i' + (cellInIdx + 1) + ' = 1;');
    + addLine('\t\tvar i' + (cellInIdx + 2) + ' = 0;');
    + addLine('\t\tvar i' + (cellInIdx + 3) + ' = 0;');
    + addLine('\t\tvar i' + (cellInIdx + 4) + ' = 0;');
    + addLine('\t}');
    +
    + // Increment the cell input index
    + cellInIdx += 5;
    + }
    + }
    + addLine();
    +
    + // For each random input
    + for (var i = 0; i < AntAgent.numRndInputs; ++i)
    + {
    + var inIdx = AntAgent.numCellInputs + i;
    +
    + addLine('\tvar i' + inIdx + ' = randomFloat(-1, 1);');
    + }
    +
    + /**
    + Generate a field input
    + */
    + function genFieldInput(idx, field)
    + {
    + var inIdx = AntAgent.numCellInputs + AntAgent.numRndInputs + idx;
    +
    + addLine('\tvar i' + inIdx + ' = ' + field + ';');
    + }
    +
    + /**
    + Generate a state variable update computation
    + */
    + function genUpdate(connVec)
    + {
    + var src = '';
    +
    + src += 'AntAgent.actFunc(';
    +
    + for (var i = 0; i < connVec.inputs.length; ++i)
    + {
    + var input = connVec.inputs[i];
    + var weight = connVec.weights[i];
    +
    + if (i !== 0)
    + src += ' + ';
    +
    + src += input + '*' + weight;
    + }
    +
    + src += ')';
    +
    + return src;
    + }
    +
    + // Compile the input computations
    + genFieldInput(0, 'this.food');
    + genFieldInput(1, 'this.water');
    + genFieldInput(2, 'this.energy');
    + addLine();
    +
    + // Compile the state updates
    + for (var i = 0; i < this.connVecs.length; ++i)
    + addLine('\tthis.s' + i + ' = ' + genUpdate(this.connVecs[i]) + ';');
    + addLine();
    +
    + // Choose the action to perform
    + addLine('\tvar maxVal = -Infinity;');
    + addLine('\tvar action = 0;\n');
    + for (var i = 0; i < NUM_ACTIONS; ++i)
    + {
    + var stateIdx = AntAgent.numStateVars - NUM_ACTIONS + i;
    +
    + var varName = 'this.s' + stateIdx;
    +
    + addLine('\tif (' + varName + ' > maxVal)');
    + addLine('\t{');
    + addLine('\t\tmaxVal = ' + varName + ';');
    + addLine('\t\taction = ' + i + ';');
    + addLine('\t}');
    + }
    + addLine();
    +
    + // Return the chosen action
    + addLine('\treturn action;');
    +
    + // Compile the think function from its source
    + var thinkFunc = new Function(src);
    +
    + // Return the thinking function
    + return thinkFunc;
    +}
    +
    View
    158 genalg.js
    @@ -0,0 +1,158 @@
    +/*****************************************************************************
    +*
    +* Gradient: an Artificial Life Experiment
    +* Copyright (C) 2011 Maxime Chevalier-Boisvert
    +*
    +* This file is part of Gradient.
    +*
    +* Gradient 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 3 of the License, or
    +* (at your option) any later version.
    +*
    +* Gradient 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 Gradient. If not, see <http://www.gnu.org/licenses/>.
    +*
    +* For more information about this program, please e-mail the
    +* author, Maxime Chevalier-Boisvert at:
    +* maximechevalierb /at/ gmail /dot/ com
    +*
    +*****************************************************************************/
    +
    +//============================================================================
    +// Genetic Algorithm Implementation
    +//============================================================================
    +
    +/**
    +Constructor for agent evolution GA
    +*/
    +function GenAlg(agentClass)
    +{
    + /**
    + Agent class function
    + */
    + this.agentClass = agentClass;
    +
    + /**
    + Population vector
    + */
    + this.population = [];
    +
    + /**
    + Minimum population size
    + */
    + this.minPopSize = 25;
    +
    + /**
    + Mutation probability, for asexual reproduction.
    + */
    + this.mutProb = 0.02;
    +
    + /**
    + Produced individual count
    + */
    + this.indCount = 0;
    +
    + /**
    + Seed individual count
    + */
    + this.seedCount = 0;
    +}
    +
    +/**
    +Update the state of the GA
    +*/
    +GenAlg.prototype.update = function ()
    +{
    + // Count of live agents
    + var liveCount = 0;
    +
    + // For each individual in the population
    + for (var i = 0; i < this.population.length; ++i)
    + {
    + var agent = this.population[i];
    +
    + // If the agent is alive
    + if (agent.isAlive())
    + {
    + // Increment the live agent count
    + liveCount++;
    + }
    + else
    + {
    + // Remove the agent from the population
    + this.population.splice(i, 1);
    + --i;
    + }
    + }
    +
    + // While the population size is below the minimum
    + while (liveCount < this.minPopSize)
    + {
    + // Create a new agent
    + var agent = this.newIndividual();
    +
    + // Add the agent to the population
    + this.population.push(agent);
    +
    + // Place the agent at random coordinates
    + world.placeAgentRnd(agent);
    +
    + // Increment the live count
    + liveCount++;
    +
    + // Increment the seed individuals count
    + this.seedCount++;
    + }
    +}
    +
    +/**
    +Create a new individual
    +*/
    +GenAlg.prototype.newIndividual = function ()
    +{
    + // Create a new agent
    + var newAgent = this.agentClass.newAgent();
    +
    + // Increment the count of individuals created
    + ++this.indCount;
    +
    + // Return the new agent
    + return newAgent;
    +}
    +
    +/**
    +Mutate an individual
    +*/
    +GenAlg.prototype.mutate = function (agent)
    +{
    + // Mutate the agent
    + var newAgent = this.agentClass.mutate(agent, this.mutProb);
    +
    + // Increment the count of individuals created
    + ++this.indCount;
    +
    + // Return a pointer to the new agent
    + return newAgent;
    +}
    +
    +/**
    +Create offspring for an agent
    +*/
    +GenAlg.prototype.makeOffspring = function (agent)
    +{
    + // Create a new agent through mutation
    + var newAgent = this.mutate(agent);
    +
    + // Add the new agent to the population
    + this.population.push(newAgent);
    +
    + // Place the new agent in the world near the parent
    + world.placeAgentNear(newAgent, agent.position.x, agent.position.y);
    +}
    +
    View
    433 gradient.js
    @@ -0,0 +1,433 @@
    +/*****************************************************************************
    +*
    +* Gradient: an Artificial Life Experiment
    +* Copyright (C) 2011 Maxime Chevalier-Boisvert
    +*
    +* This file is part of Gradient.
    +*
    +* Gradient 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 3 of the License, or
    +* (at your option) any later version.
    +*
    +* Gradient 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 Gradient. If not, see <http://www.gnu.org/licenses/>.
    +*
    +* For more information about this program, please e-mail the
    +* author, Maxime Chevalier-Boisvert at:
    +* maximechevalierb /at/ gmail /dot/ com
    +*
    +*****************************************************************************/
    +
    +//============================================================================
    +// Page interface code
    +//============================================================================
    +
    +// GUI redrawing delay
    +const GUI_REDRAW_DELAY = 0.2;
    +
    +// Speed count interval
    +const SPEED_COUNT_INTERV = 3;
    +
    +// Movement controls
    +const CTRL_UP = 0;
    +const CTRL_DOWN = 1;
    +const CTRL_LEFT = 2;
    +const CTRL_RIGHT = 3;
    +
    +/**
    +Called after page load to initialize needed resources
    +*/
    +function init()
    +{
    + // Find the debug and stats text elements
    + debugTextElem = findElementById("debug_text");
    + statsTextElem = findElementById("stats_text");
    +
    + // Find the control button elements
    + zoomInButton = findElementById("zoom_in_button");
    + zoomOutButton = findElementById("zoom_out_button");
    + realTimeButton = findElementById("real_time_button");
    + fastModeButton = findElementById("fast_mode_button");
    +
    + // Get a reference to the canvas
    + canvas = document.getElementById("canvas");
    +
    + // Set the canvas size
    + canvas.width = 512;
    + canvas.height = 512;
    +
    + // Get a 2D context for the drawing canvas
    + canvasCtx = canvas.getContext("2d");
    +
    + // Clear the canvas
    + clearCanvas(canvas, canvasCtx);
    +
    + // Create the genetic algorithm instance
    + genAlg = new GenAlg(AntAgent);
    +
    + // Create the world instance
    + world = new World();
    +
    + // Generate the world map
    + world.generate(
    + 128, // Width
    + 128, // Height
    + true, // Plants respawn flag
    + undefined,
    + undefined,
    + undefined,
    + 10, // Row walls mean
    + 1, // Row walls var
    + 10, // Col walls mean
    + 1 // Col walls var
    + );
    +
    + // Initialize the camera coordinates
    + xCoord = 0;
    + yCoord = 0;
    +
    + // Initialize the zoom level
    + zoomLevel = WORLD_ZOOM_MAX - 4;
    +
    + // Movement control states
    + controls = [];
    +
    + // Last redrawing time
    + lastRedraw = 0;
    +
    + // Set the update function to be called regularly
    + this.updateInterv = setInterval(
    + update,
    + WORLD_UPDATE_TIME_SLICE * 1000
    + );
    +
    + // Initialize the button states
    + zoomInButton.disabled = (zoomLevel >= WORLD_ZOOM_MAX);
    + zoomOutButton.disabled = (zoomLevel <= WORLD_ZOOM_MIN);
    + realTimeButton.disabled = (world.fastMode === false);
    + fastModeButton.disabled = (world.fastMode === true);
    +
    + // Store the starting time in seconds
    + startTimeSecs = getTimeSecs();
    +
    + // Initialize the speed count parameters
    + speedCountStartTime = getTimeSecs();
    + speedCountStartItrs = 0;
    + itrsPerSec = 0;
    +
    +}
    +window.addEventListener("load", init, false);
    +
    +/**
    +Key press handler
    +*/
    +function keyDown(event)
    +{
    + switch (event.keyCode)
    + {
    + case 37: controls[CTRL_LEFT] = true; break;
    + case 38: controls[CTRL_UP] = true; break;
    + case 39: controls[CTRL_RIGHT] = true; break;
    + case 40: controls[CTRL_DOWN] = true; break;
    + }
    +
    + // Prevent the default key behavior (window movement)
    + event.preventDefault();
    +}
    +window.addEventListener("keydown", keyDown, false);
    +
    +/**
    +Key release handler
    +*/
    +function keyUp(event)
    +{
    + switch (event.keyCode)
    + {
    + case 37: controls[CTRL_LEFT] = false; break;
    + case 38: controls[CTRL_UP] = false; break;
    + case 39: controls[CTRL_RIGHT] = false; break;
    + case 40: controls[CTRL_DOWN] = false; break;
    + }
    +
    + // Prevent the default key behavior (window movement)
    + event.preventDefault();
    +}
    +window.addEventListener("keyup", keyUp, false);
    +
    +/**
    +Find an element in the HTML document by its id
    +*/
    +function findElementById(id, elem)
    +{
    + if (elem === undefined)
    + elem = document
    +
    + for (k in elem.childNodes)
    + {
    + var child = elem.childNodes[k];
    +
    + if (child.attributes)
    + {
    + var childId = child.getAttribute('id');
    +
    + if (childId == id)
    + return child;
    + }
    +
    + var nestedElem = findElementById(id, child);
    +
    + if (nestedElem)
    + return nestedElem;
    + }
    +
    + return null;
    +}
    +
    +/**
    +Print text to the page, for debugging purposes
    +*/
    +function dprintln(text)
    +{
    + debugTextElem.innerHTML += escapeHTML(text + '\n');
    +}
    +
    +/**
    +Set the text in the stats box
    +*/
    +function printStats(text)
    +{
    + statsTextElem.innerHTML = escapeHTML(text);
    +}
    +
    +/**
    +Clear a canvas
    +*/
    +function clearCanvas(canvas, canvasCtx)
    +{
    + canvasCtx.fillStyle = "#111111";
    + canvasCtx.fillRect(0, 0, canvas.width, canvas.height);
    +}
    +
    +/**
    +Update the state of the system
    +*/
    +function update()
    +{
    + // Update the camera movement
    + if (controls[CTRL_LEFT])
    + moveLeft();
    + if (controls[CTRL_RIGHT])
    + moveRight();
    + if (controls[CTRL_UP])
    + moveUp();
    + if (controls[CTRL_DOWN])
    + moveDown();
    +
    + // If running in fast mode, update the world at every update
    + if (world.fastMode === true)
    + {
    + genAlg.update();
    + world.update();
    + }
    +
    + // If the GUI needs to be redrawn
    + if (getTimeSecs() > lastRedraw + GUI_REDRAW_DELAY)
    + {
    + // If running in real-time, update only before rendering
    + if (world.fastMode === false)
    + {
    + genAlg.update();
    + world.update();
    + }
    +
    + // Render the world
    + world.render(canvas, canvasCtx, xCoord, yCoord, zoomLevel);
    +
    + // Compute the time spent running
    + var timeRunningSecs = Math.round(getTimeSecs() - startTimeSecs);
    +
    + // Compute the percentage of plants still available
    + var plantPercent = (100 * world.availPlants / world.numPlants).toFixed(1);
    +
    + // Print some statistics
    + printStats(
    + 'time running: ' + timeRunningSecs + 's\n' +
    + 'iterations/s: ' + itrsPerSec + '\n' +
    + '\n' +
    + 'ind. count : ' + genAlg.indCount + '\n' +
    + 'seed inds. : ' + genAlg.seedCount + '\n' +
    + 'itr. count : ' + world.itrCount + '\n' +
    + 'eaten plants: ' + world.eatenPlantCount + '\n' +
    + '\n' +
    + 'live agents : ' + world.population.length + '\n' +
    + 'avail. plants: ' + plantPercent + '%\n' +
    + //'built blocks : ' + world.builtBlocks.length + '\n' +
    + '\n' +
    + 'zoom level: ' + zoomLevel + '\n' +
    + 'camera x : ' + xCoord + '\n' +
    + 'camera y : ' + yCoord
    + );
    +
    + // Update the last redraw time
    + lastRedraw = getTimeSecs();
    + }
    +
    + // If the speed count is to be update
    + if (getTimeSecs() > speedCountStartTime + SPEED_COUNT_INTERV)
    + {
    + // Recompute the update rate
    + var itrCount = world.itrCount - speedCountStartItrs;
    + itrsPerSec = Math.round(itrCount / SPEED_COUNT_INTERV);
    + speedCountStartItrs = world.itrCount;
    + speedCountStartTime = getTimeSecs();
    + }
    +}
    +
    +/**
    +Augment the zoom level
    +*/
    +function zoomIn()
    +{
    + // Increment the zoom level if possible
    + if (zoomLevel < WORLD_ZOOM_MAX)
    + ++zoomLevel;
    +
    + // Enable the zoom out button
    + zoomOutButton.disabled = false;
    +
    + // If zooming in is no longer possible, disable the button
    + if (zoomLevel >= WORLD_ZOOM_MAX)
    + zoomInButton.disabled = true;
    +}
    +
    +/**
    +Reduce the zoom level
    +*/
    +function zoomOut()
    +{
    + // If we are at the minimum zoom level, stop
    + if (zoomLevel === WORLD_ZOOM_MIN)
    + return;
    +
    + // Decrement the zoom level
    + --zoomLevel;
    +
    + // Enable the zoom in button
    + zoomInButton.disabled = false;
    +
    + // If zooming out is no longer possible, disable the button
    + if (zoomLevel === WORLD_ZOOM_MIN)
    + zoomOutButton.disabled = true;
    +
    + // Obtain the sprite size for this zoom level
    + var spriteSize = WORLD_SPRITE_SIZES[zoomLevel];
    +
    + // Compute the coordinates at the corner of the map
    + var cornerX = world.gridWidth - canvas.width / spriteSize;
    + var cornerY = world.gridHeight - canvas.height / spriteSize;
    +
    + // Update the camera coordinates
    + xCoord = Math.max(0, Math.min(xCoord, cornerX));
    + yCoord = Math.max(0, Math.min(yCoord, cornerY));
    +}
    +
    +/**
    +Augment the world update rate
    +*/
    +function goFaster()
    +{
    + world.fastMode = true;
    +
    + realTimeButton.disabled = false;
    + fastModeButton.disabled = true;
    +}
    +
    +/**
    +Reduce the world update rate
    +*/
    +function goSlower()
    +{
    + world.fastMode = false;
    +
    + realTimeButton.disabled = true;
    + fastModeButton.disabled = false;
    +}
    +
    +/**
    +Move the camera left
    +*/
    +function moveLeft()
    +{
    + // compute the movement delta
    + var delta = WORLD_ZOOM_MAX - (zoomLevel - WORLD_ZOOM_MIN) + 1;
    +
    + // compute the updated coordinates
    + var newXCoord = xCoord - delta;
    +
    + // Update the coordinates
    + xCoord = Math.max(0, newXCoord);
    +}
    +
    +/**
    +Move the camera right
    +*/
    +function moveRight()
    +{
    + // compute the movement delta
    + var delta = WORLD_ZOOM_MAX - (zoomLevel - WORLD_ZOOM_MIN) + 1;
    +
    + // compute the updated coordinates
    + var newXCoord = xCoord + delta;
    +
    + // Obtain the sprite size for this zoom level
    + var spriteSize = WORLD_SPRITE_SIZES[zoomLevel];
    +
    + // Compute the coordinates at the corner of the map
    + var cornerX = Math.max(world.gridWidth - canvas.width / spriteSize, 0);
    +
    + // Update the coordinates
    + xCoord = Math.min(newXCoord, cornerX);
    +}
    +
    +/**
    +Move the camera up
    +*/
    +function moveUp()
    +{
    + // compute the movement delta
    + var delta = WORLD_ZOOM_MAX - (zoomLevel - WORLD_ZOOM_MIN) + 1;
    +
    + // compute the updated coordinates
    + var newYCoord = yCoord - delta;
    +
    + // Update the coordinates
    + yCoord = Math.max(0, newYCoord);
    +}
    +
    +/**
    +Move the camera down
    +*/
    +function moveDown()
    +{
    + // compute the movement delta
    + var delta = WORLD_ZOOM_MAX - (zoomLevel - WORLD_ZOOM_MIN) + 1;
    +
    + // compute the updated coordinates
    + var newYCoord = yCoord + delta;
    +
    + // Obtain the sprite size for this zoom level
    + var spriteSize = WORLD_SPRITE_SIZES[zoomLevel];
    +
    + // Compute the coordinates at the corner of the map
    + var cornerY = Math.max(world.gridHeight - canvas.height / spriteSize, 0);
    +
    + // Update the coordinates
    + yCoord = Math.min(newYCoord, cornerY);
    +}
    +
    View
    191 utility.js
    @@ -0,0 +1,191 @@
    +/*****************************************************************************
    +*
    +* Gradient: an Artificial Life Experiment
    +* Copyright (C) 2011 Maxime Chevalier-Boisvert
    +*
    +* This file is part of Gradient.
    +*
    +* Gradient 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 3 of the License, or
    +* (at your option) any later version.
    +*
    +* Gradient 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 Gradient. If not, see <http://www.gnu.org/licenses/>.
    +*
    +* For more information about this program, please e-mail the
    +* author, Maxime Chevalier-Boisvert at:
    +* maximechevalierb /at/ gmail /dot/ com
    +*
    +*****************************************************************************/
    +
    +//============================================================================
    +// Misc utility code
    +//============================================================================
    +
    +/**
    +Assert that a condition holds true
    +*/
    +function assert(condition, errorText)
    +{
    + if (!condition)
    + {
    + error(errorText);
    + }
    +}
    +
    +/**
    +Abort execution because a critical error occurred
    +*/
    +function error(errorText)
    +{
    + alert('ERROR: ' + errorText);
    +
    + throw errorText;
    +}
    +
    +/**
    +Test that a value is integer
    +*/
    +function isInt(val)
    +{
    + return (
    + Math.floor(val) === val
    + );
    +}
    +
    +/**
    +Test that a value is a nonnegative integer
    +*/
    +function isNonNegInt(val)
    +{
    + return (
    + isInt(val) &&
    + val >= 0
    + );
    +}
    +
    +/**
    +Test that a value is a strictly positive (nonzero) integer
    +*/
    +function isPosInt(val)
    +{
    + return (
    + isInt(val) &&
    + val > 0
    + );
    +}
    +
    +/**
    +Get the current time in seconds
    +*/
    +function getTimeSecs()
    +{
    + return (new Date()).getTime() / 1000;
    +}
    +
    +/**
    +Generate a random integer within [a, b]
    +*/
    +function randomInt(a, b)
    +{
    + assert (
    + isInt(a) && isInt(b) && a <= b,
    + 'invalid params to randomInt'
    + );
    +
    + var range = b - a;
    +
    + var rnd = a + Math.floor(Math.random() * (range + 1));
    +
    + return rnd;
    +}
    +
    +/**
    +Generate a random boolean
    +*/
    +function randomBool()
    +{
    + return (randomInt(0, 1) === 1);
    +}
    +
    +/**
    +Choose a random argument value uniformly randomly
    +*/
    +function randomChoice()
    +{
    + assert (
    + arguments.length > 0,
    + 'must supply at least one possible choice'
    + );
    +
    + var idx = randomInt(0, arguments.length - 1);
    +
    + return arguments[idx];
    +}
    +
    +/**
    +Generate a random floating-point number within [a, b]
    +*/
    +function randomFloat(a, b)
    +{
    + if (a === undefined)
    + a = 0;
    + if (b === undefined)
    + b = 1;
    +
    + assert (
    + a <= b,
    + 'invalid params to randomFloat'
    + );
    +
    + var range = b - a;
    +
    + var rnd = a + Math.random() * range;
    +
    + return rnd;
    +}
    +
    +/**
    +Generate a random value from a normal distribution
    +*/
    +function randomNorm(mean, variance)
    +{
    + // Declare variables for the points and radius
    + var x1, x2, w;
    +
    + // Repeat until suitable points are found
    + do
    + {
    + x1 = 2.0 * randomFloat() - 1.0;
    + x2 = 2.0 * randomFloat() - 1.0;
    + w = x1 * x1 + x2 * x2;
    + } while (w >= 1.0 || w == 0);
    +
    + // compute the multiplier
    + w = Math.sqrt((-2.0 * Math.log(w)) / w);
    +
    + // compute the gaussian-distributed value
    + var gaussian = x1 * w;
    +
    + // Shift the gaussian value according to the mean and variance
    + return (gaussian * variance) + mean;
    +}
    +
    +/**
    +Escape a string for valid HTML formatting
    +*/
    +function escapeHTML(str)
    +{
    + str = str.replace(/\n/g, '<br>');
    + str = str.replace(/ /g, '&nbsp;');
    + str = str.replace(/\t/g, '&nbsp;&nbsp;&nbsp;&nbsp;');
    +
    + return str;
    +}
    +
    View
    55 vector.js
    @@ -0,0 +1,55 @@
    +/*****************************************************************************
    +*
    +* Gradient: an Artificial Life Experiment
    +* Copyright (C) 2011 Maxime Chevalier-Boisvert
    +*
    +* This file is part of Gradient.
    +*
    +* Gradient 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 3 of the License, or
    +* (at your option) any later version.
    +*
    +* Gradient 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 Gradient. If not, see <http://www.gnu.org/licenses/>.
    +*
    +* For more information about this program, please e-mail the
    +* author, Maxime Chevalier-Boisvert at:
    +* maximechevalierb /at/ gmail /dot/ com
    +*
    +*****************************************************************************/
    +
    +//============================================================================
    +// 2D Vectors
    +//============================================================================
    +
    +/**
    +@class 2D vector
    +*/
    +function Vector2(x, y)
    +{
    + this.x = x;
    + this.y = y;
    +}
    +
    +/**
    +Add two vectors
    +*/
    +Vector2.add = function (v1, v2)
    +{
    + return new Vector2(v1.x + v2.x, v1.y + v2.y);
    +}
    +
    +/**
    +Multiply a vector by a scalar
    +*/
    +Vector2.scalarMul = function (v, s)
    +{
    + return new Vector2(v.x * s, v.y * s);
    +}
    +
    View
    1,146 world.js
    @@ -0,0 +1,1146 @@
    +/*****************************************************************************
    +*
    +* Gradient: an Artificial Life Experiment
    +* Copyright (C) 2011 Maxime Chevalier-Boisvert
    +*
    +* This file is part of Gradient.
    +*
    +* Gradient 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 3 of the License, or
    +* (at your option) any later version.
    +*
    +* Gradient 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 Gradient. If not, see <http://www.gnu.org/licenses/>.
    +*
    +* For more information about this program, please e-mail the
    +* author, Maxime Chevalier-Boisvert at:
    +* maximechevalierb /at/ gmail /dot/ com
    +*
    +*****************************************************************************/
    +
    +//============================================================================
    +// Virtual World
    +//============================================================================
    +
    +// World update duration
    +const WORLD_UPDATE_TIME_SLICE = 0.1;
    +
    +// Number of updates to perform between checks in fast mode
    +const WORLD_UPDATE_ITR_COUNT = 8;
    +
    +// Zoom level constants
    +const WORLD_ZOOM_MIN = 0;
    +const WORLD_ZOOM_MAX = 5;
    +
    +// Sprite size constants
    +const WORLD_SPRITE_SIZES = [2, 4, 8, 16, 32, 64];
    +
    +// Plant respawning delay
    +const PLANT_RESPAWN_DELAY = 3100;
    +
    +// Built block decay delay
    +const BLOCK_DECAY_DELAY = 15000;
    +
    +// World cell kinds
    +const CELL_EMPTY = 0;
    +const CELL_PLANT = 1;
    +const CELL_EATEN = 2;
    +const CELL_WATER = 3;
    +const CELL_MINE = 4;
    +const CELL_WALL = 5;
    +
    +/**
    +@class World cell class
    +*/
    +function Cell(cellType, agent)
    +{
    + // If the cell type is unspecified, make it empty
    + if (cellType === undefined)
    + cellType = CELL_EMPTY;
    +
    + // If the agent is undefined, make it null
    + if (agent === undefined)
    + agent = null;
    +
    + /**
    + Cell type
    + */
    + this.type = cellType;
    +
    + /**
    + Agent at this cell
    + */
    + this.agent = agent;
    +}
    +
    +/**
    +@class Eaten plant class
    +*/
    +function EatenPlant(x, y, time)
    +{
    + /**
    + Plant position
    + */
    + this.x = x;
    + this.y = y;
    +
    + /**
    + Time at which to respawn
    + */
    + this.respawnTime = time;
    +
    + assert (
    + isNonNegInt(this.x) && isNonNegInt(this.y),
    + 'invalid plant coordinates'
    + );
    +
    + assert (
    + isNonNegInt(this.respawnTime),
    + 'invalid plant respawn time'
    + );
    +}
    +
    +/**
    +@class Built block class
    +*/
    +function BuiltBlock(x, y, time)
    +{
    + /**
    + Plant position
    + */
    + this.x = x;
    + this.y = y;
    +
    + /**
    + Time at which to disappear
    + */
    + this.decayTime = time;
    +
    + assert (
    + isNonNegInt(this.x) && isNonNegInt(this.y),
    + 'invalid plant coordinates'
    + );
    +
    + assert (
    + isNonNegInt(this.decayTime),
    + 'invalid block decay time'
    + );
    +}
    +
    +/**
    +@class Represent a simulated world and its contents
    +*/
    +function World()
    +{
    + /**
    + World grid width
    + */
    + this.gridWidth = 0;
    +
    + /**
    + World grid height
    + */
    + this.gridHeight = 0;
    +
    + /**
    + Plants respawning flag
    + */
    + this.plantsRespawn = true;
    +
    + /**
    + Fast update mode flag
    + */
    + this.fastMode = false;
    +
    + /**
    + Total iteration count
    + */
    + this.itrCount = 0;
    +
    + /**
    + Last reset iteration
    + */
    + this.lastResetIt = 0;
    +
    + /**
    + World grid
    + */
    + this.grid = [];
    +
    + /**
    + Population
    + */
    + this.population = [];
    +
    + /**
    + Total number of plant cells
    + */
    + this.numPlants = 0;
    +
    + /**
    + Plants currently available to eat
    + */
    + this.availPlants = 0;
    +
    + /**
    + List of eaten plants
    + */
    + this.eatenPlants = [];
    +
    + /**
    + Total plants eaten count
    + */
    + this.eatenPlantCount = 0;
    +
    + /**
    + List of built blocks
    + */
    + this.builtBlocks = [];
    +
    + /**
    + Cache of sprites last used during rendering
    + */
    + this.spriteCache = [];
    +
    + /**
    + Number of images left to be loaded
    + */
    + this.imgsToLoad = 0;
    +
    + var that = this;
    + function loadImage(fileName)
    + {
    + that.imgsToLoad++;
    +
    + var img = new Image();
    + img.src = fileName;
    +
    + img.onload = function () { that.imgsToLoad--; }
    +
    + return img;
    + }
    +
    + // Load the sprite images
    + this.emptySprite = loadImage("images/sprites/grass2.png");
    + this.waterSprite = loadImage("images/sprites/water.png");
    + this.water2Sprite = loadImage("images/sprites/water2.png");
    + this.wallSprite = loadImage("images/sprites/rock.png");
    + this.plantSprite = loadImage("images/sprites/moss_green.png");
    + this.eatenSprite = loadImage("images/sprites/moss_dark.png");
    + this.mineSprite = loadImage("images/sprites/landmine.png");
    + this.antUSprite = loadImage("images/sprites/ant_up.png");
    + this.antDSprite = loadImage("images/sprites/ant_down.png");
    + this.antLSprite = loadImage("images/sprites/ant_left.png");
    + this.antRSprite = loadImage("images/sprites/ant_right.png");
    +}
    +
    +/**
    +Generate a random world
    +*/
    +World.prototype.generate = function (
    + width,
    + height,
    + plantsRespawn,
    + waterSeedProb,
    + plantSeedProb,
    + mineProb,
    + rowWallsMean,
    + rowWallsVar,
    + colWallsMean,
    + colWallsVar
    +)
    +{
    + // Set the default generation parameters
    + if (plantsRespawn === undefined)
    + plantsRespawn = false;
    + if (waterSeedProb === undefined)
    + waterSeedProb = 0.0012;
    + if (plantSeedProb === undefined)
    + plantSeedProb = 0.004;
    + if (mineProb === undefined)
    + mineProb = 0;
    + if (rowWallsMean === undefined)
    + rowWallsMean = 0;
    + if (rowWallsVar === undefined)
    + rowWallsVar = 0;
    + if (colWallsMean === undefined)
    + colWallsMean = 0;
    + if (colWallsVar === undefined)
    + colWallsVar = 0;
    +
    + // Ensure that the parameters are valid
    + assert (width > 0 && height > 0);
    +
    + // Store the grid width and height
    + this.gridWidth = width;
    + this.gridHeight = height;
    +
    + // Create a new world grid and fill it with empty cells
    + this.grid = new Array(width * height);
    + for (var i = 0; i < this.grid.length; ++i)
    + this.grid[i] = new Cell();
    +
    + // Store the plant respawning flag
    + this.plantsRespawn = plantsRespawn;
    +
    + // Clear the list of eaten plants
    + this.eatenPlants = [];
    +
    + // Reset all counters
    + this.reset();
    +
    + //*******************************
    + // Water generation
    + //*******************************
    +
    + // For each row of cells
    + for (var y = 0; y < height; ++y)
    + {
    + // For each column
    + for (var x = 0; x < width; ++x)
    + {
    + // With a given probability
    + if (randomFloat(0, 1) < waterSeedProb)
    + {
    + // Make this a water cell
    + this.setCell(x, y, new Cell(CELL_WATER));
    + }
    + }
    + }
    +
    + // For each pond generation pass
    + for (var i = 0; i < 23; ++i)
    + {
    + // For each row of cells
    + for (var y = 1; y < this.gridHeight - 1; ++y)
    + {
    + // For each column
    + for (var x = 1; x < this.gridWidth - 1; ++x)
    + {
    + // Count the number of water neighbors
    + var numWater = this.countNeighbors(x, y, CELL_WATER);
    +
    + // With a certain probability
    + if (randomFloat(0, 1) < 0.02 * numWater + (numWater? 1:0) * 0.004 * Math.exp(numWater))
    + {
    + // Make this a water cell
    + this.setCell(x, y, new Cell(CELL_WATER));
    + }
    + }
    + }
    + }
    +
    + //*******************************
    + // Wall generation
    + //*******************************
    +
    + // Choose a random number of row walls
    + var numRowWalls = Math.round(randomNorm(rowWallsMean, rowWallsVar));
    +
    + // Create a map for the row walls
    + var rowWallMap = new Array(this.gridHeight);
    +
    + // For each row wall to generate
    + for (var wallCount = 0; wallCount < numRowWalls;)
    + {
    + // Choose a random row
    + var y = randomInt(2, this.gridHeight - 3);
    +
    + // If another wall would be immediately adjacent, skip it
    + if (rowWallMap[y - 1] === true || rowWallMap[y + 1] === true)
    + continue;
    +
    + // compute the two endpoints
    + var x1 = randomInt(1, this.gridWidth - 2);
    + var x2 = randomInt(1, this.gridWidth - 2);
    +
    + // compute the length
    + var len = Math.abs(x1 - x2);
    +
    + // If the wall is too short or too long, skip it
    + if (len < 5 || len > this.gridWidth / 4)
    + continue;
    +
    + // For each column
    + for (var x = x1; x != x2 && x > 0 && x < this.gridWidth - 1; x += ((x2 - x1) > 0? 1:-1))
    + {
    + // If this cell is water, skip it
    + if (this.cellIsType(x, y, CELL_WATER) === true)
    + break;
    +
    + // Make this cell a wall
    + this.setCell(x, y, new Cell(CELL_WALL));
    + }
    +
    + // Increment the wall count
    + ++wallCount;
    +
    + // update the row wall map
    + rowWallMap[y] = true;
    + }
    +
    + // Choose a random number of column walls
    + var numColWalls = Math.round(randomNorm(colWallsMean, colWallsVar));
    +
    + // Create a map for the column walls
    + var colWallMap = new Array(this.gridWidth);
    +
    + // For each row wall to generate
    + for (var wallCount = 0; wallCount < numColWalls;)
    + {
    + // Choose a random column
    + var x = randomInt(2, this.gridWidth - 3);
    +
    + // If another wall would be immediately adjacent, skip it
    + if (colWallMap[x - 1] === true || colWallMap[x + 1] === true)
    + continue;
    +
    + // compute the two endpoints
    + var y1 = randomInt(1, this.gridHeight - 2);
    + var y2 = randomInt(1, this.gridHeight - 2);
    +
    + // compute the length
    + var len = Math.abs(y1 - y2);
    +
    + // If the wall is too short or too long, skip it
    + if (len < 5 || len > this.gridHeight / 4)
    + continue;
    +
    + // For each row
    + for (var y = y1; y != y2 && y > 0 && y < this.gridHeight; y += ((y2 - y1) > 0? 1:-1))
    + {
    + // If this cell is water or any neighbor is a wall cell, skip it
    + if (this.cellIsType(x, y, CELL_WATER) === true||
    + this.countNeighbors(x, y, CELL_WALL) > 1)
    + break;
    +
    + // Make this cell a wall
    + this.setCell(x, y, new Cell(CELL_WALL));
    + }
    +
    + // Increment the wall count
    + ++wallCount;
    +
    + // update the column wall map
    + colWallMap[x] = true;
    + }
    +
    + //*******************************
    + // Food generation
    + //*******************************
    +
    + // For each plant generation pass
    + for (var i = 0; i < 11; ++i)
    + {
    + // For each row of cells
    + for (var y = 1; y < this.gridHeight - 1; ++y)
    + {
    + // For each column
    + for (var x = 1; x < this.gridWidth - 1; ++x)
    + {
    + // If this cell is not empty, skip it
    + if (this.cellIsType(x, y, CELL_EMPTY) === false)
    + continue;
    +
    + // Count the number of water neighbors
    + var numWater = this.countNeighbors(x, y, CELL_WATER);
    +
    + // If there are any water neighbors, continue
    + if (numWater > 0)
    + continue;
    +
    + // Count the number of plant neighbors
    + var numPlant = this.countNeighbors(x, y, CELL_PLANT);
    +
    + // With a certain probability, if there are no plant neighbors
    + if (randomFloat(0, 1) < plantSeedProb && numPlant === 0)
    + {
    + // Make this a plant cell
    + this.setCell(x, y, new Cell(CELL_PLANT));
    + }
    +
    + // Otherwise, if there are plant neighbors
    + else if (randomFloat(0, 1) < 0.04 * numPlant)
    + {
    + // Make this a plant cell with the same color as the neighbors
    + this.setCell(x, y, new Cell(CELL_PLANT));
    + }
    + }
    + }
    + }
    +
    + // Count the number of plants in the world
    + this.numPlants = 0;
    + for (var i = 0; i < this.grid.length; ++i)
    + {
    + if (this.grid[i].type === CELL_PLANT)
    + this.numPlants++;
    + }
    +