Maze

Generate Mazes, of any width and height, of any start and end point and more

in this example, orange is the starting point and cyan is the ending point

Usage

Installation

npm install @y0urstruly/maze

Importing

const {makeMaze, makeRandomMaze, makeMove} = require('@y0urstruly/maze');

Note

If you are using this on a replit instance, you might want to configure your replit.nix file based on this StackOverflow answer due to the npm canvas package that this repository uses

Exports

There are three functions that are exported for use

• makeMaze([width[,height[,start[,end[,odds[,lineWidth[,space[,startColour[,endColour]]]]]]]]])

  • Description: This function generates the maze object based on the arguments given
  • Returns:

    {
      ...maze column positions(0 through width-1){
        ...maze row positions(0 through height-1){
          N: boolean, //if the position's north end has a wall
          E: boolean, //if the position's east end has a wall
          S: boolean, //if the position's south end has a wall
          W: boolean, //if the position's west end has a wall
          touched: boolean //if a position has already been reached
          //by the time it returns, every point on the maze should have its 'touched' attribute as true
        }
      },
      height: number, //representing the height of the maze
      width: number, //representing the width of the maze
      paths: number, //was a helpful counter during the maze's generatoin but is 0 when returned
      DRAW:{
        s: number, //the size(pixels) of the space inside each maze position
        l: number, //the thickness(pixels) of each line inside the maze
        f: number, //half of the attribute l(pixels)
        ctx: createCanvas(...).getContext('2d') //a property derived from the usage of the npm 'canvas' package
      },
      ODDS:{
        numerator: number, //an integer that's more than 0 and less than denominator
        denominator: number //an integer that satisfies the above description of numerator
      },
      canvas: createCanvas(...), //a property derived from the usage of the npm 'canvas' package
      start: [number/*gx*/,  number/*gy*/], //where one starts the maze
      end: [number/*px*/,  number/*py*/] //where one completes the maze
    }

  • Arguments:
    • width number (default is 20) The width of the maze(amount of columns, more than 0)
    • height number (default is 20) The height of the maze(amount of rows, more than 0)
    • start Array (default is [0, 0]) An array [gx, gy] where one would start the maze
      gx ranges from 0 through width-1, gy ranges from 0 through height-1
    • end Array (default is [19, 19]) An array [px, py] where one would complete the maze
      px ranges from 0 through width-1, py ranges from 0 through height-1
    • odds Array (default is [2, 11]) An array [numerator, denominator] fitting the constraints defined in the ODDS
      An attribute of the maze object described above
    • lineWidth number (default is 2) The thickness(pixels) of each line inside the maze
    • space number (default is 30) The size(pixels) of the space inside each maze position
    • startColour string (default is "#FF7F00") The colour(hex or rgb) of the position where one starts the maze
    • endColour string (default is "#00F7FF") The colour(hex or rgb) of the position where one completes the maze
• makeRandomMaze([maxSize[,minSize[,minDist[,highestOdds[,lowestOdds]]]]])

  • Description: Generates a maze where both the width and height are each discrete but random integers from minSize through maxSize
    The start and end points are random but always at least minDist away from each other
    The odds are also randomly generated with the fraction of numerator/denominator always at most highestOdds and at least lowestOdds
    These odds affect the length of the maze's path
  • Returns:

    the maze object generated from the makeMaze function

  • Arguments:
    • maxSize number (default is 25) the maximum height or width of the maze(more than 0)
    • minSize number (default is 10) the minimum height or width of the maze(more than 0)
    • minDist number (default is 5) the minimum distance between the start point and the end point of the maze(more than 1)
    • highestOdds number (default is 0.9) the maximum quotient of numerator/denominator
    • lowestOdds number (default is 0.1) the minimum quotient of numerator/denominator
• makeMove(map,move[,start])

  • Description: This function takes a maze object and a string, evaluates the string from a start point(or the maze's start point) and evaluates the new position
    Eg "SSEE" means move south twice, then east once because it hits a wall when it tries to move east a second time
  • Returns:

    [
      x, //x position of new evaluated position after the string of north, east, south, west commands
      y //y position of new evaluated position after the string of north, east, south, west commands
    ]

  • Arguments:
    • map makeMaze(...) A maze object
    • move string A string with each character being either 'N','E','S','W'
      'N' to go north, 'E' to go east, 'S' to go south, 'W' to go west
    • start Array (default is Array.from(map.start)) An array [x, y] representing the starting position to evaluate the move from

Logic

• The idea is to have a grid of positions, each position having boolean attributes for all 4 directions(true if blocked, false if open) and a boolean "touched" attribute
• Then recursion is used to traverse over every single position in the grid by every untouched(touched is false) AND open(direction attribute to and from are both false) position
• The recursive function, traverseMaze, ensures that where it comes from is never blocked, hence there is always a path
  Eg: if the recursion at [19, 19] calls [19, 18] then the directions between those 2 points remain unblocked
• Even after reaching the goal, the maze is still filled in every position because in any position, if all directions are blocked BUT there is an untouched position, that direction changes to open(the boolean for that direction is made false) and recursion would resume in said untouched position
• Odds are used in 2 ways, the first one being that low odds means a low chance for a direction to be open(high chance a direction is blocked) with the intent of having low odds mean longer mazes and high odds mean shorter mazes
• The second application of odds sealed the deal, by also making odds decide the order of recursion. In this instance of recursion, one function call may get finished after a good chunk of path is already made.
  So "order of recursion" would be the odds' chance(odds is true) of the directions sorted in order of which is CLOSEST to the goal, else(odds is false) they're sorted in order of which is FURTHEST from the goal