1

/* $Id$ */

     2

     3

/** @file pathfind.h */

     4

     5

#ifndef PATHFIND_H

     6

#define PATHFIND_H

     7

     8

#include "direction_type.h"

     9

    10

enum {

    11

	STR_FACTOR  = 2,

    12

	DIAG_FACTOR = 3

    13

};

    14

    15

//#define PF_BENCH // perform simple benchmarks on the train pathfinder (not

    16

//supported on all archs)

    17

    18

struct TrackPathFinder;

    19

typedef bool TPFEnumProc(TileIndex tile, void *data, Trackdir trackdir, uint length);

    20

typedef void TPFAfterProc(TrackPathFinder *tpf);

    21

    22

typedef bool NTPEnumProc(TileIndex tile, void *data, int track, uint length);

    23

    24

#define PATHFIND_GET_LINK_OFFS(tpf, link) ((byte*)(link) - (byte*)tpf->links)

    25

#define PATHFIND_GET_LINK_PTR(tpf, link_offs) (TrackPathFinderLink*)((byte*)tpf->links + (link_offs))

    26

    27

/* y7 y6 y5 y4 y3 y2 y1 y0 x7 x6 x5 x4 x3 x2 x1 x0

    28

 * y7 y6 y5 y4 y3 y2 y1 y0 x4 x3 x2 x1 x0  0  0  0

    29

 *  0  0 y7 y6 y5 y4 y3 y2 y1 y0 x4 x3 x2 x1 x0  0

    30

 *  0  0  0  0 y5 y4 y3 y2 y1 y0 x4 x3 x2 x1 x0  0

    31

 */

    32

#define PATHFIND_HASH_TILE(tile) (TileX(tile) & 0x1F) + ((TileY(tile) & 0x1F) << 5)

    33

    34

struct TrackPathFinderLink {

    35

	TileIndex tile;

    36

	uint16 flags;

    37

	uint16 next;

    38

};

    39

    40

struct RememberData {

    41

	uint16 cur_length;

    42

	byte depth;

    43

	Track last_choosen_track;

    44

};

    45

    46

struct TrackPathFinder {

    47

	int num_links_left;

    48

	TrackPathFinderLink *new_link;

    49

    50

	TPFEnumProc *enum_proc;

    51

    52

	void *userdata;

    53

    54

	RememberData rd;

    55

    56

	TrackdirByte the_dir;

    57

    58

	TransportType tracktype;

    59

	uint sub_type;

    60

    61

	bool disable_tile_hash;

    62

    63

	uint16 hash_head[0x400];

    64

	TileIndex hash_tile[0x400];       ///< stores the link index when multi link.

    65

    66

	TrackPathFinderLink links[0x400]; ///< hopefully, this is enough.

    67

};

    68

    69

/** Some flags to modify the behaviour of original pathfinder */

    70

enum PathfindFlags {

    71

	PATHFIND_FLAGS_NONE              = 0,

    72

	PATHFIND_FLAGS_SHIP_MODE         = 0x0800, ///< pathfinder with some optimizations for ships, but does not work for other types.

    73

	PATHFIND_FLAGS_DISABLE_TILE_HASH = 0x1000, ///< do not check for searching in circles

    74

};

    75

DECLARE_ENUM_AS_BIT_SET(PathfindFlags)

    76

    77

void FollowTrack(TileIndex tile, PathfindFlags flags, TransportType tt, uint sub_type, DiagDirection direction, TPFEnumProc* enum_proc, TPFAfterProc* after_proc, void* data);

    78

void NewTrainPathfind(TileIndex tile, TileIndex dest, RailTypes railtypes, DiagDirection direction, NTPEnumProc* enum_proc, void* data);

    79

    80

#endif /* PATHFIND_H */