author | truebrain |
Sun, 15 Jun 2008 22:37:35 +0000 | |
branch | noai |
changeset 10972 | 986675d19245 |
parent 10455 | 22c441f5adf9 |
permissions | -rw-r--r-- |
2186 | 1 |
/* $Id$ */ |
2 |
||
10455
22c441f5adf9
(svn r12997) [NoAI] -Sync: with trunk r12895:12996.
rubidium
parents:
9837
diff
changeset
|
3 |
/** @file npf.h New A* pathfinder. */ |
9505 | 4 |
|
1247 | 5 |
#ifndef NPF_H |
6 |
#define NPF_H |
|
7 |
||
8 |
#include "aystar.h" |
|
9837
c9ec4f82e0d0
(svn r12503) [NoAI] -Sync: with trunk r12461:12501.
rubidium
parents:
9732
diff
changeset
|
9 |
#include "station_type.h" |
c9ec4f82e0d0
(svn r12503) [NoAI] -Sync: with trunk r12461:12501.
rubidium
parents:
9732
diff
changeset
|
10 |
#include "rail_type.h" |
c9ec4f82e0d0
(svn r12503) [NoAI] -Sync: with trunk r12461:12501.
rubidium
parents:
9732
diff
changeset
|
11 |
#include "player_type.h" |
9723
eee46cb39750
(svn r11796) [NoAI] -Sync: with trunk r11502:11795.
rubidium
parents:
9722
diff
changeset
|
12 |
#include "vehicle_type.h" |
eee46cb39750
(svn r11796) [NoAI] -Sync: with trunk r11502:11795.
rubidium
parents:
9722
diff
changeset
|
13 |
#include "tile_type.h" |
eee46cb39750
(svn r11796) [NoAI] -Sync: with trunk r11502:11795.
rubidium
parents:
9722
diff
changeset
|
14 |
#include "track_type.h" |
9724
b39bc69bb2f2
(svn r12051) [NoAI] -Sync: with trunk (r11795:12050).
rubidium
parents:
9723
diff
changeset
|
15 |
#include "core/bitmath_func.hpp" |
10455
22c441f5adf9
(svn r12997) [NoAI] -Sync: with trunk r12895:12996.
rubidium
parents:
9837
diff
changeset
|
16 |
#include "transport_type.h" |
1247 | 17 |
|
9505 | 18 |
/* mowing grass */ |
1661
6af0c4416154
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1459
diff
changeset
|
19 |
enum { |
9505 | 20 |
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. |
1661
6af0c4416154
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1459
diff
changeset
|
21 |
/* Do no change below values */ |
6af0c4416154
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1459
diff
changeset
|
22 |
NPF_HASH_SIZE = 1 << NPF_HASH_BITS, |
6af0c4416154
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1459
diff
changeset
|
23 |
NPF_HASH_HALFBITS = NPF_HASH_BITS / 2, |
6af0c4416154
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1459
diff
changeset
|
24 |
NPF_HASH_HALFMASK = (1 << NPF_HASH_HALFBITS) - 1 |
6af0c4416154
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1459
diff
changeset
|
25 |
}; |
1247 | 26 |
|
3358
798877df0899
(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
|
27 |
/* For new pathfinding. Define here so it is globally available without having |
798877df0899
(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
|
28 |
* to include npf.h */ |
798877df0899
(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
|
29 |
enum { |
798877df0899
(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
|
30 |
NPF_TILE_LENGTH = 100 |
798877df0899
(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
|
31 |
}; |
798877df0899
(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
|
32 |
|
1777
d328484bd6f2
(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 |
enum { |
d328484bd6f2
(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 |
/** This penalty is the equivalent of "inifite", which means that paths that |
d328484bd6f2
(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 |
* get this penalty will be chosen, but only if there is no other route |
d328484bd6f2
(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 |
* without it. Be careful with not applying this penalty to often, or the |
d328484bd6f2
(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 |
* total path cost might overflow.. |
d328484bd6f2
(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
|
38 |
* For now, this is just a Very Big Penalty, we might actually implement |
d328484bd6f2
(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
|
39 |
* this in a nicer way :-) |
d328484bd6f2
(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
|
40 |
*/ |
d328484bd6f2
(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
|
41 |
NPF_INFINITE_PENALTY = 1000 * NPF_TILE_LENGTH |
d328484bd6f2
(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
|
42 |
}; |
d328484bd6f2
(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
|
43 |
|
9505 | 44 |
/* Meant to be stored in AyStar.targetdata */ |
45 |
struct NPFFindStationOrTileData { |
|
46 |
TileIndex dest_coords; ///< An indication of where the station is, for heuristic purposes, or the target tile |
|
47 |
StationID station_index; ///< station index we're heading for, or INVALID_STATION when we're heading for a tile |
|
6574
e1d1a12faaf7
(svn r9051) -Codechange: typedef [enum|struct] Y {} X; -> [enum|struct] X {};
rubidium
parents:
5726
diff
changeset
|
48 |
}; |
1247 | 49 |
|
9505 | 50 |
/* Indices into AyStar.userdata[] */ |
51 |
enum { |
|
52 |
NPF_TYPE = 0, ///< Contains a TransportTypes value |
|
9624 | 53 |
NPF_SUB_TYPE, ///< Contains the sub transport type |
9505 | 54 |
NPF_OWNER, ///< Contains an Owner value |
55 |
NPF_RAILTYPES, ///< Contains a bitmask the compatible RailTypes of the engine when NPF_TYPE == TRANSPORT_RAIL. Unused otherwise. |
|
1247 | 56 |
}; |
57 |
||
9505 | 58 |
/* Indices into AyStarNode.userdata[] */ |
59 |
enum { |
|
60 |
NPF_TRACKDIR_CHOICE = 0, ///< The trackdir chosen to get here |
|
1247 | 61 |
NPF_NODE_FLAGS, |
62 |
}; |
|
2008
c9d6585c96c8
(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
|
63 |
|
9505 | 64 |
/* Flags for AyStarNode.userdata[NPF_NODE_FLAGS]. Use NPFGetBit() and NPFGetBit() to use them. */ |
65 |
enum NPFNodeFlag { |
|
9732 | 66 |
NPF_FLAG_SEEN_SIGNAL, ///< Used to mark that a signal was seen on the way, for rail only |
67 |
NPF_FLAG_REVERSE, ///< Used to mark that this node was reached from the second start node, if applicable |
|
68 |
NPF_FLAG_LAST_SIGNAL_RED, ///< Used to mark that the last signal on this path was red |
|
69 |
NPF_FLAG_IGNORE_START_TILE, ///< Used to mark that the start tile is invalid, and searching should start from the second tile on |
|
6574
e1d1a12faaf7
(svn r9051) -Codechange: typedef [enum|struct] Y {} X; -> [enum|struct] X {};
rubidium
parents:
5726
diff
changeset
|
70 |
}; |
1247 | 71 |
|
9505 | 72 |
/* Meant to be stored in AyStar.userpath */ |
73 |
struct NPFFoundTargetData { |
|
74 |
uint best_bird_dist; ///< The best heuristic found. Is 0 if the target was found |
|
75 |
uint best_path_dist; ///< The shortest path. Is (uint)-1 if no path is found |
|
76 |
Trackdir best_trackdir; ///< The trackdir that leads to the shortest path/closest birds dist |
|
77 |
AyStarNode node; ///< The node within the target the search led us to |
|
6574
e1d1a12faaf7
(svn r9051) -Codechange: typedef [enum|struct] Y {} X; -> [enum|struct] X {};
rubidium
parents:
5726
diff
changeset
|
78 |
}; |
1247 | 79 |
|
80 |
/* These functions below are _not_ re-entrant, in favor of speed! */ |
|
81 |
||
82 |
/* Will search from the given tile and direction, for a route to the given |
|
83 |
* station for the given transport type. See the declaration of |
|
84 |
* NPFFoundTargetData above for the meaning of the result. */ |
|
9732 | 85 |
NPFFoundTargetData NPFRouteToStationOrTile(TileIndex tile, Trackdir trackdir, bool ignore_start_tile, NPFFindStationOrTileData* target, TransportType type, uint sub_type, Owner owner, RailTypes railtypes); |
2951 | 86 |
|
1247 | 87 |
/* Will search as above, but with two start nodes, the second being the |
1459
6c1f01803928
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
88 |
* reverse. Look at the NPF_FLAG_REVERSE flag in the result node to see which |
6c1f01803928
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
89 |
* direction was taken (NPFGetBit(result.node, NPF_FLAG_REVERSE)) */ |
9732 | 90 |
NPFFoundTargetData NPFRouteToStationOrTileTwoWay(TileIndex tile1, Trackdir trackdir1, bool ignore_start_tile1, TileIndex tile2, Trackdir trackdir2, bool ignore_start_tile2, NPFFindStationOrTileData* target, TransportType type, uint sub_type, Owner owner, RailTypes railtypes); |
1247 | 91 |
|
92 |
/* Will search a route to the closest depot. */ |
|
93 |
||
94 |
/* Search using breadth first. Good for little track choice and inaccurate |
|
1777
d328484bd6f2
(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
|
95 |
* heuristic, such as railway/road.*/ |
9732 | 96 |
NPFFoundTargetData NPFRouteToDepotBreadthFirst(TileIndex tile, Trackdir trackdir, bool ignore_start_tile, TransportType type, uint sub_type, Owner owner, RailTypes railtypes); |
1777
d328484bd6f2
(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
|
97 |
/* Same as above but with two start nodes, the second being the reverse. Call |
d328484bd6f2
(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
|
98 |
* NPFGetBit(result.node, NPF_FLAG_REVERSE) to see from which node the path |
d328484bd6f2
(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
|
99 |
* orginated. All pathfs from the second node will have the given |
d328484bd6f2
(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
|
100 |
* reverse_penalty applied (NPF_TILE_LENGTH is the equivalent of one full |
d328484bd6f2
(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
|
101 |
* tile). |
d328484bd6f2
(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
|
102 |
*/ |
9732 | 103 |
NPFFoundTargetData NPFRouteToDepotBreadthFirstTwoWay(TileIndex tile1, Trackdir trackdir1, bool ignore_start_tile1, TileIndex tile2, Trackdir trackdir2, bool ignore_start_tile2, TransportType type, uint sub_type, Owner owner, RailTypes railtypes, uint reverse_penalty); |
1247 | 104 |
/* Search by trying each depot in order of Manhattan Distance. Good for lots |
1330
8a67d04016ce
(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
|
105 |
* of choices and accurate heuristics, such as water. */ |
9732 | 106 |
NPFFoundTargetData NPFRouteToDepotTrialError(TileIndex tile, Trackdir trackdir, bool ignore_start_tile, TransportType type, uint sub_type, Owner owner, RailTypes railtypes); |
1247 | 107 |
|
108 |
void NPFFillWithOrderData(NPFFindStationOrTileData* fstd, Vehicle* v); |
|
109 |
||
1459
6c1f01803928
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
110 |
|
6c1f01803928
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
111 |
/* |
6c1f01803928
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
112 |
* Functions to manipulate the various NPF related flags on an AyStarNode. |
6c1f01803928
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
113 |
*/ |
6c1f01803928
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
114 |
|
6c1f01803928
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
115 |
/** |
6c1f01803928
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
116 |
* Returns the current value of the given flag on the given AyStarNode. |
6c1f01803928
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
117 |
*/ |
6c1f01803928
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
118 |
static inline bool NPFGetFlag(const AyStarNode* node, NPFNodeFlag flag) |
6c1f01803928
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
119 |
{ |
9722
ebf0ece7d8f6
(svn r11503) [NoAI] -Sync: with trunk r11308:11502.
rubidium
parents:
9624
diff
changeset
|
120 |
return HasBit(node->user_data[NPF_NODE_FLAGS], flag); |
1459
6c1f01803928
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
121 |
} |
6c1f01803928
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
122 |
|
6c1f01803928
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
123 |
/** |
6c1f01803928
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
124 |
* Sets the given flag on the given AyStarNode to the given value. |
6c1f01803928
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
125 |
*/ |
6c1f01803928
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
126 |
static inline void NPFSetFlag(AyStarNode* node, NPFNodeFlag flag, bool value) |
6c1f01803928
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
127 |
{ |
6c1f01803928
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
128 |
if (value) |
9722
ebf0ece7d8f6
(svn r11503) [NoAI] -Sync: with trunk r11308:11502.
rubidium
parents:
9624
diff
changeset
|
129 |
SetBit(node->user_data[NPF_NODE_FLAGS], flag); |
1459
6c1f01803928
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
130 |
else |
9722
ebf0ece7d8f6
(svn r11503) [NoAI] -Sync: with trunk r11308:11502.
rubidium
parents:
9624
diff
changeset
|
131 |
ClrBit(node->user_data[NPF_NODE_FLAGS], flag); |
1459
6c1f01803928
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
132 |
} |
6c1f01803928
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1330
diff
changeset
|
133 |
|
2436
177cb6a8339f
(svn r2962) - const correctness for all Get* functions and most Draw* functions that don't change their pointer parameters
Darkvater
parents:
2186
diff
changeset
|
134 |
#endif /* NPF_H */ |