Wondering what’s next for npm?Check out our public roadmap! »

    maze-generation

    2.1.0 • Public • Published

    maze-generation

    npm NPM CircleCI npm bundle size

    An npm package used to generate mazes with a specified width and height.

    Mazes can be generated using either recursive backtracker (Depth First) or hunt and kill algorithms. See below for details of these algorithms.

    Additionally mazes can be generated using seeds, which allows for reproducible maze generation.

    Contributing

    Please view our CONTRIBUTING.md file for information on how to contribute, report issues and request features.

    Changelog and versioning

    Please view our CHANGELOG.md file for information on our updates.

    We use SemVer for versioning.

    Using maze-generation

    Installing

    Ensure Node.js is installed on your machine.

    Run npm i maze-generation

    Usage

    Add the following to your code where:

    • width and height should be replaced by ints corresponding to how wide and tall you want your maze.
    • seed should be replaced by an int or string and will be used as the seed for the random number generator.
    • algorithm should be: 'DEPTHFIRST' or 'HUNTANDKILL'.

    To stop heap out of memory errors, the maximum allowed height and width is 3000.

    const mazegeneration = require('maze-generation');
     
    // Generate a maze
    const generatedMaze = mazegeneration(width,height,seed,algorithm);

    To get the string representation of the generated maze write:

    const stringRepresentation = generatedMaze.toString();
    console.log(stringRepresenation);

    Example output:

     _ _ _ _ _ _ _ _ _ _
    |  _ _ _  |_ _ _    |
    | |_  |  _|  _ _ _| |
    |   |_ _  |_  | |  _|
    | |_  |_ _  | | | | |
    |  _|_  |  _| | |  _|
    |_|  _ _|_ _ _|  _| |
    |  _|   |_ _ _ _|  _|
    | |  _| |   |   |_  |
    |  _|  _| |_ _|_ _ _|
    |_ _|_ _ _ _ _ _ _ _|
    
    

    To get the JSON representation of the generated maze write:

    let JSONRepresentation = generatedMaze.toJSON();

    The outputed JSON object has the following structure (example is a 3 by 3 cell):

        {
            rows: [
                [[Object],[Object],[Object]],
                [[Object],[Object],[Object]],
                [[Object],[Object],[Object]],
            ]
        };

    Where each object is a Cell object, which as the following JSON structure:

        {  
            left: bool,
            right: bool, 
            up: bool, 
            down: bool, 
            visited: bool
        }

    The left,right,up,down fields correspond to if the wall exists in that direction. The visited field corresponds to if the cell has been visited. This should be marked as true for all completed mazes.

    Algorithms

    Depth First
       CURRENT_CELL = random cell
       Create an empty CELL_STACK
       While CURRENT_CELL has unvisited neighbour:
        Select random unvisited neighbour
        Remove walls between the two
        CURRENT_CELL = that random unvisited neighbour
        Mark CURRENT_CELL as visited and push it to the CELL_STACK
        IF CURRENT_CELL has no unvisited neighbour:
          CURRENT_CELL = CELL_STACK.pop()
    
    Hunt And Kill
      Choose a random starting cell and set that to CURRENT_CELL
      Perform a randomised walk from CURRENT_CELL
      WHILE there's unvisited cells with adjacent visited cells: 
        Find the first unvisited cell with adjacent visited cells and set that cell as the CURRENT_CELL
        Remove the wall between the CURRENT_CELL and a random visited neighbour
        Perform a randomised walk from CURRENT_CELL
    
    • More information can be found on Jamis Buck's blog.
    • This algorithm hunts for the "first unvisited cell with adjacent visited cells". First is found by searching each cell on the top row, before moving to the next row.

    Acknowledgments

    Install

    npm i maze-generation

    DownloadsWeekly Downloads

    22

    Version

    2.1.0

    License

    MIT

    Unpacked Size

    31.6 kB

    Total Files

    14

    Last publish

    Collaborators

    • avatar