Gradient A-life Modifications that speed it up ~5x http://www.cs.mcgill.ca/~mcheva/gradient/gradient.html

agents.js

/*****************************************************************************
* 
* 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

/*****************************************************************************
* 
* 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

/*****************************************************************************
* 
* 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

/*****************************************************************************
* 
* 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

/*****************************************************************************
* 
* 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

/*****************************************************************************
* 
* 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++;
	}

    // Initialize the number of available plants
    this.availPlants = this.numPlants;

	//*******************************
	// Border wall generation
	//*******************************
	
	// For each column
	for (var x = 0; x < this.gridWidth; ++x)
	{
		// Make the top border a wall
		this.setCell(x, 0, new Cell(CELL_WALL));
		
		// Make the bottom border a wall
		this.setCell(x, this.gridHeight - 1, new Cell(CELL_WALL));
	}
	
	// For each row
	for (var y = 0; y < this.gridHeight; ++y)
	{
		// Make the left border a wall
		this.setCell(0, y, new Cell(CELL_WALL));
		
		// Make the right border a wall
		this.setCell(this.gridWidth - 1, y, new Cell(CELL_WALL));
	}
}

/**
Reset the world to its post-creation state
*/
World.prototype.reset = function ()
{
	// Store the iteration count
	this.lastResetIt = this.itrCount; 

	// Respawn all plants
	this.respawnPlants(true);
		
	// Remove all built blocks
	this.decayBlocks(true);

	// Clear the current population
	this.population = [];

	// Remove any ants from the world grid
    for (var i = 0; i < this.grid.length; ++i)
        this.grid[i].agent = null;

    for (var i = 0; i < this.grid.length; ++i)
    {
        assert (
            this.grid[i].agent === null,
            'non-null agent pointer after world reset'
        );
    }
}

/**
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 = [];

	// For each eaten plant
    for (var i = 0; i < this.eatenPlants.length; ++i)
	{
        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))
        {
            eatenPlants.push(plant);
            continue;
        }
			
		// Make the corresponding cell a new plant
		this.getCell(plant.x, plant.y).type = CELL_PLANT;
		
        // Increment the available plant count
        this.availPlants++;

        assert (
            this.availPlants <= this.numPlants,
            'invalid available plant count'
        );
	}

    // Update the eaten plants array
    this.eatenPlants = eatenPlants;
}

/**
Decay built blocks
*/
World.prototype.decayBlocks = function (decayAll)
{
    // By default, do not decay all blocks
    if (decayAll === undefined)
        decayAll = false;

    // Remaining built blocks array
    var builtBlocks = [];

	// For each eaten plant
    for (var i = 0; i < this.builtBlocks.length; ++i)
	{
        var block = this.builtBlocks[i];

		// If it is not time for this block to be removed, skip it
		if (block.decayTime > this.itrCount && !(decayAll === true))
        {
            builtBlocks.push(block);
            continue;
        }
			
		// Make the corresponding cell empty
		this.getCell(block.x, block.y).type = CELL_EMPTY;
	}

    // Update the built blocks array
    this.builtBlocks = builtBlocks;
}

/**
Update the world state
*/
World.prototype.update = function ()
{
	// If fast updating mode is enabled
	if (this.fastMode === true)
	{
		// Get the time at which we start this update
		var startTime = getTimeSecs();
		
		// Until the update time slice is elapsed
		while (getTimeSecs() < startTime + WORLD_UPDATE_TIME_SLICE)
		{
			// If all agents are dead, yield early
			if (this.population.length === 0)
			    return;	
			
			// Perform a small number of update iterations
			for (var i = 0; i < WORLD_UPDATE_ITR_COUNT; ++i)
				this.iterate();		
		}
	}
	else
	{
		// Iterate only once
		this.iterate();
	}
}

/**
Perform one world iteration
*/
World.prototype.iterate = function ()
{
	// For all agents in the population
    for (var i = 0; i < this.population.length; ++i)
	{
        var agent = this.population[i];

		// Update the agent state
		agent.update();
		
		// If the agent is no longer alive
		if (agent.isAlive() === false)
		{
			// Get the agent's position
			var pos = agent.position;
		
			// Nullify the agent pointer of its cell
			this.getCell(pos.x, pos.y).agent = null;
			
			// Remove the agent from the population
			this.population.splice(i, 1);

            // Move to the next agent in the population
            --i;
		}
	}

	// If eaten plants are to be respawned, place them back in the world
	if (this.plantsRespawn === true)
		this.respawnPlants(false);

    // Decay the built blocks
    this.decayBlocks(false);

	// Increment the iteration count
	this.itrCount++;
}

/**
Render the world
*/
World.prototype.render = function (canvas, canvasCtx, xPos, yPos, zoomLevel)
{
    assert (
        isNonNegInt(zoomLevel),
        'invalid zoom level'
    );

    // If there are images left to load
    if (this.imgsToLoad > 0)
    {
        clearCanvas(canvas, canvasCtx);
        canvasCtx.fillStyle = "White";
        canvasCtx.fillText("Loading sprites...", 10, 10);
        return;
    }

	// Ensure that the arguments are valids
	assert (
        xPos < this.gridWidth &&
        yPos < this.gridHeight &&
        zoomLevel >= WORLD_ZOOM_MIN &&
        zoomLevel <= WORLD_ZOOM_MAX
    );

	// Get the sprite size for this zoom level
	var spriteSize = WORLD_SPRITE_SIZES[zoomLevel - WORLD_ZOOM_MIN];
	
    // Compute the number of rows and columns of sprites to render
    var numRows = Math.ceil(canvas.height / spriteSize);
    var numCols = Math.ceil(canvas.width / spriteSize);

    // Compute the number of sprites to render
    var numSprites = numRows * numCols;

    // If the sprite cache size does not match, reset it
    if (this.spriteCache.length !== numSprites)
    {
        clearCanvas(canvas, canvasCtx);
        this.spriteCache = new Array(numSprites);
    }

    // Choose the animated water sprite
    var waterAnim = (this.itrCount % 4 <= 1);
    var waterSprite = waterAnim? this.waterSprite:this.water2Sprite;

	// Initialize the grid and frame y positions
	var gridY = yPos;
    var frameY = 0;

	// For each row
	for (var rowIdx = 0; rowIdx < numRows && gridY < this.gridHeight; ++rowIdx)
	{	
		// Reset the grid and framey position
		var gridX = xPos;
        var frameX = 0;
	
		// For each column
		for (var colIdx = 0; colIdx < numCols && gridX < this.gridWidth; ++colIdx)
		{
			// Get a reference to this cell
			var cell = this.getCell(gridX, gridY);
		
			// Declare a reference to the sprite to draw
			var sprite;
		
			// If this cell contains an ant
			if (cell.agent !== null)
			{
				// Switch on the ant direction
				switch (cell.agent.direction)
				{
					// Set the sprite according to the direction
					case AGENT_DIR_UP   : sprite = this.antUSprite; break;
					case AGENT_DIR_DOWN : sprite = this.antDSprite; break;
					case AGENT_DIR_LEFT : sprite = this.antLSprite; break;
					case AGENT_DIR_RIGHT: sprite = this.antRSprite; break;
					
					// Invalid agent direction
					default:
                    error('invalid agent direction (' + cell.agent.direction + ')');
				}
			}
			else
			{	
				// Switch on the cell types
				switch (cell.type)
				{
					// Empty cells
					case CELL_EMPTY: sprite = this.emptySprite; break;
					
					// Water cells
					case CELL_WATER: sprite = waterSprite; break;
					
					// Wall cells
					case CELL_WALL: sprite = this.wallSprite; break;
					
					// Alive and eaten plants
					case CELL_PLANT: sprite = this.plantSprite; break;
					case CELL_EATEN: sprite = this.eatenSprite; break;
					
					// Mine cell
					case CELL_MINE: sprite = this.mineSprite; break;
					
					// Invalid cell type
					default:
                    error('invalid cell type');
				}
			}

            /*
			assert (
                sprite instanceof Image,
                'invalid sprite'
            );

            assert (
                isNonNegInt(frameX) && isNonNegInt(frameY),
                'invalid frame coordinates'
            );

            assert (
                isPosInt(spriteSize),
                'invalid sprite size'
            );
            */

            // Get the cached sprite for this frame position
            var cachedSprite = this.spriteCache[numCols * rowIdx + colIdx];

            // If the sprite does not match the cached entry
            if (sprite !== cachedSprite)
            {
                // Draw the scaled sprite at the current frame position
                canvasCtx.drawImage(sprite, frameX, frameY, spriteSize, spriteSize);

                // Update the cached sprite
                this.spriteCache[numCols * rowIdx + colIdx] = sprite;
            }
					
			// Update the grid and frame position
            gridX += 1;
			frameX += spriteSize;
		}
		
		// Update the grid and frame position
        gridY += 1;
		frameY += spriteSize;
	}
}

/**
Place an agent at a specific location on the map
*/
World.prototype.placeAgent = function (agent, x, y)
{
	// Ensure that the arguments are valid
	assert (
        x < this.gridWidth && 
        y < this.gridHeight &&
        agent !== null,
        'invalid arguments to placeAgent'
    );
	
	// If this cell is not empty, placement failed
	if (this.cellIsType(x, y, CELL_EMPTY) === false || 
        this.getCell(x, y).agent !== null)
		return false;

	// Set the ant position
	agent.position = new Vector2(x, y);
		
	// Set the agent pointer for this cell
	this.getCell(x, y).agent = agent;

	// Add the ant to the population
	this.population.push(agent);

	// Placement successful
	return true;
}

/**
Place an agent on the map at random coordinates
*/
World.prototype.placeAgentRnd = function (agent)
{
    assert (
        agent !== null,
        'invalid parameters to placeAgentRnd'
    );

    // Get the initial population size
    var initPopSize = this.population.length;

	// Try to place the ant up to 512 times
	for (var i = 0; i < 512; ++i)
	{
		// Choose random coordinates in the world
	    var x = randomInt(0, this.gridWidth - 1);
		var y = randomInt(0, this.gridHeight - 1);

		// If the agent can be placed at these coordinates			
		if (this.placeAgent(agent, x, y) === true)
		{
            assert (
                this.population.length === initPopSize + 1,
                'agent not added to population'
            );

            assert (
                world.getCell(agent.position.x, agent.position.y).agent === agent,
                'agent pointer not valid after adding agent'
            );

			// Placement successful
			return true;
		}			
	}

    assert (
        this.population.length === initPopSize,
        'agent not added but population size changed'
    );
	
	// Placement failed
	return false;
}

/**
Place an agent on the map near some coordinates
*/
World.prototype.placeAgentNear = function (agent, x, y)
{
    assert (
        agent !== null,
        'invalid parameters to placeAgentNear'
    );

    // Get the initial population size
    var initPopSize = this.population.length;

	// Try to place the ant up to 512 times
	for (var i = 0; i < 512; ++i)
	{
		// Choose random coordinates in the world
	    var nearX = x + randomInt(-12, 12);
		var nearY = y + randomInt(-12, 12);

        // If the coordinates are outside of the map, try again
        if (nearX < 0 || 
            nearY < 0 ||
            nearX >= this.gridWidth || 
            nearY >= this.gridHeight)
            continue;

		// If the agent can be placed at these coordinates			
		if (this.placeAgent(agent, nearX, nearY) === true)
		{
            assert (
                this.population.length === initPopSize + 1,
                'agent not added to population'
            );

            assert (
                world.getCell(agent.position.x, agent.position.y).agent === agent,
                'agent pointer not valid after adding agent'
            );

			// Placement successful
			return true;
		}			
	}

    assert (
        this.population.length === initPopSize,
        'agent not added but population size changed'
    );
	
	// Placement failed
	return false;
}

/**
Move an ant to new coordinates
*/
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);
	
	// Ensure that the ant pointer is valid
	assert (
        orig.agent === agent,
        'invalid agent pointer'
    );
	
	// If the destination cell is a wall or water, deny the movement
	if (dest.type === CELL_WALL || dest.type === CELL_WATER)
		return false;

	// If there is already an ant at the destination, deny the movement
	if (dest.agent !== null)
		return false;
	
	// Update the pointers to perform the movement
	orig.agent = null;
	dest.agent = agent;
	
	// Update the agent position
    agent.position = new Vector2(x, y);

	// Move successful
	return true;
}

/**
Eat a plant at the given coordinates
*/
World.prototype.eatPlant = function (x, y)
{
	// Ensure that the parameters are valid
	assert (x < this.gridWidth && y < this.gridHeight);
	
	// If this cell is not an available plant, stop
	if (this.cellIsType(x, y, CELL_PLANT) === false)
		return false;
	
	// Make this cell an eaten plant
	this.getCell(x, y).type = CELL_EATEN;

	// Add the plant to the list of eaten plants
    this.eatenPlants.push(new EatenPlant(x, y, this.itrCount + PLANT_RESPAWN_DELAY));
	
    // Decrement the available plant count
    this.availPlants--;

    // Increment the eaten plant count
    this.eatenPlantCount++;

	// Plant successfully eaten
	return true;
}

/**
Build a block at the given coordinates
*/
World.prototype.buildBlock = function (x, y)
{
	// Ensure that the parameters are valid
	assert (x < this.gridWidth && y < this.gridHeight);
	
	// If this cell is not empty, stop
	if (this.cellIsType(x, y, CELL_EMPTY) === false ||
        this.getCell(x,y).agent !== null)
		return false;
	
	// Make this cell a wall block
	this.getCell(x, y).type = CELL_WALL;

	// Add the block to the list of built blocks
    this.builtBlocks.push(new BuiltBlock(x, y, this.itrCount + BLOCK_DECAY_DELAY));

	// Plant successfully eaten
	return true;
}

/**
Test if a world cell is empty
*/
World.prototype.cellIsEmpty = function (x, y)
{
	// Perform the test
	return (this.getCell(x, y).type === CELL_EMPTY);
}

/**
Test the type of a cell
*/
World.prototype.cellIsType = function (x, y, type)
{
	// Perform the test
	return (this.getCell(x, y).type === type);
}

/**
Count cell neighbors of a given type
*/
World.prototype.countNeighbors = function (x, y, type)
{
	// Count the neighbor cells of the given type
    var count = 
		(this.cellIsType(x - 1, y - 1, type)? 1:0) +
		(this.cellIsType(x    , y - 1, type)? 1:0) +
		(this.cellIsType(x + 1, y - 1, type)? 1:0) +
		(this.cellIsType(x - 1, y    , type)? 1:0) +
		(this.cellIsType(x + 1, y    , type)? 1:0) +
		(this.cellIsType(x - 1, y + 1, type)? 1:0) +
		(this.cellIsType(x    , y + 1, type)? 1:0) +
		(this.cellIsType(x + 1, y + 1, type)? 1:0);	
	
	// Return the count
	return count;
}

/**
Set a given grid cell
*/
World.prototype.setCell = function (x, y, cell)
{
	// Ensure that the coordinates are valid
	assert (
        x >= 0 && y >= 0 &&
        x < this.gridWidth && y < this.gridHeight,
        'invalid coordinates in setCell'
    );
	
    // Ensure that the cell is valid
    assert (cell instanceof Cell);

	// Set the cell reference
	this.grid[y * this.gridWidth + x] = cell;
}

/**
Get a given grid cell
*/
World.prototype.getCell = function (x, y)
{
	// Ensure that the coordinates are valid
	assert (
        x >= 0 && y >= 0 &&
        x < this.gridWidth && y < this.gridHeight,
        'invalid coordinates in getCell'
    );
	
	// Return a reference to the cell
	return this.grid[y * this.gridWidth + x];
}