1 /* $NetBSD: auto.c,v 1.5 2002/01/31 17:35:52 christos Exp $ */ 2 3 /*- 4 * Copyright (c) 1999 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Christos Zoulas. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 3. All advertising materials mentioning features or use of this software 19 * must display the following acknowledgement: 20 * This product includes software developed by the NetBSD 21 * Foundation, Inc. and its contributors. 22 * 4. Neither the name of The NetBSD Foundation nor the names of its 23 * contributors may be used to endorse or promote products derived 24 * from this software without specific prior written permission. 25 * 26 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 27 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 28 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 29 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 30 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 31 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 32 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 33 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 34 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 35 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 36 * POSSIBILITY OF SUCH DAMAGE. 37 */ 38 39 /* 40 * Automatic move. 41 * intelligent ? 42 * Algo : 43 * IF scrapheaps don't exist THEN 44 * IF not in danger THEN 45 * stay at current position; 46 * ELSE move away from the closest robot; 47 * FI 48 * ELSE 49 * find closest heap; 50 * find closest robot; 51 * IF scrapheap is adjacenHEN 52 * move behind the scrapheap 53 * ELSE 54 * move away from the closest robot 55 * FI 56 * ELSE 57 * take the move that takes you away from the 58 * robots and closest to the heap 59 * FI 60 * FI 61 */ 62 #include "robots.h" 63 64 #define ABS(a) (((a)>0)?(a):-(a)) 65 #define MIN(a,b) (((a)>(b))?(b):(a)) 66 #define MAX(a,b) (((a)<(b))?(b):(a)) 67 68 #define CONSDEBUG(a) 69 70 static int distance __P((int, int, int, int)); 71 static int xinc __P((int)); 72 static int yinc __P((int)); 73 static const char *find_moves __P((void)); 74 static COORD *closest_robot __P((int *)); 75 static COORD *closest_heap __P((int *)); 76 static char move_towards __P((int, int)); 77 static char move_away __P((COORD *)); 78 static char move_between __P((COORD *, COORD *)); 79 static int between __P((COORD *, COORD *)); 80 81 /* distance(): 82 * return "move" number distance of the two coordinates 83 */ 84 static int 85 distance(x1, y1, x2, y2) 86 int x1, y1, x2, y2; 87 { 88 return MAX(ABS(ABS(x1) - ABS(x2)), ABS(ABS(y1) - ABS(y2))); 89 } /* end distance */ 90 91 /* xinc(): 92 * Return x coordinate moves 93 */ 94 static int 95 xinc(dir) 96 int dir; 97 { 98 switch(dir) { 99 case 'b': 100 case 'h': 101 case 'y': 102 return -1; 103 case 'l': 104 case 'n': 105 case 'u': 106 return 1; 107 case 'j': 108 case 'k': 109 default: 110 return 0; 111 } 112 } 113 114 /* yinc(): 115 * Return y coordinate moves 116 */ 117 static int 118 yinc(dir) 119 int dir; 120 { 121 switch(dir) { 122 case 'k': 123 case 'u': 124 case 'y': 125 return -1; 126 case 'b': 127 case 'j': 128 case 'n': 129 return 1; 130 case 'h': 131 case 'l': 132 default: 133 return 0; 134 } 135 } 136 137 /* find_moves(): 138 * Find possible moves 139 */ 140 static const char * 141 find_moves() 142 { 143 int x, y; 144 COORD test; 145 const char *m; 146 char *a; 147 static const char moves[] = ".hjklyubn"; 148 static char ans[sizeof moves]; 149 a = ans; 150 151 for(m = moves; *m; m++) { 152 test.x = My_pos.x + xinc(*m); 153 test.y = My_pos.y + yinc(*m); 154 move(test.y, test.x); 155 switch(winch(stdscr)) { 156 case ' ': 157 case PLAYER: 158 for(x = test.x - 1; x <= test.x + 1; x++) { 159 for(y = test.y - 1; y <= test.y + 1; y++) { 160 move(y, x); 161 if(winch(stdscr) == ROBOT) 162 goto bad; 163 } 164 } 165 *a++ = *m; 166 } 167 bad:; 168 } 169 *a = 0; 170 if(ans[0]) 171 return ans; 172 else 173 return "t"; 174 } 175 176 /* closest_robot(): 177 * return the robot closest to us 178 * and put in dist its distance 179 */ 180 static COORD * 181 closest_robot(dist) 182 int *dist; 183 { 184 COORD *rob, *end, *minrob = NULL; 185 int tdist, mindist; 186 187 mindist = 1000000; 188 end = &Robots[MAXROBOTS]; 189 for (rob = Robots; rob < end; rob++) { 190 tdist = distance(My_pos.x, My_pos.y, rob->x, rob->y); 191 if (tdist < mindist) { 192 minrob = rob; 193 mindist = tdist; 194 } 195 } 196 *dist = mindist; 197 return minrob; 198 } /* end closest_robot */ 199 200 /* closest_heap(): 201 * return the heap closest to us 202 * and put in dist its distance 203 */ 204 static COORD * 205 closest_heap(dist) 206 int *dist; 207 { 208 COORD *hp, *end, *minhp = NULL; 209 int mindist, tdist; 210 211 mindist = 1000000; 212 end = &Scrap[MAXROBOTS]; 213 for (hp = Scrap; hp < end; hp++) { 214 if (hp->x == 0 && hp->y == 0) 215 break; 216 tdist = distance(My_pos.x, My_pos.y, hp->x, hp->y); 217 if (tdist < mindist) { 218 minhp = hp; 219 mindist = tdist; 220 } 221 } 222 *dist = mindist; 223 return minhp; 224 } /* end closest_heap */ 225 226 /* move_towards(): 227 * move as close to the given direction as possible 228 */ 229 static char 230 move_towards(dx, dy) 231 int dx, dy; 232 { 233 char ok_moves[10], best_move; 234 char *ptr; 235 int move_judge, cur_judge, mvx, mvy; 236 237 (void)strcpy(ok_moves, find_moves()); 238 best_move = ok_moves[0]; 239 if (best_move != 't') { 240 mvx = xinc(best_move); 241 mvy = yinc(best_move); 242 move_judge = ABS(mvx - dx) + ABS(mvy - dy); 243 for (ptr = &ok_moves[1]; *ptr != '\0'; ptr++) { 244 mvx = xinc(*ptr); 245 mvy = yinc(*ptr); 246 cur_judge = ABS(mvx - dx) + ABS(mvy - dy); 247 if (cur_judge < move_judge) { 248 move_judge = cur_judge; 249 best_move = *ptr; 250 } 251 } 252 } 253 return best_move; 254 } /* end move_towards */ 255 256 /* move_away(): 257 * move away form the robot given 258 */ 259 static char 260 move_away(rob) 261 COORD *rob; 262 { 263 int dx, dy; 264 265 dx = sign(My_pos.x - rob->x); 266 dy = sign(My_pos.y - rob->y); 267 return move_towards(dx, dy); 268 } /* end move_away */ 269 270 271 /* move_between(): 272 * move the closest heap between us and the closest robot 273 */ 274 static char 275 move_between(rob, hp) 276 COORD *rob; 277 COORD *hp; 278 { 279 int dx, dy; 280 float slope, cons; 281 282 /* equation of the line between us and the closest robot */ 283 if (My_pos.x == rob->x) { 284 /* 285 * me and the robot are aligned in x 286 * change my x so I get closer to the heap 287 * and my y far from the robot 288 */ 289 dx = - sign(My_pos.x - hp->x); 290 dy = sign(My_pos.y - rob->y); 291 CONSDEBUG(("aligned in x")); 292 } 293 else if (My_pos.y == rob->y) { 294 /* 295 * me and the robot are aligned in y 296 * change my y so I get closer to the heap 297 * and my x far from the robot 298 */ 299 dx = sign(My_pos.x - rob->x); 300 dy = -sign(My_pos.y - hp->y); 301 CONSDEBUG(("aligned in y")); 302 } 303 else { 304 CONSDEBUG(("no aligned")); 305 slope = (My_pos.y - rob->y) / (My_pos.x - rob->x); 306 cons = slope * rob->y; 307 if (ABS(My_pos.x - rob->x) > ABS(My_pos.y - rob->y)) { 308 /* 309 * we are closest to the robot in x 310 * move away from the robot in x and 311 * close to the scrap in y 312 */ 313 dx = sign(My_pos.x - rob->x); 314 dy = sign(((slope * ((float) hp->x)) + cons) - 315 ((float) hp->y)); 316 } 317 else { 318 dx = sign(((slope * ((float) hp->x)) + cons) - 319 ((float) hp->y)); 320 dy = sign(My_pos.y - rob->y); 321 } 322 } 323 CONSDEBUG(("me (%d,%d) robot(%d,%d) heap(%d,%d) delta(%d,%d)", 324 My_pos.x, My_pos.y, rob->x, rob->y, hp->x, hp->y, dx, dy)); 325 return move_towards(dx, dy); 326 } /* end move_between */ 327 328 /* between(): 329 * Return true if the heap is between us and the robot 330 */ 331 int 332 between(rob, hp) 333 COORD *rob; 334 COORD *hp; 335 { 336 /* I = @ */ 337 if (hp->x > rob->x && My_pos.x < rob->x) 338 return 0; 339 /* @ = I */ 340 if (hp->x < rob->x && My_pos.x > rob->x) 341 return 0; 342 /* @ */ 343 /* = */ 344 /* I */ 345 if (hp->y < rob->y && My_pos.y > rob->y) 346 return 0; 347 /* I */ 348 /* = */ 349 /* @ */ 350 if (hp->y > rob->y && My_pos.y < rob->y) 351 return 0; 352 return 1; 353 } /* end between */ 354 355 /* automove(): 356 * find and do the best move if flag 357 * else get the first move; 358 */ 359 char 360 automove() 361 { 362 #if 0 363 return find_moves()[0]; 364 #else 365 COORD *robot_close; 366 COORD *heap_close; 367 int robot_dist, robot_heap, heap_dist; 368 369 robot_close = closest_robot(&robot_dist); 370 if (robot_dist > 1) 371 return('.'); 372 if (!Num_scrap) 373 /* no scrap heaps just run away */ 374 return move_away(robot_close); 375 376 heap_close = closest_heap(&heap_dist); 377 robot_heap = distance(robot_close->x, robot_close->y, 378 heap_close->x, heap_close->y); 379 if (robot_heap <= heap_dist && !between(robot_close, heap_close)) { 380 /* 381 * robot is closest to us from the heap. Run away! 382 */ 383 return move_away(robot_close); 384 } 385 386 return move_between(robot_close, heap_close); 387 #endif 388 } /* end automove */ 389