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_path_on_water(uint8_t * path,int dst_x,int dst_y,int is_flotsam)99 int map_routing_get_path_on_water(uint8_t *path, int dst_x, int dst_y, int is_flotsam)
100 {
101 int rand = random_byte() & 3;
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 while (distance > 1) {
114 int current_rand = rand;
115 distance = map_routing_distance(grid_offset);
116 if (is_flotsam) {
117 current_rand = map_random_get(grid_offset) & 3;
118 }
119 int direction = -1;
120 for (int d = 0; d < 8; d++) {
121 if (d != last_direction) {
122 int next_offset = grid_offset + map_grid_direction_delta(d);
123 int next_distance = map_routing_distance(next_offset);
124 if (next_distance) {
125 if (next_distance < distance) {
126 distance = next_distance;
127 direction = d;
128 } else if (next_distance == distance && rand == current_rand) {
129 // allow flotsam to wander
130 distance = next_distance;
131 direction = d;
132 }
133 }
134 }
135 }
136 if (direction == -1) {
137 return 0;
138 }
139 adjust_tile_in_direction(direction, &x, &y, &grid_offset);
140 int forward_direction = (direction + 4) % 8;
141 direction_path[num_tiles++] = forward_direction;
142 last_direction = forward_direction;
143 if (num_tiles >= MAX_PATH) {
144 return 0;
145 }
146 }
147 for (int i = 0; i < num_tiles; i++) {
148 path[i] = direction_path[num_tiles - i - 1];
149 }
150 return num_tiles;
151 }
152