Differences From Artifact [6098061a6d0ff01b]:
- File
src/solver.d
- 2012-07-14 13:21:56 - part of checkin [5fc8a9c49b] on branch trunk - rock pusher. (user: kinaba) [annotate]
To Artifact [3df785b1c1414432]:
- File
src/solver.d
- 2012-07-14 13:45:03 - part of checkin [62a5c6c47f] on branch trunk - Correctly implemented below-rock avoider. (user: kinaba) [annotate]
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 }