Amazing Algorithms

Framework for playing with maze generation and solving algorithms.

Right now the focus is on creating a maze solving algorithm, see below for examples. The results are displayed on a central server that solvers connect to which allows everyone to develop and test on their own laptops beforehand.

Testing a solver

Test your solver locally before submitting it.

Node.js

Node uses Jamine for testing.

npm install
npm test

Java

Java uses JUnit and PowerMock for testing.

mvn test

Ruby

Ruby uses RSpec for testing.

bundle install
bundle exec rspec src/test/ruby

Register a solver

Once a solver is complete you can register it with the central server for all to play with. NOTE: localhost is used as an example, the projected central server shows the IP to connect to.

Node.js

npm install
./node.sh ws://localhost:3000 src/main/node/randomWalk.js

Java

./java.sh ws://localhost:3000 com.neophi.amazing.solver.RandomWalkSolverFactory

Ruby

bundle install
./ruby.sh ws://localhost:3000 src/main/ruby/random_walk.rb

Central server

The central server maintains the list of maze generators and solvers and coordinates sending a generated maze to a solver and displaying the solution.

npm install
npm start
open http://localhost:3000/

Maze solving algorithms

Random Walker

Randomly picks an exit.

Wall Follower

Use either left-hand rule or right-hand rule.

Keep one hand in contact with one wall of the maze and pick the exit which follows that rule.

JSON

Solver output

Maze solver output is an array of rooms visited in order:

[
  {
    x: 0,
    y: 0,
    z: 0
  },
  {
    x: 1,
    y: 0,
    z: 0
  }
]

Generator output

Maze generation output is an object with start and finish locations and an array of rooms each with a location and list of exit locations.

{
  start: {
    x: 0,
    y: 0,
    z: 0
  },
  finish: {
    x: 1,
    y: 1,
    z: 0
  },
  rooms: [
    {
      x: 0,
      y: 0,
      z: 0,
      exits: [
        {
          x: 1,
          y: 0,
          z: 0
        },
        {
          x: 0,
          y: 1,
          z: 0
        }
      ]
    },
    {
      x: 1,
      y: 0,
      z: 0,
      exits: [
        {
          x: 0,
          y: 0,
          z: 0
        },
        {
          x: 1,
          y: 1,
          z: 0
        }
      ]
    },
    {
      x: 0,
      y: 1,
      z: 0,
      exits: [
        {
          x: 0,
          y: 0,
          z: 0
        }
      ]
    },
    {
      x: 0,
      y: 0,
      z: 0,
      exits: [
        {
          x: 1,
          y: 0,
          z: 0
        }
      ]
    }
  ]
}

Resources

http://en.wikipedia.org/wiki/Maze_generation_algorithm

http://en.wikipedia.org/wiki/Maze_solving_algorithm

http://weblog.jamisbuck.org/under-the-hood

http://www.astrolog.org/labyrnth/algrithm.htm

License

Copyright (c) 2013 Daniel Rinehart. This software is licensed under the MIT License.