Expressive JavaScript: The Electronic Life Project

Original author: Marijn Haverbeke
  • Transfer

Content




The question of whether cars can think is as pertinent as the question of whether submarines can sail.

Edsger Dijkstra, Threats to Computing Science


In project chapters, I will stop throwing you theory, and I will work with you on programs. The theory is indispensable in teaching programming, but it must be accompanied by reading and understanding non-trivial programs.

Our project is the construction of a virtual ecosystem, a small world inhabited by creatures that move and fight for survival.

Definition


To make the task feasible, we drastically simplify the concept of the world. Namely, the world will be a two-dimensional grid, where each entity occupies one cell. At each turn, the creatures will be able to perform some action.

Thus, we chop time and space into units of a fixed size: cells for space and moves for time. Of course, this is a rough and sloppy approximation. But our simulation should be entertaining, and not accurate, so we freely “cut corners”.

We can define the world using a plan - an array of strings that lays out the world grid using one character per cell.

var plan = ["############################",
            "#      #    #      o      ##",
            "#                          #",
            "#          #####           #",
            "##         #   #    ##     #",
            "###           ##     #     #",
            "#           ###      #     #",
            "#   ####                   #",
            "#   ##       o             #",
            "# o  #         o       ### #",
            "#    #                     #",
            "############################"];


The symbol “#” means walls and stones, “o” - a creature. Spaces are empty space.

A plan can be used to create an object of the world. He monitors the size and contents of the world. It has a toString method that converts the world into an output line (such as the plan on which it is based) so that we can observe what is happening inside it. The object of the world has a turn method, which allows all beings to make one move and update the state of the world in accordance with their actions.

Portray space


The grid modeling the world has width and height. Cells are defined by x and y coordinates. We use the simple Vector type (from the exercises in the previous chapter) to represent these coordinate pairs.

function Vector(x, y) {
  this.x = x;
  this.y = y;
}
Vector.prototype.plus = function(other) {
  return new Vector(this.x + other.x, this.y + other.y);
};


Then we need an object type that simulates the grid itself. A grid is part of the world, but we make a separate object out of it (which will be a property of a world object) so as not to complicate the world object. The world must load itself with things related to the world, and the grid with things related to the grid.

To store a grid of values, we have several options. You can use an array of string arrays, and use two-stage access to properties:

var grid = [["top left",    "top middle",    "top right"],
            ["bottom left", "bottom middle", "bottom right"]];
console.log(grid[1][2]);
// → bottom right


Or we can take one array, the size of width × height, and decide that the element (x, y) is at position x + (y × width).

var grid = ["top left",    "top middle",    "top right",
            "bottom left", "bottom middle", "bottom right"];
console.log(grid[2 + (1 * 3)]);
// → bottom right


Since access will be wrapped in the methods of the mesh object, the external code does not care which approach is chosen. I chose the second one because it is easier to create an array with it. When calling the Array constructor with one number as an argument, it creates a new empty array of the given length.

The following code declares a grid object with the main methods:

function Grid(width, height) {
  this.space = new Array(width * height);
  this.width = width;
  this.height = height;
}
Grid.prototype.isInside = function(vector) {
  return vector.x >= 0 && vector.x < this.width &&
         vector.y >= 0 && vector.y < this.height;
};
Grid.prototype.get = function(vector) {
  return this.space[vector.x + this.width * vector.y];
};
Grid.prototype.set = function(vector, value) {
  this.space[vector.x + this.width * vector.y] = value;
};


Elementary test:

var grid = new Grid(5, 5);
console.log(grid.get(new Vector(1, 1)));
// → undefined
grid.set(new Vector(1, 1), "X");
console.log(grid.get(new Vector(1, 1)));
// → X


Creature Programming Interface


Before we take up the constructor of the World World, we need to decide on the objects of the creatures that inhabit it. I mentioned that the world will ask the creatures what they want to do. It will work like this: every creature object has an act method, which, when called, returns an action. Action - an object of type property, which names the type of action that the creature wants to perform, for example, “move”. Action may contain additional information - such as the direction of movement.

The creatures are terribly shortsighted and see only the cells immediately adjacent to them. But this can come in handy when choosing actions. When the act method is called, it is given a view object that allows the creature to explore the surrounding area. We call eight neighboring cells their compass directions: “n” to the north, “ne” to the northeast, etc. Here's what object will be used to convert from the names of the directions to the coordinates offsets:

var directions = {
  "n":  new Vector( 0, -1),
  "ne": new Vector( 1, -1),
  "e":  new Vector( 1,  0),
  "se": new Vector( 1,  1),
  "s":  new Vector( 0,  1),
  "sw": new Vector(-1,  1),
  "w":  new Vector(-1,  0),
  "nw": new Vector(-1, -1)
};


The view object has a look method that takes direction and returns a character, for example, “#” if there is a wall, or a space if there is nothing there. The object also provides convenient find and findAll methods. Both take one of the characters representing things on the map as an argument. The first returns the direction in which this item can be found next to the creature, or null if there is no such item near. The second returns an array with all possible directions where such an object was found. For example, a creature to the left of the wall (in the west) will receive ["ne", "e", "se"] when calling findAll with the argument "#".

Here is a simple dumb creature that just walks until it crashes into an obstacle and then bounces in a random direction.

function randomElement(array) {
  return array[Math.floor(Math.random() * array.length)];
}
function BouncingCritter() {
  this.direction = randomElement(Object.keys(directions));
};
BouncingCritter.prototype.act = function(view) {
  if (view.look(this.direction) != " ")
    this.direction = view.find(" ") || "s";
  return {type: "move", direction: this.direction};
};


The helper function randomElement simply selects a random array element using Math.random and a bit of arithmetic to get a random index. We will continue to use randomness, since it is a useful thing in simulations.

The BouncingCritter constructor calls Object.keys. We saw this function in the previous chapter - it returns an array with all the property names of the object. Here she gets all the direction names from the directions object specified earlier.

The construction “|| The "s" ”in the act method is needed so that this.direction does not get null if the creature is huddled in a corner without free space around - for example, it is surrounded by other creatures.

World object


Now you can proceed to the world object World. The constructor accepts a plan (an array of strings representing the grid of the world) and a legend object. This is an object reporting what each of the map symbols means. It has a constructor for each character - except for a space that refers to null (representing empty space).

function elementFromChar(legend, ch) {
  if (ch == " ")
    return null;
  var element = new legend[ch]();
  element.originChar = ch;
  return element;
}
function World(map, legend) {
  var grid = new Grid(map[0].length, map.length);
  this.grid = grid;
  this.legend = legend;
  map.forEach(function(line, y) {
    for (var x = 0; x < line.length; x++)
      grid.set(new Vector(x, y),
               elementFromChar(legend, line[x]));
  });
}


In elementFromChar, we first create an instance of the desired type, finding the constructor of the symbol and applying new to it. Then we add the originChar property so that it is easy to find out from which symbol the element was originally created.

We will need this originChar property in the manufacture of the world toString method. The method constructs a map as a string from the current state of the world, passing a two-dimensional cycle through the cells of the grid.

function charFromElement(element) {
  if (element == null)
    return " ";
  else
    return element.originChar;
}
World.prototype.toString = function() {
  var output = "";
  for (var y = 0; y < this.grid.height; y++) {
    for (var x = 0; x < this.grid.width; x++) {
      var element = this.grid.get(new Vector(x, y));
      output += charFromElement(element);
    }
    output += "\n";
  }
  return output;
};


Wall wall is a simple object. Used to take up space and does not have an act method.

function Wall() {}


Checking the World object, creating an instance using the plan specified at the beginning of the chapter, and then calling its toString method, we get a line very similar to this plan.

var world = new World(plan, {"#": Wall, "o": BouncingCritter});
console.log(world.toString());
// → ############################
//   #      #    #      o      ##
//   #                          #
//   #          #####           #
//   ##         #   #    ##     #
//   ###           ##     #     #
//   #           ###      #     #
//   #   ####                   #
//   #   ##       o             #
//   # o  #         o       ### #
//   #    #                     #
//   ############################


this and its scope

In the World constructor, there is a call to forEach. I want to note that inside the function passed to forEach, we are no longer directly in the scope of the constructor. Each function call gets its own namespace, so this inside it no longer refers to the created object that this refers to outside the function. In general, if the function is not called as a method, this will refer to the global object.

So we cannot write this.grid to access the grid from within the loop. Instead, the external function creates a local grid variable through which the internal function accesses the grid.

This is a blunder in JavaScript design. Fortunately, the next version has a solution to this problem. In the meantime, there are workarounds. Usually write

var self = this


and after that they work with the self variable.

Another solution is to use the bind method, which allows you to bind to a specific this object.

var test = {
  prop: 10,
  addPropTo: function(array) {
    return array.map(function(elt) {
      return this.prop + elt;
    }.bind(this));
  }
};
console.log(test.addPropTo([5]));
// → [15]


The function passed to map is the result of the call binding, and therefore its this is bound to the first argument passed to bind, that is, the this variable of the external function (which contains the test object).

Most standard higher-order standard methods for arrays, such as forEach and map, accept an optional second argument, which can also be used to pass this when calling an iterative function. You could write the previous example a little easier:

var test = {
  prop: 10,
  addPropTo: function(array) {
    return array.map(function(elt) {
      return this.prop + elt;
    }, this); // ← без bind
  }
};
console.log(test.addPropTo([5]));
// → [15]


This only works with those higher order functions that have such a context parameter. If not, you have to use the other approaches mentioned.

In our own higher-order function, we can enable context parameter support by using the call method to call the function passed as an argument. For example, here's a forEach method for our Grid type that calls a given function for each lattice element that is not null or undefined:

Grid.prototype.forEach = function(f, context) {
  for (var y = 0; y < this.height; y++) {
    for (var x = 0; x < this.width; x++) {
      var value = this.space[x + y * this.width];
      if (value != null)
        f.call(context, value, new Vector(x, y));
    }
  }
};


Revive the world


The next step is to create a turn method (step) for a world object that allows creatures to act. It will traverse the grid with the forEach method, and look for objects that have an act method. Having found the object, turn calls this method, getting the action object and produces this action, if it is valid. So far we only understand the “move” action.

There is one possible problem. Can you see which one? If we allow the creatures to move as we sort through them, they can move to a cell that we have not yet processed, and then we will allow them to move again when the turn reaches this cell. Thus, we need to store an array of creatures that have already taken their step, and ignore them when re-passing.

World.prototype.turn = function() {
  var acted = [];
  this.grid.forEach(function(critter, vector) {
    if (critter.act && acted.indexOf(critter) == -1) {
      acted.push(critter);
      this.letAct(critter, vector);
    }
  }, this);
};


The second parameter of the forEach method is used to access the correct this variable in the internal function. The letAct method contains logic that allows creatures to move.

World.prototype.letAct = function(critter, vector) {
  var action = critter.act(new View(this, vector));
  if (action && action.type == "move") {
    var dest = this.checkDestination(action, vector);
    if (dest && this.grid.get(dest) == null) {
      this.grid.set(vector, null);
      this.grid.set(dest, critter);
    }
  }
};
World.prototype.checkDestination = function(action, vector) {
  if (directions.hasOwnProperty(action.direction)) {
    var dest = vector.plus(directions[action.direction]);
    if (this.grid.isInside(dest))
      return dest;
  }
};


First, we simply ask the creature to act, passing it a view object that knows about the world and the current position of the creature in the world (we will soon set the View). The act method returns an action.

If the type of action is not “move,” it is ignored. If it is “move”, and if it has a direction property that refers to a valid direction, and if the cell in this direction is empty (null), we assign the cell where the creature was just null and save the creature in the destination cell.

Note that letAct takes care to ignore invalid input. It does not assume by default that a direction is valid, or that a type property makes sense. This kind of defensive programming makes sense in some situations. This is mainly done to check the input coming from sources that you do not control (user input or reading a file), but it is also useful for isolating subsystems from each other. In our case, its purpose is to take into account that creatures can be programmed inaccurately. They do not need to check whether their intentions make sense. They simply ask for the possibility of action, and the world itself decides whether to allow it.

These two methods do not belong to the external interface of the world object. They are parts of internal implementation. Some languages ​​provide ways to declare certain methods and properties "private", and throw an error when trying to use them outside the object. JavaScript does not provide this, so you will have to rely on other ways to report what is part of the object's interface. Sometimes it helps to use a property naming scheme to distinguish between internal and external, for example, with special prefixes to internal names, such as underscores (_). This will facilitate the identification of accidental use of properties that are not part of the interface.

And the missing part, type View, looks like this:

function View(world, vector) {
  this.world = world;
  this.vector = vector;
}
View.prototype.look = function(dir) {
  var target = this.vector.plus(directions[dir]);
  if (this.world.grid.isInside(target))
    return charFromElement(this.world.grid.get(target));
  else
    return "#";
};
View.prototype.findAll = function(ch) {
  var found = [];
  for (var dir in directions)
    if (this.look(dir) == ch)
      found.push(dir);
  return found;
};
View.prototype.find = function(ch) {
  var found = this.findAll(ch);
  if (found.length == 0) return null;
  return randomElement(found);
};


The look method calculates the coordinates we are trying to look at. If they are inside the grid, it receives a symbol corresponding to the element located there. For the coordinates outside the grid, look simply pretends to be a wall there - if you set the world without surrounding walls, creatures will not be able to get off the edge.

It moves


We have created a copy of the world object. Now that all the necessary methods are ready, we should be able to make it move.

for (var i = 0; i < 5; i++) {
  world.turn();
  console.log(world.toString());
}
// → … пять ходов


Just displaying five copies of the map is not a very convenient way to observe the world. Therefore, in the sandbox for the book (or in the files for downloading ) there is a magic function animateWorld, which shows the world as an animation on the screen, doing three steps per second, until you press the stop.

animateWorld(world);
// → … заработало!


The implementation of animateWorld will remain a mystery, but after reading the following chapters of the book discussing the integration of JavaScript into browsers, it will no longer look so mysterious.

More life forms


One of the interesting situations happening in the world happens when two creatures bounce off of each other. Can you come up with another interesting form of interaction?

I came up with a creature moving along the wall. It holds its left hand (paw, tentacle, whatever) on the wall and moves along it. This, as it turned out, is not so easy to program.

We will need to calculate using directions in space. Since the directions are given by a set of lines, we need to set our own dirPlus operation to calculate relative directions. dirPlus (“n”, 1) means clockwise 45 degrees north, resulting in “ne”. dirPlus ("s", -2) means counterclockwise rotation from the south, that is, to the east.

var directionNames = Object.keys(directions);
function dirPlus(dir, n) {
  var index = directionNames.indexOf(dir);
  return directionNames[(index + n + 8) % 8];
}
function WallFollower() {
  this.dir = "s";
}
WallFollower.prototype.act = function(view) {
  var start = this.dir;
  if (view.look(dirPlus(this.dir, -3)) != " ")
    start = this.dir = dirPlus(this.dir, -2);
  while (view.look(this.dir) != " ") {
    this.dir = dirPlus(this.dir, 1);
    if (this.dir == start) break;
  }
  return {type: "move", direction: this.dir};
};


The act method only scans the creature’s environment, starting on the left side and clockwise, until it finds an empty cell. Then it moves towards this cell.

Complicating the situation is that the creature can be far from the walls in empty space - either bypassing another creature, or initially being there. If we leave the described algorithm, the unfortunate creature will turn left each turn and run in a circle.

So there is another check through if, that the scan must be started if the creature has just passed an obstacle. That is, if the space on the back and left is not empty. Otherwise, we start scanning ahead, so in empty space it will go straight.

And finally, there is a check on the coincidence of this.dir and start on each passage of the cycle so that it does not go in cycles when the creature has nowhere to go from behind walls or other creatures, and it cannot find an empty cell.

This small world shows creatures moving along walls:

animateWorld(new World(
  ["############",
   "#     #    #",
   "#   ~    ~ #",
   "#  ##      #",
   "#  ##  o####",
   "#          #",
   "############"],
  {"#": Wall,
   "~": WallFollower,
   "o": BouncingCritter}
));


More life situation


To make life in our little world more interesting, we add the concepts of food and reproduction. Each living creature has a new property, energy, which decreases when actions are taken and increases when eating food. When a creature has enough energy, it can multiply, creating a new creature of the same type. To simplify the calculations, our creatures reproduce on their own.

If the creatures just move and eat each other, the world will soon succumb to increasing entropy, energy will end in it and it will turn into a desert. To prevent this ending (or delay), we add plants to it. They do not move. They simply engage in photosynthesis and grow (produce energy), and multiply.

For this to work, we need a world with a different letAct method. We could just replace the World prototype method, but I'm used to our simulation of creatures walking on the walls and would not want to destroy it.

One solution is to use inheritance. We are creating a new constructor, LifelikeWorld, whose prototype is based on the World prototype, but overrides the letAct method. The new letAct transfers the work of committing actions to different functions stored in the actionTypes object.

function LifelikeWorld(map, legend) {
  World.call(this, map, legend);
}
LifelikeWorld.prototype = Object.create(World.prototype);
var actionTypes = Object.create(null);
LifelikeWorld.prototype.letAct = function(critter, vector) {
  var action = critter.act(new View(this, vector));
  var handled = action &&
    action.type in actionTypes &&
    actionTypes[action.type].call(this, critter,
                                  vector, action);
  if (!handled) {
    critter.energy -= 0.2;
    if (critter.energy <= 0)
      this.grid.set(vector, null);
  }
};


The new letAct method checks to see if at least some action has been passed, then whether there is a function that processes it, and in the end, whether this function returns true, indicating that the action completed successfully. Note the use of call to give functions access to the world object through this.

If the action for some reason does not work, the default action for the creature is wait. He loses 0.2 units of energy, and when his energy level drops below zero, he dies and disappears from the grid.

Action handlers


The simplest action is growth, it is used by plants. When an action object of type {type: "grow"} is returned, the following handler method will be called:

actionTypes.grow = function(critter) {
  critter.energy += 0.5;
  return true;
};


Growth is always successful and adds half a unit to the energy level of the plant.

The movement is more complicated.

actionTypes.move = function(critter, vector, action) {
  var dest = this.checkDestination(action, vector);
  if (dest == null ||
      critter.energy <= 1 ||
      this.grid.get(dest) != null)
    return false;
  critter.energy -= 1;
  this.grid.set(vector, null);
  this.grid.set(dest, critter);
  return true;
};


This action first checks, using the checkDestination method previously declared, whether the action provides a valid direction. If not, or the area is not empty in that direction, or the creature lacks energy - move returns false, indicating that the action did not take place. Otherwise, he moves the creature and subtracts energy.

In addition to movement, creatures can eat.

actionTypes.eat = function(critter, vector, action) {
  var dest = this.checkDestination(action, vector);
  var atDest = dest != null && this.grid.get(dest);
  if (!atDest || atDest.energy == null)
    return false;
  critter.energy += atDest.energy;
  this.grid.set(dest, null);
  return true;
};


Eating another creature also requires the provision of a valid directional cell. In this case, the cell must contain something with energy, for example, a creature (but not a wall, they cannot be eaten). If this is confirmed, the energy of the eaten goes to the eater, and the victim is removed from the grid.

Finally, we allow creatures to multiply.

actionTypes.reproduce = function(critter, vector, action) {
  var baby = elementFromChar(this.legend,
                             critter.originChar);
  var dest = this.checkDestination(action, vector);
  if (dest == null ||
      critter.energy <= 2 * baby.energy ||
      this.grid.get(dest) != null)
    return false;
  critter.energy -= 2 * baby.energy;
  this.grid.set(dest, baby);
  return true;
};


Reproduction takes up twice as much energy as a newborn has. Therefore, we create a hypothetical offspring using elementFromChar on the original creature. Once we have a offspring, we can find out its energy level and check whether the parent has enough energy to give birth to him. We also need a valid directional cell.

If everything is in order, the offspring is placed on the grid (and ceases to be hypothetical), and energy is wasted.

Inhabit the world


Now we have the basis for simulating creatures that are more like real ones. We could put creatures from the old into the new world, but they would just die, because they do not have the energy property. Let's make new ones. First we write a plant, which, in fact, is a fairly simple form of life.

function Plant() {
  this.energy = 3 + Math.random() * 4;
}
Plant.prototype.act = function(context) {
  if (this.energy > 15) {
    var space = context.find(" ");
    if (space)
      return {type: "reproduce", direction: space};
  }
  if (this.energy < 20)
    return {type: "grow"};
};


Plants start with a random energy level of 3 to 7 so that they do not multiply all in one go. When a plant reaches an energy of 15, and there is an empty cell nearby - it multiplies into it. If it cannot multiply, then it simply grows until it reaches energy 20.

Now we define a plant eater.

function PlantEater() {
  this.energy = 20;
}
PlantEater.prototype.act = function(context) {
  var space = context.find(" ");
  if (this.energy > 60 && space)
    return {type: "reproduce", direction: space};
  var plant = context.find("*");
  if (plant)
    return {type: "eat", direction: plant};
  if (space)
    return {type: "move", direction: space};
};


For plants, we will use the symbol * - that which the creature will seek in search of food.

Breathe life


And now we have enough elements for a new world. Imagine the following map as a grassy valley, where a herd of herbivores grazes, several boulders lie and lush vegetation blooms.

var valley = new LifelikeWorld(
  ["############################",
   "#####                 ######",
   "##   ***                **##",
   "#   *##**         **  O  *##",
   "#    ***     O    ##**    *#",
   "#       O         ##***    #",
   "#                 ##**     #",
   "#   O       #*             #",
   "#*          #**       O    #",
   "#***        ##**    O    **#",
   "##****     ###***       *###",
   "############################"],
  {"#": Wall,
   "O": PlantEater,
   "*": Plant}
);


Most of the time, plants multiply and grow, but then an abundance of food leads to an explosive growth in the population of herbivores that eat up almost all of the vegetation, which leads to mass extinction from starvation. Sometimes the ecosystem is restored and a new cycle begins. In other cases, some species dies. If herbivores, then the whole space is filled with plants. If the plants - the remaining creatures die of hunger, and the valley turns into an uninhabited wasteland. Oh, the cruelty of nature ...

Exercises


Artificial idiot

It is sad when the inhabitants of our world die out in a few minutes. To deal with this, we can try to create a smarter plant eater.

Our herbivores have several obvious problems. Firstly, they are greedy - they eat every plant they find until they completely destroy all the vegetation. Secondly, their random movement (remember that the view.find method returns a random direction) makes them hang out inefficiently and die of hunger if there are no plants nearby. And finally, they multiply too fast, which makes the cycle from abundance to hunger too fast.

Write a new type of creature that is trying to cope with one or more problems and replace it with the old PlantEater type in the valley world. Follow them. Make the necessary adjustments.

// Ваш код
function SmartPlantEater() {}
animateWorld(new LifelikeWorld(
  ["############################",
   "#####                 ######",
   "##   ***                **##",
   "#   *##**         **  O  *##",
   "#    ***     O    ##**    *#",
   "#       O         ##***    #",
   "#                 ##**     #",
   "#   O       #*             #",
   "#*          #**       O    #",
   "#***        ##**    O    **#",
   "##****     ###***       *###",
   "############################"],
  {"#": Wall,
   "O": SmartPlantEater,
   "*": Plant}
));


Predators

In any serious ecosystem, the food chain is longer than one link. Write another creature that survives by eating herbivores. You will notice that stability is even harder to achieve when cycles occur at different levels. Try to find a strategy that will allow the ecosystem to run smoothly for a while.

Enlarging the world can help with this. Then, local demographic explosions or population decline are less likely to completely destroy the population, and there is room for a relatively large population of prey that can support a small population of predators.

// Ваш код тут
function Tiger() {}
animateWorld(new LifelikeWorld(
  ["####################################################",
   "#                 ####         ****              ###",
   "#   *  @  ##                 ########       OO    ##",
   "#   *    ##        O O                 ****       *#",
   "#       ##*                        ##########     *#",
   "#      ##***  *         ****                     **#",
   "#* **  #  *  ***      #########                  **#",
   "#* **  #      *               #   *              **#",
   "#     ##              #   O   #  ***          ######",
   "#*            @       #       #   *        O  #    #",
   "#*                    #  ######                 ** #",
   "###          ****          ***                  ** #",
   "#       O                        @         O       #",
   "#   *     ##  ##  ##  ##               ###      *  #",
   "#   **         #              *       #####  O     #",
   "##  **  O   O  #  #    ***  ***        ###      ** #",
   "###               #   *****                    ****#",
   "####################################################"],
  {"#": Wall,
   "@": Tiger,
   "O": SmartPlantEater, // из предыдущего упражнения
   "*": Plant}
));

Also popular now: