interpreters/nitfol/automap.c

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