author | Darkvater |
Tue, 31 Oct 2006 23:04:47 +0000 | |
changeset 5009 | 0ae33f104d4f |
parent 3358 | c69b64a580b2 |
permissions | -rw-r--r-- |
2186 | 1 |
/* $Id$ */ |
2 |
||
1247 | 3 |
#ifndef NPF_H |
4 |
#define NPF_H |
|
5 |
||
1891
862800791170
(svn r2397) - CodeChange: rename all "ttd" files to "openttd" files.
Darkvater
parents:
1880
diff
changeset
|
6 |
#include "openttd.h" |
1247 | 7 |
#include "aystar.h" |
3135 | 8 |
#include "station.h" |
1247 | 9 |
#include "vehicle.h" |
1942
c5d5cf5b0263
(svn r2448) General cleanup of rail related code, more to follow.
matthijs
parents:
1891
diff
changeset
|
10 |
#include "tile.h" |
1247 | 11 |
|
12 |
//mowing grass |
|
1661
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1459
diff
changeset
|
13 |
enum { |
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1459
diff
changeset
|
14 |
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. */ |
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1459
diff
changeset
|
15 |
/* Do no change below values */ |
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1459
diff
changeset
|
16 |
NPF_HASH_SIZE = 1 << NPF_HASH_BITS, |
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1459
diff
changeset
|
17 |
NPF_HASH_HALFBITS = NPF_HASH_BITS / 2, |
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1459
diff
changeset
|
18 |
NPF_HASH_HALFMASK = (1 << NPF_HASH_HALFBITS) - 1 |
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1459
diff
changeset
|
19 |
}; |
1247 | 20 |
|
3358
c69b64a580b2
(svn r4153) -Codechange. Changed NPF_TILE_LENGTH into an enum and moved it out of variables.h. Just a drop in the bucket, but it is a start
celestar
parents:
3355
diff
changeset
|
21 |
/* For new pathfinding. Define here so it is globally available without having |
c69b64a580b2
(svn r4153) -Codechange. Changed NPF_TILE_LENGTH into an enum and moved it out of variables.h. Just a drop in the bucket, but it is a start
celestar
parents:
3355
diff
changeset
|
22 |
* to include npf.h */ |
c69b64a580b2
(svn r4153) -Codechange. Changed NPF_TILE_LENGTH into an enum and moved it out of variables.h. Just a drop in the bucket, but it is a start
celestar
parents:
3355
diff
changeset
|
23 |
enum { |
c69b64a580b2
(svn r4153) -Codechange. Changed NPF_TILE_LENGTH into an enum and moved it out of variables.h. Just a drop in the bucket, but it is a start
celestar
parents:
3355
diff
changeset
|
24 |
NPF_TILE_LENGTH = 100 |
c69b64a580b2
(svn r4153) -Codechange. Changed NPF_TILE_LENGTH into an enum and moved it out of variables.h. Just a drop in the bucket, but it is a start
celestar
parents:
3355
diff
changeset
|
25 |
}; |
c69b64a580b2
(svn r4153) -Codechange. Changed NPF_TILE_LENGTH into an enum and moved it out of variables.h. Just a drop in the bucket, but it is a start
celestar
parents:
3355
diff
changeset
|
26 |
|
1777
f703cf05b5b9
(svn r2281) - Fix: [ 1115204 ] [NPF] When pressing the goto depot button, trains will now also look behind it if there is no depot in front. If so, the train reverses immediately. This also work anywhere, not just at stations.
matthijs
parents:
1751
diff
changeset
|
27 |
enum { |
f703cf05b5b9
(svn r2281) - Fix: [ 1115204 ] [NPF] When pressing the goto depot button, trains will now also look behind it if there is no depot in front. If so, the train reverses immediately. This also work anywhere, not just at stations.
matthijs
parents:
1751
diff
changeset
|
28 |
/** This penalty is the equivalent of "inifite", which means that paths that |
f703cf05b5b9
(svn r2281) - Fix: [ 1115204 ] [NPF] When pressing the goto depot button, trains will now also look behind it if there is no depot in front. If so, the train reverses immediately. This also work anywhere, not just at stations.
matthijs
parents:
1751
diff
changeset
|
29 |
* get this penalty will be chosen, but only if there is no other route |
f703cf05b5b9
(svn r2281) - Fix: [ 1115204 ] [NPF] When pressing the goto depot button, trains will now also look behind it if there is no depot in front. If so, the train reverses immediately. This also work anywhere, not just at stations.
matthijs
parents:
1751
diff
changeset
|
30 |
* without it. Be careful with not applying this penalty to often, or the |
f703cf05b5b9
(svn r2281) - Fix: [ 1115204 ] [NPF] When pressing the goto depot button, trains will now also look behind it if there is no depot in front. If so, the train reverses immediately. This also work anywhere, not just at stations.
matthijs
parents:
1751
diff
changeset
|
31 |
* total path cost might overflow.. |
f703cf05b5b9
(svn r2281) - Fix: [ 1115204 ] [NPF] When pressing the goto depot button, trains will now also look behind it if there is no depot in front. If so, the train reverses immediately. This also work anywhere, not just at stations.
matthijs
parents:
1751
diff
changeset
|
32 |
* For now, this is just a Very Big Penalty, we might actually implement |
f703cf05b5b9
(svn r2281) - Fix: [ 1115204 ] [NPF] When pressing the goto depot button, trains will now also look behind it if there is no depot in front. If so, the train reverses immediately. This also work anywhere, not just at stations.
matthijs
parents:
1751
diff
changeset
|
33 |
* this in a nicer way :-) |
f703cf05b5b9
(svn r2281) - Fix: [ 1115204 ] [NPF] When pressing the goto depot button, trains will now also look behind it if there is no depot in front. If so, the train reverses immediately. This also work anywhere, not just at stations.
matthijs
parents:
1751
diff
changeset
|
34 |
*/ |
f703cf05b5b9
(svn r2281) - Fix: [ 1115204 ] [NPF] When pressing the goto depot button, trains will now also look behind it if there is no depot in front. If so, the train reverses immediately. This also work anywhere, not just at stations.
matthijs
parents:
1751
diff
changeset
|
35 |
NPF_INFINITE_PENALTY = 1000 * NPF_TILE_LENGTH |
f703cf05b5b9
(svn r2281) - Fix: [ 1115204 ] [NPF] When pressing the goto depot button, trains will now also look behind it if there is no depot in front. If so, the train reverses immediately. This also work anywhere, not just at stations.
matthijs
parents:
1751
diff
changeset
|
36 |
}; |
f703cf05b5b9
(svn r2281) - Fix: [ 1115204 ] [NPF] When pressing the goto depot button, trains will now also look behind it if there is no depot in front. If so, the train reverses immediately. This also work anywhere, not just at stations.
matthijs
parents:
1751
diff
changeset
|
37 |
|
1247 | 38 |
typedef struct NPFFindStationOrTileData { /* Meant to be stored in AyStar.targetdata */ |
39 |
TileIndex dest_coords; /* An indication of where the station is, for heuristic purposes, or the target tile */ |
|
3135 | 40 |
StationID station_index; /* station index we're heading for, or INVALID_STATION when we're heading for a tile */ |
1247 | 41 |
} NPFFindStationOrTileData; |
42 |
||
43 |
enum { /* Indices into AyStar.userdata[] */ |
|
1330
5d76a0522a11
(svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents:
1247
diff
changeset
|
44 |
NPF_TYPE = 0, /* Contains a TransportTypes value */ |
5d76a0522a11
(svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents:
1247
diff
changeset
|
45 |
NPF_OWNER, /* Contains an Owner value */ |
3355
e414a0b104a6
(svn r4150) -Feature: Merged elrails into trunk. Thanks to Tron for lots of code and proofreading, thanks to peter1138 for another lot of code and ideas.
celestar
parents:
3135
diff
changeset
|
46 |
NPF_RAILTYPES, /* Contains a bitmask the compatible RailTypes of the engine when NPF_TYPE == TRANSPORT_RAIL. Unused otherwise. */ |
1247 | 47 |
}; |
48 |
||
49 |
enum { /* Indices into AyStarNode.userdata[] */ |
|
50 |
NPF_TRACKDIR_CHOICE = 0, /* The trackdir chosen to get here */ |
|
51 |
NPF_NODE_FLAGS, |
|
52 |
}; |
|
2008
cdb444f6d43c
(svn r2516) - Feature: [pbs] Implement path-based-signalling. This allows multiple trains within the same signal block, provided their paths dont intersect. For this the block must have all exit and entry signals be pbs signals. Place these by ctrl-clicking 4 times on a normal signal.
hackykid
parents:
2006
diff
changeset
|
53 |
|
1459
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
54 |
typedef enum { /* Flags for AyStarNode.userdata[NPF_NODE_FLAGS]. Use NPFGetBit() and NPFGetBit() to use them. */ |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
55 |
NPF_FLAG_SEEN_SIGNAL, /* Used to mark that a signal was seen on the way, for rail only */ |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
56 |
NPF_FLAG_REVERSE, /* Used to mark that this node was reached from the second start node, if applicable */ |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
57 |
NPF_FLAG_LAST_SIGNAL_RED, /* Used to mark that the last signal on this path was red */ |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
58 |
} NPFNodeFlag; |
1247 | 59 |
|
60 |
typedef struct NPFFoundTargetData { /* Meant to be stored in AyStar.userpath */ |
|
61 |
uint best_bird_dist; /* The best heuristic found. Is 0 if the target was found */ |
|
62 |
uint best_path_dist; /* The shortest path. Is (uint)-1 if no path is found */ |
|
1942
c5d5cf5b0263
(svn r2448) General cleanup of rail related code, more to follow.
matthijs
parents:
1891
diff
changeset
|
63 |
Trackdir best_trackdir; /* The trackdir that leads to the shortest path/closest birds dist */ |
1247 | 64 |
AyStarNode node; /* The node within the target the search led us to */ |
65 |
} NPFFoundTargetData; |
|
66 |
||
67 |
/* These functions below are _not_ re-entrant, in favor of speed! */ |
|
68 |
||
69 |
/* Will search from the given tile and direction, for a route to the given |
|
70 |
* station for the given transport type. See the declaration of |
|
71 |
* NPFFoundTargetData above for the meaning of the result. */ |
|
3355
e414a0b104a6
(svn r4150) -Feature: Merged elrails into trunk. Thanks to Tron for lots of code and proofreading, thanks to peter1138 for another lot of code and ideas.
celestar
parents:
3135
diff
changeset
|
72 |
NPFFoundTargetData NPFRouteToStationOrTile(TileIndex tile, Trackdir trackdir, NPFFindStationOrTileData* target, TransportType type, Owner owner, RailTypeMask railtypes); |
2951 | 73 |
|
1247 | 74 |
/* Will search as above, but with two start nodes, the second being the |
1459
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
75 |
* reverse. Look at the NPF_FLAG_REVERSE flag in the result node to see which |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
76 |
* direction was taken (NPFGetBit(result.node, NPF_FLAG_REVERSE)) */ |
3355
e414a0b104a6
(svn r4150) -Feature: Merged elrails into trunk. Thanks to Tron for lots of code and proofreading, thanks to peter1138 for another lot of code and ideas.
celestar
parents:
3135
diff
changeset
|
77 |
NPFFoundTargetData NPFRouteToStationOrTileTwoWay(TileIndex tile1, Trackdir trackdir1, TileIndex tile2, Trackdir trackdir2, NPFFindStationOrTileData* target, TransportType type, Owner owner, RailTypeMask railtypes); |
1247 | 78 |
|
79 |
/* Will search a route to the closest depot. */ |
|
80 |
||
81 |
/* Search using breadth first. Good for little track choice and inaccurate |
|
1777
f703cf05b5b9
(svn r2281) - Fix: [ 1115204 ] [NPF] When pressing the goto depot button, trains will now also look behind it if there is no depot in front. If so, the train reverses immediately. This also work anywhere, not just at stations.
matthijs
parents:
1751
diff
changeset
|
82 |
* heuristic, such as railway/road.*/ |
3355
e414a0b104a6
(svn r4150) -Feature: Merged elrails into trunk. Thanks to Tron for lots of code and proofreading, thanks to peter1138 for another lot of code and ideas.
celestar
parents:
3135
diff
changeset
|
83 |
NPFFoundTargetData NPFRouteToDepotBreadthFirst(TileIndex tile, Trackdir trackdir, TransportType type, Owner owner, RailTypeMask railtypes); |
1777
f703cf05b5b9
(svn r2281) - Fix: [ 1115204 ] [NPF] When pressing the goto depot button, trains will now also look behind it if there is no depot in front. If so, the train reverses immediately. This also work anywhere, not just at stations.
matthijs
parents:
1751
diff
changeset
|
84 |
/* Same as above but with two start nodes, the second being the reverse. Call |
f703cf05b5b9
(svn r2281) - Fix: [ 1115204 ] [NPF] When pressing the goto depot button, trains will now also look behind it if there is no depot in front. If so, the train reverses immediately. This also work anywhere, not just at stations.
matthijs
parents:
1751
diff
changeset
|
85 |
* NPFGetBit(result.node, NPF_FLAG_REVERSE) to see from which node the path |
f703cf05b5b9
(svn r2281) - Fix: [ 1115204 ] [NPF] When pressing the goto depot button, trains will now also look behind it if there is no depot in front. If so, the train reverses immediately. This also work anywhere, not just at stations.
matthijs
parents:
1751
diff
changeset
|
86 |
* orginated. All pathfs from the second node will have the given |
f703cf05b5b9
(svn r2281) - Fix: [ 1115204 ] [NPF] When pressing the goto depot button, trains will now also look behind it if there is no depot in front. If so, the train reverses immediately. This also work anywhere, not just at stations.
matthijs
parents:
1751
diff
changeset
|
87 |
* reverse_penalty applied (NPF_TILE_LENGTH is the equivalent of one full |
f703cf05b5b9
(svn r2281) - Fix: [ 1115204 ] [NPF] When pressing the goto depot button, trains will now also look behind it if there is no depot in front. If so, the train reverses immediately. This also work anywhere, not just at stations.
matthijs
parents:
1751
diff
changeset
|
88 |
* tile). |
f703cf05b5b9
(svn r2281) - Fix: [ 1115204 ] [NPF] When pressing the goto depot button, trains will now also look behind it if there is no depot in front. If so, the train reverses immediately. This also work anywhere, not just at stations.
matthijs
parents:
1751
diff
changeset
|
89 |
*/ |
3355
e414a0b104a6
(svn r4150) -Feature: Merged elrails into trunk. Thanks to Tron for lots of code and proofreading, thanks to peter1138 for another lot of code and ideas.
celestar
parents:
3135
diff
changeset
|
90 |
NPFFoundTargetData NPFRouteToDepotBreadthFirstTwoWay(TileIndex tile1, Trackdir trackdir1, TileIndex tile2, Trackdir trackdir2, TransportType type, Owner owner, RailTypeMask railtypes, uint reverse_penalty); |
1247 | 91 |
/* Search by trying each depot in order of Manhattan Distance. Good for lots |
1330
5d76a0522a11
(svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents:
1247
diff
changeset
|
92 |
* of choices and accurate heuristics, such as water. */ |
3355
e414a0b104a6
(svn r4150) -Feature: Merged elrails into trunk. Thanks to Tron for lots of code and proofreading, thanks to peter1138 for another lot of code and ideas.
celestar
parents:
3135
diff
changeset
|
93 |
NPFFoundTargetData NPFRouteToDepotTrialError(TileIndex tile, Trackdir trackdir, TransportType type, Owner owner, RailTypeMask railtypes); |
1247 | 94 |
|
95 |
void NPFFillWithOrderData(NPFFindStationOrTileData* fstd, Vehicle* v); |
|
96 |
||
1459
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
97 |
|
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
98 |
/* |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
99 |
* Functions to manipulate the various NPF related flags on an AyStarNode. |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
100 |
*/ |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
101 |
|
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
102 |
/** |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
103 |
* Returns the current value of the given flag on the given AyStarNode. |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
104 |
*/ |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
105 |
static inline bool NPFGetFlag(const AyStarNode* node, NPFNodeFlag flag) |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
106 |
{ |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
107 |
return HASBIT(node->user_data[NPF_NODE_FLAGS], flag); |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
108 |
} |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
109 |
|
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
110 |
/** |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
111 |
* Sets the given flag on the given AyStarNode to the given value. |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
112 |
*/ |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
113 |
static inline void NPFSetFlag(AyStarNode* node, NPFNodeFlag flag, bool value) |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
114 |
{ |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
115 |
if (value) |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
116 |
SETBIT(node->user_data[NPF_NODE_FLAGS], flag); |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
117 |
else |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
118 |
CLRBIT(node->user_data[NPF_NODE_FLAGS], flag); |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
119 |
} |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
120 |
|
2436
7d5df545bd5d
(svn r2962) - const correctness for all Get* functions and most Draw* functions that don't change their pointer parameters
Darkvater
parents:
2186
diff
changeset
|
121 |
#endif /* NPF_H */ |