robots/auto.c

   1 /*      $NetBSD: auto.c,v 1.7 2004/08/27 09:06:25 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
  47  *                              move away from the closest robot
  48  *                      FI
  49  *              ELSE
  50  *                      find closest heap
  51  *                      find closest robot
  52  *                      IF scrapheap is adjacent THEN
  53  *                              move behind the scrapheap
  54  *                      ELSE
  55  *                              take the move that takes you away from the
  56  *                              robots and closest to the heap
  57  *                      FI
  58  *              FI
  59  */
  60 #include "robots.h"
  61
  62 #define ABS(a) (((a)>0)?(a):-(a))
  63 #define MIN(a,b) (((a)>(b))?(b):(a))
  64 #define MAX(a,b) (((a)<(b))?(b):(a))
  65
  66 #define CONSDEBUG(a)
  67
  68 static int distance(int, int, int, int);
  69 static int xinc(int);
  70 static int yinc(int);
  71 static const char *find_moves(void);
  72 static COORD *closest_robot(int *);
  73 static COORD *closest_heap(int *);
  74 static char move_towards(int, int);
  75 static char move_away(COORD *);
  76 static char move_between(COORD *, COORD *);
  77 static int between(COORD *, COORD *);
  78
  79 /* distance():
  80  *      return "move" number distance of the two coordinates
  81  */
  82 static int
  83 distance(x1, y1, x2, y2)
  84         int x1, y1, x2, y2;
  85 {
  86         return MAX(ABS(ABS(x1) - ABS(x2)), ABS(ABS(y1) - ABS(y2)));
  87 } /* end distance */
  88
  89 /* xinc():
  90  *      Return x coordinate moves
  91  */
  92 static int
  93 xinc(dir)
  94         int dir;
  95 {
  96         switch(dir) {
  97         case 'b':
  98         case 'h':
  99         case 'y':
 100                 return -1;
 101         case 'l':
 102         case 'n':
 103         case 'u':
 104                 return 1;
 105         case 'j':
 106         case 'k':
 107         default:
 108                 return 0;
 109         }
 110 }
 111
 112 /* yinc():
 113  *      Return y coordinate moves
 114  */
 115 static int
 116 yinc(dir)
 117         int dir;
 118 {
 119         switch(dir) {
 120         case 'k':
 121         case 'u':
 122         case 'y':
 123                 return -1;
 124         case 'b':
 125         case 'j':
 126         case 'n':
 127                 return 1;
 128         case 'h':
 129         case 'l':
 130         default:
 131                 return 0;
 132         }
 133 }
 134
 135 /* find_moves():
 136  *      Find possible moves
 137  */
 138 static const char *
 139 find_moves()
 140 {
 141         int x, y;
 142         COORD test;
 143         const char *m;
 144         char *a;
 145         static const char moves[] = ".hjklyubn";
 146         static char ans[sizeof moves];
 147         a = ans;
 148
 149         for(m = moves; *m; m++) {
 150                 test.x = My_pos.x + xinc(*m);
 151                 test.y = My_pos.y + yinc(*m);
 152                 move(test.y, test.x);
 153                 switch(winch(stdscr)) {
 154                 case ' ':
 155                 case PLAYER:
 156                         for(x = test.x - 1; x <= test.x + 1; x++) {
 157                                 for(y = test.y - 1; y <= test.y + 1; y++) {
 158                                         move(y, x);
 159                                         if(winch(stdscr) == ROBOT)
 160                                                 goto bad;
 161                                 }
 162                         }
 163                         *a++ = *m;
 164                 }
 165         bad:;
 166         }
 167         *a = 0;
 168         if(ans[0])
 169                 return ans;
 170         else
 171                 return "t";
 172 }
 173
 174 /* closest_robot():
 175  *      return the robot closest to us
 176  *      and put in dist its distance
 177  */
 178 static COORD *
 179 closest_robot(dist)
 180         int *dist;
 181 {
 182         COORD *rob, *end, *minrob = NULL;
 183         int tdist, mindist;
 184
 185         mindist = 1000000;
 186         end = &Robots[MAXROBOTS];
 187         for (rob = Robots; rob < end; rob++) {
 188                 tdist = distance(My_pos.x, My_pos.y, rob->x, rob->y);
 189                 if (tdist < mindist) {
 190                         minrob = rob;
 191                         mindist = tdist;
 192                 }
 193         }
 194         *dist = mindist;
 195         return minrob;
 196 } /* end closest_robot */
 197
 198 /* closest_heap():
 199  *      return the heap closest to us
 200  *      and put in dist its distance
 201  */
 202 static COORD *
 203 closest_heap(dist)
 204         int *dist;
 205 {
 206         COORD *hp, *end, *minhp = NULL;
 207         int mindist, tdist;
 208
 209         mindist = 1000000;
 210         end = &Scrap[MAXROBOTS];
 211         for (hp = Scrap; hp < end; hp++) {
 212                 if (hp->x == 0 && hp->y == 0)
 213                         break;
 214                 tdist = distance(My_pos.x, My_pos.y, hp->x, hp->y);
 215                 if (tdist < mindist) {
 216                         minhp = hp;
 217                         mindist = tdist;
 218                 }
 219         }
 220         *dist = mindist;
 221         return minhp;
 222 } /* end closest_heap */
 223
 224 /* move_towards():
 225  *      move as close to the given direction as possible
 226  */
 227 static char
 228 move_towards(dx, dy)
 229         int dx, dy;
 230 {
 231         char ok_moves[10], best_move;
 232         char *ptr;
 233         int move_judge, cur_judge, mvx, mvy;
 234
 235         (void)strcpy(ok_moves, find_moves());
 236         best_move = ok_moves[0];
 237         if (best_move != 't') {
 238                 mvx = xinc(best_move);
 239                 mvy = yinc(best_move);
 240                 move_judge = ABS(mvx - dx) + ABS(mvy - dy);
 241                 for (ptr = &ok_moves[1]; *ptr != '\0'; ptr++) {
 242                         mvx = xinc(*ptr);
 243                         mvy = yinc(*ptr);
 244                         cur_judge = ABS(mvx - dx) + ABS(mvy - dy);
 245                         if (cur_judge < move_judge) {
 246                                 move_judge = cur_judge;
 247                                 best_move = *ptr;
 248                         }
 249                 }
 250         }
 251         return best_move;
 252 } /* end move_towards */
 253
 254 /* move_away():
 255  *      move away form the robot given
 256  */
 257 static char
 258 move_away(rob)
 259         COORD *rob;
 260 {
 261         int dx, dy;
 262
 263         dx = sign(My_pos.x - rob->x);
 264         dy = sign(My_pos.y - rob->y);
 265         return  move_towards(dx, dy);
 266 } /* end move_away */
 267
 268
 269 /* move_between():
 270  *      move the closest heap between us and the closest robot
 271  */
 272 static char
 273 move_between(rob, hp)
 274         COORD *rob;
 275         COORD *hp;
 276 {
 277         int dx, dy;
 278         float slope, cons;
 279
 280         /* equation of the line between us and the closest robot */
 281         if (My_pos.x == rob->x) {
 282                 /*
 283                  * me and the robot are aligned in x
 284                  * change my x so I get closer to the heap
 285                  * and my y far from the robot
 286                  */
 287                 dx = - sign(My_pos.x - hp->x);
 288                 dy = sign(My_pos.y - rob->y);
 289                 CONSDEBUG(("aligned in x"));
 290         }
 291         else if (My_pos.y == rob->y) {
 292                 /*
 293                  * me and the robot are aligned in y
 294                  * change my y so I get closer to the heap
 295                  * and my x far from the robot
 296                  */
 297                 dx = sign(My_pos.x - rob->x);
 298                 dy = -sign(My_pos.y - hp->y);
 299                 CONSDEBUG(("aligned in y"));
 300         }
 301         else {
 302                 CONSDEBUG(("no aligned"));
 303                 slope = (My_pos.y - rob->y) / (My_pos.x - rob->x);
 304                 cons = slope * rob->y;
 305                 if (ABS(My_pos.x - rob->x) > ABS(My_pos.y - rob->y)) {
 306                         /*
 307                          * we are closest to the robot in x
 308                          * move away from the robot in x and
 309                          * close to the scrap in y
 310                          */
 311                         dx = sign(My_pos.x - rob->x);
 312                         dy = sign(((slope * ((float) hp->x)) + cons) -
 313                                   ((float) hp->y));
 314                 }
 315                 else {
 316                         dx = sign(((slope * ((float) hp->x)) + cons) -
 317                                   ((float) hp->y));
 318                         dy = sign(My_pos.y - rob->y);
 319                 }
 320         }
 321         CONSDEBUG(("me (%d,%d) robot(%d,%d) heap(%d,%d) delta(%d,%d)",
 322                 My_pos.x, My_pos.y, rob->x, rob->y, hp->x, hp->y, dx, dy));
 323         return move_towards(dx, dy);
 324 } /* end move_between */
 325
 326 /* between():
 327  *      Return true if the heap is between us and the robot
 328  */
 329 int
 330 between(rob, hp)
 331         COORD *rob;
 332         COORD *hp;
 333 {
 334         /* I = @ */
 335         if (hp->x > rob->x && My_pos.x < rob->x)
 336                 return 0;
 337         /* @ = I */
 338         if (hp->x < rob->x && My_pos.x > rob->x)
 339                 return 0;
 340         /* @ */
 341         /* = */
 342         /* I */
 343         if (hp->y < rob->y && My_pos.y > rob->y)
 344                 return 0;
 345         /* I */
 346         /* = */
 347         /* @ */
 348         if (hp->y > rob->y && My_pos.y < rob->y)
 349                 return 0;
 350         return 1;
 351 } /* end between */
 352
 353 /* automove():
 354  *      find and do the best move if flag
 355  *      else get the first move;
 356  */
 357 char
 358 automove()
 359 {
 360 #if 0
 361         return  find_moves()[0];
 362 #else
 363         COORD *robot_close;
 364         COORD *heap_close;
 365         int robot_dist, robot_heap, heap_dist;
 366
 367         robot_close = closest_robot(&robot_dist);
 368         if (robot_dist > 1)
 369                 return('.');
 370         if (!Num_scrap)
 371                 /* no scrap heaps just run away */
 372                 return move_away(robot_close);
 373
 374         heap_close = closest_heap(&heap_dist);
 375         robot_heap = distance(robot_close->x, robot_close->y,
 376             heap_close->x, heap_close->y);
 377         if (robot_heap <= heap_dist && !between(robot_close, heap_close)) {
 378                 /*
 379                  * robot is closest to us from the heap. Run away!
 380                  */
 381                 return  move_away(robot_close);
 382         }
 383
 384         return move_between(robot_close, heap_close);
 385 #endif
 386 } /* end automove */