Differences From Artifact [3df785b1c1414432]:
- File
src/solver.d
- 2012-07-14 13:45:03 - part of checkin [62a5c6c47f] on branch trunk - Correctly implemented below-rock avoider. (user: kinaba) [annotate]
To Artifact [ee353f733f706a26]:
- File
src/solver.d
- 2012-07-14 14:13:31 - part of checkin [c4d04122d8] on branch trunk - Dead end avoider. (user: kinaba) [annotate]
20 20 {
21 21 int g_wc = 0;
22 22
23 23 Game g;
24 24 this(const(Game) g)
25 25 {
26 26 this.g = g.clone();
27 + forbidden_cell = new bool[][](g.map.H+2, g.map.W+2);
27 28 }
28 29
29 30 char single_step()
30 31 {
31 - char c = act(g, death_move(g));
32 + Tuple!(string,int) de = death_move(g);
33 + char c = act(g, de[0], de[1]);
32 34 g.command(c);
33 35 return c;
34 36 }
35 37
36 - string death_move(const(Game) g)
38 + Tuple!(string,int) death_move(const(Game) g)
37 39 {
38 40 string death;
41 + int choice = 0;
39 42 foreach(char c; "UDLRW") {
40 43 Game gg = g.clone();
41 44 gg.command(c);
42 45 if( !gg.cleared && gg.dead )
43 46 death ~= c;
47 + else if( gg.map.robot != g.map.robot )
48 + choice++;
44 49 }
45 - return death;
50 + return tuple(death, choice);
46 51 }
47 52
48 - char act(const(Game) g, string death)
53 + Tuple!(Pos, int)[] log;
54 + bool[][] forbidden_cell;
55 +
56 + char act(const(Game) g, string death, int breath)
49 57 {
50 58 const Pos ro = g.map.robot;
51 59 const Pos[] la = g.map.lambdas();
52 60 const Pos li = g.map.lift;
53 61
54 62 Tuple!(char,int)[] cand;
55 63 char c = 'W';
56 64 if( la.empty ) {
57 65 cand = search(g, ro, li, death);
58 66 } else {
59 67 foreach(lam; la)
60 68 cand ~= search(g, ro, lam, death);
61 69 }
70 + cand ~= tuple('W',int.max);
62 71 sort!((Tuple!(char,int) c1, Tuple!(char,int) c2){
63 72 if(c1[1] != c2[1])
64 73 return c1[1] < c2[1];
65 74 return c1[0] < c2[0];
66 75 })(cand);
67 76 c = cand[0][0];
68 77
................................................................................
69 78 if(c=='W') {
70 79 g_wc++;
71 80 if(g_wc > 10)
72 81 c = 'A';
73 82 }
74 83 else
75 84 g_wc = 0;
85 + bool[char] choice;
86 + foreach(t; cand)
87 + choice[t[0]] = true;
88 + log ~= tuple(ro.clone(), cast(int)choice.length);
89 + if(log.length > 5)
90 + log = log[$-5..$];
91 + int cnt = 0;
92 + foreach(l; log)
93 + if(l[0] == log[$-1][0])
94 + ++cnt;
95 + if( cnt >= 3 && breath==1 ) {
96 + forbidden_cell[ro.y][ro.x] = true;
97 + }
98 +
76 99 return c;
77 100 }
78 101
79 102 Tuple!(char,int)[] search(in Game g, in Pos s, in Pos o, string death)
80 103 {
81 104 bool danger(int y, int x)
82 105 {
................................................................................
108 131 int y = p.y+dy[i];
109 132 int x = p.x+dx[i];
110 133 if(v[y][x]) continue;
111 134 if(y==s.y && x==s.x) {
112 135 char c = "UDRL"[i];
113 136 if( death.count(c) == 0 )
114 137 return [tuple(c,step)];
138 + } else if(forbidden_cell[y][x]){
115 139 } else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.') {
116 140 if(danger(y,x))
117 141 continue;
118 142 q2 ~= new Pos(y,x);
119 143 v[y][x]=true;
120 144 }
121 145 }
................................................................................
127 151 }
128 152
129 153 // any empty space is my ground
130 154 Tuple!(char,int)[] tryB() {
131 155 const(Pos)[] q = [o];
132 156 bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
133 157 v[o.y][o.x]=true;
134 - for(int step=15; q.length; ++step) {
158 + for(int step=10; q.length; ++step) {
135 159 Pos[] q2;
136 160 foreach(p; q) {
137 161 int[] dy=[-1,+1,0,0];
138 162 int[] dx=[0,0,-1,+1];
139 163 for(int i=0; i<4; ++i) {
140 164 int y = p.y+dy[i];
141 165 int x = p.x+dx[i];
142 166 if(v[y][x]) continue;
143 167 if(y==s.y && x==s.x) {
144 168 char c = "UDRL"[i];
145 169 if( death.count(c) == 0 )
146 170 return [tuple(c,step)];
171 + } else if(forbidden_cell[y][x]){
147 172 } else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.') {
148 173 q2 ~= new Pos(y,x);
149 174 v[y][x]=true;
150 175 }
151 176 }
152 177 }
153 178 q = q2;
................................................................................
156 181 }
157 182
158 183 // push rocks!
159 184 Tuple!(char,int)[] tryC() {
160 185 const(Pos)[] q = [o];
161 186 bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
162 187 v[o.y][o.x]=true;
163 - for(int step=30; q.length; ++step) {
188 + for(int step=20; q.length; ++step) {
164 189 Pos[] q2;
165 190 foreach(p; q) {
166 191 int[] dy=[-1,+1,0,0];
167 192 int[] dx=[0,0,-1,+1];
168 193 for(int i=0; i<4; ++i) {
169 194 int y = p.y+dy[i];
170 195 int x = p.x+dx[i];
171 196 if(v[y][x]) continue;
172 197 if(y==s.y && x==s.x) {
173 198 char c = "UDRL"[i];
174 199 if( death.count(c) == 0 )
175 200 return [tuple(c,step)];
201 + } else if(forbidden_cell[y][x]){
176 202 } else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.') {
177 203 q2 ~= new Pos(y,x);
178 204 v[y][x]=true;
179 205 } else if(dy[i]==0 && g.map[p]==' ' && g.map[y,x]=='*' && (g.map[y+dy[i],x+dx[i]]==' '||g.map[y+dy[i],x+dx[i]]=='R')) {
180 206 q2 ~= new Pos(y,x);
181 207 v[y][x]=true;
182 208 }
183 209 }
184 210 }
185 211 q = q2;
186 212 }
187 213 return [];
188 214 }
189 - return tryA() ~ tryB() ~ tryC() ~ tuple('W', int.max);
215 + return tryA() ~ tryB() ~ tryC();
190 216 }
191 217 }