Differences From Artifact [22c356ff1975e92f]:
- File
src/solver.d
- 2012-07-15 12:01:04 - part of checkin [a03584f1c6] on branch trunk - Refactored. (user: kinaba) [annotate]
To Artifact [393baf841678f948]:
- File
src/solver.d
- 2012-07-15 07:11:41 - part of checkin [e8aa141dbe] on branch trunk - Make manual GUI operation faster for Solver2 by delaying plan making. (user: kinaba) [annotate]
- 2012-07-15 12:14:10 - part of checkin [e02668367d] on branch trunk - Revert redesign in the trunk. (user: kinaba) [annotate]
13 13 int wait_count = 0;
14 14 int choke_count = 0;
15 15
16 16 Game g;
17 17 this(in Game g)
18 18 {
19 19 this.g = g.clone();
20 - forbidden_cell = new bool[][](g.H+2, g.W+2);
20 + forbidden_cell = new bool[][](g.map.H+2, g.map.W+2);
21 21 }
22 22
23 23 char single_step()
24 24 {
25 25 Tuple!(string,int) de = death_move(g);
26 26 char c = act(g, de[0], de[1]);
27 27 force(c);
................................................................................
39 39 string death;
40 40 int choice = 0;
41 41 foreach(char c; "UDLRW") {
42 42 Game gg = g.clone();
43 43 gg.command(c);
44 44 if( !gg.cleared && gg.dead )
45 45 death ~= c;
46 - else if( gg.robot != g.robot )
46 + else if( gg.map.robot != g.map.robot )
47 47 choice++;
48 48 else if( c != 'W' ) // meaningless move
49 49 death ~= c;
50 50 }
51 51 return tuple(death, choice);
52 52 }
53 53
54 54 Tuple!(Pos, int)[] log;
55 55 bool[][] forbidden_cell;
56 56
57 57 char act(const(Game) g, string death, int breath)
58 58 {
59 - const Pos ro = g.robot;
60 - const Pos li = g.lift;
61 - Pos[] la = g.lambdas();
59 + const Pos ro = g.map.robot;
60 + const Pos li = g.map.lift;
61 + Pos[] la = g.map.lambdas();
62 62 sort!((Pos a,Pos b){
63 63 int ad=abs(a.y-li.y)+abs(a.x-li.x);
64 64 int bd=abs(b.y-li.y)+abs(b.x-li.x);
65 65 return ad>bd;;
66 66 })(la);
67 - Pos[] ra = g.razors();
68 - const(Pos)[] hi = g.higes();
67 + Pos[] ra = g.map.razors();
68 + const(Pos)[] hi = g.map.objects('W');
69 69
70 70 Tuple!(char,int)[] cand;
71 71 char c = 'W';
72 72 if( la.empty ) {
73 73 cand = search(g, ro, [li], death);
74 74 } else {
75 75 cand ~= search(g, ro, la~ra, death);
76 76 }
77 77
78 78 // 'higesori' mode
79 - if( !hi.empty && g.num_razor>0 ) {
79 + if( !hi.empty && g.map.razor>0 ) {
80 80 int his = 0;
81 81 for(int dy=-1; dy<=+1; ++dy)
82 82 for(int dx=-1; dx<=+1; ++dx)
83 - if(g[ro.y+dy,ro.x+dx] == 'W')
83 + if(g.map[ro.y+dy,ro.x+dx] == 'W')
84 84 his++;
85 85
86 86 if(his>=2 || his==hi.length)
87 87 cand = [tuple('S',int.max)];
88 88 if(cand.empty) {
89 89 const(Pos)[] tgt;
90 - for(int y=1; y<=g.H; ++y)
91 - for(int x=1; x<=g.W; ++x)
92 - if(g[y,x]=='.'||g[y,x]==' ') {
90 + for(int y=1; y<=g.map.H; ++y)
91 + for(int x=1; x<=g.map.W; ++x)
92 + if(g.map[y,x]=='.'||g.map[y,x]==' ') {
93 93 his = 0;
94 94 for(int dy=-1; dy<=+1; ++dy)
95 95 for(int dx=-1; dx<=+1; ++dx)
96 - if(g[y+dy,x+dx] == 'W')
96 + if(g.map[y+dy,x+dx] == 'W')
97 97 his++;
98 98 if(his>=2)
99 99 tgt ~= new Pos(y,x);
100 100 }
101 101 cand ~= search(g, ro, tgt, death, true);
102 102 }
103 103 }
104 104
105 105 // 'dig' mode
106 106 if(cand.empty) {
107 107 const(Pos)[] tgt;
108 - for(int y=1; y<=g.H; ++y)
109 - for(int x=1; x<=g.W; ++x)
110 - if(g[y,x]=='.')
111 - if(g[y+1,x]=='*'||g[y+1,x-1]=='*'||g[y+1,x+1]=='*'
112 - ||g[y,x+1]=='*'||g[y,x-1]=='*')
108 + for(int y=1; y<=g.map.H; ++y)
109 + for(int x=1; x<=g.map.W; ++x)
110 + if(g.map[y,x]=='.')
111 + if(g.map[y+1,x]=='*'||g.map[y+1,x-1]=='*'||g.map[y+1,x+1]=='*'
112 + ||g.map[y,x+1]=='*'||g.map[y,x-1]=='*')
113 113 tgt ~= new Pos(y,x);
114 114 cand ~= search(g, ro, tgt, death, true);
115 115 }
116 116
117 117 if(cand.empty) {
118 118 choke_count++;
119 119 cand ~= tuple('W',int.max);
................................................................................
133 133 }
134 134 }
135 135
136 136 if(c == 'W')
137 137 wait_count++;
138 138 else
139 139 wait_count = 0;
140 - if(choke_count >= g.H)
140 + if(choke_count >= g.map.H)
141 141 c = 'A';
142 142
143 143 bool[char] choice;
144 144 foreach(t; cand)
145 145 choice[t[0]] = true;
146 146 log ~= tuple(ro.clone(), cast(int)choice.length);
147 147 if(log.length > 5)
................................................................................
157 157 return c;
158 158 }
159 159
160 160 Tuple!(char,int)[] search(in Game g, in Pos s, in Pos[] gs, string death, bool danger_ok=false)
161 161 {
162 162 bool danger(int y, int x)
163 163 {
164 - if(g[y,x] == ' ' || g[y,x] == 'R')
164 + if(g.map[y,x] == ' ' || g.map[y,x] == 'R')
165 165 return false;
166 - if(g[y+1,x] == '*')
166 + if(g.map[y+1,x] == '*')
167 + return true;
168 + if(g.map[y+1,x-1]=='*' && (g.map[y,x-1]=='\\'||g.map[y,x-1]=='*') && (g.map[y+1,x]==' '||g.map[y+1,x]=='R'))
167 169 return true;
168 - if(g[y+1,x-1]=='*' && (g[y,x-1]=='\\'||g[y,x-1]=='*') && (g[y+1,x]==' '||g[y+1,x]=='R'))
170 + if(g.map[y+1,x+1]=='*' && (g.map[y,x+1]=='*') && (g.map[y+1,x]==' '||g.map[y+1,x]=='R'))
169 171 return true;
170 - if(g[y+1,x+1]=='*' && (g[y,x+1]=='*') && (g[y+1,x]==' '||g[y+1,x]=='R'))
172 + if(g.map[y,x-1]=='*' && (g.map[y-1,x-1]=='\\'||g.map[y-1,x-1]=='*') && (g.map[y-1,x]==' '||g.map[y-1,x]=='R'))
171 173 return true;
172 - if(g[y,x-1]=='*' && (g[y-1,x-1]=='\\'||g[y-1,x-1]=='*') && (g[y-1,x]==' '||g[y-1,x]=='R'))
173 - return true;
174 - if(g[y,x+1]=='*' && (g[y-1,x+1]=='*') && (g[y-1,x]==' '||g[y-1,x]=='R'))
174 + if(g.map[y,x+1]=='*' && (g.map[y-1,x+1]=='*') && (g.map[y-1,x]==' '||g.map[y-1,x]=='R'))
175 175 return true;
176 176 return false;
177 177 }
178 178
179 179 // avoid directly below '*'
180 180 Tuple!(char,int)[] tryA() {
181 181 const(Pos)[] q;
182 182 foreach(p; gs)
183 183 if(!danger(p.y,p.x))
184 184 q ~= p;
185 - bool[][] v = new bool[][](g.H+2, g.W+2);
185 + bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
186 186 foreach(p; q) v[p.y][p.x]=true;
187 187 for(int step=1; q.length; ++step) {
188 188 Pos[] q2;
189 189 foreach(p; q) {
190 190 int[] yyy=[p.y-1,p.y+1,p.y,p.y];
191 191 int[] xxx=[p.x,p.x,p.x-1,p.x+1];
192 192 for(int i=0; i<yyy.length; ++i) {
193 193 int y = yyy[i];
194 194 int x = xxx[i];
195 - if('1'<=g[y,x]&&g[y,x]<='9') {
196 - foreach(ppp; g.trampoline_rev(g[y,x])) {
195 + if('1'<=g.map[y,x]&&g.map[y,x]<='9') {
196 + foreach(ppp; g.map.tr_source[g.map[y,x]]) {
197 197 yyy ~= ppp.y;
198 198 xxx ~= ppp.x;
199 199 }
200 200 continue;
201 201 }
202 202 if(v[y][x]) continue;
203 203 if(y==s.y && x==s.x && i<4) {
204 204 char c = "UDRL"[i];
205 205 if( death.count(c) == 0 )
206 206 return [tuple(c,step)];
207 207 } else if(forbidden_cell[y][x]){
208 - } else if(g[y,x]==' '||g[y,x]=='\\'||g[y,x]=='.'||g[y,x]=='!'||i>=4) {
208 + } else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||g.map[y,x]=='!'||i>=4) {
209 209 if(danger(y,x))
210 210 continue;
211 211 q2 ~= new Pos(y,x);
212 212 v[y][x]=true;
213 213 }
214 214 }
215 215 }
................................................................................
218 218 return [];
219 219 }
220 220
221 221 // any empty space is my ground
222 222 Tuple!(char,int)[] tryB() {
223 223 const(Pos)[] q;
224 224 foreach(p; gs) q ~= p;
225 - bool[][] v = new bool[][](g.H+2, g.W+2);
225 + bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
226 226 foreach(p; q) v[p.y][p.x]=true;
227 227 for(int step=10; q.length; ++step) {
228 228 Pos[] q2;
229 229 foreach(p; q) {
230 230 int[] yyy=[p.y-1,p.y+1,p.y,p.y];
231 231 int[] xxx=[p.x,p.x,p.x-1,p.x+1];
232 232 for(int i=0; i<yyy.length; ++i) {
233 233 int y = yyy[i];
234 234 int x = xxx[i];
235 - if('1'<=g[y,x]&&g[y,x]<='9') {
236 - foreach(ppp; g.trampoline_rev(g[y,x])) {
235 + if('1'<=g.map[y,x]&&g.map[y,x]<='9') {
236 + foreach(ppp; g.map.tr_source[g.map[y,x]]) {
237 237 yyy ~= ppp.y;
238 238 xxx ~= ppp.x;
239 239 }
240 240 continue;
241 241 }
242 242 if(v[y][x]) continue;
243 243 if(y==s.y && x==s.x && i<4) {
244 244 char c = "UDRL"[i];
245 245 if( death.count(c) == 0 )
246 246 return [tuple(c,step)];
247 247 } else if(forbidden_cell[y][x]){
248 - } else if(g[y,x]==' '||g[y,x]=='\\'||g[y,x]=='.'||g[y,x]=='!'||i>=4) {
248 + } else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||g.map[y,x]=='!'||i>=4) {
249 249 q2 ~= new Pos(y,x);
250 250 v[y][x]=true;
251 251 }
252 252 }
253 253 }
254 254 q = q2;
255 255 }
................................................................................
256 256 return [];
257 257 }
258 258
259 259 // push rocks!
260 260 Tuple!(char,int)[] tryC() {
261 261 const(Pos)[] q;
262 262 foreach(p; gs) q ~= p;
263 - bool[][] v = new bool[][](g.H+2, g.W+2);
263 + bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
264 264 foreach(p; q) v[p.y][p.x]=true;
265 265 for(int step=20; q.length; ++step) {
266 266 Pos[] q2;
267 267 foreach(p; q) {
268 268 int[] yyy=[p.y-1,p.y+1,p.y,p.y];
269 269 int[] xxx=[p.x,p.x,p.x-1,p.x+1];
270 270 for(int i=0; i<yyy.length; ++i) {
271 271 int y = yyy[i];
272 272 int x = xxx[i];
273 - if(g[p] == '*') {
273 + if(g.map[p] == '*') {
274 274 if(i>=4)continue;
275 275 if(y!=p.y)continue;
276 - if(g[y,p.x+(p.x-x)]!=' '&&g[y,p.x+(p.x-x)]!='R')continue;
276 + if(g.map[y,p.x+(p.x-x)]!=' '&&g.map[y,p.x+(p.x-x)]!='R')continue;
277 277 }
278 - if('1'<=g[y,x]&&g[y,x]<='9') {
279 - foreach(ppp; g.trampoline_rev(g[y,x])) {
278 + if('1'<=g.map[y,x]&&g.map[y,x]<='9') {
279 + foreach(ppp; g.map.tr_source[g.map[y,x]]) {
280 280 yyy ~= ppp.y;
281 281 xxx ~= ppp.x;
282 282 }
283 283 continue;
284 284 }
285 285 if(v[y][x]) continue;
286 286 if(y==s.y && x==s.x && i<4) {
287 287 char c = "UDRL"[i];
288 288 if( death.count(c) == 0 )
289 289 return [tuple(c,step)];
290 290 } else if(forbidden_cell[y][x]){
291 - } else if(g[y,x]==' '||g[y,x]=='\\'||g[y,x]=='.'||g[y,x]=='*'||g[y,x]=='!'||i>=4) {
291 + } else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||g.map[y,x]=='*'||g.map[y,x]=='!'||i>=4) {
292 292 q2 ~= new Pos(y,x);
293 293 v[y][x]=true;
294 294 }
295 295 }
296 296 }
297 297 q = q2;
298 298 }
................................................................................
314 314 make_plan(g);
315 315 }
316 316
317 317 Tuple!(Solver,string) run_sub_solver(in Game g)
318 318 {
319 319 string log;
320 320 auto s = new Solver(g);
321 - while(!g.cleared && !g.dead && plan.length<=g.H*g.W) {
321 + while(!g.cleared && !g.dead && plan.length<=g.map.H*g.map.W) {
322 322 char c = s.single_step();
323 323 if( c == 'A' )
324 324 break;
325 325 log ~= c;
326 326 }
327 327 while(log.length>0 && log[$-1]=='W')
328 328 log.length--;