1 /* automap.c: main automapping code
2 Copyright (C) 1999 Evin Robertson
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.
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.
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.
18 The author can be reached at nitfol@deja.com
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' },
42 { "down", 0, 0, 0, 0 },
43 { "wait", 0, 0, 0, 0 }
46 #define NUM_EXITS (sizeof(dirways) / sizeof(*dirways))
47 #define REVERSE_DIR(dir) (dir ^ 1)
49 #define NUM_DIRS (NUM_EXITS - 3)
50 #define NUM_WALK (NUM_EXITS - 1)
52 #define DIR_UP (NUM_DIRS + 0)
53 #define DIR_DOWN (NUM_DIRS + 1)
54 #define DIR_WAIT (NUM_DIRS + 2)
56 char *roomsymbol = NULL;
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])
61 typedef struct edge edge;
62 typedef struct loc_node loc_node;
65 loc_node *dest[2]; /* Two endpoints of passage */
66 BOOL is_oneway; /* Oneway passages are always created dest[0]--->dest[1] */
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 */
81 typedef struct edgelist edgelist;
87 static edgelist *all_edges;
89 static edge *automap_new_edge(loc_node *src, loc_node *dest, BOOL is_oneway)
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);
104 static void automap_remove_edge(edge *e)
110 for(n = 0; n < 2; n++) {
111 loc_node *thisdest = e->dest[n];
113 for(i = 0; i < NUM_DIRS; i++) {
114 if(thisdest->outgoing[i] == e)
115 thisdest->outgoing[i] = NULL;
118 LEsearchremove(all_edges, p, t, p->node == e, n_free(p->node));
122 static void automap_edges_untouch(void)
125 for(p = all_edges; p; p=p->next) {
126 p->node->touched = FALSE;
131 static void automap_edges_mindist(void)
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;
141 static hash_table rooms;
142 static char *loc_exp;
143 static zwinid automap_win;
146 void automap_kill(void)
151 LEdestruct(all_edges, n_free(all_edges->node));
152 n_hash_free_table(&rooms, n_free);
153 z_kill_window(automap_win);
157 BOOL automap_init(int numobj, const char *location_exp)
162 roomsymbol = n_strdup("*udb@UDB+");
165 loc_exp = n_strdup(location_exp);
167 n_hash_construct_table(&rooms, numobj / 2);
169 automap_win = z_split_screen(wintype_TextGrid,
170 automap_split | winmethod_Fixed,
171 automap_draw_callback, automap_mouse_callback);
176 static loc_node *room_find(glui32 location, BOOL is_real)
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);
184 static loc_node *room_find_or_create(glui32 location, BOOL is_real)
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);
192 r = (loc_node *) n_malloc(sizeof(loc_node));
193 r->number = location;
197 for(n = 0; n < NUM_EXITS; n++) {
200 r->outgoing[n] = NULL;
202 n_hash_insert(key, r, &rooms);
208 static void room_remove(loc_node *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));
221 typedef struct automap_path automap_path;
222 struct automap_path {
224 loc_node *loc; /* A location */
225 int dir; /* And the direction we're going from it */
228 typedef struct interlist interlist;
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,
240 static automap_path *automap_find_path(loc_node *location, loc_node *dest,
242 static int automap_edge_oneway(loc_node *location, int dir);
243 static loc_node *automap_edge_follow(loc_node *location, int dir);
246 static interlist *interferences = NULL;
248 static void automap_forget_interference(void)
250 LEdestroy(interferences);
253 static void automap_remember_interference(loc_node *a, loc_node *b)
256 LEsearch(interferences, p, (p->a==a && p->b==b) || (p->a==b && p->b==a));
261 LEadd(interferences, newnode);
266 static int automap_find_and_count_interference(loc_node *center)
271 automap_cycles_fill_values();
272 automap_forget_interference();
274 n_hash_enumerate(&rooms, make_untouched);
275 automap_edges_untouch();
276 automap_calc_location(center, NULL, 0, 0);
279 for(i = interferences; i; i=i->next)
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)
292 int explore_max = effort > 1;
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. */
304 for(exploring = 0; exploring <= explore_max; exploring++) {
305 edge *best_edge = NULL;
306 int best_count = oldcount;
307 int smallest_new = 10000;
309 for(p = path; p; p=p->next) {
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;
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);
318 e->guess_length += 2;
319 e->min_length = e->guess_length;
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)) {
327 best_count = newcount;
328 smallest_new = e->min_length;
331 if(automap_increase_along_path(p, oldcount, center, effort-1))
335 e->min_length = old_min_length;
336 e->guess_length = old_guess_length;
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);
350 /* Returns true if all interferences have been resolved */
351 static BOOL automap_resolve_interference(loc_node *center, int effort)
353 int skip_interferences = 0;
356 while(interferences) {
357 interlist *oldinter = interferences;
363 for(i = oldinter; i; i=i->next)
366 if(skip_interferences >= oldcount)
370 for(n = 0; n < skip_interferences; n++)
373 path = automap_find_path(i->a, i->b, FALSE);
377 interferences = NULL;
379 if(!automap_increase_along_path(path, oldcount, center, effort))
380 skip_interferences++;
389 static void automap_set_virtual_connection(loc_node *location, int d,
390 loc_node *dest, BOOL is_oneway)
392 if(location->outgoing[d]) {
393 int way = automap_edge_oneway(location, d);
395 automap_remove_edge(location->outgoing[d]);
399 edge *p = automap_new_edge(location, dest, is_oneway);
401 location->outgoing[d] = p;
403 if(dest->outgoing[REVERSE_DIR(d)])
404 automap_remove_edge(dest->outgoing[REVERSE_DIR(d)]);
405 dest->outgoing[REVERSE_DIR(d)] = p;
410 static void automap_set_connection(int location, int d, int dest, BOOL is_real)
414 r = room_find_or_create(location, is_real);
415 t = room_find_or_create(dest, is_real);
424 static edge *automap_get_edge(loc_node *location, int dir)
426 return location->outgoing[dir];
430 static loc_node *automap_edge_follow(loc_node *location, int dir)
432 if(location->outgoing[dir] == NULL)
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];
440 n_show_error(E_SYSTEM, "edge isn't connected to what it should be", 0);
445 static int automap_edge_length(loc_node *location, int dir)
447 return location->outgoing[dir]->guess_length;
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)
455 if(location->outgoing[dir] == NULL)
457 if(location->outgoing[dir]->dest[0] == location)
458 return location->outgoing[dir]->is_oneway;
459 return (location->outgoing[dir]->is_oneway) << 1;
463 static BOOL automap_draw_edge(loc_node *location, int dir, int *x, int *y)
469 edge *e = automap_get_edge(location, dir);
475 deltax = dirways[dir].deltax;
476 deltay = dirways[dir].deltay;
477 len = automap_edge_length(location, dir);
478 oneway = automap_edge_oneway(location, dir);
487 mymap_plot(*x, *y, dirways[REVERSE_DIR(dir)].oneway, location);
492 for(s = 1; s < len; s++) {
493 mymap_plot(*x, *y, dirways[dir].symbol, location);
499 mymap_plot(*x, *y, dirways[dir].oneway, location);
507 static void automap_adjust_length(loc_node *location, int dir, int newlen)
509 location->outgoing[dir]->min_length = newlen;
514 static int mapheight;
516 static char *mymap = NULL;
517 static loc_node **mymapnode = NULL;
519 static char mymap_read(int x, int y)
521 x += mapwidth / 2; y += mapheight / 2;
522 if(x < 0 || x >= mapwidth || y < 0 || y >= mapheight)
524 return mymap[x + y * mapheight];
528 static BOOL mymap_plot(int x, int y, char symbol, loc_node *node)
532 x += mapwidth / 2; y += mapheight / 2;
533 if(x < 0 || x >= mapwidth || y < 0 || y >= mapheight)
535 dest = &mymap[x + y * mapwidth];
537 if((*dest=='/' && symbol=='\\') || (*dest=='\\' && symbol=='/'))
539 else if((*dest=='-' && symbol=='|') || (*dest=='|' && symbol=='-'))
544 if(mymapnode[x + y * mapwidth])
549 mymapnode[x + y * mapwidth] = node;
551 loc_node *interfere = mymapnode[x + y * mapwidth];
552 automap_remember_interference(node, interfere);
558 void mymap_init(int width, int height)
562 mapwidth = width * 2;
563 mapheight = height * 2;
564 max = mapwidth * mapheight;
567 mymap = (char *) n_malloc(max);
568 mymapnode = (loc_node **) n_malloc(max * sizeof(*mymapnode));
569 for(i = 0; i < max; i++) {
576 int automap_get_height(void)
578 return mapheight / 2;
582 void mymap_reinit(void)
584 mymap_init(mapwidth/2, mapheight/2);
588 void mymap_kill(void)
597 static int xoffset, yoffset;
599 static void mymap_draw(void)
602 int firsty, firstx, lasty, lastx;
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] != ' ') {
621 height = lasty - firsty; width = lastx - firstx;
623 xoffset = firstx + (width - mapwidth/2) / 2;
624 yoffset = firsty + (height - mapheight/2) / 2;
626 if(yoffset >= mapheight/2)
627 yoffset = mapheight/2 - 1;
630 if(xoffset >= mapwidth/2)
631 xoffset = mapwidth/2 - 1;
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]);
641 static glui32 selected_room_number = 0;
643 static void automap_write_loc(int x, int y)
646 selected_room_number = 0;
647 x += xoffset; y += yoffset;
648 if(x < 0 || x >= mapwidth || y < 0 || y >= mapheight)
650 room = mymapnode[x + y * mapwidth];
651 if(!room || !room->found || !room->real)
653 selected_room_number = room->number;
657 glui32 automap_draw_callback(winid_t win, glui32 width, glui32 height)
662 mymap_init(width, height);
663 automap_set_locations(automap_location);
665 glk_stream_set_current(glk_window_get_stream(win));
668 if(selected_room_number) {
669 offset short_name_off = object_name(selected_room_number);
670 glk_window_move_cursor(win, 0, 0);
673 decodezscii(short_name_off, w_glk_put_char);
675 w_glk_put_string("<nameless>");
676 w_glk_put_string(" (");
677 g_print_number(selected_room_number);
684 BOOL automap_mouse_callback(BOOL is_char_event,
685 winid_t win, glui32 x, glui32 y)
687 automap_write_loc(x, y);
692 static void automap_calc_location(loc_node *location, loc_node *last,
697 loc_node *is_up, *is_down;
702 if(location->touched)
704 location->touched = TRUE;
706 /* Make sure unfound locations are blanked */
707 if(!location->found) {
708 mymap_plot(x, y, ' ', location);
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)
722 if(thisdest == is_down)
726 symbol = ROOM_SYMBOL((x==0 && y==0), is_up, is_down, location->real);
728 mymap_plot(x, y, symbol, location);
730 for(i = 0; i < NUM_DIRS; i++) {
731 loc_node *thisdest = automap_edge_follow(location, i);
732 if(thisdest && thisdest != last) {
735 automap_draw_edge(location, i, &destx, &desty);
736 automap_calc_location(thisdest, location, destx, desty);
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
747 static glui32 cookie = 0;
752 static void automap_calc_exits(loc_node *location, int depth)
755 loc_node *proposed[NUM_DIRS]; /* Store proposed edges here */
756 BOOL is_oneway[NUM_DIRS];
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);
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;
771 /* Get rid of superfluous exits */
772 for(i = 0; i < NUM_DIRS; 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) {
780 if(proposed[i]->exits[REVERSE_DIR(i)] == location)
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)
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) {
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);
804 is_oneway[i] = FALSE;
805 newnode->found = TRUE;
807 automap_set_virtual_connection(proposed[i], n, newnode, FALSE);
808 proposed[i] = newnode;
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))) {
823 is_oneway[i] = FALSE;
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]);
831 /* Explore neighbors */
833 for(i = 0; i < NUM_DIRS; i++)
834 automap_calc_exits(location->exits[i], depth-1);
839 #define INFINITY 1000000L
841 static void make_distant(const char *unused_key, void *r)
843 loc_node *t = (loc_node *) r;
848 static void automap_calc_distances(loc_node *location, glui32 distance,
852 unsigned maxdir = by_walking ? NUM_EXITS : NUM_DIRS;
853 if(location->dist < distance)
855 location->dist = distance;
856 for(i = 0; i < maxdir; i++) {
859 thisdest = location->exits[i];
861 thisdest = automap_edge_follow(location, i);
864 automap_calc_distances(thisdest, distance+1, by_walking);
869 static automap_path *automap_find_path(loc_node *location, loc_node *dest,
872 automap_path *path = NULL;
874 automap_path newnode;
877 /* Find the distances of all nodes from dest */
878 n_hash_enumerate(&rooms, make_distant);
879 automap_calc_distances(dest, 0, by_walking);
881 /* If dest isn't reachable, location's distance will still be infinite */
882 if(location->dist == INFINITY)
885 /* At each step, go toward a nearer node 'till we're there */
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++) {
896 thisdest = p->exits[i];
898 thisdest = automap_edge_follow(p, i);
900 if(thisdest && thisdest->dist < best_dist) {
902 best_dist = thisdest->dist;
903 best_node = thisdest;
907 n_show_error(E_SYSTEM, "couldn't find path there", 0);
911 newnode.dir = best_dir;
912 LEadd(path, newnode);
926 static void automap_find_cycles(loc_node *location, automap_path *curpath)
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;
935 newnode.loc = location;
936 LEadd(curpath, newnode);
938 if(thisdest->touched) { /* Found a cycle! */
941 cycleequation *cycle = NULL;
942 cycleequation newcycle;
943 for(p = curpath; p; p=p->next) {
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);
952 if(p->loc == thisdest) { /* Found the relevant endpoint */
953 if(cyclelength <= 2) /* Ignore two nodes going to each other */
956 automap_add_cycle(cycle); /* automap_add_cycle gets ownership */
960 if(!p) { /* The cycle had already been found */
964 automap_find_cycles(thisdest, curpath);
972 static void automap_calc_cycles(loc_node *start)
974 automap_delete_cycles();
975 automap_find_cycles(start, NULL);
976 automap_cycle_elimination();
977 automap_cycles_fill_values();
981 void make_untouched(const char *unused_key, void *r)
983 loc_node *t = (loc_node *) r;
988 void automap_set_locations(int center)
992 r = room_find(center, TRUE);
994 n_hash_enumerate(&rooms, make_untouched);
995 automap_edges_mindist();
996 automap_calc_cycles(r);
998 n_hash_enumerate(&rooms, make_untouched);
999 automap_forget_interference();
1001 automap_edges_untouch();
1002 automap_calc_location(r, NULL, 0, 0);
1004 automap_resolve_interference(r, 2);
1008 static int automap_dir = NUM_EXITS;
1009 static BOOL automap_explored = FALSE;
1010 zword automap_location = 0;
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)
1018 if(automap_explored) {
1019 n_show_error(E_SAVE, "tried to explore when we just did so", automap_explored);
1026 if(automap_dir == NUM_EXITS) {
1028 automap_location = evaluate_expression(loc_exp, stack_get_depth()).v;
1032 if(automap_dir == NUM_EXITS) {
1033 loc_node *r = room_find(automap_location, TRUE);
1035 automap_calc_exits(r, 0);
1036 allow_saveundo = TRUE;
1037 allow_output = TRUE;
1042 allow_saveundo = FALSE;
1043 allow_output = FALSE;
1044 automap_explored = TRUE;
1046 return dirways[automap_dir].name;
1050 /* Undoes the work of automap_explore - call whenever a turn is 'over' */
1051 BOOL automap_unexplore(void)
1055 if(!automap_explored || !loc_exp)
1057 automap_explored = FALSE;
1059 dest = evaluate_expression(loc_exp, stack_get_depth()).v;
1061 automap_set_connection(automap_location, automap_dir, dest, TRUE);
1069 char *roomsymbol = NULL;
1071 BOOL automap_unexplore(void)