Atrinik Server  4.0
pathfinder.h
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 
30 #ifndef PATHFINDER_H
31 #define PATHFINDER_H
32 
33 #include <toolkit/toolkit.h>
34 
42 #define PATH_NODE_EXIT 0x01
43 
45 typedef enum path_algo {
49 
51 } path_algo_t;
52 
56 typedef struct path_node {
57  struct path_node *next;
58  struct path_node *prev;
59  struct path_node *parent;
60 
61  struct mapdef *map;
62  int16_t x;
63  int16_t y;
64  uint8_t flags;
65  int distance_z;
66 
67  double cost;
68  double heuristic;
69  double sum;
70 } path_node_t;
71 
75 typedef struct path_visualizer {
78 
80  int16_t x;
81  int16_t y;
82 
84 
85  uint32_t id;
86  bool closed;
88 
93 typedef struct path_visualization {
94  shstr *path;
96  UT_hash_handle hh;
98 
99 #define PATHFINDING_CHECK_ID(m, id) \
100  if ((m)->pathfinding_id != (id)) { \
101  (m)->pathfinding_id = (id); \
102  memset((m)->bitmap, 0, ((MAP_WIDTH(m) + 31) / 32) * MAP_HEIGHT(m) * \
103  sizeof(*(m)->bitmap)); \
104  memset((m)->path_nodes, 0, MAP_WIDTH(m) * MAP_HEIGHT(m) * \
105  sizeof(*(m)->path_nodes)); \
106  }
107 
108 #define PATHFINDING_VISUALIZER_APPEND(visualizer, _m, _x, _y, _closed, _node) \
109  if (visualizer != NULL) { \
110  path_visualizer_t *__tmp; \
111  \
112  __tmp = ecalloc(1, sizeof(*__tmp)); \
113  __tmp->map = (_m); \
114  __tmp->x = (_x); \
115  __tmp->y = (_y); \
116  __tmp->closed = (_closed); \
117  __tmp->node = (_node); \
118  __tmp->id = node_id++; \
119  DL_APPEND(*visualizer, __tmp); \
120  }
121 
122 #define PATHFINDING_SET_CLOSED(m, x, y, id, visualizer) \
123  { \
124  PATHFINDING_CHECK_ID(m, id); \
125  PATHFINDING_VISUALIZER_APPEND(visualizer, m, x, y, true, NULL); \
126  (m)->bitmap[(x) / 32 + ((MAP_WIDTH(m) + 31) / 32) * (y)] |= \
127  (1U << ((x) % 32)); \
128  }
129 
130 #define PATHFINDING_QUERY_CLOSED(m, x, y, id) \
131  ((m)->pathfinding_id == (id) && ((m)->bitmap[(x) / 32 + \
132  ((MAP_WIDTH(m) + 31) / 32) * (y)] & (1U << ((x) % 32))))
133 
134 #define PATHFINDING_NODE_SET(m, x, y, id, node, visualizer) \
135  { \
136  PATHFINDING_CHECK_ID(m, id); \
137  PATHFINDING_VISUALIZER_APPEND(visualizer, m, x, y, false, node); \
138  (m)->path_nodes[(x) + MAP_WIDTH(m) * (y)] = node; \
139  }
140 
141 #define PATHFINDING_NODE_GET(m, x, y, id) \
142  ((m)->pathfinding_id != (id) ? NULL : (m)->path_nodes[(x) + \
143  MAP_WIDTH(m) * (y)])
144 
150 #define FLAG_WP_PATH_REQUESTED FLAG_PARALYZED
151 
152 /* Uncomment this to enable some verbose pathfinding debug messages */
153 /* #define DEBUG_PATHFINDING */
154 
158 #define LEFTOVER_CPU_FOR_PATHFINDING
159 
160 /* Prototypes */
161 
162 TOOLKIT_FUNCS_DECLARE(pathfinder);
163 
164 #endif
int distance_z
Z distance from this node to the goal.
Definition: pathfinder.h:65
int16_t x
X position.
Definition: pathfinder.h:80
struct path_visualizer * next
Next 'node'.
Definition: pathfinder.h:76
mapstruct * map
Map.
Definition: pathfinder.h:79
Total number of algorithms.
Definition: pathfinder.h:50
struct path_visualizer path_visualizer_t
int16_t y
Y position on the map for this node.
Definition: pathfinder.h:63
struct path_node * prev
Previous node in a linked list.
Definition: pathfinder.h:58
struct path_visualizer * prev
Previous 'node'.
Definition: pathfinder.h:77
shstr * path
Map path. Used as key for the hash table.
Definition: pathfinder.h:94
double cost
Cost of reaching this node (distance from origin).
Definition: pathfinder.h:67
double heuristic
Estimated cost of reaching the goal from this node.
Definition: pathfinder.h:68
path_node_t * node
The actual node. Can be NULL.
Definition: pathfinder.h:83
struct path_node path_node_t
path_visualizer_t * nodes
Visited nodes on this map.
Definition: pathfinder.h:95
int16_t x
X position on the map for this node.
Definition: pathfinder.h:62
uint32_t id
UID of the node; can be used for insertion order sorting.
Definition: pathfinder.h:85
double sum
Sum of ::cost and ::heuristic.
Definition: pathfinder.h:69
uint8_t flags
A combination of Path node flags.
Definition: pathfinder.h:64
struct mapdef * map
Pointer to the map.
Definition: pathfinder.h:61
struct path_node * parent
Node this was reached from.
Definition: pathfinder.h:59
Definition: map.h:536
struct path_node * next
Next node in a linked list.
Definition: pathfinder.h:57
int16_t y
Y position.
Definition: pathfinder.h:81
UT_hash_handle hh
Hash handle.
Definition: pathfinder.h:96
path_algo
Definition: pathfinder.h:45
struct path_visualization path_visualization_t
Dijkstra.
Definition: pathfinder.h:48
bool closed
Whether the node is closed or just visited.
Definition: pathfinder.h:86