Maze generating library in GoLang
$ cd cmd/gaze
$ go run main.go
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| | _ | |_ _ _ _ _ _ |_ _ | | _ _ _ _ _ _| |
| | | |_ _|_ _ _ _ | |_ | _ _ _ _| |_ | |_ _ | | _| |
| | | | _ _ _ _| |_ | |_| _ |_ _ |_ _ _ | | | | | _|
| | | | | |_ _ _ _ _|_ _|_ _ _ |_ | | | |_ |_ _| | |_ |
|_ _| | |_ _ |_ _ _ _ | | | | | _| |_ | _ _| _| | |
| _ |_ |_ |_ _ _| | | |_ _ _| |_ | | |_| |_ _ _| |
| | | _| | _| _ _ _ _| |_ _ _ _ _| _| | |_ _ _|_ _ _ _ |
|_ |_ |_ _| |_ _ | _ _ _ | |_ |_| | | _ _ _| _|
| _| | | _ _ _| | |_| _ |_| |_ _ _| _| _|_ _ _ | | |
|_ _ _|_ _ _|_ _ _ _|_ _ _ _|_ _ _ _ _ _ _|_ _ _ _ _ _|_ _ |
Use params to improve your experience.
- To set Heigth: -h <SIZE_IN_INTEGER>
- To set Weigth: -w <SIZE_IN_INTEGER>
Example:
$ go run main.go -h 12 -w 12
_ _ _ _ _ _ _ _ _ _ _
| | | _ _ _ _ | |
| | | |_ _| _ _ _|_ _| |
|_ _|_ _ _ _| | _ _ _ _|
| | _ _ |_ _ |_ |
|_| | | | |_ | |_ | |
| _|_ _| | _| | _| | |
|_ | | _| | _ _| _| |
| |_ _| _| | | _| _|
| |_| |_ _ _ | | _ |
| _ _|_ _ _ | | | | _|
| | |_ _ | |_| |_|_ |
|_ _|_ _ _ _|_ _ _ _ _ |
Benchmarks ran on the following hardware:
MacBook Pro 2014, OS X 10.9, 2.6 GHz Intel Core i5, 16 GB 1600 MHz DDR3.
| Algorithm | Size | Iterations | ns/ops | ms/op | allocs/op |
|---|---|---|---|---|---|
| Backtracking | 1000x500 | 1 | 5309771223 | 5309.77 | 1002 |
| Prim | 1000x500 | 10 | 118249945 | 118.24 | 1055533 |
| DeadEndFiller | 1000x500 | 10 | 192385091 | 192.38 | 2004517 |
While Prim is an order of magnitude faster, the memory allocations is still room for much improvement.
- board: imagine a
widthbyheight2D array, this represents the graphical layout of the maze. - cell: each item in the 2D array is a cell. Imagine a cell in the middle of a board, this cell could open passage(s) to the neighboring cells in any or all 4 of the directions, this is what essentially creates the maze when all the cells are processed.
- direction: the 4 directions that a cell could open a passage into.
There are many ways to generate a maze, the algos package will contains all the different implementation. All of them implements the Mazer interface that contains the Generate() method that new algorithm would need to implement.
There are also many ways to solve a maze, these are collected in solvers.
Pull requests are welcome! You could also open a Github issue to discuss and get feedback first.
MIT