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