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

Note

No worries if JavaScript or HTML are unfamiliar to you — I’ll try to explain various concepts as we go.

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!

design 4

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:

9af5a3d9 83f9 47eb b191 7ee523846ecf
Figure 2. 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:

  • npm (like Cargo, but for JavaScript),

  • wasm-pack (set of tools that make compiling Rust into WebAssembly easier).

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

Note

If you’re into Nix, installing both applications is as easy as creating a file called shell.nix:

shell.nix

let
  pkgs = import <nixpkgs> { };

in
  pkgs.mkShell {
    buildInputs = with pkgs; [
      nodejs
      wasm-pack
    ];
  }

... and executing nix-shell.

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:

Note

Formally, this kind of "talking to another system" module is known as a bridge or an interop.

$ 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)
Note

By the way, I’ve gotta apologize as I’ve made a small mistake in the previous two parts: our cargo new was missing the --name parameter.

This parameter affects the value of name inside a manifest, meaning that we should’ve had:

libs/genetic-algorithm/Cargo.toml

[package]
name = "lib-genetic-algorithm"

# instead of:
# name = "genetic-algorithm"

# ...

libs/neural-network/Cargo.toml

[package]
name = "lib-neural-network"

# instead of:
# name = "neural-network"

# ...

This is a minor thing that I consider a good practice — by prefixing workspace-crates, you reduce the risk of your local crate name-clashing with something from crates.io.

Say, we’re about to create libs/rand — by calling it lib-rand instead of just rand, we can avoid confusing other programmers who might stumble upon our code in the future.

Similar approaches include:

  • prefixing with project’s name (that’s what rustc does, for example),

  • prefixing with whatever else you want (e.g. local-foo or crate_foo),

  • not prefixing at all (also valid!).

Please, fix those two manifests, and let’s get going.

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"]
    
    Note

    Compiler transforms code into something, and crate-type determines what that something — also called an artifact — gets to be:

    • crate-type = ["bin"] means: compiler, pretty please produce a program
      (e.g. an .exe file for Windows),

    • crate-type = ["lib"] means: compiler, pretty please produce a library
      (e.g. a .dll file for Windows, .so for Linux).

    Where:

    • a program is something that you can execute directly (e.g. from your terminal),

    • a library is a piece of code that provides functions for others to use.

    The type we have to use, cdylib, stands for C dynamic library, and it tells the compiler:

    • that it should export only those functions which are intended to be called from outside, ignoring Rust-specific internal stuff.

      This prevents bloating the library with "useless" metadata, and so it’s important for WebAssembly (we don’t want our users to go bankrupt over internet bills, do we?).

    • that it should generate a dynamic library — that is: a piece of code that will get invoked by somebody else.

      This is required for WebAssembly, because — as you’ll see in a moment — our Rust code won’t run standalone: it’ll be at JavaScript’s beck and call.

      In practice, what this means is that we won’t have any fn main() { …​ }, but rather pub fn do_something() { …​ }.

  2. We have to include wasm-bindgen in our dependencies:

    libs/simulation-wasm/Cargo.toml

    # ...
    
    [dependencies]
    wasm-bindgen = "0.2"
    
    Note

    wasm-bindgen provides types and macros that facilitate writing WebAssembly-aware code.

    It is possible to write Rust + WebAssembly without it — just less convenient.

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()
}
Note

Simplifying a bit, the #[wasm_bindgen] procedural macro informs the compiler that you want to export given function or type — that is: make it visible on the JavaScript’s side.

All Rust symbols eventually are compiled into WebAssembly, but only those prepended with #[wasm_bindgen] can be invoked from the JavaScript code directly.

If you’re curious, you can further use cargo-expand to inspect what this macro does:

$ cargo expand

use wasm_bindgen::prelude::*;

pub fn whos_that_dog() -> String {
    "Mister Peanutbutter".into()
}

//  v--------v
pub extern "C" fn __wasm_bindgen_generated_whos_that_dog() ->
    <String as wasm_bindgen::convert::ReturnWasmAbi>::Abi
{
    let _ret = { whos_that_dog() };
    <String as wasm_bindgen::convert::ReturnWasmAbi>::return_abi(_ret)
}
//  ^ `extern` informs compiler (and linker) that this function must
//  | be exported (it must be visible from outside the Rust code).
//  |
//  | While `pub` determines how given symbol is visible _inside_ Rust
//  | code, `extern` says "other languages should be able to invoke
//  | this function, too".
//  |
//  | `"C"` determines a so-called application binary interface (ABI),
//  | which describes _how exactly_ the function gets to be exported
//  | (there are many different conventions that define how parameters
//  | and return values must be passed in order to be understood "on
//  | the other side").
//  |
//  | If you want to know more - which it's not required to follow
//  | the article - there's:
//  |
//  | https://doc.rust-lang.org/reference/items/external-blocks.html#abi
//  ---

... and if you’re even more curious, then you’ll like the rustwasm book :-)

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:

  • package.json is like npm-'s Cargo.toml — it contains metadata about the module itself:

    libs/simulation-wasm/pkg/package.json

    {
      "name": "lib-simulation-wasm",
      "collaborators": [
        "Patryk Wychowaniec <pwychowaniec@pm.me>"
      ],
      "version": "0.1.0",
      /* ... */
    }
  • lib_simulation_wasm.d.ts contains forward declarations for IDEs to provide type hints:

    libs/simulation-wasm/pkg/lib_simulation_wasm.d.ts

    /**
     * @returns {string}
     */
    export function whos_that_dog(): string;
  • lib_simulation_wasm_bg.wasm is the essence, as it contains the WebAssembly bytecode of our crate; it’s like .dll or .so, and you can use wabt to inspect it (mainly for fun, I guess):

    $ wasm2wat pkg/lib_simulation_wasm_bg.wasm

    (module
      (func (type 1) (param i32) (result i32)
        (local i32 i32 i32 i32)
        global.get 0
        i32.const 16
        i32.sub
        local.tee 11
        ;; ...
  • lib_simulation_wasm_bg.js contains a rather spine-chilling code that actually invokes our WebAssembly library:

    libs/simulation-wasm/pkg/lib_simulation_wasm_bg.js

    /**
     * @returns {string}
     */
    export function whos_that_dog() {
        try {
            const retptr = wasm.__wbindgen_add_to_stack_pointer(-16);
            wasm.whos_that_dog(retptr);
            var r0 = getInt32Memory0()[retptr / 4 + 0];
            var r1 = getInt32Memory0()[retptr / 4 + 1];
            return getStringFromWasm0(r0, r1);
        } finally {
            wasm.__wbindgen_add_to_stack_pointer(16);
            wasm.__wbindgen_free(r0, r1);
        }
    }
    Note

    Wait — if our Rust code does next to nothing:

    libs/simulation-wasm/src/lib.rs

    pub fn whos_that_dog() -> String {
        "Mister Peanutbutter".into()
    }

    ... then why does that piece look so complex?

    Well, in short, it’s because WebAssembly doesn’t support strings — and wasm-pack, being neat, transparently hacks its way around it.

    But first, the terminology:

    • When you move a value from one function into another, when both functions work in different environments and/or when they are written in different languages, you make it cross the foreign function interface (FFI) boundary:

      962da22e fe0c 49b1 afb6 c333e5a18447

      In this case we’d say that our fn whos_that_dog() returns a String that crosses the FFI boundary from Rust (where it’s created) into JavaScript (where it’s used).

      Crossing the FFI boundary is a big deal, because different languages tend to have different memory representations of objects — so even if Rust’s struct Foo and JavaScript’s class Foo look alike on the surface, their memory layout is different.

      This means that when you want to send a value from one language into another, you cannot just say "hey, there’s a few bytes at 0x0000CAFE - that’s Foo" — instead, you have to convert that value into something the other party can understand:

      d152e743 8a56 4f39 8376 ce72bca8c88c

      (so it’s just like speech: while you can’t show somebody what’s inside your head, you can describe it — serialize — using words.)

    • When you convert a value into another representation, you serialize it.

      For instance, a type such as this one:

      struct Foo {
          value: String,
      }

      ... can be serialized into, say, JSON that looks like this:

      {
        "value": "Hi!"
      }

      ... which can be then easily deserialized on the JavaScript’s side:

      const foo = JSON.parse('{ "value": "Hi!" }');
      console.log(foo);

      (serialization isn’t limited to human-readable formats such as JSON, YAML or XML - there’s also e.g. Protocol Buffers.)

    Now:

    While both Rust and JavaScript support strings, WebAssembly understands mostly numbers — this means that all the functions that we export via #[wasm_bindgen] might accept and return at most a handful of numbers (from WebAssembly’s point of view).

    This means that in order to return a string, wasm-pack had to get creative — it generated this boi we’ve already seen a moment ago:

    (generated automatically during compilation)

    pub extern "C" fn __wasm_bindgen_generated_whos_that_dog()
        -> <String as ReturnWasmAbi>::Abi
    {
        let _ret = { whos_that_dog() };
        <String as ReturnWasmAbi>::return_abi(_ret)
    }

    In general, this is known as shim (or glue-function, or glue-code).

    This one converts Rust’s String into a pair of numbers — following the JavaScript code:

    • r0 which determines location of returned string in memory (it’s good-old pointer),

    • r1 which determines length of returned string.

    Those two numbers are then used by getStringFromWasm0() to recreate ("deserialize") the string on JavaScript’s side — all without us having to lift a single finger.

    Pretty neat!

    (to avoid diluting this article — if you’re further interested in WebAssembly’s memory model, here’s a nice introduction.)

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:

  • <something> is called a tag,

  • a tag has an opening: <something>; and an ending: </something>,

  • a tag might contain attributes: key="value",

  • a tag might contain children (i.e. more tags inside of it).

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:

  • html wraps the entire document,

  • head contains document’s metadata (such as its language or title),

  • body contains document’s contents,

  • script loads and executes a JavaScript file,

  • p (not used here, just provided as an example) prints text,

  • b (ditto) prints text in bold:

    <body>
      <p>yes... ha ha ha... <b>yes!</b></p>
    </body>
    ab2b7ba1 2fbb 44a7 8126 592e2c8f4a1f

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 😅

Note

Since this is the second time I say "like Cargo", it’s time to get more specific:

Cargo does all of those things on its own (how comfy!), but for JavaScript we need those two, separate applications.

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
    Note

    This command might print a few scary-looking messages:

    npm WARN optional SKIPPING OPTIONAL DEPENDENCY: ...
    found 362 vulnerabilities (348 low, 4 moderate, 10 high)
      run `npm audit fix` to fix them, or `npm audit` for details

    ... but worry not — that’s just npm being npm; if it succeeds, then everything’s alright.

  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() + "!");
    
    Note

    There’s no function main() { } — that’s because JavaScript doesn’t need one: all the code gets to be executed top-down (more or less, at least).

    they’re savages, I know! /s

  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:

42ca83b3 8949 4b70 aa72 3b1b1a8bed17

yay 🎉 yay

Note

By the way: when npm run start is working, it automatically listens for changes.

If you’d like to modify this alert’s message, simply go back to lib.rs, do whatever you want, run wasm-pack build, and — in a few seconds — the site should automatically reload.

The same applies for HTML and JS, though you don’t have to re-run wasm-pack then.

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:

design 4

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: ?,
}
Note

Fun Related Note

Here, we’re designing our models using object-oriented programming — although that’s a correct approach, it’s not the only one!

There exists a marvelous pattern called entity-component-system which allows to express certain model <-> property relations (such as animal <-> position) in a bit different, cleaner-when-there-are-lots-of-properties way.

Using ECS goes beyond the scope of this article, so I’m merely sowing a seed if you happen to be looking for a cool design pattern to learn in the future.

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!

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,
}

/* ... */
Note

Overall, rotation and speed can be also represented together as a vector:

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

We’ll continue with two separate fields, because it makes certain computations easier later, but should you though feel adventurous…​

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?

  • world? ✅ exists

  • animals? ✅ exist

  • foods? ✅ exist

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

  • First of all, wasm-bindgen doesn’t support returning vectors of custom types yet:

    #[wasm_bindgen]
    #[derive(Debug)]
    struct World {
        pub animals: Vec<Animal>,
        pub foods: Vec<Food>,
    }
    error[E0277]: the trait bound `Box<[Animal]>: IntoWasmAbi` is not
                  satisfied
     --> libs/simulation-wasm/src/lib.rs
      |
      | #[wasm_bindgen]
      | ^^^^^^^^^^^^^^^ the trait `IntoWasmAbi` is not implemented for
      |                 `Box<[Animal]>`

    It’s not that vectors are entirely forbidden — they can be used, just cannot be exported:

    #[wasm_bindgen]
    #[derive(Debug)]
    struct World {
        // Ok:
        animals: Vec<Animal>,
    
        // Error:
        pub foods: Vec<Food>,
    }
    
    #[wasm_bindgen]
    impl World {
        // Error:
        pub fn animals(&self) -> &[Animal] {
            todo!()
        }
    
        // Error:
        pub fn animals_cloned(&self) -> Vec<Animal> {
            todo!()
        }
    }
    
    impl World {
        // Ok:
        //
        // (Notice missing `#[wasm_bindgen]` - this is allowed, because
        // this function won't be exported to JavaScript.)
        pub fn foods(&self) -> &[Food] {
            todo!()
        }
    }
  • Second of all, even if wasm-bindgen did support vectors of custom types, I think that it’s important to remember about separation of concerns — that is: lib-simulation should be all about "how to simulate evolution", not "how to simulate evolution and integrate with WebAssembly".

    In a second we’ll be implementing lib-simulation-wasm — and if we keep lib-simulation frontend-agnostic, it’ll be easy to create, say, lib-simulation-bevy or lib-simulation-cli next; all sharing the same simulation code underneath.

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:

e24b0b5a 9e3b 4e14 a13e f0529b35a05c

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.)

dc4ebef7 578b 4377 9a57 61d88aaac214
Note
// Nobody can stop us now:
console.log(Array(16).join('wat' - 1) + ' Batman!');

// Haha, ha:
console.log(console.log);

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!

Note

For reference, our ctxt here is of type CanvasRenderingContext2D.

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:

25e0b526 015d 4db5 8c1e 5516ef684b84

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

Note

To be on the same page, <canvas>-'s coordinate system is:

3b2960ca 6511 4686 9acd a384969e257a

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:

eb853ead 5d7e 4c0d 9e6a ca26bb515a10

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

www/index.js

/* ... */

console.log(simulation.world().animals);
dc4ebef7 578b 4377 9a57 61d88aaac214

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:

2e91178c 5441 4f66 9fbf 001d76ad752d
Note

If you’ve got an HiDPI display, you might notice that the canvas looks blurry — please do not adjust your television set, all’s "correct".

It’s because most, if not all, browsers render canvases without adjusting for screen’s pixel density, and then artificially upscale the image to match the actual resolution of the screen.

Overcoming this inconvenience requires a bit of a trickery that boils down to enlarging the canvas manually before any drawing happens, as to "correct" the browser’s default behavior:

/* ... */

const viewportWidth = viewport.width;
const viewportHeight = viewport.height;

const viewportScale = window.devicePixelRatio || 1;
// ------------------------------------------ ^^^^
// | Syntax-wise, it's like: .unwrap_or(1)
// |
// | This value determines how much physical pixels there are per
// | each single pixel on a canvas.
// |
// | Non-HiDPI displays usually have a pixel ratio of 1.0, which
// | means that drawing a single pixel on a canvas will lighten-up
// | exactly one physical pixel on the screen.
// |
// | My display has a pixel ratio of 2.0, which means that for each
// | single pixel drawn on a canvas, there will be two physical
// | pixels modified by the browser.
// ---

// The Trick, part 1: we're scaling-up canvas' *buffer*, so that it
// matches the screen's pixel ratio
viewport.width = viewportWidth * viewportScale;
viewport.height = viewportHeight * viewportScale;

// The Trick, part 2: we're scaling-down canvas' *element*, because
// the browser will automatically multiply it by the pixel ratio in
// a moment.
//
// This might seem like a no-op, but the maneuver lies in the fact
// that modifying a canvas' element size doesn't affect the canvas'
// buffer size, which internally *remains* scaled-up:
//
// ----------- < our entire page
// |         |
// |   ---   |
// |   | | < | < our canvas
// |   ---   |   (size: viewport.style.width & viewport.style.height)
// |         |
// -----------
//
// Outside the page, in the web browser's memory:
//
// ----- < our canvas' buffer
// |   | (size: viewport.width & viewport.height)
// |   |
// -----
viewport.style.width = viewportWidth + 'px';
viewport.style.height = viewportHeight + 'px';

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

// Automatically scales all operations by `viewportScale` - otherwise
// we'd have to `* viewportScale` everything by hand
ctxt.scale(viewportScale, viewportScale);

// Rest of the code follows without any changes
ctxt.fillStyle = 'rgb(0, 0, 0)';

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

As promised, this gets us a sharp image:

4248d354 2b4c 420b 87c1 c1d249cdff84

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!

bc321864 81b2 4f69 90c0 57edda4ae04f

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);
Note

JavaScripts allows for methods to be created willy-nilly at runtime - a similar code in Rust would require creating a trait:

trait DrawTriangle {
    fn draw_triangle(&mut self, x: f32, y: f32, size: f32);
}

impl DrawTriangle for CanvasRenderingContext2D {
    fn draw_triangle(&mut self, x: f32, y: f32, size: f32) {
        self.begin_path();
        /* ... */
    }
}

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,
    );
}
37718e09 3278 44ef a104 28cb5486e4ff
Note

If those triangles look too small for you, feel free to adjust the canvas' size and the 0.01 parameter.

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:

d50a7a76 abc0 415c b43c dff76f18b242

... generalized for any angle.

Vertices Go Brrr (using math)

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

0b4f3862 3b22 4499 a4b1 3d29099c5e76

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

52ce2085 216f 4ff9 85b7 7dd0c5f44d26

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:

0ee9c7b5 80a5 4c5e 92e0 f72104f4aeca

... 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:

dd44883a ab9b 4ed7 be1e b97d4b50e128
Note

I’m using quotes around rotated, because technically it makes little to no sense to talk about rotation of a point — but hopefully the mathematicians among you will forgive me for I have semantically-sinned in a good faith.

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>:

  • 0° ⇒ rotation = 0

  • 180° ⇒ rotation = PI

  • 360° ⇒ rotation = 2 * PI

  • 90° ⇒ 180° / 2 ⇒ rotation = PI / 2

  • 45° ⇒ 180° / 4 ⇒ rotation = PI / 4

  • and so on.

Okie — one vertex done:

e0fa1f63 964b 49ba 9e32 4eab5d249a13

... 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,
);
bce2d60a cd7e 4666 84f3 76ef6dbb043a

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,
);
66781628 c317 4a0c 98ce b5317abf4c4c
Note

For what it’s worth, instead of + 4.0 / 3.0, we could’ve also used - 2.0 / 3.0 (meaning "60° counterclockwise from the top vertex"):

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

... as both are identical.

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:

13650115 7ac4 47d2 a1d5 bcf1c3c7b370

... 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:

7c0a009c 202c 4666 ac69 e6c03cf75bae

... 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:

e53c3146 b334 4b4d 8492 09b6c37b4293

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:

e5597f34 11e5 48cc b76c 329f0ee543d6

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!

Note

Wait, wait — why ::new(animal.speed, 0.0)?

nalgebra assumes no specific point of reference — instruction please move at 45° doesn’t contain enough information to actually compute where the birdie should get moved: it’s 45° according to which axis?

2b162f23 e9ab 4c46 8f61 0ce617366de0

So that’s the issue our ::new(animal.speed, 0.0) solves — it says that we’re interested in rotating relative to the x axis, that is: a bird with rotation of 0° will fly to the right.

All said, this is a rather arbitrary decision that just neatly aligns with how we render triangles on <canvas>; we might’ve as well done e.g. ::new(0.0, animal.speed) and adjust our drawTriangle() to account for that.

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:

  • na::wrap(0.5, 0.0, 1.0) == 0.5 (numbers between [min,max] are left untouched),

  • na::wrap(-0.5, 0.0, 1.0) == 1.0 (if number < min { return max; }),

  • na::wrap(1.5, 0.0, 1.0) == 0.0 (if number > max { return min; }).

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:

eaeec88c f532 4976 8e1d 0b3b7660c136
Figure 3. distance(A, B) > radius(A) + radius(B) ⇒ no collision
b5eac4ea 8667 4590 91bb 0c77412d8cb1
Figure 4. 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:

0adc49b4 c1cb 4012 9d63 25bbaed96de7
Figure 5. 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°:

17d07e2f 952f 4c16 a71a aace25683c5e

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

Note

I have to confess to something: when I first wrote this simulation, I haven’t had tested the eyes — I just had no clue how to 🙈

It’s just a few days ago when I got an idea I consider neat — I’ll leave it up to you to decide.

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

  • FOV range (one f32),

  • FOV angle (one f32),

  • number of cells (one usize),

  • position (two f32-s),

  • rotation (one f32).

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!)

Note

The code you see has the correct values for expected_vision already filled — but in reality I didn’t know them up-front; behind the scenes, what I’ve done was:

#[test_case(1.0, "")]
/* ... */

... and then I’ve run $ cargo test, and copy-pasted the actual result from the error message, analyzing whether it made sense or not (e.g. getting # for fov_range of 0.1 could indicate a bug, as a birdie with such a small fov_range shouldn’t be able to see that food).

Since all of this $ cargo test and copy-pasting is a rather mundane task, to avoid boring you, the code I’ll provide in a moment will already contain all of the expected_vision pre-filled so that all of the tests pass; just keep in mind than in reality you’d have to start with e.g. empty assertion and see what comes out of it.

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))
            .cloned()
            .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))
        .cloned()
}

... 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;

/* ... */
Note

But wait — doesn’t this code require some kind of RwLock or Mutex?

I mean, what happens when user clicks train please, thank u during the time .step() is working — won’t this cause our Rust code to be invoked twice at the same time, destroying the entire universe and everything we love?

Fear not: as I mentioned before, JavaScript is single threaded — when browser executes our .step() (or rather redraw()), it "hangs" the tab.

Simplifying a bit, you could say that at a time only one line of JavaScript code is running — it’s not possible to execute both .step() and .train() at once (which would also violate the &mut self requirement on the Rust’s side); if user clicks train when .step() is working, the browser will schedule the click event to be executed in the next frame.

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?

  • birdies are cute? ✅

  • birdies eat food? ✅

  • birdies learn to catch food better and better? ✅

Nice!

Note

The concrete statistics you get are most likely different than mine, but the general trend — min, max and average going up — should be visible in most of the simulations.

The results won’t be rising up to infinity - from what I saw, most of the time you’ll get averages up to 40~50, everything above will be pretty much exceptional.

Also, please remember that we’re putting a lot of faith in random numbers! — if your birds seem to be getting stuck in local optimum too soon, try refreshing the simulation.

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:

e5313753 9b47 4c39 a198 df190f2db9c4
Figure 6. 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!