Learning to Fly: Let's simulate evolution in Rust! (pt 4)

This post is part of the learning-to-fly series:

  1. The Domain
  2. The Neural Network
  3. The Genetic Algorithm
  4. The User Interface

This is the last part of the Learning to Fly series in which we're coding a simulation of evolution using neural network and genetic algorithm:

In today's, final episode:

Sexy Polygons
ISO-Certified ASCII Diagrams
------------
| \...%....|
|   \......|
|    @>....|
|      \...|
|        \.|
------------
Cool Numbers

Now that we have implemented neural network and genetic algorithm, what awaits is the most delightful part: modelling the ecosystem and displaying them dancing triangles on our screens!

I'm obliged say that at this point we're basically on a runner's high, so if you considered the previous three parts even remotely interesting, then going through this one will feel like eating Nutella for the first time in your life.

content warning: this article contains traces of javascript

Plan

We've got struct NeuralNetwork and struct GeneticAlgorithm — but what about struct Eye or struct World? After all, our birds have to have eyes and a place to live!

So that's what we'll be doing today; we'll implement all those functions that'll determine what a bird sees or how a bird moves. We'll also — at last! — create a user interface that'll allow us to see beyond dry numbers; it's about time we engage that visual cortex of ours better!

I'm not a great salesman, but lemme give it a shot — in a marketing gabble:

we'll see our code in action (!), in real-time (!!), in a web browser (!!!)

If you're into diagrams, what we're aiming for is:

green tick = already implemented, blue dot = will be done today

As always, next to coding, we'll also investigate what's exactly happening underneath all the layers of abstractions we're given — if you're not into that, feel free to skip those yellow boxes.

Ready? Off we go!

Prerequisites

As a reminder, we're using Rust 1.53.0 — to avoid unpleasant unpleasentaries, don't forget to either execute:

$ rustup default nightly-2021-03-25

... or create a file next to Cargo.toml called rust-toolchain that says:

rust-toolchain
nightly-2021-03-25

In addition, for a fearless WebAssembly experience, we'll need two other tools:

Before continuing, please install those tools according to the system you're using.

Hello, WebAssembly World! (the Rust part)

Let's begin by creating a new crate — as in the diagram, it will be responsible for interacting with our frontend application:

$ cd libs
$ cargo new simulation-wasm --lib --name lib-simulation-wasm

# (this crate's name doesn't have to contain `wasm` - it's just a
# convention of mine, so that the crate's purpose is explicit)

To make our crate WebAssembly-aware, there are two things we have to add to its manifest:

  1. We have to set crate-type to cdylib:

    libs/simulation-wasm/Cargo.toml
    [package]
    # ...
    
    [lib]
    crate-type = ["cdylib"]
    
  2. We have to include wasm-bindgen in our dependencies:

    libs/simulation-wasm/Cargo.toml
    # ...
    
    [dependencies]
    wasm-bindgen = "0.2"
    

When it comes to adjustments, that's all — now it's Rust-time!

Since creating the simulation will take some time, and it'd be nice to see something working as soon as possible, I say we begin by creating a function that we'll be able to invoke from JavaScript right away — you know, just to ensure that this "WebAssembly" thing isn't just a hoax:

libs/simulation-wasm/src/lib.rs
pub fn whos_that_dog() -> String {
    "Mister Peanutbutter".into()
}

If we were building a regular crate to publish on crates.io, that'd be all — but for WebAssembly, there's one more thing we have to add — #[wasm_bindgen]:

libs/simulation-wasm/src/lib.rs
use wasm_bindgen::prelude::*;

#[wasm_bindgen]
pub fn whos_that_dog() -> String {
    "Mister Peanutbutter".into()
}

To build a WebAssembly crate, we'll use that wasm-pack tool we've just installed:

$ cd simulation-wasm
$ wasm-pack build

The difference between plain cargo and wasm-pack is that the latter not only compiles the code, but also generates a lot of handy JavaScript files that otherwise we'd have to write by hand — we can find them all inside a newly-created directory called pkg:

$ tree pkg
pkg
├── lib_simulation_wasm_bg.js
├── lib_simulation_wasm_bg.wasm
├── lib_simulation_wasm_bg.wasm.d.ts
├── lib_simulation_wasm.d.ts
├── lib_simulation_wasm.js
└── package.json

To ground ourselves, let's take a brief look at what we've got:

Phew, that's a lot of information for one fn() -> String that we still haven't seen working — but that's only because I wanted to give you an introduction as to "why wasm-pack generates so many files" and "why no cargo build"; later we won't be inspecting those artifacts again.

So, now that our crate is compiled, <deep-breath/>,

how do we run it?

Hello, WebAssembly World! (the JavaScript part)

Frontend time!

To start our frontend application, let's go back to the project's root directory (next to our top-level Cargo.toml):

$ cd ../..

Setting up a frontend requires a bit of boilerplate too — luckily, this time we can use npm init to copy-paste the WebAssembly frontend template project for us:

$ npm init wasm-app www

You should now see a directory called www with a handful of files:

$ tree www
www
├── bootstrap.js
├── index.html
├── index.js
├── LICENSE-APACHE
├── LICENSE-MIT
├── package.json
├── package-lock.json
├── README.md
└── webpack.config.js

... let's briefly go through them.

Knowing your enemy

Le point d'entrée, similar to Rust's main.rs, here is index.html:

www/index.html
<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title>Hello wasm-pack!</title>
  </head>

  <body>
    <script src="./bootstrap.js"></script>
  </body>
</html>

A quick primer on HTML:

Overall, an HTML document describes a tree representation of the web page:

html
├── head
│   ├── meta
│   └── title
└── body
    └── script

... which browser analyzes, trying to make something nice out of it.

Each tag has a certain meaning:

Armed with all this knowledge, we can see that our page doesn't actually do that much — the most important thing is that it loads bootstrap.js:

www/bootstrap.js
import("./index.js")
  .catch(e => console.error("Error importing `index.js`:", e));

import is like Rust's use or extern crate. Contrary to Rust, in JavaScript import can be used as a statement, meaning that it returns a value; in pseudo-Rust, what happens above is:

(mod "./index.js")
    .await
    .map_err(|err| {
        eprintln!("Error importing ...", err);
    });

We can see that this code loads index.js, so let's take a look there:

www/index.js
import * as wasm from "hello-wasm-pack";
//                     ^-------------^
//                      defined in package.json

wasm.greet();

This import is a bit different in that it resembles extern crate more:

extern crate hello_wasm_pack as wasm;

wasm::greet();

When it comes to the application's code itself, that's all.

We can also spot one more file, called webpack.config.js — while we won't have to touch it, it won't hurt to take a look either:

www/webpack.config.js
const CopyWebpackPlugin = require("copy-webpack-plugin");
const path = require('path');

module.exports = {
  entry: "./bootstrap.js",
  output: {
    path: path.resolve(__dirname, "dist"),
    filename: "bootstrap.js",
  },
  mode: "development",
  plugins: [
    new CopyWebpackPlugin(['index.html'])
  ],
};

This file contains configuration for webpack, which is…​ kinda like Cargo, but for JavaScript 😅

What To Do After You Know Your Enemy

Having exchanged pleasantries with the filesystem, let's get back to the business:

  1. Currently npm doesn't know about lib-simulation-wasm — let's fix it:

    www/package.json
    {
      /* ... */
      "devDependencies": {
        "lib-simulation-wasm": "file:../libs/simulation-wasm/pkg",
        /* ... */
      }
    }
    
  2. After that, we have to let npm know about that change:

    $ cd www
    $ npm install
    
  3. Now it's time for index.js:

    www/index.js
    import * as sim from "lib-simulation-wasm";
    
    alert("Who's that dog? " + sim.whos_that_dog() + "!");
    
  4. With everything ready, we can now launch our application — this is basically cargo run:

    $ npm run start
    
    ...
    ℹ 「wds」: Project is running at http://localhost:8080/
    ...
    

When you now open this link in your browser, you'll be greeted with a peppy, springy & spry:

yay 🎉 yay

Hello, WebAssembly World! (the summary part)

So…​ what is all this?

Granted, displaying an alert message doesn't exactly qualify us for Da Nobel Prize (unless i'm mistaken in which case please let me know urgently thanks) — but our point was to get something running quickly, and we did get something running pretty quickly.

In the next section, we'll lay the foundations for our simulation — just enough to have something to send to JavaScript.

Hello, Simulation!

As before, to keep the boundaries clean & tidy, let's start by creating a new crate:

$ cd ../libs
$ cargo new simulation --lib --name lib-simulation

This crate will contain our simulation engine:

libs/simulation/src/lib.rs
pub struct Simulation;

Now, to avoid conjuring a design out of thin air, let's recall our drawing from before:

What do we see there? Hmm, well — certainly a world:

libs/simulation/src/lib.rs
pub struct Simulation {
    world: World,
}

#[derive(Debug)]
pub struct World;

... which contains some animals (birds!) and foods (rich in protein & fiber!):

libs/simulation/src/lib.rs
/* ... */

#[derive(Debug)]
pub struct World {
    animals: Vec<Animal>,
    foods: Vec<Food>,
}

#[derive(Debug)]
pub struct Animal;

#[derive(Debug)]
pub struct Food;

... which are located at some coordinates:

libs/simulation/src/lib.rs
/* ... */

#[derive(Debug)]
pub struct Animal {
    position: ?,
}

#[derive(Debug)]
pub struct Food {
    position: ?,
}

Our world is two-dimensional, which sets us at:

libs/simulation/src/lib.rs
/* ... */

#[derive(Debug)]
pub struct Animal {
    position: Point2,
}

#[derive(Debug)]
pub struct Food {
    position: Point2,
}

#[derive(Debug)]
pub struct Point2 {
    x: f32,
    y: f32,
}

Moreover, animals are of certain rotati…​

wait — did you hear that?

oh no

who's that?

oh no

🚨 it's the not-invented-here police 🚨

So far we've been writing a lot of code by hand — you know, that genetic algorithm and neural network, to name a few.

At least now, when it comes to a few mathematical data structures, I'd like to avoid reinventing the wheel — in part because there's barely anything educational in writing:

#[derive(Copy, Clone, Debug)]
pub struct Point2 {
    x: f32,
    y: f32,
}

impl Point2 {
    pub fn new(...) -> Self {
        /* ... */
    }

    /* ... */
}

impl Add<Point2> for Point2 {
    /* ... */
}

impl Sub<Point2> for Point2 {
    /* ... */
}

impl Mul<Point2> for f32 {
    /* ... */
}

impl Mul<f32> for Point2 {
    /* ... */
}

#[cfg(test)]
mod tests {
    /* ... */
}

... and in part because I'd like to introduce you to a crate that I love: nalgebra!

Quoting their documentation:

nalgebra is a linear algebra library written for Rust targeting:

  • General-purpose linear algebra (still lacks a lot of features…)

  • Real-time computer graphics.

  • Real-time computer physics.

In other words: math for the people, done right; and it plays nice with WebAssembly.

nalgebra provides a variety of different tools: from simple functions such as clamp, through somewhat complicated structures such as quaternions, to our beloved Point2.

Since it's just a crate, installing it boils down to editing the manifest:

libs/simulation/Cargo.toml
# ...

[dependencies]
nalgebra = "0.26"

... and then our code from a moment ago becomes:

libs/simulation/src/lib.rs
use nalgebra as na;
// --------- ^^
// | This kind of import - one that uses `as` - is called an alias.
// | You'd say that we're aliasing `nalgebra` as `na`.
// ---

/* ... */

#[derive(Debug)]
pub struct Animal {
    position: na::Point2<f32>,
}

#[derive(Debug)]
pub struct Food {
    position: na::Point2<f32>,
}

Where were we? Ah, right — animals are of certain rotation and speed:

libs/simulation/src/lib.rs
/* ... */

#[derive(Debug)]
pub struct Animal {
    position: na::Point2<f32>,
    rotation: na::Rotation2<f32>,
    speed: f32,
}

/* ... */

Now that we have a few models, it'd be nice if we could somehow construct them, so:

libs/simulation/Cargo.toml
# ...

[dependencies]
nalgebra = "0.26"
rand = "0.8"

... and while we're here, let's enable nalgebra's support for rand — it'll come handy in a moment:

libs/simulation/Cargo.toml
# ...

[dependencies]
nalgebra = { version = "0.26", features = ["rand-no-std"] }
rand = "0.8"

We'll start with a few rudimentary constructors that just randomize everything:

libs/simulation/src/lib.rs
use nalgebra as na;
use rand::{Rng, RngCore};

/* ... */

impl Simulation {
    pub fn random(rng: &mut dyn RngCore) -> Self {
        Self {
            world: World::random(rng),
        }
    }
}

impl World {
    pub fn random(rng: &mut dyn RngCore) -> Self {
        let animals = (0..40)
            .map(|_| Animal::random(rng))
            .collect();

        let foods = (0..60)
            .map(|_| Food::random(rng))
            .collect();

        // ^ Our algorithm allows for animals and foods to overlap, so
        // | it's hardly ideal - but good enough for our purposes.
        // |
        // | A more complex solution could be based off of e.g.
        // | Poisson disk sampling:
        // |
        // | https://en.wikipedia.org/wiki/Supersampling
        // ---

        Self { animals, foods }
    }
}

impl Animal {
    pub fn random(rng: &mut dyn RngCore) -> Self {
        Self {
            position: rng.gen(),
            // ------ ^-------^
            // | If not for `rand-no-std`, we'd have to do awkward
            // | `na::Point2::new(rng.gen(), rng.gen())` instead
            // ---

            rotation: rng.gen(),
            speed: 0.002,
        }
    }
}

impl Food {
    pub fn random(rng: &mut dyn RngCore) -> Self {
        Self {
            position: rng.gen(),
        }
    }
}

A getter is a function that allows to access object's state — a few of them will come useful:

libs/simulation/src/lib.rs
/* ... */

impl Simulation {
    /* ... */

    pub fn world(&self) -> &World {
        &self.world
    }
}

impl World {
    /* ... */

    pub fn animals(&self) -> &[Animal] {
        &self.animals
    }

    pub fn foods(&self) -> &[Food] {
        &self.foods
    }
}

impl Animal {
    /* ... */

    pub fn position(&self) -> na::Point2<f32> {
        // ------------------ ^
        // | No need to return a reference, because na::Point2 is Copy.
        // |
        // | (meaning: it's so small that cloning it is cheaper than
        // | messing with references.)
        // |
        // | Of course you don't have to memorize which types are Copy
        // | and which aren't - if you accidentally return a reference
        // | to a type that's Copy, rust-clippy will point it out and
        // | suggest a change :-)
        // ---

        self.position
    }

    pub fn rotation(&self) -> na::Rotation2<f32> {
        self.rotation
    }
}

impl Food {
    /* ... */

    pub fn position(&self) -> na::Point2<f32> {
        self.position
    }
}

Nice?

Nice.

There's a lot of code still missing, but at this point we've got enough to get ✨ something ✨ displayed on the screen via JavaScript.

All About That JS

Now, you might be wondering:

If we want to invoke this code from JavaScript, shouldn't we have #[wasm_bindgen] all over the place?

... to which I'll reply:

Excellent question! <high-fives himself/>

Ok, let's go back to lib-simulation-wasm — we have to make it aware of rand and lib-simulation:

libs/simulation-wasm/Cargo.toml
# ...

[dependencies]
rand = "0.8"
wasm-bindgen = "0.2"

lib-simulation = { path = "../simulation" }
                        # ^ path relative to _this_ Cargo.toml

Now inside lib-simulation-wasm we can refer to lib_simulation:

libs/simulation-wasm/src/lib.rs
use lib_simulation as sim;

... and implement a WebAssembly-aware wrapper (also known as proxy):

libs/simulation-wasm/src/lib.rs
use lib_simulation as sim;
use rand::prelude::*;
use wasm_bindgen::prelude::*;

#[wasm_bindgen]
pub struct Simulation {
    rng: ThreadRng,
    sim: sim::Simulation,
}

#[wasm_bindgen]
impl Simulation {
    #[wasm_bindgen(constructor)]
    pub fn new() -> Self {
        let mut rng = thread_rng();
        let sim = sim::Simulation::random(&mut rng);

        Self { rng, sim }
    }
}

As for baby steps, this looks good — let's try compiling it; surely nothing can fail just yet!

$ wasm-pack build
[INFO]: Checking for the Wasm target...
[INFO]: Compiling to Wasm...

   Compiling getrandom v0.2.2

   error: target is not supported, for more information see:
          https://docs.rs/getrandom/#unsupported-targets
--> /home/pwy/.cargo/registry/src/...
3:9
    |
213 | /         compile_error!("target is not supported, for more information see: \\
214 | |                         https://docs.rs/getrandom/#unsupported-targets");
    | |_________________________________________________________________________^

error[E0433]: failed to resolve: use of undeclared crate or module `imp`
   --> /home/pwy/.cargo/registry/src/...
5:5
    |
235 |     imp::getrandom_inner(dest)
    |     ^^^ use of undeclared crate or module `imp`

ayy, ayy

Being honest, this error took me by surprise — fortunately, the linked page describes what's going on quite well: rand internally depends on getrandom, which does support WebAssembly inside a web browser, but only when asked explicitly:

libs/simulation-wasm/Cargo.toml
# ...

[dependencies]
# ...

getrandom = { version = "0.2", features = ["js"] }

Let's try rebuilding now:

$ wasm-pack build
[INFO]: Checking for the Wasm target...
[INFO]: Compiling to Wasm...

warning: field is never read: `rng`
    ...

warning: field is never read: `sim`
    ...

warning: 2 warnings emitted

    Finished release [optimized] target(s) in 0.01s

[WARN]: origin crate has no README
[INFO]: Installing wasm-bindgen...
[INFO]: Optimizing wasm binaries with `wasm-opt`...
[INFO]: Optional fields missing from Cargo.toml: 'description',
        'repository', and 'license'. These are not necessary, but
         recommended
[INFO]: :-) Done in 0.63s
[INFO]: :-) Your wasm pkg is ready to publish at /home/pwy/Projects/...

On the JavaScript's side, we can now do:

www/index.js
import * as sim from "lib-simulation-wasm";

const simulation = new sim.Simulation();
// --------------- ^-^
// | For all practical purposes, this is a fancy syntax for Rust's:
// | `Simulation::new()`
// ---

Great, we've got the simulation engine up and running!

However it's a pretty quiet engine, that one, because currently it just randomizes some animals and foods, and goes quiet. To make it fun, let's propagate more data into JavaScript.

To do that, we'll need a few more models - they'll be kinda copy-pasted from lib-simulation, but with WebAssembly in mind:

libs/simulation-wasm/src/lib.rs
/* ... */

#[wasm_bindgen]
pub struct Simulation {
    /* ... */
}

#[wasm_bindgen]
#[derive(Clone, Debug)]
pub struct World {
    pub animals: Vec<Animal>,
}

#[wasm_bindgen]
#[derive(Clone, Debug)]
pub struct Animal {
    pub x: f32,
    pub y: f32,
}

// ^ This model is smaller than `lib_simulation::Animal` - that's
// | because a bird's position is all we need on the JavaScript's
// | side at the moment; there's no need to map rest of the fields.

/* ... */

... and two conversion methods:

libs/simulation-wasm/src/lib.rs
/* ... */

#[wasm_bindgen]
impl Simulation {
    /* ... */
}

impl From<&sim::World> for World {
    fn from(world: &sim::World) -> Self {
        let animals = world
            .animals()
            .iter()
            .map(Animal::from)
            .collect();

        Self { animals }
    }
}

impl From<&sim::Animal> for Animal {
    fn from(animal: &sim::Animal) -> Self {
        Self {
            x: animal.position().x,
            y: animal.position().y,
        }
    }
}

With all that in our editor, we can now add:

libs/simulation-wasm/src/lib.rs
/* ... */

#[wasm_bindgen]
impl Simulation {
    /* ... */

    pub fn world(&self) -> World {
        World::from(self.sim.world())
    }
}

/* ... */

... aaaand

oh my

heart starts to

beat faster

as i execute

$ wasm-pack build

aaaaand

oh no 😢

error[E0277]: the trait bound `Box<[Animal]>: IntoWasmAbi` is not
              satisfied
 --> libs/simulation-wasm/src/lib.rs
  |
3 | #[wasm_bindgen]
  | ^^^^^^^^^^^^^^^ the trait `IntoWasmAbi` is not implemented for
  |                 `Box<[Animal]>`

Ah, we know this message: it's because wasm-pack doesn't support vectors of custom types!

Let's roll back and analyze what happened — wasm-pack gave up here:

libs/simulation-wasm/src/lib.rs
#[wasm_bindgen]
#[derive(Clone, Debug)]
pub struct World {
    pub animals: Vec<Animal>,
    //           ^---------^
}

... if we can't rely on wasm-pack here, is there some other solution we could use? oh my — yes!

Serde Be My Guide

Meet Serde:

Serde is a framework for serializing and deserializing Rust data structures efficiently and generically.

Put another way: Serde takes a struct Foo { } and transforms it into (or from) JSON, YAML, or any other format you'd like (and there are a lot of them!).

If you hadn't had the opportunity to use Serde yet, here's a demo (unrelated to our simulation):

use serde::Serialize;

#[derive(Serialize)]
struct User {
    name: &'static str,
    friends: Vec<&'static str>,
}

fn main() {
    let user = User {
        name: "Patryk",
        friends: vec![
            "Chinchilla named Flora",
            "Oak named Bartek",
        ],
    };

    println!(
        "JSON:\\n{}\\n",
        serde_json::to_string_pretty(&user).unwrap(),
    );

    println!(
        "YAML:\\n{}",
        serde_yaml::to_string(&user).unwrap(),
    );
}

Installing Serde and making it compatible with wasm-bindgen is as easy as:

libs/simulation-wasm/Cargo.toml
# ...

[dependencies]
serde = { version = "1.0", features = ["derive"] }
# ------------------------------------- ^----^
# | Enables the `#[derive(Serialize)]` and `#[derive(Deserialize)]`
# | macros.
# |
# | Without this feature-switch, we'd have to write `impl Serialize` by
# | hand, I guess, which ain't no fun.
# ---

wasm-bindgen = { version = "0.2", features = ["serde-serialize"] }
# -------------------------------------------- ^-------------^
# | Enables `JsValue::from_serde()` that you'll see in a moment.
# ---

# ...

Since we don't want for wasm-bindgen to serialize our two models anymore, let's drop their #[wasm_bindgen]:

libs/simulation-wasm/src/lib.rs
/* ... */


#[derive(Clone, Debug)]
pub struct World {
    pub animals: Vec<Animal>,
}


#[derive(Clone, Debug)]
pub struct Animal {
    pub x: f32,
    pub y: f32,
}

/* ... */

... make them serializable by Serde:

libs/simulation-wasm/src/lib.rs
use serde::Serialize;

/* ... */

#[derive(Clone, Debug, Serialize)]
pub struct World {
    pub animals: Vec<Animal>,
}

#[derive(Clone, Debug, Serialize)]
pub struct Animal {
    pub x: f32,
    pub y: f32,
}

/* ... */

... and adjust Simulation::world():

libs/simulation-wasm/src/lib.rs
/* ... */

#[wasm_bindgen]
impl Simulation {
    /* ... */

    pub fn world(&self) -> JsValue {
        let world = World::from(self.sim.world());
        JsValue::from_serde(&world).unwrap()
    }
}

/* ... */

Question time: I'll take one from the audience.

What happened? Can't wasm-pack do it on its own? Would you rather hug a horse-sized duck or 100 duck-sized horses?

  1. What happened is that instead of letting wasm-pack serialize our models using its own serialization algorithm, we've forced them to be serialized into JSON — via JsValue.

    If not for Serde, wasm-pack would use a custom, binary format that's more compact…​ had it only supported vectors of custom types, that is.

  2. My guess is that while wasm-pack could opt for Serde by default, it's essentially a trade-off: JSON is more versatile, but its output tends to be longer than what a binary format can achieve, so it makes sense for wasm-pack to use the smaller format by default.

  3. I'd definitely hug a horse-sized duck - what a sublime creature!

Let's rebuild our Rust code (remember to run this command inside libs/simulation-wasm):

$ wasm-pack build
[INFO]: Checking for the Wasm target...
[INFO]: Compiling to Wasm...

warning: field is never read: `rng`
    ...

warning: 1 warning emitted

    Finished release [optimized] target(s) in 0.02s

...

K, nice.

So, in essence, what we've created is a function that returns a JSON:

{
  "animals": [
    { "x": 0.2, "y": 0.1 },
    { "x": 0.3, "y": 0.7 }
  ]
}

... which can be then easily parsed by the web browser:

www/index.js
import * as sim from "lib-simulation-wasm";

const simulation = new sim.Simulation();
const world = simulation.world();
// --------------------- ^---^
// | Parsing already happens inside this automatically-generated
// | function - we don't have to do anything more in here.
// ---

All this should work…​ in theory; but how can we be sure our world contains any meaningful data? By using our own eyes!

Most browsers expose a thing called developer console (also known as developer tools), which you should be able to access by pressing F12:

(Safari users might require an extra hoop.)

What can we do with this console? We can print stuff to it:

www/index.js
/* ... */

console.log(world);

(I assume npm run start is still working in the background — if it's not, remember to re-launch it.)

Nice; now that we know the positions of animals, it means we can draw them!

Hello, Graphics!

Drawing stuff in HTML + JavaScript is relatively painless - we'll use a thing called <canvas>:

www/index.html
<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title>Hello wasm-pack!</title>
  </head>

  <body>
    <canvas id="viewport"></canvas>
    <script src="./bootstrap.js"></script>
  </body>
</html>

Our canvas has an attribute called id — this attribute is used to name tags, so that they can be easily found from inside JavaScript:

www/index.js
/* ... */

const viewport = document.getElementById('viewport');
// ------------- ^------^
// | `document` is a global object that allows to access and modify
// | current page (e.g. create or remove stuff from it).
// ---

If you want to take a moment to digest what's happening, feel free to console.log(viewport); and click through its properties - there's a lot of them!

To display stuff on <canvas>, we have to request for a specific drawing mode (think: 2D vs 3D):

www/index.js
/* ... */

const ctxt = viewport.getContext('2d');

So far, so good!

There are many methods and properties we can invoke on ctxt — let's start by investigating fillStyle and fillRect():

www/index.js
/* ... */

// ---
// | Determines color of the upcoming shape.
// - v-------v
ctxt.fillStyle = 'rgb(255, 0, 0)';
// ------------------ ^-^ -^ -^
// | Each of those three parameters is a number from range 0 up to 255:
// |
// | rgb(0, 0, 0) = black
// |
// | rgb(255, 0, 0) = red
// | rgb(0, 255, 0) = green
// | rgb(0, 0, 255) = blue
// |
// | rgb(255, 255, 0) = yellow
// | rgb(0, 255, 255) = cyan
// | rgb(255, 0, 255) = magenta
// |
// | rgb(128, 128, 128) = gray
// | rgb(255, 255, 255) = white
// ---

ctxt.fillRect(10, 10, 100, 50);
// ---------- X   Y   W    H
// | Draws rectangle filled with color determined by `fillStyle`.
// |
// | X = position on the X axis (left-to-right)
// | Y = position on the Y axis (top-to-bottom)
// | W = width
// | X = height
// |
// | (unit: pixels)
// ---

Launching this code should make our <canvas> print a red rectangle:

Ah, Mondrian would be so proud — I tell you: we're going places!

It’s My Data

Now that we know how to draw rectangles, let's bring our data back into the picture:

www/index.js
import * as sim from "lib-simulation-wasm";

const simulation = new sim.Simulation();
const viewport = document.getElementById('viewport');
const ctxt = viewport.getContext('2d');

ctxt.fillStyle = 'rgb(0, 0, 0)';

for (const animal of simulation.world().animals) {
    ctxt.fillRect(animal.x, animal.y, 15, 15);
}

... and:

Well, ain't that a bummer — what happened? Let's investigate our data once again:

www/index.js
/* ... */

console.log(simulation.world().animals);

Ah, positions of our animals belong to range <0.0, 1.0>, while <canvas> expects coordinates in the unit of a pixel — we can fix this by scaling the numbers while rendering:

www/index.js
/* ... */

const viewport = document.getElementById('viewport');
const viewportWidth = viewport.width;
const viewportHeight = viewport.height;

/* ... */

for (const animal of simulation.world().animals) {
    ctxt.fillRect(
        animal.x * viewportWidth,
        animal.y * viewportHeight,
        15,
        15,
    );
}

... which gets us:

So…​ would you believe it, someone told me that squares are not fashionable anymore!

Apparently ▼ triangles ▲ are all the rage, so let's try drawing one.

Somewhat unluckily, JavaScript doesn't provide any method for printing triangles, requiring us to draw them manually vertex-by-vertex instead.

To get a grip of how it works, let's start with a hard-coded example:

www/index.js
/* ... */

// Starts drawing a polygon
ctxt.beginPath();

// Moves cursor at x=50, y=0
ctxt.moveTo(50, 0);

// Draws a line from (50,0) to (100,50) and moves cursor there
// (this gets us the right side of our triangle)
ctxt.lineTo(100, 50);

// Draws a line from (100,50) to (0,50) and moves cursor there
// (this gets us the bottom side of our triangle)
ctxt.lineTo(0, 50);

// Draws a line from (0,50) to (50,0) and moves cursor there
// (this gets us the left side of our triangle)
ctxt.lineTo(50, 0);

// Fills our triangle with a black color
//
// (there's also `ctxt.stroke();`, which would render only our triangle's
// outline instead.)
ctxt.fillStyle = 'rgb(0, 0, 0)';
ctxt.fill();

... aaaand, what a beauty!

Since drawing a triangle requires a few steps, to make it easier to use, let's make it a function:

www/index.js
/* ... */

function drawTriangle(ctxt, x, y, size) {
    ctxt.beginPath();
    ctxt.moveTo(x, y);
    ctxt.lineTo(x + size, y + size);
    ctxt.lineTo(x - size, y + size);
    ctxt.lineTo(x, y);

    ctxt.fillStyle = 'rgb(0, 0, 0)';
    ctxt.fill();
}

drawTriangle(ctxt, 50, 0, 50);

... or, a bit more idiomatic:

www/index.js
/* ... */

// ---
// | The type of our `ctxt`.
// v------------------ v
CanvasRenderingContext2D.prototype.drawTriangle = function (x, y, size) {
    this.beginPath();
    this.moveTo(x, y);
    this.lineTo(x + size, y + size);
    this.lineTo(x - size, y + size);
    this.lineTo(x, y);

    this.fillStyle = 'rgb(0, 0, 0)';
    this.fill();
};

ctxt.drawTriangle(50, 0, 50);

Equipped with .drawTriangle(), we can now do:

www/index.html
<!-- ... -->
<canvas id="viewport" width="800" height="800"></canvas>
<!-- ... -->
www/index.js
/* ... */

for (const animal of simulation.world().animals) {
    ctxt.drawTriangle(
        animal.x * viewportWidth,
        animal.y * viewportHeight,
        0.01 * viewportWidth,
    );
}

Nice 😎

... and you know what would be even nicer? If they were rotated!

Vertices Go Brr

We already have a field called rotation inside lib-simulation:

libs/simulation/src/lib.rs
/* ... */

#[derive(Debug)]
pub struct Animal {
    /* ... */
    rotation: na::Rotation2<f32>,
    /* ... */
}

... so all we've gotta do is to pass it into JavaScript:

libs/simulation-wasm/src/lib.rs
/* ... */

#[derive(Clone, Debug, Serialize)]
pub struct Animal {
    pub x: f32,
    pub y: f32,
    pub rotation: f32,
}

/* ... */

impl From<&sim::Animal> for Animal {
    fn from(animal: &sim::Animal) -> Self {
        Self {
            x: animal.position().x,
            y: animal.position().y,
            rotation: animal.rotation().angle(),
        }
    }
}

... now wasm-pack build:

$ wasm-pack build
...
[INFO]: :-) Done in 2.42s
[INFO]: :-) Your wasm pkg is ready to publish at /home/pwy/Projects/...

... and we're back to JavaScript.

Since the rotation will be different for each triangle, we'll need to have another parameter:

www/index.js
/* ... */

CanvasRenderingContext2D.prototype.drawTriangle =
    function (x, y, size, rotation) {
        /* ... */
    };

/* ... */

Now, intuitively, what we're looking for is:

... generalized for any angle.

Vertices Go Brrr (using math)

Let's bring back our triangle — this time, together with its circumscribed circle:

Under this circumstances, I'd casually describe rotating as moving each vertex alongside the circle "with" certain angle:

How do we know where to move those points? Well, whenever there's a circle involved, there's probably a fair share of trigonometry happening underneath — it's certainly true this time!

You might've heard of cos() and sin() — while they aren't that impressive plotted separately:

... when we juxtapose both of them on a circle, we might just spot that what cos(angle) returns in practice is the x coordinate of a point "rotated" with given angle — and, similarly, sin(angle) yields the y coordinate:

Speaking in code-terms — if what we have currently is:

this.moveTo(x, y);

... then rotating the x coordinate requires applying + cos():

this.moveTo(
    x + Math.cos(rotation) * size,
    y,
);

... and rotating the y coordinate requires applying + sin():

this.moveTo(
    x + Math.cos(rotation) * size,
    y + Math.sin(rotation) * size,
);

... where rotation is measured in radians — that is, <0°, 360°> shrank to <0, 2 * PI>:

Okie — one vertex done:

... two more to go!

Since interior angles of a triangle sum up to 180° degrees, then inside our equilateral triangle, each vertex must be of angle = 180° / 3 = 60°.

A quick conversion to radians, using proportions:

2 * PI = 360°
     x = 60°

360° * x = 2 * PI * 60°    | divide by 2
180° * x = PI * 60°        | divide by 180°
       x = PI * 60° / 180° | simplify
       x = PI * 2 / 3      | shuffle constant to left
       x = 2 / 3 * PI      | enjoy

... gives us:

this.moveTo(
    x + Math.cos(rotation) * size,
    y + Math.sin(rotation) * size,
);

this.lineTo(
    x + Math.cos(rotation + 2.0 / 3.0 * Math.PI) * size,
    y + Math.sin(rotation + 2.0 / 3.0 * Math.PI) * size,
);

Similarly, the third vertex will be 60° away from the second vertex:

2 * PI = 360°
     x = 60° + 60°

/* ... */

x = 4 / 3 * PI

... giving us:

this.moveTo(
    x + Math.cos(rotation) * size,
    y + Math.sin(rotation) * size,
);

this.lineTo(
    x + Math.cos(rotation + 2.0 / 3.0 * Math.PI) * size,
    y + Math.sin(rotation + 2.0 / 3.0 * Math.PI) * size,
);

this.lineTo(
    x + Math.cos(rotation + 4.0 / 3.0 * Math.PI) * size,
    y + Math.sin(rotation + 4.0 / 3.0 * Math.PI) * size,
);

As you might see in the drawing, now we're missing only the very last edge going from the third vertex back into the first:

... so:

/* ... */

this.lineTo(
    x + Math.cos(rotation + 4.0 / 3.0 * Math.PI) * size,
    y + Math.sin(rotation + 4.0 / 3.0 * Math.PI) * size,
);

this.lineTo(
    x + Math.cos(rotation) * size,
    y + Math.sin(rotation) * size,
);

In all its glory, our code is:

www/index.js
/* ... */

CanvasRenderingContext2D.prototype.drawTriangle =
    function (x, y, size, rotation) {
        this.beginPath();

        this.moveTo(
            x + Math.cos(rotation) * size,
            y + Math.sin(rotation) * size,
        );

        this.lineTo(
            x + Math.cos(rotation + 2.0 / 3.0 * Math.PI) * size,
            y + Math.sin(rotation + 2.0 / 3.0 * Math.PI) * size,
        );

        this.lineTo(
            x + Math.cos(rotation + 4.0 / 3.0 * Math.PI) * size,
            y + Math.sin(rotation + 4.0 / 3.0 * Math.PI) * size,
        );

        this.lineTo(
            x + Math.cos(rotation) * size,
            y + Math.sin(rotation) * size,
        );

        this.stroke();
    };

ctxt.drawTriangle(50, 50, 25, Math.PI / 4);

Does it work? Apparently:

... but it's kinda hard to spot that it's rotated — what if we extruded one of the vertices?

www/index.js
/* ... */

CanvasRenderingContext2D.prototype.drawTriangle =
    function (x, y, size, rotation) {
        this.beginPath();

        this.moveTo(
            x + Math.cos(rotation) * size * 1.5,
            y + Math.sin(rotation) * size * 1.5,
        );

        /* ... */

        this.lineTo(
            x + Math.cos(rotation) * size * 1.5,
            y + Math.sin(rotation) * size * 1.5,
        );

        this.stroke();
    };

/* ... */

There, better:

Animals Go Brrr

Now that we are able to render rotated triangles, we can adjust our code from before:

www/index.js
/* ... */

for (const animal of simulation.world().animals) {
    ctxt.drawTriangle(
        animal.x * viewportWidth,
        animal.y * viewportHeight,
        0.01 * viewportWidth,
        animal.rotation,
    );
}

... which gives us:

Neat; high five, pal — we've earned it!

step()-ping stones

Stationary triangles are cool — obviously! — but moving triangles are even better.

Our birds don't have brains, but they do have rotation & speed — this means we can simulate physics on them, even if they won't be able to interact with their environment yet:

libs/simulation/src/lib.rs
/* ... */

impl Simulation {
    /* ... */

    /// Performs a single step - a single second, so to say - of our
    /// simulation.
    pub fn step(&mut self) {
        for animal in &mut self.world.animals {
            animal.position += animal.rotation * animal.speed;
        }
    }
}

/* ... */

One cargo check after:

$ cargo check
error[E0277]: cannot multiply `Rotation<f32, 2_usize>` by `f32`
   |
   |             animal.position += animal.rotation * animal.speed;
   |                                                ^
   |             -----------------------------------|
   |             no implementation for `Rotation<f32, 2_usize> * f32`
   |
   = help: the trait `Mul<f32>` is not implemented for
     `Rotation<f32, 2_usize>`

Hmm, nalgebra doesn't provide Rotation2 * f32 — maybe we can use a vector instead?

libs/simulation/src/lib.rs
/* ... */
animal.position += animal.rotation * na::Vector2::new(animal.speed, 0.0);
/* ... */
$ cargo check
Finished dev [unoptimized + debuginfo] target(s) in 18.04s

Bingo!

With step() inside lib-simulation, we can now expose it via lib-simulation-wasm:

libs/simulation-wasm/src/lib.rs
/* ... */

#[wasm_bindgen]
impl Simulation {
    /* ... */

    pub fn step(&mut self) {
        self.sim.step();
    }
}

/* ... */

... and compile:

$ wasm-pack build
....
[INFO]: :-) Done in 3.58s
[INFO]: :-) Your wasm pkg is ready to publish at /home/pwy/Projects/...

As for invoking .step() from JavaScript — while in some languages we might've used a loop:

/* ... */

while (true) {
     ctxt.clearRect(0, 0, viewportWidth, viewportHeight);

     simulation.step();

     for (const animal of simulation.world().animals) {
         ctxt.drawTriangle(
             animal.x * viewportWidth,
             animal.y * viewportHeight,
             0.01 * viewportWidth,
             animal.rotation,
         );
     }
}

... the web browser environment makes it a bit harder, because our code mustn't block. That's because when JavaScript is working, browser waits for it to finish, hanging the tab and preventing user from interacting with the page.

The more time it takes for the code to complete, the longer the tab is blocked — it's essentially single-threaded. So if we wrote while (true) { …​ }, the browser would just hang the tab forever, patiently waiting for the code to finish working.

Instead of blocking, we can use a function called requestAnimationFrame() — it schedules a function to be executed just before the next frame is drawn, and finishes immediately:

www/index.js
/* ... */

function redraw() {
    ctxt.clearRect(0, 0, viewportWidth, viewportHeight);

    simulation.step();

    for (const animal of simulation.world().animals) {
        ctxt.drawTriangle(
            animal.x * viewportWidth,
            animal.y * viewportHeight,
            0.01 * viewportWidth,
            animal.rotation,
        );
    }

    // requestAnimationFrame() schedules code only for the next frame.
    //
    // Because we want for our simulation to continue forever, we've
    // gotta keep re-scheduling our function:
    requestAnimationFrame(redraw);
}

redraw();

And voilà:

... or rather voil-whaaat — why do they disappear after a while?

Let's go back to lib-simulation and investigate:

libs/simulation/src/lib.rs
/* ... */

impl Simulation {
    /* ... */

    pub fn step(&mut self) {
        for animal in &mut self.world.animals {
            animal.position +=
                animal.rotation * na::Vector2::new(animal.speed, 0.0);
        }
    }
}

/* ... */

So we add rotation to position and…​ ah, right! Our map is bounded by <0.0, 1.0> — anything beyond those coordinates can exist, but it'd be rendered outside the canvas; as we've just seen.

Let's fix it:

libs/simulation/src/lib.rs
/* ... */

impl Simulation {
    /* ... */

    pub fn step(&mut self) {
        for animal in &mut self.world.animals {
            animal.position +=
                animal.rotation * na::Vector2::new(animal.speed, 0.0);

            animal.position.x = na::wrap(animal.position.x, 0.0, 1.0);
            animal.position.y = na::wrap(animal.position.y, 0.0, 1.0);
        }
    }
}

/* ... */

wrap() does pretty much what it says — the first argument is the number being checked, while the second and third arguments determine minimum and maximum allowed values:

With this fix, let's $ wasm-pack build — and:

Woohoo!

You’re Somebody Else (when you’re hungry)

All said, birds constitute for only half of our ecosystem - we've also got food.

Rendering food

Fortunately, because we've already written lots of the code, rendering food distills to just a few changes:

libs/simulation-wasm/src/lib.rs
/* ... */

#[derive(Clone, Debug, Serialize)]
pub struct World {
    pub animals: Vec<Animal>,
    pub foods: Vec<Food>,
}

#[derive(Clone, Debug, Serialize)]
pub struct Food {
    pub x: f32,
    pub y: f32,
}

/* ... */

impl From<&sim::World> for World {
    fn from(world: &sim::World) -> Self {
        /* ... */

        let foods = world
            .foods()
            .iter()
            .map(Food::from)
            .collect();

        Self { animals, foods }
    }
}

/* ... */

impl From<&sim::Food> for Food {
    fn from(food: &sim::Food) -> Self {
        Self {
            x: food.position().x,
            y: food.position().y,
        }
    }
}
www/index.js
/* ... */

CanvasRenderingContext2D.prototype.drawCircle =
    function(x, y, radius) {
        this.beginPath();

        // ---
        // | Circle's center.
        // ----- v -v
        this.arc(x, y, radius, 0, 2.0 * Math.PI);
        // ------------------- ^ -^-----------^
        // | Range at which the circle starts and ends, in radians.
        // |
        // | By manipulating these two parameters you can e.g. draw
        // | only half of a circle, Pac-Man style.
        // ---

        this.fillStyle = 'rgb(0, 0, 0)';
        this.fill();
    };

function redraw() {
    ctxt.clearRect(0, 0, viewportWidth, viewportHeight);

    simulation.step();

    const world = simulation.world();

    for (const food of world.foods) {
        ctxt.drawCircle(
            food.x * viewportWidth,
            food.y * viewportHeight,
            (0.01 / 2.0) * viewportWidth,
        );
    }

    for (const animal of world.animals) {
        /* ... */
    }

    /* ... */
}

/* ... */

Believe me or not, it's enough!

$ wasm-pack build
....
[INFO]: :-) Done in 1.25s
[INFO]: :-) Your wasm pkg is ready to publish at /home/pwy/Projects/...

Pimpin'-up

Our math checks out, but our simulation's appearance is…​ daunting — let's try pimpin' it up:

www/index.html
<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title>Shorelark</title>
  </head>
  <style>
    body {
      background: #1f2639; /* A nice navy blue color that I found by
                              a nice trial and error */
    }
  </style>
  <body>
    <canvas id="viewport" width="800" height="800"></canvas>
    <script src="./bootstrap.js"></script>
  </body>
</html>
www/index.js
/* ... */

CanvasRenderingContext2D.prototype.drawTriangle =
    function (x, y, size, rotation) {
        /* ... */

        this.fillStyle = 'rgb(255, 255, 255)'; // A nice white color
        this.fill();
    };

CanvasRenderingContext2D.prototype.drawCircle =
    function(x, y, radius) {
        /* ... */

        this.fillStyle = 'rgb(0, 255, 128)'; // A nice green color
        this.fill();
    };

/* ... */

There, better:

Simulating food

At the moment, when our birdies collide with food, nothing happens — time to improve it!

First, let's refactor step() a bit:

libs/simulation/src/lib.rs
/* ... */

impl Simulation {
    /* ... */

    pub fn step(&mut self) {
        self.process_movements();
    }

    fn process_movements(&mut self) {
        for animal in &mut self.world.animals {
            animal.position +=
                animal.rotation * na::Vector2::new(animal.speed, 0.0);

            animal.position.x = na::wrap(animal.position.x, 0.0, 1.0);
            animal.position.y = na::wrap(animal.position.y, 0.0, 1.0);
        }
    }
}

/* ... */

Now:

libs/simulation/src/lib.rs
/* ... */

impl Simulation {
    /* ... */

    pub fn step(&mut self) {
        self.process_collisions();
        self.process_movements();
    }

    fn process_collisions(&mut self) {
        todo!();
    }

    /* ... */
}

/* ... */

In plain English, what we want to achieve is:

/* ... */

fn process_collisions(&mut self) {
    for each animal {
        for each food {
            if animal collides with food {
                handle collision
            }
        }
    }
}

/* ... */

The process of checking whether two polygons collide is called hit-testing — so since our birds are triangles and our foods are circles, the thing we should be duckduckgoing for is triangle circle hit test algorithm (or triangle circle collision etc.).

But — funny thing — this kind of hit-testing is unbearably complex, so whaddya say we try something simpler; hang tight:

What if we assumed our birds are circles?

You know, we can keep drawing them as triangles — it's only about the physics engine.

Agreed? (just kidding, I know you can't reply here.)

Ok, so circle-circle hit testing relies on checking whether the distance between two cirles is shorter or equal than the sum of their radii:

distance(A, B) > radius(A) + radius(B) ⇒ no collision
distance(A, B) <= radius(A) + radius(B) ⇒ collision

In practice, this reduces to a single if:

libs/simulation/src/lib.rs
/* ... */

pub fn step(&mut self, rng: &mut dyn RngCore) {
    self.process_collisions(rng);
    self.process_movements();
}

fn process_collisions(&mut self, rng: &mut dyn RngCore) {
    for animal in &mut self.world.animals {
        for food in &mut self.world.foods {
            let distance = na::distance(
                &animal.position,
                &food.position,
            );

            if distance <= 0.01 {
                food.position = rng.gen();
            }
        }
    }
}

/* ... */
libs/simulation-wasm/src/lib.rs
/* ... */

#[wasm_bindgen]
impl Simulation {
    /* ... */

    pub fn step(&mut self) {
        self.sim.step(&mut self.rng);
    }
}

/* ... */

The distance returned by nalgebra is in the same units as our positions - so a distance of, say, 0.5 means that our animal and food are half a map apart from each other, while 0.0 means that both are at the exact same coordinates.

0.01 determines the radius of our food — I've chosen 0.01 because it seems to play nice with the sizes we're using for drawing.

Overall, does it work? Oh my!

Birdie and the Brain

Our birds can fly, but they can't interact with their environment yet — in this chapter we'll implement eyes, allowing for our birds to see the food, and brains, allowing for our birds to decide where they want to fly.

Refactoring

There's a lot of code inside libs/simulation/src/lib.rs - before we go further, let's take a moment to refactor it.

A good rule of thumb is to keep a struct per file, so:

libs/simulation/src/lib.rs
pub use self::{animal::*, food::*, world::*};

mod animal;
mod food;
mod world;

use nalgebra as na;
use rand::{Rng, RngCore};

pub struct Simulation {
    /* ... */
}

impl Simulation {
    /* ... */
}
libs/simulation/src/animal.rs
use crate::*;

#[derive(Debug)]
pub struct Animal {
    /* ... */
}

impl Animal {
    /* ... */
}
libs/simulation/src/food.rs
use crate::*;

#[derive(Debug)]
pub struct Food {
    /* ... */
}

impl Food {
    /* ... */
}
libs/simulation/src/world.rs
use crate::*;

#[derive(Debug)]
pub struct World {
    /* ... */
}

impl World {
    /* ... */
}

... and now:

$ cargo check
error[E0616]: field `animals` of struct `world::World` is private
  --> libs/simulation/src/lib.rs
   |
   |         for animal in &mut self.world.animals {
   |                                       ^^^^^^^ private field

error[E0616]: field `foods` of struct `world::World` is private
  --> libs/simulation/src/lib.rs
   |
   |             for food in &mut self.world.foods {
   |                                         ^^^^^ private field

/* ... */

Oh no; we've only shuffled some code around — what happened? Let's see the offending place:

libs/simulation/src/lib.rs
/* ... */

impl Simulation {
    /* ... */

    fn process_collisions(&mut self, rng: &mut dyn RngCore) {
        for animal in &mut self.world.animals {
            //                       ^------^

            for food in &mut self.world.foods {
                //                     ^----^

                /* ... */
            }
        }
    }
}

Previously, when all four structs were in the same file, Rust's visibility rules allowed for all of them to access each other's private fields. Now that our structs are in separate files, they can't access non-pub fields anymore.

There are two ways we could solve this issue:

  1. We could provide mutable getters:

    // libs/simulation/src/world.rs
    impl World {
        pub(crate) fn animals_mut(&mut self) -> &mut [Animal] {
            &mut self.animals
        }
    
        pub(crate) fn foods_mut(&mut self) -> &mut [Food] {
            &mut self.foods
        }
    }
    
    // libs/simulation/src/lib.rs
    impl Simulation {
        fn process_collisions(&mut self, rng: &mut dyn RngCore) {
            for animal in self.world.animals_mut() {
                for food in self.world.foods_mut() {
                    /* ... */
                }
            }
        }
    }
    
  2. We could change World-'s fields to be crate-public instead of private:

    #[derive(Debug)]
    pub struct World {
        pub(crate) animals: Vec<Animal>,
        pub(crate) foods: Vec<Food>,
    }
    

All fields (or functions, as seen in the first case) prepended with pub(crate) are visible to the entire code inside given crate — so pub(crate) animals means that all the code inside lib-simulation will be able to access world.animals, and it'll remain private for other crates.

As for the difference between both snippets, it's pretty minor:

  1. Some people advocate for mutable getters, because they make refactoring easier (e.g. you can rename the field from animals to birds, but keep fn animals_mut() to avoid introducing a breaking change),

  2. Some people advocate for crate-public fields, because they make the code shorter (there's no need to create additional functions).

For simplicity, we'll go with the second approach — with an additional touch:

libs/simulation/src/lib.rs
#![feature(crate_visibility_modifier)]
// ^ Allows to write `crate field: ...` instead of a bit longer
// | `pub(crate) field: ...`.
// |
// | I like it, because it makes the code easier to follow.
// ---

/* ... */
libs/simulation/src/animal.rs
/* ... */

#[derive(Debug)]
pub struct Animal {
    crate position: na::Point2<f32>,
    crate rotation: na::Rotation2<f32>,
    crate speed: f32,
}

/* ... */
libs/simulation/src/food.rs
/* ... */

#[derive(Debug)]
pub struct Food {
    crate position: na::Point2<f32>,
}

/* ... */
libs/simulation/src/world.rs
/* ... */

#[derive(Debug)]
pub struct World {
    crate animals: Vec<Animal>,
    crate foods: Vec<Food>,
}

/* ... */
$ cargo check
Checking lib-simulation v0.1.0
    Checking lib-simulation-wasm v0.1.0
    Finished dev [unoptimized + debuginfo] target(s) in 0.57s

Nice 😎 — now we're ready to implement eyes!

Eye Of The Birdie

What's an eye?

Well, a biologist might tell you that eye is an organ that provides vision; a philosopher's take might be that eye is a window to one's soul; and me? I think that an eye…​

libs/simulation/src/lib.rs
pub use self::{animal::*, eye::*, food::*, world::*};

mod animal;
mod eye;
mod food;
mod world;

... is a struct!

libs/simulation/src/eye.rs
use crate::*;

#[derive(Debug)]
pub struct Eye;

Not just any struct, though — it's gotta have one function in particular:

libs/simulation/src/eye.rs
/* ... */

impl Eye {
    pub fn process_vision() -> Vec<f32> {
        todo!()
    }
}

The result of this function is a vector of numbers, where each number — each eye cell — tells us how close the nearest food matching that eye cell is:

Example of an eye with three eye cells

Such an eye is defined by a few parameters:

libs/simulation/src/eye.rs
use crate::*;
use std::f32::consts::*;

/// How far our eye can see:
///
/// -----------------
/// |               |
/// |               |
/// |               |
/// |@      %      %|
/// |               |
/// |               |
/// |               |
/// -----------------
///
/// If @ marks our birdie and % marks food, then a FOV_RANGE of:
///
/// - 0.1 = 10% of the map = bird sees no foods (at least in this case)
/// - 0.5 = 50% of the map = bird sees one of the foods
/// - 1.0 = 100% of the map = bird sees both foods
const FOV_RANGE: f32 = 0.25;

/// How wide our eye can see.
///
/// If @> marks our birdie (rotated to the right) and . marks the area
/// our birdie sees, then a FOV_ANGLE of:
///
/// - PI/2 = 90° =
///   -----------------
///   |             /.|
///   |           /...|
///   |         /.....|
///   |       @>......|
///   |         \\.....|
///   |           \\...|
///   |             \\.|
///   -----------------
///
/// - PI = 180° =
///   -----------------
///   |       |.......|
///   |       |.......|
///   |       |.......|
///   |       @>......|
///   |       |.......|
///   |       |.......|
///   |       |.......|
///   -----------------
///
/// - 2 * PI = 360° =
///   -----------------
///   |...............|
///   |...............|
///   |...............|
///   |.......@>......|
///   |...............|
///   |...............|
///   |...............|
///   -----------------
///
/// Field of view depends on both FOV_RANGE and FOV_ANGLE:
///
/// - FOV_RANGE=0.4, FOV_ANGLE=PI/2:
///   -----------------
///   |       @       |
///   |     /.v.\\     |
///   |   /.......\\   |
///   |   ---------   |
///   |               |
///   |               |
///   |               |
///   -----------------
///
/// - FOV_RANGE=0.5, FOV_ANGLE=2*PI:
///   -----------------
///   |               |
///   |      ---      |
///   |     /...\\     |
///   |    |..@..|    |
///   |     \\.../     |
///   |      ---      |
///   |               |
///   -----------------
const FOV_ANGLE: f32 = PI + FRAC_PI_4;

/// How much photoreceptors there are in a single eye.
///
/// More cells means our birds will have more "crisp" vision, allowing
/// them to locate the food more precisely - but the trade-off is that
/// the evolution process will then take longer, or even fail, unable
/// to find any solution.
///
/// I've found values between 3~11 sufficient, with eyes having more
/// than ~20 photoreceptors yielding progressively worse results.
const CELLS: usize = 9;

#[derive(Debug)]
pub struct Eye {
    fov_range: f32,
    fov_angle: f32,
    cells: usize,
}

impl Eye {
    // FOV_RANGE, FOV_ANGLE & CELLS are the values we'll use during
    // simulation - but being able to create an arbitrary eye will
    // come handy during the testing:
    fn new(fov_range: f32, fov_angle: f32, cells: usize) -> Self {
        assert!(fov_range > 0.0);
        assert!(fov_angle > 0.0);
        assert!(cells > 0);

        Self { fov_range, fov_angle, cells }
    }

    pub fn cells(&self) -> usize {
        self.cells
    }

    pub fn process_vision(
        &self,
        position: na::Point2<f32>,
        rotation: na::Rotation2<f32>,
        foods: &[Food],
    ) -> Vec<f32> {
        todo!()
    }
}

impl Default for Eye {
    fn default() -> Self {
        Self::new(FOV_RANGE, FOV_ANGLE, CELLS)
    }
}

The basic outline of our algorithm is:

libs/simulation/src/eye.rs
/* ... */

pub fn process_vision(/* ... */) -> Vec<f32> {
    let mut cells = vec![0.0; self.cells];

    for food in foods {
        if food inside fov {
           cells[cell that sees this food] += how close the food is;
        }
    }

    cells
}

/* ... */

How can we check if some food is inside our field of view? Two conditions must be fulfilled:

  1. The distance between us and the food must be no greater than FOV_RANGE:

    libs/simulation/src/eye.rs
    /* ... */
    
    for food in foods {
        let vec = food.position - position;
    
        // ^ Represents a *vector* from food to us
        //
        // In case this is the first time you hear the word `vector`, a
        // quick definition would be:
        //
        // > A vector is an object that has *magnitude* (aka length)
        // > and *direction*.
        //
        // You could say a vector is an arrow:
        //
        //   ---> this is a vector of magnitude=3 (if we count each
        //        dash as a single "unit of space"), and direction=0°
        //        (at least relative to the X axis)
        //
        //    |   this is a vector of magnitude=1 and direction=90°
        //    v   (at least when we treat direction clockwise)
        //
        // Our food-to-birdie vectors are no different:
        //
        // ---------
        // |       |  gets us this vector:
        // |@     %|          <-----
        // |       |  (magnitude=5, direction=180°)
        // ---------
        //
        // ---------  gets us this vector:
        // |   %   |           |
        // |       |           |
        // |   @   |           v
        // ---------  (magnitude=2, direction=90°)
        //
        // This is not to be confused with Rust's `Vec` or C++'s
        // `std::vector`, which technically *are* vectors, but in a more
        // abstract sense -- better not overthink it.
        //
        // (https://stackoverflow.com/questions/581426/why-is-a-c-vector-called-a-vector).
    
        // ---
        // | Fancy way to say "length of the vector".
        // ----------- v----v
        let dist = vec.norm();
    
        if dist >= self.fov_range {
            continue;
        }
    }
    
    /* ... */
    
  2. The angle between us and the food must be no greater than FOV_ANGLE — and since our birdie's vision is symmetrical (they see the same amount "on the left" and "on the right", just like humans do), this means that our angle must be <-FOV_ANGLE/2, +FOV_ANGLE/2>:

    libs/simulation/src/eye.rs
    /* ... */
    
    for food in foods {
        /* ... */
    
        // Returns vector's direction relative to the X axis, that is:
        //
        //   --> = 0° = 0
        //
        //    |  = 90° = PI / 2
        //    v
        //
        //   <--- = 180° = PI
        //
        // (if you've been measuring rotations before - this is atan2
        // in disguise.)
        let angle = na::Rotation2::rotation_between(
            &na::Vector2::x(),
            &vec,
        ).angle();
    
        // Because our bird is *also* rotated, we have to include its
        // rotation too:
        let angle = angle - rotation.angle();
    
        // Rotation is wrapping (from -PI to PI), that is:
        //
        //   = angle of 2*PI
        //   = angle of PI    (because 2*PI >= PI)
        //   = angle of 0     (          PI >= PI)
        //                    (           0 < PI; fin.)
        //
        //  angle of 2*PI + PI/2
        //  = angle of 1*PI + PI/2  (because 2*PI + PI/2 >= PI)
        //  = angle of PI/2         (          PI + PI/2 >= PI)
        //                          (               PI/2 < PI; fin.)
        //
        //  angle of -2.5*PI
        //  = angle of -1.5*PI  (because -2.5*PI <= -PI)
        //  = angle of -0.5*PI  (        -1.5*PI <= -PI)
        //                      (        -0.5*PI > -PI; fin.)
        //
        // Intuitively:
        //
        // - when you rotate yourself twice around the axis, it's the
        //   same as if you rotated once, as if you've never rotated
        //   at all.
        //
        //   (your bony labyrinth might have a different opinion tho.)
        //
        // - when you rotate by 90° and then by 360°, it's the same
        //   as if you rotated only by 90° (*or* by 270°, just in the
        //   opposite direction).
        let angle = na::wrap(angle, -PI, PI);
    
        // If current angle is outside our birdie's field of view, jump
        // to the next food
        if angle < -self.fov_angle / 2.0 ||
           angle > self.fov_angle / 2.0
        {
            continue;
        }
    }
    
    /* ... */
    

Ok, we've rejected all the foods outside our birdie's field of view — for the eye to work, we need one more thing:

cells[cell that sees this food] += how close the food is;

Determining which concrete cell sees the food is a bit tricky, but it distills to looking at the angle between the food and our eye — e.g. for an eye with three cells and fov of 120°:

In the poetic language of code:

libs/simulation/src/eye.rs
/* ... */

for food in foods {
    /* ... */

    // Makes angle *relative* to our birdie's field of view - that is:
    // transforms it from <-FOV_ANGLE/2,+FOV_ANGLE/2> to <0,FOV_ANGLE>.
    //
    // After this operation:
    // - an angle of 0° means "the beginning of the FOV",
    // - an angle of self.fov_angle means "the ending of the FOV".
    let angle = angle + self.fov_angle / 2.0;

    // Since this angle is now in range <0,FOV_ANGLE>, by dividing it by
    // FOV_ANGLE, we transform it to range <0,1>.
    //
    // The value we get can be treated as a percentage, that is:
    //
    // - 0.2 = the food is seen by the "20%-th" eye cell
    //         (practically: it's a bit to the left)
    //
    // - 0.5 = the food is seen by the "50%-th" eye cell
    //         (practically: it's in front of our birdie)
    //
    // - 0.8 = the food is seen by the "80%-th" eye cell
    //         (practically: it's a bit to the right)
    let cell = angle / self.fov_angle;

    // With cell in range <0,1>, by multiplying it by the number of
    // cells we get range <0,CELLS> - this corresponds to the actual
    // cell index inside our `cells` array.
    //
    // Say, we've got 8 eye cells:
    // - 0.2 * 8 = 20% * 8 = 1.6 ~= 1 = second cell (indexing from 0!)
    // - 0.5 * 8 = 50% * 8 = 4.0 ~= 4 = fifth cell
    // - 0.8 * 8 = 80% * 8 = 6.4 ~= 6 = seventh cell
    let cell = cell * (self.cells as f32);

    // Our `cell` is of type `f32` - before we're able to use it to
    // index an array, we have to convert it to `usize`.
    //
    // We're also doing `.min()` to cover an extreme edge case: for
    // cell=1.0 (which corresponds to a food being maximally to the
    // right side of our birdie), we'd get `cell` of `cells.len()`,
    // which is one element *beyond* what the `cells` array contains
    // (its range is <0, cells.len()-1>).
    //
    // Being honest, I've only caught this thanks to unit tests we'll
    // write in a moment, so if you consider my explanation
    // insufficient (pretty fair!), please feel free to drop the
    // `.min()` part later and see which tests fail - and why :-)
    let cell = (cell as usize).min(cells.len() - 1);
}

/* ... */

Now that we know the cell index, our final touch in here is:

libs/simulation/src/eye.rs
/* ... */

for food in foods {
    /* ... */

    // Energy is inversely proportional to the distance between our
    // birdie and the currently checked food; that is - an energy of:
    //
    // - 0.0001 = food is barely in the field of view (i.e. far away),
    // - 1.0000 = food is right in front of the bird.
    //
    // We could also model energy in reverse manner - "the higher the
    // energy, the further away the food" - but from what I've seen, it
    // makes the learning process a bit harder.
    //
    // As always, feel free to experiment! -- overall this isn't the
    // only way of implementing eyes :-)
    let energy = (self.fov_range - dist) / self.fov_range;

    cells[cell] += energy;
}

/* ... */

That's a lot of math! — how do we know it works? Of course, by testing it 😊

Nothing But Tests

The first obstacle is that our vision requires lot of parameters to compute:

Even ignoring the number of cells — which we can hard-code without losing much — this gets us 5 different tunables that affect each other, plus we've also got to specify locations of our foods; moon on a stick, checking all of the combinations, I tell ya'!

The second obstacle is that our Eye::process_vision() returns Vec<f32>, so it's one of those functions that take some dry numbers and return some dry numbers; not only it's a bit boring, but also resilient to solid testing:

is vec![0.0, 0.1, 0.7] really the response we want for x=0.2, y=0.5? who knows!

So, as for the first obstacle, my idea is to use a thing called parameterized tests — with a pinch of salt, parameterized tests are when you create a testing function:

#[test]
fn some_test() {
    /* ... */
}

... and make it accept one or many parameters:

// This is just an example in pseudo-Rust

#[test(x=10, y=20, z=30)]
#[test(x=50, y=50, z=50)]
#[test(x=0, y=0, z=0)]
fn some_test(x: f32, y: f32, z: usize) {
    /* ... */
}

This testing methodology allows to cover the input space more thoroughly than you'd do with copy-pasted mod { …​ }, simply because adding more edge cases is just so easy.

Rust doesn't support parameterized tests natively — at least not in the manner that I've shown above — but there exist a few crates providing this functionality; we're going to use test-case:

libs/simulation/Cargo.toml
# ...

[dev-dependencies]
test-case = "1.1"

... which has a pretty straightforward syntax:

libs/simulation/src/eye.rs
/* ... */

#[cfg(test)]
mod tests {
    use super::*;

    mod different_fov_ranges {
        use super::*;
        use test_case::test_case;

        #[test_case(1.0)]
        #[test_case(0.5)]
        #[test_case(0.1)]
        fn test(fov_range: f32) {
            todo!()
        }
    }
}

This solves the first obstacle, at least for all the practical purposes; while we still won't be able to cover all the cases (remember how many numbers f32 can encode?), the more test-cases we include, the more confident we can be that our code works as intended.

As for the second hindrance: instead of comparing blunt vectors of number, whaddya say we compare graphical representations of what the bird sees?

Stay with me: even if process_vision() returns something like vec![0.0, 0.5, 0.0], it doesn't mean we're forced to compare that in our tests! If instead of a vector, what we compared was, hmm, " * ", it'd be waay easier to ensure our eye works correctly!

So, baby steps:

libs/simulation/src/eye.rs
/* ... */

#[cfg(test)]
mod tests {
    use super::*;

    fn test(
        foods: Vec<Food>,
        fov_range: f32,
        fov_angle: f32,
        x: f32,
        y: f32,
        rot: f32,
        expected_vision: &str,
    ) {
        todo!()
    }

    mod different_fov_ranges {
        use super::*;
        use test_case::test_case;

        #[test_case(1.0)]
        #[test_case(0.5)]
        #[test_case(0.1)]
        fn test(fov_range: f32) {
            super::test(
                todo!(),
                fov_range,
                todo!(),
                todo!(),
                todo!(),
                todo!(),
                todo!(),
             );
        }
    }
}

Hmmm, no — that's waaay too many parameters for a single function; how about a struct?

libs/simulation/src/eye.rs
/* ... */

#[cfg(test)]
mod tests {
    use super::*;

    struct TestCase {
        foods: Vec<Food>,
        fov_range: f32,
        fov_angle: f32,
        x: f32,
        y: f32,
        rot: f32,
        expected_vision: &'static str,
    }

    impl TestCase {
        fn run(self) {
            todo!()
        }
    }

    mod different_fov_ranges {
        use super::*;
        use test_case::test_case;

        #[test_case(1.0)]
        #[test_case(0.5)]
        #[test_case(0.1)]
        fn test(fov_range: f32) {
            TestCase {
                foods: todo!(),
                fov_angle: todo!(),
                x: todo!(),
                y: todo!(),
                rot: todo!(),
                expected_vision: todo!(),
                fov_range,
            }.run()
        }
    }
}

Nice and readable; nice and readable.

Our test's result, expected_vision, depends on fov_range, so it's formally a parameter, too:

libs/simulation/src/eye.rs
/* ... */

mod different_fov_ranges {
    use super::*;
    use test_case::test_case;

    #[test_case(1.0, "not sure yet")]
    #[test_case(0.5, "not sure yet")]
    #[test_case(0.1, "not sure yet")]
    fn test(fov_range: f32, expected_vision: &'static str) {
        TestCase {
            foods: todo!(),
            fov_angle: todo!(),
            x: todo!(),
            y: todo!(),
            rot: todo!(),
            fov_range,
            expected_vision,
        }.run()
    }
}

/* ... */

About that TestCase — from a birds-eye view, what we're looking for is:

/* ... */

impl TestCase {
    fn run(self) {
        let eye = Eye::new(/* ... */);

        let actual_vision = eye.process_vision(/* ... */);
        let actual_vision = make_human_readable(actual_vision);

        assert_eq!(actual_vision, self.expected_vision);
    }
}

/* ... */

Since our TestCase already knows all the parameters needed, we can start implementing it:

libs/simulation/src/eye.rs
/* ... */

/// All our tests will use eyes hard-coded to thirteen eye cells.
///
/// As for the "why":
///
/// While we certainly *could* implement tests for different number of
/// eye cells, after a while I've decided it's just not worth the
/// hassle - as you'll see in a moment, we'll already get a good coverage
/// via the other parameters, so creating a separate set of tests for
/// different values of eye cells seemed like a waste of time.
///
/// As for the "why this number in particular":
///
/// I've checked a few numbers by hand, and generally found 13 to yield
/// pretty good results. As always, nothing special about 13 in
/// particular, your (eye) mileage may vary.
const TEST_EYE_CELLS: usize = 13;

impl TestCase {
    fn run(self) {
        let eye = Eye::new(
            self.fov_range,
            self.fov_angle,
            TEST_EYE_CELLS,
        );

        let actual_vision = eye.process_vision(
            na::Point2::new(self.x, self.y),
            na::Rotation2::new(self.rot),
            &self.foods,
        );

        /* ... */
    }
}

/* ... */

Currently our actual_vision is Vec<f32> — we can convert it into a string via a chip of .into_iter(), .map() and .join() magic:

libs/simulation/src/eye.rs
/* ... */

impl TestCase {
    fn run(self) {
        /* ... */

        let actual_vision: Vec<_> = actual_vision
            .into_iter()
            .map(|cell| {
                // As a reminder, the higher cell's value, the closer
                // the food is:

                if cell >= 0.7 {
                    // <0.7, 1.0>
                    // food is right in front of us
                    "#"
                } else if cell >= 0.3 {
                    // <0.3, 0.7)
                    // food is somewhat further
                    "+"
                } else if cell > 0.0 {
                    // <0.0, 0.3)
                    // food is pretty far away
                    "."
                } else {
                    // 0.0
                    // no food in sight, this cell sees empty space
                    " "
                }
            })
            .collect();

        // As before, there's nothing special about the cell values
        // (`0.7`, `0.3`, `0.0`) or the characters (`#`, `+`, `.`).
        //
        // I've chosen hash because to my eye it seems to occupy the
        // most "visual space" out of all the ASCII characters (thus
        // it represents a food being close), and then plus and dot
        // are just smaller (representing food being further away).

        // `.join()` converts `Vec<String>` into `String` using a
        // separator - e.g. `vec!["a", "b", "c"].join("|")` would
        // return `a|b|c`.
        let actual_vision = actual_vision.join("");

        // The finish line!
        assert_eq!(actual_vision, self.expected_vision);
    }
}

/* ... */

Just like that, our testing framework is complete! 🥳

Now, as for the tests — allow me to present you pure beauty:

libs/simulation/src/eye.rs
/* ... */

// A helper-function that allows to create food easily
fn food(x: f32, y: f32) -> Food {
    Food {
        position: na::Point2::new(x, y),
    }
}

mod different_fov_ranges {
    use super::*;
    use test_case::test_case;

    /// During tests in this module, we're using a world that looks
    /// like this:
    ///
    /// ------------
    /// |          |
    /// |          |
    /// |    @>   %|
    /// |          |
    /// |          |
    /// ------------
    ///
    /// Each test gradually reduces our birdie's field of view and
    /// compares what the birdie sees:
    ///
    /// ------------
    /// |        /.|
    /// |      /...|
    /// |    @>...%|
    /// |      \\...|
    /// |        \\.|
    /// ------------
    ///
    /// ------------
    /// |          |
    /// |      /.| |
    /// |    @>..|%|
    /// |      \\.| |
    /// |          |
    /// ------------
    ///
    /// ------------
    /// |          |
    /// |          |
    /// |    @>.| %|
    /// |          |
    /// |          |
    /// ------------
    ///
    /// Over time, what we see is the food gradually disappearing
    /// into an emptiness:
    ///
    /// (well, technically the food and bird remain stationary - it's
    /// only the birdie's own field of view that gets reduced.)
    #[test_case(1.0, "      +      ")] // Food is inside the FOV
    #[test_case(0.9, "      +      ")] // ditto
    #[test_case(0.8, "      +      ")] // ditto
    #[test_case(0.7, "      .      ")] // Food slowly disappears
    #[test_case(0.6, "      .      ")] // ditto
    #[test_case(0.5, "             ")] // Food disappeared!
    #[test_case(0.4, "             ")]
    #[test_case(0.3, "             ")]
    #[test_case(0.2, "             ")]
    #[test_case(0.1, "             ")]
    fn test(fov_range: f32, expected_vision: &'static str) {
        TestCase {
            foods: vec![food(1.0, 0.5)],
            fov_angle: FRAC_PI_2,
            x: 0.5,
            y: 0.5,
            rot: 0.0,
            fov_range,
            expected_vision,
        }.run()
    }
}

/* ... */

Breath in, breath out:

$ cargo test --workspace
running 10 tests
test eye::tests::different_fov_ranges::test::_0_4_ ... ok
test eye::tests::different_fov_ranges::test::_0_2_ ... ok
test eye::tests::different_fov_ranges::test::_0_5_ ... ok
test eye::tests::different_fov_ranges::test::_0_1_ ... ok
test eye::tests::different_fov_ranges::test::_0_3_ ... ok
test eye::tests::different_fov_ranges::test::_0_8_ ... ok
test eye::tests::different_fov_ranges::test::_0_9_ ... ok
test eye::tests::different_fov_ranges::test::_1_0_ ... ok
test eye::tests::different_fov_ranges::test::_0_7_ ... ok
test eye::tests::different_fov_ranges::test::_0_6_ ... ok

test result: ok. 10 passed; 0 failed

Ha, ha! — it works! And it's readable! (and, with luck, even maintainable!)

That's one parameter — four more to go! What about rotation?

libs/simulation/src/eye.rs
/* ... */

mod different_rotations {
    use super::*;
    use test_case::test_case;

    /// World:
    ///
    /// ------------
    /// |          |
    /// |          |
    /// |    @>    |
    /// |          |
    /// |         %|
    /// ------------
    ///
    /// Test cases:
    ///
    /// ------------
    /// |..........|
    /// |..........|
    /// |....@>....|
    /// |..........|
    /// |.........%|
    /// ------------
    ///
    /// ------------
    /// |..........|
    /// |..........|
    /// |....@.....|
    /// |....v.....|
    /// |.........%|
    /// ------------
    ///
    /// ------------
    /// |..........|
    /// |..........|
    /// |...<@.....|
    /// |..........|
    /// |.........%|
    /// ------------
    ///
    /// ... and so on, until we do a full circle, 360° rotation:
    #[test_case(0.00 * PI, "         +   ")] // Food is to our right
    #[test_case(0.25 * PI, "        +    ")]
    #[test_case(0.50 * PI, "      +      ")]
    #[test_case(0.75 * PI, "    +        ")]
    #[test_case(1.00 * PI, "   +         ")] // Food is behind us
    #[test_case(1.25 * PI, " +           ")] // (we continue to see it
    #[test_case(1.50 * PI, "            +")] // due to 360° fov_angle.)
    #[test_case(1.75 * PI, "           + ")]
    #[test_case(2.00 * PI, "         +   ")] // Here we've done 360°
    #[test_case(2.25 * PI, "        +    ")] // (and a bit more, to
    #[test_case(2.50 * PI, "      +      ")] // prove the numbers wrap.)
    fn test(rot: f32, expected_vision: &'static str) {
        TestCase {
            foods: vec![food(0.5, 1.0)],
            fov_range: 1.0,
            fov_angle: 2.0 * PI,
            x: 0.5,
            y: 0.5,
            rot,
            expected_vision,
        }.run()
    }
}

/* ... */

Testing position is even more fun:

libs/simulation/src/eye.rs
/* ... */

mod different_positions {
    use super::*;
    use test_case::test_case;

    /// World:
    ///
    /// ------------
    /// |          |
    /// |         %|
    /// |          |
    /// |         %|
    /// |          |
    /// ------------
    ///
    /// Test cases for the X axis:
    ///
    /// ------------
    /// |          |
    /// |        /%|
    /// |       @>.|
    /// |        \\%|
    /// |          |
    /// ------------
    ///
    /// ------------
    /// |        /.|
    /// |      /..%|
    /// |     @>...|
    /// |      \\..%|
    /// |        \\.|
    /// ------------
    ///
    /// ... and so on, going further left
    ///     (or, from the bird's point of view - going _back_)
    ///
    /// Test cases for the Y axis:
    ///
    /// ------------
    /// |     @>...|
    /// |       \\.%|
    /// |         \\|
    /// |         %|
    /// |          |
    /// ------------
    ///
    /// ------------
    /// |      /...|
    /// |     @>..%|
    /// |      \\...|
    /// |        \\%|
    /// |          |
    /// ------------
    ///
    /// ... and so on, going further down
    ///     (or, from the bird's point of view - going _right_)

    // Checking the X axis:
    // (you can see the bird is "flying away" from the foods)
    #[test_case(0.9, 0.5, "#           #")]
    #[test_case(0.8, 0.5, "  #       #  ")]
    #[test_case(0.7, 0.5, "   +     +   ")]
    #[test_case(0.6, 0.5, "    +   +    ")]
    #[test_case(0.5, 0.5, "    +   +    ")]
    #[test_case(0.4, 0.5, "     + +     ")]
    #[test_case(0.3, 0.5, "     . .     ")]
    #[test_case(0.2, 0.5, "     . .     ")]
    #[test_case(0.1, 0.5, "     . .     ")]
    #[test_case(0.0, 0.5, "             ")]
    //
    // Checking the Y axis:
    // (you can see the bird is "flying alongside" the foods)
    #[test_case(0.5, 0.0, "            +")]
    #[test_case(0.5, 0.1, "          + .")]
    #[test_case(0.5, 0.2, "         +  +")]
    #[test_case(0.5, 0.3, "        + +  ")]
    #[test_case(0.5, 0.4, "      +  +   ")]
    #[test_case(0.5, 0.6, "   +  +      ")]
    #[test_case(0.5, 0.7, "  + +        ")]
    #[test_case(0.5, 0.8, "+  +         ")]
    #[test_case(0.5, 0.9, ". +          ")]
    #[test_case(0.5, 1.0, "+            ")]
    fn test(x: f32, y: f32, expected_vision: &'static str) {
        TestCase {
            foods: vec![food(1.0, 0.4), food(1.0, 0.6)],
            fov_range: 1.0,
            fov_angle: FRAC_PI_2,
            rot: 0.0,
            x,
            y,
            expected_vision,
        }.run()
    }
}

/* ... */

We've got only one more parameter left to cover: field of view's angle.

We'll use the same framework, but imagining what happens in here is tiny bit more complicated (or at least it took me a minute to ensure the behavior is correct):

libs/simulation/src/eye.rs
/* ... */

mod different_fov_angles {
    use super::*;
    use test_case::test_case;

    /// World:
    ///
    /// ------------
    /// |%  %  %  %|
    /// |          |
    /// |    @>    |
    /// |          |
    /// |%  %  %  %|
    /// ------------
    ///
    /// Test cases:
    ///
    /// ------------
    /// |%  %  %/.%|
    /// |      /...|
    /// |    @>....|
    /// |      \\...|
    /// |%  %  %\\.%|
    /// ------------
    ///
    /// ------------
    /// |%  %|.%..%|
    /// |    |.....|
    /// |    @>....|
    /// |    |.....|
    /// |%  %|.%..%|
    /// ------------
    ///
    /// ... and so on, until we reach the full, 360° FOV
    #[test_case(0.25 * PI, " +         + ")] // FOV is narrow = 2 foods
    #[test_case(0.50 * PI, ".  +     +  .")]
    #[test_case(0.75 * PI, "  . +   + .  ")] // FOV gets progressively
    #[test_case(1.00 * PI, "   . + + .   ")] // wider and wider...
    #[test_case(1.25 * PI, "   . + + .   ")]
    #[test_case(1.50 * PI, ".   .+ +.   .")]
    #[test_case(1.75 * PI, ".   .+ +.   .")]
    #[test_case(2.00 * PI, "+.  .+ +.  .+")] // FOV is wide = 8 foods
    fn test(fov_angle: f32, expected_vision: &'static str) {
        TestCase {
            foods: vec![
                food(0.0, 0.0),
                food(0.0, 0.33),
                food(0.0, 0.66),
                food(0.0, 1.0),
                food(1.0, 0.0),
                food(1.0, 0.33),
                food(1.0, 0.66),
                food(1.0, 1.0),
            ],
            fov_range: 1.0,
            x: 0.5,
            y: 0.5,
            rot: 0.0,
            fov_angle,
            expected_vision,
        }.run()
    }
}

/* ... */

Nice:

cargo test --workspace
test result: ok. 49 passed; 0 failed

So — we've got eyez, but what about brainz? Fortunately, we've already implemented it!

libs/simulation/Cargo.toml
# ...

[dependencies]
# ...

lib-neural-network = { path = "../neural-network" }

# ...
libs/simuation/src/lib.rs
/* ... */

use lib_neural_network as nn;
use nalgebra as na;
use rand::{Rng, RngCore};

/* ... */
libs/simulation/src/animal.rs
/* ... */

#[derive(Debug)]
pub struct Animal {
    /* ... */
    crate eye: Eye,
    crate brain: nn::Network,
}

impl Animal {
    pub fn random(rng: &mut dyn RngCore) -> Self {
        let eye = Eye::default();

        let brain = nn::Network::random(
            rng,
            &[
                // The Input Layer
                //
                // Because our eye returns Vec<f32>, and our neural
                // network works on Vec<f32>, we can pass-through
                // numbers from eye into the neural network directly.
                //
                // Had our birdies had, I dunno, ears, we could do
                // something like: `eye.cells() + ear.nerves()` etc.
                nn::LayerTopology {
                    neurons: eye.cells(),
                },

                // The Hidden Layer
                //
                // There is no best answer as to "how many neurons
                // the hidden layer should contain" (or how many
                // hidden layers there should be, even - there could
                // be zero, one, two or more!).
                //
                // The rule of thumb is to start with a single hidden
                // layer that has somewhat more neurons that the input
                // layer, and see how well the network performs.
                nn::LayerTopology {
                    neurons: 2 * eye.cells(),
                },

                // The Output Layer
                //
                // Since the brain will control our bird's speed and
                // rotation, this gives us two numbers = two neurons.
                nn::LayerTopology { neurons: 2 },
            ],
        );

        Self {
            /* ... */
            eye,
            brain,
        }
    }

    /* ... */
}
libs/simulation/src/lib.rs
/* ... */

// FRAC_PI_2 = PI / 2.0; a convenient shortcut
use std::f32::consts::FRAC_PI_2;

/// Minimum speed of a bird.
///
/// Keeping it above zero prevents birds from getting stuck in one place.
const SPEED_MIN: f32 = 0.001;

/// Maximum speed of a bird.
///
/// Keeping it "sane" prevents birds from accelerating up to infinity,
/// which makes the simulation... unrealistic :-)
const SPEED_MAX: f32 = 0.005;

/// Speed acceleration; determines how much the brain can affect bird's
/// speed during one step.
///
/// Assuming our bird is currently flying with speed=0.5, when the brain
/// yells "stop flying!", a SPEED_ACCEL of:
///
/// - 0.1 = makes it take 5 steps ("5 seconds") for the bird to actually
///         slow down to SPEED_MIN,
///
/// - 0.5 = makes it take 1 step for the bird to slow down to SPEED_MIN.
///
/// This improves simulation faithfulness, because - as in real life -
/// it's not possible to increase speed from 1km/h to 50km/h in one
/// instant, even if your brain very much wants to.
const SPEED_ACCEL: f32 = 0.2;

/// Ditto, but for rotation:
///
/// - 2 * PI = it takes one step for the bird to do a 360° rotation,
/// - PI = it takes two steps for the bird to do a 360° rotation,
///
/// I've chosen PI/2, because - as our motto goes - this value seems
/// to play nice.
const ROTATION_ACCEL: f32 = FRAC_PI_2;

impl Simulation {
    /* ... */

    pub fn step(&mut self, rng: &mut dyn RngCore) {
        self.process_collisions(rng);
        self.process_brains();
        self.process_movements();
    }

    /* ... */

    fn process_brains(&mut self) {
        for animal in &mut self.world.animals {
            let vision = animal.eye.process_vision(
                animal.position,
                animal.rotation,
                &self.world.foods,
            );

            let response = animal.brain.propagate(vision);

            // ---
            // | Limits number to given range.
            // -------------------- v---v
            let speed = response[0].clamp(
                -SPEED_ACCEL,
                SPEED_ACCEL,
            );

            let rotation = response[1].clamp(
                -ROTATION_ACCEL,
                ROTATION_ACCEL,
            );

            // Our speed & rotation here are *relative* - that is: when
            // they are equal to zero, what the brain says is "keep
            // flying as you are now", not "stop flying".
            //
            // Both values being relative is crucial, because our bird's
            // brain doesn't know its own speed and rotation*, meaning
            // that it fundamentally cannot return absolute values.
            //
            // * they'd have to be provided as separate inputs to the
            //   neural network, which would make the evolution process
            //   waaay longer, if even possible.

            animal.speed =
                (animal.speed + speed).clamp(SPEED_MIN, SPEED_MAX);

            animal.rotation = na::Rotation2::new(
                animal.rotation.angle() + rotation,
            );

            // (btw, there is no need for ROTATION_MIN or ROTATION_MAX,
            // because rotation automatically wraps from 2*PI back to 0 -
            // we've already witnessed that when we were testing eyes,
            // inside `mod different_rotations { ... }`.)
        }
    }

    /* ... */
}

Does it work? Let's find out!

$ wasm-pack build
...
[INFO]: :-) Done in 12.20s
[INFO]: :-) Your wasm pkg is ready to publish at /home/pwy/Projects/...

Oh my, oh my, oh my!

Birds were flying from continent to continent long before we were. They reached the coldest place on Earth, Antarctica, long before we did. They can survive in the hottest of deserts. Some can remain on the wing for years at a time. They can girdle the globe.

— David Attenborough about our simulation (hypothesized)

What we see is enchanting: each bird, equipped with a randomized brain, decides where it wants to fly, trying to adjust its behavior to its surroundings.

Some of our birds fly in circles, some exhibit more complex behaviors — and, if you're lucky (try refreshing the page a few times!), what you'll see is a bird actually steering into the food, as if it understood.

Currently this is pure luck though; our next, and the last, milestone will be about teaching — we'll augment our simulation with the final piece of puzzle: the genetic algorithm.

Huggin' & Evolvin'

Even though our birds can fly, their brains are entirely random at the moment — in this chapter we'll see how we can integrate our simulation with a genetic algorithm, so that our birdies can learn & evolve.

Broadly speaking, we want to maximize the amount of food eaten per bird — that'll be our fitness function; and the way we'll achieve that is that we'll run the simulation for some time (called generation), note down how many foods have been eaten by each bird, and then, uhm, reproduce the best birdies.

Let's get to it!

libs/simulation/Cargo.toml
# ...

[dependencies]
# ...

lib-genetic-algorithm = { path = "../genetic-algorithm" }
lib-neural-network = { path = "../neural-network" }

# ...
libs/simulation/src/lib.rs
/* ... */

use lib_genetic_algorithm as ga;
use lib_neural_network as nn;
/* ... */
libs/simulation/src/lib.rs
/* ... */

/// How much `.step()`-s have to occur before we push data into the
/// genetic algorithm.
///
/// Value that's too low might prevent the birds from learning, while
/// a value that's too high will make the evolution unnecessarily
/// slower.
///
/// You can treat this number as "for how many steps each bird gets
/// to live"; 2500 was chosen with a fair dice roll.
const GENERATION_LENGTH: usize = 2500;

pub struct Simulation {
    world: World,
    ga: ga::GeneticAlgorithm<ga::RouletteWheelSelection>,
    age: usize,
}

impl Simulation {
    pub fn random(rng: &mut dyn RngCore) -> Self {
        let world = World::random(rng);

        let ga = ga::GeneticAlgorithm::new(
            ga::RouletteWheelSelection::default(),
            ga::UniformCrossover::default(),
            ga::GaussianMutation::new(0.01, 0.3),
            // ---------------------- ^--^ -^-^
            // | Chosen with a bit of experimentation.
            // |
            // | Higher values can make the simulation more chaotic,
            // | which - a bit counterintuitively - might allow for
            // | it to discover *better* solutions; but the trade-off
            // | is that higher values might also cause current, good
            // | enough solutions to be discarded.
            // ---
        );

        Self { world, ga, age: 0 }
    }

    /* ... */

    pub fn step(&mut self, rng: &mut dyn RngCore) {
        self.process_collisions(rng);
        self.process_brains();
        self.process_movements();

        self.age += 1;

        if self.age > GENERATION_LENGTH {
            self.evolve(rng);
        }
    }

    /* ... */

    fn evolve(&mut self, rng: &mut dyn RngCore) {
        self.age = 0;

        // Step 1: Prepare birdies to be sent into the genetic algorithm
        let current_population = todo!();

        // Step 2: Evolve birdies
        let evolved_population = self.ga.evolve(
            rng,
            &current_population,
        );

        // Step 3: Bring birdies back from the genetic algorithm
        self.world.animals = todo!();

        // Step 4: Restart foods
        //
        // (this is not strictly necessary, but it allows to easily spot
        // when the evolution happens - so it's more of a UI thing.)
        for food in &mut self.world.foods {
            food.position = rng.gen();
        }
    }
}

As you might remember, our GenenticAlgorithm::evolve() requires for the "evolvable" type to implement a trait called Individual:

libs/genetic-algorithm/src/lib.rs
pub fn evolve<I>(
    &self,
    rng: &mut dyn RngCore,
    population: &[I],
) -> (Vec<I>, Statistics)
where
    I: Individual

... so a naïve approach could be to simply implement Individual for Animal — after all, birdies are the thing we want to evolve:

libs/simulation/src/animal.rs
/* ... */

impl ga::Individual for Animal {
    fn create(chromosome: ga::Chromosome) -> Self {
        todo!()
    }

    fn chromosome(&self) -> &ga::Chromosome {
        todo!()
    }

    fn fitness(&self) -> f32 {
        todo!()
    }
}

But as soon as we try to actually implement those functions, we quickly get backed into a corner — for instance: how can we implement fn chromosome() that returns a reference to ga::Chromosome if our Animal doesn't contain a field called chromosome?

libs/simulation/src/animal.rs
/* ... */

impl ga::Individual for Animal {
    /* ... */

    fn chromosome(&self) -> &ga::Chromosome {
       &self.what // :'-(
    }

    /* ... */
}

Granted, you could say that since we control code inside lib-genetic-algorithm, we can just change fn chromosome() to work on owned Chromosome-s instead — and you'd be right! But this doesn't actually solve the underlying design issue, merely pushes it somewhere else:

libs/simulation/src/animal.rs
/* ... */

impl ga::Individual for Animal {
    fn create(chromosome: ga::Chromosome) -> Self {
        Self {
            position: rng.gen(), // err: we don't have access to PRNG
                                 // in here!
            /* ... */
        }
    }

    /* ... */
}

So, for the sake of argument, let's assume that our ga::Individual is designed correctly — how can we integrate Animal with it, then?

Most easily — by creating a dedicated struct:

libs/simulation/src/lib.rs
/* ... */

mod animal;
mod animal_individual;
/* ... */

use self::animal_individual::*;
use lib_genetic_algorithm as ga;
use lib_neural_network as nn;
/* ... */
libs/simulation/src/animal_individual.rs
use crate::*;

pub struct AnimalIndividual;

impl ga::Individual for AnimalIndividual {
    fn create(chromosome: ga::Chromosome) -> Self {
        todo!()
    }

    fn chromosome(&self) -> &ga::Chromosome {
        todo!()
    }

    fn fitness(&self) -> f32 {
        todo!()
    }
}

As we see, this structure has to contain at least those two fields:

libs/simulation/src/animal_individual.rs
use crate::*;

pub struct AnimalIndividual {
    fitness: f32,
    chromosome: ga::Chromosome,
}

impl ga::Individual for AnimalIndividual {
    fn create(chromosome: ga::Chromosome) -> Self {
        Self {
            fitness: 0.0,
            chromosome,
        }
    }

    fn chromosome(&self) -> &ga::Chromosome {
        &self.chromosome
    }

    fn fitness(&self) -> f32 {
        self.fitness
    }
}

Let's go back to fn evolve() and see how it fits there:

libs/simulation/src/lib.rs
/* ... */

fn evolve(&mut self, rng: &mut dyn RngCore) {
    self.age = 0;

    // Transforms `Vec<Animal>` to `Vec<AnimalIndividual>`
    let current_population: Vec<_> = self
        .world
        .animals
        .iter()
        .map(|animal| convert Animal to AnimalIndividual)
        .collect();

    // Evolves this `Vec<AnimalIndividual>`
    let evolved_population = self.ga.evolve(
        rng,
        &current_population,
    );

    // Transforms `Vec<AnimalIndividual>` back into `Vec<Animal>`
    self.world.animals = evolved_population
        .into_iter()
        .map(|individual| convert AnimalIndividual to Animal)
        .collect();

    for food in &mut self.world.foods {
        food.position = rng.gen();
    }
}

/* ... */

Seems like this might just work!

To implement those .map()-s, we'll need two conversion methods:

libs/simulation/src/animal_individual.rs
/* ... */

impl AnimalIndividual {
    pub fn from_animal(animal: &Animal) -> Self {
        todo!()
    }

    pub fn into_animal(self, rng: &mut dyn RngCore) -> Animal {
        todo!()
    }
}

/* ... */

... which allow us to:

libs/simulation/src/lib.rs
/* ... */

fn evolve(&mut self, rng: &mut dyn RngCore) {
    /* ... */

    let current_population: Vec<_> = self
        .world
        .animals
        .iter()
        .map(AnimalIndividual::from_animal)
        .collect();

    /* ... */

    self.world.animals = evolved_population
        .into_iter()
        .map(|individual| individual.into_animal(rng))
        .collect();

    /* ... */
}

/* ... */

Ok, so: how can we implement those two conversion methods?

from_animal

Let's bring into the picture the important bits:

libs/simulation/src/animal_individual.rs
/* ... */

pub struct AnimalIndividual {
    fitness: f32,
    chromosome: ga::Chromosome,
}

impl AnimalIndividual {
    pub fn from_animal(animal: &Animal) -> Self {
        Self {
            fitness: todo!(),
            chromosome: todo!(),
        }
    }

    /* ... */
}

/* ... */

What are we supposed to do inside ::from_animal()? Well, looks like two things:

  1. determine animal's fitness score,

  2. determine animal's chromosome (aka genotype).

Finding out fitness score is pretty easy — since we already handle collisions, all we've gotta do is to count them:

libs/simulation/src/animal.rs
/* ... */

#[derive(Debug)]
pub struct Animal {
    /* ... */

    /// Number of foods eaten by this animal
    crate satiation: usize,
}

impl Animal {
    pub fn random(rng: &mut dyn RngCore) -> Self {
        /* ... */

        Self {
            /* ... */
            satiation: 0,
        }
    }

    /* ... */
}

/* ... */
libs/simulation/src/lib.rs
/* ... */

impl Simulation {
    /* ... */

    fn process_collisions(&mut self, rng: &mut dyn RngCore) {
        for animal in &mut self.world.animals {
            for food in &mut self.world.foods {
                /* ... */

                if distance <= 0.01 {
                    animal.satiation += 1;
                    food.position = rng.gen();
                }
            }
        }
    }

    /* ... */
}

/* ... */
libs/simulation/src/animal_individual.rs
/* ... */

impl AnimalIndividual {
    pub fn from_animal(animal: &Animal) -> Self {
        Self {
            fitness: animal.satiation as f32,
            chromosome: todo!(),
        }
    }

    /* ... */
}

/* ... */

Ah, I love when all the pieces just fit together — don't ya'?

When it comes to the second field, chromosome, there'll be a bit more work there. As a reminder, what we mean by chromosome here is weights of the neural network; so ideally we'd write:

libs/simulation/src/animal_individual.rs
/* ... */

impl AnimalIndividual {
    pub fn from_animal(animal: &Animal) -> Self {
        Self {
            /* ... */
            chromosome: animal.brain.weights(),
        }
    }

    /* ... */
}

/* ... */

... but our lib-neural-network-'s Network doesn't have such method…​ yet!

To implement .weights(), let's go back to lib-neural-network — what we're looking for is:

libs/neural-network/src/lib.rs
/* ... */

impl Network {
    /* ... */

    pub fn weights(&self) -> Vec<f32> {
        todo!()
    }
}

/* ... */

'cause we're good programmers, let's start with a test:

libs/neural-network/src/lib.rs
/* ... */

#[cfg(test)]
mod tests {
    /* ... */

    mod weights {
        use super::*;

        #[test]
        fn test() {
            let network = Network::new(vec![
                Layer::new(vec![Neuron::new(0.1, vec![0.2, 0.3, 0.4])]),
                Layer::new(vec![Neuron::new(0.5, vec![0.6, 0.7, 0.8])]),
            ]);

            let actual = network.weights();
            let expected = vec![0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8];

            approx::assert_relative_eq!(
                actual.as_slice(),
                expected.as_slice(),
            );
        }
    }
}

As for the implementation, I'll show you two of them — one uses explicit for loops, while the other works on combinators; barring some preallocation stuff, both are equivalent:

  1. Explicit loops:

    libs/neural-network/src/lib.rs
    pub fn weights(&self) -> Vec<f32> {
        let mut weights = Vec::new();
    
        for layer in &self.layers {
            for neuron in &layer.neurons {
                weights.push(neuron.bias);
    
                for weight in &neuron.weights {
                    weights.push(*weight);
                }
            }
        }
    
        weights
    }
    
  2. Combinators:

    libs/neural-network/src/lib.rs
    pub fn weights(&self) -> Vec<f32> {
        use std::iter::once;
    
        self.layers
            .iter()
            .flat_map(|layer| layer.neurons.iter())
            .flat_map(|neuron| once(&neuron.bias).chain(&neuron.weights))
            .copied()
            .collect()
    }
    

I consider the combinator approach more idiomatic as it allows to avoid allocating any vector:

pub fn weights(&self) -> impl Iterator<Item = f32> + '_ {
    self.layers
        .iter()
        .flat_map(|layer| layer.neurons.iter())
        .flat_map(|neuron| once(&neuron.bias).chain(&neuron.weights))
        .copied()
}

... but, when push comes to shove, maintenability is usually more important than performance, so choose whichever version you prefer :-)

Also, while we're here, let's implement an inverse method we'll need later — ::from_weights():

/* ... */

impl Network {
    /* ... */

    pub fn from_weights(
        layers: &[LayerTopology],
        weights: impl IntoIterator<Item = f32>,
    ) -> Self {
        todo!()
    }

    /* ... */
}

/* ... */

Ideally, we'd like for the following identity to hold:

network == Network::from_weights(network.weights())

... so let's base our tests exactly on that:

/* ... */

#[cfg(test)]
mod tests {
    /* ... */

    mod from_weights {
        use super::*;

        #[test]
        fn test() {
            let layers = &[
                LayerTopology { neurons: 3 },
                LayerTopology { neurons: 2 },
            ];

            let weights = vec![0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8];

            let network = Network::from_weights(layers, weights.clone());
            let actual: Vec<_> = network.weights().collect();

            approx::assert_relative_eq!(
                actual.as_slice(),
                weights.as_slice(),
            );
        }
    }

    /* ... */
}

... and then an example implementation could be:

libs/neural-network/src/lib.rs
/* ... */

impl Network {
    /* ... */

    pub fn from_weights(
        layers: &[LayerTopology],
        weights: impl IntoIterator<Item = f32>,
    ) -> Self {
        assert!(layers.len() > 1);

        let mut weights = weights.into_iter();

        let layers = layers
            .windows(2)
            .map(|layers| {
                Layer::from_weights(
                    layers[0].neurons,
                    layers[1].neurons,
                    &mut weights,
                )
            })
            .collect();

        if weights.next().is_some() {
            panic!("got too many weights");
        }

        Self { layers }
    }

    /* ... */
}

impl Layer {
    /* ... */

    pub fn from_weights(
        input_size: usize,
        output_size: usize,
        weights: &mut dyn Iterator<Item = f32>,
    ) -> Self {
        let neurons = (0..output_size)
            .map(|_| Neuron::from_weights(input_size, weights))
            .collect();

        Self { neurons }
    }

    /* ... */
}

impl Neuron {
    /* ... */

    pub fn from_weights(
        output_neurons: usize,
        weights: &mut dyn Iterator<Item = f32>,
    ) -> Self {
        let bias = weights.next().expect("got not enough weights");

        let weights = (0..output_neurons)
            .map(|_| weights.next().expect("got not enough weights"))
            .collect();

        Self { bias, weights }
    }

    /* ... */
}

Recreating network from weights is quite complex, so don't worry if this code takes a moment to sink-in — took a while to write, too!

Refactoring

Our Network has now everything we need to make it compatible with genetic algorithm — but before we do that, let's take a moment to refactor one thing.

Inside our Animal, what we have now is:

libs/simulation/src/animal.rs
/* ... */

#[derive(Debug)]
pub struct Animal {
    /* ... */
    crate brain: nn::Network,
    /* ... */
}

/* ... */

... and what I have on mind is to refactor brain: nn::Network into a distinct, em, body part:

libs/simulation/src/lib.rs
/* ... */

pub use self::{animal::*, brain::*, eye::*, food::*, world::*};

mod animal;
mod animal_individual;
mod brain;
/* ... */
libs/simulation/src/brain.rs
use crate::*;

#[derive(Debug)]
pub struct Brain {
    crate nn: nn::Network,
}

impl Brain {
    pub fn random(rng: &mut dyn RngCore, eye: &Eye) -> Self {
        Self {
            nn: nn::Network::random(rng, &Self::topology(eye)),
        }
    }

    crate fn as_chromosome(&self) -> ga::Chromosome {
        self.nn.weights().collect()
    }

    fn topology(eye: &Eye) -> [nn::LayerTopology; 3] {
        [
            nn::LayerTopology {
                neurons: eye.cells(),
            },
            nn::LayerTopology {
                neurons: 2 * eye.cells(),
            },
            nn::LayerTopology { neurons: 2 },
        ]
    }
}
libs/simulation/src/animal.rs
/* ... */

#[derive(Debug)]
pub struct Animal {
    /* ... */
    crate brain: Brain,
    /* ... */
}

impl Animal {
    pub fn random(rng: &mut dyn RngCore) -> Self {
        let eye = Eye::default();
        let brain = Brain::random(rng, &eye);

        Self::new(eye, brain, rng)
    }

    crate fn as_chromosome(&self) -> ga::Chromosome {
        // We evolve only our birds' brains, but technically there's no
        // reason not to simulate e.g. physical properties such as size.
        //
        // If that was to happen, this function could be adjusted to
        // return a longer chromosome that encodes not only the brain,
        // but also, say, birdie's color.

        self.brain.as_chromosome()
    }

    /* ... */

    fn new(eye: Eye, brain: Brain, rng: &mut dyn RngCore) -> Self {
        Self {
            position: rng.gen(),
            rotation: rng.gen(),
            speed: 0.002,
            eye,
            brain,
            satiation: 0,
        }
    }
}
libs/simulation/src/lib.rs
fn process_brains(&mut self) {
    for animal in &mut self.world.animals {
        /* ... */

        let response = animal.brain.nn.propagate(vision);

        /* ... */
    }
}

All this allows us to complete AnimalIndividual::from_animal():

libs/simulation/src/animal_individual.rs
/* ... */

impl AnimalIndividual {
    pub fn from_animal(animal: &Animal) -> Self {
        Self {
            fitness: animal.satiation as f32,
            chromosome: animal.as_chromosome(),
        }
    }

    /* ... */
}

/* ... */

Once again, all the pieces fit together 🥳

into_animal

With our latest changes we can transform Animal into AnimalIndividual and send it into the genetic algorithm — now it's time to implement the reverse operation: given a brand-new AnimalIndividual fresh from the genetic algorithm, we have to convert it into Animal:

libs/simulation/src/animal_individual.rs
/* ... */

impl AnimalIndividual {
    /* ... */

    pub fn into_animal(self, rng: &mut dyn RngCore) -> Animal {
        Animal::from_chromosome(self.chromosome, rng)
    }
}

/* ... */
libs/simulation/src/animal.rs
/* ... */

impl Animal {
    /* ... */

    /// "Restores" bird from a chromosome.
    ///
    /// We have to have access to the PRNG in here, because our
    /// chromosomes encode only the brains - and while we restore the
    /// bird, we have to also randomize its position, direction, etc.
    /// (so it's stuff that wouldn't make sense to keep in the genome.)
    crate fn from_chromosome(
        chromosome: ga::Chromosome,
        rng: &mut dyn RngCore,
    ) -> Self {
        let eye = Eye::default();
        let brain = Brain::from_chromosome(chromosome, &eye);

        Self::new(eye, brain, rng)
    }

    crate fn as_chromosome(&self) -> ga::Chromosome {
        self.brain.as_chromosome()
    }

    /* ... */
}

/* ... */
libs/simulation/src/brain.rs
/* ... */

impl Brain {
    /* ... */

    crate fn from_chromosome(
        chromosome: ga::Chromosome,
        eye: &Eye,
    ) -> Self {
        Self {
            nn: nn::Network::from_weights(
                &Self::topology(eye),
                chromosome,
            ),
        }
    }

    crate fn as_chromosome(&self) -> ga::Chromosome {
        self.nn.weights().collect()
    }

    /* ... */
}

Looks like…​ we're done! Are we done??

Ready, Set…​

We're kinda-sorta done — while you could just launch wasm-pack build, take your binoculars and start to watch wildlife freely flying and electively evolving on your screen now, there are two things we can do to make this experience more rewarding:

  1. First of all: since evolution happens once every 2500 steps, and we perform 60 steps per second (there's one step per one frame, and the browser tries to keep steady 60 FPS), then in real-time we're talking about one evolution per ~40 seconds.

    If we wanted to witness birdies getting smarter and smarter, we'd have to wait around 10 generations (speaking from experience), so roughly 6.5 minutes. 6.5 minutes of bluntly staring into the screen — what a waste of time!

    (though i'm very into this kind of stuff — there's no screentime-shaming on this blog, my pal)

    But if we had some kind of a "fast-forward" button…​

  2. Second of all: even if evolution works (with big emphasis on if, 'cause - you know - we're skeptics!), at the moment we'd have no way of knowing.

    I mean, do our current birds really fly better than those from five minutes ago?

    Luckily to us, because we're digital, finding evidence for evolution gets pretty easy: we'll just enhance lib-genetic-algorithm so that it returns statistics — such as an average fitness score — and we'll use console.log() to see if those statistics grow!

<slowly-breaths-out/>

Our journey heads towards its end — the code that we'll write in a moment will be the culminating point of all the hard work we've done over the past months. I'd like to thank you for taking the time to go through all of this, and I hope this project was at least partially as interesting to you as it was to me.

So, my friend — are you ready to knock on wood and begin our final birdie-adventure?

Fast-Forward & Statistics

Inside our JavaScript code we invoke .step() only during redraw() — that's what makes our simulation "stuck" to 60 FPS:

www/index.js
/* ... */

function redraw() {
    /* ... */

    simulation.step();

    /* ... */
}

/* ... */

To make our simulation faster, we could either invoke .step() many times at once:

www/index.js
/* ... */

function redraw() {
    /* ... */

    // Performs 10 steps per frame, which makes simulation 10x faster
    // (at least if your computer can catch up!)
    for (let i = 0; i < 10; i += 1) {
        simulation.step();
    }

    /* ... */
}

/* ... */

... or, a bit better, we could provide a dedicated method that "fast-forwards" an entire generation; this way we could keep the simulation running at 1x speed, and only bind this "fast-forwarding" to a button; make it fast-forward on-demand.

To use a shorter noun, instead of calling it fn fast_forward(), let's go with fn train():

libs/simulation/src/lib.rs
/* ... */

impl Simulation {
    /* ... */

    pub fn step(&mut self, rng: &mut dyn RngCore) -> bool {
        /* ... */

        self.age += 1;

        if self.age > GENERATION_LENGTH {
            self.evolve(rng);
            true
        } else {
            false
        }
    }

    /// Fast-forwards 'till the end of the current generation.
    pub fn train(&mut self, rng: &mut dyn RngCore) {
        loop {
            if self.step(rng) {
                return;
            }
        }
    }

    /* ... */
}
libs/simulation-wasm/src/lib.rs
/* ... */

#[wasm_bindgen]
impl Simulation {
    /* ... */

    pub fn train(&mut self) {
        self.sim.train(&mut self.rng);
    }
}

/* ... */
www/index.html
<!-- ... -->
<style>
  /* ... */

  #train {
      position: absolute;
      top: 0;
      margin: 15px;
  }
</style>
<body>
  <canvas id="viewport" width="800" height="800"></canvas>
  <button id="train">train please, thank u</button>
  <script src="./bootstrap.js"></script>
</body>
<!-- ... -->
www/index.js
import * as sim from "lib-simulation-wasm";

let simulation = new sim.Simulation();

document.getElementById('train').onclick = function() {
    simulation.train();
};

const viewport = document.getElementById('viewport');
const viewportScale = window.devicePixelRatio || 1;

/* ... */

Ok, now that we can speed-up the evolution, let's get our hands dirty with statistics — the simplest thing we have at hand are fitness scores, so lib-genetic-algorithm seems like a nice place to implement them:

libs/genetic-algorithm/src/lib.rs
/* ... */

#[derive(Clone, Debug)]
pub struct Statistics {
    min_fitness: f32,
    max_fitness: f32,
    avg_fitness: f32,
}

/* ... */

impl<S> GeneticAlgorithm<S>
where
    S: SelectionMethod,
{
    /* ... */

    pub fn evolve<I>(/* ... */) -> (Vec<I>, Statistics)
    where
        I: Individual,
    {
        assert!(!population.is_empty());

        let new_population = (0..population.len())
            .map(|_| {
                /* ... */
            })
            .collect();

        let stats = Statistics::new(population);

        (new_population, stats)
    }
}

/* ... */

impl Statistics {
    fn new<I>(population: &[I]) -> Self
    where
        I: Individual,
    {
        assert!(!population.is_empty());

        let mut min_fitness = population[0].fitness();
        let mut max_fitness = min_fitness;
        let mut sum_fitness = 0.0;

        for individual in population {
            let fitness = individual.fitness();

            min_fitness = min_fitness.min(fitness);
            max_fitness = max_fitness.max(fitness);
            sum_fitness += fitness;
        }

        Self {
            min_fitness,
            max_fitness,
            avg_fitness: sum_fitness / (population.len() as f32),
        }
    }

    pub fn min_fitness(&self) -> f32 {
        self.min_fitness
    }

    pub fn max_fitness(&self) -> f32 {
        self.max_fitness
    }

    pub fn avg_fitness(&self) -> f32 {
        self.avg_fitness
    }
}
/* ... */

impl Simulation {
    /* ... */

    pub fn step(
        &mut self,
        rng: &mut dyn RngCore,
    ) -> Option<ga::Statistics> {
        /* ... */

        if self.age > GENERATION_LENGTH {
            Some(self.evolve(rng))
        } else {
            None
        }
    }

    pub fn train(&mut self, rng: &mut dyn RngCore) -> ga::Statistics {
        loop {
            if let Some(summary) = self.step(rng) {
                return summary;
            }
        }
    }

    /* ... */

    fn evolve(&mut self, rng: &mut dyn RngCore) -> ga::Statistics {
        /* ... */

        let (evolved_population, stats) = self.ga.evolve(
        /* ... */

        stats
    }
}
libs/simulation-wasm/src/lib.rs
/* ... */

#[wasm_bindgen]
impl Simulation {
    /* ... */

    /// min = minimum amount of food eaten by any bird
    ///
    /// max = maximum amount of food eaten by any bird
    ///
    /// avg = sum of all the food eaten by all the birds,
    ///       divided by the number of birds
    ///
    /// Median could also come useful!
    pub fn train(&mut self) -> String {
        let stats = self.sim.train(&mut self.rng);

        format!(
            "min={:.2}, max={:.2}, avg={:.2}",
            stats.min_fitness(),
            stats.max_fitness(),
            stats.avg_fitness()
        )
    }
}
www/index.js
/* ... */

document.getElementById('train').onclick = function() {
    console.log(simulation.train());
};

/* ... */

This time, when building, don't forget about the --release switch — it enables optimizations which are crucial to get .train() working at a reasonable performance:

$ wasm-pack build --release
...
[INFO]: :-) Done in 40.00s
[INFO]: :-) Your wasm pkg is ready to publish at /home/pwy/Projects/...

Ready, Set, Go!

Finally, ultimately, eventually, at long — the outcome of our diligent, assiduous coding; u ready?

🎉

Nice?

Nice!

Closing Thoughts

Started from the bottom, haven't we?

Started from rough sketches, got through our very first struct Network, designed genetic algorithm, implemented tests for eyes (how awesome is that!), to end up with a bunch of self-governing birdies that certainly don't seem to look like this much code on the surface :-)

Since I've already done the sentimental part in the previous section, in here let me just re-thank you for your time — I hope this series showed you a fair share of Rust idioms, testing techniques, and delivered on its promise of using WebAssembly in an interesting way.

And, champ, that's for you:

A shorelark (or at least my attempt at drawing one)

What now?

If you want to fiddle a bit on your own, there's still a few things to do here, simulation-wise!

You remember all those constants such as FOV_RANGE?

If instead of keeping them hard-coded, you made them configurable via some struct Config, you could then create an application that'd traverse different combinations of those parameters, trying to find the most optimal ones:

let mut stats = Vec::new();

for fov_range in vec![0.1, 0.2, 0.3, 0.4, ..., PI] {
    for fov_distance in vec![0.1, 0.2, 0.3, 0.4, ..., 1.0] {
        let current_stats = run_simulation(
            fov_range,
            fov_distance,
            /* ... */,
        );

        stats.push((fov_range, fov_distance, current_stats));
    }
}

// TODO using `stats`, find out which combinations yielded the best
//      results :-)

Bonus points for using rayon!

As a reminder: the entire source code, a bit refactored, is available at my GitHub; if you just skimmed this article and/or don't feel like copy-pasting all the snippets, you can simply clone that repository and start from there.

What’s next?

I've got a few ideas on mind — I'm thinking ATmega328p + Rust + light = <3; we'll see how things play out :-)

Until next time!