summaryrefslogtreecommitdiff
path: root/src/yapf/yapf_road.cpp
blob: 55ace4a12e75d5a3ea395588b5cf6440e87c6e5e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
/* $Id$ */

/** @file yapf_road.cpp The road pathfinding. */

#include "../stdafx.h"
#include "../depot_base.h"

#include "yapf.hpp"
#include "yapf_node_road.hpp"


template <class Types>
class CYapfCostRoadT
{
public:
	typedef typename Types::Tpf Tpf; ///< pathfinder (derived from THIS class)
	typedef typename Types::TrackFollower TrackFollower; ///< track follower helper
	typedef typename Types::NodeList::Titem Node; ///< this will be our node type
	typedef typename Node::Key Key;    ///< key to hash tables

protected:
	/// to access inherited path finder
	Tpf& Yapf() {return *static_cast<Tpf*>(this);}

	int SlopeCost(TileIndex tile, TileIndex next_tile, Trackdir trackdir)
	{
		// height of the center of the current tile
		int x1 = TileX(tile) * TILE_SIZE;
		int y1 = TileY(tile) * TILE_SIZE;
		int z1 = GetSlopeZ(x1 + TILE_SIZE / 2, y1 + TILE_SIZE / 2);

		// height of the center of the next tile
		int x2 = TileX(next_tile) * TILE_SIZE;
		int y2 = TileY(next_tile) * TILE_SIZE;
		int z2 = GetSlopeZ(x2 + TILE_SIZE / 2, y2 + TILE_SIZE / 2);

		if (z2 - z1 > 1) {
			/* Slope up */
			return Yapf().PfGetSettings().road_slope_penalty;
		}
		return 0;
	}

	/** return one tile cost */
	FORCEINLINE int OneTileCost(TileIndex tile, Trackdir trackdir)
	{
		int cost = 0;
		// set base cost
		if (IsDiagonalTrackdir(trackdir)) {
			cost += YAPF_TILE_LENGTH;
			switch (GetTileType(tile)) {
				case MP_ROAD:
					/* Increase the cost for level crossings */
					if (IsLevelCrossing(tile))
						cost += Yapf().PfGetSettings().road_crossing_penalty;
					break;
				case MP_STATION:
					if (IsDriveThroughStopTile(tile))
						cost += Yapf().PfGetSettings().road_stop_penalty;
					break;

				default:
					break;
			}
		} else {
			// non-diagonal trackdir
			cost = YAPF_TILE_CORNER_LENGTH + Yapf().PfGetSettings().road_curve_penalty;
		}
		return cost;
	}

public:
	/** Called by YAPF to calculate the cost from the origin to the given node.
	 *  Calculates only the cost of given node, adds it to the parent node cost
	 *  and stores the result into Node::m_cost member */
	FORCEINLINE bool PfCalcCost(Node& n, const TrackFollower *tf)
	{
		int segment_cost = 0;
		// start at n.m_key.m_tile / n.m_key.m_td and walk to the end of segment
		TileIndex tile = n.m_key.m_tile;
		Trackdir trackdir = n.m_key.m_td;
		while (true) {
			// base tile cost depending on distance between edges
			segment_cost += Yapf().OneTileCost(tile, trackdir);

			const Vehicle *v = Yapf().GetVehicle();
			// we have reached the vehicle's destination - segment should end here to avoid target skipping
			if (v->current_order.IsType(OT_GOTO_STATION) && tile == v->dest_tile) break;

			// stop if we have just entered the depot
			if (IsRoadDepotTile(tile) && trackdir == DiagDirToDiagTrackdir(ReverseDiagDir(GetRoadDepotDirection(tile)))) {
				// next time we will reverse and leave the depot
				break;
			}

			// if there are no reachable trackdirs on new tile, we have end of road
			TrackFollower F(Yapf().GetVehicle());
			if (!F.Follow(tile, trackdir)) break;

			// if there are more trackdirs available & reachable, we are at the end of segment
			if (KillFirstBit(F.m_new_td_bits) != TRACKDIR_BIT_NONE) break;

			Trackdir new_td = (Trackdir)FindFirstBit2x64(F.m_new_td_bits);

			// stop if RV is on simple loop with no junctions
			if (F.m_new_tile == n.m_key.m_tile && new_td == n.m_key.m_td) return false;

			// if we skipped some tunnel tiles, add their cost
			segment_cost += F.m_tiles_skipped * YAPF_TILE_LENGTH;

			// add hilly terrain penalty
			segment_cost += Yapf().SlopeCost(tile, F.m_new_tile, trackdir);

			// add min/max speed penalties
			int min_speed = 0;
			int max_speed = F.GetSpeedLimit(&min_speed);
			if (max_speed < v->max_speed) segment_cost += 1 * (v->max_speed - max_speed);
			if (min_speed > v->max_speed) segment_cost += 10 * (min_speed - v->max_speed);

			// move to the next tile
			tile = F.m_new_tile;
			trackdir = new_td;
		};

		// save end of segment back to the node
		n.m_segment_last_tile = tile;
		n.m_segment_last_td = trackdir;

		// save also tile cost
		int parent_cost = (n.m_parent != NULL) ? n.m_parent->m_cost : 0;
		n.m_cost = parent_cost + segment_cost;
		return true;
	}
};


template <class Types>
class CYapfDestinationAnyDepotRoadT
{
public:
	typedef typename Types::Tpf Tpf;                     ///< the pathfinder class (derived from THIS class)
	typedef typename Types::TrackFollower TrackFollower;
	typedef typename Types::NodeList::Titem Node;        ///< this will be our node type
	typedef typename Node::Key Key;                      ///< key to hash tables

	/// to access inherited path finder
	Tpf& Yapf() {return *static_cast<Tpf*>(this);}

	/// Called by YAPF to detect if node ends in the desired destination
	FORCEINLINE bool PfDetectDestination(Node& n)
	{
		bool bDest = IsRoadDepotTile(n.m_segment_last_tile);
		return bDest;
	}

	/** Called by YAPF to calculate cost estimate. Calculates distance to the destination
	 *  adds it to the actual cost from origin and stores the sum to the Node::m_estimate */
	FORCEINLINE bool PfCalcEstimate(Node& n)
	{
		n.m_estimate = n.m_cost;
		return true;
	}
};


template <class Types>
class CYapfDestinationTileRoadT
{
public:
	typedef typename Types::Tpf Tpf;                     ///< the pathfinder class (derived from THIS class)
	typedef typename Types::TrackFollower TrackFollower;
	typedef typename Types::NodeList::Titem Node;        ///< this will be our node type
	typedef typename Node::Key Key;                      ///< key to hash tables

protected:
	TileIndex    m_destTile;
	TrackdirBits m_destTrackdirs;

public:
	void SetDestination(TileIndex tile, TrackdirBits trackdirs)
	{
		m_destTile = tile;
		m_destTrackdirs = trackdirs;
	}

protected:
	/// to access inherited path finder
	Tpf& Yapf() {return *static_cast<Tpf*>(this);}

public:
	/// Called by YAPF to detect if node ends in the desired destination
	FORCEINLINE bool PfDetectDestination(Node& n)
	{
		bool bDest = (n.m_segment_last_tile == m_destTile) && ((m_destTrackdirs & TrackdirToTrackdirBits(n.m_segment_last_td)) != TRACKDIR_BIT_NONE);
		return bDest;
	}

	/** Called by YAPF to calculate cost estimate. Calculates distance to the destination
	 *  adds it to the actual cost from origin and stores the sum to the Node::m_estimate */
	inline bool PfCalcEstimate(Node& n)
	{
		static int dg_dir_to_x_offs[] = {-1, 0, 1, 0};
		static int dg_dir_to_y_offs[] = {0, 1, 0, -1};
		if (PfDetectDestination(n)) {
			n.m_estimate = n.m_cost;
			return true;
		}

		TileIndex tile = n.m_segment_last_tile;
		DiagDirection exitdir = TrackdirToExitdir(n.m_segment_last_td);
		int x1 = 2 * TileX(tile) + dg_dir_to_x_offs[(int)exitdir];
		int y1 = 2 * TileY(tile) + dg_dir_to_y_offs[(int)exitdir];
		int x2 = 2 * TileX(m_destTile);
		int y2 = 2 * TileY(m_destTile);
		int dx = abs(x1 - x2);
		int dy = abs(y1 - y2);
		int dmin = min(dx, dy);
		int dxy = abs(dx - dy);
		int d = dmin * YAPF_TILE_CORNER_LENGTH + (dxy - 1) * (YAPF_TILE_LENGTH / 2);
		n.m_estimate = n.m_cost + d;
		assert(n.m_estimate >= n.m_parent->m_estimate);
		return true;
	}
};



template <class Types>
class CYapfFollowRoadT
{
public:
	typedef typename Types::Tpf Tpf;                     ///< the pathfinder class (derived from THIS class)
	typedef typename Types::TrackFollower TrackFollower;
	typedef typename Types::NodeList::Titem Node;        ///< this will be our node type
	typedef typename Node::Key Key;                      ///< key to hash tables

protected:
	/// to access inherited path finder
	FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);}

public:

	/** Called by YAPF to move from the given node to the next tile. For each
	 *  reachable trackdir on the new tile creates new node, initializes it
	 *  and adds it to the open list by calling Yapf().AddNewNode(n) */
	inline void PfFollowNode(Node& old_node)
	{
		TrackFollower F(Yapf().GetVehicle());
		if (F.Follow(old_node.m_segment_last_tile, old_node.m_segment_last_td))
			Yapf().AddMultipleNodes(&old_node, F);
	}

	/// return debug report character to identify the transportation type
	FORCEINLINE char TransportTypeChar() const {return 'r';}

	static Trackdir stChooseRoadTrack(const Vehicle *v, TileIndex tile, DiagDirection enterdir)
	{
		Tpf pf;
		return pf.ChooseRoadTrack(v, tile, enterdir);
	}

	FORCEINLINE Trackdir ChooseRoadTrack(const Vehicle *v, TileIndex tile, DiagDirection enterdir)
	{
		// handle special case - when next tile is destination tile
		if (tile == v->dest_tile) {
			// choose diagonal trackdir reachable from enterdir
			return DiagDirToDiagTrackdir(enterdir);
		}
		// our source tile will be the next vehicle tile (should be the given one)
		TileIndex src_tile = tile;
		// get available trackdirs on the start tile
		TrackdirBits src_trackdirs = TrackStatusToTrackdirBits(GetTileTrackStatus(tile, TRANSPORT_ROAD, v->u.road.compatible_roadtypes));
		// select reachable trackdirs only
		src_trackdirs &= DiagdirReachesTrackdirs(enterdir);

		// get available trackdirs on the destination tile
		TileIndex dest_tile = v->dest_tile;
		TrackdirBits dest_trackdirs = TrackStatusToTrackdirBits(GetTileTrackStatus(dest_tile, TRANSPORT_ROAD, v->u.road.compatible_roadtypes));

		// set origin and destination nodes
		Yapf().SetOrigin(src_tile, src_trackdirs);
		Yapf().SetDestination(dest_tile, dest_trackdirs);

		// find the best path
		Yapf().FindPath(v);

		// if path not found - return INVALID_TRACKDIR
		Trackdir next_trackdir = INVALID_TRACKDIR;
		Node *pNode = Yapf().GetBestNode();
		if (pNode != NULL) {
			// path was found or at least suggested
			// walk through the path back to its origin
			while (pNode->m_parent != NULL) {
				pNode = pNode->m_parent;
			}
			// return trackdir from the best origin node (one of start nodes)
			Node& best_next_node = *pNode;
			assert(best_next_node.GetTile() == tile);
			next_trackdir = best_next_node.GetTrackdir();
		}
		return next_trackdir;
	}

	static uint stDistanceToTile(const Vehicle *v, TileIndex tile)
	{
		Tpf pf;
		return pf.DistanceToTile(v, tile);
	}

	FORCEINLINE uint DistanceToTile(const Vehicle *v, TileIndex dst_tile)
	{
		// handle special case - when current tile is the destination tile
		if (dst_tile == v->tile) {
			// distance is zero in this case
			return 0;
		}

		if (!SetOriginFromVehiclePos(v)) return UINT_MAX;

		// set destination tile, trackdir
		//   get available trackdirs on the destination tile
		TrackdirBits dst_td_bits = TrackStatusToTrackdirBits(GetTileTrackStatus(dst_tile, TRANSPORT_ROAD, v->u.road.compatible_roadtypes));
		Yapf().SetDestination(dst_tile, dst_td_bits);

		// if path not found - return distance = UINT_MAX
		uint dist = UINT_MAX;

		// find the best path
		if (!Yapf().FindPath(v)) return dist;

		Node *pNode = Yapf().GetBestNode();
		if (pNode != NULL) {
			// path was found
			// get the path cost estimate
			dist = pNode->GetCostEstimate();
		}

		return dist;
	}

	/** Return true if the valid origin (tile/trackdir) was set from the current vehicle position. */
	FORCEINLINE bool SetOriginFromVehiclePos(const Vehicle *v)
	{
		// set origin (tile, trackdir)
		TileIndex src_tile = v->tile;
		Trackdir src_td = GetVehicleTrackdir(v);
		if ((TrackStatusToTrackdirBits(GetTileTrackStatus(src_tile, TRANSPORT_ROAD, v->u.road.compatible_roadtypes)) & TrackdirToTrackdirBits(src_td)) == 0) {
			// sometimes the roadveh is not on the road (it resides on non-existing track)
			// how should we handle that situation?
			return false;
		}
		Yapf().SetOrigin(src_tile, TrackdirToTrackdirBits(src_td));
		return true;
	}

	static Depot* stFindNearestDepot(const Vehicle* v, TileIndex tile, Trackdir td)
	{
		Tpf pf;
		return pf.FindNearestDepot(v, tile, td);
	}

	FORCEINLINE Depot* FindNearestDepot(const Vehicle* v, TileIndex tile, Trackdir td)
	{
		// set origin and destination nodes
		Yapf().SetOrigin(tile, TrackdirToTrackdirBits(td));

		// find the best path
		bool bFound = Yapf().FindPath(v);
		if (!bFound) return false;

		// some path found
		// get found depot tile
		Node *n = Yapf().GetBestNode();
		TileIndex depot_tile = n->m_segment_last_tile;
		assert(IsRoadDepotTile(depot_tile));
		Depot* ret = GetDepotByTile(depot_tile);
		return ret;
	}
};

template <class Tpf_, class Tnode_list, template <class Types> class Tdestination>
struct CYapfRoad_TypesT
{
	typedef CYapfRoad_TypesT<Tpf_, Tnode_list, Tdestination>  Types;

	typedef Tpf_                              Tpf;
	typedef CFollowTrackRoad                  TrackFollower;
	typedef Tnode_list                        NodeList;
	typedef CYapfBaseT<Types>                 PfBase;
	typedef CYapfFollowRoadT<Types>           PfFollow;
	typedef CYapfOriginTileT<Types>           PfOrigin;
	typedef Tdestination<Types>               PfDestination;
	typedef CYapfSegmentCostCacheNoneT<Types> PfCache;
	typedef CYapfCostRoadT<Types>             PfCost;
};

struct CYapfRoad1         : CYapfT<CYapfRoad_TypesT<CYapfRoad1        , CRoadNodeListTrackDir, CYapfDestinationTileRoadT    > > {};
struct CYapfRoad2         : CYapfT<CYapfRoad_TypesT<CYapfRoad2        , CRoadNodeListExitDir , CYapfDestinationTileRoadT    > > {};

struct CYapfRoadAnyDepot1 : CYapfT<CYapfRoad_TypesT<CYapfRoadAnyDepot1, CRoadNodeListTrackDir, CYapfDestinationAnyDepotRoadT> > {};
struct CYapfRoadAnyDepot2 : CYapfT<CYapfRoad_TypesT<CYapfRoadAnyDepot2, CRoadNodeListExitDir , CYapfDestinationAnyDepotRoadT> > {};


Trackdir YapfChooseRoadTrack(const Vehicle *v, TileIndex tile, DiagDirection enterdir)
{
	// default is YAPF type 2
	typedef Trackdir (*PfnChooseRoadTrack)(const Vehicle*, TileIndex, DiagDirection);
	PfnChooseRoadTrack pfnChooseRoadTrack = &CYapfRoad2::stChooseRoadTrack; // default: ExitDir, allow 90-deg

	// check if non-default YAPF type should be used
	if (_settings_game.pf.yapf.disable_node_optimization) {
		pfnChooseRoadTrack = &CYapfRoad1::stChooseRoadTrack; // Trackdir, allow 90-deg
	}

	Trackdir td_ret = pfnChooseRoadTrack(v, tile, enterdir);
	return td_ret;
}

uint YapfRoadVehDistanceToTile(const Vehicle *v, TileIndex tile)
{
	// default is YAPF type 2
	typedef uint (*PfnDistanceToTile)(const Vehicle*, TileIndex);
	PfnDistanceToTile pfnDistanceToTile = &CYapfRoad2::stDistanceToTile; // default: ExitDir, allow 90-deg

	// check if non-default YAPF type should be used
	if (_settings_game.pf.yapf.disable_node_optimization)
		pfnDistanceToTile = &CYapfRoad1::stDistanceToTile; // Trackdir, allow 90-deg

	// measure distance in YAPF units
	uint dist = pfnDistanceToTile(v, tile);
	// convert distance to tiles
	if (dist != UINT_MAX)
		dist = (dist + YAPF_TILE_LENGTH - 1) / YAPF_TILE_LENGTH;
	return dist;
}

Depot* YapfFindNearestRoadDepot(const Vehicle *v)
{
	TileIndex tile = v->tile;
	Trackdir trackdir = GetVehicleTrackdir(v);
	if ((TrackStatusToTrackdirBits(GetTileTrackStatus(tile, TRANSPORT_ROAD, v->u.road.compatible_roadtypes)) & TrackdirToTrackdirBits(trackdir)) == 0)
		return NULL;

	// handle the case when our vehicle is already in the depot tile
	if (IsRoadDepotTile(tile)) {
		// only what we need to return is the Depot*
		return GetDepotByTile(tile);
	}

	// default is YAPF type 2
	typedef Depot* (*PfnFindNearestDepot)(const Vehicle*, TileIndex, Trackdir);
	PfnFindNearestDepot pfnFindNearestDepot = &CYapfRoadAnyDepot2::stFindNearestDepot;

	// check if non-default YAPF type should be used
	if (_settings_game.pf.yapf.disable_node_optimization)
		pfnFindNearestDepot = &CYapfRoadAnyDepot1::stFindNearestDepot; // Trackdir, allow 90-deg

	Depot* ret = pfnFindNearestDepot(v, tile, trackdir);
	return ret;
}