Overview
| SHA1 Hash: | c4d04122d8de2ec97e30802f7af4733005d00fd9 |
|---|---|
| Date: | 2012-07-14 23:13:31 |
| User: | kinaba |
| Comment: | Dead end avoider. |
| Timelines: | family | ancestors | descendants | both | trunk |
| Diffs: | redesign |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [16f0b5784f]
- sym-trunk inherited from [16f0b5784f]
Changes
Modified src/solver.d from [3df785b1c1414432] to [ee353f733f706a26].
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 }