1 /* automap.c: main automapping code
2 Copyright (C) 1999 Evin Robertson
3 Copyright (C) 2010 Jörg Walter
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.
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.
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.
19 The author can be reached at nitfol@deja.com
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 }
48 #define DIAGONAL_CROSS 0x2573
50 #define NUM_EXITS (sizeof(dirways) / sizeof(*dirways))
51 #define REVERSE_DIR(dir) (dir ^ 1)
53 #define NUM_DIRS (NUM_EXITS - 3)
54 #define NUM_WALK (NUM_EXITS - 1)
56 #define DIR_UP (NUM_DIRS + 0)
57 #define DIR_DOWN (NUM_DIRS + 1)
58 #define DIR_WAIT (NUM_DIRS + 2)
61 char *roomsymbol = NULL;
62 glui32 uni_roomsymbol[9] = { 0x25cb, 0x25b3, 0x25bd, 0x25c7, 0x25cf, 0x25b2, 0x25bc, 0x25c6, 0x25cc };
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])
67 typedef struct edge edge;
68 typedef struct loc_node loc_node;
71 loc_node *dest[2]; /* Two endpoints of passage */
72 BOOL is_oneway; /* Oneway passages are always created dest[0]--->dest[1] */
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 */
87 typedef struct edgelist edgelist;
93 static edgelist *all_edges;
95 static edge *automap_new_edge(loc_node *src, loc_node *dest, BOOL is_oneway)
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);
110 static void automap_remove_edge(edge *e)
116 for(n = 0; n < 2; n++) {
117 loc_node *thisdest = e->dest[n];
119 for(i = 0; i < NUM_DIRS; i++) {
120 if(thisdest->outgoing[i] == e)
121 thisdest->outgoing[i] = NULL;
124 LEsearchremove(all_edges, p, t, p->node == e, n_free(p->node));
128 static void automap_edges_untouch(void)
131 for(p = all_edges; p; p=p->next) {
132 p->node->touched = FALSE;
137 static void automap_edges_mindist(void)
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;
147 static hash_table rooms;
148 static char *loc_exp;
149 static zwinid automap_win;
152 void automap_kill(void)
157 LEdestruct(all_edges, n_free(all_edges->node));
158 n_hash_free_table(&rooms, n_free);
159 z_kill_window(automap_win);
162 BOOL automap_init(int numobj, const char *location_exp)
168 for (i = 0; i < strlen(roomsymbol); i++) {
169 uni_roomsymbol[i] = (unsigned char)roomsymbol[i];
174 loc_exp = n_strdup(location_exp);
176 n_hash_construct_table(&rooms, numobj / 2);
178 automap_win = z_split_screen(wintype_TextGrid,
179 automap_split | winmethod_Fixed,
180 automap_draw_callback, automap_mouse_callback);
185 static loc_node *room_find(glui32 location, BOOL is_real)
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);
193 static loc_node *room_find_or_create(glui32 location, BOOL is_real)
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);
201 r = (loc_node *) n_malloc(sizeof(loc_node));
202 r->number = location;
206 for(n = 0; n < NUM_EXITS; n++) {
209 r->outgoing[n] = NULL;
211 n_hash_insert(key, r, &rooms);
217 static void room_remove(loc_node *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));
230 typedef struct automap_path automap_path;
231 struct automap_path {
233 loc_node *loc; /* A location */
234 int dir; /* And the direction we're going from it */
237 typedef struct interlist interlist;
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,
249 static automap_path *automap_find_path(loc_node *location, loc_node *dest,
251 static int automap_edge_oneway(loc_node *location, int dir);
252 static loc_node *automap_edge_follow(loc_node *location, int dir);
255 static interlist *interferences = NULL;
257 static void automap_forget_interference(void)
259 LEdestroy(interferences);
262 static void automap_remember_interference(loc_node *a, loc_node *b)
265 LEsearch(interferences, p, (p->a==a && p->b==b) || (p->a==b && p->b==a));
270 LEadd(interferences, newnode);
275 static int automap_find_and_count_interference(loc_node *center)
280 automap_cycles_fill_values();
281 automap_forget_interference();
283 n_hash_enumerate(&rooms, make_untouched);
284 automap_edges_untouch();
285 automap_calc_location(center, NULL, 0, 0);
288 for(i = interferences; i; i=i->next)
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)
301 int explore_max = effort > 1;
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. */
313 for(exploring = 0; exploring <= explore_max; exploring++) {
314 edge *best_edge = NULL;
315 int best_count = oldcount;
316 int smallest_new = 10000;
318 for(p = path; p; p=p->next) {
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;
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);
327 e->guess_length += 2;
328 e->min_length = e->guess_length;
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)) {
336 best_count = newcount;
337 smallest_new = e->min_length;
340 if(automap_increase_along_path(p, oldcount, center, effort-1))
344 e->min_length = old_min_length;
345 e->guess_length = old_guess_length;
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);
359 /* Returns true if all interferences have been resolved */
360 static BOOL automap_resolve_interference(loc_node *center, int effort)
362 int skip_interferences = 0;
365 while(interferences) {
366 interlist *oldinter = interferences;
372 for(i = oldinter; i; i=i->next)
375 if(skip_interferences >= oldcount)
379 for(n = 0; n < skip_interferences; n++)
382 path = automap_find_path(i->a, i->b, FALSE);
386 interferences = NULL;
388 if(!automap_increase_along_path(path, oldcount, center, effort))
389 skip_interferences++;
398 static void automap_set_virtual_connection(loc_node *location, int d,
399 loc_node *dest, BOOL is_oneway)
401 if(location->outgoing[d]) {
402 int way = automap_edge_oneway(location, d);
404 automap_remove_edge(location->outgoing[d]);
408 edge *p = automap_new_edge(location, dest, is_oneway);
410 location->outgoing[d] = p;
412 if(dest->outgoing[REVERSE_DIR(d)])
413 automap_remove_edge(dest->outgoing[REVERSE_DIR(d)]);
414 dest->outgoing[REVERSE_DIR(d)] = p;
419 static void automap_set_connection(int location, int d, int dest, BOOL is_real)
423 r = room_find_or_create(location, is_real);
424 t = room_find_or_create(dest, is_real);
433 static edge *automap_get_edge(loc_node *location, int dir)
435 return location->outgoing[dir];
439 static loc_node *automap_edge_follow(loc_node *location, int dir)
441 if(location->outgoing[dir] == NULL)
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];
449 n_show_error(E_SYSTEM, "edge isn't connected to what it should be", 0);
454 static int automap_edge_length(loc_node *location, int dir)
456 return location->outgoing[dir]->guess_length;
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)
464 if(location->outgoing[dir] == NULL)
466 if(location->outgoing[dir]->dest[0] == location)
467 return location->outgoing[dir]->is_oneway;
468 return (location->outgoing[dir]->is_oneway) << 1;
472 static BOOL automap_draw_edge(loc_node *location, int dir, int *x, int *y)
478 edge *e = automap_get_edge(location, dir);
484 deltax = dirways[dir].deltax;
485 deltay = dirways[dir].deltay;
486 len = automap_edge_length(location, dir);
487 oneway = automap_edge_oneway(location, dir);
496 mymap_plot(*x, *y, dirways[REVERSE_DIR(dir)].oneway, location);
501 for(s = 1; s < len; s++) {
502 mymap_plot(*x, *y, dirways[dir].symbol, location);
508 mymap_plot(*x, *y, dirways[dir].oneway, location);
516 static void automap_adjust_length(loc_node *location, int dir, int newlen)
518 location->outgoing[dir]->min_length = newlen;
523 static int mapheight;
525 static glui32 *mymap = NULL;
526 static loc_node **mymapnode = NULL;
528 static char mymap_read(int x, int y)
530 x += mapwidth / 2; y += mapheight / 2;
531 if(x < 0 || x >= mapwidth || y < 0 || y >= mapheight)
533 return mymap[x + y * mapheight];
537 static BOOL mymap_plot(int x, int y, glui32 symbol, loc_node *node)
541 x += mapwidth / 2; y += mapheight / 2;
542 if(x < 0 || x >= mapwidth || y < 0 || y >= mapheight)
544 dest = &mymap[x + y * mapwidth];
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))
553 if(mymapnode[x + y * mapwidth])
558 mymapnode[x + y * mapwidth] = node;
560 loc_node *interfere = mymapnode[x + y * mapwidth];
561 automap_remember_interference(node, interfere);
567 void mymap_init(int width, int height)
571 mapwidth = width * 2;
572 mapheight = height * 2;
573 max = mapwidth * mapheight;
576 mymap = (glui32 *) n_malloc(max*sizeof(*mymap));
577 mymapnode = (loc_node **) n_malloc(max * sizeof(*mymapnode));
578 for(i = 0; i < max; i++) {
585 int automap_get_height(void)
587 return mapheight / 2;
591 void mymap_reinit(void)
593 mymap_init(mapwidth/2, mapheight/2);
597 void mymap_kill(void)
606 static int xoffset, yoffset;
608 static void mymap_draw(void)
611 int firsty, firstx, lasty, lastx;
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] != ' ') {
630 height = lasty - firsty; width = lastx - firstx;
632 xoffset = firstx + (width - mapwidth/2) / 2;
633 yoffset = firsty + (height - mapheight/2) / 2;
635 if(yoffset >= mapheight/2)
636 yoffset = mapheight/2 - 1;
639 if(xoffset >= mapwidth/2)
640 xoffset = mapwidth/2 - 1;
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]);
650 static glui32 selected_room_number = 0;
652 static void automap_write_loc(int x, int y)
655 selected_room_number = 0;
656 x += xoffset; y += yoffset;
657 if(x < 0 || x >= mapwidth || y < 0 || y >= mapheight)
659 room = mymapnode[x + y * mapwidth];
660 if(!room || !room->found || !room->real)
662 selected_room_number = room->number;
666 glui32 automap_draw_callback(winid_t win, glui32 width, glui32 height)
671 mymap_init(width, height);
672 automap_set_locations(automap_location);
674 glk_stream_set_current(glk_window_get_stream(win));
677 if(selected_room_number) {
678 offset short_name_off = object_name(selected_room_number);
679 glk_window_move_cursor(win, 0, 0);
682 decodezscii(short_name_off, w_glk_put_char);
684 w_glk_put_string("<nameless>");
685 w_glk_put_string(" (");
686 g_print_number(selected_room_number);
693 BOOL automap_mouse_callback(BOOL is_char_event,
694 winid_t win, glui32 x, glui32 y)
696 automap_write_loc(x, y);
701 static void automap_calc_location(loc_node *location, loc_node *last,
706 loc_node *is_up, *is_down;
711 if(location->touched)
713 location->touched = TRUE;
715 /* Make sure unfound locations are blanked */
716 if(!location->found) {
717 mymap_plot(x, y, ' ', location);
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)
731 if(thisdest == is_down)
735 symbol = ROOM_SYMBOL((x==0 && y==0), is_up, is_down, location->real);
737 mymap_plot(x, y, symbol, location);
739 for(i = 0; i < NUM_DIRS; i++) {
740 loc_node *thisdest = automap_edge_follow(location, i);
741 if(thisdest && thisdest != last) {
744 automap_draw_edge(location, i, &destx, &desty);
745 automap_calc_location(thisdest, location, destx, desty);
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
756 static glui32 cookie = 0;
761 static void automap_calc_exits(loc_node *location, int depth)
764 loc_node *proposed[NUM_DIRS]; /* Store proposed edges here */
765 BOOL is_oneway[NUM_DIRS];
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);
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;
780 /* Get rid of superfluous exits */
781 for(i = 0; i < NUM_DIRS; 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) {
789 if(proposed[i]->exits[REVERSE_DIR(i)] == location)
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)
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) {
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);
813 is_oneway[i] = FALSE;
814 newnode->found = TRUE;
816 automap_set_virtual_connection(proposed[i], n, newnode, FALSE);
817 proposed[i] = newnode;
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))) {
832 is_oneway[i] = FALSE;
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]);
840 /* Explore neighbors */
842 for(i = 0; i < NUM_DIRS; i++)
843 automap_calc_exits(location->exits[i], depth-1);
848 #define INFINITY 1000000L
850 static void make_distant(const char *unused_key, void *r)
852 loc_node *t = (loc_node *) r;
857 static void automap_calc_distances(loc_node *location, glui32 distance,
861 unsigned maxdir = by_walking ? NUM_EXITS : NUM_DIRS;
862 if(location->dist < distance)
864 location->dist = distance;
865 for(i = 0; i < maxdir; i++) {
868 thisdest = location->exits[i];
870 thisdest = automap_edge_follow(location, i);
873 automap_calc_distances(thisdest, distance+1, by_walking);
878 static automap_path *automap_find_path(loc_node *location, loc_node *dest,
881 automap_path *path = NULL;
883 automap_path newnode;
886 /* Find the distances of all nodes from dest */
887 n_hash_enumerate(&rooms, make_distant);
888 automap_calc_distances(dest, 0, by_walking);
890 /* If dest isn't reachable, location's distance will still be infinite */
891 if(location->dist == INFINITY)
894 /* At each step, go toward a nearer node 'till we're there */
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++) {
905 thisdest = p->exits[i];
907 thisdest = automap_edge_follow(p, i);
909 if(thisdest && thisdest->dist < best_dist) {
911 best_dist = thisdest->dist;
912 best_node = thisdest;
916 n_show_error(E_SYSTEM, "couldn't find path there", 0);
920 newnode.dir = best_dir;
921 LEadd(path, newnode);
935 static void automap_find_cycles(loc_node *location, automap_path *curpath)
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;
944 newnode.loc = location;
945 LEadd(curpath, newnode);
947 if(thisdest->touched) { /* Found a cycle! */
950 cycleequation *cycle = NULL;
951 cycleequation newcycle;
952 for(p = curpath; p; p=p->next) {
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);
961 if(p->loc == thisdest) { /* Found the relevant endpoint */
962 if(cyclelength <= 2) /* Ignore two nodes going to each other */
965 automap_add_cycle(cycle); /* automap_add_cycle gets ownership */
969 if(!p) { /* The cycle had already been found */
973 automap_find_cycles(thisdest, curpath);
981 static void automap_calc_cycles(loc_node *start)
983 automap_delete_cycles();
984 automap_find_cycles(start, NULL);
985 automap_cycle_elimination();
986 automap_cycles_fill_values();
990 void make_untouched(const char *unused_key, void *r)
992 loc_node *t = (loc_node *) r;
997 void automap_set_locations(int center)
1001 r = room_find(center, TRUE);
1003 n_hash_enumerate(&rooms, make_untouched);
1004 automap_edges_mindist();
1005 automap_calc_cycles(r);
1007 n_hash_enumerate(&rooms, make_untouched);
1008 automap_forget_interference();
1010 automap_edges_untouch();
1011 automap_calc_location(r, NULL, 0, 0);
1013 automap_resolve_interference(r, 2);
1017 static int automap_dir = NUM_EXITS;
1018 static BOOL automap_explored = FALSE;
1019 zword automap_location = 0;
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)
1027 if(automap_explored) {
1028 n_show_error(E_SAVE, "tried to explore when we just did so", automap_explored);
1035 if(automap_dir == NUM_EXITS) {
1037 automap_location = evaluate_expression(loc_exp, stack_get_depth()).v;
1041 if(automap_dir == NUM_EXITS) {
1042 loc_node *r = room_find(automap_location, TRUE);
1044 automap_calc_exits(r, 0);
1045 allow_saveundo = TRUE;
1046 allow_output = TRUE;
1051 allow_saveundo = FALSE;
1052 allow_output = FALSE;
1053 automap_explored = TRUE;
1055 return dirways[automap_dir].name;
1059 /* Undoes the work of automap_explore - call whenever a turn is 'over' */
1060 BOOL automap_unexplore(void)
1064 if(!automap_explored || !loc_exp)
1066 automap_explored = FALSE;
1068 dest = evaluate_expression(loc_exp, stack_get_depth()).v;
1070 automap_set_connection(automap_location, automap_dir, dest, TRUE);
1078 char *roomsymbol = NULL;
1080 BOOL automap_unexplore(void)