Maze Project

The aim is to be able to generate perfect mazes - mazes that are always solve-able for any pair of cells in the maze with the additional property that there exists a unique solution for that pair. In addition, solve the maze for the given scenarios:

• Chart the path from the top-left to the bottom-right of the maze.

• Discover a longest path in the maze.

• Discover a most convoluted path in the maze.

The project will generate randomly shaped mazes for every run of the program (within reason).

For the design of the project, please refer to the Design doc.

Project Setup

This project is written in Rust (version: rustc 1.28.0 (9634041f0 2018-07-30)). Rust uses cargo as the build/dependency manager, and rustup as the tool for installing Rust toolchains.

To set up Rust, please follow the following steps:

1. Go to the rustup.rs site to install the latest version of rustup using the command shown on the site: curl https://sh.rustup.rs -sSf | sh

2. Following the default options should install the toolchain management tool, rustup. Note that you can pick from amongst a number of preset toolchains - stable, nightly, and some others. Choose stable (nightly should work fine as well though).

3. Verify that the installation went through fine:

   $ cargo --version
   cargo 1.28.0 (96a2c7d16 2018-07-13)
   

Building the project

Note: This project should work both with all Rust editions - 2015 or 2018.

From the project root, run the following command: cargo clean && cargo build --release as in:

$ cargo clean && cargo build --release
   Compiling libc v0.2.43
   Compiling rand_core v0.2.1
   Compiling rand v0.5.5
   Compiling maze_project v0.1.0 (file:///Users/z0ltan/Code/Projects/games/maze_rs)
    Finished release [optimized] target(s) in 4.59s

Generating documentation for the Project

Rust comes with its own documentation tool (much like javadoc) built-in. To generate the project documentation, run the following command: cargo doc --no-deps --open as in:

$ cargo doc --no-deps --open
    Checking rand_core v0.2.1
    Checking libc v0.2.43
    Checking rand v0.5.5
 Documenting maze_project v0.1.0 (file:///Users/z0ltan/Code/Projects/games//maze_rs)
    Finished dev [unoptimized + debuginfo] target(s) in 4.35s
     Opening /Users/z0ltan/Code/Projects/games/maze_rs/target/doc/maze_rs/index.html
   Launching open

This should open the generated HTML page in your default browser.

Running the project

To run the project, use the cargo run command with any parameters passed in, like so:

$ cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.03s
     Running `target/debug/maze_project`
Usage: cargo run HEIGHT WIDTH

Running the tests

Rust comes with its own test suite built-in, and the cargo test command should run all tests in the project:

$ cargo test
    Finished dev [unoptimized + debuginfo] target(s) in 0.03s
     Running target/debug/deps/maze_project-c360a1a0a2cd554c

running 16 tests
test ds::tests::test_maze_data ... ok
test ds::tests::test_point ... ok
test ds::tests::teste_maze_data_sanity ... ok
test helper::tests::test_char_for_direction_east ... ok
test helper::tests::test_char_for_direction_north ... ok
test helper::tests::test_char_for_direction_southt ... ok
test ds::graphs::test::test_add_edge_panic ... ok
test ds::graphs::test::test_get_adjancent_vertices_panic ... ok
test ds::graphs::test::test_get_spanning_tree_panic ... ok
test helper::tests::test_char_for_direction_west ... ok
test helper::tests::test_get_direction_east ... ok
test helper::tests::test_get_direction_north ... ok
test helper::tests::test_get_direction_south ... ok
test helper::tests::test_get_direction_west ... ok
test ds::graphs::test::test_spanning_tree_params ... ok
test ds::graphs::test::test_generate_spanning_tree ... ok

test result: ok. 16 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

     Running target/debug/deps/maze_project-c14ba56a651feb63

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

   Doc-tests maze_project

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

Sample Run

Simply run the project with the desired dimensions of the grid. Shown below is a sample run:

$ cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.03s
     Running `target/debug/maze_project`
Usage: cargo run HEIGHT WIDTH


$ cargo run 15 20
    Finished dev [unoptimized + debuginfo] target(s) in 0.03s
     Running `target/debug/maze_project 15 20`


   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
   | s                             |                           |   |   |   |   |   |
   +   +   +   +---+   +   +---+---+   +---+   +---+---+   +---+   +   +   +   +   +
   | v |   |       |   |           |       |           |                           |
   +   +---+---+---+---+   +   +   +   +   +---+---+   +---+---+---+---+---+---+---+
   | v     |       |   |   |   |       |           |               |       |       |
   +   +   +   +   +   +---+   +---+   +---+---+---+   +---+---+---+---+   +   +   +
   | v |       |           |   |   |               |   |   |       |   |   |   |   |
   +   +---+---+---+---+---+   +   +---+---+---+---+---+   +---+   +   +   +   +---+
   | >   v             |   |   |                       |       |   |   |           |
   +   +   +   +   +---+   +---+   +   +---+---+---+---+   +---+   +   +   +   +---+
   |   | v |   |                   |               |       |   |           |       |
   +   +   +   +---+   +   +   +---+   +   +   +---+---+   +   +   +   +---+---+   +
   |   | v |   |       |   |       |   |   |       |   |       |   |       |       |
   +   +   +---+---+---+   +---+   +   +---+---+---+   +   +---+   +---+---+---+   +
   |   | v             |       |   |   |           |               |   |   |   |   |
   +---+   +---+   +---+---+---+---+---+---+   +---+---+   +   +---+   +   +   +---+
   |     v     |                       |       |   |       |   |                   |
   +   +   +---+---+   +   +---+---+---+   +---+   +   +   +---+   +---+---+---+   +
   |   | v         |   |           |       |   |       |           |           |   |
   +   +   +---+---+   +---+---+---+---+   +   +   +   +---+---+---+   +---+   +---+
   |   | >   v     |           |   |       |   |   |       |               |   |   |
   +---+   +   +---+---+---+---+   +---+   +   +   +---+---+   +   +---+---+---+   +
   |       | >   v         |   |       |   |       |   |       |                   |
   +   +---+   +   +---+---+   +   +---+   +   +---+   +---+   +---+---+---+---+---+
   |   |       | >   >   v     |           |       |   |       | >   >   >   >   v |
   +---+   +   +   +---+   +---+   +---+---+   +---+   +   +---+   +---+---+---+   +
   |       |   |   |   | >   >   >   >   >   >   >   >   >   >   ^             | v |
   +   +---+   +   +   +---+   +   +---+   +---+   +---+   +   +---+---+   +---+   +
   |       |   |           |   |   |           |       |   |           |       | t |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

Enter choice (1 - solve, 2 - longest path, 3 - quit)...
1

   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
   | s                             |                           |   |   |   |   |   |
   +   +   +   +---+   +   +---+---+   +---+   +---+---+   +---+   +   +   +   +   +
   | v |   |       |   |           |       |           |                           |
   +   +---+---+---+---+   +   +   +   +   +---+---+   +---+---+---+---+---+---+---+
   | v     |       |   |   |   |       |           |               |       | >   v |
   +   +   +   +   +   +---+   +---+   +---+---+---+   +---+---+---+---+   +   +   +
   | v |       |           |   |   |               |   |   |       |   |   | ^ | t |
   +   +---+---+---+---+---+   +   +---+---+---+---+---+   +---+   +   +   +   +---+
   | >   v             |   |   |                       |       |   |   | >   ^     |
   +   +   +   +   +---+   +---+   +   +---+---+---+---+   +---+   +   +   +   +---+
   |   | v |   |                   |               |       |   | >   >   ^ |       |
   +   +   +   +---+   +   +   +---+   +   +   +---+---+   +   +   +   +---+---+   +
   |   | v |   |       |   |       |   |   |       |   |       | ^ |       |       |
   +   +   +---+---+---+   +---+   +   +---+---+---+   +   +---+   +---+---+---+   +
   |   | v             |       |   |   |           |     >   >   ^ |   |   |   |   |
   +---+   +---+   +---+---+---+---+---+---+   +---+---+   +   +---+   +   +   +---+
   |     v     |                       |       |   | >   ^ |   |                   |
   +   +   +---+---+   +   +---+---+---+   +---+   +   +   +---+   +---+---+---+   +
   |   | v         |   |           |       |   | >   ^ |           |           |   |
   +   +   +---+---+   +---+---+---+---+   +   +   +   +---+---+---+   +---+   +---+
   |   | >   v     |           |   |       |   | ^ |       |               |   |   |
   +---+   +   +---+---+---+---+   +---+   +   +   +---+---+   +   +---+---+---+   +
   |       | >   v         |   |       |   | >   ^ |   |       |                   |
   +   +---+   +   +---+---+   +   +---+   +   +---+   +---+   +---+---+---+---+---+
   |   |       | >   >   v     |           | ^     |   |       |                   |
   +---+   +   +   +---+   +---+   +---+---+   +---+   +   +---+   +---+---+---+   +
   |       |   |   |   | >   >   >   >   >   ^                                 |   |
   +   +---+   +   +   +---+   +   +---+   +---+   +---+   +   +---+---+   +---+   +
   |       |   |           |   |   |           |       |   |           |       |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

Enter choice (1 - solve, 2 - longest path, 3 - quit)...
2

Limitations and Possible Enhancements

• Uses ANSI Escape Codes for rendering the maze, and so scrolling is a problem. Recommended limits are a 25 x 25 maze, but on bigger screens with greater resolutions and configurations, more or less should be possible. The code does not enforce any limit other than a minimum of a 1 x 1 maze size.

• Again, due to the use of ANSI Escape Codes, the code should work fine on any ANSI-compliant terminal, and that rules out basic Windows command lines.

• Most complicated Paths should be relatively straightforward to implement, and the planned approach is mentioned in the supporting Design doc.

• All tweakable configurations (animation speeds, font colours, cell sprites et al) should ideally be placed in an external configuration file.

Licence

Please refer to the licence file at LICENCE