Overview
| SHA1 Hash: | 62a5c6c47f21abf244627cea87075169c4f9373c |
|---|---|
| Date: | 2012-07-14 22:45:03 |
| User: | kinaba |
| Comment: | Correctly implemented below-rock 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/game.d from [545a22e98c8c86c7] to [17dbdc662950a670].
145 // Adjust coordinate to the spec. bottom-left is (1,1). 145 // Adjust coordinate to the spec. bottom-left is (1,1). 146 --y, --x; 146 --y, --x; 147 if(y<0||H<=y||x<0||W<=x) 147 if(y<0||H<=y||x<0||W<=x) 148 return '#'; 148 return '#'; 149 return data[H-1-y][x]; 149 return data[H-1-y][x]; 150 } 150 } 151 151 152 char opIndex(Pos p) | 152 char opIndex(in Pos p) 153 { 153 { 154 return this[p.y, p.x]; 154 return this[p.y, p.x]; 155 } 155 } 156 } 156 } 157 157 158 void opIndexAssign(char c, int y, int x) 158 void opIndexAssign(char c, int y, int x) 159 { 159 { ................................................................................................................................................................................ 160 // Adjust coordinate to the spec. bottom-left is (1,1). 160 // Adjust coordinate to the spec. bottom-left is (1,1). 161 --y, --x; 161 --y, --x; 162 if(y<0||H<=y||x<0||W<=x) 162 if(y<0||H<=y||x<0||W<=x) 163 return; 163 return; 164 data[H-1-y][x] = c; 164 data[H-1-y][x] = c; 165 } 165 } 166 166 167 void opIndexAssign(char c, Pos p) | 167 void opIndexAssign(char c, in Pos p) 168 { 168 { 169 this[p.y, p.x] = c; 169 this[p.y, p.x] = c; 170 } 170 } 171 171 172 Pos[] lambdas() const { 172 Pos[] lambdas() const { 173 Pos[] ans; 173 Pos[] ans; 174 for(int y=1; y<=H; ++y) 174 for(int y=1; y<=H; ++y)
Modified src/solver.d from [6098061a6d0ff01b] to [3df785b1c1414432].
47 47 48 char act(const(Game) g, string death) 48 char act(const(Game) g, string death) 49 { 49 { 50 const Pos ro = g.map.robot; 50 const Pos ro = g.map.robot; 51 const Pos[] la = g.map.lambdas(); 51 const Pos[] la = g.map.lambdas(); 52 const Pos li = g.map.lift; 52 const Pos li = g.map.lift; 53 53 > 54 Tuple!(char,int)[] cand; 54 char c = 'W'; 55 char c = 'W'; 55 if( la.empty ) { 56 if( la.empty ) { 56 auto r = search(g, ro, li, death); | 57 cand = search(g, ro, li, death); 57 c = r[0]; < 58 } else { 58 } else { 59 Tuple!(char,int)[] cand; < 60 foreach(lam; la) 59 foreach(lam; la) 61 cand ~= search(g, ro, lam, death); 60 cand ~= search(g, ro, lam, death); 62 sort!((Tuple!(char,int) c1, Tuple!(char,int) c2){ < 63 if(c1[1] != c2[1]) < 64 return c1[1] < c2[1]; < 65 return c1[0] < c2[0]; < 66 })(cand); < 67 c = cand[0][0]; < 68 } 61 } > 62 sort!((Tuple!(char,int) c1, Tuple!(char,int) c2){ > 63 if(c1[1] != c2[1]) > 64 return c1[1] < c2[1]; > 65 return c1[0] < c2[0]; > 66 })(cand); > 67 c = cand[0][0]; > 68 69 if(c=='W') { 69 if(c=='W') { 70 g_wc++; 70 g_wc++; 71 if(g_wc > 10) 71 if(g_wc > 10) 72 c = 'A'; 72 c = 'A'; 73 } 73 } 74 else 74 else 75 g_wc = 0; 75 g_wc = 0; 76 return c; 76 return c; 77 } 77 } 78 78 79 Tuple!(char,int) search(in Game g, in Pos s, in Pos o, string death) | 79 Tuple!(char,int)[] search(in Game g, in Pos s, in Pos o, string death) 80 { 80 { > 81 bool danger(int y, int x) > 82 { > 83 if(g.map[y+1,x] == '*') > 84 return true; > 85 if(g.map[y+1,x-1]=='*' && (g.map[y,x-1]=='\\'||g.map[y,x > 86 return true; > 87 if(g.map[y+1,x+1]=='*' && (g.map[y,x+1]=='*') && (g.map[ > 88 return true; > 89 if(g.map[y,x-1]=='*' && (g.map[y-1,x-1]=='\\'||g.map[y-1 > 90 return true; > 91 if(g.map[y,x+1]=='*' && (g.map[y-1,x+1]=='*') && (g.map[ > 92 return true; > 93 return false; > 94 } > 95 81 // avoid directly below '*' 96 // avoid directly below '*' > 97 Tuple!(char,int)[] tryA() { 82 const(Pos)[] q = [o]; | 98 const(Pos)[] q = [o]; 83 bool[][] v = new bool[][](g.map.H+2, g.map.W+2); | 99 bool[][] v = new bool[][](g.map.H+2, g.map.W+2); > 100 if( !danger(o.y,o.x) ) { 84 v[o.y][o.x]=true; | 101 v[o.y][o.x]=true; 85 for(int step=1; q.length; ++step) { | 102 for(int step=1; q.length; ++step) { 86 Pos[] q2; | 103 Pos[] q2; 87 foreach(p; q) { | 104 foreach(p; q) { 88 int[] dy=[-1,+1,0,0]; | 105 int[] dy=[-1,+1,0,0]; 89 int[] dx=[0,0,-1,+1]; | 106 int[] dx=[0,0,-1,+1]; 90 for(int i=0; i<4; ++i) { | 107 for(int i=0; i<4; ++i) { 91 int y = p.y+dy[i]; | 108 int y = p.y+dy[i]; 92 int x = p.x+dx[i]; | 109 int x = p.x+dx[i]; 93 if(v[y][x]) continue; | 110 if(v[y][x]) continue; 94 if(y==s.y && x==s.x) { | 111 if(y==s.y && x==s.x) { 95 char c = "UDRL"[i]; | 112 char c = "UDRL"[ 96 if( death.count(c) == 0 ) | 113 if( death.count( 97 return tuple(c,step); | 114 return [ 98 } else if(g.map[y,x]==' '||g.map[y,x]==' | 115 } else if(g.map[y,x]==' 99 q2 ~= new Pos(y,x); < 100 v[y][x]=true; < 101 } else if(g.map[y,x]=='.' && g.map[y-1,x | 116 if(danger(y,x)) > 117 continue 102 q2 ~= new Pos(y,x); | 118 q2 ~= new Pos(y, 103 v[y][x]=true; | 119 v[y][x]=true; > 120 } > 121 } 104 } 122 } > 123 q = q2; 105 } 124 } 106 } 125 } 107 q = q2; | 126 return []; 108 } 127 } 109 128 110 // any empty space is my ground 129 // any empty space is my ground > 130 Tuple!(char,int)[] tryB() { 111 q = [o]; | 131 const(Pos)[] q = [o]; 112 v = new bool[][](g.map.H+2, g.map.W+2); | 132 bool[][] v = new bool[][](g.map.H+2, g.map.W+2); 113 v[o.y][o.x]=true; | 133 v[o.y][o.x]=true; 114 for(int step=1000; q.length; ++step) { | 134 for(int step=15; q.length; ++step) { 115 Pos[] q2; | 135 Pos[] q2; 116 foreach(p; q) { | 136 foreach(p; q) { 117 int[] dy=[-1,+1,0,0]; | 137 int[] dy=[-1,+1,0,0]; 118 int[] dx=[0,0,-1,+1]; | 138 int[] dx=[0,0,-1,+1]; 119 for(int i=0; i<4; ++i) { | 139 for(int i=0; i<4; ++i) { 120 int y = p.y+dy[i]; | 140 int y = p.y+dy[i]; 121 int x = p.x+dx[i]; | 141 int x = p.x+dx[i]; 122 if(v[y][x]) continue; | 142 if(v[y][x]) continue; 123 if(y==s.y && x==s.x) { | 143 if(y==s.y && x==s.x) { 124 char c = "UDRL"[i]; | 144 char c = "UDRL"[i]; 125 if( death.count(c) == 0 ) | 145 if( death.count(c) == 0 126 return tuple(c,step); | 146 return [tuple(c, 127 } else if(g.map[y,x]==' '||g.map[y,x]==' | 147 } else if(g.map[y,x]==' '||g.map 128 q2 ~= new Pos(y,x); | 148 q2 ~= new Pos(y,x); 129 v[y][x]=true; | 149 v[y][x]=true; 130 } else if(g.map[y,x]=='.'/* && g[y-1,x]! < 131 q2 ~= new Pos(y,x); < 132 v[y][x]=true; < > 150 } 133 } 151 } 134 } 152 } > 153 q = q2; 135 } 154 } 136 q = q2; | 155 return []; 137 } 156 } 138 157 139 // push rocks! 158 // push rocks! > 159 Tuple!(char,int)[] tryC() { 140 q = [o]; | 160 const(Pos)[] q = [o]; 141 v = new bool[][](g.map.H+2, g.map.W+2); | 161 bool[][] v = new bool[][](g.map.H+2, g.map.W+2); 142 v[o.y][o.x]=true; | 162 v[o.y][o.x]=true; 143 for(int step=2000; q.length; ++step) { | 163 for(int step=30; q.length; ++step) { 144 Pos[] q2; | 164 Pos[] q2; 145 foreach(p; q) { | 165 foreach(p; q) { 146 int[] dy=[-1,+1,0,0]; | 166 int[] dy=[-1,+1,0,0]; 147 int[] dx=[0,0,-1,+1]; | 167 int[] dx=[0,0,-1,+1]; 148 for(int i=0; i<4; ++i) { | 168 for(int i=0; i<4; ++i) { 149 int y = p.y+dy[i]; | 169 int y = p.y+dy[i]; 150 int x = p.x+dx[i]; | 170 int x = p.x+dx[i]; 151 if(v[y][x]) continue; | 171 if(v[y][x]) continue; 152 if(y==s.y && x==s.x) { | 172 if(y==s.y && x==s.x) { 153 char c = "UDRL"[i]; | 173 char c = "UDRL"[i]; 154 if( death.count(c) == 0 ) | 174 if( death.count(c) == 0 155 return tuple(c,step); | 175 return [tuple(c, 156 } else if(g.map[y,x]==' '||g.map[y,x]==' | 176 } else if(g.map[y,x]==' '||g.map 157 q2 ~= new Pos(y,x); | 177 q2 ~= new Pos(y,x); 158 v[y][x]=true; | 178 v[y][x]=true; 159 } else if(g.map[y,x]=='.'/* && g[y-1,x]! < 160 q2 ~= new Pos(y,x); < 161 v[y][x]=true; < 162 } else if(dy[i]==0 && g.map[y,x]=='*' && | 179 } else if(dy[i]==0 && g.map[p]== 163 q2 ~= new Pos(y,x); | 180 q2 ~= new Pos(y,x); 164 v[y][x]=true; | 181 v[y][x]=true; > 182 } 165 } 183 } 166 } 184 } > 185 q = q2; 167 } 186 } 168 q = q2; | 187 return []; 169 } 188 } 170 return tuple('W', int.max); | 189 return tryA() ~ tryB() ~ tryC() ~ tuple('W', int.max); 171 } 190 } 172 } 191 }