-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathjsmaze4.html
2647 lines (2342 loc) · 90 KB
/
jsmaze4.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<?xml-stylesheet href="#maze-style" type="text/css"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<title>Maze</title>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<style type="text/css" id="maze-style">
html { width: 100vw; height: 100vh; }
body, div, table, tr, th, td { margin: 0; padding: 0; border: 0; }
body { width: 100vw; height: 100vh; background: #ddd; }
div#wrap { width: 100vw; height: 100vh; margin: auto auto; }
div#svg-container { width: 100vw; height: calc(100vh - 50px); background: #fff; position: relative; }
div#form { width: 100vw; min-height: 50px; position: relative; }
h1 { display: inline-block; margin: 0; margin-right: 2rem; }
svg { width: 100%; height: 100%; }
svg rect { stroke: #00f; stroke-width: 1; }
svg polygon.depth-map { stroke-width: 1; }
/* depth map inserted here */
svg line.wall { stroke: white; stroke-width: 1; }
svg line.wall.open { opacity: 0.0; }
svg line.edge { stroke: #fff; stroke-width: 1; opacity: 0.0; z-index: 1; }
svg line.edge.open { stroke-width: 2; }
svg line.edge.closed { stroke-width: 1; stroke-dasharray: 4 1; }
svg.plain line.edge { stroke: #0800ff; }
svg.plain line.closed { stroke: #0800ff; }
svg circle.cell-center { stroke: #ff0008; stroke-width: 1; opacity: 0.0; z-index: 2; }
svg.plain { background: white; }
svg.plain line.wall { stroke: black; }
svg.plain polygon.depth-map { fill: white; stroke: white; }
svg.show-sets-1 line.set-0 { stroke: #f00; }
svg.show-sets-1 line.set-1 { stroke: #0f0; }
svg.show-sets-2 line.set-0 { stroke: #0f0; }
svg.show-sets-2 line.set-1 { stroke: #f00; }
svg.show-sets-3 line.set-0 { stroke: #000; }
svg.show-sets-3 line.set-1 { opacity: 0.0; }
svg.show-sets-4 line.set-0 { opacity: 0.0; }
svg.show-sets-4 line.set-1 { stroke: #000; }
svg.show-sets-5 line.wall.open { opacity: 1.0; }
svg.show-sets-6 line.wall { opacity: 0.05; }
svg.show-sets-6 line.edge { opacity: 1.0; }
svg.show-sets-6 line.edge.closed { opacity: 0.33; }
svg.show-sets-6 circle.cell-center { opacity: 1.0; }
svg.no-depth polygon.depth-map { opacity: 0.0; }
svg.no-depth rect#bg { fill: blue; }
svg.plain rect#bg { fill: white; background: white; }
svg polyline#solution { fill: none; stroke-width: 2; }
svg polyline#solution { stroke: #ff0; z-index: 5; }
svg.plain polyline#solution { stroke: #f0f; }
svg polyline#solution { opacity: 0.0; }
svg.show-solution polyline#solution { opacity: 1.0; }
</style>
<script type="text/javascript">
// <![CDATA[
// Get query parameters from the url. This returns an object like this:
// ?param => args['param']=true
// ?param=value => args['param']=value
// ?param[]=value => args['param']=[value,...]
function get_args() {
var args = new Object();
var query_string=location.search.slice(1);
if (!query_string) return args;
var query_pairs = query_string.split('&');
var pname, pvalue;
for (var i=0 ; i<query_pairs.length ; i++) {
var equal_position=query_pairs[i].indexOf('=');
if (equal_position<0) {
args[my_uri_decoder(query_pairs[i])]=true;
} else {
pname=my_uri_decoder(query_pairs[i].slice(0,equal_position));
pvalue=my_uri_decoder(query_pairs[i].slice(equal_position+1));
// If a name is followed by [], then we'll create an array of
// values. This is good for a multiple-select box
if (pname.match(/\[\]$/)) {
pname=pname.slice(0,-2);
if (!args[pname]) args[pname]=new Array();
args[pname].push(pvalue);
} else {
args[pname]=pvalue;
}
}
}
return args;
}
function my_uri_decoder(v) {
return decodeURIComponent(v.replace(/\+/g,'%20'));
}
// Easily add functions to run at load time
function add_body_onload(func) {
var old_body_onload=window.onload;
window.onload=function() {
if (old_body_onload) { old_body_onload(); }
func();
}
}
// Gives us a random permutation. This is Durstenfeld's
// version of Knuth's shuffle, with in-place swapping.
function random_perm(len) {
var orig=Array(len);
for (var x=0; x<len; x++) {
orig[x]=x;
}
for (var x=len-1; x>0; x--) {
var offset=Math.floor(Math.random()*(x+1));
if (offset != x) {
var tmp = orig[offset];
orig[offset] = orig[x];
orig[x] = tmp;
}
}
return orig;
}
// after "svg polygon.depth-map" we can add some lines for depth
var style_sheet = document.getElementById('maze-style').sheet;
var svg_polygon_line_number = Array.from(style_sheet.cssRules).findIndex(line => line.selectorText == 'svg polygon.depth-map')
if (svg_polygon_line_number !== null) {
//svg polygon.depth-map.depth-0 { fill: #000000; stroke: #000000; }
for (var i=0; i<256; i++) {
var color = i.toString(16);
if (color.length==1) { color = '0' + color; }
style_sheet.insertRule('svg polygon.depth-map.depth-' + i + ' { fill: #0000' + color + '; stroke: #0000' + color + '; }', svg_polygon_line_number);
}
}
// The maze is set on a set of points, some of which connect to
// form walls. A closed set of walls connects to create a
// cell. We use object references between cells and walls
// to quickly be able to traverse the maze. So, a wall has a
// list of both cells to which it connects and a cell has a
// list of all of its walls.
//
// Points have an x,y coordinate that exists to specify their
// position relative to other points. They also have a set of
// walls that use them as an end point.
function Point(x, y) {
this.x=x;
this.y=y;
this.walls=[];
}
Point.prototype = {
// Add another point to this one.
plus: function(other_point) {
return new Point(this.x+other_point.x, this.y+other_point.y);
},
// Subtract another point from this one
minus: function(other_point) {
return new Point(this.x-other_point.x, this.y-other_point.y);
},
// Divide the point
divided_by: function(divisor) {
return new Point(this.x / divisor, this.y / divisor);
},
// for generalized code the multiplier might be another
// point. Assuming a fixed number here.
times: function(multiplier) {
return new Point(this.x * multiplier, this.y * multiplier);
},
// Compute distance between points. Between "distance_to"
// and "angle_to" we have a set of polar coordinates of
// "other_point" if "this" is at the origin.
distance_to: function(other_point) {
return Math.sqrt(Math.pow(other_point.x-this.x,2) + Math.pow(other_point.y-this.y,2));
},
// From this point, find the angle to another point
angle_to: function(other_point) {
return Math.atan2(other_point.y-this.y,other_point.x-this.x)
},
// Given a wall, find the next wall in clockwise order
next_cw_wall: function(this_wall) {
var wall_at = null;
for (var j=0 ; j<this.walls.length ; j++) {
if (this.walls[j] == this_wall) {
wall_at = j;
break;
}
}
if (wall_at !== null) {
if (wall_at > 0) {
return this.walls[wall_at-1];
} else {
return this.walls[this.walls.length-1];
}
} else {
return null;
}
},
// Sorts all walls attached to this point in rotational order
sort_walls: function() {
var walls = [];
for (var j = 0 ; j < this.walls.length ; j++) {
var wall = this.walls[j];
walls.push([wall,this.angle_to(wall.other_end(this))]);
}
function wall_sorter(a,b) { return(a[1]-b[1]); }
walls.sort(wall_sorter);
this.walls = [];
for (var j = 0 ; j < walls.length ; j++) {
this.walls.push(walls[j][0]);
}
},
// Removes duplicate walls - they should already be sorted.
// This will remove the wall reference from the other end
// point, also.
uniq_walls: function() {
// assuming there are walls - if none or one return immediately
if (this.walls.length < 2) return;
var last_wall_other_end = null;
for (var j = this.walls.length-1 ; j>=0 ; j--) {
var wall = this.walls[j];
var other_end = wall.other_end(this);
if (other_end == last_wall_other_end) {
// This wall is going away - remove from other end
// point wall list, also
this.walls.splice(j,1);
for (var k=other_end.walls.length-1 ; k>=0 ; k--) {
if (other_end.walls[k] === wall) {
other_end.walls.splice(k,1);
}
}
} else {
last_wall_other_end = other_end;
}
}
},
// Finds all faces attached to a point that aren't yet "found"
// and returns an array of Cells. The "signed_area" makes sure
// that we only find faces that have walls/vertices in
// clockwise order. The reason is that the algorithm will find
// the face from all of the outside walls. The
// "safety_counter" can also make it fairly easy to ignore
// those, but ultimately the only real way to ignore it in all
// circumstances is to recognize that it'll have a negative
// "signed_area".
find_faces: function(max_face_size) {
var ret_cells = [];
for (var i=0 ; i<this.walls.length ; i++) {
var wall = this.walls[i];
if (!wall.traversed(this,wall.other_end(this))) {
var safety_counter = 0;
var walls = [];
var this_point=this;
var other_point;
var signed_area = 0; // Make sure we're going around clockwise
do {
walls.push(wall);
other_point = wall.other_end(this_point);
signed_area += (this_point.x * other_point.y - other_point.x * this_point.y);
this_point = wall.traverse(this_point,other_point);
wall = this_point.next_cw_wall(wall)
safety_counter++;
} while (this_point != this && wall);
if (walls.length <= max_face_size && signed_area > 0 && wall) {
ret_cells.push(new Cell(walls));
}
}
}
return ret_cells;
},
// returns a string representing the point
toString: function() {
return "" + this.x + ',' + this.y;
},
// remove all walls
remove_walls: function() {
this.walls = [];
}
};
// Walls have a few pieces of information: two end points, the
// state (open (0) or closed (1)), and the two cells that it
// connects.
function Wall(p1,p2) {
this.points=[p1,p2];
this.state=1;
this.cells=[];
p1.walls.push(this);
p2.walls.push(this);
// These are used for face finding - "down" is "point 0 to
// point 1", "up" is "point 1 to point 0".
this.traversed_down=false;
this.traversed_up=false;
// Used to keep track of both "sides"
this.set=null;
}
Wall.prototype = {
// Return a point representing the center of this wall
center: function() {
return(new Point((this.points[0].x+this.points[1].x)/2,(this.points[0].y+this.points[1].y)/2));
},
// Returns true if the wall is open
is_open: function() {
return (this.state==0);
},
// Marks a wall as open, returns "true" if the wall
// state changes as a result
open: function() {
if (this.state==0) {
return null;
} else {
this.state=0;
return true;
}
},
// Marks a wall as closed, returns "true" if the wall
// state changes as a result
close: function() {
if (this.state==1) {
return null;
} else {
this.state=1;
return true;
}
},
// Given a point, returns the "other end" point on the wall.
other_end: function(point) {
if (this.points[0] == point) {
return(this.points[1]);
} else if (this.points[1] == point) {
return(this.points[0]);
} else {
return null;
}
},
// Traverses a wall and marks the direction as traversed.
traverse: function(point0, point1) {
if (point0 == this.points[0] && point1 == this.points[1]) {
this.traversed_down = true;
return point1;
} else if (point0 == this.points[1] && point1 == this.points[0]) {
this.traversed_up = true;
return point1;
} else {
return null;
}
},
// Returns true if wall has already been traversed in given
// direction.
traversed: function(point0, point1) {
if (point0 == this.points[0] && point1 == this.points[1]) {
return this.traversed_down;
} else if (point0 == this.points[1] && point1 == this.points[0]) {
return this.traversed_up;
} else {
return null;
}
},
// returns a string representing the wall
toString: function() {
return this.points[0].toString() + ':' + this.points[1].toString();
},
// Each wall has one or two cells (it's possible that
// an edge wall may have only one cell). This will
// return "undefined" if there is no neighbor, otherwise it
// will return the neighbor given a reference to one cell.
neighbor: function(cell) {
if (this.cells[0] == cell) {
return this.cells[1];
} else {
return this.cells[0];
}
},
// Helper to get the length of a wall
length: function() {
return this.points[0].distance_to(this.points[1]);
},
// Get the angle of the wall
angle: function() {
return this.points[0].angle_to(this.points[1]);
}
};
// Cells have a set of walls along with a few other pieces of
// information that are used while generating a maze.
// Generally, a permutation of wall directions and a pointer to
// the "current" item in the permutation list.
function Cell(walls) {
this.walls = walls;
for (var i=0 ; i<this.walls.length ; i++) {
this.walls[i].cells.push(this);
}
this.perm=random_perm(this.walls.length);
this.current_perm=0;
this.entry_wall=undefined;
this.depth=undefined;
// Used in drunk walk algorithm
this.serial=undefined;
}
Cell.prototype = {
// Returns a point representing the exact center of the cell.
center: function() {
var x_avg = 0.0;
for (var i=0 ; i<this.walls.length ; i++) {
x_avg += this.walls[i].points[0].x;
x_avg += this.walls[i].points[1].x;
}
x_avg /= this.walls.length * 2;
var y_avg = 0.0;
for (var i=0 ; i<this.walls.length ; i++) {
y_avg += this.walls[i].points[0].y;
y_avg += this.walls[i].points[1].y;
}
y_avg /= this.walls.length * 2;
return(new Point(x_avg,y_avg));
},
// Return a list of all vertices of a cell, in order
vertices: function() {
var points = [];
// I need to pick only a single point from each wall, and it
// will be the point that isn't in the next wall.
for (var i=0 ; i<this.walls.length ; i++) {
var this_wall = this.walls[i];
var next_wall = this.walls[i+1];
if (!next_wall) { next_wall = this.walls[0]; }
if (this_wall.points[0] != next_wall.points[0] && this_wall.points[0] != next_wall.points[1]) {
points.push(this_wall.points[0]);
} else {
points.push(this_wall.points[1]);
}
}
return points;
},
// Return a list of neighboring cells
neighbors: function() {
var ret = new Array;
for (var i=0 ; i < this.walls.length ; i++) {
var this_wall = this.walls[i];
var this_neighbor = this_wall.neighbor(this);
if (this_neighbor) { ret.push(this_neighbor); }
}
return ret;
},
// Return a list of neighboring cells that haven't been visited
unvisited_neighbors: function() {
var ret = new Array;
for (var i=0 ; i < this.walls.length ; i++) {
var this_wall = this.walls[i];
var this_neighbor = this_wall.neighbor(this);
if (this_neighbor && !this_neighbor.visited()) { ret.push(this_neighbor); }
}
return ret;
},
visited: function() {
for (var i=0 ; i<this.walls.length ; i++) {
if (this.walls[i].is_open()) {
return true;
}
}
return false;
}
};
// A maze is a collection of cells with a path through them.
// It is two graphs that are interconnected - one which is a
// set of all walls (close and open) and the other a path
// through the open walls. This data structure holds
// everything of interest about the maze.
function Maze(xsize,ysize,base_style,maze_style) {
// General data and accessors
this.points = [];
this.walls = [];
this.cells = [];
this.start_point=null;
this.end_point=null;
this.start_wall=null;
this.end_wall=null;
this.max_depth=null;
this.end_depth=null;
this.base_style=Maze.base_styles_info[base_style];
if (!this.base_style) {
throw new Error("Unknown base style: " + base_style);
}
this.maze_style=Maze.maze_styles_info[maze_style];
if (!this.maze_style) {
throw new Error("Unknown maze style: " + maze_style);
}
if (xsize < this.maze_style.min_xsize) {
throw new Error("Minimum xsize is " + this.maze_style.min_xsize);
}
if (ysize < this.maze_style.min_ysize) {
throw new Error("Minimum ysize is " + this.maze_style.min_ysize);
}
this.xsize = xsize * this.base_style.x_multiplier;
this.ysize = ysize * this.base_style.y_multiplier;
// Now, we'll initialize the maze. First, set up the cells
// according to the "base style".
this.base_style.algo.call(this, this.xsize, this.ysize, this.points, this.walls);
this.sort_walls_for_points(this.points);
// We now have a complete set of points and walls, we need to
// walk that data structure and determine a set of cells.
// In graph parlance, points == vertices, walls == edges, and
// cells == faces.
// There's a better more efficient way to do this - figure it
// out later.
// TODO: figure out a more efficient way to do this
for (var j=0 ; j<this.points.length ; j++) {
var faces=this.points[j].find_faces(this.base_style.max_face_size);
this.cells = this.cells.concat(faces);
}
// At this point, we're ready to actually make a maze. Get
// the start and end cells, then generate the maze.
this.start_wall = this.find_start_wall(this.points);
this.end_wall = this.find_end_wall(this.points);
this.maze_style.algo.call(this);
// Purely for aesthetics, open the corners
this.open_corners();
// And set the max depth and end depth, which are useful for
// rendering.
this.find_max_depth();
this.end_depth = this.end_cell().depth;
// Split the walls into two sets
this.set_wall_sets();
}
Maze.base_styles = {};
Maze.maze_styles = {};
// To create a maze, we need to move around until we're back to
// the original point. There's enough information stored in
// each cell to perform this algorithm non-recursively in a
// while loop.
// If performed recursively, this algorithm is simple...
Maze.maze_styles.recursive = function() {
function recursive_maze(cell,entry_wall,depth) {
cell.depth=depth;
cell.entry_wall=entry_wall;
// Now, go through the surrounding cells and recurse
for (var k=0 ; k<cell.perm.length ; k++) {
var wall_num = cell.perm[k];
var neighbor = cell.walls[wall_num].neighbor(cell);
if (neighbor && !neighbor.visited()) {
cell.walls[wall_num].open();
arguments.callee(neighbor,cell.walls[wall_num],depth+1);
}
}
}
recursive_maze(this.start_cell(),null,0);
}
// This is Prim's algorithm. The idea is to start at a random
// location (or at "the starting point", it ultimately won't
// matter) and simply add cells one at a time to the current
// maze in a random order. Basically, any cell that's touching
// an existing maze cell is fair game for attaching to the
// maze.
// The "official" way of doing this is to separate the maze
// into three cell types: "in", "out", and "frontier". "in"
// cells are part of the maze, "frontier" cells are those which
// are next to an "in" cell, and "out" are all others. On each
// cycle a frontier cell is chosen at random, attached to the
// maze, and removed from the list of frontier cells. All of
// its neighbors which are "out" then become frontier cells and
// the cycle is repeated. It stops when there are no more
// frontier cells.
//
// There's no need for recursion.
Maze.maze_styles.prim = function() {
var frontier_cells = new Array;
// Doing this officially, start at a random location
var start = this.cells[Math.floor(Math.random() * this.cells.length)];
//var start = this.start_cell();
frontier_cells = start.unvisited_neighbors();
while (frontier_cells.length > 0) {
var next_cell = frontier_cells[Math.floor(Math.random() * frontier_cells.length)];
// My reading of Prim's algorithm is that we always
// connect back to the first cell for which this was a
// frontier. Oh well. I'd rather just make it random.
var visited_neighbor_walls = new Array;
var unvisited_neighbors = new Array;
for (var i=0 ; i<next_cell.walls.length ; i++) {
var this_wall = next_cell.walls[i];
var this_neighbor = this_wall.neighbor(next_cell);
if (this_neighbor) {
if (this_neighbor.visited()) {
visited_neighbor_walls.push(this_wall);
} else {
unvisited_neighbors.push(this_neighbor);
}
}
}
// now, we have a list of visited neighbors and a list of
// unvisited neighbors. Unvisited neighbors get added to
// the frontier list while one of the visited neighbors
// will be the lucky neighbor to which we'll connect.
if (visited_neighbor_walls.length) {
var connect_to_num = Math.floor(Math.random() * visited_neighbor_walls.length);
var connect_to_wall = visited_neighbor_walls[connect_to_num];
} else {
// There are no visited neighbors, which will only occur
// when we're at the start.
for (var connect_to_num=0 ; connect_to_num < next_cell.walls.length ; connect_to_num++) {
if (next_cell.walls[connect_to_num].neighbor(next_cell) == start) {
var connect_to_wall = next_cell.walls[connect_to_num];
break;
}
}
}
connect_to_wall.open();
// Remove this cell from the frontier list
for (var i = 0 ; i < frontier_cells.length ; i++) {
if (frontier_cells[i] == next_cell) {
frontier_cells.splice(i,1);
break;
}
}
// And add all unvisited neighbors to the frontier list
// (if they're not already there)
for (var i = 0 ; i < unvisited_neighbors.length ; i++) {
var found = false;
for (var j = 0 ; j < frontier_cells.length ; j++) {
if (frontier_cells[j] == unvisited_neighbors[i]) {
found = true;
break;
}
}
if (!found) {
frontier_cells.push(unvisited_neighbors[i]);
}
}
}
// This needs to have depth calculated independently
this.find_depth(this.start_cell(), null, 0);
}
// Like Prim's algorithm, but each "frontier" cell adds a path
// each cycle. In this case, a frontier cell is one in which
// there are neighbors that aren't yet part of the maze. When
// a cell has no more unvisited neighbors, it drops out of the
// frontier list.
Maze.maze_styles.bacterial = function() {
var frontier_cells = new Array;
// Doing this officially, start at a random location
var start = this.cells[Math.floor(Math.random() * this.cells.length)];
//var start = this.start_cell();
frontier_cells = [start];
while (frontier_cells.length > 0) {
var to_be_removed = new Array;
var current_frontier_length = frontier_cells.length;
var my_order = random_perm(current_frontier_length);
for (var k = 0 ; k < current_frontier_length ; k++) {
var next_cell = frontier_cells[my_order[k]];
var unvisited_neighbor_walls = new Array;
for (var i=0 ; i<next_cell.walls.length ; i++) {
var this_wall = next_cell.walls[i];
var this_neighbor = this_wall.neighbor(next_cell);
if (this_neighbor && !this_neighbor.visited()) {
unvisited_neighbor_walls.push([this_neighbor,this_wall]);
}
}
if (unvisited_neighbor_walls.length == 0) {
to_be_removed.push(my_order[k]);
} else {
// Choose one at random and move to it, and add it
// to the frontier list.
var item = unvisited_neighbor_walls[Math.floor(Math.random() * unvisited_neighbor_walls.length)];
var this_neighbor = item[0];
var this_wall = item[1];
this_wall.open();
frontier_cells.push(this_neighbor);
}
}
var remove_num;
to_be_removed.sort(function(a, b) { return a - b; });
// Remove frontier cells that have no unvisited neighbors
while (to_be_removed.length > 0) {
var remove_num = to_be_removed.pop();
frontier_cells.splice(remove_num,1);
}
}
// This needs to have depth calculated independently
this.find_depth(this.start_cell(), null, 0);
}
// My unicursal algorithm doesn't work well yet. It sometimes
// works.
//
// Odd way to make a maze - this is really a space filling
// curve. The idea of this is to have one long path from
// start to finish with no dead ends. The way to do this
// (or at least the way I'll do it) is that each time the maze
// touches a side or an existing path we have to check to make
// sure we didn't cut off any cells. If we did, we backtrack
// by one cell, closing the entry wall. In that case, after
// backtracking we need to next move to cell that will move us
// into the area that isn't filled - a wall between the
// original entry wall and the exit wall. If there is none we
// need to backtrack again until we can find one.
Maze.maze_styles.unicursal_better_but_nonfunctional = function() {
var end_cell = this.end_cell();
function check_neighbor(cell,entry_wall) {
if (!cell || cell == end_cell) {
return false;
} else {
var map = new Array(cell.walls.length);
cell.walls.forEach(function(wall,index,arr) {
var neighbor = wall.neighbor(cell);
map[index] = (!neighbor || neighbor.visited()) ? 'v' : 'u';
});
if (map.filter(function(x) { return x=='u'; }).length < 2) {
// This one only has a single way out
return true;
} else {
return false;
}
}
}
function recursive_maze(cell,entry_wall,depth) {
cell.depth=depth;
cell.entry_wall=entry_wall;
// Let's see if we're touching a cell that is either
// on the outside or is already part of the path,
// ignoring the cell from whence we came.
var pattern = new Array(cell.perm.length);
var must_visit = new Array(cell.perm.length);
for (var k=0 ; k<cell.walls.length ; k++) {
var neighbor = cell.walls[k].neighbor(cell);
pattern[k] = (!neighbor || neighbor.visited()) ? 'v' : 'u';
must_visit[k] = check_neighbor(neighbor, cell.walls[k]);
}
var must_visit_count = must_visit.filter(function(x) { return x; }).length;
if (must_visit_count > 1) {
// More than one "must visit cell", must backtrack
return true;
} else if (must_visit_count == 1) {
// Must visit this cell
var wall_num = must_visit.indexOf(true);
var neighbor = cell.walls[wall_num].neighbor(cell);
cell.walls[wall_num].open();
var backtrack = arguments.callee(neighbor,cell.walls[wall_num],depth+1);
if (backtrack) {
cell.walls[wall_num].close();
return false;
}
} else if (pattern.join('').match(/(v+|u+)/g).length >= 4) {
// We're touching an outside wall or another
// part of the path, make sure we didn't just
// cut off some cells. If we did cut off some
// cells, there will be a closed path of walls
// around the cells. If that closed path
// includes the "exit cell", it should be
// ignored. If it doesn't include the exit
// cell, it'll be enclosed and we'll backtrack.
// There is likely a way to determine this based
// on whether the path is clockwise or CCW
// depending on the relationship between the
// current cell and the touched cell/wall, but
// I'll figure that out later.
//
// A little later: This might not completely solve
// it, but if we run into another wall we can
// determine if this block cuts a space into two
// pieces. This is a dirt simple computation -
// between the current wall and the entry wall
// there should be closed walls with unvisited
// neighbor cells on each side. The only
// difference is if we're at the end cell, in
// which case any unvisited neighbor cells will
// cause a backtrack.
//
// More simply stated, if we start at 0 and go
// through all the walls on the current cell,
// we may find alternating sections of visited
// cell/outer wall, unvisited cell, visited
// cell/outer wall, unvisited cell. If we find
// that pattern, we backtrack.
//
// Okay, more. From the current cell, we need to
// determine which cell to visit next. Any other
// neighboring unvisited cells should have at least
// two walls that are on unvisited cells, and those
// two walls should share one end point. So if the
// current square causes any of its neighbors to have
// only one openable wall we need to backtrack.
return true;
}
// If it's the last cell, we backtrack if there
// are any unvisited cells around it.
if (cell == end_cell) {
if (pattern.indexOf('u') > -1) {
return true;
}
} else {
// If it's not the last cell and it's a dead end, then
// we backtrack
if (pattern.join('').match(/^v+$/)) {
return true;
}
}
var backtracked = false;
var visited_elsewhere = false;
// Now, go through the surrounding cells and recurse
var possible_walls = [];
for (var k=0 ; k<cell.perm.length ; k++) {
var wall_num = cell.perm[k];
if (pattern[wall_num] == 'u') {
var neighbor = cell.walls[wall_num].neighbor(cell);
cell.walls[wall_num].open();
var backtrack = arguments.callee(neighbor,cell.walls[wall_num],depth+1);
if (backtrack) {
cell.walls[wall_num].close();
backtracked = true;
} else {
visited_elsewhere = true;
}
}
}
if (!visited_elsewhere && backtracked) {
return true;
} else {
// Don't backtrack
return false;
}
}
recursive_maze(this.start_cell(),null,0);
}
// Really inefficient unicursal algorithm. This is a standard
// recursive backtracker with a slight modification. If we're
// at the last cell and there are no unvisited cells then we
// return "true". If the recursion returns true then we return
// true. If it's false then we try the next wall, and return
// false if all return false.
//
// Without offering a proof I believe that the time this takes
// to generate a random path grows exponentially with the maze
// size. Just doing simple tests, I can get it to work easily
// on a 7x5 square maze (at least one dimension has to be odd
// for a square maze), 9x6 works sometimes, but 11x7
// essentially locks up.
Maze.maze_styles.unicursal = function() {
var end_cell = this.end_cell();
var max_depth = this.cells.length-1;
function recursive_maze(cell,entry_wall,depth) {
cell.depth=depth;
cell.entry_wall=entry_wall;
// Check if this is the end (yes, I'm aware of the
// optimization).
if (cell == end_cell) {
if (depth == max_depth) {
return true;
} else {
return false;
}
}
// Now, go through the surrounding cells and recurse
for (var k=0 ; k<cell.perm.length ; k++) {
var wall_num = cell.perm[k];
var neighbor = cell.walls[wall_num].neighbor(cell);
if (neighbor && !neighbor.visited()) {
cell.walls[wall_num].open();
var winner = arguments.callee(neighbor,cell.walls[wall_num],depth+1);
if (winner) return true;
cell.walls[wall_num].close();
}
}
return false;
}
var success = recursive_maze(this.start_cell(),null,0);
if (!success) {
throw "Cannot create unicursal maze with these parameters."
}
}
// Create a maze using the drunk walk algorithm. In this
// algorithm, we create random segments that grow like the
// recursive algorithm above until they connect to another
// existing segment. Each cell has a "serial" number that
// specifies which segment it belongs to, so as a segment grows
// it can see if it's touching "self" or "other". It will
// connect to "other" and quit growing.
Maze.maze_styles.drunk_walk = function() {
function drunk_walk(cell, entry_wall, serial, depth) {
pieces_left--;
cell.serial = serial;
if (depth==0) return false;
for (var k=0 ; k<cell.perm.length ; k++) {
var wall_num = cell.perm[k];
var wall = cell.walls[wall_num];
if (wall != entry_wall && !wall.is_open()) {
var neighbor = wall.neighbor(cell);
if (neighbor) {
if (!neighbor.serial) {
wall.open();
var ret=arguments.callee(neighbor,wall,serial,depth-1);
if (!ret) return false;
} else if (neighbor.serial != serial) {
wall.open();
return false;
}
}
}
}
return true;
}
// Note that this is a scoped variable - the "drunk_walk"
// function refers to it.
var pieces_left = this.cells.length;