src/pathfind.h
author smatz
Wed, 24 Sep 2008 16:40:06 +0000
changeset 10184 bf4e3ff4cf16
parent 9111 48ce04029fe4
permissions -rw-r--r--
(svn r14395) -Fix [FS#2285]: crashes and GUI desyncs when order is deleted/modified while the timetable window is open
-Fix: close any dropdown and child windows in the Order and Timetable windows when selected order is deselected, deleted, ...
2186
db48cf29b983 (svn r2701) Insert Id tags into all source files
tron
parents: 2125
diff changeset
     1
/* $Id$ */
db48cf29b983 (svn r2701) Insert Id tags into all source files
tron
parents: 2125
diff changeset
     2
9111
48ce04029fe4 (svn r12971) -Documentation: add @file in files that missed them and add something more than whitespace as description of files that don't have a description.
rubidium
parents: 8800
diff changeset
     3
/** @file pathfind.h The oldest pathfinder that's supported. */
6352
938ab8f48e5d (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas
parents: 6248
diff changeset
     4
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
     5
#ifndef PATHFIND_H
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
     6
#define PATHFIND_H
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
     7
8100
6bc08f98ec16 (svn r11661) -Codechange: some header reworks in order to try to reduce the compile time of OpenTTD by reduce the amount of circular-ish dependencies.
rubidium
parents: 6683
diff changeset
     8
#include "direction_type.h"
3153
e83501906eae (svn r3776) Replace many ints and magic numbers by Direction, DiagDirection and friends
tron
parents: 2493
diff changeset
     9
4406
cc20171473bb (svn r6159) -Fix: FindClosestTrainDepot hardly ever found a depot with NPF off due to absence of distance-normalization (Rojer)
Darkvater
parents: 4000
diff changeset
    10
enum {
cc20171473bb (svn r6159) -Fix: FindClosestTrainDepot hardly ever found a depot with NPF off due to absence of distance-normalization (Rojer)
Darkvater
parents: 4000
diff changeset
    11
	STR_FACTOR  = 2,
cc20171473bb (svn r6159) -Fix: FindClosestTrainDepot hardly ever found a depot with NPF off due to absence of distance-normalization (Rojer)
Darkvater
parents: 4000
diff changeset
    12
	DIAG_FACTOR = 3
cc20171473bb (svn r6159) -Fix: FindClosestTrainDepot hardly ever found a depot with NPF off due to absence of distance-normalization (Rojer)
Darkvater
parents: 4000
diff changeset
    13
};
cc20171473bb (svn r6159) -Fix: FindClosestTrainDepot hardly ever found a depot with NPF off due to absence of distance-normalization (Rojer)
Darkvater
parents: 4000
diff changeset
    14
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents: 926
diff changeset
    15
//#define PF_BENCH // perform simple benchmarks on the train pathfinder (not
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents: 926
diff changeset
    16
//supported on all archs)
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents: 926
diff changeset
    17
6248
e4a2ed7e5613 (svn r9051) -Codechange: typedef [enum|struct] Y {} X; -> [enum|struct] X {};
rubidium
parents: 5587
diff changeset
    18
struct TrackPathFinder;
8611
9037a4227d67 (svn r12193) -Codechange: Rename a magic variable, give it a decent type, and remove a 'goto'.
frosch
parents: 8398
diff changeset
    19
typedef bool TPFEnumProc(TileIndex tile, void *data, Trackdir trackdir, uint length);
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    20
typedef void TPFAfterProc(TrackPathFinder *tpf);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    21
2125
edc17858f9f6 (svn r2635) Fix: [ntp/misc] Improve the old pathfinder. Changed it to A* instead of Dijkstra.
ludde
parents: 1977
diff changeset
    22
typedef bool NTPEnumProc(TileIndex tile, void *data, int track, uint length);
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    23
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    24
#define PATHFIND_GET_LINK_OFFS(tpf, link) ((byte*)(link) - (byte*)tpf->links)
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    25
#define PATHFIND_GET_LINK_PTR(tpf, link_offs) (TrackPathFinderLink*)((byte*)tpf->links + (link_offs))
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    26
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    27
/* y7 y6 y5 y4 y3 y2 y1 y0 x7 x6 x5 x4 x3 x2 x1 x0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    28
 * y7 y6 y5 y4 y3 y2 y1 y0 x4 x3 x2 x1 x0  0  0  0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    29
 *  0  0 y7 y6 y5 y4 y3 y2 y1 y0 x4 x3 x2 x1 x0  0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    30
 *  0  0  0  0 y5 y4 y3 y2 y1 y0 x4 x3 x2 x1 x0  0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    31
 */
926
a6d140a6a4de (svn r1414) Move TileIndex, TILE_MASK and GET_TILE_[XY] to map.h and turn the latter into inline functions names Tile[XY]
tron
parents: 201
diff changeset
    32
#define PATHFIND_HASH_TILE(tile) (TileX(tile) & 0x1F) + ((TileY(tile) & 0x1F) << 5)
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    33
6248
e4a2ed7e5613 (svn r9051) -Codechange: typedef [enum|struct] Y {} X; -> [enum|struct] X {};
rubidium
parents: 5587
diff changeset
    34
struct TrackPathFinderLink {
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    35
	TileIndex tile;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    36
	uint16 flags;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    37
	uint16 next;
6248
e4a2ed7e5613 (svn r9051) -Codechange: typedef [enum|struct] Y {} X; -> [enum|struct] X {};
rubidium
parents: 5587
diff changeset
    38
};
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    39
6248
e4a2ed7e5613 (svn r9051) -Codechange: typedef [enum|struct] Y {} X; -> [enum|struct] X {};
rubidium
parents: 5587
diff changeset
    40
struct RememberData {
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    41
	uint16 cur_length;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    42
	byte depth;
8611
9037a4227d67 (svn r12193) -Codechange: Rename a magic variable, give it a decent type, and remove a 'goto'.
frosch
parents: 8398
diff changeset
    43
	Track last_choosen_track;
6248
e4a2ed7e5613 (svn r9051) -Codechange: typedef [enum|struct] Y {} X; -> [enum|struct] X {};
rubidium
parents: 5587
diff changeset
    44
};
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    45
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    46
struct TrackPathFinder {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    47
	int num_links_left;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    48
	TrackPathFinderLink *new_link;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    49
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    50
	TPFEnumProc *enum_proc;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    51
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    52
	void *userdata;
201
c40d343115f8 (svn r202) -Codechange: I missed some files with trailing spaces.. this should be
truelight
parents: 159
diff changeset
    53
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    54
	RememberData rd;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    55
5587
167d9a91ef02 (svn r8038) -Merge: the cpp branch. Effort of KUDr, Celestar, glx, Smoovius, stillunknown and pv2b.
rubidium
parents: 5475
diff changeset
    56
	TrackdirByte the_dir;
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    57
8263
2b3e64c5e680 (svn r11827) -Codechange: do not include enum_type.hpp unnecessary.
rubidium
parents: 8236
diff changeset
    58
	TransportType tracktype;
6683
b88ae30866ce (svn r9914) -Codechange: prepare GTTS and the pathfinders to handle multiple road types on a single tile.
rubidium
parents: 6352
diff changeset
    59
	uint sub_type;
b88ae30866ce (svn r9914) -Codechange: prepare GTTS and the pathfinders to handle multiple road types on a single tile.
rubidium
parents: 6352
diff changeset
    60
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    61
	bool disable_tile_hash;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    62
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    63
	uint16 hash_head[0x400];
6352
938ab8f48e5d (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas
parents: 6248
diff changeset
    64
	TileIndex hash_tile[0x400];       ///< stores the link index when multi link.
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    65
6352
938ab8f48e5d (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas
parents: 6248
diff changeset
    66
	TrackPathFinderLink links[0x400]; ///< hopefully, this is enough.
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    67
};
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    68
8800
c30102fee110 (svn r12540) -Codechange: Enumify some values in original pathfinder and remove an unused variable.
frosch
parents: 8611
diff changeset
    69
/** Some flags to modify the behaviour of original pathfinder */
c30102fee110 (svn r12540) -Codechange: Enumify some values in original pathfinder and remove an unused variable.
frosch
parents: 8611
diff changeset
    70
enum PathfindFlags {
c30102fee110 (svn r12540) -Codechange: Enumify some values in original pathfinder and remove an unused variable.
frosch
parents: 8611
diff changeset
    71
	PATHFIND_FLAGS_NONE              = 0,
c30102fee110 (svn r12540) -Codechange: Enumify some values in original pathfinder and remove an unused variable.
frosch
parents: 8611
diff changeset
    72
	PATHFIND_FLAGS_SHIP_MODE         = 0x0800, ///< pathfinder with some optimizations for ships, but does not work for other types.
c30102fee110 (svn r12540) -Codechange: Enumify some values in original pathfinder and remove an unused variable.
frosch
parents: 8611
diff changeset
    73
	PATHFIND_FLAGS_DISABLE_TILE_HASH = 0x1000, ///< do not check for searching in circles
c30102fee110 (svn r12540) -Codechange: Enumify some values in original pathfinder and remove an unused variable.
frosch
parents: 8611
diff changeset
    74
};
c30102fee110 (svn r12540) -Codechange: Enumify some values in original pathfinder and remove an unused variable.
frosch
parents: 8611
diff changeset
    75
DECLARE_ENUM_AS_BIT_SET(PathfindFlags)
c30102fee110 (svn r12540) -Codechange: Enumify some values in original pathfinder and remove an unused variable.
frosch
parents: 8611
diff changeset
    76
c30102fee110 (svn r12540) -Codechange: Enumify some values in original pathfinder and remove an unused variable.
frosch
parents: 8611
diff changeset
    77
void FollowTrack(TileIndex tile, PathfindFlags flags, TransportType tt, uint sub_type, DiagDirection direction, TPFEnumProc* enum_proc, TPFAfterProc* after_proc, void* data);
8236
8a5dd0b42e47 (svn r11800) -Codechange: move some functions to a more logical location + some type safety.
rubidium
parents: 8142
diff changeset
    78
void NewTrainPathfind(TileIndex tile, TileIndex dest, RailTypes railtypes, DiagDirection direction, NTPEnumProc* enum_proc, void* data);
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    79
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    80
#endif /* PATHFIND_H */