|
1 #ifndef NPF_H |
|
2 #define NPF_H |
|
3 |
|
4 #include "ttd.h" |
|
5 #include "aystar.h" |
|
6 #include "vehicle.h" |
|
7 |
|
8 //#define NPF_DEBUG |
|
9 //#define NPF_MARKROUTE //Mark the routes considered by the pathfinder by |
|
10 //mowing grass |
|
11 |
|
12 typedef struct NPFFindStationOrTileData { /* Meant to be stored in AyStar.targetdata */ |
|
13 TileIndex dest_coords; /* An indication of where the station is, for heuristic purposes, or the target tile */ |
|
14 int station_index; /* station index we're heading for, or -1 when we're heading for a tile */ |
|
15 } NPFFindStationOrTileData; |
|
16 |
|
17 enum { /* Indices into AyStar.userdata[] */ |
|
18 NPF_TYPE = 0, /* Contains an TransportTypes value */ |
|
19 }; |
|
20 |
|
21 enum { /* Indices into AyStarNode.userdata[] */ |
|
22 NPF_TRACKDIR_CHOICE = 0, /* The trackdir chosen to get here */ |
|
23 NPF_NODE_FLAGS, |
|
24 }; |
|
25 enum { /* Flags for AyStarNode.userdata[NPF_NODE_FLAGS]*/ |
|
26 NPF_FLAG_SEEN_SIGNAL = 1, /* Used to mark that a signal was seen on the way, for rail only */ |
|
27 NPF_FLAG_REVERSE = 2, /* Used to mark that this node was reached from the second start node, if applicable */ |
|
28 }; |
|
29 |
|
30 typedef struct NPFFoundTargetData { /* Meant to be stored in AyStar.userpath */ |
|
31 uint best_bird_dist; /* The best heuristic found. Is 0 if the target was found */ |
|
32 uint best_path_dist; /* The shortest path. Is (uint)-1 if no path is found */ |
|
33 byte best_trackdir; /* The trackdir that leads to the shortes path/closest birds dist */ |
|
34 AyStarNode node; /* The node within the target the search led us to */ |
|
35 } NPFFoundTargetData; |
|
36 |
|
37 /* These functions below are _not_ re-entrant, in favor of speed! */ |
|
38 |
|
39 /* Will search from the given tile and direction, for a route to the given |
|
40 * station for the given transport type. See the declaration of |
|
41 * NPFFoundTargetData above for the meaning of the result. */ |
|
42 NPFFoundTargetData NPFRouteToStationOrTile(TileIndex tile, byte trackdir, NPFFindStationOrTileData* target, TransportType type); |
|
43 /* Will search as above, but with two start nodes, the second being the |
|
44 * reverse. Look at the NPF_NODE_REVERSE flag in the result node to see which |
|
45 * direction was taken */ |
|
46 NPFFoundTargetData NPFRouteToStationOrTileTwoWay(TileIndex tile1, byte trackdir1, TileIndex tile2, byte trackdir2, NPFFindStationOrTileData* target, TransportType type); |
|
47 |
|
48 /* Will search a route to the closest depot. */ |
|
49 |
|
50 /* Search using breadth first. Good for little track choice and inaccurate |
|
51 * heuristic, such as railway/road */ |
|
52 NPFFoundTargetData NPFRouteToDepotBreadthFirst(TileIndex tile, byte trackdir, TransportType type); |
|
53 /* Search by trying each depot in order of Manhattan Distance. Good for lots |
|
54 * of choices and accurate heuristics, such as water */ |
|
55 NPFFoundTargetData NPFRouteToDepotTrialError(TileIndex tile, byte trackdir, TransportType type); |
|
56 |
|
57 void NPFFillWithOrderData(NPFFindStationOrTileData* fstd, Vehicle* v); |
|
58 |
|
59 /* |
|
60 * Some tables considering tracks, directions and signals. |
|
61 * XXX: Better place to but these? |
|
62 */ |
|
63 |
|
64 /** |
|
65 * Maps a trackdir to the bit that stores its status in the map arrays, in the |
|
66 * direction along with the trackdir. |
|
67 */ |
|
68 const byte _signal_along_trackdir[14]; |
|
69 |
|
70 /** |
|
71 * Maps a trackdir to the bit that stores its status in the map arrays, in the |
|
72 * direction against the trackdir. |
|
73 */ |
|
74 const byte _signal_against_trackdir[14]; |
|
75 |
|
76 /** |
|
77 * Maps a trackdir to the trackdirs that can be reached from it (ie, when |
|
78 * entering the next tile. |
|
79 */ |
|
80 const uint16 _trackdir_reaches_trackdirs[14]; |
|
81 |
|
82 /** |
|
83 * Maps a trackdir to all trackdirs that make 90 deg turns with it. |
|
84 */ |
|
85 const uint16 _trackdir_crosses_trackdirs[14]; |
|
86 |
|
87 /** |
|
88 * Maps a track to all tracks that make 90 deg turns with it. |
|
89 */ |
|
90 const byte _track_crosses_tracks[6]; |
|
91 |
|
92 /** |
|
93 * Maps a trackdir to the (4-way) direction the tile is exited when following |
|
94 * that trackdir. |
|
95 */ |
|
96 const byte _trackdir_to_exitdir[14]; |
|
97 |
|
98 /** |
|
99 * Maps a track and an (4-way) dir to the trackdir that represents the track |
|
100 * with the exit in the given direction. |
|
101 */ |
|
102 const byte _track_exitdir_to_trackdir[6][4]; |
|
103 |
|
104 /** |
|
105 * Maps a track and a full (8-way) direction to the trackdir that represents |
|
106 * the track running in the given direction. |
|
107 */ |
|
108 const byte _track_direction_to_trackdir[6][8]; |
|
109 |
|
110 /** |
|
111 * Maps a (4-way) direction to the diagonal track that runs in that |
|
112 * direction. |
|
113 */ |
|
114 const byte _dir_to_diag_trackdir[4]; |
|
115 |
|
116 /** |
|
117 * Maps a (4-way) direction to the reverse. |
|
118 */ |
|
119 const byte _reverse_dir[4]; |
|
120 |
|
121 /** |
|
122 * Maps a trackdir to the reverse trackdir. |
|
123 */ |
|
124 const byte _reverse_trackdir[14]; |
|
125 |
|
126 #define REVERSE_TRACKDIR(trackdir) (trackdir ^ 0x8) |
|
127 |
|
128 #endif // NPF_H |