Atrinik Server  4.0
pathfinder.c
Go to the documentation of this file.
1 /*************************************************************************
2  * Atrinik, a Multiplayer Online Role Playing Game *
3  * *
4  * Copyright (C) 2009-2014 Alex Tokar and Atrinik Development Team *
5  * *
6  * Fork from Crossfire (Multiplayer game for X-windows). *
7  * *
8  * This program is free software; you can redistribute it and/or modify *
9  * it under the terms of the GNU General Public License as published by *
10  * the Free Software Foundation; either version 2 of the License, or *
11  * (at your option) any later version. *
12  * *
13  * This program is distributed in the hope that it will be useful, *
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
16  * GNU General Public License for more details. *
17  * *
18  * You should have received a copy of the GNU General Public License *
19  * along with this program; if not, write to the Free Software *
20  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. *
21  * *
22  * The author can be reached at admin@atrinik.org *
23  ************************************************************************/
24 
40 #include <global.h>
41 #include <toolkit/string.h>
42 #include <arch.h>
43 #include <player.h>
44 #include <object.h>
45 #include <exit.h>
46 #include <toolkit/clioptions.h>
47 
51 #define TIME_PATHFINDING 0
52 
56 #define VISUALIZE_PATHFINDING 0
57 
61 #define PATHFINDER_QUEUE_SIZE 100
62 
66 #define PATHFINDER_NODEBUF 1000
67 
71 #define PATH_COST 1.0
72 
76 #define PATH_COST_DIAG 1.01
77 
81 #define PATH_COST_LEVEL 1000.
82 
86 static struct {
87  object *waypoint;
88  tag_t wp_count;
90 
94 static int pathfinder_queue_first = 0;
98 static int pathfinder_queue_last = 0;
99 
107 static int pathfinder_nodebuf_next = 0;
108 
113 static const double algo_modifiers[] = {
114  0, 0.5, 1.0,
115 };
116 CASSERT_ARRAY(algo_modifiers, PATH_ALGO_NUM);
117 
121 static const char *const algo_strs[] = {
122  "BFS", "A*", "Dijkstra",
123 };
124 CASSERT_ARRAY(algo_strs, PATH_ALGO_NUM);
125 
129 static path_algo_t path_algo = PATH_ALGO_ASTAR;
130 
134 static double path_greed = 1.0;
135 TOOLKIT_API(IMPORTS(clioptions), DEPENDS(logger));
136 
141 "Changes the algorithm used for pathfinding.\n\n"
142 "Available algorithms: BFS, A*, Dijkstra";
144 static bool
146  char **errmsg)
147 {
148  path_algo_t algo;
149  for (algo = 0; algo < PATH_ALGO_NUM; algo++) {
150  if (strcasecmp(algo_strs[algo], arg) == 0) {
151  break;
152  }
153  }
154 
155  if (algo == PATH_ALGO_NUM) {
156  *errmsg = estrdup("Unknown algorithm");
157  return false;
158  }
159 
160  if (path_algo == algo) {
161  *errmsg = estrdup("Algorithm unchanged");
162  return false;
163  }
164 
165  LOG(INFO, "Pathfinding algorithm changed from %s to %s",
166  algo_strs[path_algo], algo_strs[algo]);
167  path_algo = algo;
168  return true;
169 }
170 
175 "Sets the pathfinding heuristics greed modifier.";
177 static bool
179  char **errmsg)
180 {
181  double greed = atof(arg);
182  if (DBL_EQUAL(path_greed, greed)) {
183  *errmsg = estrdup("Greed modifier unchanged");
184  return false;
185  }
186 
187  LOG(INFO, "Pathfinding greed modifier changed from %f to %f",
188  path_greed, greed);
189  path_greed = greed;
190  return true;
191 }
192 
193 TOOLKIT_INIT_FUNC(pathfinder)
194 {
195  clioption_t *cli;
196  CLIOPTIONS_CREATE_ARGUMENT(cli,
197  pathfinder_algorithm,
198  "Set pathfinding algorithm");
199  clioptions_enable_changeable(cli);
200  CLIOPTIONS_CREATE_ARGUMENT(cli,
201  pathfinder_greed,
202  "Set pathfinding greed modifier");
203  clioptions_enable_changeable(cli);
204 }
205 TOOLKIT_INIT_FUNC_FINISH
206 
207 TOOLKIT_DEINIT_FUNC(pathfinder)
208 {
209 }
210 TOOLKIT_DEINIT_FUNC_FINISH
211 
220 static bool
222 {
223  HARD_ASSERT(waypoint != NULL);
224 
225  /* Queue full? */
227  (pathfinder_queue_first == 0 &&
229  return false;
230  }
231 
233  pathfinder_queue[pathfinder_queue_last].wp_count = waypoint->count;
234 
237  }
238 
239  return true;
240 }
241 
249 static object *
251 {
252  HARD_ASSERT(count != NULL);
253 
254  /* Queue empty? */
256  return NULL;
257  }
258 
260  *count = pathfinder_queue[pathfinder_queue_first].wp_count;
261 
264  }
265 
266  return waypoint;
267 }
268 
275 void path_request(object *waypoint)
276 {
277  HARD_ASSERT(waypoint != NULL);
278 
279  if (QUERY_FLAG(waypoint, FLAG_WP_PATH_REQUESTED)) {
280  return;
281  }
282 
283 #ifdef DEBUG_PATHFINDING
284  LOG(DEBUG, "enqueuing path request for >%s< -> >%s<",
285  waypoint->env->name,
286  waypoint->name);
287 #endif
288 
289  if (pathfinder_queue_enqueue(waypoint)) {
290  SET_FLAG(waypoint, FLAG_WP_PATH_REQUESTED);
291  waypoint->owner = waypoint->env;
292  waypoint->ownercount = waypoint->env->count;
293  }
294 }
295 
302 object *
304 {
305  object *waypoint;
306 
307  do {
308  tag_t count;
309  waypoint = pathfinder_queue_dequeue(&count);
310 
311  if (waypoint == NULL) {
312  return NULL;
313  }
314 
315  /* Verify the waypoint and its monster. */
316  if (!OBJECT_VALID(waypoint, count) ||
317  !OBJECT_VALID(waypoint->owner, waypoint->ownercount) ||
318  !(QUERY_FLAG(waypoint, FLAG_CURSED) ||
319  QUERY_FLAG(waypoint, FLAG_DAMNED)) ||
320  (QUERY_FLAG(waypoint, FLAG_DAMNED) &&
321  !OBJECT_VALID(waypoint->enemy, waypoint->enemy_count))) {
322  waypoint = NULL;
323  }
324  } while (waypoint == NULL);
325 
326 #ifdef DEBUG_PATHFINDING
327  LOG(DEBUG, "dequeued '%s' -> '%s'",
328  waypoint->owner->name,
329  waypoint->name);
330 #endif
331 
333  return waypoint;
334 }
335 
360  int16_t x,
361  int16_t y,
362  double cost,
363  path_node_t *start,
364  path_node_t *goal,
365  path_node_t *parent)
366 {
367  HARD_ASSERT(map != NULL);
368  HARD_ASSERT(start != NULL);
369  HARD_ASSERT(goal != NULL);
370 
371  SOFT_ASSERT_RC(!OUT_OF_MAP(map, x, y),
372  NULL,
373  "Out of map: %s %d,%d",
374  map->path,
375  x,
376  y);
377 
378  /* Out of memory? */
379  if (unlikely(pathfinder_nodebuf_next == PATHFINDER_NODEBUF)) {
380 #ifdef DEBUG_PATHFINDING
381  LOG(DEBUG, "Out of static buffer memory");
382 #endif
383  return NULL;
384  }
385 
386  rv_vector rv;
388  x,
389  y,
390  goal->map,
391  goal->x,
392  goal->y,
393  &rv,
395  return NULL;
396  }
397 
398  rv_vector rv2;
400  start->x,
401  start->y,
402  goal->map,
403  goal->x,
404  goal->y,
405  &rv2,
407  return NULL;
408  }
409 
410  int cross = abs(rv.distance_x * rv2.distance_y -
411  rv2.distance_x * rv.distance_y);
412  int straight = abs(abs(rv.distance_x) - abs(rv.distance_y));
413  int diagonal = MAX(abs(rv.distance_x), abs(rv.distance_y)) - straight;
414 
415  path_node_t *node = &pathfinder_nodebuf[pathfinder_nodebuf_next++];
416 
417  node->next = NULL;
418  node->prev = NULL;
419  node->parent = parent;
420  node->map = map;
421  node->x = x;
422  node->y = y;
423  node->cost = cost;
424  node->flags = 0;
425  node->distance_z = abs(rv.distance_z);
426  node->heuristic = straight + PATH_COST_DIAG * diagonal + cross * 0.001 +
427  abs(rv.distance_z) * PATH_COST_LEVEL;
428  node->heuristic *= path_greed;
429 
430  const double modifier = algo_modifiers[path_algo];
431  node->sum = (modifier * node->cost + (1 - modifier) * node->heuristic) /
432  MAX(modifier, 1 - modifier);
433 
434  return node;
435 }
436 
444 static void
446 {
447  HARD_ASSERT(node != NULL);
448  HARD_ASSERT(list != NULL);
449 
450  SOFT_ASSERT(*list != NULL,
451  "Removing node from an empty list: %s, %d, %d",
452  node->map->path,
453  node->x,
454  node->y);
455 
456  if (node->prev != NULL) {
457  node->prev->next = node->next;
458  } else {
459  *list = node->next;
460  }
461 
462  if (node->next != NULL) {
463  node->next->prev = node->prev;
464  }
465 
466  node->next = node->prev = NULL;
467 }
468 
476 static void
478 {
479  HARD_ASSERT(node != NULL);
480  HARD_ASSERT(list != NULL);
481 
482  if (*list != NULL) {
483  (*list)->prev = node;
484  }
485 
486  node->next = *list;
487  node->prev = NULL;
488 
489  *list = node;
490 }
491 
501 static void
503 {
504  HARD_ASSERT(node != NULL);
505  HARD_ASSERT(list != NULL);
506 
507  /* Figure out which node to insert in front of. */
508  path_node_t *insert_before = NULL;
509  path_node_t *last;
510  for (path_node_t *tmp = *list; tmp != NULL; tmp = tmp->next) {
511  last = tmp;
512 
513  if (node->sum <= tmp->sum) {
514  insert_before = tmp;
515  break;
516  }
517  }
518 
519  if (insert_before == *list) {
520  /* Insert first. */
521  path_node_insert(node, list);
522  } else if (insert_before == NULL) {
523  /* Insert last. */
524  node->next = NULL;
525  node->prev = last;
526  last->next = node;
527  } else {
528  /* Insert in middle. */
529  node->next = insert_before;
530  node->prev = insert_before->prev;
531  insert_before->prev = node;
532 
533  if (node->prev != NULL) {
534  node->prev->next = node;
535  }
536  }
537 }
538 
553 static int
554 tile_is_blocked (object *op, mapstruct *map, int x, int y)
555 {
556  int block;
557  if (op->type == PLAYER && CONTR(op)->tcl) {
558  block = 0;
559  } else {
560  block = object_blocked(op, map, x, y);
561  }
562 
563  return block;
564 }
565 
588 shstr *
590 {
591  mapstruct *last_map;
592  StringBuffer *sb;
593  path_node_t *tmp;
594  char *cp;
595  shstr *ret;
596 
597  HARD_ASSERT(path != NULL);
598 
599  last_map = NULL;
600  sb = stringbuffer_new();
601 
602  for (tmp = path; tmp != NULL; tmp = tmp->next) {
603  if (tmp->map != last_map) {
604  if (last_map != NULL) {
605  stringbuffer_append_char(sb, '\n');
606  }
607 
608  stringbuffer_append_string(sb, tmp->map->path);
609  last_map = tmp->map;
610  }
611 
612  stringbuffer_append_printf(sb, " %d,%d,%d", tmp->x, tmp->y, tmp->flags);
613  }
614 
615  cp = stringbuffer_finish(sb);
616  ret = add_string(cp);
617  efree(cp);
618 
619  return ret;
620 }
621 
652 int path_get_next(shstr *buf, int16_t *off, shstr **mappath, mapstruct **map,
653  int *x, int *y, uint32_t *flags)
654 {
655  const char *coord_start, *coord_end, *map_def;
656 
657  HARD_ASSERT(buf != NULL);
658  HARD_ASSERT(off != NULL);
659  HARD_ASSERT(mappath != NULL);
660  HARD_ASSERT(map != NULL && *map != NULL);
661  HARD_ASSERT(x != NULL);
662  HARD_ASSERT(y != NULL);
663  HARD_ASSERT(flags != NULL);
664 
665  map_def = coord_start = buf + *off;
666 
667  if (string_isempty(*mappath)) {
668  /* Scan backwards from requested offset to previous linebreak or start
669  * of string */
670  for (map_def = coord_start; map_def > buf && *(map_def - 1) != '\n';
671  map_def--) {
672  }
673  }
674 
675  /* Extract map path if any at the current position (this part is only used
676  * when we go between map tiles, or when we extract the first step). */
677  if (!isdigit(*map_def)) {
678  /* Temporary buffer for map path extraction */
679  char map_name[HUGE_BUF];
680  const char *mapend;
681 
682  /* Find the end of the map path */
683  mapend = strchr(map_def, ' ');
684 
685  if (mapend == NULL) {
686  LOG(BUG, "No delimeter after map name in path description "
687  "'%s' off %d", buf, *off);
688  return 0;
689  }
690 
691  strncpy(map_name, map_def, mapend - map_def);
692  map_name[mapend - map_def] = '\0';
693 
694  /* Store the new map path in the given shared string */
695  FREE_AND_COPY_HASH(*mappath, map_name);
696 
697  /* Adjust coordinate pointer to point after map path */
698  if (!isdigit(*coord_start)) {
699  coord_start = mapend + 1;
700  }
701  }
702 
703  /* Select the map we are aiming at. */
704  if (*mappath) {
705  /* We assume map name is already normalized. */
706  if (*map == NULL || (*map)->path != *mappath) {
707  *map = ready_map_name(*mappath, NULL, MAP_NAME_SHARED);
708  }
709  }
710 
711  if (*map == NULL) {
712  LOG(BUG, "Couldn't load map from description '%s' off %d", buf,
713  *off);
714  return 0;
715  }
716 
717  /* Get the requested coordinate pair. */
718  coord_end = coord_start + strcspn(coord_start, " \n");
719 
720  if (coord_end == coord_start || sscanf(coord_start, "%d,%d,%d", x, y,
721  flags) != 3) {
722  LOG(BUG, "Illegal coordinate pair in '%s' off %d", buf, *off);
723  return 0;
724  }
725 
726  /* Adjust coordinates to be on the safe side */
727  *map = get_map_from_coord(*map, x, y);
728 
729  if (*map == NULL) {
730  LOG(BUG, "Location (%d, %d) is out of map", *x, *y);
731  return 0;
732  }
733 
734  /* Adjust the offset */
735  *off = coord_end - buf + (*coord_end ? 1 : 0);
736 
737  return 1;
738 }
739 
760 {
761  path_node_t *tmp, *next;
762  int last_dir;
763  rv_vector v;
764 #ifdef DEBUG_PATHFINDING
765  int removed_nodes = 0, total_nodes = 2;
766 #endif
767 
768  /* Guarantee at least length 3 */
769  if (path == NULL || path->next == NULL) {
770  return path;
771  }
772 
773  next = path->next;
774 
775  get_rangevector_from_mapcoords(path->map, path->x, path->y, next->map,
776  next->x, next->y, &v, RV_EUCLIDIAN_DISTANCE);
777  last_dir = v.direction;
778 
779  for (tmp = next; tmp != NULL && tmp->next != NULL; tmp = next) {
780  next = tmp->next;
781 
782 #ifdef DEBUG_PATHFINDING
783  total_nodes++;
784 #endif
785  get_rangevector_from_mapcoords(tmp->map, tmp->x, tmp->y, next->map,
786  next->x, next->y, &v, RV_EUCLIDIAN_DISTANCE);
787 
788  if (last_dir == v.direction) {
789  path_node_remove(tmp, &path);
790 #ifdef DEBUG_PATHFINDING
791  removed_nodes++;
792 #endif
793  } else {
794  last_dir = v.direction;
795  }
796  }
797 
798 #ifdef DEBUG_PATHFINDING
799  LOG(DEBUG, "removed %d nodes of %d (%.0f%%)", removed_nodes,
800  total_nodes, (float) removed_nodes * 100.0 / (float) total_nodes);
801 #endif
802 
803  return path;
804 }
805 
812  path_visualizer_t **visualizer)
813 {
814  path_visualizer_t *node, *tmp;
815  path_visualization_t *visualization_node;
816 
817  HARD_ASSERT(visualization != NULL);
818  HARD_ASSERT(visualizer != NULL);
819 
820  DL_FOREACH_SAFE(*visualizer, node, tmp)
821  {
822  HASH_FIND(hh, *visualization, &node->map->path, sizeof(shstr *),
823  visualization_node);
824 
825  if (visualization_node == NULL) {
826  visualization_node = ecalloc(1, sizeof(*visualization_node));
827  FREE_AND_ADD_REF_HASH(visualization_node->path, node->map->path);
828  HASH_ADD(hh, *visualization, path, sizeof(shstr *),
829  visualization_node);
830  }
831 
832  DL_DELETE(*visualizer, node);
833  DL_APPEND(visualization_node->nodes, node);
834  }
835 }
836 
859 path_node_t *path_find(object *op, mapstruct *map1, int x, int y,
860  mapstruct *map2, int x2, int y2, path_visualizer_t **visualizer)
861 {
862  path_node_t *open_list, *found_path, *visited, *node, *new_node, *best;
863  path_node_t start, goal;
864  static uint32_t traversal_id = 0;
865  int i, nx, ny, is_diagonal, node_x, node_y;
866  mapstruct *m, *node_map;
867  double cost;
868  rv_vector rv;
869  uint32_t node_id;
870 #if VISUALIZE_PATHFINDING
871  path_visualizer_t *visualizer_tmp;
872 #endif
873 #if TIME_PATHFINDING
874  int searched;
875 #endif
876 
877  start.x = x;
878  start.y = y;
879  start.map = map1;
880 
881  goal.x = x2;
882  goal.y = y2;
883  goal.map = map2;
884 
885  /* Avoid overflow of traversal_id */
886  if (traversal_id == UINT32_MAX) {
887  DL_FOREACH(first_map, m) {
888  m->pathfinding_id = 0;
889  }
890 
891  traversal_id = 0;
892  }
893 
894 #if TIME_PATHFINDING
895  searched = 0;
896  TIMER_START(1);
897 #endif
898 
899  traversal_id++;
901  node_id = 0;
902  found_path = NULL;
903 
904 #if VISUALIZE_PATHFINDING
905  visualizer_tmp = NULL;
906 
907  if (visualizer == NULL) {
908  visualizer = &visualizer_tmp;
909  }
910 #endif
911 
912  /* The initial tile. */
913  open_list = best = path_node_new(map1, x, y, 0.0, &start, &goal, NULL);
914  if (open_list == NULL) {
915  return NULL;
916  }
917 
918  while (open_list != NULL && pathfinder_nodebuf_next < PATHFINDER_NODEBUF) {
919  node = open_list;
920  path_node_remove(node, &open_list);
921 
922  bool reached_goal = node->heuristic <= 1.2;
923  if (op->more != NULL && !reached_goal &&
924  node->heuristic <= (op->quick_pos >> 4) + 1) {
925  for (object *tmp = op; tmp != NULL; tmp = tmp->more) {
926  int tmp_x = node->x + tmp->arch->clone.x;
927  int tmp_y = node->y + tmp->arch->clone.y;
928  mapstruct *tmp_map = get_map_from_coord(node->map,
929  &tmp_x,
930  &tmp_y);
931  if (tmp_map == NULL) {
932  continue;
933  }
934 
935  get_rangevector_from_mapcoords(tmp_map, tmp_x, tmp_y, goal.map,
936  goal.x, goal.y, &rv, 0);
937  if (rv.distance <= 1) {
938  reached_goal = true;
939  break;
940  }
941  }
942  }
943 
944  if (reached_goal) {
945  if (visualizer != NULL) {
946  PATHFINDING_SET_CLOSED(node->map, node->x, node->y,
947  traversal_id, visualizer);
948  PATHFINDING_SET_CLOSED(goal.map, goal.x, goal.y,
949  traversal_id, visualizer);
950  }
951 
952  for ( ; node != NULL; node = node->parent) {
953  path_node_insert(node, &found_path);
954  }
955 
956  break;
957  }
958 
959  /* Close this tile. */
960  PATHFINDING_SET_CLOSED(node->map, node->x, node->y, traversal_id,
961  visualizer);
962 
963  node_map = node->map;
964  node_x = node->x;
965  node_y = node->y;
966 
967  if (GET_MAP_FLAGS(node_map, node_x, node_y) & P_IS_EXIT &&
968  op->behavior & BEHAVIOR_EXITS) {
969  object *tmp;
970 
971  for (tmp = GET_MAP_OB(node_map, node_x, node_y); tmp != NULL;
972  tmp = tmp->above) {
973  if (tmp->type == EXIT) {
974  m = exit_get_destination(tmp, &nx, &ny, true);
975 
976  /* Do not enter exits that have worse z distance than the
977  * current node. */
978  if (m != NULL && get_rangevector_from_mapcoords(m, node_x,
979  node_y, goal.map, goal.x, goal.y, &rv,
980  RV_RECURSIVE_SEARCH) && abs(rv.distance_z) <=
981  node->distance_z) {
982  node_map = m;
983  node_x = nx;
984  node_y = ny;
985 
986  /* Add exit flag to the node with the exit, to indicate
987  * that the path user needs to use an exit on that tile
988  * (possibly having to apply it, in case it's not a
989  * portal or the like). */
990  node->flags |= PATH_NODE_EXIT;
991 
992  /* Close the tile that the exit leads to. */
993  PATHFINDING_SET_CLOSED(node_map, node_x, node_y,
994  traversal_id, visualizer);
995 
996  break;
997  }
998  }
999  }
1000  }
1001 
1002  for (i = 1; i <= SIZEOFFREE1; i++) {
1003  nx = node_x + freearr_x[i];
1004  ny = node_y + freearr_y[i];
1005  is_diagonal = nx != node_x && ny != node_y;
1006 
1007  m = get_map_from_coord(node_map, &nx, &ny);
1008 
1009  if (m == NULL) {
1010  continue;
1011  }
1012 
1013  /* Skip closed tiles. */
1014  if (PATHFINDING_QUERY_CLOSED(m, nx, ny, traversal_id)) {
1015  continue;
1016  }
1017 
1018  /* Skip blocked tiles. */
1019  if (tile_is_blocked(op, m, nx, ny) != 0) {
1020  continue;
1021  }
1022 
1023  /* If the object can't use secret passages and they're a player or a
1024  * that is not chasing an enemy, and this tile is a secret passage,
1025  * skip it. */
1026  if (!(GET_MAP_FLAGS(m, nx, ny) & P_DOOR_CLOSED) &&
1027  (op->type != PLAYER || !CONTR(op)->tcl) &&
1029  (op->type == PLAYER || !OBJECT_VALID(op->enemy,
1030  op->enemy_count)) && blocks_view(m, nx, ny)) {
1031  continue;
1032  }
1033 
1034  /* Calculate the cost. */
1035  cost = node->cost + (is_diagonal ? PATH_COST_DIAG : PATH_COST);
1036  cost += GET_MAP_MOVE_FLAGS(m, nx, ny) * 0.001;
1037 
1038  if (op->behavior & BEHAVIOR_STEALTH) {
1039  cost += GET_MAP_LIGHT(m, nx, ny) * 0.001;
1040  }
1041 
1042  /* Get the visited path node on this tile, if any. */
1043  visited = PATHFINDING_NODE_GET(m, nx, ny, traversal_id);
1044 
1045  /* If we have visited this node previously, and the cost is not any
1046  * better, skip it. */
1047  if (visited != NULL && cost >= visited->cost) {
1048  continue;
1049  }
1050 
1051  if (visited != NULL) {
1052  /* Remove previously visited node from the open list. */
1053  path_node_remove(visited, &open_list);
1054 
1055  if (visited == best) {
1056  best = NULL;
1057  }
1058  } else {
1059 #if TIME_PATHFINDING
1060  searched++;
1061 #endif
1062  }
1063 
1064  new_node = path_node_new(m, nx, ny, cost, &start, &goal, node);
1065 
1066  if (new_node == NULL) {
1067  continue;
1068  }
1069 
1070  path_node_insert_priority(new_node, &open_list);
1071  PATHFINDING_NODE_SET(m, nx, ny, traversal_id, new_node, visualizer);
1072 
1073  if (best == NULL || new_node->sum < best->sum) {
1074  best = new_node;
1075  }
1076  }
1077  }
1078 
1079  if (found_path == NULL) {
1080  for (node = best; node != NULL; node = node->parent) {
1081  path_node_insert(node, &found_path);
1082  }
1083  }
1084 
1085 #if TIME_PATHFINDING
1086  TIMER_UPDATE(1);
1087  LOG(DEVEL, "Pathfinding took %f seconds (searched %d nodes)",
1088  TIMER_GET(1), searched);
1089 #endif
1090 
1091 #if VISUALIZE_PATHFINDING
1092  {
1093  char path[HUGE_BUF];
1094  FILE *fp;
1095 
1096  snprintf(path, sizeof(path), "%s/pathfinding/%u.json",
1097  settings.datapath, traversal_id);
1098  path_ensure_directories(path);
1099 
1100  fp = fopen(path, "w");
1101 
1102  if (fp == NULL) {
1103  LOG(BUG, "Could not open %s for writing.", path);
1104  } else {
1105  path_visualization_t *visualization, *curr, *tmp;
1106  path_visualizer_t *visualizer_node, *visualizer_node_tmp;
1107  StringBuffer *sb;
1108  char *cp;
1109 
1110  visualization = NULL;
1111  path_visualize(&visualization, visualizer);
1112 
1113  fprintf(fp, "{\"start\": {\"map\": \"%s\", \"x\": %d, \"y\": %d},\n"
1114  "\"goal\": {\"map\": \"%s\", \"x\": %d, \"y\": %d},\n"
1115  "\"nodes\": {\n", start.map->path, start.x, start.y,
1116  goal.map->path, goal.x, goal.y);
1117 
1118  HASH_ITER(hh, visualization, curr, tmp)
1119  {
1120  m = has_been_loaded_sh(curr->path);
1121  fprintf(fp, "\"%s\": {\"walked\": [\n", m->path);
1122 
1123  DL_FOREACH_SAFE(curr->nodes, visualizer_node,
1124  visualizer_node_tmp)
1125  {
1126  fprintf(fp, "{\"id\": %u, \"x\": %d, \"y\": %d, "
1127  "\"closed\": %s, \"exit\": %s", visualizer_node->id,
1128  visualizer_node->x, visualizer_node->y,
1129  visualizer_node->closed ? "true" : "false",
1130  GET_MAP_FLAGS(m, visualizer_node->x,
1131  visualizer_node->y) & P_IS_EXIT ? "true" : "false");
1132 
1133  if (visualizer_node->node == NULL) {
1134  fprintf(fp, ", \"cost\": NaN, \"heuristic\": NaN, "
1135  "\"sum\": NaN");
1136  } else {
1137  fprintf(fp, ", \"cost\": %f, \"heuristic\": %f, "
1138  "\"sum\": %f", visualizer_node->node->cost,
1139  visualizer_node->node->heuristic,
1140  visualizer_node->node->sum);
1141  }
1142 
1143  fprintf(fp, "}");
1144 
1145  if (visualizer_node_tmp != NULL) {
1146  fprintf(fp, ",");
1147  }
1148 
1149  fprintf(fp, "\n");
1150 
1151  DL_DELETE(curr->nodes, visualizer_node);
1152  efree(visualizer_node);
1153  }
1154 
1155  sb = stringbuffer_new();
1156 
1157  for (x = 0; x < m->width; x++) {
1158  for (y = 0; y < m->height; y++) {
1159  if (!tile_is_blocked(op, m, x, y)) {
1160  continue;
1161  }
1162 
1163  if (stringbuffer_length(sb) != 0) {
1164  stringbuffer_append_char(sb, ',');
1165  }
1166 
1167  stringbuffer_append_printf(sb, "\n{\"x\": %d, "
1168  "\"y\": %d}", x, y);
1169  }
1170  }
1171 
1172  cp = stringbuffer_finish(sb);
1173  fprintf(fp, "],\n\"walls\": [%s\n]}%s\n", cp,
1174  tmp != NULL ? "," : "");
1175  efree(cp);
1176 
1177  HASH_DEL(visualization, curr);
1178  FREE_ONLY_HASH(curr->path);
1179  efree(curr);
1180  }
1181 
1182  fprintf(fp, "},\n\"path\": [\n");
1183 
1184  for (node = found_path; node != NULL; node = node->next) {
1185  m = NULL;
1186 
1187  if (node->flags & PATH_NODE_EXIT) {
1188  object *exit;
1189 
1190  for (exit = GET_MAP_OB(node->map, node->x, node->y);
1191  exit != NULL; exit = exit->above) {
1192  if (exit->type == EXIT) {
1193  m = exit_get_destination(exit, &nx, &ny, true);
1194  }
1195  }
1196  }
1197 
1198  fprintf(fp, "{\"map\": \"%s\", \"x\": %d, \"y\": %d, "
1199  "\"flags\": %d}%s\n", node->map->path, node->x, node->y,
1200  node->flags, node->next != NULL || m != NULL ? "," :
1201  "");
1202 
1203  if (m != NULL) {
1204  fprintf(fp, "{\"map\": \"%s\", \"x\": %d, \"y\": %d}%s\n",
1205  m->path, nx, ny, node->next != NULL ? "," : "");
1206 
1207  }
1208  }
1209 
1210  fprintf(fp, "],\n\"time_taken\": ");
1211 
1212 #if TIME_PATHFINDING
1213  fprintf(fp, "%f", TIMER_GET(1));
1214 #else
1215  fprintf(fp, "NaN");
1216 #endif
1217 
1218  fprintf(fp, ",\n\"num_searched\": ");
1219 
1220 #if TIME_PATHFINDING
1221  fprintf(fp, "%d", searched);
1222 #else
1223  fprintf(fp, "NaN");
1224 #endif
1225 
1226  fprintf(fp, "\n}\n");
1227 
1228  fclose(fp);
1229 
1230  LOG(DEVEL, "Generated pathfinding visualization for '%s': %s",
1231  op->name, path);
1232  }
1233  }
1234 #endif
1235 
1236  return found_path;
1237 }
int distance_z
Z distance from this node to the goal.
Definition: pathfinder.h:65
#define FREE_AND_ADD_REF_HASH(_sv_, _nv_)
Definition: global.h:116
static void path_node_remove(path_node_t *node, path_node_t **list)
Definition: pathfinder.c:445
static double path_greed
Definition: pathfinder.c:134
int16_t x
X position.
Definition: pathfinder.h:80
#define FREE_AND_COPY_HASH(_sv_, _nv_)
Definition: global.h:100
#define EXIT
Definition: define.h:312
tag_t ownercount
Definition: object.h:219
uint8_t quick_pos
Definition: object.h:357
int direction
Definition: map.h:787
void path_request(object *waypoint)
Definition: pathfinder.c:275
mapstruct * map
Map.
Definition: pathfinder.h:79
int blocks_view(mapstruct *m, int x, int y)
Definition: map.c:507
char datapath[MAX_BUF]
Definition: global.h:343
Total number of algorithms.
Definition: pathfinder.h:50
#define FLAG_CURSED
Definition: define.h:1154
unsigned int distance
Definition: map.h:775
tag_t enemy_count
Definition: object.h:216
#define RV_NO_DISTANCE
Definition: map.h:813
path_node_t * path_find(object *op, mapstruct *map1, int x, int y, mapstruct *map2, int x2, int y2, path_visualizer_t **visualizer)
Definition: pathfinder.c:859
#define BEHAVIOR_STEALTH
Definition: object.h:608
int16_t y
Y position on the map for this node.
Definition: pathfinder.h:63
static int tile_is_blocked(object *op, mapstruct *map, int x, int y)
Definition: pathfinder.c:554
shstr * path
Definition: map.h:568
#define SIZEOFFREE1
Definition: define.h:654
mapstruct * get_map_from_coord(mapstruct *m, int *x, int *y)
Definition: map.c:1869
#define FLAG_WP_PATH_REQUESTED
Definition: pathfinder.h:150
#define RV_EUCLIDIAN_DISTANCE
Definition: map.h:805
int distance_x
Definition: map.h:778
int height
Definition: map.h:653
struct obj * above
Definition: object.h:120
int object_blocked(object *op, mapstruct *m, int x, int y)
Definition: object.c:3224
#define OUT_OF_MAP(M, X, Y)
Definition: map.h:240
#define PLAYER
Definition: define.h:122
#define BEHAVIOR_SECRET_PASSAGES
Definition: object.h:616
struct path_node * prev
Previous node in a linked list.
Definition: pathfinder.h:58
static void path_node_insert(path_node_t *node, path_node_t **list)
Definition: pathfinder.c:477
static void path_node_insert_priority(path_node_t *node, path_node_t **list)
Definition: pathfinder.c:502
#define QUERY_FLAG(xyz, p)
Definition: define.h:761
struct obj * enemy
Definition: object.h:196
static TOOLKIT_DEINIT_FUNC_FINISH bool pathfinder_queue_enqueue(object *waypoint)
Definition: pathfinder.c:221
shstr * path
Map path. Used as key for the hash table.
Definition: pathfinder.h:94
path_node_t * path_compress(path_node_t *path)
Definition: pathfinder.c:759
double cost
Cost of reaching this node (distance from origin).
Definition: pathfinder.h:67
static const double algo_modifiers[]
Definition: pathfinder.c:113
tag_t wp_count
Waypoint's ID.
Definition: pathfinder.c:88
int distance_y
Definition: map.h:781
#define FLAG_DAMNED
Definition: define.h:1158
#define P_DOOR_CLOSED
Definition: map.h:272
void path_visualize(path_visualization_t **visualization, path_visualizer_t **visualizer)
Definition: pathfinder.c:811
static bool clioptions_option_pathfinder_algorithm(const char *arg, char **errmsg)
Definition: pathfinder.c:145
#define RV_RECURSIVE_SEARCH
Definition: map.h:825
static path_node_t * path_node_new(mapstruct *map, int16_t x, int16_t y, double cost, path_node_t *start, path_node_t *goal, path_node_t *parent)
Definition: pathfinder.c:359
struct sound_ambient_match * next
Next match rule in a linked list.
Definition: sound_ambient.c:39
#define PATH_COST_LEVEL
Definition: pathfinder.c:81
static struct @13 pathfinder_queue[PATHFINDER_QUEUE_SIZE]
object * waypoint
Waypoint object.
Definition: pathfinder.c:87
static bool clioptions_option_pathfinder_greed(const char *arg, char **errmsg)
Definition: pathfinder.c:178
#define P_IS_EXIT
Definition: map.h:260
const char * name
Definition: object.h:168
#define SET_FLAG(xyz, p)
Definition: define.h:741
struct obj * env
Definition: object.h:130
static int pathfinder_nodebuf_next
Definition: pathfinder.c:107
#define PATHFINDER_QUEUE_SIZE
Definition: pathfinder.c:61
double heuristic
Estimated cost of reaching the goal from this node.
Definition: pathfinder.h:68
#define BEHAVIOR_EXITS
Definition: object.h:612
#define PATH_COST_DIAG
Definition: pathfinder.c:76
static path_node_t pathfinder_nodebuf[PATHFINDER_NODEBUF]
Definition: pathfinder.c:103
path_node_t * node
The actual node. Can be NULL.
Definition: pathfinder.h:83
TOOLKIT_INIT_FUNC(http_server)
Definition: http_server.c:85
struct settings_struct settings
Definition: init.c:55
#define MAP_NAME_SHARED
Definition: map.h:157
path_visualizer_t * nodes
Visited nodes on this map.
Definition: pathfinder.h:95
struct obj * owner
Definition: object.h:207
tag_t count
Definition: object.h:142
int path_get_next(shstr *buf, int16_t *off, shstr **mappath, mapstruct **map, int *x, int *y, uint32_t *flags)
Definition: pathfinder.c:652
int get_rangevector_from_mapcoords(mapstruct *map1, int x, int y, mapstruct *map2, int x2, int y2, rv_vector *retval, int flags)
Definition: map.c:2297
int16_t x
X position on the map for this node.
Definition: pathfinder.h:62
int distance_z
Definition: map.h:784
uint32_t id
UID of the node; can be used for insertion order sorting.
Definition: pathfinder.h:85
uint32_t pathfinding_id
Definition: map.h:600
int freearr_x[SIZEOFFREE]
Definition: object.c:84
uint8_t behavior
Definition: object.h:399
uint8_t type
Definition: object.h:360
#define CLEAR_FLAG(xyz, p)
Definition: define.h:751
double sum
Sum of ::cost and ::heuristic.
Definition: pathfinder.h:69
uint8_t flags
A combination of Path node flags.
Definition: pathfinder.h:64
TOOLKIT_INIT_FUNC_FINISH TOOLKIT_DEINIT_FUNC(http_server)
Definition: http_server.c:124
struct mapdef * map
Pointer to the map.
Definition: pathfinder.h:61
static int pathfinder_queue_last
Definition: pathfinder.c:98
static const char * clioptions_option_pathfinder_greed_desc
Definition: pathfinder.c:174
mapstruct * has_been_loaded_sh(shstr *name)
Definition: map.c:389
#define PATH_NODE_EXIT
Definition: pathfinder.h:42
#define OBJECT_VALID(_ob_, _count_)
Definition: object.h:548
static path_algo_t path_algo
Definition: pathfinder.c:129
struct path_node * parent
Node this was reached from.
Definition: pathfinder.h:59
static const char *const algo_strs[]
Definition: pathfinder.c:121
#define PATH_COST
Definition: pathfinder.c:71
#define PATHFINDER_NODEBUF
Definition: pathfinder.c:66
object * path_get_next_request(void)
Definition: pathfinder.c:303
mapstruct * ready_map_name(const char *name, mapstruct *originator, int flags)
Definition: map.c:1584
static int pathfinder_queue_first
Definition: pathfinder.c:94
Definition: map.h:536
struct path_node * next
Next node in a linked list.
Definition: pathfinder.h:57
int width
Definition: map.h:656
shstr * path_encode(path_node_t *path)
Definition: pathfinder.c:589
int16_t y
Y position.
Definition: pathfinder.h:81
path_algo
Definition: pathfinder.h:45
#define FREE_ONLY_HASH(_nv_)
Definition: global.h:143
mapstruct * exit_get_destination(object *op, int *x, int *y, bool do_load)
Definition: exit.c:383
int freearr_y[SIZEOFFREE]
Definition: object.c:99
mapstruct * first_map
Definition: main.c:59
struct obj * more
Definition: object.h:133
static object * pathfinder_queue_dequeue(tag_t *count)
Definition: pathfinder.c:250
static const char * clioptions_option_pathfinder_algorithm_desc
Definition: pathfinder.c:140
bool closed
Whether the node is closed or just visited.
Definition: pathfinder.h:86
time_t last
Last successful update.
Definition: metaserver.c:47