February 6, 2015 at 15:31A random maze on JS you yourself know how many lines
Having read the articles about [anything] in JavaScript in 30 lines of code, I thought: why am I worse? Not finding the item “writing bad code” in the list of his shortcomings, he decided to do something interesting.
Labyrinths always blew some magic and riddles in my direction, so the search for “something interesting” ended quickly enough. Unfortunately, the creation of the game dragged on for many hours of experimenting on the console and my nerves.
Initially, realizing the size of the righteous anger of adherents of immaculate programming, I did not plan to publish my works, but after the cat, a couple of friends and my pride liked the game, I decided to write an article (fortunately, the theoretical part can be introduced into it).
For supporters of the principle “you know less - sleep better” a link is offered on JSFiddle (arrow control).
What is the most difficult thing to create such a game? That's right, the generation of the maze itself. That is why at first I didn’t start by looking at existing algorithms and choosing the best one, but by creating my own wheel with preference and widowed aristocrats of the most strict rules.
My idea was simple, like Gregory Galloway’s snow: to write a recursive function that, starting at the point [0: 0], would run through the maze and “eat out” its path until it crawled out. As soon as she does this, we randomly select N cells from the path passed to her and run the same function from these cells.
Pros: the ability to adjust the complexity of the maze by calibrating the value of N.
Cons: the randomness of everything and everything.
No sooner said than done!.
After crying over my decision, I turned to experts for help. Fortunately, their advice proved H E M A R O .
Having studied these algorithms, I settled on the randomized Prim algorithm (in fact, having slightly altered it too), 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), cells (vertices) of which must belong to one of 2 sets:
1) “Walls” (black blocks), which form these bizarre maze patterns;
2) “Passages” (white blocks) - just what you can move around.
The algorithm is as follows:
Labyrinths always blew some magic and riddles in my direction, so the search for “something interesting” ended quickly enough. Unfortunately, the creation of the game dragged on for many hours of experimenting on the console and my nerves.
Initially, realizing the size of the righteous anger of adherents of immaculate programming, I did not plan to publish my works, but after the cat, a couple of friends and my pride liked the game, I decided to write an article (fortunately, the theoretical part can be introduced into it).
For supporters of the principle “you know less - sleep better” a link is offered on JSFiddle (arrow control).
Start
What is the most difficult thing to create such a game? That's right, the generation of the maze itself. That is why at first I didn’t start by looking at existing algorithms and choosing the best one, but by creating my own wheel with preference and widowed aristocrats of the most strict rules.
My idea was simple, like Gregory Galloway’s snow: to write a recursive function that, starting at the point [0: 0], would run through the maze and “eat out” its path until it crawled out. As soon as she does this, we randomly select N cells from the path passed to her and run the same function from these cells.
Pros: the ability to adjust the complexity of the maze by calibrating the value of N.
Cons: the randomness of everything and everything.
No sooner said than done!.
After crying over my decision, I turned to experts for help. Fortunately, their advice proved H E M A R O .
Prim's randomized algorithm
Having studied these algorithms, I settled on the randomized Prim algorithm (in fact, having slightly altered it too), 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), cells (vertices) of which must belong to one of 2 sets:
1) “Walls” (black blocks), which form these bizarre maze patterns;
2) “Passages” (white blocks) - just what you can move around.
The algorithm is as follows:
- We start with a table (graph), all cells (vertices) of which belong to the set of "Walls";
- Select a cell. We remove it from the set of “Walls” and add it to the set of “Passages”. All the walls adjacent to it (vertically and horizontally) are added to the "Special List of Walls
, approved by the plenary session of the State Duma"; - Take the "Special List of Walls."
- If it is not empty, then select a random wall from it
1) If the cell on the side opposite to the wall belongs to the set of “Passages”, then remove this wall from the “SPS” (special list of walls):
2) If the cell on the opposite side belongs to set of "Walls", then:- We remove this wall from the set of "Walls";
- Add this wall to the many “Passages”;
- We remove the cell on the opposite side from the set of "Walls";
- Add a cell on the opposite side to the set of “Passages”;
- Add the walls adjacent to the cell on the opposite side to the “Special List of Walls”;
- We return to point 3.
- If it is empty, then the labyrinth generation is complete.
(arrow control). - If it is not empty, then select a random wall from it
Good luck
PS If, when passing through, nothing popped up (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!).