automap.c

/*  automap.c: main automapping code
    Copyright (C) 1999  Evin Robertson

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.

    The author can be reached at nitfol@deja.com
*/

#include "nitfol.h"

#ifdef DEBUGGING

struct dirinfo {
  const char *name;
  int deltax, deltay;
  char symbol;
  char oneway;
};

static const struct dirinfo dirways[] = {
  { "n",   0, -1, '|',  '^' },
  { "s",   0,  1, '|',  'v' },
  { "w",  -1,  0, '-',  '<' },
  { "e",   1,  0, '-',  '>' },
  { "nw", -1, -1, '\\', '^' },
  { "se",  1,  1, '\\', 'v' },
  { "ne",  1, -1, '/',  '^' },
  { "sw", -1,  1, '/',  'v' },
  { "up",  0,  0, 0,    0   },
  { "down", 0, 0, 0,    0   },
  { "wait", 0, 0, 0,    0   }
};

#define NUM_EXITS (sizeof(dirways) / sizeof(*dirways))
#define REVERSE_DIR(dir) (dir ^ 1)

#define NUM_DIRS  (NUM_EXITS - 3)
#define NUM_WALK  (NUM_EXITS - 1)

#define DIR_UP   (NUM_DIRS + 0)
#define DIR_DOWN (NUM_DIRS + 1)
#define DIR_WAIT (NUM_DIRS + 2)

char *roomsymbol = NULL;

#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])


typedef struct edge edge;
typedef struct loc_node loc_node;

struct edge {
  loc_node *dest[2];                    /* Two endpoints of passage */
  BOOL is_oneway; /* Oneway passages are always created dest[0]--->dest[1] */
  BOOL touched;
  int min_length;
  int guess_length;
};

struct loc_node {
  zword number;
  BOOL found, real, touched;
  edge *outgoing[NUM_DIRS];             /* Drawn map connections */
  loc_node *exits[NUM_EXITS];           /* Actual connections */
  glui32 dist;                          /* For automap_find_path */
};


typedef struct edgelist edgelist;
struct edgelist {
  edgelist *next;
  edge *node;
};

static edgelist *all_edges;

static edge *automap_new_edge(loc_node *src, loc_node *dest, BOOL is_oneway)
{
  edgelist newedge;
  newedge.node = n_malloc(sizeof(edge));
  newedge.node->dest[0] = src;
  newedge.node->dest[1] = dest;
  newedge.node->is_oneway = is_oneway;
  newedge.node->touched = FALSE;
  newedge.node->min_length = is_oneway ? 4 : 2;
  newedge.node->guess_length = is_oneway ? 4 : 2;  
  LEadd(all_edges, newedge);
  return newedge.node;
}


static void automap_remove_edge(edge *e)
{
  unsigned n, i;
  edgelist *p, *t;
  if(e == NULL)
    return;
  for(n = 0; n < 2; n++) {
    loc_node *thisdest = e->dest[n];
    if(thisdest)
      for(i = 0; i < NUM_DIRS; i++) {
	if(thisdest->outgoing[i] == e)
	  thisdest->outgoing[i] = NULL;
      }
  }
  LEsearchremove(all_edges, p, t, p->node == e, n_free(p->node));
}


static void automap_edges_untouch(void)
{
  edgelist *p;
  for(p = all_edges; p; p=p->next) {
    p->node->touched = FALSE;
  }
}


static void automap_edges_mindist(void)
{
  edgelist *p;
  for(p = all_edges; p; p=p->next) {
    int len = p->node->is_oneway ? 4 : 2;
    p->node->min_length = p->node->guess_length = len;
  }
}


static hash_table rooms;
static char *loc_exp;
static zwinid automap_win;


void automap_kill(void)
{
  mymap_kill();
  n_free(loc_exp);
  loc_exp = NULL;
  LEdestruct(all_edges, n_free(all_edges->node));
  n_hash_free_table(&rooms, n_free);
  z_kill_window(automap_win);
}


BOOL automap_init(int numobj, const char *location_exp)
{
  automap_kill();

  if(!roomsymbol)
    roomsymbol = n_strdup("*udb@UDB+");
  
  if(location_exp)
    loc_exp = n_strdup(location_exp);

  n_hash_construct_table(&rooms, numobj / 2);

  automap_win = z_split_screen(wintype_TextGrid,
			       automap_split | winmethod_Fixed,
			       automap_draw_callback, automap_mouse_callback);
  return TRUE;
}


static loc_node *room_find(glui32 location, BOOL is_real)
{
  const char *preface = is_real ? "" : "fake";
  const char *key = n_static_number(preface, location);
  return (loc_node *) n_hash_lookup(key, &rooms);  
}


static loc_node *room_find_or_create(glui32 location, BOOL is_real)
{
  loc_node *r;
  const char *preface = is_real ? "" : "fake";
  const char *key = n_static_number(preface, location);
  r = (loc_node *) n_hash_lookup(key, &rooms);
  if(r == NULL) {
    unsigned n;
    r = (loc_node *) n_malloc(sizeof(loc_node));
    r->number = location;
    r->found = FALSE;
    r->real = is_real;
    r->touched = FALSE;
    for(n = 0; n < NUM_EXITS; n++) {
      r->exits[n] = NULL;
      if(n < NUM_DIRS)
	r->outgoing[n] = NULL;
    }
    n_hash_insert(key, r, &rooms);
  }
  return r;
}


static void room_remove(loc_node *room)
{
  unsigned n;
  if(room) {
    const char *preface = room->real ? "" : "fake";
    for(n = 0; n < NUM_DIRS; n++)
      automap_remove_edge(room->outgoing[n]);
    n_free(n_hash_del(n_static_number(preface, room->number), &rooms));
  }
}



typedef struct automap_path automap_path;
struct automap_path {
  automap_path *next;
  loc_node *loc; /* A location */
  int dir;       /* And the direction we're going from it */
};

typedef struct interlist interlist;
struct interlist {
  interlist *next;

  loc_node *a, *b;
};


static BOOL mymap_plot(int x, int y, char symbol, loc_node *node);
static edge *automap_get_edge(loc_node *location, int dir);
static void automap_calc_location(loc_node *location, loc_node *last,
				  int x, int y);
static automap_path *automap_find_path(loc_node *location, loc_node *dest,
				       BOOL by_walking);
static int automap_edge_oneway(loc_node *location, int dir);
static loc_node *automap_edge_follow(loc_node *location, int dir);


static interlist *interferences = NULL;

static void automap_forget_interference(void)
{
  LEdestroy(interferences);
}

static void automap_remember_interference(loc_node *a, loc_node *b)
{
  /*  interlist *p;
  LEsearch(interferences, p, (p->a==a && p->b==b) || (p->a==b && p->b==a));
  if(!p) {*/
    interlist newnode;
    newnode.a = a;
    newnode.b = b;
    LEadd(interferences, newnode);
    /*  }*/
}


static int automap_find_and_count_interference(loc_node *center)
{
  interlist *i;
  int count;
  
  automap_cycles_fill_values();
  automap_forget_interference();
  mymap_reinit();
  n_hash_enumerate(&rooms, make_untouched);
  automap_edges_untouch();
  automap_calc_location(center, NULL, 0, 0);
  
  count = 0;
  for(i = interferences; i; i=i->next)
    count++;
  
  return count;
}


/* Returns TRUE if it improved any */
static BOOL automap_increase_along_path(automap_path *path, int oldcount,
					loc_node *center, int effort)
{
  automap_path *p;
  int exploring;
  int explore_max = effort > 1;
  if(!effort)
    return FALSE;

  /* Takes two passes at trying to improve the situation.
     The first time (!exploring), it tries increasing the length of each
     edge along the path, observing the results and then undoing the increase.
     If it was able to improve anything, it returns with the best improvement.
     Otherwise it tries increasing the length of each edge and calling itself;
     If its child is able to improve things, then it returns with both
     lengthenings in effect. */
  
  for(exploring = 0; exploring <= explore_max; exploring++) {
    edge *best_edge = NULL;
    int best_count = oldcount;
    int smallest_new = 10000;
    
    for(p = path; p; p=p->next) {
      int newcount;
      edge *e = automap_get_edge(p->loc, p->dir);
      int old_min_length = e->min_length;
      int old_guess_length = e->guess_length;

      if(p->next && p->next->loc != automap_edge_follow(p->loc, p->dir))
	  n_show_error(E_SYSTEM, "path doesn't follow itself", 0);

      e->guess_length += 2;
      e->min_length = e->guess_length;
      
      if(!exploring) {
	newcount = automap_find_and_count_interference(center);
	if(newcount < best_count
	   || (newcount == best_count && newcount < oldcount
	       && e->min_length < smallest_new)) {
	  best_edge = e;
	  best_count = newcount;
	  smallest_new = e->min_length;
	}
      } else {
	if(automap_increase_along_path(p, oldcount, center, effort-1))
	  return TRUE;
      }
    
      e->min_length   = old_min_length;
      e->guess_length = old_guess_length;
    }

    if(!exploring && best_edge) {
      best_edge->guess_length += 2;
      best_edge->min_length = best_edge->guess_length;
      automap_find_and_count_interference(center);
      return TRUE;
    }
  }
  return FALSE;
}


/* Returns true if all interferences have been resolved */
static BOOL automap_resolve_interference(loc_node *center, int effort)
{
  int skip_interferences = 0;
  int n;
  
  while(interferences) {
    interlist *oldinter = interferences;
    interlist *i;
    automap_path *path;
    int oldcount;

    oldcount = 0;
    for(i = oldinter; i; i=i->next)
      oldcount++;

    if(skip_interferences >= oldcount)
      return FALSE;
    
    i = oldinter;
    for(n = 0; n < skip_interferences; n++)
      i=i->next;
    
    path = automap_find_path(i->a, i->b, FALSE);
    if(!path)
      return FALSE;

    interferences = NULL;
    
    if(!automap_increase_along_path(path, oldcount, center, effort))
      skip_interferences++;

    LEdestroy(oldinter);
    LEdestroy(path);
  }
  return TRUE;
}


static void automap_set_virtual_connection(loc_node *location, int d,
					   loc_node *dest, BOOL is_oneway)
{
  if(location->outgoing[d]) {
    int way = automap_edge_oneway(location, d);
    if(dest || way != 2)
      automap_remove_edge(location->outgoing[d]);
  }

  if(dest) {
    edge *p = automap_new_edge(location, dest, is_oneway);

    location->outgoing[d] = p;

    if(dest->outgoing[REVERSE_DIR(d)])
      automap_remove_edge(dest->outgoing[REVERSE_DIR(d)]);
    dest->outgoing[REVERSE_DIR(d)] = p;
  }
}


static void automap_set_connection(int location, int d, int dest, BOOL is_real)
{
  loc_node *r, *t;

  r = room_find_or_create(location, is_real);
  t = room_find_or_create(dest, is_real);

  if(t == r)
    t = NULL;
  
  r->exits[d] = t;
}


static edge *automap_get_edge(loc_node *location, int dir)
{
  return location->outgoing[dir];
}


static loc_node *automap_edge_follow(loc_node *location, int dir)
{
  if(location->outgoing[dir] == NULL)
    return NULL;
  
  if(location->outgoing[dir]->dest[0] == location)
    return location->outgoing[dir]->dest[1];
  if(location->outgoing[dir]->dest[1] == location)
    return location->outgoing[dir]->dest[0];
  
  n_show_error(E_SYSTEM, "edge isn't connected to what it should be", 0);
  return NULL;
}


static int automap_edge_length(loc_node *location, int dir)
{
  return location->outgoing[dir]->guess_length;
}


/* Returns 0 if not oneway, 1 if oneway in the given direction, and 2 if
   oneway in the other direction */
static int automap_edge_oneway(loc_node *location, int dir)
{
  if(location->outgoing[dir] == NULL)
    return 0;
  if(location->outgoing[dir]->dest[0] == location)
    return location->outgoing[dir]->is_oneway;
  return (location->outgoing[dir]->is_oneway) << 1;
}


static BOOL automap_draw_edge(loc_node *location, int dir, int *x, int *y)
{
  int deltax, deltay;
  int s;
  int len;
  int oneway;
  edge *e = automap_get_edge(location, dir);
  
  if(e->touched)
    return TRUE;
  e->touched = TRUE;

  deltax = dirways[dir].deltax;
  deltay = dirways[dir].deltay;
  len = automap_edge_length(location, dir);
  oneway = automap_edge_oneway(location, dir);
  
  *x += deltax;
  *y += deltay;

  if(oneway)
    len--;
  
  if(oneway == 2) {
    mymap_plot(*x, *y, dirways[REVERSE_DIR(dir)].oneway, location);
    *x += deltax;
    *y += deltay;
  }
    
  for(s = 1; s < len; s++) {
    mymap_plot(*x, *y, dirways[dir].symbol, location);
    *x += deltax;
    *y += deltay;
  }

  if(oneway == 1) {
    mymap_plot(*x, *y, dirways[dir].oneway, location);
    *x += deltax;
    *y += deltay;
  }
  return TRUE;
}


static void automap_adjust_length(loc_node *location, int dir, int newlen)
{
  location->outgoing[dir]->min_length = newlen;
}


static int mapwidth;
static int mapheight;

static char *mymap = NULL;
static loc_node **mymapnode = NULL;

static char mymap_read(int x, int y)
{
  x += mapwidth / 2; y += mapheight / 2;
  if(x < 0 || x >= mapwidth || y < 0 || y >= mapheight)
    return ' ';
  return mymap[x + y * mapheight];
}


static BOOL mymap_plot(int x, int y, char symbol, loc_node *node)
{
  BOOL status = TRUE;
  char *dest;
  x += mapwidth / 2; y += mapheight / 2;
  if(x < 0 || x >= mapwidth || y < 0 || y >= mapheight)
    return status;
  dest = &mymap[x + y * mapwidth];
  if(*dest != ' ') {
    if((*dest=='/' && symbol=='\\') || (*dest=='\\' && symbol=='/'))
      symbol = 'X';
    else if((*dest=='-' && symbol=='|') || (*dest=='|' && symbol=='-'))
      symbol = '+';
    else
      status = FALSE;
  } else {
    if(mymapnode[x + y * mapwidth])
      status = FALSE;
  }
  if(status) {
    *dest = symbol;
    mymapnode[x + y * mapwidth] = node;
  } else {
    loc_node *interfere = mymapnode[x + y * mapwidth];
    automap_remember_interference(node, interfere);
  }
  return status;
}


void mymap_init(int width, int height)
{
  int i;
  int max;
  mapwidth = width * 2;
  mapheight = height * 2;
  max = mapwidth * mapheight;
  n_free(mymap);
  n_free(mymapnode);
  mymap = (char *) n_malloc(max);
  mymapnode = (loc_node **) n_malloc(max * sizeof(*mymapnode));
  for(i = 0; i < max; i++) {
    mymap[i] = ' ';
    mymapnode[i] = NULL;
  }
}


int automap_get_height(void)
{
  return mapheight / 2;
}


void mymap_reinit(void)
{
  mymap_init(mapwidth/2, mapheight/2);
}


void mymap_kill(void)
{
  n_free(mymap);
  mymap = NULL;    
  n_free(mymapnode);
  mymapnode = NULL;
}


static int xoffset, yoffset;

static void mymap_draw(void)
{
  int x, y;
  int firsty, firstx, lasty, lastx;
  int height, width;

  firsty = mapheight; firstx = mapwidth;
  lasty = 0; lastx = 0;
  for(y = 0; y < mapheight; y++) {
    for(x = 0; x < mapwidth; x++)
      if(mymap[x + y * mapwidth] != ' ') {
	if(y < firsty)
	  firsty = y;
	if(y > lasty)
	  lasty = y;
	if(x < firstx)
	  firstx = x;
	if(x > lastx)
	  lastx = x;
      }
  }

  height = lasty - firsty; width = lastx - firstx;
  
  xoffset = firstx + (width - mapwidth/2) / 2;
  yoffset = firsty + (height - mapheight/2) / 2;

  if(yoffset >= mapheight/2)
    yoffset = mapheight/2 - 1;
  if(yoffset <= 1)
    yoffset = 2;
  if(xoffset >= mapwidth/2)
    xoffset = mapwidth/2 - 1;
  if(xoffset <= 1)
    xoffset = 2;
  
  for(y = 0; y < mapheight/2; y++) {
    for(x = 0; x < mapwidth/2; x++)
      glk_put_char(mymap[x+xoffset + (y+yoffset) * mapwidth]);
  }
}

static glui32 selected_room_number = 0;

static void automap_write_loc(int x, int y)
{
  loc_node *room;
  selected_room_number = 0;
  x += xoffset; y += yoffset;
  if(x < 0 || x >= mapwidth || y < 0 || y >= mapheight)
    return;
  room = mymapnode[x + y * mapwidth];
  if(!room || !room->found || !room->real)
    return;
  selected_room_number = room->number;
}


glui32 automap_draw_callback(winid_t win, glui32 width, glui32 height)
{
  if(win == NULL)
    return automap_size;

  mymap_init(width, height);
  automap_set_locations(automap_location);
  
  glk_stream_set_current(glk_window_get_stream(win));
  mymap_draw();

  if(selected_room_number) {
    offset short_name_off = object_name(selected_room_number);
    glk_window_move_cursor(win, 0, 0);

    if(short_name_off)
      decodezscii(short_name_off, w_glk_put_char);
    else
      w_glk_put_string("<nameless>");
    w_glk_put_string(" (");
    g_print_number(selected_room_number);
    glk_put_char(')');
  }
  return automap_size;
}


BOOL automap_mouse_callback(BOOL is_char_event,
			    winid_t win, glui32 x, glui32 y)
{
  automap_write_loc(x, y);
  return FALSE;
}


static void automap_calc_location(loc_node *location, loc_node *last,
				  int x, int y)
{
  unsigned i;
  char symbol;
  loc_node *is_up, *is_down;

  if(!location)
    return;

  if(location->touched)
    return;
  location->touched = TRUE;

  /* Make sure unfound locations are blanked */
  if(!location->found) {
    mymap_plot(x, y, ' ', location);
    return;
  }


  /* Don't draw up/down exits if there's a normal passage leading that way */
  is_up = location->exits[DIR_UP];
  is_down = location->exits[DIR_DOWN];
  for(i = 0; i < NUM_DIRS; i++) {
    loc_node *thisdest = automap_edge_follow(location, i);
    if(thisdest && !thisdest->real)
      thisdest = location->exits[i];
    if(thisdest == is_up)
      is_up = 0;
    if(thisdest == is_down)
      is_down = 0;
  }

  symbol = ROOM_SYMBOL((x==0 && y==0), is_up, is_down, location->real);

  mymap_plot(x, y, symbol, location);

  for(i = 0; i < NUM_DIRS; i++) {
    loc_node *thisdest = automap_edge_follow(location, i);
    if(thisdest && thisdest != last) {
      int destx = x;
      int desty = y;
      automap_draw_edge(location, i, &destx, &desty);
      automap_calc_location(thisdest, location, destx, desty);
    }
  }
}


/* Returns magic cookies to identify fake locations */
static glui32 automap_get_cookie(void) {
  /* FIXME: When the glui32 wraps around Bad Things will happen if we return a
     cookie still in use.  Should reissue cookies to everyone when we wrap
     around. */
  static glui32 cookie = 0;
  return cookie++;
}


static void automap_calc_exits(loc_node *location, int depth)
{
  unsigned i, n;
  loc_node *proposed[NUM_DIRS];         /* Store proposed edges here */
  BOOL is_oneway[NUM_DIRS];
  
  /* Remove fake locations */
  for(i = 0; i < NUM_DIRS; i++) {
    loc_node *curdest = automap_edge_follow(location, i);
    if(curdest && !curdest->real)
      room_remove(curdest);
  }

  /* Default to things going the way they actually do */
  for(i = 0; i < NUM_DIRS; i++) {
    proposed[i] = location->exits[i];
    is_oneway[i] = FALSE;
  }
  
  /* Get rid of superfluous exits */
  for(i = 0; i < NUM_DIRS; i++) {
    if(proposed[i]) {
      for(n = i+1; n < NUM_DIRS; n++) {
	if(proposed[n] == proposed[i]) {
	  if(proposed[i]->exits[REVERSE_DIR(n)] == location) {
	    proposed[i] = NULL;
	    break;
	  }
	  if(proposed[i]->exits[REVERSE_DIR(i)] == location)
	    proposed[n] = NULL;
	}
      }
    }
  }

  /* Handle forced movement */
  for(i = 0; i < NUM_DIRS; i++) {
    if(proposed[i] && proposed[i] == location->exits[DIR_WAIT]) {
      if(proposed[i]->exits[REVERSE_DIR(i)] != location)
	proposed[i] = NULL;
    }
  }
  
  /* Check for one way and bent passages */
  for(i = 0; i < NUM_DIRS; i++) {
    if(proposed[i] && proposed[i]->found
       && proposed[i]->exits[REVERSE_DIR(i)] != location) {
      is_oneway[i] = TRUE;
      for(n = 0; n < NUM_DIRS; n++) {
	if(n != i && proposed[i]->exits[n] == location) {
	  loc_node *newnode = room_find_or_create(automap_get_cookie(), FALSE);
	    
	  is_oneway[i] = FALSE;
	  newnode->found = TRUE;
	    
	  automap_set_virtual_connection(proposed[i], n, newnode, FALSE);
	  proposed[i] = newnode;
	}
      }
    }
  }

  /* If it's a one way passage, but there are up/down exits connecting the two,
     ignore the passage */
  for(i = 0; i < NUM_DIRS; i++) {
    if(is_oneway[i] && proposed[i]
	 && ((location->exits[DIR_UP] == proposed[i]
	      && proposed[i]->exits[DIR_DOWN] == location)
	     || (location->exits[DIR_DOWN] == proposed[i]
		 && proposed[i]->exits[DIR_UP] == location))) {
      proposed[i] = 0;
      is_oneway[i] = FALSE;
    }
  }

  /* Create the proposed passages */
  for(i = 0; i < NUM_DIRS; i++)
    automap_set_virtual_connection(location, i, proposed[i], is_oneway[i]);
  
  /* Explore neighbors */
  if(depth) {
    for(i = 0; i < NUM_DIRS; i++)
      automap_calc_exits(location->exits[i], depth-1);
  }
}


#define INFINITY 1000000L

static void make_distant(const char *unused_key, void *r)
{
  loc_node *t = (loc_node *) r;
  t->dist = INFINITY;
}


static void automap_calc_distances(loc_node *location, glui32 distance,
				   BOOL by_walking)
{
  unsigned i;
  unsigned maxdir = by_walking ? NUM_EXITS : NUM_DIRS;
  if(location->dist < distance)
    return;
  location->dist = distance;
  for(i = 0; i < maxdir; i++) {
    loc_node *thisdest;
    if(by_walking)
      thisdest = location->exits[i];
    else
      thisdest = automap_edge_follow(location, i);

    if(thisdest)
      automap_calc_distances(thisdest, distance+1, by_walking);
  }
}


static automap_path *automap_find_path(loc_node *location, loc_node *dest,
				       BOOL by_walking)
{
  automap_path *path = NULL;
  automap_path *rev;
  automap_path newnode;
  loc_node *p;

  /* Find the distances of all nodes from dest */
  n_hash_enumerate(&rooms, make_distant);
  automap_calc_distances(dest, 0, by_walking);

  /* If dest isn't reachable, location's distance will still be infinite */
  if(location->dist == INFINITY)
    return NULL;

  /* At each step, go toward a nearer node 'till we're there */
  p = location;
  while(p != dest) {
    unsigned i;
    unsigned best_dir;
    glui32 best_dist = INFINITY;
    loc_node *best_node = NULL;
    unsigned maxdir = by_walking ? NUM_EXITS : NUM_DIRS;
    for(i = 0; i < maxdir; i++) {
      loc_node *thisdest;
      if(by_walking)
	thisdest = p->exits[i];
      else
	thisdest = automap_edge_follow(p, i);
      
      if(thisdest && thisdest->dist < best_dist) {
	best_dir = i;
	best_dist = thisdest->dist;
	best_node = thisdest;
      }
    }
    if(!best_node) {
      n_show_error(E_SYSTEM, "couldn't find path there", 0);
      return NULL;
    }
    newnode.loc = p;
    newnode.dir = best_dir;
    LEadd(path, newnode);
    p = best_node;
  }

  rev = NULL;
  while(path) {
    LEadd(rev, *path);
    LEremove(path);
  }

  return rev;
}


static void automap_find_cycles(loc_node *location, automap_path *curpath)
{
  unsigned i;
  location->touched = TRUE;
  for(i = 0; i < NUM_DIRS; i++) {
    loc_node *thisdest = automap_edge_follow(location, i);
    if(thisdest && thisdest->found) {
      automap_path newnode;
      newnode.dir = i;
      newnode.loc = location;
      LEadd(curpath, newnode);

      if(thisdest->touched) {           /* Found a cycle! */
	int cyclelength = 0;
	automap_path *p;
	cycleequation *cycle = NULL;
	cycleequation newcycle;
	for(p = curpath; p; p=p->next) {
	  int dir = p->dir;
	  newcycle.var = &(p->loc->outgoing[dir]->guess_length);
	  newcycle.min = &(p->loc->outgoing[dir]->min_length);
	  newcycle.xcoefficient = dirways[dir].deltax;
	  newcycle.ycoefficient = dirways[dir].deltay;
	  LEadd(cycle, newcycle);
	  
	  cyclelength++;
	  if(p->loc == thisdest) {      /* Found the relevant endpoint */
	    if(cyclelength <= 2)     /* Ignore two nodes going to each other */
	      LEdestroy(cycle);
	    else
	      automap_add_cycle(cycle); /* automap_add_cycle gets ownership */
	    break;
	  }
	}
	if(!p) {                        /* The cycle had already been found */
	  LEdestroy(cycle);
	}
      } else {
	automap_find_cycles(thisdest, curpath);
      }
      LEremove(curpath);
    }
  }
}


static void automap_calc_cycles(loc_node *start)
{
  automap_delete_cycles();
  automap_find_cycles(start, NULL);
  automap_cycle_elimination();
  automap_cycles_fill_values();
}


void make_untouched(const char *unused_key, void *r)
{
  loc_node *t = (loc_node *) r;
  t->touched = FALSE;
}


void automap_set_locations(int center)
{
  loc_node *r;

  r = room_find(center, TRUE);

  n_hash_enumerate(&rooms, make_untouched);
  automap_edges_mindist();
  automap_calc_cycles(r);

  n_hash_enumerate(&rooms, make_untouched);
  automap_forget_interference();
  mymap_reinit();
  automap_edges_untouch();
  automap_calc_location(r, NULL, 0, 0);

  automap_resolve_interference(r, 2);
}


static int automap_dir = NUM_EXITS;
static BOOL automap_explored = FALSE;
zword automap_location = 0;


/* Returns a direction it wants you to explore in.  Take the direction and
   call automap_unexplore, which'll take you back to the @read.
   If it returns NULL, we're finished; get player input */
const char *automap_explore(void)
{
  if(automap_explored) {
    n_show_error(E_SAVE, "tried to explore when we just did so", automap_explored);
    return NULL;
  }

  if(!loc_exp)
    return NULL;

  if(automap_dir == NUM_EXITS) {
    fast_saveundo();
    automap_location = evaluate_expression(loc_exp, stack_get_depth()).v;    
    automap_dir = 0;
  } else {
    automap_dir++;
    if(automap_dir == NUM_EXITS) {
      loc_node *r = room_find(automap_location, TRUE);
      r->found = TRUE;
      automap_calc_exits(r, 0);
      allow_saveundo = TRUE;
      allow_output = TRUE;
      return NULL;
    }    
  }

  allow_saveundo = FALSE;
  allow_output = FALSE;
  automap_explored = TRUE;

  return dirways[automap_dir].name;
}


/* Undoes the work of automap_explore - call whenever a turn is 'over' */
BOOL automap_unexplore(void)
{
  zword dest;

  if(!automap_explored || !loc_exp)
    return FALSE;
  automap_explored = FALSE;
  
  dest = evaluate_expression(loc_exp, stack_get_depth()).v;
  
  automap_set_connection(automap_location, automap_dir, dest, TRUE);
  
  fast_restoreundo();
  return TRUE;
}

#else

char *roomsymbol = NULL;

BOOL automap_unexplore(void)
{
  return FALSE;
}

#endif