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