Genetic Algorithm in the browser with WebAssembly
Tags: rust, webassembly, javascript
Published: 2019-07-30 13:14:09

This is the second post in my series on Rust and WebAssembly with Genetic Algorithms. In this post I'm going to build on the Genetic Algorithm I have implemented in Rust for the travelling salesman problem. I'll take the Rust implementation and make some adjustments that will allow it to be compiled to WebAssembly and interact with JavaScript and the browser. Then I'll develop a web application that will provide the user interface for running the Genetic Algorithm.

All the code for this post can be found [here](https://github.com/d3spis3d/wasm-genetic), and the live demo can be found [here](https://d3spis3d.github.io/wasm-genetic/).

![Cracked textured Photo by Vincent Burkhead on Unsplash](https://thepracticaldev.s3.amazonaws.com/i/w002gywiv7p03155v854.jpg)
Photo by [Vincent Burkhead](https://unsplash.com/@creativejunkie?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText) on [Unsplash](https://unsplash.com/search/photos/abstract?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText)

For this project I am using the [Rust Webpack Template](https://github.com/rustwasm/rust-webpack-template), which is designed to create monorepo style Web applications which are made up to JavaScript, HTML and Rust-generated WebAssembly. This template relies on a few tools; `wasm-pack`, `npm`, and setting up the WebAssembly compile target `wasm32-unknown-unknown`. More details on the setup can be found in the `wasm-pack` [docs](https://rustwasm.github.io/docs/wasm-pack/introduction.html).

To start with, there are a number of changes that need to be made to the Rust code to support compilation to WebAssembly. The first thing is to add `wasm-bindgen` which will provide the means to define which parts of the Rust code will be exported and accessible from JavaScript. Adding the `wasm-bindgen` macro to the **Simulation** struct tells the library to build this as an export from the WebAssembly module, and adding the macro for the constructor allows the **Simulation** to be created using `new Simulation()` in JavaScript.

```rust
#[wasm_bindgen]
pub struct Simulation {
    population: Vec<Path>,
    city_list: Vec<City>,
    max_iterations: usize,
    crossover_rate: f64,
    mutation_rate: f64,
    survival_rate: f64,
}

#[wasm_bindgen]
impl Simulation {
    #[wasm_bindgen(constructor)]
    pub fn new(
        population_size: usize,
        city_list: String,
        max_iterations: usize,
        crossover_rate: f64,
        mutation_rate: f64,
        survival_rate: f64,
    ) -> Simulation {
        ...
    }
}
```

The Rust implementation uses the [rand](https://crates.io/crates/rand) crate; luckily the rand crate provides support for the WebAssembly compile target using `wasm-bindgen`. This can be set in the projects Cargo.toml and as of version 0.7 works seamlessly.

```toml
[dependencies.rand]
version = "0.7"
features = [
  "wasm-bindgen",
]
```

Another useful crate is `js_sys`, which provides bindings to JavaScripts built-in objects and standard library. This is useful to marshal the results of the simulation to a format the calling JavaScript can understand. The return type of the **Simulation**'s run method becomes Array from `js_sys`, and an array is constructed with the first entry being the ordered list of nodes visited for the solution, and the second the fitness.

```rust
pub fn run(&mut self) -> Array {

      ...

      let array = js_sys::Array::new();
      let order = js_sys::Array::new();
      for o in fittest.order {
          order.push(&JsValue::from(o as u32));
      }

      array.push(&order);
      array.push(&JsValue::from(fittest.fitness));

      array
  }
```

The web application for running the simulation is designed to be simple; it has inputs for the algorithm parameters, an area where the user may click to add cities, and a preset button which adds a list of default cities.

![Screenshot of web application for Genetic Algorithm](https://thepracticaldev.s3.amazonaws.com/i/abp9edfuv9n7p33ujmym.png) 

To prevent the main thread from being blocked while running the WebAssembly, the module is run in a Web Worker. The first step is to change the Webpack config provided by the Rust Webpack template to build the app and worker JavaScript files separately.

```js
const appConfig = {
  target: 'web',
  entry: "./js/index.js",
  output: {
    path: dist,
    filename: '[name].[hash].js',
  },
  devServer: {
    contentBase: dist
  },
  plugins: [
    new HtmlWebpackPlugin({
      template: 'index.html',
      chunks: ['main']
    }),
  ],
  module: {
    rules: [
      {
        test: /\.css$/,
        use: [{ loader: 'style-loader' }, { loader: 'css-loader' }],
      }
    ]
  }
}

workerConfig = {
  target: 'webworker',
  entry: "./js/worker.js",
  output: {
    path: dist,
    filename: 'worker.js',
    globalObject: 'self'
  },
  devServer: {
    contentBase: dist
  },
  resolve: {
    extensions: [".js", ".wasm"]
  },
  plugins: [
    new WasmPackPlugin({
      crateDirectory: path.resolve(__dirname, "crate"),
    }),
  ]
}

module.exports = [appConfig, workerConfig]
```

The worker code is pretty simple. It imports the WebAssembly module, sets up a message handler to receive data from the main thread with the simulation parameters, runs the **Simulation** and posts a message back to the main thread with the results.

```js
import("../crate/pkg").then(({ Simulation }) => {

  onmessage = function(msg) {
    const {
      iterations,
      citiesString,
      population_size,
      crossover,
      mutation,
      survival
    } = msg.data

    const s = new Simulation(
      iterations,
      citiesString,
      population_size,
      crossover,
      mutation,
      survival
    )

    const result = s.run()

    self.postMessage({
      path: result[0],
      fitness: result[1]
    })
  }
})
```

The application code includes a click handler that captures the users clicks inside the drawing space and adds a dot. The position of the dot is stored in `data-x` and `data-y` attributes on the DOM elements for passing to the WebAssembly code later.

```js
const draw = document.getElementById('draw')

function addDot(x, y) {
  const dot = document.createElement('div')
  dot.className = 'dot'
  dot.style = `top: ${y}px; left: ${x}px;`
  dot.setAttribute('data-x', x)
  dot.setAttribute('data-y', y)
  draw.appendChild(dot)
}

draw.onclick = function(event) {
  addDot(event.offsetX, event.offsetY)
}
```

The main part of the application is the `onsubmit` function for the form. It is responsible for:

- capturing the input parameters for the simulation,
- extracting the co-ordinates of the cities that the user has drawn,
- sending a message to the worker with the parameters,
- setting a message handler to receive the results of the simulation run and draw the solution,
- drawing the cities on the solution canvas.

```js
form.onsubmit = function(event) {
  event.preventDefault()
  const [iterations, population_size, crossover, mutation, survival] = event.target

  const cities = []
  const count = draw.children.length
  for (let c = 0; c < count; c++) {
    cities.push([
      draw.children[c].getAttribute('data-x'),
      draw.children[c].getAttribute('data-y')
    ])
  }

  const citiesString = cities.map(c => c.join(',')).join(';')

  worker.postMessage({
    iterations: parseInt(iterations.value, 10),
    citiesString,
    population_size: parseInt(population_size.value, 10),
    crossover: parseFloat(crossover.value),
    mutation: parseFloat(mutation.value),
    survival: parseFloat(survival.value)
  })

  worker.onmessage = function(msg) {
    const { path, fitness } = msg.data

    for (let p = 0; p < path.length - 1; p++) {
      const start = cities[path[p]]
      const end = cities[path[p+1]]

      ctx.beginPath()
      ctx.moveTo(start[0], start[1])
      ctx.lineTo(end[0], end[1])
      ctx.stroke()
    }
  }

  const ctx = canvas.getContext('2d')

  cities.map(c => {
    ctx.beginPath()
    ctx.arc(c[0], c[1], 2, 0, 2 * Math.PI, false)
    ctx.fillStyle = 'black'
    ctx.fill()
  })
}
```

The complete code can be found [here](https://github.com/d3spis3d/wasm-genetic), as well as the demo [here](https://d3spis3d.github.io/wasm-genetic/).

In this article I have shown how to modify Rust code for compilation into WebAssembly and build a web application to use the WebAssembly module. In the last article in this series I will take about running this WebAssembly module outside of the browser with Wasmtime.