Maze solver (micromouse) for the web

2021.05.17

A brief history

In the previous article, we have generated a maze with few steps. Deep into the code, I changed a little bit to compatible with a new solver.

class Maze {
 constructor(options){
  // preparation
  const { size, cellSize, wallSize } = Object.assign({
   size: 10,
   cellSize: 20,
   wallSize: 1
  }, options);
  ...

I had wrapped the entire code into a class with some parameters such as size, cell size, wall size. The output is an array of walls (rectangle with position and size).

class Maze {

  ...

  get walls(){
    const walls = [
      { x: 0, y: 0, w: this.width, h: this.wallSize },
      { x: 0, y: this.width - this.wallSize, w: this.width, h: this.wallSize },
      { x: 0, y: 0, w: this.wallSize, h: this.height },
      { x: this.width - this.wallSize, y: 0, w: this.wallSize, h: this.height },
    ];

    ...
  }

  ...

}

You can try my new code at Maze Generation.

In visualization, we have a maze that looks like this:

Solid version


Wireframes version

Environment

Beforehand create the solver, I created a requirement space for that. By using MatterJS for physic simulation which consists of collision detection (for the contact between mouse and wall), ray casting (for wall detection sensors).

Matter.js is a 2D physics engine for the web

Running environment, contains Matter JS engine, Maze Generator, start point (location class), end area (area class), mouse, wall. My mouse inherits the Mouse class.

Using maze library was mention in the last section. In Matter JS, it's becoming bodies. I also added starting point and ending area.


Mouse

My solver use Wall Follower algorithm.

My mouse has 2 system actions: run, stop. And 4 control actions: go (straight), brake (stop-go and rotate), left (rotate left), right (rotate right). It has two sensors, the first one (main sensor) for wall detection on straight going (angle: 0 rad, length: 18), and another one (wall sensor) to turn (angle: -3 * pi /4, length: sqrt(2 * 20^2)).

When the mouse moving, it leaves footprints like this.

When meeting walls, it turns right 90 degrees.

When the wall sensor cannot detect walls, it back to meet the wall again and turn left 90 degrees, then straight ahead.

That alls, just simple. The result:

Resources


By: Anh Hao