interpreters/nitfol/automap.c

   1 /*  automap.c: main automapping code
   2     Copyright (C) 1999  Evin Robertson
   3     Copyright (C) 2010 Jörg Walter
   4
   5     This program is free software; you can redistribute it and/or modify
   6     it under the terms of the GNU General Public License as published by
   7     the Free Software Foundation; either version 2 of the License, or
   8     (at your option) any later version.
   9
  10     This program is distributed in the hope that it will be useful,
  11     but WITHOUT ANY WARRANTY; without even the implied warranty of
  12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU General Public License for more details.
  14
  15     You should have received a copy of the GNU General Public License
  16     along with this program; if not, write to the Free Software
  17     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
  18
  19     The author can be reached at nitfol@deja.com
  20 */
  21
  22 #include "nitfol.h"
  23
  24 #ifdef DEBUGGING
  25
  26 struct dirinfo {
  27   const char *name;
  28   int deltax, deltay;
  29   glui32 symbol;
  30   glui32 oneway;
  31 };
  32
  33 static const struct dirinfo dirways[] = {
  34   { "n",   0, -1, 0x2502,  0x2191 },
  35   { "s",   0,  1, 0x2502,  0x2193 },
  36   { "w",  -1,  0, 0x2500,  0x2190 },
  37   { "e",   1,  0, 0x2500,  0x2192 },
  38   { "nw", -1, -1, 0x2572,  0x2196 },
  39   { "se",  1,  1, 0x2572,  0x2198 },
  40   { "ne",  1, -1, 0x2571,  0x2197 },
  41   { "sw", -1,  1, 0x2571,  0x2199 },
  42   { "up",  0,  0, 0x21c8,    0   },
  43   { "down", 0, 0, 0x21ca,    0   },
  44   { "wait", 0, 0, 0x21ba,    0   }
  45 };
  46
  47 #define CROSS 0x253c
  48 #define DIAGONAL_CROSS 0x2573
  49
  50 #define NUM_EXITS (sizeof(dirways) / sizeof(*dirways))
  51 #define REVERSE_DIR(dir) (dir ^ 1)
  52
  53 #define NUM_DIRS  (NUM_EXITS - 3)
  54 #define NUM_WALK  (NUM_EXITS - 1)
  55
  56 #define DIR_UP   (NUM_DIRS + 0)
  57 #define DIR_DOWN (NUM_DIRS + 1)
  58 #define DIR_WAIT (NUM_DIRS + 2)
  59
  60 // "*udb@UDB+"
  61 char *roomsymbol = NULL;
  62 glui32 uni_roomsymbol[9] = { 0x25cb, 0x25b3, 0x25bd, 0x25c7, 0x25cf, 0x25b2, 0x25bc, 0x25c6, 0x25cc };
  63
  64 #define ROOM_SYMBOL(is_player, is_up, is_down, is_real) (is_real ? uni_roomsymbol[(is_up != 0) | ((is_down != 0) << 1) | ((is_player != 0) << 2)] : uni_roomsymbol[8])
  65
  66
  67 typedef struct edge edge;
  68 typedef struct loc_node loc_node;
  69
  70 struct edge {
  71   loc_node *dest[2];                    /* Two endpoints of passage */
  72   BOOL is_oneway; /* Oneway passages are always created dest[0]--->dest[1] */
  73   BOOL touched;
  74   int min_length;
  75   int guess_length;
  76 };
  77
  78 struct loc_node {
  79   zword number;
  80   BOOL found, real, touched;
  81   edge *outgoing[NUM_DIRS];             /* Drawn map connections */
  82   loc_node *exits[NUM_EXITS];           /* Actual connections */
  83   glui32 dist;                          /* For automap_find_path */
  84 };
  85
  86
  87 typedef struct edgelist edgelist;
  88 struct edgelist {
  89   edgelist *next;
  90   edge *node;
  91 };
  92
  93 static edgelist *all_edges;
  94
  95 static edge *automap_new_edge(loc_node *src, loc_node *dest, BOOL is_oneway)
  96 {
  97   edgelist newedge;
  98   newedge.node = n_malloc(sizeof(edge));
  99   newedge.node->dest[0] = src;
 100   newedge.node->dest[1] = dest;
 101   newedge.node->is_oneway = is_oneway;
 102   newedge.node->touched = FALSE;
 103   newedge.node->min_length = is_oneway ? 4 : 2;
 104   newedge.node->guess_length = is_oneway ? 4 : 2;
 105   LEadd(all_edges, newedge);
 106   return newedge.node;
 107 }
 108
 109
 110 static void automap_remove_edge(edge *e)
 111 {
 112   unsigned n, i;
 113   edgelist *p, *t;
 114   if(e == NULL)
 115     return;
 116   for(n = 0; n < 2; n++) {
 117     loc_node *thisdest = e->dest[n];
 118     if(thisdest)
 119       for(i = 0; i < NUM_DIRS; i++) {
 120         if(thisdest->outgoing[i] == e)
 121           thisdest->outgoing[i] = NULL;
 122       }
 123   }
 124   LEsearchremove(all_edges, p, t, p->node == e, n_free(p->node));
 125 }
 126
 127
 128 static void automap_edges_untouch(void)
 129 {
 130   edgelist *p;
 131   for(p = all_edges; p; p=p->next) {
 132     p->node->touched = FALSE;
 133   }
 134 }
 135
 136
 137 static void automap_edges_mindist(void)
 138 {
 139   edgelist *p;
 140   for(p = all_edges; p; p=p->next) {
 141     int len = p->node->is_oneway ? 4 : 2;
 142     p->node->min_length = p->node->guess_length = len;
 143   }
 144 }
 145
 146
 147 static hash_table rooms;
 148 static char *loc_exp;
 149 static zwinid automap_win;
 150
 151
 152 void automap_kill(void)
 153 {
 154   mymap_kill();
 155   n_free(loc_exp);
 156   loc_exp = NULL;
 157   LEdestruct(all_edges, n_free(all_edges->node));
 158   n_hash_free_table(&rooms, n_free);
 159   z_kill_window(automap_win);
 160 }
 161
 162 BOOL automap_init(int numobj, const char *location_exp)
 163 {
 164   int i;
 165   automap_kill();
 166
 167   if(roomsymbol) {
 168     for (i = 0; i < strlen(roomsymbol); i++) {
 169       uni_roomsymbol[i] = (unsigned char)roomsymbol[i];
 170     }
 171   }
 172
 173   if(location_exp)
 174     loc_exp = n_strdup(location_exp);
 175
 176   n_hash_construct_table(&rooms, numobj / 2);
 177
 178   automap_win = z_split_screen(wintype_TextGrid,
 179                                automap_split | winmethod_Fixed,
 180                                automap_draw_callback, automap_mouse_callback);
 181   return TRUE;
 182 }
 183
 184
 185 static loc_node *room_find(glui32 location, BOOL is_real)
 186 {
 187   const char *preface = is_real ? "" : "fake";
 188   const char *key = n_static_number(preface, location);
 189   return (loc_node *) n_hash_lookup(key, &rooms);
 190 }
 191
 192
 193 static loc_node *room_find_or_create(glui32 location, BOOL is_real)
 194 {
 195   loc_node *r;
 196   const char *preface = is_real ? "" : "fake";
 197   const char *key = n_static_number(preface, location);
 198   r = (loc_node *) n_hash_lookup(key, &rooms);
 199   if(r == NULL) {
 200     unsigned n;
 201     r = (loc_node *) n_malloc(sizeof(loc_node));
 202     r->number = location;
 203     r->found = FALSE;
 204     r->real = is_real;
 205     r->touched = FALSE;
 206     for(n = 0; n < NUM_EXITS; n++) {
 207       r->exits[n] = NULL;
 208       if(n < NUM_DIRS)
 209         r->outgoing[n] = NULL;
 210     }
 211     n_hash_insert(key, r, &rooms);
 212   }
 213   return r;
 214 }
 215
 216
 217 static void room_remove(loc_node *room)
 218 {
 219   unsigned n;
 220   if(room) {
 221     const char *preface = room->real ? "" : "fake";
 222     for(n = 0; n < NUM_DIRS; n++)
 223       automap_remove_edge(room->outgoing[n]);
 224     n_free(n_hash_del(n_static_number(preface, room->number), &rooms));
 225   }
 226 }
 227
 228
 229
 230 typedef struct automap_path automap_path;
 231 struct automap_path {
 232   automap_path *next;
 233   loc_node *loc; /* A location */
 234   int dir;       /* And the direction we're going from it */
 235 };
 236
 237 typedef struct interlist interlist;
 238 struct interlist {
 239   interlist *next;
 240
 241   loc_node *a, *b;
 242 };
 243
 244
 245 static BOOL mymap_plot(int x, int y, glui32 symbol, loc_node *node);
 246 static edge *automap_get_edge(loc_node *location, int dir);
 247 static void automap_calc_location(loc_node *location, loc_node *last,
 248                                   int x, int y);
 249 static automap_path *automap_find_path(loc_node *location, loc_node *dest,
 250                                        BOOL by_walking);
 251 static int automap_edge_oneway(loc_node *location, int dir);
 252 static loc_node *automap_edge_follow(loc_node *location, int dir);
 253
 254
 255 static interlist *interferences = NULL;
 256
 257 static void automap_forget_interference(void)
 258 {
 259   LEdestroy(interferences);
 260 }
 261
 262 static void automap_remember_interference(loc_node *a, loc_node *b)
 263 {
 264   /*  interlist *p;
 265   LEsearch(interferences, p, (p->a==a && p->b==b) || (p->a==b && p->b==a));
 266   if(!p) {*/
 267     interlist newnode;
 268     newnode.a = a;
 269     newnode.b = b;
 270     LEadd(interferences, newnode);
 271     /*  }*/
 272 }
 273
 274
 275 static int automap_find_and_count_interference(loc_node *center)
 276 {
 277   interlist *i;
 278   int count;
 279
 280   automap_cycles_fill_values();
 281   automap_forget_interference();
 282   mymap_reinit();
 283   n_hash_enumerate(&rooms, make_untouched);
 284   automap_edges_untouch();
 285   automap_calc_location(center, NULL, 0, 0);
 286
 287   count = 0;
 288   for(i = interferences; i; i=i->next)
 289     count++;
 290
 291   return count;
 292 }
 293
 294
 295 /* Returns TRUE if it improved any */
 296 static BOOL automap_increase_along_path(automap_path *path, int oldcount,
 297                                         loc_node *center, int effort)
 298 {
 299   automap_path *p;
 300   int exploring;
 301   int explore_max = effort > 1;
 302   if(!effort)
 303     return FALSE;
 304
 305   /* Takes two passes at trying to improve the situation.
 306      The first time (!exploring), it tries increasing the length of each
 307      edge along the path, observing the results and then undoing the increase.
 308      If it was able to improve anything, it returns with the best improvement.
 309      Otherwise it tries increasing the length of each edge and calling itself;
 310      If its child is able to improve things, then it returns with both
 311      lengthenings in effect. */
 312
 313   for(exploring = 0; exploring <= explore_max; exploring++) {
 314     edge *best_edge = NULL;
 315     int best_count = oldcount;
 316     int smallest_new = 10000;
 317
 318     for(p = path; p; p=p->next) {
 319       int newcount;
 320       edge *e = automap_get_edge(p->loc, p->dir);
 321       int old_min_length = e->min_length;
 322       int old_guess_length = e->guess_length;
 323
 324       if(p->next && p->next->loc != automap_edge_follow(p->loc, p->dir))
 325           n_show_error(E_SYSTEM, "path doesn't follow itself", 0);
 326
 327       e->guess_length += 2;
 328       e->min_length = e->guess_length;
 329
 330       if(!exploring) {
 331         newcount = automap_find_and_count_interference(center);
 332         if(newcount < best_count
 333            || (newcount == best_count && newcount < oldcount
 334                && e->min_length < smallest_new)) {
 335           best_edge = e;
 336           best_count = newcount;
 337           smallest_new = e->min_length;
 338         }
 339       } else {
 340         if(automap_increase_along_path(p, oldcount, center, effort-1))
 341           return TRUE;
 342       }
 343
 344       e->min_length   = old_min_length;
 345       e->guess_length = old_guess_length;
 346     }
 347
 348     if(!exploring && best_edge) {
 349       best_edge->guess_length += 2;
 350       best_edge->min_length = best_edge->guess_length;
 351       automap_find_and_count_interference(center);
 352       return TRUE;
 353     }
 354   }
 355   return FALSE;
 356 }
 357
 358
 359 /* Returns true if all interferences have been resolved */
 360 static BOOL automap_resolve_interference(loc_node *center, int effort)
 361 {
 362   int skip_interferences = 0;
 363   int n;
 364
 365   while(interferences) {
 366     interlist *oldinter = interferences;
 367     interlist *i;
 368     automap_path *path;
 369     int oldcount;
 370
 371     oldcount = 0;
 372     for(i = oldinter; i; i=i->next)
 373       oldcount++;
 374
 375     if(skip_interferences >= oldcount)
 376       return FALSE;
 377
 378     i = oldinter;
 379     for(n = 0; n < skip_interferences; n++)
 380       i=i->next;
 381
 382     path = automap_find_path(i->a, i->b, FALSE);
 383     if(!path)
 384       return FALSE;
 385
 386     interferences = NULL;
 387
 388     if(!automap_increase_along_path(path, oldcount, center, effort))
 389       skip_interferences++;
 390
 391     LEdestroy(oldinter);
 392     LEdestroy(path);
 393   }
 394   return TRUE;
 395 }
 396
 397
 398 static void automap_set_virtual_connection(loc_node *location, int d,
 399                                            loc_node *dest, BOOL is_oneway)
 400 {
 401   if(location->outgoing[d]) {
 402     int way = automap_edge_oneway(location, d);
 403     if(dest || way != 2)
 404       automap_remove_edge(location->outgoing[d]);
 405   }
 406
 407   if(dest) {
 408     edge *p = automap_new_edge(location, dest, is_oneway);
 409
 410     location->outgoing[d] = p;
 411
 412     if(dest->outgoing[REVERSE_DIR(d)])
 413       automap_remove_edge(dest->outgoing[REVERSE_DIR(d)]);
 414     dest->outgoing[REVERSE_DIR(d)] = p;
 415   }
 416 }
 417
 418
 419 static void automap_set_connection(int location, int d, int dest, BOOL is_real)
 420 {
 421   loc_node *r, *t;
 422
 423   r = room_find_or_create(location, is_real);
 424   t = room_find_or_create(dest, is_real);
 425
 426   if(t == r)
 427     t = NULL;
 428
 429   r->exits[d] = t;
 430 }
 431
 432
 433 static edge *automap_get_edge(loc_node *location, int dir)
 434 {
 435   return location->outgoing[dir];
 436 }
 437
 438
 439 static loc_node *automap_edge_follow(loc_node *location, int dir)
 440 {
 441   if(location->outgoing[dir] == NULL)
 442     return NULL;
 443
 444   if(location->outgoing[dir]->dest[0] == location)
 445     return location->outgoing[dir]->dest[1];
 446   if(location->outgoing[dir]->dest[1] == location)
 447     return location->outgoing[dir]->dest[0];
 448
 449   n_show_error(E_SYSTEM, "edge isn't connected to what it should be", 0);
 450   return NULL;
 451 }
 452
 453
 454 static int automap_edge_length(loc_node *location, int dir)
 455 {
 456   return location->outgoing[dir]->guess_length;
 457 }
 458
 459
 460 /* Returns 0 if not oneway, 1 if oneway in the given direction, and 2 if
 461    oneway in the other direction */
 462 static int automap_edge_oneway(loc_node *location, int dir)
 463 {
 464   if(location->outgoing[dir] == NULL)
 465     return 0;
 466   if(location->outgoing[dir]->dest[0] == location)
 467     return location->outgoing[dir]->is_oneway;
 468   return (location->outgoing[dir]->is_oneway) << 1;
 469 }
 470
 471
 472 static BOOL automap_draw_edge(loc_node *location, int dir, int *x, int *y)
 473 {
 474   int deltax, deltay;
 475   int s;
 476   int len;
 477   int oneway;
 478   edge *e = automap_get_edge(location, dir);
 479
 480   if(e->touched)
 481     return TRUE;
 482   e->touched = TRUE;
 483
 484   deltax = dirways[dir].deltax;
 485   deltay = dirways[dir].deltay;
 486   len = automap_edge_length(location, dir);
 487   oneway = automap_edge_oneway(location, dir);
 488
 489   *x += deltax;
 490   *y += deltay;
 491
 492   if(oneway)
 493     len--;
 494
 495   if(oneway == 2) {
 496     mymap_plot(*x, *y, dirways[REVERSE_DIR(dir)].oneway, location);
 497     *x += deltax;
 498     *y += deltay;
 499   }
 500
 501   for(s = 1; s < len; s++) {
 502     mymap_plot(*x, *y, dirways[dir].symbol, location);
 503     *x += deltax;
 504     *y += deltay;
 505   }
 506
 507   if(oneway == 1) {
 508     mymap_plot(*x, *y, dirways[dir].oneway, location);
 509     *x += deltax;
 510     *y += deltay;
 511   }
 512   return TRUE;
 513 }
 514
 515
 516 static void automap_adjust_length(loc_node *location, int dir, int newlen)
 517 {
 518   location->outgoing[dir]->min_length = newlen;
 519 }
 520
 521
 522 static int mapwidth;
 523 static int mapheight;
 524
 525 static glui32 *mymap = NULL;
 526 static loc_node **mymapnode = NULL;
 527
 528 static char mymap_read(int x, int y)
 529 {
 530   x += mapwidth / 2; y += mapheight / 2;
 531   if(x < 0 || x >= mapwidth || y < 0 || y >= mapheight)
 532     return ' ';
 533   return mymap[x + y * mapheight];
 534 }
 535
 536
 537 static BOOL mymap_plot(int x, int y, glui32 symbol, loc_node *node)
 538 {
 539   BOOL status = TRUE;
 540   glui32 *dest;
 541   x += mapwidth / 2; y += mapheight / 2;
 542   if(x < 0 || x >= mapwidth || y < 0 || y >= mapheight)
 543     return status;
 544   dest = &mymap[x + y * mapwidth];
 545   if(*dest != ' ') {
 546     if((*dest==dirways[4].symbol && symbol==dirways[6].symbol) || (*dest==dirways[6].symbol && symbol==dirways[4].symbol))
 547       symbol = DIAGONAL_CROSS;
 548     else if((*dest==dirways[0].symbol && symbol==dirways[2].symbol) || (*dest==dirways[2].symbol && symbol==dirways[0].symbol))
 549       symbol = CROSS;
 550     else
 551       status = FALSE;
 552   } else {
 553     if(mymapnode[x + y * mapwidth])
 554       status = FALSE;
 555   }
 556   if(status) {
 557     *dest = symbol;
 558     mymapnode[x + y * mapwidth] = node;
 559   } else {
 560     loc_node *interfere = mymapnode[x + y * mapwidth];
 561     automap_remember_interference(node, interfere);
 562   }
 563   return status;
 564 }
 565
 566
 567 void mymap_init(int width, int height)
 568 {
 569   int i;
 570   int max;
 571   mapwidth = width * 2;
 572   mapheight = height * 2;
 573   max = mapwidth * mapheight;
 574   n_free(mymap);
 575   n_free(mymapnode);
 576   mymap = (glui32 *) n_malloc(max*sizeof(*mymap));
 577   mymapnode = (loc_node **) n_malloc(max * sizeof(*mymapnode));
 578   for(i = 0; i < max; i++) {
 579     mymap[i] = ' ';
 580     mymapnode[i] = NULL;
 581   }
 582 }
 583
 584
 585 int automap_get_height(void)
 586 {
 587   return mapheight / 2;
 588 }
 589
 590
 591 void mymap_reinit(void)
 592 {
 593   mymap_init(mapwidth/2, mapheight/2);
 594 }
 595
 596
 597 void mymap_kill(void)
 598 {
 599   n_free(mymap);
 600   mymap = NULL;
 601   n_free(mymapnode);
 602   mymapnode = NULL;
 603 }
 604
 605
 606 static int xoffset, yoffset;
 607
 608 static void mymap_draw(void)
 609 {
 610   int x, y;
 611   int firsty, firstx, lasty, lastx;
 612   int height, width;
 613
 614   firsty = mapheight; firstx = mapwidth;
 615   lasty = 0; lastx = 0;
 616   for(y = 0; y < mapheight; y++) {
 617     for(x = 0; x < mapwidth; x++)
 618       if(mymap[x + y * mapwidth] != ' ') {
 619         if(y < firsty)
 620           firsty = y;
 621         if(y > lasty)
 622           lasty = y;
 623         if(x < firstx)
 624           firstx = x;
 625         if(x > lastx)
 626           lastx = x;
 627       }
 628   }
 629
 630   height = lasty - firsty; width = lastx - firstx;
 631
 632   xoffset = firstx + (width - mapwidth/2) / 2;
 633   yoffset = firsty + (height - mapheight/2) / 2;
 634
 635   if(yoffset >= mapheight/2)
 636     yoffset = mapheight/2 - 1;
 637   if(yoffset <= 1)
 638     yoffset = 2;
 639   if(xoffset >= mapwidth/2)
 640     xoffset = mapwidth/2 - 1;
 641   if(xoffset <= 1)
 642     xoffset = 2;
 643
 644   for(y = 0; y < mapheight/2; y++) {
 645     for(x = 0; x < mapwidth/2; x++)
 646       glk_put_char_uni(mymap[x+xoffset + (y+yoffset) * mapwidth]);
 647   }
 648 }
 649
 650 static glui32 selected_room_number = 0;
 651
 652 static void automap_write_loc(int x, int y)
 653 {
 654   loc_node *room;
 655   selected_room_number = 0;
 656   x += xoffset; y += yoffset;
 657   if(x < 0 || x >= mapwidth || y < 0 || y >= mapheight)
 658     return;
 659   room = mymapnode[x + y * mapwidth];
 660   if(!room || !room->found || !room->real)
 661     return;
 662   selected_room_number = room->number;
 663 }
 664
 665
 666 glui32 automap_draw_callback(winid_t win, glui32 width, glui32 height)
 667 {
 668   if(win == NULL)
 669     return automap_size;
 670
 671   mymap_init(width, height);
 672   automap_set_locations(automap_location);
 673
 674   glk_stream_set_current(glk_window_get_stream(win));
 675   mymap_draw();
 676
 677   if(selected_room_number) {
 678     offset short_name_off = object_name(selected_room_number);
 679     glk_window_move_cursor(win, 0, 0);
 680
 681     if(short_name_off)
 682       decodezscii(short_name_off, w_glk_put_char);
 683     else
 684       w_glk_put_string("<nameless>");
 685     w_glk_put_string(" (");
 686     g_print_number(selected_room_number);
 687     glk_put_char(')');
 688   }
 689   return automap_size;
 690 }
 691
 692
 693 BOOL automap_mouse_callback(BOOL is_char_event,
 694                             winid_t win, glui32 x, glui32 y)
 695 {
 696   automap_write_loc(x, y);
 697   return FALSE;
 698 }
 699
 700
 701 static void automap_calc_location(loc_node *location, loc_node *last,
 702                                   int x, int y)
 703 {
 704   unsigned i;
 705   glui32 symbol;
 706   loc_node *is_up, *is_down;
 707
 708   if(!location)
 709     return;
 710
 711   if(location->touched)
 712     return;
 713   location->touched = TRUE;
 714
 715   /* Make sure unfound locations are blanked */
 716   if(!location->found) {
 717     mymap_plot(x, y, ' ', location);
 718     return;
 719   }
 720
 721
 722   /* Don't draw up/down exits if there's a normal passage leading that way */
 723   is_up = location->exits[DIR_UP];
 724   is_down = location->exits[DIR_DOWN];
 725   for(i = 0; i < NUM_DIRS; i++) {
 726     loc_node *thisdest = automap_edge_follow(location, i);
 727     if(thisdest && !thisdest->real)
 728       thisdest = location->exits[i];
 729     if(thisdest == is_up)
 730       is_up = 0;
 731     if(thisdest == is_down)
 732       is_down = 0;
 733   }
 734
 735   symbol = ROOM_SYMBOL((x==0 && y==0), is_up, is_down, location->real);
 736
 737   mymap_plot(x, y, symbol, location);
 738
 739   for(i = 0; i < NUM_DIRS; i++) {
 740     loc_node *thisdest = automap_edge_follow(location, i);
 741     if(thisdest && thisdest != last) {
 742       int destx = x;
 743       int desty = y;
 744       automap_draw_edge(location, i, &destx, &desty);
 745       automap_calc_location(thisdest, location, destx, desty);
 746     }
 747   }
 748 }
 749
 750
 751 /* Returns magic cookies to identify fake locations */
 752 static glui32 automap_get_cookie(void) {
 753   /* FIXME: When the glui32 wraps around Bad Things will happen if we return a
 754      cookie still in use.  Should reissue cookies to everyone when we wrap
 755      around. */
 756   static glui32 cookie = 0;
 757   return cookie++;
 758 }
 759
 760
 761 static void automap_calc_exits(loc_node *location, int depth)
 762 {
 763   unsigned i, n;
 764   loc_node *proposed[NUM_DIRS];         /* Store proposed edges here */
 765   BOOL is_oneway[NUM_DIRS];
 766
 767   /* Remove fake locations */
 768   for(i = 0; i < NUM_DIRS; i++) {
 769     loc_node *curdest = automap_edge_follow(location, i);
 770     if(curdest && !curdest->real)
 771       room_remove(curdest);
 772   }
 773
 774   /* Default to things going the way they actually do */
 775   for(i = 0; i < NUM_DIRS; i++) {
 776     proposed[i] = location->exits[i];
 777     is_oneway[i] = FALSE;
 778   }
 779
 780   /* Get rid of superfluous exits */
 781   for(i = 0; i < NUM_DIRS; i++) {
 782     if(proposed[i]) {
 783       for(n = i+1; n < NUM_DIRS; n++) {
 784         if(proposed[n] == proposed[i]) {
 785           if(proposed[i]->exits[REVERSE_DIR(n)] == location) {
 786             proposed[i] = NULL;
 787             break;
 788           }
 789           if(proposed[i]->exits[REVERSE_DIR(i)] == location)
 790             proposed[n] = NULL;
 791         }
 792       }
 793     }
 794   }
 795
 796   /* Handle forced movement */
 797   for(i = 0; i < NUM_DIRS; i++) {
 798     if(proposed[i] && proposed[i] == location->exits[DIR_WAIT]) {
 799       if(proposed[i]->exits[REVERSE_DIR(i)] != location)
 800         proposed[i] = NULL;
 801     }
 802   }
 803
 804   /* Check for one way and bent passages */
 805   for(i = 0; i < NUM_DIRS; i++) {
 806     if(proposed[i] && proposed[i]->found
 807        && proposed[i]->exits[REVERSE_DIR(i)] != location) {
 808       is_oneway[i] = TRUE;
 809       for(n = 0; n < NUM_DIRS; n++) {
 810         if(n != i && proposed[i]->exits[n] == location) {
 811           loc_node *newnode = room_find_or_create(automap_get_cookie(), FALSE);
 812
 813           is_oneway[i] = FALSE;
 814           newnode->found = TRUE;
 815
 816           automap_set_virtual_connection(proposed[i], n, newnode, FALSE);
 817           proposed[i] = newnode;
 818         }
 819       }
 820     }
 821   }
 822
 823   /* If it's a one way passage, but there are up/down exits connecting the two,
 824      ignore the passage */
 825   for(i = 0; i < NUM_DIRS; i++) {
 826     if(is_oneway[i] && proposed[i]
 827          && ((location->exits[DIR_UP] == proposed[i]
 828               && proposed[i]->exits[DIR_DOWN] == location)
 829              || (location->exits[DIR_DOWN] == proposed[i]
 830                  && proposed[i]->exits[DIR_UP] == location))) {
 831       proposed[i] = 0;
 832       is_oneway[i] = FALSE;
 833     }
 834   }
 835
 836   /* Create the proposed passages */
 837   for(i = 0; i < NUM_DIRS; i++)
 838     automap_set_virtual_connection(location, i, proposed[i], is_oneway[i]);
 839
 840   /* Explore neighbors */
 841   if(depth) {
 842     for(i = 0; i < NUM_DIRS; i++)
 843       automap_calc_exits(location->exits[i], depth-1);
 844   }
 845 }
 846
 847
 848 #define INFINITY 1000000L
 849
 850 static void make_distant(const char *unused_key, void *r)
 851 {
 852   loc_node *t = (loc_node *) r;
 853   t->dist = INFINITY;
 854 }
 855
 856
 857 static void automap_calc_distances(loc_node *location, glui32 distance,
 858                                    BOOL by_walking)
 859 {
 860   unsigned i;
 861   unsigned maxdir = by_walking ? NUM_EXITS : NUM_DIRS;
 862   if(location->dist < distance)
 863     return;
 864   location->dist = distance;
 865   for(i = 0; i < maxdir; i++) {
 866     loc_node *thisdest;
 867     if(by_walking)
 868       thisdest = location->exits[i];
 869     else
 870       thisdest = automap_edge_follow(location, i);
 871
 872     if(thisdest)
 873       automap_calc_distances(thisdest, distance+1, by_walking);
 874   }
 875 }
 876
 877
 878 static automap_path *automap_find_path(loc_node *location, loc_node *dest,
 879                                        BOOL by_walking)
 880 {
 881   automap_path *path = NULL;
 882   automap_path *rev;
 883   automap_path newnode;
 884   loc_node *p;
 885
 886   /* Find the distances of all nodes from dest */
 887   n_hash_enumerate(&rooms, make_distant);
 888   automap_calc_distances(dest, 0, by_walking);
 889
 890   /* If dest isn't reachable, location's distance will still be infinite */
 891   if(location->dist == INFINITY)
 892     return NULL;
 893
 894   /* At each step, go toward a nearer node 'till we're there */
 895   p = location;
 896   while(p != dest) {
 897     unsigned i;
 898     unsigned best_dir;
 899     glui32 best_dist = INFINITY;
 900     loc_node *best_node = NULL;
 901     unsigned maxdir = by_walking ? NUM_EXITS : NUM_DIRS;
 902     for(i = 0; i < maxdir; i++) {
 903       loc_node *thisdest;
 904       if(by_walking)
 905         thisdest = p->exits[i];
 906       else
 907         thisdest = automap_edge_follow(p, i);
 908
 909       if(thisdest && thisdest->dist < best_dist) {
 910         best_dir = i;
 911         best_dist = thisdest->dist;
 912         best_node = thisdest;
 913       }
 914     }
 915     if(!best_node) {
 916       n_show_error(E_SYSTEM, "couldn't find path there", 0);
 917       return NULL;
 918     }
 919     newnode.loc = p;
 920     newnode.dir = best_dir;
 921     LEadd(path, newnode);
 922     p = best_node;
 923   }
 924
 925   rev = NULL;
 926   while(path) {
 927     LEadd(rev, *path);
 928     LEremove(path);
 929   }
 930
 931   return rev;
 932 }
 933
 934
 935 static void automap_find_cycles(loc_node *location, automap_path *curpath)
 936 {
 937   unsigned i;
 938   location->touched = TRUE;
 939   for(i = 0; i < NUM_DIRS; i++) {
 940     loc_node *thisdest = automap_edge_follow(location, i);
 941     if(thisdest && thisdest->found) {
 942       automap_path newnode;
 943       newnode.dir = i;
 944       newnode.loc = location;
 945       LEadd(curpath, newnode);
 946
 947       if(thisdest->touched) {           /* Found a cycle! */
 948         int cyclelength = 0;
 949         automap_path *p;
 950         cycleequation *cycle = NULL;
 951         cycleequation newcycle;
 952         for(p = curpath; p; p=p->next) {
 953           int dir = p->dir;
 954           newcycle.var = &(p->loc->outgoing[dir]->guess_length);
 955           newcycle.min = &(p->loc->outgoing[dir]->min_length);
 956           newcycle.xcoefficient = dirways[dir].deltax;
 957           newcycle.ycoefficient = dirways[dir].deltay;
 958           LEadd(cycle, newcycle);
 959
 960           cyclelength++;
 961           if(p->loc == thisdest) {      /* Found the relevant endpoint */
 962             if(cyclelength <= 2)     /* Ignore two nodes going to each other */
 963               LEdestroy(cycle);
 964             else
 965               automap_add_cycle(cycle); /* automap_add_cycle gets ownership */
 966             break;
 967           }
 968         }
 969         if(!p) {                        /* The cycle had already been found */
 970           LEdestroy(cycle);
 971         }
 972       } else {
 973         automap_find_cycles(thisdest, curpath);
 974       }
 975       LEremove(curpath);
 976     }
 977   }
 978 }
 979
 980
 981 static void automap_calc_cycles(loc_node *start)
 982 {
 983   automap_delete_cycles();
 984   automap_find_cycles(start, NULL);
 985   automap_cycle_elimination();
 986   automap_cycles_fill_values();
 987 }
 988
 989
 990 void make_untouched(const char *unused_key, void *r)
 991 {
 992   loc_node *t = (loc_node *) r;
 993   t->touched = FALSE;
 994 }
 995
 996
 997 void automap_set_locations(int center)
 998 {
 999   loc_node *r;
1000
1001   r = room_find(center, TRUE);
1002
1003   n_hash_enumerate(&rooms, make_untouched);
1004   automap_edges_mindist();
1005   automap_calc_cycles(r);
1006
1007   n_hash_enumerate(&rooms, make_untouched);
1008   automap_forget_interference();
1009   mymap_reinit();
1010   automap_edges_untouch();
1011   automap_calc_location(r, NULL, 0, 0);
1012
1013   automap_resolve_interference(r, 2);
1014 }
1015
1016
1017 static int automap_dir = NUM_EXITS;
1018 static BOOL automap_explored = FALSE;
1019 zword automap_location = 0;
1020
1021
1022 /* Returns a direction it wants you to explore in.  Take the direction and
1023    call automap_unexplore, which'll take you back to the @read.
1024    If it returns NULL, we're finished; get player input */
1025 const char *automap_explore(void)
1026 {
1027   if(automap_explored) {
1028     n_show_error(E_SAVE, "tried to explore when we just did so", automap_explored);
1029     return NULL;
1030   }
1031
1032   if(!loc_exp)
1033     return NULL;
1034
1035   if(automap_dir == NUM_EXITS) {
1036     fast_saveundo();
1037     automap_location = evaluate_expression(loc_exp, stack_get_depth()).v;
1038     automap_dir = 0;
1039   } else {
1040     automap_dir++;
1041     if(automap_dir == NUM_EXITS) {
1042       loc_node *r = room_find(automap_location, TRUE);
1043       r->found = TRUE;
1044       automap_calc_exits(r, 0);
1045       allow_saveundo = TRUE;
1046       allow_output = TRUE;
1047       return NULL;
1048     }
1049   }
1050
1051   allow_saveundo = FALSE;
1052   allow_output = FALSE;
1053   automap_explored = TRUE;
1054
1055   return dirways[automap_dir].name;
1056 }
1057
1058
1059 /* Undoes the work of automap_explore - call whenever a turn is 'over' */
1060 BOOL automap_unexplore(void)
1061 {
1062   zword dest;
1063
1064   if(!automap_explored || !loc_exp)
1065     return FALSE;
1066   automap_explored = FALSE;
1067
1068   dest = evaluate_expression(loc_exp, stack_get_depth()).v;
1069
1070   automap_set_connection(automap_location, automap_dir, dest, TRUE);
1071
1072   fast_restoreundo();
1073   return TRUE;
1074 }
1075
1076 #else
1077
1078 char *roomsymbol = NULL;
1079
1080 BOOL automap_unexplore(void)
1081 {
1082   return FALSE;
1083 }
1084
1085 #endif