Differences From Artifact [0bb4050087a6fb3f]:
- File
src/solver.d
- 2012-07-14 12:29:17 - part of checkin [9d4aca73fa] on branch trunk - GUI+Solver revived. (user: kinaba) [annotate]
To Artifact [e22cb888fb6353ea]:
- File
src/solver.d
- 2012-07-14 13:02:03 - part of checkin [b4aceba693] on branch trunk - 1 step death move detector rev.1 (user: kinaba) [annotate]
24 this(const(Game) g) 24 this(const(Game) g)
25 { 25 {
26 this.g = g.clone(); 26 this.g = g.clone();
27 } 27 }
28 28
29 char single_step() 29 char single_step()
30 { 30 {
31 char c = act(g); | 31 char c = act(g, death_move(g));
32 g.command(c); 32 g.command(c);
33 return c; 33 return c;
34 } 34 }
35 35
> 36 string death_move(const(Game) g)
> 37 {
> 38 string death;
> 39 foreach(char c; "UDLRW") {
> 40 Game gg = g.clone();
> 41 gg.command(c);
> 42 if( !gg.cleared && gg.dead )
> 43 death ~= c;
> 44 }
> 45 return death;
> 46 }
> 47
36 char act(const(Game) g) | 48 char act(const(Game) g, string death)
37 { 49 {
38 const Pos ro = g.map.robot; 50 const Pos ro = g.map.robot;
39 const Pos[] la = g.map.lambdas(); 51 const Pos[] la = g.map.lambdas();
40 const Pos li = g.map.lift; 52 const Pos li = g.map.lift;
41 53
42 char c = 'W'; 54 char c = 'W';
43 if( la.empty ) { 55 if( la.empty ) {
44 auto r = search(g, ro, li); | 56 auto r = search(g, ro, li, death);
45 c = r[0]; 57 c = r[0];
46 } else { 58 } else {
47 Tuple!(char,int)[] cand; 59 Tuple!(char,int)[] cand;
48 foreach(lam; la) 60 foreach(lam; la)
49 cand ~= search(g, ro, lam); | 61 cand ~= search(g, ro, lam, death);
50 sort!((Tuple!(char,int) c1, Tuple!(char,int) c2){ 62 sort!((Tuple!(char,int) c1, Tuple!(char,int) c2){
51 if(c1[1] != c2[1]) 63 if(c1[1] != c2[1])
52 return c1[1] < c2[1]; 64 return c1[1] < c2[1];
53 return c1[0] < c2[0]; 65 return c1[0] < c2[0];
54 })(cand); 66 })(cand);
55 c = cand[0][0]; 67 c = cand[0][0];
56 } 68 }
................................................................................................................................................................................
60 c = 'A'; 72 c = 'A';
61 } 73 }
62 else 74 else
63 g_wc = 0; 75 g_wc = 0;
64 return c; 76 return c;
65 } 77 }
66 78
67 Tuple!(char,int) search(in Game g, in Pos s, in Pos o) | 79 Tuple!(char,int) search(in Game g, in Pos s, in Pos o, string death)
68 { 80 {
69 const(Pos)[] q = [o]; 81 const(Pos)[] q = [o];
70 bool[][] v = new bool[][](g.map.H+2, g.map.W+2); 82 bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
71 for(int step=1; q.length; ++step) { 83 for(int step=1; q.length; ++step) {
72 Pos[] q2; 84 Pos[] q2;
73 foreach(p; q) { 85 foreach(p; q) {
74 int[] dy=[-1,+1,0,0]; 86 int[] dy=[-1,+1,0,0];
75 int[] dx=[0,0,-1,+1]; 87 int[] dx=[0,0,-1,+1];
76 for(int i=0; i<4; ++i) { 88 for(int i=0; i<4; ++i) {
77 int y = p.y+dy[i]; 89 int y = p.y+dy[i];
78 int x = p.x+dx[i]; 90 int x = p.x+dx[i];
79 if(v[y][x]) continue; 91 if(v[y][x]) continue;
80 if(y==s.y && x==s.x) { 92 if(y==s.y && x==s.x) {
81 if(i==0) return tuple('U',step); | 93 char c = "UDRL"[i];
82 if(i==1) return tuple('D',step); | 94 if( death.count(c) == 0 )
83 if(i==2) return tuple('R',step); | 95 return tuple(c,step);
84 if(i==3) return tuple('L',step); <
85 } else if(g.map[y,x]==' '||g.map[y,x]==' 96 } else if(g.map[y,x]==' '||g.map[y,x]=='
86 q2 ~= new Pos(y,x); 97 q2 ~= new Pos(y,x);
87 v[y][x]=true; 98 v[y][x]=true;
88 } else if(g.map[y,x]=='.' && g.map[y-1,x 99 } else if(g.map[y,x]=='.' && g.map[y-1,x
89 q2 ~= new Pos(y,x); 100 q2 ~= new Pos(y,x);
90 v[y][x]=true; 101 v[y][x]=true;
91 } 102 }
................................................................................................................................................................................
101 int[] dy=[-1,+1,0,0]; 112 int[] dy=[-1,+1,0,0];
102 int[] dx=[0,0,-1,+1]; 113 int[] dx=[0,0,-1,+1];
103 for(int i=0; i<4; ++i) { 114 for(int i=0; i<4; ++i) {
104 int y = p.y+dy[i]; 115 int y = p.y+dy[i];
105 int x = p.x+dx[i]; 116 int x = p.x+dx[i];
106 if(v[y][x]) continue; 117 if(v[y][x]) continue;
107 if(y==s.y && x==s.x) { 118 if(y==s.y && x==s.x) {
108 if(i==0) return tuple('U',step); | 119 char c = "UDRL"[i];
109 if(i==1) return tuple('D',step); | 120 if( death.count(c) == 0 )
110 if(i==2) return tuple('R',step); | 121 return tuple(c,step);
111 if(i==3) return tuple('L',step); <
112 } else if(g.map[y,x]==' '||g.map[y,x]==' 122 } else if(g.map[y,x]==' '||g.map[y,x]=='
113 q2 ~= new Pos(y,x); 123 q2 ~= new Pos(y,x);
114 v[y][x]=true; 124 v[y][x]=true;
115 } else if(g.map[y,x]=='.'/* && g[y-1,x]! 125 } else if(g.map[y,x]=='.'/* && g[y-1,x]!
116 q2 ~= new Pos(y,x); 126 q2 ~= new Pos(y,x);
117 v[y][x]=true; 127 v[y][x]=true;
118 } 128 }