Skip to content

Commit 1debc37

Browse files
author
Kevin Nadro
committed
Added Maze creation example
I saw that there isn’t anything on disjoint sets or mazes under the examples so I implemented the process of making a maze. I have visualized a maze creation before (https://github.com/nadr0/Maze). I have always been a fan of visualizing data structures or algorithms and I though this was the perfect chance! My code is rather large but it gets the job done. I
1 parent fe7d899 commit 1debc37

File tree

5 files changed

+318
-1
lines changed

5 files changed

+318
-1
lines changed

‎algorithm/category.json

+2-1
Original file line numberDiff line numberDiff line change
@@ -102,7 +102,8 @@
102102
"etc": {
103103
"list": {
104104
"flood_fill": "Flood Fill",
105-
"cellular_automata": "Cellular Automata"
105+
"cellular_automata": "Cellular Automata",
106+
"create_maze": "Create Maze"
106107
},
107108
"name": "Uncategorized"
108109
}

‎algorithm/etc/create_maze/create_maze/code.js

+247
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,247 @@
1+
function buildMaze(){
2+
var mySet = new disjoint_set();
3+
var width = m;
4+
var height = n;
5+
var setSize = 0;
6+
var graph = [];
7+
var visitedMap = {};
8+
var walls = {};
9+
var rightWalls = [];
10+
var downWalls = [];
11+
var location = 0;
12+
13+
mySet.addElements(width*height);
14+
15+
// init 'graph'
16+
for (var i = 0; i < width; i++) {
17+
graph[i] = new Array(height);
18+
for(var j = 0; j < height; j++){
19+
graph[i][j] = location;
20+
21+
walls[location] = {down: true, right: true};
22+
visitedMap[location] = false;
23+
24+
rightWalls.push({x:i, y:j});
25+
downWalls.push({x:i, y:j});
26+
location++;
27+
}
28+
};
29+
30+
var rightWalls = shuffle(rightWalls);
31+
var downWalls = shuffle(downWalls);
32+
while(setSize != mySet.elements - 1){
33+
var randomWall = Math.floor((Math.random() * 2) + 1);
34+
if(randomWall === 1 && downWalls.length > 0){
35+
// Down wall
36+
var currNode = downWalls.pop();
37+
var i_x = currNode.x;
38+
var i_y = currNode.y;
39+
var i_y_down = i_y + 1;
40+
if(i_y_down < height){
41+
var u = graph[i_x][i_y];
42+
var v = graph[i_x][i_y_down];
43+
if(mySet.find(u) != mySet.find(v)){
44+
mySet.setUnion(u,v);
45+
setSize++;
46+
// delete wall
47+
walls[u].down = false;
48+
}
49+
}
50+
}else if(randomWall === 2 && rightWalls.length > 0){
51+
// Right Wall
52+
var currNode = rightWalls.pop();
53+
var i_x = currNode.x;
54+
var i_y = currNode.y;
55+
var i_x_right = i_x + 1;
56+
if(i_x_right < width){
57+
var u = graph[i_x][i_y];
58+
var v = graph[i_x_right][i_y];
59+
if(mySet.find(u) != mySet.find(v)){
60+
mySet.setUnion(u,v);
61+
setSize++;
62+
// delete wall
63+
walls[u].right = false;
64+
}
65+
}
66+
}
67+
}
68+
69+
//update deleted walls
70+
for (var i = 0; i < width; i++) {
71+
for(var j = 0; j < height; j++){
72+
var current_wall = walls[graph[i][j]];
73+
74+
if(current_wall.down === false){
75+
G[j*2 + 2][i*3 + 1] = ' ';
76+
G[j*2 + 2][i*3 + 2] = ' ';
77+
tracer._select(j*2 + 2, i*3 + 1)._wait();
78+
tracer._select(j*2 + 2, i*3 + 2)._wait();
79+
}
80+
// tracer._notify(i, j, G[i][j])._wait();
81+
if(current_wall.right === false){
82+
G[j*2 + 1][i*3 + 3] = ' ';
83+
tracer._select(j*2 +1 , i*3 + 3)._wait();
84+
}
85+
tracer._setData(G);
86+
}
87+
}
88+
89+
// Start location
90+
G[0][0] = '│';
91+
G[0][1] = ' ';
92+
G[0][2] = ' ';
93+
// End location
94+
G[v_end-1][h_end-1] = '│';
95+
G[v_end-1][h_end-2] = ' ';
96+
G[v_end-1][h_end-3] = ' ';
97+
98+
// clean up grid for looks
99+
for (var i = 0; i < v_end; i++) {
100+
for(var j = 0; j < h_end; j++){
101+
if(G[i][j] === '├'){
102+
if(G[i][j+1] === ' '){
103+
G[i][j] = '│';
104+
}
105+
}
106+
107+
if(G[i][j] === '┤'){
108+
if(G[i][j-1] === ' '){
109+
G[i][j] = '│';
110+
}
111+
}
112+
113+
if(G[i][j] === '┬'){
114+
if(G[i+1][j] === ' '){
115+
G[i][j] = '─';
116+
}
117+
}
118+
119+
if(G[i][j] === '┴'){
120+
if(G[i-1][j] === ' '){
121+
G[i][j] = '─';
122+
}
123+
}
124+
125+
if(G[i][j] === '┼'){
126+
if(G[i][j+1] === ' '&& G[i-1][j] === ' ' && G[i][j-1] !== ' ' && G[i+1][j] !== ' '){
127+
G[i][j] = '┐';
128+
}
129+
else if(G[i][j-1] === ' '&& G[i-1][j] === ' ' && G[i+1][j] !== ' ' && G[i][j+1] !== ' '){
130+
G[i][j] = '┌';
131+
}
132+
else if(G[i][j-1] === ' '&& G[i+1][j] === ' ' && G[i-1][j] !== ' ' && G[i][j+1] !== ' '){
133+
G[i][j] = '└';
134+
}
135+
else if(G[i][j+1] === ' '&& G[i+1][j] === ' ' && G[i-1][j] !== ' ' && G[i][j-1] !== ' '){
136+
G[i][j] = '┘';
137+
}
138+
139+
else if(G[i][j+1] === ' '&& G[i][j-1] === ' ' && (G[i+1][j] === ' ' || G[i-1][j] === ' ')){
140+
G[i][j] = '│';
141+
}
142+
else if(G[i+1][j] === ' '&& G[i-1][j] === ' ' && (G[i][j-1] === ' ' || G[i][j+1] === ' ')){
143+
G[i][j] = '─';
144+
}
145+
146+
else if(G[i][j+1] === ' '&& G[i][j-1] === ' ' ){
147+
G[i][j] = '│';
148+
}
149+
else if(G[i+1][j] === ' '&& G[i-1][j] === ' '){
150+
G[i][j] = '─';
151+
}
152+
else if(G[i+1][j] === ' ' && G[i-1][j] !== ' ' && G[i][j-1] !== ' ' && G[i][j+1] !== ' '){
153+
G[i][j] = '┴';
154+
}
155+
156+
else if(G[i-1][j] === ' ' && G[i+1][j] !== ' ' && G[i][j+1] !== ' ' && G[i][j-1] !== ' '){
157+
G[i][j] = '┬';
158+
}
159+
160+
else if(G[i][j+1] === ' ' && G[i-1][j] !== ' ' && G[i+1][j] !== ' ' && G[i][j-1] !== ' '){
161+
G[i][j] = '┤';
162+
}
163+
164+
else if(G[i][j-1] === ' ' && G[i-1][j] !== ' ' && G[i+1][j] !== ' ' && G[i][j+1] !== ' '){
165+
G[i][j] = '├';
166+
}
167+
168+
169+
}
170+
171+
}
172+
}
173+
174+
G[1][1] = 'S';
175+
G[v_end-1][h_end-2] = 'E';
176+
// last wall clean up for start & end locations
177+
if(G[0][3] === '┬'){
178+
G[0][3] = '┌';
179+
}
180+
if(G[v_end-1][h_end-4] === '┴'){
181+
G[v_end-1][h_end-4] = '┘';
182+
}
183+
184+
// set the data
185+
tracer._setData(G);
186+
}
187+
188+
class disjoint_set {
189+
constructor(){
190+
this.set = [];
191+
this.elements = 0;
192+
}
193+
addElements(numberOfElements){
194+
for(var i = 0; i < numberOfElements; i++){
195+
this.elements++;
196+
this.set.push(-1);
197+
}
198+
}
199+
find(element){
200+
if(this.set[element] < 0){
201+
return element;
202+
}else {
203+
return this.set[element] = this.find(this.set[element]);
204+
}
205+
}
206+
setUnion(_a,_b){
207+
var a = this.find(_a);
208+
var b = this.find(_b);
209+
210+
if(a != b){
211+
var newSize = (this.set[a] + this.set[b]);
212+
if(this.compareSize(a,b)){
213+
this.set[b] = a;
214+
this.set[a] = newSize;
215+
}else{
216+
this.set[a] = b;
217+
this.set[b] = newSize;
218+
}
219+
}
220+
}
221+
compareSize(a,b){
222+
if(this.set[a] === this.set[b]){
223+
return true;
224+
}else if(this.set[a] < this.set[b]){
225+
return true;
226+
}else{
227+
return false;
228+
}
229+
}
230+
}
231+
232+
// http://bost.ocks.org/mike/shuffle/
233+
function shuffle(array) {
234+
var m = array.length, t, i;
235+
// While there remain elements to shuffle…
236+
while (m) {
237+
// Pick a remaining element…
238+
i = Math.floor(Math.random() * m--);
239+
// And swap it with the current element.
240+
t = array[m];
241+
array[m] = array[i];
242+
array[i] = t;
243+
}
244+
return array;
245+
}
246+
247+
buildMaze();

‎algorithm/etc/create_maze/create_maze/data.js

+58
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
var tracer = new Array2DTracer ();
2+
var n = 6; // rows (change these!)
3+
var m = 6; // columns (change these!)
4+
5+
var h_end = m * 4 - (m-1);
6+
var v_end = n * 3 - (n-1);
7+
8+
var G = [];
9+
10+
for (var i = 0; i < v_end; i++) {
11+
G[i] = new Array(h_end);
12+
for(var j = 0; j < h_end; j++){
13+
14+
G[i][j] = ' ';
15+
16+
if(i === 0 && j === 0){ // top-left corner
17+
G[i][j] = '┌';
18+
}else if( i === 0 && j === h_end-1){ // top-right corner
19+
G[i][j] = '┐';
20+
}else if(i === v_end - 1 && j === 0){ // bottom-left corner
21+
G[i][j] = '└';
22+
}else if(i === v_end - 1 && j === h_end - 1){ // bottom-right corner
23+
G[i][j] = '┘';
24+
}
25+
else if( (j % 3 === 0) && (i % v_end !== 0 && i !== v_end-1 && i % 2 == 1)){
26+
G[i][j] = '│';
27+
}else if (i % 2 === 0){
28+
G[i][j] = '─';
29+
}
30+
31+
if(m > 1){
32+
if( j % 3 === 0 && j !== 0 && j !== h_end - 1 && i === 0){
33+
G[i][j] = '┬';
34+
}
35+
if( j % 3 === 0 && j !== 0 && j !== h_end - 1 && i === v_end-1){
36+
G[i][j] = '┴';
37+
}
38+
}
39+
40+
if(n > 1){
41+
if(i % 2 === 0 && i !== 0 && i !==v_end-1 && j === 0){
42+
G[i][j] = '├';
43+
}
44+
if(i % 2 === 0 && i !== 0 && i !==v_end-1 && j === h_end-1){
45+
G[i][j] = '┤';
46+
}
47+
}
48+
49+
if(n > 1 && m > 1){
50+
if(i % 2 === 0 && j % 3 === 0 && i !== 0 && j !== 0 && i !== v_end-1 && j !== h_end-1){
51+
G[i][j] = '┼';
52+
}
53+
}
54+
55+
}
56+
}
57+
58+
tracer._setData(G);

‎algorithm/etc/create_maze/desc.json

+9
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
{
2+
"Create Maze": "Building a maze can be done with using disjoint sets.",
3+
"References": [
4+
"<a href='https://en.wikipedia.org/wiki/Disjoint-set_data_structure'>Disjoint Sets Wikipedia</a>"
5+
],
6+
"files": {
7+
"create_maze": ""
8+
}
9+
}

‎gulpfile.babel.js

+2
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,7 @@
11
'use strict';
22

3+
var Promise = require('es6-promise').Promise;
4+
35
import path from 'path';
46
import gulp from 'gulp';
57
import uglify from 'gulp-uglify';

0 commit comments

Comments
 (0)