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