Last active

Embed URL

HTTPS clone URL

SSH clone URL

You can clone with HTTPS or SSH.

Download Gist
rmmh revised this gist . 5 changed files with 90 additions and 151 deletions. View gist @ b832c5c
agents.js
175 
@@ -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;
+}
\ No newline at end of file
gradient.js
9 
@@ -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;
}
}
utility.js
5 
@@ -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
*/
vector.js
12 
@@ -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);
-}
-
+}
\ No newline at end of file
world.js
40 
@@ -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);
rmmh created this gist . View gist @ e5ecf50
agents.js
741 
@@ -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;
+}
+
genalg.js
158 
@@ -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);
+}
+
gradient.js
433 
@@ -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);
+}
+
utility.js
191 
@@ -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;
+}
+
vector.js
55 
@@ -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);
+}
+
world.js
1,146 
@@ -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);
+