1 #include "routing_path.h"
2
3 #include "core/calc.h"
4 #include "core/random.h"
5 #include "map/grid.h"
6 #include "map/random.h"
7 #include "map/routing.h"
8
9 #define MAX_PATH 500
10
11 static int direction_path[MAX_PATH];
12
adjust_tile_in_direction(int direction,int * x,int * y,int * grid_offset)13 static void adjust_tile_in_direction(int direction, int *x, int *y, int *grid_offset)
14 {
15 switch (direction) {
16 case DIR_0_TOP:
17 --*y;
18 break;
19 case DIR_1_TOP_RIGHT:
20 ++*x;
21 --*y;
22 break;
23 case DIR_2_RIGHT:
24 ++*x;
25 break;
26 case DIR_3_BOTTOM_RIGHT:
27 ++*x;
28 ++*y;
29 break;
30 case DIR_4_BOTTOM:
31 ++*y;
32 break;
33 case DIR_5_BOTTOM_LEFT:
34 --*x;
35 ++*y;
36 break;
37 case DIR_6_LEFT:
38 --*x;
39 break;
40 case DIR_7_TOP_LEFT:
41 --*x;
42 --*y;
43 break;
44 }
45 *grid_offset += map_grid_direction_delta(direction);
46 }
47
map_routing_get_path(uint8_t * path,int src_x,int src_y,int dst_x,int dst_y,int num_directions)48 int map_routing_get_path(uint8_t *path, int src_x, int src_y, int dst_x, int dst_y, int num_directions)
49 {
50 int dst_grid_offset = map_grid_offset(dst_x, dst_y);
51 int distance = map_routing_distance(dst_grid_offset);
52 if (distance <= 0 || distance >= 998) {
53 return 0;
54 }
55
56 int num_tiles = 0;
57 int last_direction = -1;
58 int x = dst_x;
59 int y = dst_y;
60 int grid_offset = dst_grid_offset;
61 int step = num_directions == 8 ? 1 : 2;
62
63 while (distance > 1) {
64 distance = map_routing_distance(grid_offset);
65 int direction = -1;
66 int general_direction = calc_general_direction(x, y, src_x, src_y);
67 for (int d = 0; d < 8; d += step) {
68 if (d != last_direction) {
69 int next_offset = grid_offset + map_grid_direction_delta(d);
70 int next_distance = map_routing_distance(next_offset);
71 if (next_distance) {
72 if (next_distance < distance) {
73 distance = next_distance;
74 direction = d;
75 } else if (next_distance == distance && (d == general_direction || direction == -1)) {
76 distance = next_distance;
77 direction = d;
78 }
79 }
80 }
81 }
82 if (direction == -1) {
83 return 0;
84 }
85 adjust_tile_in_direction(direction, &x, &y, &grid_offset);
86 int forward_direction = (direction + 4) % 8;
87 direction_path[num_tiles++] = forward_direction;
88 last_direction = forward_direction;
89 if (num_tiles >= MAX_PATH) {
90 return 0;
91 }
92 }
93 for (int i = 0; i < num_tiles; i++) {
94 path[i] = direction_path[num_tiles - i - 1];
95 }
96 return num_tiles;
97 }
98
map_routing_get_closest_tile_within_range(int src_x,int src_y,int dst_x,int dst_y,int num_directions,int range,int * out_x,int * out_y)99 int map_routing_get_closest_tile_within_range(
100 int src_x, int src_y, int dst_x, int dst_y, int num_directions, int range, int *out_x, int *out_y)
101 {
102 int dst_grid_offset = map_grid_offset(dst_x, dst_y);
103 int distance = map_routing_distance(dst_grid_offset);
104 if (distance <= 0 || distance >= 998) {
105 return 0;
106 }
107
108 int num_tiles = 0;
109 int last_direction = -1;
110 int x = dst_x;
111 int y = dst_y;
112 int grid_offset = dst_grid_offset;
113 int step = num_directions == 8 ? 1 : 2;
114
115 while (distance > 1) {
116 distance = map_routing_distance(grid_offset);
117 *out_x = x;
118 *out_y = y;
119 if (distance <= range) {
120 return 1;
121 }
122 int direction = -1;
123 int general_direction = calc_general_direction(x, y, src_x, src_y);
124 for (int d = 0; d < 8; d += step) {
125 if (d != last_direction) {
126 int next_offset = grid_offset + map_grid_direction_delta(d);
127 int next_distance = map_routing_distance(next_offset);
128 if (next_distance) {
129 if (next_distance < distance) {
130 distance = next_distance;
131 direction = d;
132 } else if (next_distance == distance && (d == general_direction || direction == -1)) {
133 distance = next_distance;
134 direction = d;
135 }
136 }
137 }
138 }
139 if (direction == -1) {
140 return 0;
141 }
142 adjust_tile_in_direction(direction, &x, &y, &grid_offset);
143 int forward_direction = (direction + 4) % 8;
144 direction_path[num_tiles++] = forward_direction;
145 last_direction = forward_direction;
146 if (num_tiles >= MAX_PATH) {
147 return 0;
148 }
149 }
150 return 0;
151 }
152
map_routing_get_path_on_water(uint8_t * path,int dst_x,int dst_y,int is_flotsam)153 int map_routing_get_path_on_water(uint8_t *path, int dst_x, int dst_y, int is_flotsam)
154 {
155 int rand = random_byte() & 3;
156 int dst_grid_offset = map_grid_offset(dst_x, dst_y);
157 int distance = map_routing_distance(dst_grid_offset);
158 if (distance <= 0 || distance >= 998) {
159 return 0;
160 }
161
162 int num_tiles = 0;
163 int last_direction = -1;
164 int x = dst_x;
165 int y = dst_y;
166 int grid_offset = dst_grid_offset;
167 while (distance > 1) {
168 int current_rand = rand;
169 distance = map_routing_distance(grid_offset);
170 if (is_flotsam) {
171 current_rand = map_random_get(grid_offset) & 3;
172 }
173 int direction = -1;
174 for (int d = 0; d < 8; d++) {
175 if (d != last_direction) {
176 int next_offset = grid_offset + map_grid_direction_delta(d);
177 int next_distance = map_routing_distance(next_offset);
178 if (next_distance) {
179 if (next_distance < distance) {
180 distance = next_distance;
181 direction = d;
182 } else if (next_distance == distance && rand == current_rand) {
183 // allow flotsam to wander
184 distance = next_distance;
185 direction = d;
186 }
187 }
188 }
189 }
190 if (direction == -1) {
191 return 0;
192 }
193 adjust_tile_in_direction(direction, &x, &y, &grid_offset);
194 int forward_direction = (direction + 4) % 8;
195 direction_path[num_tiles++] = forward_direction;
196 last_direction = forward_direction;
197 if (num_tiles >= MAX_PATH) {
198 return 0;
199 }
200 }
201 for (int i = 0; i < num_tiles; i++) {
202 path[i] = direction_path[num_tiles - i - 1];
203 }
204 return num_tiles;
205 }
206