author | truelight |
Thu, 24 Mar 2005 14:43:40 +0000 | |
changeset 1540 | 6eef12dab5bf |
parent 1503 | 39d0f85977cf |
child 1617 | c3d3caad6d1e |
permissions | -rw-r--r-- |
1247 | 1 |
#include "stdafx.h" |
2 |
#include "ttd.h" |
|
1299
39c06aba09aa
(svn r1803) Move debugging stuff into files of it's own
tron
parents:
1248
diff
changeset
|
3 |
#include "debug.h" |
1247 | 4 |
#include "npf.h" |
5 |
#include "aystar.h" |
|
6 |
#include "macros.h" |
|
7 |
#include "pathfind.h" |
|
8 |
#include "station.h" |
|
9 |
#include "tile.h" |
|
1313
f1013ec3d318
(svn r1817) -Codechange: Moved depot-functions to depot.c
truelight
parents:
1299
diff
changeset
|
10 |
#include "depot.h" |
1247 | 11 |
|
12 |
AyStar _train_find_station; |
|
13 |
AyStar _train_find_depot; |
|
14 |
AyStar _road_find_station; |
|
15 |
AyStar _road_find_depot; |
|
16 |
AyStar _npf_aystar; |
|
17 |
||
18 |
/* Maps a trackdir to the bit that stores its status in the map arrays, in the |
|
19 |
* direction along with the trackdir */ |
|
20 |
const byte _signal_along_trackdir[14] = { |
|
21 |
0x80, 0x80, 0x80, 0x20, 0x40, 0x10, 0, 0, |
|
22 |
0x40, 0x40, 0x40, 0x10, 0x80, 0x20 |
|
23 |
}; |
|
24 |
||
25 |
/* Maps a trackdir to the bit that stores its status in the map arrays, in the |
|
26 |
* direction against the trackdir */ |
|
27 |
const byte _signal_against_trackdir[14] = { |
|
28 |
0x40, 0x40, 0x40, 0x10, 0x80, 0x20, 0, 0, |
|
29 |
0x80, 0x80, 0x80, 0x20, 0x40, 0x10 |
|
30 |
}; |
|
31 |
||
32 |
/* Maps a trackdir to the trackdirs that can be reached from it (ie, when |
|
33 |
* entering the next tile */ |
|
34 |
const uint16 _trackdir_reaches_trackdirs[14] = { |
|
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
35 |
0x1009, 0x0016, 0x1009, 0x0016, 0x0520, 0x0016, 0, 0, |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
36 |
0x0520, 0x2A00, 0x2A00, 0x0520, 0x2A00, 0x1009 |
1247 | 37 |
}; |
38 |
||
39 |
/* Maps a trackdir to all trackdirs that make 90 deg turns with it. */ |
|
40 |
const uint16 _trackdir_crosses_trackdirs[14] = { |
|
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
41 |
0x0202, 0x0101, 0x3030, 0x3030, 0x0C0C, 0x0C0C, 0, 0, |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
42 |
0x0202, 0x0101, 0x3030, 0x3030, 0x0C0C, 0x0C0C |
1247 | 43 |
}; |
44 |
||
45 |
/* Maps a track to all tracks that make 90 deg turns with it. */ |
|
46 |
const byte _track_crosses_tracks[6] = { |
|
47 |
0x2, /* Track 1 -> Track 2 */ |
|
48 |
0x1, /* Track 2 -> Track 1 */ |
|
49 |
0x30, /* Upper -> Left | Right */ |
|
50 |
0x30, /* Lower -> Left | Right */ |
|
51 |
0x0C, /* Left -> Upper | Lower */ |
|
52 |
0x0C, /* Right -> Upper | Lower */ |
|
53 |
}; |
|
54 |
||
55 |
/* Maps a trackdir to the (4-way) direction the tile is exited when following |
|
56 |
* that trackdir */ |
|
57 |
const byte _trackdir_to_exitdir[14] = { |
|
58 |
0,1,0,1,2,1, 0,0, |
|
59 |
2,3,3,2,3,0, |
|
60 |
}; |
|
61 |
||
62 |
const byte _track_exitdir_to_trackdir[6][4] = { |
|
63 |
{0, 0xff, 8, 0xff}, |
|
64 |
{0xff, 1, 0xff, 9}, |
|
65 |
{2, 0xff, 0xff, 10}, |
|
66 |
{0xff, 3, 11, 0xf}, |
|
67 |
{0xff, 0xff, 4, 12}, |
|
68 |
{13, 5, 0xff, 0xff} |
|
69 |
}; |
|
70 |
||
71 |
const byte _track_direction_to_trackdir[6][8] = { |
|
72 |
{0xff, 0, 0xff, 0xff, 0xff, 8, 0xff, 0xff}, |
|
73 |
{0xff, 0xff, 0xff, 1, 0xff, 0xff, 0xff, 9}, |
|
74 |
{0xff, 0xff, 2, 0xff, 0xff, 0xff, 10, 0xff}, |
|
75 |
{0xff, 0xff, 3, 0xff, 0xff, 0xff, 11, 0xff}, |
|
76 |
{12, 0xff, 0xff, 0xff, 4, 0xff, 0xff, 0xff}, |
|
77 |
{13, 0xff, 0xff, 0xff, 5, 0xff, 0xff, 0xff} |
|
78 |
}; |
|
79 |
||
80 |
const byte _dir_to_diag_trackdir[4] = { |
|
81 |
0, 1, 8, 9, |
|
82 |
}; |
|
83 |
||
84 |
const byte _reverse_dir[4] = { |
|
85 |
2, 3, 0, 1 |
|
86 |
}; |
|
87 |
||
88 |
const byte _reverse_trackdir[14] = { |
|
89 |
8, 9, 10, 11, 12, 13, 0xFF, 0xFF, |
|
90 |
0, 1, 2, 3, 4, 5 |
|
91 |
}; |
|
92 |
||
93 |
/* The cost of each trackdir. A diagonal piece is the full NPF_TILE_LENGTH, |
|
94 |
* the shorter piece is sqrt(2)/2*NPF_TILE_LENGTH =~ 0.7071 |
|
95 |
*/ |
|
96 |
#define NPF_STRAIGHT_LENGTH (uint)(NPF_TILE_LENGTH * 0.7071) |
|
97 |
static const uint _trackdir_length[14] = { |
|
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
98 |
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
|
99 |
0, 0, |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
100 |
NPF_TILE_LENGTH, NPF_TILE_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH |
1247 | 101 |
}; |
102 |
||
103 |
uint NTPHash(uint key1, uint key2) |
|
104 |
{ |
|
105 |
return PATHFIND_HASH_TILE(key1); |
|
106 |
} |
|
107 |
||
108 |
int32 NPFCalcZero(AyStar* as, AyStarNode* current, OpenListNode* parent) { |
|
109 |
return 0; |
|
110 |
} |
|
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 |
/* 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
|
113 |
* 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
|
114 |
* as defined by its top tile (st->train_tile) and its width/height (st->trainst_w, st->trainst_h) |
1247 | 115 |
*/ |
1452
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
116 |
TileIndex CalcClosestStationTile(int station, TileIndex tile) { |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
117 |
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
|
118 |
|
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
119 |
int x1,x2,x3,tx; |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
120 |
int y1,y2,y3,ty; |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
121 |
|
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
122 |
x1 = TileX(st->train_tile); y1 = TileY(st->train_tile); // topmost corner of station |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
123 |
x2 = x1 + st->trainst_w - 1; y2 = y1 + st->trainst_h - 1; // lowermost corner of station |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
124 |
x3 = TileX(tile); y3 = TileY(tile); // tile we take the distance from |
1452
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
125 |
|
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
126 |
// 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
|
127 |
// but if we are between those coordinates, we will aim for our own x coordinate |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
128 |
if (x3 < x1) |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
129 |
tx = x1; |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
130 |
else if (x3 > x2) |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
131 |
tx = x2; |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
132 |
else |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
133 |
tx = x3; |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
134 |
|
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
135 |
// same for y coordinate, see above comment |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
136 |
if (y3 < y1) |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
137 |
ty = y1; |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
138 |
else if (y3 > y2) |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
139 |
ty = y2; |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
140 |
else |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
141 |
ty = y3; |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
142 |
|
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
143 |
// return the tile of our target coordinates |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
144 |
return TILE_XY(tx,ty); |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
145 |
}; |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
146 |
|
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
147 |
/* Calcs the heuristic to the target tile (using NPFFindStationOrTileData). |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
148 |
* If the target is a station, the heuristic is probably "wrong"! Normally |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
149 |
* this shouldn't matter, but if it turns out to be a problem, we could use |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
150 |
* the heuristic below? |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
151 |
* Afterthis will save the heuristic into NPFFoundTargetData if it is the |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
152 |
* smallest until now. It will then also save |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
153 |
* AyStarNode.user_data[NPF_TRACKDIR_CHOICE] in best_trackdir |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
154 |
*/ |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
155 |
int32 NPFCalcTileHeuristic(AyStar* as, AyStarNode* current, OpenListNode* parent) { |
1247 | 156 |
NPFFindStationOrTileData* fstd = (NPFFindStationOrTileData*)as->user_target; |
157 |
NPFFoundTargetData* ftd = (NPFFoundTargetData*)as->user_path; |
|
158 |
TileIndex from = current->tile; |
|
159 |
TileIndex to = fstd->dest_coords; |
|
160 |
uint dist = DistanceManhattan(from, to) * NPF_TILE_LENGTH; |
|
161 |
||
162 |
if (dist < ftd->best_bird_dist) { |
|
163 |
ftd->best_bird_dist = dist; |
|
164 |
ftd->best_trackdir = current->user_data[NPF_TRACKDIR_CHOICE]; |
|
165 |
} |
|
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
166 |
#ifdef NPF_DEBUG |
1247 | 167 |
debug("Calculating H for: (%d, %d). Result: %d", TileX(current->tile), TileY(current->tile), dist); |
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
168 |
#endif |
1247 | 169 |
return dist; |
170 |
} |
|
171 |
||
1452
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
172 |
/* Calcs the heuristic to the target station or tile. Almost the same as above |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
173 |
* function, but calculates the distance to train stations with |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
174 |
* CalcClosestStationTile instead. So is somewhat more correct for stations |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
175 |
* (truly optimistic), but this added correctness is not really required we |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
176 |
* believe (matthijs & Hackykid) |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
177 |
*/ |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
178 |
int32 NPFCalcStationOrTileHeuristic(AyStar* as, AyStarNode* current, OpenListNode* parent) { |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
179 |
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
|
180 |
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
|
181 |
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
|
182 |
TileIndex to = fstd->dest_coords; |
1453 | 183 |
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
|
184 |
|
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
185 |
// for train-stations, we are going to aim for the closest station tile |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
186 |
if ((as->user_data[NPF_TYPE] == TRANSPORT_RAIL) && (fstd->station_index != -1)) |
1453 | 187 |
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
|
188 |
|
1453 | 189 |
dist = DistanceManhattan(from, to) * NPF_TILE_LENGTH; |
1452
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
190 |
|
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
191 |
if (dist < ftd->best_bird_dist) { |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
192 |
ftd->best_bird_dist = dist; |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
193 |
ftd->best_trackdir = current->user_data[NPF_TRACKDIR_CHOICE]; |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
194 |
} |
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
195 |
#ifdef NPF_DEBUG |
1452
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
196 |
debug("Calculating H for: (%d, %d). Result: %d", TileX(current->tile), TileY(current->tile), dist); |
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
197 |
#endif |
1452
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
198 |
return dist; |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
199 |
} |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
200 |
|
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
201 |
|
1247 | 202 |
/* Fills AyStarNode.user_data[NPF_TRACKDIRCHOICE] with the chosen direction to |
203 |
* get here, either getting it from the current choice or from the parent's |
|
204 |
* choice */ |
|
205 |
void NPFFillTrackdirChoice(AyStarNode* current, OpenListNode* parent) |
|
206 |
{ |
|
207 |
if (parent->path.parent == NULL) { |
|
208 |
byte trackdir = current->direction; |
|
209 |
/* This is a first order decision, so we'd better save the |
|
210 |
* direction we chose */ |
|
211 |
current->user_data[NPF_TRACKDIR_CHOICE] = trackdir; |
|
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
212 |
#ifdef NPF_DEBUG |
1247 | 213 |
debug("Saving trackdir: %#x", trackdir); |
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
214 |
#endif |
1247 | 215 |
} else { |
216 |
/* We've already made the decision, so just save our parent's |
|
217 |
* decision */ |
|
218 |
current->user_data[NPF_TRACKDIR_CHOICE] = parent->path.node.user_data[NPF_TRACKDIR_CHOICE]; |
|
219 |
} |
|
220 |
||
221 |
} |
|
222 |
||
223 |
/* Will return the cost of the tunnel. If it is an entry, it will return the |
|
224 |
* cost of that tile. If the tile is an exit, it will return the tunnel length |
|
225 |
* including the exit tile. Requires that this is a Tunnel tile */ |
|
226 |
uint NPFTunnelCost(AyStarNode* current) { |
|
227 |
byte exitdir = _trackdir_to_exitdir[current->direction]; |
|
228 |
TileIndex tile = current->tile; |
|
229 |
if ( (uint)(_map5[tile] & 3) == _reverse_dir[exitdir]) { |
|
230 |
/* We just popped out if this tunnel, since were |
|
231 |
* facing the tunnel exit */ |
|
232 |
FindLengthOfTunnelResult flotr; |
|
233 |
flotr = FindLengthOfTunnel(tile, _reverse_dir[exitdir]); |
|
234 |
return flotr.length * NPF_TILE_LENGTH; |
|
235 |
//TODO: Penalty for tunnels? |
|
236 |
} else { |
|
237 |
/* We are entering the tunnel, the enter tile is just a |
|
238 |
* straight track */ |
|
239 |
return NPF_TILE_LENGTH; |
|
240 |
} |
|
241 |
} |
|
242 |
||
243 |
uint NPFSlopeCost(AyStarNode* current) { |
|
244 |
TileIndex next = current->tile + TileOffsByDir(_trackdir_to_exitdir[current->direction]); |
|
1503
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
245 |
int x,y; |
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
246 |
int8 z1,z2; |
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
247 |
|
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
248 |
x = TileX(current->tile) * 16; |
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
249 |
y = TileY(current->tile) * 16; |
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
250 |
z1 = GetSlopeZ(x+8, y+8); |
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
251 |
|
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
252 |
x = TileX(next) * 16; |
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
253 |
y = TileY(next) * 16; |
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
254 |
z2 = GetSlopeZ(x+8, y+8); |
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
255 |
|
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
256 |
if ((z2 - z1) > 1) { |
1247 | 257 |
/* Slope up */ |
258 |
return _patches.npf_rail_slope_penalty; |
|
259 |
} |
|
260 |
return 0; |
|
261 |
/* Should we give a bonus for slope down? Probably not, we |
|
262 |
* could just substract that bonus from the penalty, because |
|
263 |
* there is only one level of steepness... */ |
|
264 |
} |
|
265 |
||
266 |
void NPFMarkTile(TileIndex tile) { |
|
267 |
switch(GetTileType(tile)) { |
|
268 |
case MP_RAILWAY: |
|
269 |
case MP_STREET: |
|
270 |
/* DEBUG: mark visited tiles by mowing the grass under them |
|
271 |
* ;-) */ |
|
272 |
_map2[tile] &= ~15; |
|
273 |
MarkTileDirtyByTile(tile); |
|
274 |
break; |
|
275 |
default: |
|
276 |
break; |
|
277 |
} |
|
278 |
} |
|
279 |
||
280 |
int32 NPFWaterPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent) { |
|
281 |
//TileIndex tile = current->tile; |
|
282 |
int32 cost = 0; |
|
283 |
byte trackdir = current->direction; |
|
284 |
||
285 |
cost = _trackdir_length[trackdir]; /* Should be different for diagonal tracks */ |
|
286 |
||
287 |
/* TODO Penalties? */ |
|
288 |
||
289 |
return cost; |
|
290 |
} |
|
291 |
||
292 |
/* Determine the cost of this node, for road tracks */ |
|
293 |
int32 NPFRoadPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent) { |
|
294 |
TileIndex tile = current->tile; |
|
295 |
int32 cost = 0; |
|
296 |
/* Determine base length */ |
|
297 |
switch (GetTileType(tile)) { |
|
298 |
case MP_TUNNELBRIDGE: |
|
299 |
if ((_map5[tile] & 0xF0)==0) { |
|
300 |
cost = NPFTunnelCost(current); |
|
301 |
break; |
|
302 |
} |
|
303 |
/* Fall through if above if is false, it is a bridge |
|
304 |
* then. We treat that as ordinary rail */ |
|
305 |
case MP_STREET: |
|
306 |
cost = NPF_TILE_LENGTH; |
|
307 |
break; |
|
308 |
default: |
|
309 |
break; |
|
310 |
} |
|
311 |
||
312 |
/* Determine extra costs */ |
|
313 |
||
314 |
/* Check for slope */ |
|
315 |
cost += NPFSlopeCost(current); |
|
316 |
||
317 |
/* Check for turns */ |
|
318 |
//TODO |
|
319 |
||
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
320 |
#ifdef NPF_MARKROUTE |
1247 | 321 |
NPFMarkTile(tile); |
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
322 |
#endif |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
323 |
#ifdef NPF_DEBUG |
1247 | 324 |
debug("Calculating G for: (%d, %d). Result: %d", TileX(current->tile), TileY(current->tile), cost); |
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
325 |
#endif |
1247 | 326 |
return cost; |
327 |
} |
|
328 |
||
329 |
||
330 |
/* Determine the cost of this node, for railway tracks */ |
|
331 |
int32 NPFRailPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent) { |
|
332 |
TileIndex tile = current->tile; |
|
333 |
byte trackdir = current->direction; |
|
334 |
int32 cost = 0; |
|
335 |
/* Determine base length */ |
|
336 |
switch (GetTileType(tile)) { |
|
337 |
case MP_TUNNELBRIDGE: |
|
338 |
if ((_map5[tile] & 0xF0)==0) { |
|
339 |
cost = NPFTunnelCost(current); |
|
340 |
break; |
|
341 |
} |
|
342 |
/* Fall through if above if is false, it is a bridge |
|
343 |
* then. We treat that as ordinary rail */ |
|
344 |
case MP_RAILWAY: |
|
345 |
cost = _trackdir_length[trackdir]; /* Should be different for diagonal tracks */ |
|
346 |
break; |
|
347 |
case MP_STREET: /* Railway crossing */ |
|
348 |
cost = NPF_TILE_LENGTH; |
|
349 |
break; |
|
1503
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
350 |
case MP_STATION: |
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
351 |
/* We give a station tile a penalty. Logically we would only |
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
352 |
* want to give station tiles that are not our destination |
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
353 |
* this penalty. This would discourage trains to drive through |
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
354 |
* busy stations. But, we can just give any station tile a |
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
355 |
* penalty, because every possible route will get this penalty |
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
356 |
* exactly once, on its end tile (if it's a station) and it |
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
357 |
* will therefore not make a difference. */ |
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
358 |
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
|
359 |
break; |
1247 | 360 |
default: |
361 |
break; |
|
362 |
} |
|
363 |
||
364 |
/* Determine extra costs */ |
|
365 |
||
1459
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
366 |
/* Check for signals */ |
1502
620b1d5904c4
(svn r2006) - Fix: [NPF] Wrong signal detection for last signal red detection. Multiple tracks per tile with only one signal were detected wrong. (HackyKid)
matthijs
parents:
1464
diff
changeset
|
367 |
if (IsTileType(tile, MP_RAILWAY) && (_map5[tile] & 0xC0) == 0x40 && (_map3_lo[tile] & _signal_along_trackdir[trackdir]) != 0) { |
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 |
/* Ordinary track with signals */ |
1247 | 369 |
if ((_map2[tile] & _signal_along_trackdir[trackdir]) == 0) { |
370 |
/* 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
|
371 |
if (!NPFGetFlag(current, NPF_FLAG_SEEN_SIGNAL)) { |
1247 | 372 |
/* Penalize the first signal we |
373 |
* encounter, if it is red */ |
|
374 |
cost += _patches.npf_rail_firstred_penalty; |
|
375 |
} |
|
1459
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
376 |
/* 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
|
377 |
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
|
378 |
} else { |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
379 |
/* 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
|
380 |
NPFSetFlag(current, NPF_FLAG_LAST_SIGNAL_RED, false); |
1247 | 381 |
} |
1459
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
382 |
NPFSetFlag(current, NPF_FLAG_SEEN_SIGNAL, true); |
1247 | 383 |
} |
384 |
||
1459
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
385 |
/* 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
|
386 |
* red */ |
1503
39d0f85977cf
(svn r2007) - Fix: [NPF] Slope penalties did not work correctly with foundations. (HackyKid)
matthijs
parents:
1502
diff
changeset
|
387 |
if (as->EndNodeCheck(as, current)==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
|
388 |
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
|
389 |
|
1247 | 390 |
/* Check for slope */ |
391 |
cost += NPFSlopeCost(current); |
|
392 |
||
393 |
/* Check for turns */ |
|
1460 | 394 |
if (current->direction != parent->path.node.direction) |
395 |
cost += _patches.npf_rail_curve_penalty; |
|
396 |
//TODO, with realistic acceleration, also the amount of straight track between |
|
397 |
// curves should be taken into account, as this affects the speed limit. |
|
1247 | 398 |
|
399 |
/* Check for occupied track */ |
|
400 |
//TODO |
|
401 |
||
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
402 |
#ifdef NPF_MARKROUTE |
1247 | 403 |
NPFMarkTile(tile); |
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
404 |
#endif |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
405 |
#ifdef NPF_DEBUG |
1247 | 406 |
debug("Calculating G for: (%d, %d). Result: %d", TileX(current->tile), TileY(current->tile), cost); |
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
407 |
#endif |
1247 | 408 |
return cost; |
409 |
} |
|
410 |
||
411 |
/* Will find any depot */ |
|
1459
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
412 |
int32 NPFFindDepot(AyStar* as, AyStarNode *node) { |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
413 |
TileIndex tile = node->tile; |
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
|
414 |
if (IsTileDepotType(tile, as->user_data[NPF_TYPE])) |
1247 | 415 |
return AYSTAR_FOUND_END_NODE; |
416 |
else |
|
417 |
return AYSTAR_DONE; |
|
418 |
} |
|
419 |
||
420 |
/* Will find a station identified using the NPFFindStationOrTileData */ |
|
1459
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
421 |
int32 NPFFindStationOrTile(AyStar* as, AyStarNode *node) { |
1464
fe5fcc14b2a2
(svn r1968) - Fix: [NPF] Mixed declarations and statements
matthijs
parents:
1463
diff
changeset
|
422 |
NPFFindStationOrTileData* fstd = (NPFFindStationOrTileData*)as->user_target; |
fe5fcc14b2a2
(svn r1968) - Fix: [NPF] Mixed declarations and statements
matthijs
parents:
1463
diff
changeset
|
423 |
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
|
424 |
|
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
425 |
/* See if we checked this before */ |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
426 |
if (NPFGetFlag(node, NPF_FLAG_TARGET_CHECKED)) |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
427 |
return NPFGetFlag(node, NPF_FLAG_IS_TARGET); |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
428 |
/* We're gonna check this now and store the result, let's mark that */ |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
429 |
NPFSetFlag(node, NPF_FLAG_TARGET_CHECKED, true); |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
430 |
|
1247 | 431 |
/* If GetNeighbours said we could get here, we assume the station type |
432 |
* 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
|
433 |
if ( |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
434 |
(fstd->station_index == -1 && tile == fstd->dest_coords) || /* We've found the tile, or */ |
1247 | 435 |
(IsTileType(tile, MP_STATION) && _map2[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
|
436 |
) { |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
437 |
NPFSetFlag(node, NPF_FLAG_TARGET_CHECKED, true); |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
438 |
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
|
439 |
} else { |
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
440 |
NPFSetFlag(node, NPF_FLAG_TARGET_CHECKED, false); |
1247 | 441 |
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
|
442 |
} |
1247 | 443 |
} |
444 |
||
445 |
/* To be called when current contains the (shortest route to) the target node. |
|
446 |
* Will fill the contents of the NPFFoundTargetData using |
|
447 |
* AyStarNode[NPF_TRACKDIR_CHOICE]. |
|
448 |
*/ |
|
449 |
void NPFSaveTargetData(AyStar* as, OpenListNode* current) { |
|
450 |
NPFFoundTargetData* ftd = (NPFFoundTargetData*)as->user_path; |
|
451 |
ftd->best_trackdir = current->path.node.user_data[NPF_TRACKDIR_CHOICE]; |
|
452 |
ftd->best_path_dist = current->g; |
|
453 |
ftd->best_bird_dist = 0; |
|
454 |
ftd->node = current->path.node; |
|
455 |
} |
|
456 |
||
457 |
/* Will just follow the results of GetTileTrackStatus concerning where we can |
|
458 |
* go and where not. Uses AyStar.user_data[NPF_TYPE] as the transport type and |
|
459 |
* 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
|
460 |
* 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
|
461 |
* 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
|
462 |
* copy AyStarNode.user_data[NPF_NODE_FLAGS] from the parent */ |
1247 | 463 |
void NPFFollowTrack(AyStar* aystar, OpenListNode* current) { |
464 |
byte src_trackdir = current->path.node.direction; |
|
465 |
TileIndex src_tile = current->path.node.tile; |
|
466 |
byte src_exitdir = _trackdir_to_exitdir[src_trackdir]; |
|
467 |
FindLengthOfTunnelResult flotr; |
|
468 |
TileIndex dst_tile; |
|
469 |
int i = 0; |
|
470 |
uint trackdirs, ts; |
|
471 |
TransportType type = aystar->user_data[NPF_TYPE]; |
|
472 |
/* Initialize to 0, so we can jump out (return) somewhere an have no neighbours */ |
|
473 |
aystar->num_neighbours = 0; |
|
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
474 |
#ifdef NPF_DEBUG |
1247 | 475 |
debug("Expanding: (%d, %d, %d) [%d]", TileX(src_tile), TileY(src_tile), src_trackdir, src_tile); |
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
476 |
#endif |
1247 | 477 |
|
478 |
/* Find dest tile */ |
|
479 |
if (IsTileType(src_tile, MP_TUNNELBRIDGE) && (_map5[src_tile] & 0xF0)==0 && (_map5[src_tile] & 3) == src_exitdir) { |
|
480 |
/* This is a tunnel. We know this tunnel is our type, |
|
481 |
* otherwise we wouldn't have got here. It is also facing us, |
|
482 |
* so we should skip it's body */ |
|
483 |
flotr = FindLengthOfTunnel(src_tile, src_exitdir); |
|
484 |
dst_tile = flotr.tile; |
|
485 |
} else { |
|
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
|
486 |
if (IsTileDepotType(src_tile, type)){ |
1247 | 487 |
/* This is a road station or a train or road depot. We can enter and exit |
488 |
* those from one side only. Trackdirs don't support that (yet), so we'll |
|
489 |
* do this here. */ |
|
490 |
||
491 |
byte exitdir; |
|
492 |
/* Find out the exit direction first */ |
|
493 |
if (IsRoadStationTile(src_tile)) |
|
494 |
exitdir = GetRoadStationDir(src_tile); |
|
495 |
else /* Train or road depot. Direction is stored the same for both, in map5 */ |
|
496 |
exitdir = _map5[src_tile] & 3; /* Extract the direction from the map */ |
|
497 |
||
498 |
/* Let's see if were headed the right way */ |
|
499 |
if (src_trackdir != _dir_to_diag_trackdir[exitdir]) |
|
500 |
/* Not going out of the station/depot through the exit, but the back. No |
|
501 |
* neighbours then. */ |
|
502 |
return; |
|
503 |
} |
|
504 |
/* This a normal tile, a bridge, a tunnel exit, etc. */ |
|
505 |
dst_tile = AddTileIndexDiffCWrap(src_tile, TileIndexDiffCByDir(_trackdir_to_exitdir[src_trackdir])); |
|
506 |
if (dst_tile == INVALID_TILE) { |
|
507 |
/* We reached the border of the map */ |
|
508 |
/* TODO Nicer control flow for this */ |
|
509 |
return; |
|
510 |
} |
|
511 |
} |
|
512 |
||
513 |
// TODO: check correct rail type (mono, maglev, etc) |
|
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
|
514 |
|
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
|
515 |
/* Check the owner of the tile */ |
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
|
516 |
if ( |
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
|
517 |
IsTileType(dst_tile, MP_RAILWAY) /* Rail tile */ |
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
|
518 |
|| IsTileDepotType(dst_tile, TRANSPORT_ROAD) /* Road depot tile */ |
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
|
519 |
|| IsTileType(dst_tile, MP_STATION) /* Station tile */ |
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
|
520 |
|| IsTileDepotType(dst_tile, TRANSPORT_WATER) /* Water depot tile */ |
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
|
521 |
) /* TODO: Crossings, tunnels and bridges are "public" now */ |
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
|
522 |
/* The above cases are "private" tiles, we need to check the owner */ |
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
|
523 |
if (!IsTileOwner(dst_tile, aystar->user_data[NPF_OWNER])) |
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
|
524 |
return; |
1247 | 525 |
|
526 |
/* Determine available tracks */ |
|
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
|
527 |
if (type == TRANSPORT_ROAD && (IsRoadStationTile(dst_tile) || IsTileDepotType(dst_tile, TRANSPORT_ROAD))){ |
1247 | 528 |
/* Road stations and depots return 0 on GTTS, so we have to do this by hand... */ |
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
|
529 |
byte exitdir; |
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
|
530 |
if (IsRoadStationTile(dst_tile)) |
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
|
531 |
exitdir = GetRoadStationDir(dst_tile); |
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
|
532 |
else /* Road depot */ |
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
|
533 |
/* Find the trackdirs that are available for a depot with this orientation. They are in both directions */ |
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
|
534 |
exitdir = _map5[dst_tile] & 3; /* Extract the direction from the map */ |
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
|
535 |
ts = (1 << _dir_to_diag_trackdir[exitdir]) |
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
|
536 |
| (1 << _dir_to_diag_trackdir[_reverse_dir[exitdir]]); |
1247 | 537 |
} else { |
538 |
ts = GetTileTrackStatus(dst_tile, type); |
|
539 |
} |
|
540 |
trackdirs = ts & 0x3F3F; /* Filter out signal status and the unused bits */ |
|
541 |
||
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
542 |
#ifdef NPF_DEBUG |
1247 | 543 |
debug("Next node: (%d, %d) [%d], possible trackdirs: %#x", TileX(dst_tile), TileY(dst_tile), dst_tile, trackdirs); |
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
544 |
#endif |
1247 | 545 |
/* Select only trackdirs we can reach from our current trackdir */ |
546 |
trackdirs &= _trackdir_reaches_trackdirs[src_trackdir]; |
|
547 |
if (_patches.forbid_90_deg && (type == TRANSPORT_RAIL || type == TRANSPORT_WATER)) /* Filter out trackdirs that would make 90 deg turns for trains */ |
|
548 |
trackdirs &= ~_trackdir_crosses_trackdirs[src_trackdir]; |
|
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
549 |
#ifdef NPF_DEBUG |
1247 | 550 |
debug("After filtering: (%d, %d), possible trackdirs: %#x", TileX(dst_tile), TileY(dst_tile), trackdirs); |
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
551 |
#endif |
1247 | 552 |
|
553 |
/* Enumerate possible track */ |
|
554 |
while (trackdirs != 0) { |
|
555 |
byte dst_trackdir; |
|
556 |
dst_trackdir = FindFirstBit2x64(trackdirs); |
|
557 |
trackdirs = KillFirstBit2x64(trackdirs); |
|
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
558 |
#ifdef NPF_DEBUG |
1247 | 559 |
debug("Expanded into trackdir: %d, remaining trackdirs: %#x", dst_trackdir, trackdirs); |
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
560 |
#endif |
1247 | 561 |
|
562 |
/* Check for oneway signal against us */ |
|
563 |
if (IsTileType(dst_tile, MP_RAILWAY) && (_map5[dst_tile]&0xC0) == 0x40) { |
|
564 |
// the tile has a signal |
|
565 |
byte signal_present = _map3_lo[dst_tile]; |
|
566 |
if (!(signal_present & _signal_along_trackdir[dst_trackdir])) { |
|
567 |
// if one way signal not pointing towards us, stop going in this direction. |
|
568 |
if (signal_present & _signal_against_trackdir[dst_trackdir]) |
|
569 |
break; |
|
570 |
} |
|
571 |
} |
|
572 |
{ |
|
573 |
/* We've found ourselves a neighbour :-) */ |
|
574 |
AyStarNode* neighbour = &aystar->neighbours[i]; |
|
575 |
neighbour->tile = dst_tile; |
|
576 |
neighbour->direction = dst_trackdir; |
|
577 |
/* Save user data */ |
|
578 |
neighbour->user_data[NPF_NODE_FLAGS] = current->path.node.user_data[NPF_NODE_FLAGS]; |
|
579 |
NPFFillTrackdirChoice(neighbour, current); |
|
580 |
} |
|
581 |
i++; |
|
582 |
} |
|
583 |
aystar->num_neighbours = i; |
|
584 |
} |
|
585 |
||
586 |
/* |
|
587 |
* Plan a route to the specified target (which is checked by target_proc), |
|
588 |
* from start1 and if not NULL, from start2 as well. The type of transport we |
|
589 |
* are checking is in type. |
|
590 |
* When we are looking for one specific target (optionally multiple tiles), we |
|
591 |
* should use a good heuristic to perform aystar search. When we search for |
|
592 |
* multiple targets that are spread around, we should perform a breadth first |
|
593 |
* search by specifiying CalcZero as our heuristic. |
|
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 |
NPFFoundTargetData NPFRouteInternal(AyStarNode* start1, AyStarNode* start2, NPFFindStationOrTileData* target, AyStar_EndNodeCheck target_proc, AyStar_CalculateH heuristic_proc, TransportType type, Owner owner) { |
1247 | 596 |
int r; |
597 |
NPFFoundTargetData result; |
|
598 |
||
599 |
/* Initialize procs */ |
|
600 |
_npf_aystar.CalculateH = heuristic_proc; |
|
601 |
_npf_aystar.EndNodeCheck = target_proc; |
|
602 |
_npf_aystar.FoundEndNode = NPFSaveTargetData; |
|
603 |
_npf_aystar.GetNeighbours = NPFFollowTrack; |
|
604 |
if (type == TRANSPORT_RAIL) |
|
605 |
_npf_aystar.CalculateG = NPFRailPathCost; |
|
606 |
else if (type == TRANSPORT_ROAD) |
|
607 |
_npf_aystar.CalculateG = NPFRoadPathCost; |
|
608 |
else if (type == TRANSPORT_WATER) |
|
609 |
_npf_aystar.CalculateG = NPFWaterPathCost; |
|
610 |
else |
|
611 |
assert(0); |
|
612 |
||
613 |
/* Initialize Start Node(s) */ |
|
614 |
start1->user_data[NPF_TRACKDIR_CHOICE] = 0xff; |
|
615 |
start1->user_data[NPF_NODE_FLAGS] = 0; |
|
616 |
_npf_aystar.addstart(&_npf_aystar, start1); |
|
617 |
if (start2) { |
|
618 |
start2->user_data[NPF_TRACKDIR_CHOICE] = 0xff; |
|
1459
19333d7f99b3
(svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents:
1453
diff
changeset
|
619 |
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
|
620 |
NPFSetFlag(start2, NPF_FLAG_REVERSE, true); |
1247 | 621 |
_npf_aystar.addstart(&_npf_aystar, start2); |
622 |
} |
|
623 |
||
624 |
/* Initialize result */ |
|
625 |
result.best_bird_dist = (uint)-1; |
|
626 |
result.best_path_dist = (uint)-1; |
|
627 |
result.best_trackdir = 0xff; |
|
628 |
_npf_aystar.user_path = &result; |
|
629 |
||
630 |
/* Initialize target */ |
|
631 |
_npf_aystar.user_target = target; |
|
632 |
||
633 |
/* Initialize user_data */ |
|
634 |
_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
|
635 |
_npf_aystar.user_data[NPF_OWNER] = owner; |
1247 | 636 |
|
637 |
/* GO! */ |
|
638 |
r = AyStarMain_Main(&_npf_aystar); |
|
639 |
assert(r != AYSTAR_STILL_BUSY); |
|
640 |
||
641 |
if (result.best_bird_dist != 0) { |
|
642 |
if (target) { |
|
643 |
DEBUG(misc, 1) ("NPF: Could not find route to 0x%x from 0x%x.", target->dest_coords, start1->tile); |
|
644 |
} else { |
|
645 |
/* Assumption: target == NULL, so we are looking for a depot */ |
|
646 |
DEBUG(misc, 1) ("NPF: Could not find route to a depot from 0x%x.", start1->tile); |
|
647 |
} |
|
648 |
||
649 |
} |
|
650 |
return result; |
|
651 |
} |
|
652 |
||
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
|
653 |
NPFFoundTargetData NPFRouteToStationOrTileTwoWay(TileIndex tile1, byte trackdir1, TileIndex tile2, byte trackdir2, NPFFindStationOrTileData* target, TransportType type, Owner owner) { |
1247 | 654 |
AyStarNode start1; |
655 |
AyStarNode start2; |
|
656 |
||
657 |
start1.tile = tile1; |
|
658 |
start2.tile = tile2; |
|
659 |
start1.direction = trackdir1; |
|
660 |
start2.direction = trackdir2; |
|
661 |
||
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
|
662 |
return NPFRouteInternal(&start1, &start2, target, NPFFindStationOrTile, NPFCalcStationOrTileHeuristic, type, owner); |
1247 | 663 |
} |
664 |
||
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
|
665 |
NPFFoundTargetData NPFRouteToStationOrTile(TileIndex tile, byte trackdir, NPFFindStationOrTileData* target, TransportType type, Owner owner) { |
1247 | 666 |
AyStarNode start; |
667 |
||
668 |
assert(tile != 0); |
|
669 |
||
670 |
start.tile = tile; |
|
671 |
start.direction = trackdir; |
|
672 |
/* We set this in case the target is also the start tile, we will just |
|
673 |
* return a not found then */ |
|
674 |
start.user_data[NPF_TRACKDIR_CHOICE] = 0xff; |
|
675 |
||
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
|
676 |
return NPFRouteInternal(&start, NULL, target, NPFFindStationOrTile, NPFCalcStationOrTileHeuristic, type, owner); |
1247 | 677 |
} |
678 |
||
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
|
679 |
NPFFoundTargetData NPFRouteToDepotBreadthFirst(TileIndex tile, byte trackdir, TransportType type, Owner owner) { |
1247 | 680 |
AyStarNode start; |
681 |
||
682 |
start.tile = tile; |
|
683 |
start.direction = trackdir; |
|
684 |
/* We set this in case the target is also the start tile, we will just |
|
685 |
* return a not found then */ |
|
686 |
start.user_data[NPF_TRACKDIR_CHOICE] = 0xff; |
|
687 |
||
688 |
/* perform a breadth first search. Target is NULL, |
|
689 |
* since we are just looking for any 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
|
690 |
return NPFRouteInternal(&start, NULL, NULL, NPFFindDepot, NPFCalcZero, type, owner); |
1247 | 691 |
} |
692 |
||
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
|
693 |
NPFFoundTargetData NPFRouteToDepotTrialError(TileIndex tile, byte trackdir, TransportType type, Owner owner) { |
1247 | 694 |
/* Okay, what we're gonna do. First, we look at all depots, calculate |
695 |
* the manhatten distance to get to each depot. We then sort them by |
|
696 |
* distance. We start by trying to plan a route to the closest, then |
|
697 |
* the next closest, etc. We stop when the best route we have found so |
|
698 |
* far, is shorter than the manhattan distance. This will obviously |
|
699 |
* always find the closest depot. It will probably be most efficient |
|
700 |
* for ships, since the heuristic will not be to far off then. I hope. |
|
701 |
*/ |
|
702 |
Queue depots; |
|
703 |
int r; |
|
704 |
NPFFoundTargetData best_result; |
|
705 |
NPFFoundTargetData result; |
|
706 |
NPFFindStationOrTileData target; |
|
707 |
AyStarNode start; |
|
708 |
Depot* current; |
|
1313
f1013ec3d318
(svn r1817) -Codechange: Moved depot-functions to depot.c
truelight
parents:
1299
diff
changeset
|
709 |
Depot *depot; |
1247 | 710 |
|
711 |
init_InsSort(&depots); |
|
712 |
/* 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
|
713 |
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
|
714 |
/* 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
|
715 |
* owner */ |
1338 | 716 |
if (IsValidDepot(depot) && 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
|
717 |
/* 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
|
718 |
depots.push(&depots, depot, DistanceManhattan(tile, depot->xy)); |
1247 | 719 |
} |
720 |
||
721 |
/* Now, let's initialise the aystar */ |
|
722 |
||
723 |
/* Initialize procs */ |
|
724 |
_npf_aystar.CalculateH = NPFCalcStationOrTileHeuristic; |
|
725 |
_npf_aystar.EndNodeCheck = NPFFindStationOrTile; |
|
726 |
_npf_aystar.FoundEndNode = NPFSaveTargetData; |
|
727 |
_npf_aystar.GetNeighbours = NPFFollowTrack; |
|
728 |
if (type == TRANSPORT_RAIL) |
|
729 |
_npf_aystar.CalculateG = NPFRailPathCost; |
|
730 |
else if (type == TRANSPORT_ROAD) |
|
731 |
_npf_aystar.CalculateG = NPFRoadPathCost; |
|
732 |
else if (type == TRANSPORT_WATER) |
|
733 |
_npf_aystar.CalculateG = NPFWaterPathCost; |
|
734 |
else |
|
735 |
assert(0); |
|
736 |
||
737 |
/* Initialize target */ |
|
738 |
target.station_index = -1; /* We will initialize dest_coords inside the loop below */ |
|
739 |
_npf_aystar.user_target = ⌖ |
|
740 |
||
741 |
/* Initialize user_data */ |
|
742 |
_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
|
743 |
_npf_aystar.user_data[NPF_OWNER] = owner; |
1247 | 744 |
|
745 |
/* Initialize Start Node */ |
|
746 |
start.tile = tile; |
|
747 |
start.direction = trackdir; /* We will initialize user_data inside the loop below */ |
|
748 |
||
749 |
/* Initialize Result */ |
|
750 |
_npf_aystar.user_path = &result; |
|
751 |
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
|
752 |
best_result.best_bird_dist = (uint)-1; |
1247 | 753 |
|
754 |
/* Just iterate the depots in order of increasing distance */ |
|
755 |
while ((current = depots.pop(&depots))) { |
|
756 |
/* 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
|
757 |
* depot's manhattan distance. HACK: We call DistanceManhattan |
1247 | 758 |
* again, we should probably modify the queue to give us that |
759 |
* value... */ |
|
760 |
if ( DistanceManhattan(tile, current->xy * NPF_TILE_LENGTH) > best_result.best_path_dist) |
|
761 |
break; |
|
762 |
||
763 |
/* Initialize Start Node */ |
|
764 |
/* We set this in case the target is also the start tile, we will just |
|
765 |
* return a not found then */ |
|
766 |
start.user_data[NPF_TRACKDIR_CHOICE] = 0xff; |
|
767 |
start.user_data[NPF_NODE_FLAGS] = 0; |
|
768 |
_npf_aystar.addstart(&_npf_aystar, &start); |
|
769 |
||
770 |
/* Initialize result */ |
|
771 |
result.best_bird_dist = (uint)-1; |
|
772 |
result.best_path_dist = (uint)-1; |
|
773 |
result.best_trackdir = 0xff; |
|
774 |
||
775 |
/* Initialize target */ |
|
776 |
target.dest_coords = current->xy; |
|
777 |
||
778 |
/* GO! */ |
|
779 |
r = AyStarMain_Main(&_npf_aystar); |
|
780 |
assert(r != AYSTAR_STILL_BUSY); |
|
781 |
||
782 |
/* This depot is closer */ |
|
783 |
if (result.best_path_dist < best_result.best_path_dist) |
|
784 |
best_result = result; |
|
785 |
} |
|
786 |
if (result.best_bird_dist != 0) { |
|
787 |
DEBUG(misc, 1) ("NPF: Could not find route to any depot from 0x%x.", tile); |
|
788 |
} |
|
789 |
return best_result; |
|
790 |
} |
|
791 |
||
792 |
void InitializeNPF(void) |
|
793 |
{ |
|
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
794 |
init_AyStar(&_npf_aystar, NTPHash, 1024); |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
795 |
_npf_aystar.loops_per_tick = 0; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
796 |
_npf_aystar.max_path_cost = 0; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
797 |
_npf_aystar.max_search_nodes = 0; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
798 |
#if 0 |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
799 |
init_AyStar(&_train_find_station, NTPHash, 1024); |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
800 |
init_AyStar(&_train_find_depot, NTPHash, 1024); |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
801 |
init_AyStar(&_road_find_station, NTPHash, 1024); |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
802 |
init_AyStar(&_road_find_depot, NTPHash, 1024); |
1247 | 803 |
|
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
804 |
_train_find_station.loops_per_tick = 0; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
805 |
_train_find_depot.loops_per_tick = 0; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
806 |
_road_find_station.loops_per_tick = 0; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
807 |
_road_find_depot.loops_per_tick = 0; |
1247 | 808 |
|
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
809 |
_train_find_station.max_path_cost = 0; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
810 |
_train_find_depot.max_path_cost = 0; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
811 |
_road_find_station.max_path_cost = 0; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
812 |
_road_find_depot.max_path_cost = 0; |
1247 | 813 |
|
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
814 |
_train_find_station.max_search_nodes = 0; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
815 |
_train_find_depot.max_search_nodes = 0; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
816 |
_road_find_station.max_search_nodes = 0; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
817 |
_road_find_depot.max_search_nodes = 0; |
1247 | 818 |
|
1463
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
819 |
_train_find_station.CalculateG = NPFRailPathCost; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
820 |
_train_find_depot.CalculateG = NPFRailPathCost; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
821 |
_road_find_station.CalculateG = NPFRoadPathCost; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
822 |
_road_find_depot.CalculateG = NPFRoadPathCost; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
823 |
|
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
824 |
_train_find_station.CalculateH = NPFCalcStationHeuristic; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
825 |
_train_find_depot.CalculateH = NPFCalcStationHeuristic; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
826 |
_road_find_station.CalculateH = NPFCalcStationHeuristic; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
827 |
_road_find_depot.CalculateH = NPFCalcStationHeuristic; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
828 |
|
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
829 |
_train_find_station.EndNodeCheck = NPFFindStationOrTile; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
830 |
_train_find_depot.EndNodeCheck = NPFFindStationOrTile; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
831 |
_road_find_station.EndNodeCheck = NPFFindStationOrTile; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
832 |
_road_find_depot.EndNodeCheck = NPFFindStationOrTile; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
833 |
|
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
834 |
_train_find_station.FoundEndNode = NPFSaveTargetData; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
835 |
_train_find_depot.FoundEndNode = NPFSaveTargetData; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
836 |
_road_find_station.FoundEndNode = NPFSaveTargetData; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
837 |
_road_find_depot.FoundEndNode = NPFSaveTargetData; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
838 |
|
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
839 |
_train_find_station.GetNeighbours = NPFFollowTrack; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
840 |
_train_find_depot.GetNeighbours = NPFFollowTrack; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
841 |
_road_find_station.GetNeighbours = NPFFollowTrack; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
842 |
_road_find_depot.GetNeighbours = NPFFollowTrack; |
85a05f2da980
(svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents:
1460
diff
changeset
|
843 |
#endif |
1247 | 844 |
} |
845 |
||
846 |
void NPFFillWithOrderData(NPFFindStationOrTileData* fstd, Vehicle* v) { |
|
847 |
/* Ships don't really reach their stations, but the tile in front. So don't |
|
848 |
* save the station id for ships. For roadvehs we don't store it either, |
|
849 |
* because multistop depends on vehicles actually reaching the exact |
|
850 |
* dest_tile, not just any stop of that station. |
|
851 |
* So only for train orders to stations we fill fstd->station_index, for all |
|
852 |
* others only dest_coords */ |
|
853 |
if ((v->current_order.type) == OT_GOTO_STATION && v->type == VEH_Train) { |
|
854 |
fstd->station_index = v->current_order.station; |
|
1452
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
855 |
/* Let's take the closest tile of the station as our target for trains */ |
a978fdcbca3e
(svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents:
1339
diff
changeset
|
856 |
fstd->dest_coords = CalcClosestStationTile(v->current_order.station, v->tile); |
1247 | 857 |
} else { |
858 |
fstd->dest_coords = v->dest_tile; |
|
859 |
fstd->station_index = -1; |
|
860 |
} |
|
861 |
} |