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