robots/auto.c

   1 /*      $NetBSD: auto.c,v 1.6 2004/01/27 20:30:30 jsm 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(int, int, int, int);
  71 static int xinc(int);
  72 static int yinc(int);
  73 static const char *find_moves(void);
  74 static COORD *closest_robot(int *);
  75 static COORD *closest_heap(int *);
  76 static char move_towards(int, int);
  77 static char move_away(COORD *);
  78 static char move_between(COORD *, COORD *);
  79 static int between(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 */