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