Maze Solver
Posted: March 2nd, 2018, 11:57 pm
I made a ten-state von-Neumann rule that can solve mazes:
It does this by filling the maze with cells defined by what direction they were filled from.
Once the goal is located, the fill directions are used to backtrack to the start.
Your start cell (a fill cell) should be against a wall and have its fill direction coming from the wall to prevent the backtrack from overshooting.
Your goal cell cannot have its fill direction coming from a wall (or the backtracking will not work) and should have its fill direction coming from the direction it will be reached first from.
A big example maze:
Code: Select all
@RULE Solver
0 vacuum
1 wall
2 fill from N
3 fill from E
4 fill from S
5 fill from W
6 path from N
7 path from E
8 path from S
9 path from W
@TABLE
n_states:10
neighborhood:vonNeumann
symmetries:none
var a = {0,1,2,3,4,5,6,7,8,9}
var b = a
var c = b
var d = c
var f1 = {2,3,4,5}
var f2 = f1
var f3 = f2
var f4 = f3
# draw path
0,f1,b,c,d,2
0,a,f2,c,d,3
0,a,b,f3,d,4
0,a,b,c,f4,5
# retrace path
2,a,b,6,d,6
3,a,b,6,d,7
4,a,b,6,d,8
5,a,b,6,d,9
2,a,b,c,7,6
3,a,b,c,7,7
4,a,b,c,7,8
5,a,b,c,7,9
2,8,b,c,d,6
3,8,b,c,d,7
4,8,b,c,d,8
5,8,b,c,d,9
2,a,9,c,d,6
3,a,9,c,d,7
4,a,9,c,d,8
5,a,9,c,d,9
@COLORS
1 130 130 130
2 140 000 110
3 130 000 120
4 120 000 130
5 111 000 140
6 060 180 060
7 065 170 065
8 070 160 070
9 075 150 075
Once the goal is located, the fill directions are used to backtrack to the start.
Your start cell (a fill cell) should be against a wall and have its fill direction coming from the wall to prevent the backtrack from overshooting.
Your goal cell cannot have its fill direction coming from a wall (or the backtracking will not work) and should have its fill direction coming from the direction it will be reached first from.
A big example maze:
Code: Select all
x = 197, y = 131, rule = Solver
8.16A$7.A16.5A$7.A21.7A$7.A28.14A$7.A42.6A$6.2A48.9A$5.2A58.3A$4.19A
45.8A$4.A18.6A47.4A$4.A24.9A42.4A$4.A32.10A37.3A$4.A42.7A33.2A$4.A48.
6A30.2A$4.5A46.A3.15A17.A$4.A3.8A39.A18.5A13.2A38.33A14.10A$4.A10.6A
34.A22.3A13.2A5.31A7.A25.15A8.A$4.A15.7A28.A25.2A13.5A9.A28.A49.A$4.A
22.4A24.A26.3A25.A28.A49.A$4.A26.17A7.A29.2A23.A28.A49.A$4.A50.A6.11A
13.A23.A28.A17.11A22.A$4.A50.A5.2A9.7A7.A24.A27.A6.12A10.4A18.A$4.A
49.A6.A16.2A6.A10.5A9.A13.6A8.A6.A24.12A7.A$4.A8.10A31.A6.A17.A6.A9.
2A3.2A8.A7.7A4.3A6.A6.A35.A7.A$4.A8.A9.7A24.A6.A17.A6.A8.2A5.2A7.A7.A
19.A6.A35.A7.A$4.A8.A14.A.12A12.A6.A17.A5.2A7.2A7.A7.A7.A18.A7.A35.A
7.A$4.A8.A14.A12.3A10.A6.2A16.A5.A7.2A8.A7.A7.A18.A7.A35.A7.A$4.A8.A
13.2A14.12A6.A6.A10.A5.A7.A9.A7.A7.A18.A7.A35.A7.A$4.A8.A13.A14.A18.A
6.A9.A6.A7.A9.A7.A7.A18.A7.A35.A8.A$4.A8.A13.A14.A18.A6.2A8.A6.A7.A9.
A7.A7.A5.14A7.A7.20A8.A8.A$4.A8.A13.A14.A18.A7.A8.A6.A7.A9.A7.A7.A18.
A7.A7.A19.A7.A8.A$4.A7.A7.A6.A6.2A6.A18.A7.A8.A6.A7.A9.A7.A7.A18.A7.A
6.A20.A7.A8.A$4.A7.A7.A6.A6.A6.2A5.14A7.A7.2A6.A7.A9.A7.A7.A18.A7.A
27.A7.A8.A$4.A7.A7.A5.A6.2A6.A6.A12.A7.A7.A7.A7.A9.A7.A7.A18.2A6.A27.
2A6.A8.A$4.A7.A7.A5.A6.A7.A6.A12.A7.A7.A7.A7.A9.A6.2A7.A19.A6.A28.A6.
A8.A$4.A7.A7.A5.A6.A7.A5.2A12.A7.2A6.A7.A7.A9.A6.A8.A19.A6.2A.5A18.4A
6.A8.A$5.A6.A7.A5.A6.A7.A5.A13.A8.A6.A7.A7.A9.A6.A8.A.11A7.A5.4A4.3A
13.4A9.A8.A$5.A6.A7.A2.F2.A6.A7.A5.A7.A5.A8.A6.A7.2A6.A9.A6.A8.2A18.A
4.A10.15A12.2A7.A$5.A6.A8.6A6.A7.A5.A7.A5.A8.A6.A8.A6.A16.A8.A19.A4.A
38.A7.A$5.A6.A20.A13.A6.2A5.A8.A6.A8.A7.A15.A8.A19.A4.A38.A7.A$5.A6.A
20.A12.2A6.A6.A8.A6.A16.2A14.A8.A19.A4.A38.A7.A$5.A6.A18.4A11.A7.A6.A
8.A6.A18.2A12.A8.A19.A3.2A38.A7.A$5.A6.3A15.3A2.3A8.A7.A6.A8.A6.2A18.
10A3.A8.A19.A3.A39.A7.A$5.A9.A14.A7.5A3.A6.A7.A8.A7.A28.4A8.A19.A3.A
39.A7.A$5.A10.4A9.2A11.7A4.A7.A8.A8.2A38.A19.A3.A9.15A15.A7.A$5.A13.
4A6.A19.5A7.A8.A9.11A28.A18.2A3.A23.3A13.2A6.A$5.A16.8A22.2A7.2A7.A
20.7A21.A6.13A4.A26.5A9.A6.A$5.A23.5A19.2A7.2A6.A27.6A15.A18.A4.A31.
3A6.A6.A$5.7A22.2A18.A9.2A4.A32.4A12.A23.A33.A6.A6.A$4.2A5.4A21.2A17.
A9.2A3.A35.3A10.A23.A34.A5.2A5.A$4.2A8.3A20.A.5A11.2A9.A3.A37.4A7.A
23.A34.A6.2A4.A$4.A12.3A17.3A3.2A11.2A8.2A2.A40.10A22.A18.7A9.2A6.A4.
A$4.A15.4A20.2A11.2A8.3A.A8.8A32.2A15.A5.A15.4A16.A7.A3.A$4.A19.4A17.
3A10.A10.3A5.3A7.2A5.13A14.2A4.2A6.24A20.A7.A3.A$4.A22.5A16.2A8.A12.
7A10.7A11.3A13.7A3.4A43.2A6.A3.A$4.A27.2A15.2A7.2A11.4A33.3A17.4A48.A
6.A3.A$4.A28.3A14.2A7.A14.4A32.3A67.2A5.A3.A$3.A31.5A11.A8.A16.4A31.
3A58.A7.A5.A3.A$3.A35.2A10.2A7.A19.2A32.5A52.2A8.A4.2A3.A$3.A36.2A10.
A7.3A19.A35.4A44.5A10.2A.3A4.A$3.A6.A5.2A23.2A9.A7.A2.2A17.10A30.5A
19.20A16.3A6.A$3.A6.A5.A.6A19.A8.A6.A4.2A26.2A32.3A16.2A7.A36.A$2.A7.
A5.A7.3A16.A7.2A4.3A5.A28.9A26.3A12.2A8.2A35.A$2.A7.A5.A10.5A11.A7.A
5.2A7.9A27.11A18.3A9.2A10.A20.2A13.A$2.A7.A5.A14.6A6.2A6.A5.A9.A6.3A
35.11A10.2A7.A12.A19.2A7.8A$2.A7.A5.A19.2A6.3A4.A5.A8.A9.3A43.A10.A7.
A13.A17.2A8.2A6.A$2.A7.A4.2A20.2A10.3A5.A8.A11.A43.A10.A7.A13.A17.A8.
A8.A$2.A7.A4.A6.A15.3A8.A7.A7.2A12.7A36.A10.A7.A13.9A8.A8.2A8.A$2.A6.
A5.A3.4A17.A8.A6.2A5.3A13.A5.2A35.A10.A6.A22.A8.A8.A9.A$.A7.A6.4A20.
2A7.A5.2A6.A15.A6.2A5.A6.9A13.A10.A6.A22.A7.2A7.A10.A$.A7.A31.2A5.A6.
A7.A7.A7.A8.6A6.A8.3A10.A10.A6.A22.A7.A7.A11.A$.A6.2A18.8A6.2A4.A6.A
7.A7.A7.A13.A6.A10.A10.A10.A6.A22.A7.A7.A11.A$.A5.2A15.5A6.2A7.A3.A5.
2A7.A7.A7.A13.A6.A11.A9.A10.A6.A13.A8.A7.A7.A11.A$.A5.A11.6A12.2A5.A
2.2A5.A15.2A7.A13.A6.A11.A9.A10.A6.A13.A8.A7.A7.A4.2A5.A$.A5.2A9.2A
18.A5.A2.A6.2A14.A8.A13.A6.A11.A9.A10.A6.A13.A8.A7.A7.A5.A5.A$.A6.2A
4.5A19.A5.4A7.4A11.A8.A13.A6.A11.2A8.A10.A6.A13.A8.A7.A13.A5.A$.A7.6A
23.2A8.A9.4A8.A8.A5.A7.A6.A12.A8.A10.A6.A13.A8.A7.A13.A5.A$.A37.2A7.
2A11.3A5.A9.A5.A6.A7.A3.2A7.2A7.A10.A6.A12.A9.A7.A13.A5.A$.A19.2A8.2A
7.2A8.4A9.7A9.A5.A6.A7.A4.A8.A7.A10.A6.A12.A9.A7.A13.A5.A$.A20.A9.A8.
A11.5A10.2A9.A5.A6.A7.A4.A8.A7.A10.A6.A11.2A9.A7.A14.A4.A$.A21.A8.2A
7.2A14.A11.A9.A5.A5.2A7.A4.A8.A7.A10.A6.A11.A10.A8.A13.A3.A$.A22.2A7.
2A7.A15.2A10.A8.A5.A5.A7.2A4.A8.A7.A10.A6.A11.2A9.A8.A13.A3.A$.A23.2A
8.A6.A16.4A7.A7.A6.5A.A7.A5.A8.A7.A10.A6.A12.A9.A8.A13.A3.2A$9A17.A9.
2A24.3A5.A7.A10.2A8.A5.A8.A7.A10.A6.2A11.A18.2A12.A4.A$.A6.8A11.A9.2A
25.A5.A7.A20.A5.A8.A7.A10.A7.A11.A18.15A4.A$2.A12.4A9.A9.A31.A7.A20.A
5.A8.A7.A10.A7.A11.2A17.A18.A$2.A15.A9.2A8.2A30.A7.A20.A5.A8.A7.A10.A
7.A12.2A3.14A19.A$2.A16.A9.2A8.A30.A8.7A12.2A5.A8.A7.A10.2A6.A12.6A
32.A$3.A16.A9.A8.A6.14A10.A15.9A3.A6.A8.A7.2A10.A6.2A9.3A4.2A31.A$3.A
16.2A8.A8.A19.4A8.A22.3A.A6.A8.A8.A10.A7.3A3.5A7.A32.A$3.A17.A8.A8.A
23.A7.A24.3A6.A8.A8.A10.A10.3A12.A10.10A12.A$3.A17.A8.A8.2A22.5A3.A
33.A8.A8.A10.A25.A10.A8.A4.9A$3.A17.2A7.A9.A26.5A33.A8.A9.A9.A25.A10.
A8.A12.A$3.A18.A7.2A8.A30.2A32.A8.A9.A9.A25.A10.A8.A12.A$4.A17.A8.A8.
A31.2A31.A8.A9.A9.A25.A10.A8.A12.A$4.A7.A9.A8.A8.2A31.2A30.A8.A9.A9.A
14.A10.A10.A8.A12.A$4.A7.A9.A9.A8.15A19.2A28.A8.A9.A9.15A11.2A9.A8.A
12.A$4.A7.2A8.A9.A23.2A18.22A7.A8.A9.A9.A26.A9.A9.8A4.A$4.A8.A8.2A8.
2A24.11A29.8A8.A9.A9.A26.A9.A8.A13.A$4.A8.A9.A9.A34.A45.A9.A9.A26.A
18.A13.A$4.A8.A9.A9.2A33.A45.A9.A9.A20.6A18.A14.A$4.A8.A9.2A9.A33.A
45.A19.A5.16A23.A14.A$5.A7.A10.A10.2A32.A44.A19.7A38.2A13.A$5.A7.A11.
A9.A.16A16.A44.2A52.4A8.A13.A$5.A7.A11.4A6.A16.3A14.A11.10A24.A50.2A
3.10A13.A$5.A7.A21.A18.2A13.A20.7A18.A49.2A13.A7.7A$5.A7.2A20.A19.2A
12.A27.6A12.A49.A14.A14.A$5.A8.A20.A20.8A5.A32.11A2.2A47.2A14.A14.A$
6.A7.2A19.A33.A43.11A39.2A8.A6.A14.A$6.A8.A19.A34.A52.4A29.8A9.A6.A
14.A$6.A8.2A18.A34.A7.A48.12A8.10A16.A6.A14.A$6.A9.7A12.A34.A8.3A57.
8A26.A6.A14.A$6.A15.5A8.A34.A11.A62.A27.A6.A14.A$6.A19.3A6.A9.2A23.2A
11.4A58.A27.A6.A14.A$6.A21.8A10.8A17.A15.3A55.A14.14A6.A15.A$6.A46.
19A18.7A48.A9.6A19.A7.A7.A$7.A63.A24.4A45.A7.2A25.A7.A7.A$7.A63.A28.
5A40.A7.A26.A7.A7.A$7.A63.A33.5A36.A6.A26.A7.A7.A$7.A63.A38.6A11.6A
13.A6.A26.A7.A7.A$7.A63.A44.11A6.14A6.2A8.7A10.A7.A7.A$7.A63.A82.A7.
2A5.7A4.A8.A6.A$7.81A66.A20.3A2.A8.A6.A$88.7A59.A22.4A8.A6.A$95.3A56.
A25.A8.A6.A$98.4A52.2A33.A6.A$102.4A49.A34.A5.A$106.6A43.A34.A5.A$
112.16A17.21A24.A5.A$128.17A21.10A14.A5.A$176.13A2.A.D2.A$189.8A!