1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
|
#ifndef NPF_H
#define NPF_H
#include "ttd.h"
#include "aystar.h"
#include "vehicle.h"
//mowing grass
enum {
NPF_HASH_BITS = 12, /* The size of the hash used in pathfinding. Just changing this value should be sufficient to change the hash size. Should be an even value. */
/* Do no change below values */
NPF_HASH_SIZE = 1 << NPF_HASH_BITS,
NPF_HASH_HALFBITS = NPF_HASH_BITS / 2,
NPF_HASH_HALFMASK = (1 << NPF_HASH_HALFBITS) - 1
};
typedef struct NPFFindStationOrTileData { /* Meant to be stored in AyStar.targetdata */
TileIndex dest_coords; /* An indication of where the station is, for heuristic purposes, or the target tile */
int station_index; /* station index we're heading for, or -1 when we're heading for a tile */
} NPFFindStationOrTileData;
enum { /* Indices into AyStar.userdata[] */
NPF_TYPE = 0, /* Contains a TransportTypes value */
NPF_OWNER, /* Contains an Owner value */
};
enum { /* Indices into AyStarNode.userdata[] */
NPF_TRACKDIR_CHOICE = 0, /* The trackdir chosen to get here */
NPF_NODE_FLAGS,
};
typedef enum { /* Flags for AyStarNode.userdata[NPF_NODE_FLAGS]. Use NPFGetBit() and NPFGetBit() to use them. */
NPF_FLAG_SEEN_SIGNAL, /* Used to mark that a signal was seen on the way, for rail only */
NPF_FLAG_REVERSE, /* Used to mark that this node was reached from the second start node, if applicable */
NPF_FLAG_LAST_SIGNAL_RED, /* Used to mark that the last signal on this path was red */
NPF_FLAG_TARGET_CHECKED, /* Used by end node checking function of npf to mark
that they have evaluated this node. When this
flag is on, NPF_FLAG_IS_TARGET is on when the
node is a target, and off when it is not. Should
never be used directly, only by the end node
checking functions for caching of results. */
NPF_FLAG_IS_TARGET, /* See comment for NPF_FLAG_TARGET_CHECKED */
} NPFNodeFlag;
typedef struct NPFFoundTargetData { /* Meant to be stored in AyStar.userpath */
uint best_bird_dist; /* The best heuristic found. Is 0 if the target was found */
uint best_path_dist; /* The shortest path. Is (uint)-1 if no path is found */
byte best_trackdir; /* The trackdir that leads to the shortest path/closest birds dist */
AyStarNode node; /* The node within the target the search led us to */
} NPFFoundTargetData;
/* These functions below are _not_ re-entrant, in favor of speed! */
/* Will search from the given tile and direction, for a route to the given
* station for the given transport type. See the declaration of
* NPFFoundTargetData above for the meaning of the result. */
NPFFoundTargetData NPFRouteToStationOrTile(TileIndex tile, byte trackdir, NPFFindStationOrTileData* target, TransportType type, Owner owner);
/* Will search as above, but with two start nodes, the second being the
* reverse. Look at the NPF_FLAG_REVERSE flag in the result node to see which
* direction was taken (NPFGetBit(result.node, NPF_FLAG_REVERSE)) */
NPFFoundTargetData NPFRouteToStationOrTileTwoWay(TileIndex tile1, byte trackdir1, TileIndex tile2, byte trackdir2, NPFFindStationOrTileData* target, TransportType type, Owner owner);
/* Will search a route to the closest depot. */
/* Search using breadth first. Good for little track choice and inaccurate
* heuristic, such as railway/road */
NPFFoundTargetData NPFRouteToDepotBreadthFirst(TileIndex tile, byte trackdir, TransportType type, Owner owner);
/* Search by trying each depot in order of Manhattan Distance. Good for lots
* of choices and accurate heuristics, such as water. */
NPFFoundTargetData NPFRouteToDepotTrialError(TileIndex tile, byte trackdir, TransportType type, Owner owner);
void NPFFillWithOrderData(NPFFindStationOrTileData* fstd, Vehicle* v);
/*
* Functions to manipulate the various NPF related flags on an AyStarNode.
*/
/**
* Returns the current value of the given flag on the given AyStarNode.
*/
static inline bool NPFGetFlag(const AyStarNode* node, NPFNodeFlag flag)
{
return HASBIT(node->user_data[NPF_NODE_FLAGS], flag);
}
/**
* Sets the given flag on the given AyStarNode to the given value.
*/
static inline void NPFSetFlag(AyStarNode* node, NPFNodeFlag flag, bool value)
{
if (value)
SETBIT(node->user_data[NPF_NODE_FLAGS], flag);
else
CLRBIT(node->user_data[NPF_NODE_FLAGS], flag);
}
/*
* Some tables considering tracks, directions and signals.
* XXX: Better place to but these?
*/
/**
* Maps a trackdir to the bit that stores its status in the map arrays, in the
* direction along with the trackdir.
*/
const byte _signal_along_trackdir[14];
/**
* Maps a trackdir to the bit that stores its status in the map arrays, in the
* direction against the trackdir.
*/
const byte _signal_against_trackdir[14];
/**
* Maps a trackdir to the trackdirs that can be reached from it (ie, when
* entering the next tile.
*/
const uint16 _trackdir_reaches_trackdirs[14];
/**
* Maps a trackdir to all trackdirs that make 90 deg turns with it.
*/
const uint16 _trackdir_crosses_trackdirs[14];
/**
* Maps a track to all tracks that make 90 deg turns with it.
*/
const byte _track_crosses_tracks[6];
/**
* Maps a trackdir to the (4-way) direction the tile is exited when following
* that trackdir.
*/
const byte _trackdir_to_exitdir[14];
/**
* Maps a track and an (4-way) dir to the trackdir that represents the track
* with the exit in the given direction.
*/
const byte _track_exitdir_to_trackdir[6][4];
/**
* Maps a track and a full (8-way) direction to the trackdir that represents
* the track running in the given direction.
*/
const byte _track_direction_to_trackdir[6][8];
/**
* Maps a (4-way) direction to the diagonal track that runs in that
* direction.
*/
const byte _dir_to_diag_trackdir[4];
/**
* Maps a (4-way) direction to the reverse.
*/
const byte _reverse_dir[4];
/**
* Maps a trackdir to the reverse trackdir.
*/
const byte _reverse_trackdir[14];
#define REVERSE_TRACKDIR(trackdir) (trackdir ^ 0x8)
#endif // NPF_H
|
