author | rubidium |
Thu, 01 Feb 2007 15:49:12 +0000 | |
changeset 5893 | 7e431a4abebb |
parent 5598 | 2fadbd43709d |
child 6012 | 065d7234a7a9 |
permissions | -rw-r--r-- |
2186 | 1 |
/* $Id$ */ |
2 |
||
1247 | 3 |
#include "stdafx.h" |
1891
862800791170
(svn r2397) - CodeChange: rename all "ttd" files to "openttd" files.
Darkvater
parents:
1857
diff
changeset
|
4 |
#include "openttd.h" |
3234
a2791a480b71
(svn r3907) Replace many bridge related direct map accesses with calls to shiny new functions and mark some strange constructs with XXX
tron
parents:
3184
diff
changeset
|
5 |
#include "bridge_map.h" |
1299
39c06aba09aa
(svn r1803) Move debugging stuff into files of it's own
tron
parents:
1248
diff
changeset
|
6 |
#include "debug.h" |
2163
b17b313113a0
(svn r2673) Include functions.h directly, not globally via openttd.h
tron
parents:
2115
diff
changeset
|
7 |
#include "functions.h" |
1247 | 8 |
#include "npf.h" |
9 |
#include "aystar.h" |
|
10 |
#include "macros.h" |
|
11 |
#include "pathfind.h" |
|
12 |
#include "station.h" |
|
3315
c9d989783c55
(svn r4079) Add GetSation{Index,ByTile}() to get the station index resp. the station from a tile
tron
parents:
3309
diff
changeset
|
13 |
#include "station_map.h" |
1247 | 14 |
#include "tile.h" |
1313
f1013ec3d318
(svn r1817) -Codechange: Moved depot-functions to depot.c
truelight
parents:
1299
diff
changeset
|
15 |
#include "depot.h" |
3154 | 16 |
#include "tunnel_map.h" |
5469
7edfc643abbc
(svn r7751) -Codechange: move network_* to a new network map. Furthermore move the low level network functions to network/core, so they can be reused by the masterserver and website-serverlist-updater.
rubidium
parents:
5385
diff
changeset
|
17 |
#include "network/network.h" |
3957
25f4a4f22e05
(svn r5116) Move the overly generic GetDepotDirection() from a header to its only consumer
tron
parents:
3933
diff
changeset
|
18 |
#include "water_map.h" |
1247 | 19 |
|
1983 | 20 |
static AyStar _npf_aystar; |
1247 | 21 |
|
22 |
/* The cost of each trackdir. A diagonal piece is the full NPF_TILE_LENGTH, |
|
23 |
* the shorter piece is sqrt(2)/2*NPF_TILE_LENGTH =~ 0.7071 |
|
24 |
*/ |
|
1677
d534f0c8c845
(svn r2181) - Add: DistanceTrack() to calculate the distance over optimally laid out tracks.
matthijs
parents:
1661
diff
changeset
|
25 |
#define NPF_STRAIGHT_LENGTH (uint)(NPF_TILE_LENGTH * STRAIGHT_TRACK_LENGTH) |
1950
aeb6067adc30
(svn r2456) * Prettyfied npf.c using enums and wrappers from rail.h.
matthijs
parents:
1945
diff
changeset
|
26 |
static const uint _trackdir_length[TRACKDIR_END] = { |
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
27 |
NPF_TILE_LENGTH, NPF_TILE_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
28 |
0, 0, |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
29 |
NPF_TILE_LENGTH, NPF_TILE_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH |
1247 | 30 |
}; |
31 |
||
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
|
32 |
/** |
2403
41852918a741
(svn r2929) * Move DistanceTrack from map.c to npf.c and rename to NPFDistanceTrack.
matthijs
parents:
2186
diff
changeset
|
33 |
* Calculates the minimum distance traveled to get from t0 to t1 when only |
41852918a741
(svn r2929) * Move DistanceTrack from map.c to npf.c and rename to NPFDistanceTrack.
matthijs
parents:
2186
diff
changeset
|
34 |
* using tracks (ie, only making 45 degree turns). Returns the distance in the |
41852918a741
(svn r2929) * Move DistanceTrack from map.c to npf.c and rename to NPFDistanceTrack.
matthijs
parents:
2186
diff
changeset
|
35 |
* NPF scale, ie the number of full tiles multiplied by NPF_TILE_LENGTH to |
41852918a741
(svn r2929) * Move DistanceTrack from map.c to npf.c and rename to NPFDistanceTrack.
matthijs
parents:
2186
diff
changeset
|
36 |
* prevent rounding. |
41852918a741
(svn r2929) * Move DistanceTrack from map.c to npf.c and rename to NPFDistanceTrack.
matthijs
parents:
2186
diff
changeset
|
37 |
*/ |
2416 | 38 |
static uint NPFDistanceTrack(TileIndex t0, TileIndex t1) |
2403
41852918a741
(svn r2929) * Move DistanceTrack from map.c to npf.c and rename to NPFDistanceTrack.
matthijs
parents:
2186
diff
changeset
|
39 |
{ |
5587
167d9a91ef02
(svn r8038) -Merge: the cpp branch. Effort of KUDr, Celestar, glx, Smoovius, stillunknown and pv2b.
rubidium
parents:
5584
diff
changeset
|
40 |
const uint dx = delta(TileX(t0), TileX(t1)); |
167d9a91ef02
(svn r8038) -Merge: the cpp branch. Effort of KUDr, Celestar, glx, Smoovius, stillunknown and pv2b.
rubidium
parents:
5584
diff
changeset
|
41 |
const uint dy = delta(TileY(t0), TileY(t1)); |
2403
41852918a741
(svn r2929) * Move DistanceTrack from map.c to npf.c and rename to NPFDistanceTrack.
matthijs
parents:
2186
diff
changeset
|
42 |
|
41852918a741
(svn r2929) * Move DistanceTrack from map.c to npf.c and rename to NPFDistanceTrack.
matthijs
parents:
2186
diff
changeset
|
43 |
const uint straightTracks = 2 * min(dx, dy); /* The number of straight (not full length) tracks */ |
41852918a741
(svn r2929) * Move DistanceTrack from map.c to npf.c and rename to NPFDistanceTrack.
matthijs
parents:
2186
diff
changeset
|
44 |
/* OPTIMISATION: |
41852918a741
(svn r2929) * Move DistanceTrack from map.c to npf.c and rename to NPFDistanceTrack.
matthijs
parents:
2186
diff
changeset
|
45 |
* Original: diagTracks = max(dx, dy) - min(dx,dy); |
41852918a741
(svn r2929) * Move DistanceTrack from map.c to npf.c and rename to NPFDistanceTrack.
matthijs
parents:
2186
diff
changeset
|
46 |
* Proof: |
41852918a741
(svn r2929) * Move DistanceTrack from map.c to npf.c and rename to NPFDistanceTrack.
matthijs
parents:
2186
diff
changeset
|
47 |
* (dx+dy) - straightTracks == (min + max) - straightTracks = min + max - 2 * min = max - min */ |
41852918a741
(svn r2929) * Move DistanceTrack from map.c to npf.c and rename to NPFDistanceTrack.
matthijs
parents:
2186
diff
changeset
|
48 |
const uint diagTracks = dx + dy - straightTracks; /* The number of diagonal (full tile length) tracks. */ |
41852918a741
(svn r2929) * Move DistanceTrack from map.c to npf.c and rename to NPFDistanceTrack.
matthijs
parents:
2186
diff
changeset
|
49 |
|
41852918a741
(svn r2929) * Move DistanceTrack from map.c to npf.c and rename to NPFDistanceTrack.
matthijs
parents:
2186
diff
changeset
|
50 |
/* Don't factor out NPF_TILE_LENGTH below, this will round values and lose |
41852918a741
(svn r2929) * Move DistanceTrack from map.c to npf.c and rename to NPFDistanceTrack.
matthijs
parents:
2186
diff
changeset
|
51 |
* precision */ |
41852918a741
(svn r2929) * Move DistanceTrack from map.c to npf.c and rename to NPFDistanceTrack.
matthijs
parents:
2186
diff
changeset
|
52 |
return diagTracks * NPF_TILE_LENGTH + straightTracks * NPF_TILE_LENGTH * STRAIGHT_TRACK_LENGTH; |
41852918a741
(svn r2929) * Move DistanceTrack from map.c to npf.c and rename to NPFDistanceTrack.
matthijs
parents:
2186
diff
changeset
|
53 |
} |
41852918a741
(svn r2929) * Move DistanceTrack from map.c to npf.c and rename to NPFDistanceTrack.
matthijs
parents:
2186
diff
changeset
|
54 |
|
2951 | 55 |
|
2075
21d2986569d1
(svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents:
2049
diff
changeset
|
56 |
#if 0 |
1983 | 57 |
static uint NTPHash(uint key1, uint key2) |
1247 | 58 |
{ |
1661
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1655
diff
changeset
|
59 |
/* This function uses the old hash, which is fixed on 10 bits (1024 buckets) */ |
1247 | 60 |
return PATHFIND_HASH_TILE(key1); |
61 |
} |
|
2075
21d2986569d1
(svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents:
2049
diff
changeset
|
62 |
#endif |
1247 | 63 |
|
1950
aeb6067adc30
(svn r2456) * Prettyfied npf.c using enums and wrappers from rail.h.
matthijs
parents:
1945
diff
changeset
|
64 |
/** |
aeb6067adc30
(svn r2456) * Prettyfied npf.c using enums and wrappers from rail.h.
matthijs
parents:
1945
diff
changeset
|
65 |
* Calculates a hash value for use in the NPF. |
4434
a08cb4b5c179
(svn r6204) -Cleanup: replace non-indentation with spaces; like '}<TAB>else {' -> '} else {', tabs between code and comment, etc.
rubidium
parents:
4424
diff
changeset
|
66 |
* @param key1 The TileIndex of the tile to hash |
a08cb4b5c179
(svn r6204) -Cleanup: replace non-indentation with spaces; like '}<TAB>else {' -> '} else {', tabs between code and comment, etc.
rubidium
parents:
4424
diff
changeset
|
67 |
* @param key2 The Trackdir of the track on the tile. |
1950
aeb6067adc30
(svn r2456) * Prettyfied npf.c using enums and wrappers from rail.h.
matthijs
parents:
1945
diff
changeset
|
68 |
* |
4434
a08cb4b5c179
(svn r6204) -Cleanup: replace non-indentation with spaces; like '}<TAB>else {' -> '} else {', tabs between code and comment, etc.
rubidium
parents:
4424
diff
changeset
|
69 |
* @todo Think of a better hash. |
1950
aeb6067adc30
(svn r2456) * Prettyfied npf.c using enums and wrappers from rail.h.
matthijs
parents:
1945
diff
changeset
|
70 |
*/ |
1983 | 71 |
static uint NPFHash(uint key1, uint key2) |
1661
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1655
diff
changeset
|
72 |
{ |
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1655
diff
changeset
|
73 |
/* TODO: think of a better hash? */ |
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1655
diff
changeset
|
74 |
uint part1 = TileX(key1) & NPF_HASH_HALFMASK; |
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1655
diff
changeset
|
75 |
uint part2 = TileY(key1) & NPF_HASH_HALFMASK; |
1950
aeb6067adc30
(svn r2456) * Prettyfied npf.c using enums and wrappers from rail.h.
matthijs
parents:
1945
diff
changeset
|
76 |
|
5587
167d9a91ef02
(svn r8038) -Merge: the cpp branch. Effort of KUDr, Celestar, glx, Smoovius, stillunknown and pv2b.
rubidium
parents:
5584
diff
changeset
|
77 |
assert(IsValidTrackdir((Trackdir)key2)); |
1950
aeb6067adc30
(svn r2456) * Prettyfied npf.c using enums and wrappers from rail.h.
matthijs
parents:
1945
diff
changeset
|
78 |
assert(IsValidTile(key1)); |
2951 | 79 |
return ((part1 << NPF_HASH_HALFBITS | part2) + (NPF_HASH_SIZE * key2 / TRACKDIR_END)) % NPF_HASH_SIZE; |
1661
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1655
diff
changeset
|
80 |
} |
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1655
diff
changeset
|
81 |
|
1983 | 82 |
static int32 NPFCalcZero(AyStar* as, AyStarNode* current, OpenListNode* parent) |
83 |
{ |
|
1247 | 84 |
return 0; |
85 |
} |
|
86 |
||
1452
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
87 |
/* Calcs the tile of given station that is closest to a given tile |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
88 |
* for this we assume the station is a rectangle, |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
89 |
* as defined by its top tile (st->train_tile) and its width/height (st->trainst_w, st->trainst_h) |
1247 | 90 |
*/ |
1983 | 91 |
static TileIndex CalcClosestStationTile(StationID station, TileIndex tile) |
92 |
{ |
|
1452
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
93 |
const Station* st = GetStation(station); |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
94 |
|
1983 | 95 |
uint minx = TileX(st->train_tile); // topmost corner of station |
96 |
uint miny = TileY(st->train_tile); |
|
97 |
uint maxx = minx + st->trainst_w - 1; // lowermost corner of station |
|
98 |
uint maxy = miny + st->trainst_h - 1; |
|
99 |
uint x; |
|
100 |
uint y; |
|
1452
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
101 |
|
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
102 |
// we are going the aim for the x coordinate of the closest corner |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
103 |
// but if we are between those coordinates, we will aim for our own x coordinate |
1983 | 104 |
x = clamp(TileX(tile), minx, maxx); |
1452
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
105 |
|
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
106 |
// same for y coordinate, see above comment |
1983 | 107 |
y = clamp(TileY(tile), miny, maxy); |
1452
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
108 |
|
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
109 |
// return the tile of our target coordinates |
1983 | 110 |
return TileXY(x, y); |
2182 | 111 |
} |
1452
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
112 |
|
1677
d534f0c8c845
(svn r2181) - Add: DistanceTrack() to calculate the distance over optimally laid out tracks.
matthijs
parents:
1661
diff
changeset
|
113 |
/* Calcs the heuristic to the target station or tile. For train stations, it |
d534f0c8c845
(svn r2181) - Add: DistanceTrack() to calculate the distance over optimally laid out tracks.
matthijs
parents:
1661
diff
changeset
|
114 |
* takes into account the direction of approach. |
1452
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
115 |
*/ |
1983 | 116 |
static int32 NPFCalcStationOrTileHeuristic(AyStar* as, AyStarNode* current, OpenListNode* parent) |
117 |
{ |
|
1452
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
118 |
NPFFindStationOrTileData* fstd = (NPFFindStationOrTileData*)as->user_target; |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
119 |
NPFFoundTargetData* ftd = (NPFFoundTargetData*)as->user_path; |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
120 |
TileIndex from = current->tile; |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
121 |
TileIndex to = fstd->dest_coords; |
1453 | 122 |
uint dist; |
1452
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
123 |
|
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
124 |
// for train-stations, we are going to aim for the closest station tile |
3135 | 125 |
if (as->user_data[NPF_TYPE] == TRANSPORT_RAIL && fstd->station_index != INVALID_STATION) |
1453 | 126 |
to = CalcClosestStationTile(fstd->station_index, from); |
1452
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
127 |
|
2951 | 128 |
if (as->user_data[NPF_TYPE] == TRANSPORT_ROAD) { |
1677
d534f0c8c845
(svn r2181) - Add: DistanceTrack() to calculate the distance over optimally laid out tracks.
matthijs
parents:
1661
diff
changeset
|
129 |
/* Since roads only have diagonal pieces, we use manhattan distance here */ |
d534f0c8c845
(svn r2181) - Add: DistanceTrack() to calculate the distance over optimally laid out tracks.
matthijs
parents:
1661
diff
changeset
|
130 |
dist = DistanceManhattan(from, to) * NPF_TILE_LENGTH; |
2951 | 131 |
} else { |
1677
d534f0c8c845
(svn r2181) - Add: DistanceTrack() to calculate the distance over optimally laid out tracks.
matthijs
parents:
1661
diff
changeset
|
132 |
/* Ships and trains can also go diagonal, so the minimum distance is shorter */ |
2403
41852918a741
(svn r2929) * Move DistanceTrack from map.c to npf.c and rename to NPFDistanceTrack.
matthijs
parents:
2186
diff
changeset
|
133 |
dist = NPFDistanceTrack(from, to); |
2951 | 134 |
} |
1452
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
135 |
|
5380
8ea58542b6e0
(svn r7565) -Codechange: Rework DEBUG functionality. Look for appropiate debugging levels to
Darkvater
parents:
4561
diff
changeset
|
136 |
DEBUG(npf, 4, "Calculating H for: (%d, %d). Result: %d", TileX(current->tile), TileY(current->tile), dist); |
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
|
137 |
|
2916
b687477adcba
(svn r3472) - [PBS] Remove from trunk. Anyone interested can still find it in branch/pbs. This reverts revisions r3158, r3140, r3075, r2977, r2674, r2625, r2621, r2529, r2528, r2525, r2524, r2519, r2517, r2516, r2507, r2499. (in conjunction with Tron)
Darkvater
parents:
2878
diff
changeset
|
138 |
if (dist < ftd->best_bird_dist) { |
1452
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
139 |
ftd->best_bird_dist = dist; |
5587
167d9a91ef02
(svn r8038) -Merge: the cpp branch. Effort of KUDr, Celestar, glx, Smoovius, stillunknown and pv2b.
rubidium
parents:
5584
diff
changeset
|
140 |
ftd->best_trackdir = (Trackdir)current->user_data[NPF_TRACKDIR_CHOICE]; |
1452
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
141 |
} |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
142 |
return dist; |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
143 |
} |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
144 |
|
2951 | 145 |
|
1247 | 146 |
/* Fills AyStarNode.user_data[NPF_TRACKDIRCHOICE] with the chosen direction to |
147 |
* get here, either getting it from the current choice or from the parent's |
|
148 |
* choice */ |
|
1983 | 149 |
static void NPFFillTrackdirChoice(AyStarNode* current, OpenListNode* parent) |
1247 | 150 |
{ |
151 |
if (parent->path.parent == NULL) { |
|
1950
aeb6067adc30
(svn r2456) * Prettyfied npf.c using enums and wrappers from rail.h.
matthijs
parents:
1945
diff
changeset
|
152 |
Trackdir trackdir = (Trackdir)current->direction; |
1247 | 153 |
/* This is a first order decision, so we'd better save the |
154 |
* direction we chose */ |
|
155 |
current->user_data[NPF_TRACKDIR_CHOICE] = trackdir; |
|
5380
8ea58542b6e0
(svn r7565) -Codechange: Rework DEBUG functionality. Look for appropiate debugging levels to
Darkvater
parents:
4561
diff
changeset
|
156 |
DEBUG(npf, 6, "Saving trackdir: 0x%X", trackdir); |
1247 | 157 |
} else { |
2951 | 158 |
/* We've already made the decision, so just save our parent's decision */ |
1247 | 159 |
current->user_data[NPF_TRACKDIR_CHOICE] = parent->path.node.user_data[NPF_TRACKDIR_CHOICE]; |
160 |
} |
|
161 |
} |
|
162 |
||
163 |
/* Will return the cost of the tunnel. If it is an entry, it will return the |
|
164 |
* cost of that tile. If the tile is an exit, it will return the tunnel length |
|
165 |
* including the exit tile. Requires that this is a Tunnel tile */ |
|
1983 | 166 |
static uint NPFTunnelCost(AyStarNode* current) |
167 |
{ |
|
1950
aeb6067adc30
(svn r2456) * Prettyfied npf.c using enums and wrappers from rail.h.
matthijs
parents:
1945
diff
changeset
|
168 |
DiagDirection exitdir = TrackdirToExitdir((Trackdir)current->direction); |
1247 | 169 |
TileIndex tile = current->tile; |
3154 | 170 |
if (GetTunnelDirection(tile) == ReverseDiagDir(exitdir)) { |
1247 | 171 |
/* We just popped out if this tunnel, since were |
172 |
* facing the tunnel exit */ |
|
173 |
FindLengthOfTunnelResult flotr; |
|
3147
fc76d566a68e
(svn r3767) Move all direction related enums and functions to a separate header
tron
parents:
3135
diff
changeset
|
174 |
flotr = FindLengthOfTunnel(tile, ReverseDiagDir(exitdir)); |
1247 | 175 |
return flotr.length * NPF_TILE_LENGTH; |
176 |
//TODO: Penalty for tunnels? |
|
177 |
} else { |
|
178 |
/* We are entering the tunnel, the enter tile is just a |
|
179 |
* straight track */ |
|
180 |
return NPF_TILE_LENGTH; |
|
181 |
} |
|
182 |
} |
|
183 |
||
5385
3868f2e6db9b
(svn r7573) -Merged the bridge branch. Allows to build bridges of arbitrary rail/road combinations (including signals)
celestar
parents:
5380
diff
changeset
|
184 |
static inline uint NPFBridgeCost(AyStarNode *current) |
3868f2e6db9b
(svn r7573) -Merged the bridge branch. Allows to build bridges of arbitrary rail/road combinations (including signals)
celestar
parents:
5380
diff
changeset
|
185 |
{ |
3868f2e6db9b
(svn r7573) -Merged the bridge branch. Allows to build bridges of arbitrary rail/road combinations (including signals)
celestar
parents:
5380
diff
changeset
|
186 |
return NPF_TILE_LENGTH * GetBridgeLength(current->tile, GetOtherBridgeEnd(current->tile)); |
3868f2e6db9b
(svn r7573) -Merged the bridge branch. Allows to build bridges of arbitrary rail/road combinations (including signals)
celestar
parents:
5380
diff
changeset
|
187 |
} |
3868f2e6db9b
(svn r7573) -Merged the bridge branch. Allows to build bridges of arbitrary rail/road combinations (including signals)
celestar
parents:
5380
diff
changeset
|
188 |
|
1983 | 189 |
static uint NPFSlopeCost(AyStarNode* current) |
190 |
{ |
|
5587
167d9a91ef02
(svn r8038) -Merge: the cpp branch. Effort of KUDr, Celestar, glx, Smoovius, stillunknown and pv2b.
rubidium
parents:
5584
diff
changeset
|
191 |
TileIndex next = current->tile + TileOffsByDiagDir(TrackdirToExitdir((Trackdir)current->direction)); |
1503
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
192 |
int x,y; |
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
193 |
int8 z1,z2; |
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
194 |
|
1942
c5d5cf5b0263
(svn r2448) General cleanup of rail related code, more to follow.
matthijs
parents:
1941
diff
changeset
|
195 |
x = TileX(current->tile) * TILE_SIZE; |
c5d5cf5b0263
(svn r2448) General cleanup of rail related code, more to follow.
matthijs
parents:
1941
diff
changeset
|
196 |
y = TileY(current->tile) * TILE_SIZE; |
c5d5cf5b0263
(svn r2448) General cleanup of rail related code, more to follow.
matthijs
parents:
1941
diff
changeset
|
197 |
/* get the height of the center of the current tile */ |
3993
1ac50ad7e554
(svn r5196) - Codechange: replace two incorrect uses of TILE_HEIGHT with TILE_SIZE / 2
peter1138
parents:
3977
diff
changeset
|
198 |
z1 = GetSlopeZ(x + TILE_SIZE / 2, y + TILE_SIZE / 2); |
1503
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
199 |
|
1942
c5d5cf5b0263
(svn r2448) General cleanup of rail related code, more to follow.
matthijs
parents:
1941
diff
changeset
|
200 |
x = TileX(next) * TILE_SIZE; |
c5d5cf5b0263
(svn r2448) General cleanup of rail related code, more to follow.
matthijs
parents:
1941
diff
changeset
|
201 |
y = TileY(next) * TILE_SIZE; |
c5d5cf5b0263
(svn r2448) General cleanup of rail related code, more to follow.
matthijs
parents:
1941
diff
changeset
|
202 |
/* get the height of the center of the next tile */ |
3993
1ac50ad7e554
(svn r5196) - Codechange: replace two incorrect uses of TILE_HEIGHT with TILE_SIZE / 2
peter1138
parents:
3977
diff
changeset
|
203 |
z2 = GetSlopeZ(x + TILE_SIZE / 2, y + TILE_SIZE / 2); |
1503
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
204 |
|
2951 | 205 |
if (z2 - z1 > 1) { |
1247 | 206 |
/* Slope up */ |
207 |
return _patches.npf_rail_slope_penalty; |
|
208 |
} |
|
209 |
return 0; |
|
210 |
/* Should we give a bonus for slope down? Probably not, we |
|
211 |
* could just substract that bonus from the penalty, because |
|
212 |
* there is only one level of steepness... */ |
|
213 |
} |
|
214 |
||
3532
2eb08a39d78d
(svn r4389) -Fix: [NPF] Don't mark tiles when debugging in multiplayer, this will cause desyncs.
matthijs
parents:
3531
diff
changeset
|
215 |
/** |
2eb08a39d78d
(svn r4389) -Fix: [NPF] Don't mark tiles when debugging in multiplayer, this will cause desyncs.
matthijs
parents:
3531
diff
changeset
|
216 |
* Mark tiles by mowing the grass when npf debug level >= 1. |
2eb08a39d78d
(svn r4389) -Fix: [NPF] Don't mark tiles when debugging in multiplayer, this will cause desyncs.
matthijs
parents:
3531
diff
changeset
|
217 |
* Will not work for multiplayer games, since it can (will) cause desyncs. |
2eb08a39d78d
(svn r4389) -Fix: [NPF] Don't mark tiles when debugging in multiplayer, this will cause desyncs.
matthijs
parents:
3531
diff
changeset
|
218 |
*/ |
1983 | 219 |
static void NPFMarkTile(TileIndex tile) |
220 |
{ |
|
4077
d4d440dd8925
(svn r5391) Miscellaneous, mostly bracing and whitespace, nothing spectacular
tron
parents:
4048
diff
changeset
|
221 |
#ifndef NO_DEBUG_MESSAGES |
3532
2eb08a39d78d
(svn r4389) -Fix: [NPF] Don't mark tiles when debugging in multiplayer, this will cause desyncs.
matthijs
parents:
3531
diff
changeset
|
222 |
if (_debug_npf_level < 1 || _networking) return; |
3017
a75caf4efa2d
(svn r3597) Miscellaneous (I like that word) changes: Fix some indentation, add consts, reduce indentation level by short-circuit logic, convert if cascades to switch, whitespace, bracing, plus some minor stuff
tron
parents:
2952
diff
changeset
|
223 |
switch (GetTileType(tile)) { |
a75caf4efa2d
(svn r3597) Miscellaneous (I like that word) changes: Fix some indentation, add consts, reduce indentation level by short-circuit logic, convert if cascades to switch, whitespace, bracing, plus some minor stuff
tron
parents:
2952
diff
changeset
|
224 |
case MP_RAILWAY: |
a75caf4efa2d
(svn r3597) Miscellaneous (I like that word) changes: Fix some indentation, add consts, reduce indentation level by short-circuit logic, convert if cascades to switch, whitespace, bracing, plus some minor stuff
tron
parents:
2952
diff
changeset
|
225 |
/* DEBUG: mark visited tiles by mowing the grass under them ;-) */ |
a75caf4efa2d
(svn r3597) Miscellaneous (I like that word) changes: Fix some indentation, add consts, reduce indentation level by short-circuit logic, convert if cascades to switch, whitespace, bracing, plus some minor stuff
tron
parents:
2952
diff
changeset
|
226 |
if (!IsTileDepotType(tile, TRANSPORT_RAIL)) { |
3531
38916043bbac
(svn r4387) -Codechange: Use map accessors even for debugging purposes (npf).
celestar
parents:
3520
diff
changeset
|
227 |
SetRailGroundType(tile, RAIL_GROUND_BARREN); |
3017
a75caf4efa2d
(svn r3597) Miscellaneous (I like that word) changes: Fix some indentation, add consts, reduce indentation level by short-circuit logic, convert if cascades to switch, whitespace, bracing, plus some minor stuff
tron
parents:
2952
diff
changeset
|
228 |
MarkTileDirtyByTile(tile); |
a75caf4efa2d
(svn r3597) Miscellaneous (I like that word) changes: Fix some indentation, add consts, reduce indentation level by short-circuit logic, convert if cascades to switch, whitespace, bracing, plus some minor stuff
tron
parents:
2952
diff
changeset
|
229 |
} |
a75caf4efa2d
(svn r3597) Miscellaneous (I like that word) changes: Fix some indentation, add consts, reduce indentation level by short-circuit logic, convert if cascades to switch, whitespace, bracing, plus some minor stuff
tron
parents:
2952
diff
changeset
|
230 |
break; |
a75caf4efa2d
(svn r3597) Miscellaneous (I like that word) changes: Fix some indentation, add consts, reduce indentation level by short-circuit logic, convert if cascades to switch, whitespace, bracing, plus some minor stuff
tron
parents:
2952
diff
changeset
|
231 |
|
a75caf4efa2d
(svn r3597) Miscellaneous (I like that word) changes: Fix some indentation, add consts, reduce indentation level by short-circuit logic, convert if cascades to switch, whitespace, bracing, plus some minor stuff
tron
parents:
2952
diff
changeset
|
232 |
case MP_STREET: |
a75caf4efa2d
(svn r3597) Miscellaneous (I like that word) changes: Fix some indentation, add consts, reduce indentation level by short-circuit logic, convert if cascades to switch, whitespace, bracing, plus some minor stuff
tron
parents:
2952
diff
changeset
|
233 |
if (!IsTileDepotType(tile, TRANSPORT_ROAD)) { |
4048 | 234 |
SetRoadside(tile, ROADSIDE_BARREN); |
3017
a75caf4efa2d
(svn r3597) Miscellaneous (I like that word) changes: Fix some indentation, add consts, reduce indentation level by short-circuit logic, convert if cascades to switch, whitespace, bracing, plus some minor stuff
tron
parents:
2952
diff
changeset
|
235 |
MarkTileDirtyByTile(tile); |
a75caf4efa2d
(svn r3597) Miscellaneous (I like that word) changes: Fix some indentation, add consts, reduce indentation level by short-circuit logic, convert if cascades to switch, whitespace, bracing, plus some minor stuff
tron
parents:
2952
diff
changeset
|
236 |
} |
a75caf4efa2d
(svn r3597) Miscellaneous (I like that word) changes: Fix some indentation, add consts, reduce indentation level by short-circuit logic, convert if cascades to switch, whitespace, bracing, plus some minor stuff
tron
parents:
2952
diff
changeset
|
237 |
break; |
a75caf4efa2d
(svn r3597) Miscellaneous (I like that word) changes: Fix some indentation, add consts, reduce indentation level by short-circuit logic, convert if cascades to switch, whitespace, bracing, plus some minor stuff
tron
parents:
2952
diff
changeset
|
238 |
|
a75caf4efa2d
(svn r3597) Miscellaneous (I like that word) changes: Fix some indentation, add consts, reduce indentation level by short-circuit logic, convert if cascades to switch, whitespace, bracing, plus some minor stuff
tron
parents:
2952
diff
changeset
|
239 |
default: |
a75caf4efa2d
(svn r3597) Miscellaneous (I like that word) changes: Fix some indentation, add consts, reduce indentation level by short-circuit logic, convert if cascades to switch, whitespace, bracing, plus some minor stuff
tron
parents:
2952
diff
changeset
|
240 |
break; |
a75caf4efa2d
(svn r3597) Miscellaneous (I like that word) changes: Fix some indentation, add consts, reduce indentation level by short-circuit logic, convert if cascades to switch, whitespace, bracing, plus some minor stuff
tron
parents:
2952
diff
changeset
|
241 |
} |
1678
187385f01cc9
(svn r2182) - Add: [NPF] There is now a debug class for NPF. Use -d npf<level> to enable debugging printouts from npf.
matthijs
parents:
1677
diff
changeset
|
242 |
#endif |
1247 | 243 |
} |
244 |
||
1983 | 245 |
static int32 NPFWaterPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent) |
246 |
{ |
|
1247 | 247 |
//TileIndex tile = current->tile; |
248 |
int32 cost = 0; |
|
1950
aeb6067adc30
(svn r2456) * Prettyfied npf.c using enums and wrappers from rail.h.
matthijs
parents:
1945
diff
changeset
|
249 |
Trackdir trackdir = (Trackdir)current->direction; |
1247 | 250 |
|
251 |
cost = _trackdir_length[trackdir]; /* Should be different for diagonal tracks */ |
|
252 |
||
1950
aeb6067adc30
(svn r2456) * Prettyfied npf.c using enums and wrappers from rail.h.
matthijs
parents:
1945
diff
changeset
|
253 |
if (IsBuoyTile(current->tile) && IsDiagonalTrackdir(trackdir)) |
1751
009a240d035a
(svn r2255) - Fix: [ 9680363 ] [NPF] Broken buoy handling for ships
matthijs
parents:
1749
diff
changeset
|
254 |
cost += _patches.npf_buoy_penalty; /* A small penalty for going over buoys */ |
009a240d035a
(svn r2255) - Fix: [ 9680363 ] [NPF] Broken buoy handling for ships
matthijs
parents:
1749
diff
changeset
|
255 |
|
1950
aeb6067adc30
(svn r2456) * Prettyfied npf.c using enums and wrappers from rail.h.
matthijs
parents:
1945
diff
changeset
|
256 |
if (current->direction != NextTrackdir((Trackdir)parent->path.node.direction)) |
1751
009a240d035a
(svn r2255) - Fix: [ 9680363 ] [NPF] Broken buoy handling for ships
matthijs
parents:
1749
diff
changeset
|
257 |
cost += _patches.npf_water_curve_penalty; |
009a240d035a
(svn r2255) - Fix: [ 9680363 ] [NPF] Broken buoy handling for ships
matthijs
parents:
1749
diff
changeset
|
258 |
|
009a240d035a
(svn r2255) - Fix: [ 9680363 ] [NPF] Broken buoy handling for ships
matthijs
parents:
1749
diff
changeset
|
259 |
/* TODO More penalties? */ |
1247 | 260 |
|
261 |
return cost; |
|
262 |
} |
|
263 |
||
264 |
/* Determine the cost of this node, for road tracks */ |
|
1983 | 265 |
static int32 NPFRoadPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent) |
266 |
{ |
|
1247 | 267 |
TileIndex tile = current->tile; |
268 |
int32 cost = 0; |
|
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:
1753
diff
changeset
|
269 |
|
1247 | 270 |
/* Determine base length */ |
271 |
switch (GetTileType(tile)) { |
|
272 |
case MP_TUNNELBRIDGE: |
|
5385
3868f2e6db9b
(svn r7573) -Merged the bridge branch. Allows to build bridges of arbitrary rail/road combinations (including signals)
celestar
parents:
5380
diff
changeset
|
273 |
cost = IsTunnel(tile) ? NPFTunnelCost(current) : NPFBridgeCost(current); |
2605
0e7993eabf16
(svn r3142) Remove a now invalid case fall-through and use helper function instead of map access.
peter1138
parents:
2493
diff
changeset
|
274 |
break; |
2951 | 275 |
|
1247 | 276 |
case MP_STREET: |
277 |
cost = NPF_TILE_LENGTH; |
|
2006
9d5d7fd428c2
(svn r2514) - Codechange: [NPF] Move the checking of railtype into a funciton IsCompatibleRail().
matthijs
parents:
1983
diff
changeset
|
278 |
/* Increase the cost for level crossings */ |
4000
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3993
diff
changeset
|
279 |
if (IsLevelCrossing(tile)) cost += _patches.npf_crossing_penalty; |
1247 | 280 |
break; |
2951 | 281 |
|
1247 | 282 |
default: |
283 |
break; |
|
284 |
} |
|
285 |
||
286 |
/* Determine extra costs */ |
|
287 |
||
288 |
/* Check for slope */ |
|
289 |
cost += NPFSlopeCost(current); |
|
290 |
||
1941
ca268f8837df
(svn r2447) * Add: [NPF] Penalty for road vehicles making turns.
matthijs
parents:
1927
diff
changeset
|
291 |
/* Check for turns. Road vehicles only really drive diagonal, turns are |
ca268f8837df
(svn r2447) * Add: [NPF] Penalty for road vehicles making turns.
matthijs
parents:
1927
diff
changeset
|
292 |
* represented by non-diagonal tracks */ |
5587
167d9a91ef02
(svn r8038) -Merge: the cpp branch. Effort of KUDr, Celestar, glx, Smoovius, stillunknown and pv2b.
rubidium
parents:
5584
diff
changeset
|
293 |
if (!IsDiagonalTrackdir((Trackdir)current->direction)) |
1941
ca268f8837df
(svn r2447) * Add: [NPF] Penalty for road vehicles making turns.
matthijs
parents:
1927
diff
changeset
|
294 |
cost += _patches.npf_road_curve_penalty; |
1247 | 295 |
|
296 |
NPFMarkTile(tile); |
|
5380
8ea58542b6e0
(svn r7565) -Codechange: Rework DEBUG functionality. Look for appropiate debugging levels to
Darkvater
parents:
4561
diff
changeset
|
297 |
DEBUG(npf, 4, "Calculating G for: (%d, %d). Result: %d", TileX(current->tile), TileY(current->tile), cost); |
1247 | 298 |
return cost; |
299 |
} |
|
300 |
||
301 |
||
302 |
/* Determine the cost of this node, for railway tracks */ |
|
1983 | 303 |
static int32 NPFRailPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent) |
304 |
{ |
|
1247 | 305 |
TileIndex tile = current->tile; |
1950
aeb6067adc30
(svn r2456) * Prettyfied npf.c using enums and wrappers from rail.h.
matthijs
parents:
1945
diff
changeset
|
306 |
Trackdir trackdir = (Trackdir)current->direction; |
1247 | 307 |
int32 cost = 0; |
3017
a75caf4efa2d
(svn r3597) Miscellaneous (I like that word) changes: Fix some indentation, add consts, reduce indentation level by short-circuit logic, convert if cascades to switch, whitespace, bracing, plus some minor stuff
tron
parents:
2952
diff
changeset
|
308 |
/* HACK: We create a OpenListNode manually, so we can call EndNodeCheck */ |
1617
c3d3caad6d1e
(svn r2121) -Fix: changed the 2nd param of AyStar_EndNodeCheck back to what it should be
truelight
parents:
1503
diff
changeset
|
309 |
OpenListNode new_node; |
c3d3caad6d1e
(svn r2121) -Fix: changed the 2nd param of AyStar_EndNodeCheck back to what it should be
truelight
parents:
1503
diff
changeset
|
310 |
|
1247 | 311 |
/* Determine base length */ |
312 |
switch (GetTileType(tile)) { |
|
313 |
case MP_TUNNELBRIDGE: |
|
5385
3868f2e6db9b
(svn r7573) -Merged the bridge branch. Allows to build bridges of arbitrary rail/road combinations (including signals)
celestar
parents:
5380
diff
changeset
|
314 |
cost = IsTunnel(tile) ? NPFTunnelCost(current) : NPFBridgeCost(current); |
3868f2e6db9b
(svn r7573) -Merged the bridge branch. Allows to build bridges of arbitrary rail/road combinations (including signals)
celestar
parents:
5380
diff
changeset
|
315 |
break; |
2951 | 316 |
|
1247 | 317 |
case MP_RAILWAY: |
318 |
cost = _trackdir_length[trackdir]; /* Should be different for diagonal tracks */ |
|
319 |
break; |
|
2951 | 320 |
|
1247 | 321 |
case MP_STREET: /* Railway crossing */ |
322 |
cost = NPF_TILE_LENGTH; |
|
323 |
break; |
|
2951 | 324 |
|
1503
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
325 |
case MP_STATION: |
2951 | 326 |
/* We give a station tile a penalty. Logically we would only want to give |
327 |
* station tiles that are not our destination this penalty. This would |
|
328 |
* discourage trains to drive through busy stations. But, we can just |
|
329 |
* give any station tile a penalty, because every possible route will get |
|
330 |
* this penalty exactly once, on its end tile (if it's a station) and it |
|
331 |
* will therefore not make a difference. */ |
|
1503
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
332 |
cost = NPF_TILE_LENGTH + _patches.npf_rail_station_penalty; |
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
333 |
break; |
2951 | 334 |
|
1247 | 335 |
default: |
336 |
break; |
|
337 |
} |
|
338 |
||
339 |
/* Determine extra costs */ |
|
340 |
||
1459
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
341 |
/* Check for signals */ |
1944
dd9cba5fab2a
(svn r2450) * Codechange: Replaced all uses of the arrays in tile.h with calls to the associated wrapper functions.
matthijs
parents:
1942
diff
changeset
|
342 |
if (IsTileType(tile, MP_RAILWAY) && HasSignalOnTrackdir(tile, trackdir)) { |
1459
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
343 |
/* Ordinary track with signals */ |
3520
a288391e66a3
(svn r4376) -Codechange Renamed GetSignalState to GetSignalStateByTrackdir
celestar
parents:
3498
diff
changeset
|
344 |
if (GetSignalStateByTrackdir(tile, trackdir) == SIGNAL_STATE_RED) { |
1247 | 345 |
/* Signal facing us is red */ |
1459
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
346 |
if (!NPFGetFlag(current, NPF_FLAG_SEEN_SIGNAL)) { |
1247 | 347 |
/* Penalize the first signal we |
348 |
* encounter, if it is red */ |
|
1643
420cad9e62e4
(svn r2147) - Add: [NPF] Give red presignal exit signals a different (higher) penalty, to discourage trains from waiting at presignal exits.
matthijs
parents:
1617
diff
changeset
|
349 |
|
420cad9e62e4
(svn r2147) - Add: [NPF] Give red presignal exit signals a different (higher) penalty, to discourage trains from waiting at presignal exits.
matthijs
parents:
1617
diff
changeset
|
350 |
/* Is this a presignal exit or combo? */ |
3238
9ebec0a611ee
(svn r3912) Move the signal type enum and GetSignalType() to rail_map.h; also add SetSignalType() and use the functions
tron
parents:
3235
diff
changeset
|
351 |
SignalType sigtype = GetSignalType(tile); |
2951 | 352 |
if (sigtype == SIGTYPE_EXIT || sigtype == SIGTYPE_COMBO) { |
1643
420cad9e62e4
(svn r2147) - Add: [NPF] Give red presignal exit signals a different (higher) penalty, to discourage trains from waiting at presignal exits.
matthijs
parents:
1617
diff
changeset
|
353 |
/* Penalise exit and combo signals differently (heavier) */ |
420cad9e62e4
(svn r2147) - Add: [NPF] Give red presignal exit signals a different (higher) penalty, to discourage trains from waiting at presignal exits.
matthijs
parents:
1617
diff
changeset
|
354 |
cost += _patches.npf_rail_firstred_exit_penalty; |
2951 | 355 |
} else { |
1643
420cad9e62e4
(svn r2147) - Add: [NPF] Give red presignal exit signals a different (higher) penalty, to discourage trains from waiting at presignal exits.
matthijs
parents:
1617
diff
changeset
|
356 |
cost += _patches.npf_rail_firstred_penalty; |
2951 | 357 |
} |
1247 | 358 |
} |
1459
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
359 |
/* Record the state of this signal */ |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
360 |
NPFSetFlag(current, NPF_FLAG_LAST_SIGNAL_RED, true); |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
361 |
} else { |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
362 |
/* Record the state of this signal */ |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
363 |
NPFSetFlag(current, NPF_FLAG_LAST_SIGNAL_RED, false); |
1247 | 364 |
} |
1459
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
365 |
NPFSetFlag(current, NPF_FLAG_SEEN_SIGNAL, true); |
1247 | 366 |
} |
367 |
||
1459
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
368 |
/* Penalise the tile if it is a target tile and the last signal was |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
369 |
* red */ |
1950
aeb6067adc30
(svn r2456) * Prettyfied npf.c using enums and wrappers from rail.h.
matthijs
parents:
1945
diff
changeset
|
370 |
/* HACK: We create a new_node here so we can call EndNodeCheck. Ugly as hell |
aeb6067adc30
(svn r2456) * Prettyfied npf.c using enums and wrappers from rail.h.
matthijs
parents:
1945
diff
changeset
|
371 |
* of course... */ |
1617
c3d3caad6d1e
(svn r2121) -Fix: changed the 2nd param of AyStar_EndNodeCheck back to what it should be
truelight
parents:
1503
diff
changeset
|
372 |
new_node.path.node = *current; |
1950
aeb6067adc30
(svn r2456) * Prettyfied npf.c using enums and wrappers from rail.h.
matthijs
parents:
1945
diff
changeset
|
373 |
if (as->EndNodeCheck(as, &new_node) == AYSTAR_FOUND_END_NODE && NPFGetFlag(current, NPF_FLAG_LAST_SIGNAL_RED)) |
1459
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
374 |
cost += _patches.npf_rail_lastred_penalty; |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
375 |
|
1247 | 376 |
/* Check for slope */ |
377 |
cost += NPFSlopeCost(current); |
|
378 |
||
379 |
/* Check for turns */ |
|
1950
aeb6067adc30
(svn r2456) * Prettyfied npf.c using enums and wrappers from rail.h.
matthijs
parents:
1945
diff
changeset
|
380 |
if (current->direction != NextTrackdir((Trackdir)parent->path.node.direction)) |
1460 | 381 |
cost += _patches.npf_rail_curve_penalty; |
382 |
//TODO, with realistic acceleration, also the amount of straight track between |
|
383 |
// curves should be taken into account, as this affects the speed limit. |
|
1247 | 384 |
|
2916
b687477adcba
(svn r3472) - [PBS] Remove from trunk. Anyone interested can still find it in branch/pbs. This reverts revisions r3158, r3140, r3075, r2977, r2674, r2625, r2621, r2529, r2528, r2525, r2524, r2519, r2517, r2516, r2507, r2499. (in conjunction with Tron)
Darkvater
parents:
2878
diff
changeset
|
385 |
/* Check for reverse in depot */ |
b687477adcba
(svn r3472) - [PBS] Remove from trunk. Anyone interested can still find it in branch/pbs. This reverts revisions r3158, r3140, r3075, r2977, r2674, r2625, r2621, r2529, r2528, r2525, r2524, r2519, r2517, r2516, r2507, r2499. (in conjunction with Tron)
Darkvater
parents:
2878
diff
changeset
|
386 |
if (IsTileDepotType(tile, TRANSPORT_RAIL) && as->EndNodeCheck(as, &new_node) != AYSTAR_FOUND_END_NODE) { |
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:
1753
diff
changeset
|
387 |
/* Penalise any depot tile that is not the last tile in the path. This |
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:
1753
diff
changeset
|
388 |
* _should_ penalise every occurence of reversing in a depot (and only |
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:
1753
diff
changeset
|
389 |
* that) */ |
2916
b687477adcba
(svn r3472) - [PBS] Remove from trunk. Anyone interested can still find it in branch/pbs. This reverts revisions r3158, r3140, r3075, r2977, r2674, r2625, r2621, r2529, r2528, r2525, r2524, r2519, r2517, r2516, r2507, r2499. (in conjunction with Tron)
Darkvater
parents:
2878
diff
changeset
|
390 |
cost += _patches.npf_rail_depot_reverse_penalty; |
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
|
391 |
} |
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:
1753
diff
changeset
|
392 |
|
1247 | 393 |
/* Check for occupied track */ |
394 |
//TODO |
|
395 |
||
396 |
NPFMarkTile(tile); |
|
5380
8ea58542b6e0
(svn r7565) -Codechange: Rework DEBUG functionality. Look for appropiate debugging levels to
Darkvater
parents:
4561
diff
changeset
|
397 |
DEBUG(npf, 4, "Calculating G for: (%d, %d). Result: %d", TileX(current->tile), TileY(current->tile), cost); |
1247 | 398 |
return cost; |
399 |
} |
|
400 |
||
401 |
/* Will find any depot */ |
|
1983 | 402 |
static int32 NPFFindDepot(AyStar* as, OpenListNode *current) |
403 |
{ |
|
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:
1753
diff
changeset
|
404 |
/* It's not worth caching the result with NPF_FLAG_IS_TARGET here as below, |
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:
1753
diff
changeset
|
405 |
* since checking the cache not that much faster than the actual check */ |
5587
167d9a91ef02
(svn r8038) -Merge: the cpp branch. Effort of KUDr, Celestar, glx, Smoovius, stillunknown and pv2b.
rubidium
parents:
5584
diff
changeset
|
406 |
return IsTileDepotType(current->path.node.tile, (TransportType)as->user_data[NPF_TYPE]) ? |
4000
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3993
diff
changeset
|
407 |
AYSTAR_FOUND_END_NODE : AYSTAR_DONE; |
1247 | 408 |
} |
409 |
||
410 |
/* Will find a station identified using the NPFFindStationOrTileData */ |
|
1983 | 411 |
static int32 NPFFindStationOrTile(AyStar* as, OpenListNode *current) |
412 |
{ |
|
1464
fe5fcc14b2a2
(svn r1968) - Fix: [NPF] Mixed declarations and statements
matthijs
parents:
1463
diff
changeset
|
413 |
NPFFindStationOrTileData* fstd = (NPFFindStationOrTileData*)as->user_target; |
1617
c3d3caad6d1e
(svn r2121) -Fix: changed the 2nd param of AyStar_EndNodeCheck back to what it should be
truelight
parents:
1503
diff
changeset
|
414 |
AyStarNode *node = ¤t->path.node; |
1464
fe5fcc14b2a2
(svn r1968) - Fix: [NPF] Mixed declarations and statements
matthijs
parents:
1463
diff
changeset
|
415 |
TileIndex tile = node->tile; |
1459
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
416 |
|
1247 | 417 |
/* If GetNeighbours said we could get here, we assume the station type |
418 |
* is correct */ |
|
1459
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
419 |
if ( |
3135 | 420 |
(fstd->station_index == INVALID_STATION && tile == fstd->dest_coords) || /* We've found the tile, or */ |
3315
c9d989783c55
(svn r4079) Add GetSation{Index,ByTile}() to get the station index resp. the station from a tile
tron
parents:
3309
diff
changeset
|
421 |
(IsTileType(tile, MP_STATION) && GetStationIndex(tile) == fstd->station_index) /* the station */ |
1459
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
422 |
) { |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
423 |
return AYSTAR_FOUND_END_NODE; |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
424 |
} else { |
1247 | 425 |
return AYSTAR_DONE; |
1459
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
426 |
} |
1247 | 427 |
} |
428 |
||
429 |
/* To be called when current contains the (shortest route to) the target node. |
|
430 |
* Will fill the contents of the NPFFoundTargetData using |
|
431 |
* AyStarNode[NPF_TRACKDIR_CHOICE]. |
|
432 |
*/ |
|
1983 | 433 |
static void NPFSaveTargetData(AyStar* as, OpenListNode* current) |
434 |
{ |
|
1247 | 435 |
NPFFoundTargetData* ftd = (NPFFoundTargetData*)as->user_path; |
1950
aeb6067adc30
(svn r2456) * Prettyfied npf.c using enums and wrappers from rail.h.
matthijs
parents:
1945
diff
changeset
|
436 |
ftd->best_trackdir = (Trackdir)current->path.node.user_data[NPF_TRACKDIR_CHOICE]; |
1247 | 437 |
ftd->best_path_dist = current->g; |
438 |
ftd->best_bird_dist = 0; |
|
439 |
ftd->node = current->path.node; |
|
440 |
} |
|
441 |
||
1967
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
442 |
/** |
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
443 |
* Finds out if a given player's vehicles are allowed to enter a given tile. |
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
444 |
* @param owner The owner of the vehicle. |
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
445 |
* @param tile The tile that is about to be entered. |
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
446 |
* @param enterdir The direction from which the vehicle wants to enter the tile. |
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
447 |
* @return true if the vehicle can enter the tile. |
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
448 |
* @todo This function should be used in other places than just NPF, |
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
449 |
* maybe moved to another file too. |
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
450 |
*/ |
1983 | 451 |
static bool VehicleMayEnterTile(Owner owner, TileIndex tile, DiagDirection enterdir) |
1967
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
452 |
{ |
2951 | 453 |
if (IsTileType(tile, MP_RAILWAY) || /* Rail tile (also rail depot) */ |
3442
41d828e2d5ab
(svn r4272) -Codechange: Moved the map-accessing stuff from station.h into station_map.h
celestar
parents:
3404
diff
changeset
|
454 |
IsRailwayStationTile(tile) || /* Rail station tile */ |
2951 | 455 |
IsTileDepotType(tile, TRANSPORT_ROAD) || /* Road depot tile */ |
3404
eb8ebfe5df67
(svn r4215) -Codechange: Renamed *RoadStation* functions to *RoadStop* and moved them to station_map.h to keep consistency
celestar
parents:
3355
diff
changeset
|
456 |
IsRoadStopTile(tile) || /* Road station tile */ |
2951 | 457 |
IsTileDepotType(tile, TRANSPORT_WATER)) { /* Water depot tile */ |
1967
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
458 |
return IsTileOwner(tile, owner); /* You need to own these tiles entirely to use them */ |
2951 | 459 |
} |
1967
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
460 |
|
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
461 |
switch (GetTileType(tile)) { |
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
462 |
case MP_STREET: |
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
463 |
/* rail-road crossing : are we looking at the railway part? */ |
3498
ece6348becad
(svn r4349) Remove GetCrossingTransportType(), it's slightly overkill
tron
parents:
3442
diff
changeset
|
464 |
if (IsLevelCrossing(tile) && |
ece6348becad
(svn r4349) Remove GetCrossingTransportType(), it's slightly overkill
tron
parents:
3442
diff
changeset
|
465 |
DiagDirToAxis(enterdir) != GetCrossingRoadAxis(tile)) { |
1967
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
466 |
return IsTileOwner(tile, owner); /* Railway needs owner check, while the street is public */ |
3498
ece6348becad
(svn r4349) Remove GetCrossingTransportType(), it's slightly overkill
tron
parents:
3442
diff
changeset
|
467 |
} |
1967
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
468 |
break; |
2951 | 469 |
|
1967
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
470 |
case MP_TUNNELBRIDGE: |
3184
118a520164e4
(svn r3830) Move IsTunnelTile() from tile.h to tunnel_map.h and add IsTunnel(), which just checks for a tunnel, but not the tile type as IsTunnelTile() does
tron
parents:
3179
diff
changeset
|
471 |
if ((IsTunnel(tile) && GetTunnelTransportType(tile) == TRANSPORT_RAIL) || |
5385
3868f2e6db9b
(svn r7573) -Merged the bridge branch. Allows to build bridges of arbitrary rail/road combinations (including signals)
celestar
parents:
5380
diff
changeset
|
472 |
(IsBridge(tile) && GetBridgeTransportType(tile) == TRANSPORT_RAIL)) { |
1967
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
473 |
return IsTileOwner(tile, owner); |
2951 | 474 |
} |
1967
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
475 |
break; |
2951 | 476 |
|
1967
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
477 |
default: |
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
478 |
break; |
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
479 |
} |
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
480 |
|
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
481 |
return true; /* no need to check */ |
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
482 |
} |
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
483 |
|
3957
25f4a4f22e05
(svn r5116) Move the overly generic GetDepotDirection() from a header to its only consumer
tron
parents:
3933
diff
changeset
|
484 |
|
25f4a4f22e05
(svn r5116) Move the overly generic GetDepotDirection() from a header to its only consumer
tron
parents:
3933
diff
changeset
|
485 |
/** |
25f4a4f22e05
(svn r5116) Move the overly generic GetDepotDirection() from a header to its only consumer
tron
parents:
3933
diff
changeset
|
486 |
* Returns the direction the exit of the depot on the given tile is facing. |
25f4a4f22e05
(svn r5116) Move the overly generic GetDepotDirection() from a header to its only consumer
tron
parents:
3933
diff
changeset
|
487 |
*/ |
25f4a4f22e05
(svn r5116) Move the overly generic GetDepotDirection() from a header to its only consumer
tron
parents:
3933
diff
changeset
|
488 |
static DiagDirection GetDepotDirection(TileIndex tile, TransportType type) |
25f4a4f22e05
(svn r5116) Move the overly generic GetDepotDirection() from a header to its only consumer
tron
parents:
3933
diff
changeset
|
489 |
{ |
25f4a4f22e05
(svn r5116) Move the overly generic GetDepotDirection() from a header to its only consumer
tron
parents:
3933
diff
changeset
|
490 |
assert(IsTileDepotType(tile, type)); |
25f4a4f22e05
(svn r5116) Move the overly generic GetDepotDirection() from a header to its only consumer
tron
parents:
3933
diff
changeset
|
491 |
|
25f4a4f22e05
(svn r5116) Move the overly generic GetDepotDirection() from a header to its only consumer
tron
parents:
3933
diff
changeset
|
492 |
switch (type) { |
25f4a4f22e05
(svn r5116) Move the overly generic GetDepotDirection() from a header to its only consumer
tron
parents:
3933
diff
changeset
|
493 |
case TRANSPORT_RAIL: return GetRailDepotDirection(tile); |
25f4a4f22e05
(svn r5116) Move the overly generic GetDepotDirection() from a header to its only consumer
tron
parents:
3933
diff
changeset
|
494 |
case TRANSPORT_ROAD: return GetRoadDepotDirection(tile); |
25f4a4f22e05
(svn r5116) Move the overly generic GetDepotDirection() from a header to its only consumer
tron
parents:
3933
diff
changeset
|
495 |
case TRANSPORT_WATER: return GetShipDepotDirection(tile); |
25f4a4f22e05
(svn r5116) Move the overly generic GetDepotDirection() from a header to its only consumer
tron
parents:
3933
diff
changeset
|
496 |
default: return INVALID_DIAGDIR; /* Not reached */ |
25f4a4f22e05
(svn r5116) Move the overly generic GetDepotDirection() from a header to its only consumer
tron
parents:
3933
diff
changeset
|
497 |
} |
25f4a4f22e05
(svn r5116) Move the overly generic GetDepotDirection() from a header to its only consumer
tron
parents:
3933
diff
changeset
|
498 |
} |
25f4a4f22e05
(svn r5116) Move the overly generic GetDepotDirection() from a header to its only consumer
tron
parents:
3933
diff
changeset
|
499 |
|
25f4a4f22e05
(svn r5116) Move the overly generic GetDepotDirection() from a header to its only consumer
tron
parents:
3933
diff
changeset
|
500 |
|
1247 | 501 |
/* Will just follow the results of GetTileTrackStatus concerning where we can |
502 |
* go and where not. Uses AyStar.user_data[NPF_TYPE] as the transport type and |
|
503 |
* an argument to GetTileTrackStatus. Will skip tunnels, meaning that the |
|
1459
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
504 |
* entry and exit are neighbours. Will fill |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
505 |
* AyStarNode.user_data[NPF_TRACKDIR_CHOICE] with an appropriate value, and |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
506 |
* copy AyStarNode.user_data[NPF_NODE_FLAGS] from the parent */ |
1983 | 507 |
static void NPFFollowTrack(AyStar* aystar, OpenListNode* current) |
508 |
{ |
|
1950
aeb6067adc30
(svn r2456) * Prettyfied npf.c using enums and wrappers from rail.h.
matthijs
parents:
1945
diff
changeset
|
509 |
Trackdir src_trackdir = (Trackdir)current->path.node.direction; |
1247 | 510 |
TileIndex src_tile = current->path.node.tile; |
1944
dd9cba5fab2a
(svn r2450) * Codechange: Replaced all uses of the arrays in tile.h with calls to the associated wrapper functions.
matthijs
parents:
1942
diff
changeset
|
511 |
DiagDirection src_exitdir = TrackdirToExitdir(src_trackdir); |
3295
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
512 |
TileIndex dst_tile = INVALID_TILE; |
1950
aeb6067adc30
(svn r2456) * Prettyfied npf.c using enums and wrappers from rail.h.
matthijs
parents:
1945
diff
changeset
|
513 |
int i; |
5587
167d9a91ef02
(svn r8038) -Merge: the cpp branch. Effort of KUDr, Celestar, glx, Smoovius, stillunknown and pv2b.
rubidium
parents:
5584
diff
changeset
|
514 |
uint32 ts; |
167d9a91ef02
(svn r8038) -Merge: the cpp branch. Effort of KUDr, Celestar, glx, Smoovius, stillunknown and pv2b.
rubidium
parents:
5584
diff
changeset
|
515 |
TrackdirBits trackdirbits; |
167d9a91ef02
(svn r8038) -Merge: the cpp branch. Effort of KUDr, Celestar, glx, Smoovius, stillunknown and pv2b.
rubidium
parents:
5584
diff
changeset
|
516 |
TransportType type = (TransportType)aystar->user_data[NPF_TYPE]; |
5385
3868f2e6db9b
(svn r7573) -Merged the bridge branch. Allows to build bridges of arbitrary rail/road combinations (including signals)
celestar
parents:
5380
diff
changeset
|
517 |
bool override_dst_check = false; |
1247 | 518 |
/* Initialize to 0, so we can jump out (return) somewhere an have no neighbours */ |
519 |
aystar->num_neighbours = 0; |
|
5380
8ea58542b6e0
(svn r7565) -Codechange: Rework DEBUG functionality. Look for appropiate debugging levels to
Darkvater
parents:
4561
diff
changeset
|
520 |
DEBUG(npf, 4, "Expanding: (%d, %d, %d) [%d]", TileX(src_tile), TileY(src_tile), src_trackdir, src_tile); |
1247 | 521 |
|
522 |
/* Find dest tile */ |
|
3184
118a520164e4
(svn r3830) Move IsTunnelTile() from tile.h to tunnel_map.h and add IsTunnel(), which just checks for a tunnel, but not the tile type as IsTunnelTile() does
tron
parents:
3179
diff
changeset
|
523 |
if (IsTunnelTile(src_tile) && GetTunnelDirection(src_tile) == src_exitdir) { |
1247 | 524 |
/* This is a tunnel. We know this tunnel is our type, |
525 |
* otherwise we wouldn't have got here. It is also facing us, |
|
526 |
* so we should skip it's body */ |
|
3179 | 527 |
dst_tile = GetOtherTunnelEnd(src_tile); |
5385
3868f2e6db9b
(svn r7573) -Merged the bridge branch. Allows to build bridges of arbitrary rail/road combinations (including signals)
celestar
parents:
5380
diff
changeset
|
528 |
override_dst_check = true; |
3868f2e6db9b
(svn r7573) -Merged the bridge branch. Allows to build bridges of arbitrary rail/road combinations (including signals)
celestar
parents:
5380
diff
changeset
|
529 |
} else if (IsBridgeTile(src_tile) && GetBridgeRampDirection(src_tile) == src_exitdir) { |
3868f2e6db9b
(svn r7573) -Merged the bridge branch. Allows to build bridges of arbitrary rail/road combinations (including signals)
celestar
parents:
5380
diff
changeset
|
530 |
dst_tile = GetOtherBridgeEnd(src_tile); |
3868f2e6db9b
(svn r7573) -Merged the bridge branch. Allows to build bridges of arbitrary rail/road combinations (including signals)
celestar
parents:
5380
diff
changeset
|
531 |
override_dst_check = true; |
3404
eb8ebfe5df67
(svn r4215) -Codechange: Renamed *RoadStation* functions to *RoadStop* and moved them to station_map.h to keep consistency
celestar
parents:
3355
diff
changeset
|
532 |
} else if (type != TRANSPORT_WATER && (IsRoadStopTile(src_tile) || IsTileDepotType(src_tile, type))) { |
3295
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
533 |
/* This is a road station or a train or road depot. We can enter and exit |
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
534 |
* those from one side only. Trackdirs don't support that (yet), so we'll |
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
535 |
* do this here. */ |
1247 | 536 |
|
3295
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
537 |
DiagDirection exitdir; |
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
538 |
/* Find out the exit direction first */ |
3404
eb8ebfe5df67
(svn r4215) -Codechange: Renamed *RoadStation* functions to *RoadStop* and moved them to station_map.h to keep consistency
celestar
parents:
3355
diff
changeset
|
539 |
if (IsRoadStopTile(src_tile)) { |
eb8ebfe5df67
(svn r4215) -Codechange: Renamed *RoadStation* functions to *RoadStop* and moved them to station_map.h to keep consistency
celestar
parents:
3355
diff
changeset
|
540 |
exitdir = GetRoadStopDir(src_tile); |
3333 | 541 |
} else { /* Train or road depot */ |
3295
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
542 |
exitdir = GetDepotDirection(src_tile, type); |
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
543 |
} |
1247 | 544 |
|
3295
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
545 |
/* Let's see if were headed the right way into the depot */ |
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
546 |
if (src_trackdir == DiagdirToDiagTrackdir(ReverseDiagDir(exitdir))) { |
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
547 |
/* We are headed inwards. We cannot go through the back of the depot. |
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
548 |
* For rail, we can now reverse. Reversing for road vehicles is never |
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
549 |
* useful, since you cannot take paths you couldn't take before |
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
550 |
* reversing (as with rail). */ |
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
551 |
if (type == TRANSPORT_RAIL) { |
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
552 |
/* We can only reverse here, so we'll not consider this direction, but |
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
553 |
* jump ahead to the reverse direction. It would be nicer to return |
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
554 |
* one neighbour here (the reverse trackdir of the one we are |
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
555 |
* considering now) and then considering that one to return the tracks |
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
556 |
* outside of the depot. But, because the code layout is cleaner this |
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
557 |
* way, we will just pretend we are reversed already */ |
1944
dd9cba5fab2a
(svn r2450) * Codechange: Replaced all uses of the arrays in tile.h with calls to the associated wrapper functions.
matthijs
parents:
1942
diff
changeset
|
558 |
src_trackdir = ReverseTrackdir(src_trackdir); |
4561 | 559 |
dst_tile = AddTileIndexDiffCWrap(src_tile, TileIndexDiffCByDiagDir(exitdir)); |
3295
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
560 |
} else { |
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
561 |
dst_tile = INVALID_TILE; /* Road vehicle heading inwards: dead end */ |
2951 | 562 |
} |
3309
329e83a739a5
(svn r4071) - Fix: [NPF] Trains & busses were unable to find a route when leaving a depot or bus stop. Small omission from r4023 (fix by glx)
matthijs
parents:
3295
diff
changeset
|
563 |
} else { |
4561 | 564 |
dst_tile = AddTileIndexDiffCWrap(src_tile, TileIndexDiffCByDiagDir(exitdir)); |
1247 | 565 |
} |
3295
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
566 |
} else { |
1247 | 567 |
/* This a normal tile, a bridge, a tunnel exit, etc. */ |
4561 | 568 |
dst_tile = AddTileIndexDiffCWrap(src_tile, TileIndexDiffCByDiagDir(TrackdirToExitdir(src_trackdir))); |
3295
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
569 |
} |
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
570 |
if (dst_tile == INVALID_TILE) { |
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
571 |
/* We reached the border of the map */ |
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
572 |
/* TODO Nicer control flow for this */ |
39a2c60c23e9
(svn r4023) - Fix: [ 1453646 NPF ] Road vehicles planning through the back of depots and stations.
matthijs
parents:
3238
diff
changeset
|
573 |
return; |
1247 | 574 |
} |
575 |
||
1965
71079b9c26a8
(svn r2471) - Fix: [ 1221249 ] [NPF] Vehicles try to drive into a tunnel entrance from above.
matthijs
parents:
1950
diff
changeset
|
576 |
/* I can't enter a tunnel entry/exit tile from a tile above the tunnel. Note |
71079b9c26a8
(svn r2471) - Fix: [ 1221249 ] [NPF] Vehicles try to drive into a tunnel entrance from above.
matthijs
parents:
1950
diff
changeset
|
577 |
* that I can enter the tunnel from a tile below the tunnel entrance. This |
71079b9c26a8
(svn r2471) - Fix: [ 1221249 ] [NPF] Vehicles try to drive into a tunnel entrance from above.
matthijs
parents:
1950
diff
changeset
|
578 |
* solves the problem of vehicles wanting to drive off a tunnel entrance */ |
5385
3868f2e6db9b
(svn r7573) -Merged the bridge branch. Allows to build bridges of arbitrary rail/road combinations (including signals)
celestar
parents:
5380
diff
changeset
|
579 |
if (!override_dst_check) { |
3868f2e6db9b
(svn r7573) -Merged the bridge branch. Allows to build bridges of arbitrary rail/road combinations (including signals)
celestar
parents:
5380
diff
changeset
|
580 |
if (IsTileType(dst_tile, MP_TUNNELBRIDGE)) { |
3868f2e6db9b
(svn r7573) -Merged the bridge branch. Allows to build bridges of arbitrary rail/road combinations (including signals)
celestar
parents:
5380
diff
changeset
|
581 |
if (IsTunnel(dst_tile)) { |
3868f2e6db9b
(svn r7573) -Merged the bridge branch. Allows to build bridges of arbitrary rail/road combinations (including signals)
celestar
parents:
5380
diff
changeset
|
582 |
if (GetTunnelDirection(dst_tile) != src_exitdir) return; |
3868f2e6db9b
(svn r7573) -Merged the bridge branch. Allows to build bridges of arbitrary rail/road combinations (including signals)
celestar
parents:
5380
diff
changeset
|
583 |
} else { |
3868f2e6db9b
(svn r7573) -Merged the bridge branch. Allows to build bridges of arbitrary rail/road combinations (including signals)
celestar
parents:
5380
diff
changeset
|
584 |
if (GetBridgeRampDirection(dst_tile) != src_exitdir) return; |
3868f2e6db9b
(svn r7573) -Merged the bridge branch. Allows to build bridges of arbitrary rail/road combinations (including signals)
celestar
parents:
5380
diff
changeset
|
585 |
} |
3868f2e6db9b
(svn r7573) -Merged the bridge branch. Allows to build bridges of arbitrary rail/road combinations (including signals)
celestar
parents:
5380
diff
changeset
|
586 |
} |
2493
f6b4300cc2b0
(svn r3019) -Codechange: Replace explicit shifting/anding/oring with GB and SB
tron
parents:
2416
diff
changeset
|
587 |
} |
1965
71079b9c26a8
(svn r2471) - Fix: [ 1221249 ] [NPF] Vehicles try to drive into a tunnel entrance from above.
matthijs
parents:
1950
diff
changeset
|
588 |
|
2006
9d5d7fd428c2
(svn r2514) - Codechange: [NPF] Move the checking of railtype into a funciton IsCompatibleRail().
matthijs
parents:
1983
diff
changeset
|
589 |
/* check correct rail type (mono, maglev, etc) */ |
1749
711c154a1fb7
(svn r2253) - Fix: [ 1190896 1184378 ] [NPF] Trains ignoring their railtype (mono, maglev) (glx)
matthijs
parents:
1700
diff
changeset
|
590 |
if (type == TRANSPORT_RAIL) { |
5587
167d9a91ef02
(svn r8038) -Merge: the cpp branch. Effort of KUDr, Celestar, glx, Smoovius, stillunknown and pv2b.
rubidium
parents:
5584
diff
changeset
|
591 |
RailType dst_type = GetTileRailType(dst_tile, TrackdirToTrack(src_trackdir)); |
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:
3333
diff
changeset
|
592 |
if (!HASBIT(aystar->user_data[NPF_RAILTYPES], dst_type)) |
1749
711c154a1fb7
(svn r2253) - Fix: [ 1190896 1184378 ] [NPF] Trains ignoring their railtype (mono, maglev) (glx)
matthijs
parents:
1700
diff
changeset
|
593 |
return; |
711c154a1fb7
(svn r2253) - Fix: [ 1190896 1184378 ] [NPF] Trains ignoring their railtype (mono, maglev) (glx)
matthijs
parents:
1700
diff
changeset
|
594 |
} |
1330
5d76a0522a11
(svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents:
1313
diff
changeset
|
595 |
|
5d76a0522a11
(svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents:
1313
diff
changeset
|
596 |
/* Check the owner of the tile */ |
5587
167d9a91ef02
(svn r8038) -Merge: the cpp branch. Effort of KUDr, Celestar, glx, Smoovius, stillunknown and pv2b.
rubidium
parents:
5584
diff
changeset
|
597 |
if (!VehicleMayEnterTile((Owner)aystar->user_data[NPF_OWNER], dst_tile, TrackdirToExitdir(src_trackdir))) { |
1967
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
598 |
return; |
a01f4d5dd957
(svn r2473) - Add: VehicleMayEnterTile(), which checks if the tile owner of a tile is correct for a vehicle to enter it. Based upon glx's code.
matthijs
parents:
1965
diff
changeset
|
599 |
} |
1247 | 600 |
|
601 |
/* Determine available tracks */ |
|
3404
eb8ebfe5df67
(svn r4215) -Codechange: Renamed *RoadStation* functions to *RoadStop* and moved them to station_map.h to keep consistency
celestar
parents:
3355
diff
changeset
|
602 |
if (type != TRANSPORT_WATER && (IsRoadStopTile(dst_tile) || IsTileDepotType(dst_tile, type))){ |
1655
8f9e052ce51e
(svn r2159) - Fix: [NPF] Road vehicles never found their target station or depots (introduced in r2154)
matthijs
parents:
1650
diff
changeset
|
603 |
/* Road stations and road and train depots return 0 on GTTS, so we have to do this by hand... */ |
1950
aeb6067adc30
(svn r2456) * Prettyfied npf.c using enums and wrappers from rail.h.
matthijs
parents:
1945
diff
changeset
|
604 |
DiagDirection exitdir; |
3404
eb8ebfe5df67
(svn r4215) -Codechange: Renamed *RoadStation* functions to *RoadStop* and moved them to station_map.h to keep consistency
celestar
parents:
3355
diff
changeset
|
605 |
if (IsRoadStopTile(dst_tile)) { |
eb8ebfe5df67
(svn r4215) -Codechange: Renamed *RoadStation* functions to *RoadStop* and moved them to station_map.h to keep consistency
celestar
parents:
3355
diff
changeset
|
606 |
exitdir = GetRoadStopDir(dst_tile); |
2951 | 607 |
} else { /* Road or train depot */ |
1650
4a5141e10b72
(svn r2154) - Fix: [NPF] Vehicles should no longer try to drive through the back of depots and road stations.
matthijs
parents:
1644
diff
changeset
|
608 |
exitdir = GetDepotDirection(dst_tile, type); |
2951 | 609 |
} |
1650
4a5141e10b72
(svn r2154) - Fix: [NPF] Vehicles should no longer try to drive through the back of depots and road stations.
matthijs
parents:
1644
diff
changeset
|
610 |
/* Find the trackdirs that are available for a depot or station with this |
4a5141e10b72
(svn r2154) - Fix: [NPF] Vehicles should no longer try to drive through the back of depots and road stations.
matthijs
parents:
1644
diff
changeset
|
611 |
* orientation. They are only "inwards", since we are reaching this tile |
4a5141e10b72
(svn r2154) - Fix: [NPF] Vehicles should no longer try to drive through the back of depots and road stations.
matthijs
parents:
1644
diff
changeset
|
612 |
* from some other tile. This prevents vehicles driving into depots from |
4a5141e10b72
(svn r2154) - Fix: [NPF] Vehicles should no longer try to drive through the back of depots and road stations.
matthijs
parents:
1644
diff
changeset
|
613 |
* the back */ |
3147
fc76d566a68e
(svn r3767) Move all direction related enums and functions to a separate header
tron
parents:
3135
diff
changeset
|
614 |
ts = TrackdirToTrackdirBits(DiagdirToDiagTrackdir(ReverseDiagDir(exitdir))); |
1247 | 615 |
} else { |
616 |
ts = GetTileTrackStatus(dst_tile, type); |
|
617 |
} |
|
5587
167d9a91ef02
(svn r8038) -Merge: the cpp branch. Effort of KUDr, Celestar, glx, Smoovius, stillunknown and pv2b.
rubidium
parents:
5584
diff
changeset
|
618 |
trackdirbits = (TrackdirBits)(ts & TRACKDIR_BIT_MASK); /* Filter out signal status and the unused bits */ |
1247 | 619 |
|
5380
8ea58542b6e0
(svn r7565) -Codechange: Rework DEBUG functionality. Look for appropiate debugging levels to
Darkvater
parents:
4561
diff
changeset
|
620 |
DEBUG(npf, 4, "Next node: (%d, %d) [%d], possible trackdirs: 0x%X", TileX(dst_tile), TileY(dst_tile), dst_tile, trackdirbits); |
1247 | 621 |
/* Select only trackdirs we can reach from our current trackdir */ |
1944
dd9cba5fab2a
(svn r2450) * Codechange: Replaced all uses of the arrays in tile.h with calls to the associated wrapper functions.
matthijs
parents:
1942
diff
changeset
|
622 |
trackdirbits &= TrackdirReachesTrackdirs(src_trackdir); |
1247 | 623 |
if (_patches.forbid_90_deg && (type == TRANSPORT_RAIL || type == TRANSPORT_WATER)) /* Filter out trackdirs that would make 90 deg turns for trains */ |
2916
b687477adcba
(svn r3472) - [PBS] Remove from trunk. Anyone interested can still find it in branch/pbs. This reverts revisions r3158, r3140, r3075, r2977, r2674, r2625, r2621, r2529, r2528, r2525, r2524, r2519, r2517, r2516, r2507, r2499. (in conjunction with Tron)
Darkvater
parents:
2878
diff
changeset
|
624 |
trackdirbits &= ~TrackdirCrossesTrackdirs(src_trackdir); |
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
|
625 |
|
5380
8ea58542b6e0
(svn r7565) -Codechange: Rework DEBUG functionality. Look for appropiate debugging levels to
Darkvater
parents:
4561
diff
changeset
|
626 |
DEBUG(npf, 6, "After filtering: (%d, %d), possible trackdirs: 0x%X", TileX(dst_tile), TileY(dst_tile), trackdirbits); |
1247 | 627 |
|
1950
aeb6067adc30
(svn r2456) * Prettyfied npf.c using enums and wrappers from rail.h.
matthijs
parents:
1945
diff
changeset
|
628 |
i = 0; |
1247 | 629 |
/* Enumerate possible track */ |
1944
dd9cba5fab2a
(svn r2450) * Codechange: Replaced all uses of the arrays in tile.h with calls to the associated wrapper functions.
matthijs
parents:
1942
diff
changeset
|
630 |
while (trackdirbits != 0) { |
5598
2fadbd43709d
(svn r8052) - Codechange: RemoveFirstTrack() and RemoveFirstTrackdir() now accept pointer to TrackBits/TrackdirBits instead of reference.
KUDr
parents:
5587
diff
changeset
|
631 |
Trackdir dst_trackdir = RemoveFirstTrackdir(&trackdirbits); |
5380
8ea58542b6e0
(svn r7565) -Codechange: Rework DEBUG functionality. Look for appropiate debugging levels to
Darkvater
parents:
4561
diff
changeset
|
632 |
DEBUG(npf, 5, "Expanded into trackdir: %d, remaining trackdirs: 0x%X", dst_trackdir, trackdirbits); |
1247 | 633 |
|
634 |
/* Check for oneway signal against us */ |
|
3792
67c865c9315c
(svn r4788) - Codechange: RAILTYPE_{NORMAL,ELECTRIC,...} and RAIL_TYPE_{NORMAL,SIGNAL,...} have nearly the same name, rename RAIL_TYPE_* to RAIL_TILE_* of extra clarity
rubidium
parents:
3630
diff
changeset
|
635 |
if (IsTileType(dst_tile, MP_RAILWAY) && GetRailTileType(dst_tile) == RAIL_TILE_SIGNALS) { |
1944
dd9cba5fab2a
(svn r2450) * Codechange: Replaced all uses of the arrays in tile.h with calls to the associated wrapper functions.
matthijs
parents:
1942
diff
changeset
|
636 |
if (HasSignalOnTrackdir(dst_tile, ReverseTrackdir(dst_trackdir)) && !HasSignalOnTrackdir(dst_tile, dst_trackdir)) |
1247 | 637 |
// if one way signal not pointing towards us, stop going in this direction. |
1944
dd9cba5fab2a
(svn r2450) * Codechange: Replaced all uses of the arrays in tile.h with calls to the associated wrapper functions.
matthijs
parents:
1942
diff
changeset
|
638 |
break; |
1247 | 639 |
} |
640 |
{ |
|
641 |
/* We've found ourselves a neighbour :-) */ |
|
642 |
AyStarNode* neighbour = &aystar->neighbours[i]; |
|
643 |
neighbour->tile = dst_tile; |
|
644 |
neighbour->direction = dst_trackdir; |
|
645 |
/* Save user data */ |
|
646 |
neighbour->user_data[NPF_NODE_FLAGS] = current->path.node.user_data[NPF_NODE_FLAGS]; |
|
647 |
NPFFillTrackdirChoice(neighbour, current); |
|
648 |
} |
|
649 |
i++; |
|
650 |
} |
|
651 |
aystar->num_neighbours = i; |
|
652 |
} |
|
653 |
||
654 |
/* |
|
655 |
* Plan a route to the specified target (which is checked by target_proc), |
|
656 |
* from start1 and if not NULL, from start2 as well. The type of transport we |
|
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:
1753
diff
changeset
|
657 |
* are checking is in type. reverse_penalty is applied to all routes 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:
1753
diff
changeset
|
658 |
* originate from the second start node. |
1247 | 659 |
* When we are looking for one specific target (optionally multiple tiles), we |
660 |
* should use a good heuristic to perform aystar search. When we search for |
|
661 |
* multiple targets that are spread around, we should perform a breadth first |
|
662 |
* search by specifiying CalcZero as our heuristic. |
|
663 |
*/ |
|
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:
3333
diff
changeset
|
664 |
static NPFFoundTargetData NPFRouteInternal(AyStarNode* start1, AyStarNode* start2, NPFFindStationOrTileData* target, AyStar_EndNodeCheck target_proc, AyStar_CalculateH heuristic_proc, TransportType type, Owner owner, RailTypeMask railtypes, uint reverse_penalty) |
1983 | 665 |
{ |
1247 | 666 |
int r; |
667 |
NPFFoundTargetData result; |
|
668 |
||
669 |
/* Initialize procs */ |
|
670 |
_npf_aystar.CalculateH = heuristic_proc; |
|
671 |
_npf_aystar.EndNodeCheck = target_proc; |
|
672 |
_npf_aystar.FoundEndNode = NPFSaveTargetData; |
|
673 |
_npf_aystar.GetNeighbours = NPFFollowTrack; |
|
4000
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3993
diff
changeset
|
674 |
switch (type) { |
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3993
diff
changeset
|
675 |
default: NOT_REACHED(); |
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3993
diff
changeset
|
676 |
case TRANSPORT_RAIL: _npf_aystar.CalculateG = NPFRailPathCost; break; |
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3993
diff
changeset
|
677 |
case TRANSPORT_ROAD: _npf_aystar.CalculateG = NPFRoadPathCost; break; |
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3993
diff
changeset
|
678 |
case TRANSPORT_WATER: _npf_aystar.CalculateG = NPFWaterPathCost; break; |
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3993
diff
changeset
|
679 |
} |
1247 | 680 |
|
681 |
/* Initialize Start Node(s) */ |
|
1942
c5d5cf5b0263
(svn r2448) General cleanup of rail related code, more to follow.
matthijs
parents:
1941
diff
changeset
|
682 |
start1->user_data[NPF_TRACKDIR_CHOICE] = INVALID_TRACKDIR; |
1247 | 683 |
start1->user_data[NPF_NODE_FLAGS] = 0; |
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:
1753
diff
changeset
|
684 |
_npf_aystar.addstart(&_npf_aystar, start1, 0); |
1247 | 685 |
if (start2) { |
1942
c5d5cf5b0263
(svn r2448) General cleanup of rail related code, more to follow.
matthijs
parents:
1941
diff
changeset
|
686 |
start2->user_data[NPF_TRACKDIR_CHOICE] = INVALID_TRACKDIR; |
1459
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
687 |
start2->user_data[NPF_NODE_FLAGS] = 0; |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
688 |
NPFSetFlag(start2, NPF_FLAG_REVERSE, true); |
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:
1753
diff
changeset
|
689 |
_npf_aystar.addstart(&_npf_aystar, start2, reverse_penalty); |
1247 | 690 |
} |
691 |
||
692 |
/* Initialize result */ |
|
693 |
result.best_bird_dist = (uint)-1; |
|
694 |
result.best_path_dist = (uint)-1; |
|
1942
c5d5cf5b0263
(svn r2448) General cleanup of rail related code, more to follow.
matthijs
parents:
1941
diff
changeset
|
695 |
result.best_trackdir = INVALID_TRACKDIR; |
1247 | 696 |
_npf_aystar.user_path = &result; |
697 |
||
698 |
/* Initialize target */ |
|
699 |
_npf_aystar.user_target = target; |
|
700 |
||
701 |
/* Initialize user_data */ |
|
702 |
_npf_aystar.user_data[NPF_TYPE] = type; |
|
1330
5d76a0522a11
(svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents:
1313
diff
changeset
|
703 |
_npf_aystar.user_data[NPF_OWNER] = owner; |
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:
3333
diff
changeset
|
704 |
_npf_aystar.user_data[NPF_RAILTYPES] = railtypes; |
1247 | 705 |
|
706 |
/* GO! */ |
|
707 |
r = AyStarMain_Main(&_npf_aystar); |
|
708 |
assert(r != AYSTAR_STILL_BUSY); |
|
709 |
||
710 |
if (result.best_bird_dist != 0) { |
|
3053
403425c55a3c
(svn r3642) There is a 'npf' debug level for a reason, use that instead of bastardizing 'misc'. Also, pointers are checked against NULL in an if-statement
Darkvater
parents:
3017
diff
changeset
|
711 |
if (target != NULL) { |
5380
8ea58542b6e0
(svn r7565) -Codechange: Rework DEBUG functionality. Look for appropiate debugging levels to
Darkvater
parents:
4561
diff
changeset
|
712 |
DEBUG(npf, 1, "Could not find route to tile 0x%X from 0x%X.", target->dest_coords, start1->tile); |
1247 | 713 |
} else { |
714 |
/* Assumption: target == NULL, so we are looking for a depot */ |
|
5380
8ea58542b6e0
(svn r7565) -Codechange: Rework DEBUG functionality. Look for appropiate debugging levels to
Darkvater
parents:
4561
diff
changeset
|
715 |
DEBUG(npf, 1, "Could not find route to a depot from tile 0x%X.", start1->tile); |
1247 | 716 |
} |
717 |
||
718 |
} |
|
719 |
return result; |
|
720 |
} |
|
721 |
||
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:
3333
diff
changeset
|
722 |
NPFFoundTargetData NPFRouteToStationOrTileTwoWay(TileIndex tile1, Trackdir trackdir1, TileIndex tile2, Trackdir trackdir2, NPFFindStationOrTileData* target, TransportType type, Owner owner, RailTypeMask railtypes) |
1983 | 723 |
{ |
1247 | 724 |
AyStarNode start1; |
725 |
AyStarNode start2; |
|
726 |
||
727 |
start1.tile = tile1; |
|
728 |
start2.tile = tile2; |
|
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:
1753
diff
changeset
|
729 |
/* We set this in case the target is also the start tile, we will just |
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:
1753
diff
changeset
|
730 |
* return a not found then */ |
1942
c5d5cf5b0263
(svn r2448) General cleanup of rail related code, more to follow.
matthijs
parents:
1941
diff
changeset
|
731 |
start1.user_data[NPF_TRACKDIR_CHOICE] = INVALID_TRACKDIR; |
1247 | 732 |
start1.direction = trackdir1; |
733 |
start2.direction = trackdir2; |
|
1942
c5d5cf5b0263
(svn r2448) General cleanup of rail related code, more to follow.
matthijs
parents:
1941
diff
changeset
|
734 |
start2.user_data[NPF_TRACKDIR_CHOICE] = INVALID_TRACKDIR; |
1247 | 735 |
|
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:
3333
diff
changeset
|
736 |
return NPFRouteInternal(&start1, (IsValidTile(tile2) ? &start2 : NULL), target, NPFFindStationOrTile, NPFCalcStationOrTileHeuristic, type, owner, railtypes, 0); |
1247 | 737 |
} |
738 |
||
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:
3333
diff
changeset
|
739 |
NPFFoundTargetData NPFRouteToStationOrTile(TileIndex tile, Trackdir trackdir, NPFFindStationOrTileData* target, TransportType type, Owner owner, RailTypeMask railtypes) |
1983 | 740 |
{ |
5587
167d9a91ef02
(svn r8038) -Merge: the cpp branch. Effort of KUDr, Celestar, glx, Smoovius, stillunknown and pv2b.
rubidium
parents:
5584
diff
changeset
|
741 |
return NPFRouteToStationOrTileTwoWay(tile, trackdir, INVALID_TILE, INVALID_TRACKDIR, target, type, owner, 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:
1753
diff
changeset
|
742 |
} |
1247 | 743 |
|
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:
3333
diff
changeset
|
744 |
NPFFoundTargetData NPFRouteToDepotBreadthFirstTwoWay(TileIndex tile1, Trackdir trackdir1, TileIndex tile2, Trackdir trackdir2, TransportType type, Owner owner, RailTypeMask railtypes, uint reverse_penalty) |
1983 | 745 |
{ |
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:
1753
diff
changeset
|
746 |
AyStarNode start1; |
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:
1753
diff
changeset
|
747 |
AyStarNode start2; |
1247 | 748 |
|
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:
1753
diff
changeset
|
749 |
start1.tile = tile1; |
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:
1753
diff
changeset
|
750 |
start2.tile = tile2; |
1247 | 751 |
/* We set this in case the target is also the start tile, we will just |
752 |
* return a not found then */ |
|
1942
c5d5cf5b0263
(svn r2448) General cleanup of rail related code, more to follow.
matthijs
parents:
1941
diff
changeset
|
753 |
start1.user_data[NPF_TRACKDIR_CHOICE] = INVALID_TRACKDIR; |
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:
1753
diff
changeset
|
754 |
start1.direction = trackdir1; |
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:
1753
diff
changeset
|
755 |
start2.direction = trackdir2; |
1942
c5d5cf5b0263
(svn r2448) General cleanup of rail related code, more to follow.
matthijs
parents:
1941
diff
changeset
|
756 |
start2.user_data[NPF_TRACKDIR_CHOICE] = INVALID_TRACKDIR; |
1247 | 757 |
|
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:
1753
diff
changeset
|
758 |
/* perform a breadth first search. Target is NULL, |
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:
1753
diff
changeset
|
759 |
* since we are just looking for any depot...*/ |
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:
3333
diff
changeset
|
760 |
return NPFRouteInternal(&start1, (IsValidTile(tile2) ? &start2 : NULL), NULL, NPFFindDepot, NPFCalcZero, type, owner, railtypes, reverse_penalty); |
1247 | 761 |
} |
762 |
||
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:
3333
diff
changeset
|
763 |
NPFFoundTargetData NPFRouteToDepotBreadthFirst(TileIndex tile, Trackdir trackdir, TransportType type, Owner owner, RailTypeMask railtypes) |
1983 | 764 |
{ |
5587
167d9a91ef02
(svn r8038) -Merge: the cpp branch. Effort of KUDr, Celestar, glx, Smoovius, stillunknown and pv2b.
rubidium
parents:
5584
diff
changeset
|
765 |
return NPFRouteToDepotBreadthFirstTwoWay(tile, trackdir, INVALID_TILE, INVALID_TRACKDIR, type, owner, railtypes, 0); |
1247 | 766 |
} |
767 |
||
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:
3333
diff
changeset
|
768 |
NPFFoundTargetData NPFRouteToDepotTrialError(TileIndex tile, Trackdir trackdir, TransportType type, Owner owner, RailTypeMask railtypes) |
1983 | 769 |
{ |
1247 | 770 |
/* Okay, what we're gonna do. First, we look at all depots, calculate |
771 |
* the manhatten distance to get to each depot. We then sort them by |
|
772 |
* distance. We start by trying to plan a route to the closest, then |
|
773 |
* the next closest, etc. We stop when the best route we have found so |
|
774 |
* far, is shorter than the manhattan distance. This will obviously |
|
775 |
* always find the closest depot. It will probably be most efficient |
|
776 |
* for ships, since the heuristic will not be to far off then. I hope. |
|
777 |
*/ |
|
778 |
Queue depots; |
|
779 |
int r; |
|
4424 | 780 |
NPFFoundTargetData best_result = {(uint)-1, (uint)-1, INVALID_TRACKDIR, {INVALID_TILE, 0, {0, 0}}}; |
1247 | 781 |
NPFFoundTargetData result; |
782 |
NPFFindStationOrTileData target; |
|
783 |
AyStarNode start; |
|
784 |
Depot* current; |
|
1313
f1013ec3d318
(svn r1817) -Codechange: Moved depot-functions to depot.c
truelight
parents:
1299
diff
changeset
|
785 |
Depot *depot; |
1247 | 786 |
|
787 |
init_InsSort(&depots); |
|
788 |
/* Okay, let's find all depots that we can use first */ |
|
1313
f1013ec3d318
(svn r1817) -Codechange: Moved depot-functions to depot.c
truelight
parents:
1299
diff
changeset
|
789 |
FOR_ALL_DEPOTS(depot) { |
1330
5d76a0522a11
(svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents:
1313
diff
changeset
|
790 |
/* Check if this is really a valid depot, it is of the needed type and |
5d76a0522a11
(svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents:
1313
diff
changeset
|
791 |
* owner */ |
4346
66105d4f6e83
(svn r6047) -Codechange: FOR_ALL now _only_ loops valid items, and skips invalid ones
truelight
parents:
4077
diff
changeset
|
792 |
if (IsTileDepotType(depot->xy, type) && IsTileOwner(depot->xy, owner)) |
1330
5d76a0522a11
(svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents:
1313
diff
changeset
|
793 |
/* If so, let's add it to the queue, sorted by distance */ |
1313
f1013ec3d318
(svn r1817) -Codechange: Moved depot-functions to depot.c
truelight
parents:
1299
diff
changeset
|
794 |
depots.push(&depots, depot, DistanceManhattan(tile, depot->xy)); |
1247 | 795 |
} |
796 |
||
797 |
/* Now, let's initialise the aystar */ |
|
798 |
||
799 |
/* Initialize procs */ |
|
800 |
_npf_aystar.CalculateH = NPFCalcStationOrTileHeuristic; |
|
801 |
_npf_aystar.EndNodeCheck = NPFFindStationOrTile; |
|
802 |
_npf_aystar.FoundEndNode = NPFSaveTargetData; |
|
803 |
_npf_aystar.GetNeighbours = NPFFollowTrack; |
|
4077
d4d440dd8925
(svn r5391) Miscellaneous, mostly bracing and whitespace, nothing spectacular
tron
parents:
4048
diff
changeset
|
804 |
switch (type) { |
d4d440dd8925
(svn r5391) Miscellaneous, mostly bracing and whitespace, nothing spectacular
tron
parents:
4048
diff
changeset
|
805 |
default: NOT_REACHED(); |
d4d440dd8925
(svn r5391) Miscellaneous, mostly bracing and whitespace, nothing spectacular
tron
parents:
4048
diff
changeset
|
806 |
case TRANSPORT_RAIL: _npf_aystar.CalculateG = NPFRailPathCost; break; |
d4d440dd8925
(svn r5391) Miscellaneous, mostly bracing and whitespace, nothing spectacular
tron
parents:
4048
diff
changeset
|
807 |
case TRANSPORT_ROAD: _npf_aystar.CalculateG = NPFRoadPathCost; break; |
d4d440dd8925
(svn r5391) Miscellaneous, mostly bracing and whitespace, nothing spectacular
tron
parents:
4048
diff
changeset
|
808 |
case TRANSPORT_WATER: _npf_aystar.CalculateG = NPFWaterPathCost; break; |
d4d440dd8925
(svn r5391) Miscellaneous, mostly bracing and whitespace, nothing spectacular
tron
parents:
4048
diff
changeset
|
809 |
} |
1247 | 810 |
|
811 |
/* Initialize target */ |
|
3135 | 812 |
target.station_index = INVALID_STATION; /* We will initialize dest_coords inside the loop below */ |
1247 | 813 |
_npf_aystar.user_target = ⌖ |
814 |
||
815 |
/* Initialize user_data */ |
|
816 |
_npf_aystar.user_data[NPF_TYPE] = type; |
|
1330
5d76a0522a11
(svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents:
1313
diff
changeset
|
817 |
_npf_aystar.user_data[NPF_OWNER] = owner; |
1247 | 818 |
|
819 |
/* Initialize Start Node */ |
|
820 |
start.tile = tile; |
|
821 |
start.direction = trackdir; /* We will initialize user_data inside the loop below */ |
|
822 |
||
823 |
/* Initialize Result */ |
|
824 |
_npf_aystar.user_path = &result; |
|
825 |
best_result.best_path_dist = (uint)-1; |
|
1330
5d76a0522a11
(svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents:
1313
diff
changeset
|
826 |
best_result.best_bird_dist = (uint)-1; |
1247 | 827 |
|
828 |
/* Just iterate the depots in order of increasing distance */ |
|
5587
167d9a91ef02
(svn r8038) -Merge: the cpp branch. Effort of KUDr, Celestar, glx, Smoovius, stillunknown and pv2b.
rubidium
parents:
5584
diff
changeset
|
829 |
while ((current = (Depot*)depots.pop(&depots))) { |
1247 | 830 |
/* Check to see if we already have a path shorter than this |
1330
5d76a0522a11
(svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents:
1313
diff
changeset
|
831 |
* depot's manhattan distance. HACK: We call DistanceManhattan |
1247 | 832 |
* again, we should probably modify the queue to give us that |
833 |
* value... */ |
|
834 |
if ( DistanceManhattan(tile, current->xy * NPF_TILE_LENGTH) > best_result.best_path_dist) |
|
835 |
break; |
|
836 |
||
837 |
/* Initialize Start Node */ |
|
838 |
/* We set this in case the target is also the start tile, we will just |
|
839 |
* return a not found then */ |
|
1942
c5d5cf5b0263
(svn r2448) General cleanup of rail related code, more to follow.
matthijs
parents:
1941
diff
changeset
|
840 |
start.user_data[NPF_TRACKDIR_CHOICE] = INVALID_TRACKDIR; |
1247 | 841 |
start.user_data[NPF_NODE_FLAGS] = 0; |
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:
1753
diff
changeset
|
842 |
_npf_aystar.addstart(&_npf_aystar, &start, 0); |
1247 | 843 |
|
844 |
/* Initialize result */ |
|
845 |
result.best_bird_dist = (uint)-1; |
|
846 |
result.best_path_dist = (uint)-1; |
|
1942
c5d5cf5b0263
(svn r2448) General cleanup of rail related code, more to follow.
matthijs
parents:
1941
diff
changeset
|
847 |
result.best_trackdir = INVALID_TRACKDIR; |
1247 | 848 |
|
849 |
/* Initialize target */ |
|
850 |
target.dest_coords = current->xy; |
|
851 |
||
852 |
/* GO! */ |
|
853 |
r = AyStarMain_Main(&_npf_aystar); |
|
854 |
assert(r != AYSTAR_STILL_BUSY); |
|
855 |
||
856 |
/* This depot is closer */ |
|
857 |
if (result.best_path_dist < best_result.best_path_dist) |
|
858 |
best_result = result; |
|
859 |
} |
|
860 |
if (result.best_bird_dist != 0) { |
|
5380
8ea58542b6e0
(svn r7565) -Codechange: Rework DEBUG functionality. Look for appropiate debugging levels to
Darkvater
parents:
4561
diff
changeset
|
861 |
DEBUG(npf, 1, "Could not find route to any depot from tile 0x%X.", tile); |
1247 | 862 |
} |
863 |
return best_result; |
|
864 |
} |
|
865 |
||
866 |
void InitializeNPF(void) |
|
867 |
{ |
|
1661
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1655
diff
changeset
|
868 |
init_AyStar(&_npf_aystar, NPFHash, NPF_HASH_SIZE); |
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
869 |
_npf_aystar.loops_per_tick = 0; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
870 |
_npf_aystar.max_path_cost = 0; |
1700
e1fe3446d013
(svn r2204) - Add: [NPF] NPF now has a maximum number of nodes it will search. The default value is 5000 for now, which is an educated guess. Probably needs some finetuning. Hopefully this "feature" can be removed later on, when more sophisticated means of limiting the pathfinder have been implemented. This should make ships and larger networks playable for now, though.
matthijs
parents:
1678
diff
changeset
|
871 |
//_npf_aystar.max_search_nodes = 0; |
e1fe3446d013
(svn r2204) - Add: [NPF] NPF now has a maximum number of nodes it will search. The default value is 5000 for now, which is an educated guess. Probably needs some finetuning. Hopefully this "feature" can be removed later on, when more sophisticated means of limiting the pathfinder have been implemented. This should make ships and larger networks playable for now, though.
matthijs
parents:
1678
diff
changeset
|
872 |
/* We will limit the number of nodes for now, until we have a better |
e1fe3446d013
(svn r2204) - Add: [NPF] NPF now has a maximum number of nodes it will search. The default value is 5000 for now, which is an educated guess. Probably needs some finetuning. Hopefully this "feature" can be removed later on, when more sophisticated means of limiting the pathfinder have been implemented. This should make ships and larger networks playable for now, though.
matthijs
parents:
1678
diff
changeset
|
873 |
* solution to really fix performance */ |
e1fe3446d013
(svn r2204) - Add: [NPF] NPF now has a maximum number of nodes it will search. The default value is 5000 for now, which is an educated guess. Probably needs some finetuning. Hopefully this "feature" can be removed later on, when more sophisticated means of limiting the pathfinder have been implemented. This should make ships and larger networks playable for now, though.
matthijs
parents:
1678
diff
changeset
|
874 |
_npf_aystar.max_search_nodes = _patches.npf_max_search_nodes; |
1247 | 875 |
} |
876 |
||
1983 | 877 |
void NPFFillWithOrderData(NPFFindStationOrTileData* fstd, Vehicle* v) |
878 |
{ |
|
1247 | 879 |
/* Ships don't really reach their stations, but the tile in front. So don't |
880 |
* save the station id for ships. For roadvehs we don't store it either, |
|
881 |
* because multistop depends on vehicles actually reaching the exact |
|
882 |
* dest_tile, not just any stop of that station. |
|
883 |
* So only for train orders to stations we fill fstd->station_index, for all |
|
884 |
* others only dest_coords */ |
|
2951 | 885 |
if (v->current_order.type == OT_GOTO_STATION && v->type == VEH_Train) { |
4527
fa30d19685c2
(svn r6353) -Codechange: Make DestinationID a typedef of uin16, which is as large as any type of destinataion (StationID, DepotID, WaypointID) it can hold
tron
parents:
4434
diff
changeset
|
886 |
fstd->station_index = v->current_order.dest; |
1452
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
887 |
/* Let's take the closest tile of the station as our target for trains */ |
4527
fa30d19685c2
(svn r6353) -Codechange: Make DestinationID a typedef of uin16, which is as large as any type of destinataion (StationID, DepotID, WaypointID) it can hold
tron
parents:
4434
diff
changeset
|
888 |
fstd->dest_coords = CalcClosestStationTile(v->current_order.dest, v->tile); |
1247 | 889 |
} else { |
890 |
fstd->dest_coords = v->dest_tile; |
|
3135 | 891 |
fstd->station_index = INVALID_STATION; |
1247 | 892 |
} |
893 |
} |