Random maze on js in you know how many lines

Having read articles on [anything else] in JavaScript in 30 lines of code, I thought: why am I worse? Not finding the item “writing bad code” in the list of my shortcomings, I decided to do something interesting.

The labyrinths have always guided in my direction with some magic and riddles, so the search for "something interesting" ended quickly enough. Unfortunately, the creation of the game was delayed for many hours of experiments on the console and my nerves.

Initially, realizing the size of the righteous anger of adepts of immaculate programming, I did not plan to publish my writings, but after the game was liked by the cat, a couple of friends and my vanity, I decided to write an article (you can incorporate the theoretical part into it).
')
For supporters of the principle “you know less - sleep better”, a link to JSFiddle (arrow control) is suggested.

Start

What is the most difficult in creating such a game? That's right, the generation of the labyrinth itself. That is why, at first, I began not with examining the existing algorithms and choosing the optimal one, but with creating my own wheel with preference and widowed aristocrats of the most strict rules.

My idea was as simple as Gregory Galloway’s snow: to write a recursive function that, starting from the point [0: 0], would run through the maze and “drive out” its way until it got out. As soon as she does this, we randomly select N cells from the path traveled by her and start the same function from these cells.

Pros: the ability to adjust the complexity of the labyrinth, humidifying the value of N.
Cons: randomness of everything and everything.

Said - done! .

After crying over my decision, I turned to the experts for help. Fortunately, their advice turned out to be NMEMALO .

Prima's randomized algorithm

Having studied these algorithms, I settled on the Prima randomized algorithm (in fact, altering it a little), considering its implementation to be the most concise.

So first, a little about the maze. A labyrinth is a table (of course, it would be more correct to call it a graph), the cells (vertices) of which must belong to one of 2 sets:
1) "Walls" (black blocks), which form these fancy patterns of the maze;
2) “Passages” (white blocks) - just that, on which you can move.

The algorithm is as follows:

1. We start with a table (graph), all the cells (vertices) of which belong to the set of "Walls";
2. Select a cell. Remove it from the set of "Walls" and add to the set of "Passages". All the walls adjacent to it (vertical and horizontal) are added to the “Special List of Walls approved by the plenary session of the State Duma ”;
3. Take the "Special List of Walls".
   
   1. If it is not empty, then we choose a random wall from it.
      1) If the cell on the side opposite to the wall belongs to the “Passages” set, then we delete this wall from the “ATP” (special list of walls):
      
      
      
      2) If the cell on the opposite side belongs to the set of "Walls", then:
      
      • Remove this wall from the set of "Walls";
      • Add this wall to the set of “Passages”;
      • Remove the cell on the opposite side from the set of "Walls";
      • Add a cell on the opposite side to the “Passages” set;
      • Add adjacent to the cell on the opposite side of the wall in the "Special List of Walls";
      • Returning to paragraph 3.
      
      
   2. If it is empty, the maze generation is complete.
   
   (control arrows).
   
   Good luck!
   
   PS If during the passage you did not jump out anything (on the screen), then for some reason the picture did not load.
   
   PPS The code on JSFiddle is slightly modified (compressed) in order to fit in 40 lines (do not hit!).