pathfind.c
author Darkvater
Sat, 02 Apr 2005 23:05:09 +0000
changeset 1632 10c391e108b7
parent 1209 2e00193652b2
child 1891 862800791170
permissions -rw-r--r--
(svn r2136) - Fix: [ 1174313 ] terrain hotkeys nonfunctional in scenario editor (D,Q,W,E,R,T,Y,U fltr)
- Fix: 'L' no longer opens ingame terraform bar in scenario editor bar, but the land generator one
- Feature: [ 1095110 ] Create Lake and draggable Create Desert tools (initial implementation GoneWacko), also added sticky buttons to land generator and town generator
- CodeChange: moved around some of the draggable tools, demystifying them
- CodeChange: change CmdBuildCanal to allow for XANDY dragging not only X or Y (only scenario editor)
- CodeChange: add some more enums to sprites.
- TODO: merge most of the ingame and scenario editor land terraform code. This can only be done after OnClickButton function is changed so it also includes the backreference to the widget being clicked, postponed to after 0.4.0
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
     1
#include "stdafx.h"
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
     2
#include "ttd.h"
679
04ca2cd69420 (svn r1117) Move map arrays and some related macros into their own files map.c and map.h
tron
parents: 536
diff changeset
     3
#include "map.h"
1209
2e00193652b2 (svn r1713) Split off several functions which query/set information about a single tile from map.h and put them into a seperate file tile.h
tron
parents: 1035
diff changeset
     4
#include "tile.h"
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
     5
#include "pathfind.h"
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
     6
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
     7
// remember which tiles we have already visited so we don't visit them again.
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
     8
static bool TPFSetTileBit(TrackPathFinder *tpf, uint tile, int dir)
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
     9
{
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    10
	uint hash, val, offs;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    11
	TrackPathFinderLink *link, *new_link;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    12
	uint bits = 1 << dir;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    13
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    14
	if (tpf->disable_tile_hash)
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    15
		return true;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    16
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    17
	hash = PATHFIND_HASH_TILE(tile);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    18
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    19
	val = tpf->hash_head[hash];
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    20
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    21
	if (val == 0) {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    22
		/* unused hash entry, set the appropriate bit in it and return true
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    23
		 * to indicate that a bit was set. */
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    24
		tpf->hash_head[hash] = bits;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    25
		tpf->hash_tile[hash] = (TileIndex)tile;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    26
		return true;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    27
	} else if (!(val & 0x8000)) {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    28
		/* single tile */
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    29
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    30
		if ( (TileIndex)tile == tpf->hash_tile[hash] ) {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    31
			/* found another bit for the same tile,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    32
			 * check if this bit is already set, if so, return false */
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    33
			if (val & bits)
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    34
				return false;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    35
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    36
			/* otherwise set the bit and return true to indicate that the bit
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    37
			 * was set */
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    38
			tpf->hash_head[hash] = val | bits;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    39
			return true;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    40
		} else {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    41
			/* two tiles with the same hash, need to make a link */
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
    42
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    43
			/* allocate a link. if out of links, handle this by returning
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    44
			 * that a tile was already visisted. */
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    45
			if (tpf->num_links_left == 0)
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    46
				return false;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    47
			tpf->num_links_left--;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    48
			link = tpf->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
			/* move the data that was previously in the hash_??? variables
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    51
			 * to the link struct, and let the hash variables point to the link */
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    52
			link->tile = tpf->hash_tile[hash];
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    53
			tpf->hash_tile[hash] = PATHFIND_GET_LINK_OFFS(tpf, link);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    54
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    55
			link->flags = tpf->hash_head[hash];
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
    56
			tpf->hash_head[hash] = 0xFFFF; /* multi link */
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    57
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    58
			link->next = 0xFFFF;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    59
		}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    60
	} else {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    61
		/* a linked list of many tiles,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    62
		 * find the one corresponding to the tile, if it exists.
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    63
		 * otherwise make a new link */
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
    64
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    65
		offs = tpf->hash_tile[hash];
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    66
		do {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    67
			link = PATHFIND_GET_LINK_PTR(tpf, offs);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    68
			if ( (TileIndex)tile == link->tile) {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    69
				/* found the tile in the link list,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    70
				 * check if the bit was alrady set, if so return false to indicate that the
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    71
				 * bit was already set */
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    72
				if (link->flags & bits)
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    73
					return false;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    74
				link->flags |= bits;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    75
				return true;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    76
			}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    77
		} while ((offs=link->next) != 0xFFFF);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    78
	}
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
    79
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    80
	/* get here if we need to add a new link to link,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    81
	 * first, allocate a new link, in the same way as before */
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    82
	if (tpf->num_links_left == 0)
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    83
			return false;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    84
	tpf->num_links_left--;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    85
	new_link = tpf->new_link++;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    86
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    87
	/* then fill the link with the new info, and establish a ptr from the old
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    88
	 * link to the new one */
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    89
	new_link->tile = (TileIndex)tile;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    90
	new_link->flags = bits;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    91
	new_link->next = 0xFFFF;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    92
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    93
	link->next = PATHFIND_GET_LINK_OFFS(tpf, new_link);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    94
	return true;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    95
}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    96
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    97
static const byte _bits_mask[4] = {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    98
	0x19,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
    99
	0x16,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   100
	0x25,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   101
	0x2A,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   102
};
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   103
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   104
static const byte _tpf_new_direction[14] = {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   105
	0,1,0,1,2,1, 0,0,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   106
	2,3,3,2,3,0,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   107
};
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   108
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   109
static const byte _tpf_prev_direction[14] = {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   110
	0,1,1,0,1,2, 0,0,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   111
	2,3,2,3,0,3,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   112
};
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   113
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   114
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   115
static const byte _otherdir_mask[4] = {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   116
	0x10,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   117
	0,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   118
	0x5,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   119
	0x2A,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   120
};
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   121
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   122
#ifdef DEBUG_TILE_PUSH
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   123
extern void dbg_push_tile(uint tile, int track);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   124
extern void dbg_pop_tile();
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   125
#endif
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   126
410
0efd84450b01 (svn r607) -Patch: [ 985102 ] static cleanup
tron
parents: 318
diff changeset
   127
static void TPFMode2(TrackPathFinder *tpf, uint tile, int direction)
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   128
{
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   129
	uint bits;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   130
	int i;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   131
	RememberData rd;
753
faa88086b52e (svn r1209) -Fix: fix compiler warning (sorry)
truelight
parents: 752
diff changeset
   132
	int owner = -1;
747
4bf34cf669d0 (svn r1203) -Fix: the pathfinder no longer sees rail with an other owner as a
truelight
parents: 679
diff changeset
   133
752
4e4ec58ba45f (svn r1208) -Fix: the owner-check introduced in r1203 now also works correctly for
truelight
parents: 747
diff changeset
   134
	if (tpf->tracktype == TRANSPORT_RAIL) {
1035
812f837ee03f (svn r1536) Move GET_TILEHEIGHT, GET_TILETYPE and IS_TILETYPE to map.h, turn them into inline functions and add some asserts
tron
parents: 1034
diff changeset
   135
		if (IsTileType(tile, MP_RAILWAY) || IsTileType(tile, MP_STATION) || IsTileType(tile, MP_TUNNELBRIDGE)) {
913
f999e421226d (svn r1400) -Fix: signal stays red if a track is removed (Darkvater / Tron / TrueLight)
truelight
parents: 905
diff changeset
   136
			owner = _map_owner[tile];
f999e421226d (svn r1400) -Fix: signal stays red if a track is removed (Darkvater / Tron / TrueLight)
truelight
parents: 905
diff changeset
   137
			/* Check if we are on the middle of a bridge (has no owner) */
1035
812f837ee03f (svn r1536) Move GET_TILEHEIGHT, GET_TILETYPE and IS_TILETYPE to map.h, turn them into inline functions and add some asserts
tron
parents: 1034
diff changeset
   138
			if (IsTileType(tile, MP_TUNNELBRIDGE) && (_map5[tile] & 0xC0) == 0xC0)
913
f999e421226d (svn r1400) -Fix: signal stays red if a track is removed (Darkvater / Tron / TrueLight)
truelight
parents: 905
diff changeset
   139
				owner = -1;
f999e421226d (svn r1400) -Fix: signal stays red if a track is removed (Darkvater / Tron / TrueLight)
truelight
parents: 905
diff changeset
   140
		}
752
4e4ec58ba45f (svn r1208) -Fix: the owner-check introduced in r1203 now also works correctly for
truelight
parents: 747
diff changeset
   141
	}
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   142
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   143
	// This addition will sometimes overflow by a single tile.
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   144
	// The use of TILE_MASK here makes sure that we still point at a valid
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   145
	// tile, and then this tile will be in the sentinel row/col, so GetTileTrackStatus will fail.
900
27eb21ced433 (svn r1386) Move TileIndexDiff to map.h
tron
parents: 753
diff changeset
   146
	tile = TILE_MASK(tile + TileOffsByDir(direction));
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   147
747
4bf34cf669d0 (svn r1203) -Fix: the pathfinder no longer sees rail with an other owner as a
truelight
parents: 679
diff changeset
   148
	/* Check in case of rail if the owner is the same */
1034
e761d474e204 (svn r1535) -Fix: bah, I hate to be wrong.. oh, euh, wrong copy/paste from TPFMode 1
truelight
parents: 979
diff changeset
   149
	if (tpf->tracktype == TRANSPORT_RAIL) {
1035
812f837ee03f (svn r1536) Move GET_TILEHEIGHT, GET_TILETYPE and IS_TILETYPE to map.h, turn them into inline functions and add some asserts
tron
parents: 1034
diff changeset
   150
		if (IsTileType(tile, MP_RAILWAY) || IsTileType(tile, MP_STATION) || IsTileType(tile, MP_TUNNELBRIDGE))
913
f999e421226d (svn r1400) -Fix: signal stays red if a track is removed (Darkvater / Tron / TrueLight)
truelight
parents: 905
diff changeset
   151
			/* Check if we are on the middle of a bridge (has no owner) */
1035
812f837ee03f (svn r1536) Move GET_TILEHEIGHT, GET_TILETYPE and IS_TILETYPE to map.h, turn them into inline functions and add some asserts
tron
parents: 1034
diff changeset
   152
			if (!IsTileType(tile, MP_TUNNELBRIDGE) || (_map5[tile] & 0xC0) != 0xC0)
913
f999e421226d (svn r1400) -Fix: signal stays red if a track is removed (Darkvater / Tron / TrueLight)
truelight
parents: 905
diff changeset
   153
				if (owner != -1 && _map_owner[tile] != owner)
f999e421226d (svn r1400) -Fix: signal stays red if a track is removed (Darkvater / Tron / TrueLight)
truelight
parents: 905
diff changeset
   154
					return;
752
4e4ec58ba45f (svn r1208) -Fix: the owner-check introduced in r1203 now also works correctly for
truelight
parents: 747
diff changeset
   155
	}
747
4bf34cf669d0 (svn r1203) -Fix: the pathfinder no longer sees rail with an other owner as a
truelight
parents: 679
diff changeset
   156
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   157
	if (++tpf->rd.cur_length > 50)
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   158
		return;
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   159
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   160
	bits = GetTileTrackStatus(tile, tpf->tracktype);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   161
	bits = (byte)((bits | (bits >> 8)) & _bits_mask[direction]);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   162
	if (bits == 0)
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   163
		return;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   164
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: 913
diff changeset
   165
	assert(TileX(tile) != MapMaxX() && TileY(tile) != MapMaxY());
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   166
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   167
	if ( (bits & (bits - 1)) == 0 ) {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   168
		/* only one direction */
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   169
		i = 0;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   170
		while (!(bits&1))
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   171
			i++, bits>>=1;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   172
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   173
		rd = tpf->rd;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   174
		goto continue_here;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   175
	}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   176
	/* several directions */
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   177
	i=0;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   178
	do {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   179
		if (!(bits & 1)) continue;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   180
		rd = tpf->rd;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   181
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   182
		// Change direction 4 times only
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   183
		if ((byte)i != tpf->rd.pft_var6) {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   184
			if(++tpf->rd.depth > 4) {
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   185
				tpf->rd = rd;
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   186
				return;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   187
			}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   188
			tpf->rd.pft_var6 = (byte)i;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   189
		}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   190
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   191
continue_here:;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   192
		tpf->the_dir = HASBIT(_otherdir_mask[direction],i) ? (i+8) : i;
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   193
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   194
#ifdef DEBUG_TILE_PUSH
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   195
		dbg_push_tile(tile, tpf->the_dir);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   196
#endif
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   197
		if (!tpf->enum_proc(tile, tpf->userdata, tpf->the_dir, tpf->rd.cur_length, NULL)) {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   198
			TPFMode2(tpf, tile, _tpf_new_direction[tpf->the_dir]);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   199
		}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   200
#ifdef DEBUG_TILE_PUSH
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   201
		dbg_pop_tile();
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   202
#endif
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   203
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   204
		tpf->rd = rd;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   205
	} while (++i, bits>>=1);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   206
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   207
}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   208
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   209
static const int8 _get_tunlen_inc[5] = { -16, 0, 16, 0, -16 };
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   210
22
fe6f35cc987b (svn r23) -Some omments on the code (blathijs)
darkvater
parents: 0
diff changeset
   211
/* Returns the end tile and the length of a tunnel. The length does not
fe6f35cc987b (svn r23) -Some omments on the code (blathijs)
darkvater
parents: 0
diff changeset
   212
 * include the starting tile (entry), it does include the end tile (exit).
fe6f35cc987b (svn r23) -Some omments on the code (blathijs)
darkvater
parents: 0
diff changeset
   213
 */
159
139cf78bfb28 (svn r160) -Codechange: made GetTileTrackStatus more readable (blathijs)
truelight
parents: 148
diff changeset
   214
FindLengthOfTunnelResult FindLengthOfTunnel(uint tile, int direction)
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   215
{
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   216
	FindLengthOfTunnelResult flotr;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   217
	int x,y;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   218
	byte z;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   219
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   220
	flotr.length = 0;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   221
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: 913
diff changeset
   222
	x = TileX(tile) * 16;
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: 913
diff changeset
   223
	y = TileY(tile) * 16;
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   224
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   225
	z = GetSlopeZ(x+8, y+8);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   226
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   227
	for(;;) {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   228
		flotr.length++;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   229
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   230
		x += _get_tunlen_inc[direction];
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   231
		y += _get_tunlen_inc[direction+1];
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   232
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   233
		tile = TILE_FROM_XY(x,y);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   234
1035
812f837ee03f (svn r1536) Move GET_TILEHEIGHT, GET_TILETYPE and IS_TILETYPE to map.h, turn them into inline functions and add some asserts
tron
parents: 1034
diff changeset
   235
		if (IsTileType(tile, MP_TUNNELBRIDGE) &&
241
e6e62a5e7f52 (svn r242) -Fix: Pathfinding bug for road vehicles introduced in r160 fixed (blathijs)
darkvater
parents: 193
diff changeset
   236
				(_map5[tile] & 0xF0) == 0 &&					// tunnel entrance/exit
e6e62a5e7f52 (svn r242) -Fix: Pathfinding bug for road vehicles introduced in r160 fixed (blathijs)
darkvater
parents: 193
diff changeset
   237
				//((_map5[tile]>>2)&3) == type &&		// rail/road-tunnel <-- This is not necesary to check, right?
e6e62a5e7f52 (svn r242) -Fix: Pathfinding bug for road vehicles introduced in r160 fixed (blathijs)
darkvater
parents: 193
diff changeset
   238
				((_map5[tile] & 3)^2) == direction &&	// entrance towards: 0 = NE, 1 = SE, 2 = SW, 3 = NW
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   239
				GetSlopeZ(x+8, y+8) == z)
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   240
					break;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   241
	}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   242
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   243
	flotr.tile = tile;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   244
	return flotr;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   245
}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   246
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   247
static const uint16 _tpfmode1_and[4] = { 0x1009, 0x16, 0x520, 0x2A00 };
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   248
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   249
static uint SkipToEndOfTunnel(TrackPathFinder *tpf, uint tile, int direction) {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   250
	FindLengthOfTunnelResult flotr;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   251
	TPFSetTileBit(tpf, tile, 14);
159
139cf78bfb28 (svn r160) -Codechange: made GetTileTrackStatus more readable (blathijs)
truelight
parents: 148
diff changeset
   252
	flotr = FindLengthOfTunnel(tile, direction);
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   253
	tpf->rd.cur_length += flotr.length;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   254
	TPFSetTileBit(tpf, flotr.tile, 14);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   255
	return flotr.tile;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   256
}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   257
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   258
const byte _ffb_64[128] = {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   259
0,0,1,0,2,0,1,0,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   260
3,0,1,0,2,0,1,0,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   261
4,0,1,0,2,0,1,0,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   262
3,0,1,0,2,0,1,0,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   263
5,0,1,0,2,0,1,0,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   264
3,0,1,0,2,0,1,0,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   265
4,0,1,0,2,0,1,0,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   266
3,0,1,0,2,0,1,0,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   267
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   268
0,0,0,2,0,4,4,6,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   269
0,8,8,10,8,12,12,14,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   270
0,16,16,18,16,20,20,22,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   271
16,24,24,26,24,28,28,30,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   272
0,32,32,34,32,36,36,38,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   273
32,40,40,42,40,44,44,46,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   274
32,48,48,50,48,52,52,54,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   275
48,56,56,58,56,60,60,62,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   276
};
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   277
410
0efd84450b01 (svn r607) -Patch: [ 985102 ] static cleanup
tron
parents: 318
diff changeset
   278
static void TPFMode1(TrackPathFinder *tpf, uint tile, int direction)
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   279
{
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   280
	uint bits;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   281
	int i;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   282
	RememberData rd;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   283
	uint tile_org = tile;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   284
1035
812f837ee03f (svn r1536) Move GET_TILEHEIGHT, GET_TILETYPE and IS_TILETYPE to map.h, turn them into inline functions and add some asserts
tron
parents: 1034
diff changeset
   285
	if (IsTileType(tile, MP_TUNNELBRIDGE) && (_map5[tile] & 0xF0) == 0) {
241
e6e62a5e7f52 (svn r242) -Fix: Pathfinding bug for road vehicles introduced in r160 fixed (blathijs)
darkvater
parents: 193
diff changeset
   286
		if ((_map5[tile] & 3) != direction || ((_map5[tile]>>2)&3) != tpf->tracktype)
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   287
			return;
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   288
		tile = SkipToEndOfTunnel(tpf, tile, direction);
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   289
	}
900
27eb21ced433 (svn r1386) Move TileIndexDiff to map.h
tron
parents: 753
diff changeset
   290
	tile += TileOffsByDir(direction);
747
4bf34cf669d0 (svn r1203) -Fix: the pathfinder no longer sees rail with an other owner as a
truelight
parents: 679
diff changeset
   291
4bf34cf669d0 (svn r1203) -Fix: the pathfinder no longer sees rail with an other owner as a
truelight
parents: 679
diff changeset
   292
	/* Check in case of rail if the owner is the same */
752
4e4ec58ba45f (svn r1208) -Fix: the owner-check introduced in r1203 now also works correctly for
truelight
parents: 747
diff changeset
   293
	if (tpf->tracktype == TRANSPORT_RAIL) {
1035
812f837ee03f (svn r1536) Move GET_TILEHEIGHT, GET_TILETYPE and IS_TILETYPE to map.h, turn them into inline functions and add some asserts
tron
parents: 1034
diff changeset
   294
		if (IsTileType(tile_org, MP_RAILWAY) || IsTileType(tile_org, MP_STATION) || IsTileType(tile_org, MP_TUNNELBRIDGE))
812f837ee03f (svn r1536) Move GET_TILEHEIGHT, GET_TILETYPE and IS_TILETYPE to map.h, turn them into inline functions and add some asserts
tron
parents: 1034
diff changeset
   295
			if (IsTileType(tile, MP_RAILWAY) || IsTileType(tile, MP_STATION) || IsTileType(tile, MP_TUNNELBRIDGE))
913
f999e421226d (svn r1400) -Fix: signal stays red if a track is removed (Darkvater / Tron / TrueLight)
truelight
parents: 905
diff changeset
   296
				/* Check if we are on a bridge (middle parts don't have an owner */
1035
812f837ee03f (svn r1536) Move GET_TILEHEIGHT, GET_TILETYPE and IS_TILETYPE to map.h, turn them into inline functions and add some asserts
tron
parents: 1034
diff changeset
   297
				if (!IsTileType(tile, MP_TUNNELBRIDGE) || (_map5[tile] & 0xC0) != 0xC0)
812f837ee03f (svn r1536) Move GET_TILEHEIGHT, GET_TILETYPE and IS_TILETYPE to map.h, turn them into inline functions and add some asserts
tron
parents: 1034
diff changeset
   298
					if (!IsTileType(tile_org, MP_TUNNELBRIDGE) || (_map5[tile_org] & 0xC0) != 0xC0)
913
f999e421226d (svn r1400) -Fix: signal stays red if a track is removed (Darkvater / Tron / TrueLight)
truelight
parents: 905
diff changeset
   299
						if (_map_owner[tile_org] != _map_owner[tile])
f999e421226d (svn r1400) -Fix: signal stays red if a track is removed (Darkvater / Tron / TrueLight)
truelight
parents: 905
diff changeset
   300
							return;
752
4e4ec58ba45f (svn r1208) -Fix: the owner-check introduced in r1203 now also works correctly for
truelight
parents: 747
diff changeset
   301
	}
747
4bf34cf669d0 (svn r1203) -Fix: the pathfinder no longer sees rail with an other owner as a
truelight
parents: 679
diff changeset
   302
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   303
	tpf->rd.cur_length++;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   304
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   305
	bits = GetTileTrackStatus(tile, tpf->tracktype);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   306
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   307
	if ((byte)bits != tpf->var2) {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   308
		bits &= _tpfmode1_and[direction];
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   309
		bits = bits | (bits>>8);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   310
	}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   311
	bits &= 0xBF;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   312
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   313
	if (bits != 0) {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   314
		if (!tpf->disable_tile_hash || (tpf->rd.cur_length <= 64 && (KILL_FIRST_BIT(bits) == 0 || ++tpf->rd.depth <= 7))) {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   315
			do {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   316
				i = FIND_FIRST_BIT(bits);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   317
				bits = KILL_FIRST_BIT(bits);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   318
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   319
				tpf->the_dir = (_otherdir_mask[direction] & (byte)(1 << i)) ? (i+8) : i;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   320
				rd = tpf->rd;
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   321
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   322
#ifdef DEBUG_TILE_PUSH
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   323
		dbg_push_tile(tile, tpf->the_dir);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   324
#endif
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   325
				if (TPFSetTileBit(tpf, tile, tpf->the_dir) &&
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   326
						!tpf->enum_proc(tile, tpf->userdata, tpf->the_dir, tpf->rd.cur_length, &tpf->rd.pft_var6) ) {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   327
					TPFMode1(tpf, tile, _tpf_new_direction[tpf->the_dir]);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   328
				}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   329
#ifdef DEBUG_TILE_PUSH
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   330
		dbg_pop_tile();
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   331
#endif
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   332
				tpf->rd = rd;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   333
			} while (bits != 0);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   334
		}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   335
	}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   336
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   337
	/* the next is only used when signals are checked.
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   338
	 * seems to go in 2 directions simultaneously */
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   339
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   340
	/* if i can get rid of this, tail end recursion can be used to minimize
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   341
	 * stack space dramatically. */
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   342
	if (tpf->hasbit_13)
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   343
		return;
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   344
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   345
	tile = tile_org;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   346
	direction ^= 2;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   347
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   348
	bits = GetTileTrackStatus(tile, tpf->tracktype);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   349
	bits |= (bits >> 8);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   350
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   351
	if ( (byte)bits != tpf->var2) {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   352
		bits &= _bits_mask[direction];
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   353
	}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   354
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   355
	bits &= 0xBF;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   356
	if (bits == 0)
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   357
		return;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   358
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   359
	do {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   360
		i = FIND_FIRST_BIT(bits);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   361
		bits = KILL_FIRST_BIT(bits);
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   362
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   363
		tpf->the_dir = (_otherdir_mask[direction] & (byte)(1 << i)) ? (i+8) : i;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   364
		rd = tpf->rd;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   365
		if (TPFSetTileBit(tpf, tile, tpf->the_dir) &&
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   366
				!tpf->enum_proc(tile, tpf->userdata, tpf->the_dir, tpf->rd.cur_length, &tpf->rd.pft_var6) ) {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   367
			TPFMode1(tpf, tile, _tpf_new_direction[tpf->the_dir]);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   368
		}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   369
		tpf->rd = rd;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   370
	} while (bits != 0);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   371
}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   372
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   373
void FollowTrack(uint tile, uint16 flags, byte direction, TPFEnumProc *enum_proc, TPFAfterProc *after_proc, void *data)
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   374
{
318
648afd1ab9a7 (svn r328) -Fix: remove some unlogical alloca()s (Tron)
darkvater
parents: 241
diff changeset
   375
	TrackPathFinder tpf;
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   376
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   377
	assert(direction < 4);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   378
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   379
	/* initialize path finder variables */
318
648afd1ab9a7 (svn r328) -Fix: remove some unlogical alloca()s (Tron)
darkvater
parents: 241
diff changeset
   380
	tpf.userdata = data;
648afd1ab9a7 (svn r328) -Fix: remove some unlogical alloca()s (Tron)
darkvater
parents: 241
diff changeset
   381
	tpf.enum_proc = enum_proc;
648afd1ab9a7 (svn r328) -Fix: remove some unlogical alloca()s (Tron)
darkvater
parents: 241
diff changeset
   382
	tpf.new_link = tpf.links;
648afd1ab9a7 (svn r328) -Fix: remove some unlogical alloca()s (Tron)
darkvater
parents: 241
diff changeset
   383
	tpf.num_links_left = lengthof(tpf.links);
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   384
318
648afd1ab9a7 (svn r328) -Fix: remove some unlogical alloca()s (Tron)
darkvater
parents: 241
diff changeset
   385
	tpf.rd.cur_length = 0;
648afd1ab9a7 (svn r328) -Fix: remove some unlogical alloca()s (Tron)
darkvater
parents: 241
diff changeset
   386
	tpf.rd.depth = 0;
648afd1ab9a7 (svn r328) -Fix: remove some unlogical alloca()s (Tron)
darkvater
parents: 241
diff changeset
   387
	tpf.rd.pft_var6 = 0;
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   388
318
648afd1ab9a7 (svn r328) -Fix: remove some unlogical alloca()s (Tron)
darkvater
parents: 241
diff changeset
   389
	tpf.var2 = HASBIT(flags, 15) ? 0x43 : 0xFF; /* 0x8000 */
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   390
318
648afd1ab9a7 (svn r328) -Fix: remove some unlogical alloca()s (Tron)
darkvater
parents: 241
diff changeset
   391
	tpf.disable_tile_hash = HASBIT(flags, 12) != 0;     /* 0x1000 */
648afd1ab9a7 (svn r328) -Fix: remove some unlogical alloca()s (Tron)
darkvater
parents: 241
diff changeset
   392
	tpf.hasbit_13 = HASBIT(flags, 13) != 0;		 /* 0x2000 */
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   393
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   394
318
648afd1ab9a7 (svn r328) -Fix: remove some unlogical alloca()s (Tron)
darkvater
parents: 241
diff changeset
   395
	tpf.tracktype = (byte)flags;
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   396
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   397
	if (HASBIT(flags, 11)) {
318
648afd1ab9a7 (svn r328) -Fix: remove some unlogical alloca()s (Tron)
darkvater
parents: 241
diff changeset
   398
		tpf.rd.pft_var6 = 0xFF;
648afd1ab9a7 (svn r328) -Fix: remove some unlogical alloca()s (Tron)
darkvater
parents: 241
diff changeset
   399
		tpf.enum_proc(tile, data, 0, 0, 0);
648afd1ab9a7 (svn r328) -Fix: remove some unlogical alloca()s (Tron)
darkvater
parents: 241
diff changeset
   400
		TPFMode2(&tpf, tile, direction);
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   401
	} else {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   402
		/* clear the hash_heads */
318
648afd1ab9a7 (svn r328) -Fix: remove some unlogical alloca()s (Tron)
darkvater
parents: 241
diff changeset
   403
		memset(tpf.hash_head, 0, sizeof(tpf.hash_head));
648afd1ab9a7 (svn r328) -Fix: remove some unlogical alloca()s (Tron)
darkvater
parents: 241
diff changeset
   404
		TPFMode1(&tpf, tile, direction);
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   405
	}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   406
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   407
	if (after_proc != NULL)
318
648afd1ab9a7 (svn r328) -Fix: remove some unlogical alloca()s (Tron)
darkvater
parents: 241
diff changeset
   408
		after_proc(&tpf);
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   409
}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   410
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   411
typedef struct {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   412
	TileIndex tile;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   413
	uint16 cur_length;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   414
	byte track;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   415
	byte depth;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   416
	byte state;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   417
	byte first_track;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   418
} StackedItem;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   419
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   420
static const byte _new_dir[6][4] = {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   421
{0,0xff,2,0xff,},
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   422
{0xff,1,0xff,3,},
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   423
{0xff,0,3,0xff,},
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   424
{1,0xff,0xff,2,},
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   425
{3,2,0xff,0xff,},
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   426
{0xff,0xff,1,0,},
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   427
};
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   428
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   429
static const byte _new_track[6][4] = {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   430
{0,0xff,8,0xff,},
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   431
{0xff,1,0xff,9,},
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   432
{0xff,2,10,0xff,},
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   433
{3,0xff,0xff,11,},
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   434
{12,4,0xff,0xff,},
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   435
{0xff,0xff,5,13,},
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   436
};
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   437
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   438
typedef struct HashLink {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   439
	TileIndex tile;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   440
	uint16 typelength;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   441
	uint16 next;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   442
} HashLink;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   443
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   444
typedef struct {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   445
	TPFEnumProc *enum_proc;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   446
	void *userdata;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   447
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   448
	byte tracktype;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   449
	uint maxlength;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   450
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   451
	HashLink *new_link;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   452
	uint num_links_left;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   453
979
11ea18598e16 (svn r1475) Fix some more signed/unsigned comparison warnings
tron
parents: 926
diff changeset
   454
	uint nstack;
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   455
	StackedItem stack[256]; // priority queue of stacked items
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   456
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   457
	uint16 hash_head[0x400]; // hash heads. 0 means unused. 0xFFC0 = length, 0x3F = type
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   458
	TileIndex hash_tile[0x400]; // tiles. or links.
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   459
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   460
	HashLink links[0x400]; // hash links
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   461
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   462
} NewTrackPathFinder;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   463
#define NTP_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
   464
#define NTP_GET_LINK_PTR(tpf, link_offs) (HashLink*)((byte*)tpf->links + (link_offs))
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   465
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   466
#define ARR(i) tpf->stack[(i)-1]
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   467
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   468
// called after a new element was added in the queue at the last index.
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   469
// move it down to the proper position
536
03d80fecb999 (svn r907) Sprinkle holy ANSI water:
tron
parents: 500
diff changeset
   470
static inline void HeapifyUp(NewTrackPathFinder *tpf)
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   471
{
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   472
	StackedItem si;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   473
	int i = ++tpf->nstack;
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   474
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   475
	while (i != 1 && ARR(i).cur_length < ARR(i>>1).cur_length) {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   476
		// the child element is larger than the parent item.
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   477
		// swap the child item and the parent item.
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   478
		si = ARR(i); ARR(i) = ARR(i>>1); ARR(i>>1) = si;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   479
		i>>=1;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   480
	}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   481
}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   482
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   483
// called after the element 0 was eaten. fill it with a new element
536
03d80fecb999 (svn r907) Sprinkle holy ANSI water:
tron
parents: 500
diff changeset
   484
static inline void HeapifyDown(NewTrackPathFinder *tpf)
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   485
{
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   486
	StackedItem si;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   487
	int i = 1, j;
979
11ea18598e16 (svn r1475) Fix some more signed/unsigned comparison warnings
tron
parents: 926
diff changeset
   488
	int n;
11ea18598e16 (svn r1475) Fix some more signed/unsigned comparison warnings
tron
parents: 926
diff changeset
   489
11ea18598e16 (svn r1475) Fix some more signed/unsigned comparison warnings
tron
parents: 926
diff changeset
   490
	assert(tpf->nstack > 0);
11ea18598e16 (svn r1475) Fix some more signed/unsigned comparison warnings
tron
parents: 926
diff changeset
   491
	n = --tpf->nstack;
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   492
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   493
	if (n == 0) return; // heap is empty so nothing to do?
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   494
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   495
	// copy the last item to index 0. we use it as base for heapify.
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   496
	ARR(1) = ARR(n+1);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   497
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   498
	while ((j=i*2) <= n) {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   499
		// figure out which is smaller of the children.
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   500
		if (j != n && ARR(j).cur_length > ARR(j+1).cur_length)
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   501
			j++; // right item is smaller
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   502
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   503
		assert(i <= n && j <= n);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   504
		if (ARR(i).cur_length <= ARR(j).cur_length)
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   505
			break; // base elem smaller than smallest, done!
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   506
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   507
		// swap parent with the child
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   508
		si = ARR(i); ARR(i) = ARR(j); ARR(j) = si;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   509
		i = j;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   510
	}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   511
}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   512
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   513
// mark a tile as visited and store the length of the path.
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   514
// if we already had a better path to this tile, return false.
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   515
// otherwise return true.
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   516
static bool NtpVisit(NewTrackPathFinder *tpf, uint tile, uint dir, uint length)
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   517
{
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   518
	uint hash,head;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   519
	HashLink *link, *new_link;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   520
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   521
	assert(length < 1024);
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   522
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   523
	hash = PATHFIND_HASH_TILE(tile);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   524
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   525
	// never visited before?
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   526
	if ((head=tpf->hash_head[hash]) == 0) {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   527
		tpf->hash_tile[hash] = tile;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   528
		tpf->hash_head[hash] = dir | (length << 2);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   529
		return true;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   530
	}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   531
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   532
	if (head != 0xffff) {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   533
		if ( (TileIndex)tile == tpf->hash_tile[hash] && (head & 0x3) == dir ) {
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   534
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   535
			// longer length
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   536
			if (length >= (head >> 2)) return false;
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   537
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   538
			tpf->hash_head[hash] = dir | (length << 2);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   539
			return true;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   540
		}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   541
		// two tiles with the same hash, need to make a link
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   542
		// allocate a link. if out of links, handle this by returning
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   543
		// that a tile was already visisted.
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   544
		if (tpf->num_links_left == 0)
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   545
			return false;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   546
		tpf->num_links_left--;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   547
		link = tpf->new_link++;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   548
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   549
		/* move the data that was previously in the hash_??? variables
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   550
		 * to the link struct, and let the hash variables point to the link */
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   551
		link->tile = tpf->hash_tile[hash];
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   552
		tpf->hash_tile[hash] = NTP_GET_LINK_OFFS(tpf, link);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   553
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   554
		link->typelength = tpf->hash_head[hash];
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   555
		tpf->hash_head[hash] = 0xFFFF; /* multi link */
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   556
		link->next = 0xFFFF;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   557
	} else {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   558
		// a linked list of many tiles,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   559
		// find the one corresponding to the tile, if it exists.
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   560
		// otherwise make a new link
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   561
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   562
		uint offs = tpf->hash_tile[hash];
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   563
		do {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   564
			link = NTP_GET_LINK_PTR(tpf, offs);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   565
			if ( (TileIndex)tile == link->tile && (uint)(link->typelength & 0x3) == dir) {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   566
				if (length >= (uint)(link->typelength >> 2)) return false;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   567
				link->typelength = dir | (length << 2);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   568
				return true;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   569
			}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   570
		} while ((offs=link->next) != 0xFFFF);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   571
	}
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   572
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   573
	/* get here if we need to add a new link to link,
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   574
	 * first, allocate a new link, in the same way as before */
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   575
	if (tpf->num_links_left == 0)
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   576
			return false;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   577
	tpf->num_links_left--;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   578
	new_link = tpf->new_link++;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   579
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   580
	/* then fill the link with the new info, and establish a ptr from the old
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   581
	 * link to the new one */
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   582
	new_link->tile = (TileIndex)tile;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   583
	new_link->typelength = dir | (length << 2);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   584
	new_link->next = 0xFFFF;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   585
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   586
	link->next = NTP_GET_LINK_OFFS(tpf, new_link);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   587
	return true;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   588
}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   589
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   590
static bool NtpCheck(NewTrackPathFinder *tpf, uint tile, uint dir, uint length)
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   591
{
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   592
	uint hash,head,offs;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   593
	HashLink *link;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   594
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   595
	hash = PATHFIND_HASH_TILE(tile);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   596
	head=tpf->hash_head[hash];
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   597
	assert(head);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   598
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   599
	if (head != 0xffff) {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   600
		assert( tpf->hash_tile[hash] == tile && (head & 3) == dir);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   601
		assert( (head >> 2) <= length);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   602
		return length == (head >> 2);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   603
	}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   604
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   605
	// else it's a linked list of many tiles
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   606
	offs = tpf->hash_tile[hash];
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   607
	for(;;) {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   608
		link = NTP_GET_LINK_PTR(tpf, offs);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   609
		if ( (TileIndex)tile == link->tile && (uint)(link->typelength & 0x3) == dir) {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   610
			assert( (uint)(link->typelength >> 2) <= length);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   611
			return length == (uint)(link->typelength >> 2);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   612
		}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   613
		offs = link->next;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   614
		assert(offs != 0xffff);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   615
	}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   616
}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   617
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   618
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   619
// new more optimized pathfinder for trains...
410
0efd84450b01 (svn r607) -Patch: [ 985102 ] static cleanup
tron
parents: 318
diff changeset
   620
static void NTPEnum(NewTrackPathFinder *tpf, uint tile, uint direction)
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   621
{
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   622
	uint bits, tile_org;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   623
	int i;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   624
	StackedItem si;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   625
	FindLengthOfTunnelResult flotr;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   626
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   627
	si.cur_length = 0;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   628
	si.depth = 0;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   629
	si.state = 0;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   630
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   631
restart:
1035
812f837ee03f (svn r1536) Move GET_TILEHEIGHT, GET_TILETYPE and IS_TILETYPE to map.h, turn them into inline functions and add some asserts
tron
parents: 1034
diff changeset
   632
	if (IsTileType(tile, MP_TUNNELBRIDGE) && (_map5[tile] & 0xF0) == 0) {
148
6a72b12f5588 (svn r149) -Fix: [997703] Junction after tunnel bug (blathijs)
truelight
parents: 22
diff changeset
   633
		/* This is a tunnel tile */
6a72b12f5588 (svn r149) -Fix: [997703] Junction after tunnel bug (blathijs)
truelight
parents: 22
diff changeset
   634
		if ( (uint)(_map5[tile] & 3) != (direction ^ 2)) { /* ^ 2 is reversing the direction */
6a72b12f5588 (svn r149) -Fix: [997703] Junction after tunnel bug (blathijs)
truelight
parents: 22
diff changeset
   635
			/* We are not just driving out of the tunnel */
6a72b12f5588 (svn r149) -Fix: [997703] Junction after tunnel bug (blathijs)
truelight
parents: 22
diff changeset
   636
			if ( (uint)(_map5[tile] & 3) != direction || ((_map5[tile]>>1)&6) != tpf->tracktype)
6a72b12f5588 (svn r149) -Fix: [997703] Junction after tunnel bug (blathijs)
truelight
parents: 22
diff changeset
   637
				/* We are not driving into the tunnel, or it
6a72b12f5588 (svn r149) -Fix: [997703] Junction after tunnel bug (blathijs)
truelight
parents: 22
diff changeset
   638
				 * is an invalid tunnel */
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   639
				goto popnext;
159
139cf78bfb28 (svn r160) -Codechange: made GetTileTrackStatus more readable (blathijs)
truelight
parents: 148
diff changeset
   640
			flotr = FindLengthOfTunnel(tile, direction);
148
6a72b12f5588 (svn r149) -Fix: [997703] Junction after tunnel bug (blathijs)
truelight
parents: 22
diff changeset
   641
			si.cur_length += flotr.length;
6a72b12f5588 (svn r149) -Fix: [997703] Junction after tunnel bug (blathijs)
truelight
parents: 22
diff changeset
   642
			tile = flotr.tile;
6a72b12f5588 (svn r149) -Fix: [997703] Junction after tunnel bug (blathijs)
truelight
parents: 22
diff changeset
   643
		}
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   644
	}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   645
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   646
	// remember the start tile so we know if we're in an inf loop.
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   647
	tile_org = tile;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   648
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   649
	for(;;) {
900
27eb21ced433 (svn r1386) Move TileIndexDiff to map.h
tron
parents: 753
diff changeset
   650
		tile += TileOffsByDir(direction);
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   651
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   652
		// too long search length? bail out.
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   653
		if (++si.cur_length >= tpf->maxlength)
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   654
			goto popnext;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   655
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   656
		// not a regular rail tile?
1035
812f837ee03f (svn r1536) Move GET_TILEHEIGHT, GET_TILETYPE and IS_TILETYPE to map.h, turn them into inline functions and add some asserts
tron
parents: 1034
diff changeset
   657
		if (!IsTileType(tile, MP_RAILWAY) || (bits = _map5[tile]) & 0xC0) {
159
139cf78bfb28 (svn r160) -Codechange: made GetTileTrackStatus more readable (blathijs)
truelight
parents: 148
diff changeset
   658
			bits = GetTileTrackStatus(tile, TRANSPORT_RAIL) & _tpfmode1_and[direction];
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   659
			bits = (bits | (bits >> 8)) & 0x3F;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   660
			break;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   661
		}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   662
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   663
		// regular rail tile, determine the tracks that are actually reachable.
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   664
		bits &= _bits_mask[direction];
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   665
		if (bits == 0) goto popnext; // no tracks there? stop searching.
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   666
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   667
		// complex tile?, let the generic handler handle that..
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   668
		if (KILL_FIRST_BIT(bits) != 0) break;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   669
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   670
		// don't bother calling the callback when we have regular tracks only.
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   671
		// it's usually not needed anyway. that will speed up things.
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   672
		direction = _new_dir[FIND_FIRST_BIT(bits)][direction];
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   673
		assert(direction != 0xFF);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   674
		if (tile == tile_org) goto popnext; // detect infinite loop..
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   675
	}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   676
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   677
	if (!bits) goto popnext;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   678
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   679
	// if only one reachable track, use tail recursion optimization.
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   680
	if (KILL_FIRST_BIT(bits) == 0) {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   681
		i = _new_track[FIND_FIRST_BIT(bits)][direction];
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   682
		// call the callback
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   683
		if (tpf->enum_proc(tile, tpf->userdata, i, si.cur_length, &si.state))
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   684
			goto popnext; // we should stop searching in this direction.
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   685
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   686
		// we should continue searching. determine new direction.
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   687
		direction = _tpf_new_direction[i];
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   688
		goto restart; // use tail recursion optimization.
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   689
	}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   690
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   691
	// too high recursion depth.. bail out..
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   692
	if (si.depth >= _patches.pf_maxdepth)
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   693
		goto popnext;
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   694
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   695
	si.depth++; // increase recursion depth.
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   696
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   697
	// see if this tile was already visited..?
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   698
	if (NtpVisit(tpf, tile, direction, si.cur_length)) {
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   699
		// push all possible alternatives
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   700
		si.tile = tile;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   701
		do {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   702
			si.track = _new_track[FIND_FIRST_BIT(bits)][direction];
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   703
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   704
			// out of stack items, bail out?
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   705
			if (tpf->nstack >= lengthof(tpf->stack))
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   706
				break;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   707
			tpf->stack[tpf->nstack] = si;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   708
			HeapifyUp(tpf);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   709
		} while ((bits = KILL_FIRST_BIT(bits)) != 0);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   710
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   711
		// if this is the first recursion step, we need to fill the first_track member.
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   712
		// so the code outside knows which path is better.
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   713
		// also randomize the order in which we search through them.
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   714
		if (si.depth == 1) {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   715
			uint32 r = Random();
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   716
			assert(tpf->nstack == 2 || tpf->nstack == 3);
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   717
			if (r&1) swap_byte(&tpf->stack[0].track, &tpf->stack[1].track);
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   718
			if (tpf->nstack != 2) {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   719
				byte t = tpf->stack[2].track;
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   720
				if (r&2) swap_byte(&tpf->stack[0].track, &t);
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   721
				if (r&4) swap_byte(&tpf->stack[1].track, &t);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   722
				tpf->stack[2].first_track = tpf->stack[2].track = t;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   723
			}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   724
			tpf->stack[0].first_track = tpf->stack[0].track;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   725
			tpf->stack[1].first_track = tpf->stack[1].track;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   726
		}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   727
	}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   728
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   729
popnext:
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   730
	// where to continue.
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   731
	do {
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   732
		if (tpf->nstack == 0) return; // nothing left?
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   733
		si = tpf->stack[0];
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   734
		tile = si.tile;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   735
		HeapifyDown(tpf);
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   736
	} while (
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   737
		!NtpCheck(tpf, tile, _tpf_prev_direction[si.track], si.cur_length) || // already have better path to that tile?
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   738
		tpf->enum_proc(tile, tpf->userdata, si.track, si.cur_length, &si.state)
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   739
	);
193
0a7025304867 (svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents: 159
diff changeset
   740
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   741
	direction = _tpf_new_direction[si.track];
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   742
	goto restart;
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   743
}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   744
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   745
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   746
// new pathfinder for trains. better and faster.
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   747
void NewTrainPathfind(uint tile, byte direction, TPFEnumProc *enum_proc, void *data, byte *cache)
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   748
{
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   749
	if (!_patches.new_pathfinding) {
159
139cf78bfb28 (svn r160) -Codechange: made GetTileTrackStatus more readable (blathijs)
truelight
parents: 148
diff changeset
   750
		FollowTrack(tile, 0x3000 | TRANSPORT_RAIL, direction, enum_proc, NULL, data);
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   751
	} else {
318
648afd1ab9a7 (svn r328) -Fix: remove some unlogical alloca()s (Tron)
darkvater
parents: 241
diff changeset
   752
		NewTrackPathFinder tpf;
648afd1ab9a7 (svn r328) -Fix: remove some unlogical alloca()s (Tron)
darkvater
parents: 241
diff changeset
   753
		tpf.userdata = data;
648afd1ab9a7 (svn r328) -Fix: remove some unlogical alloca()s (Tron)
darkvater
parents: 241
diff changeset
   754
		tpf.enum_proc = enum_proc;
648afd1ab9a7 (svn r328) -Fix: remove some unlogical alloca()s (Tron)
darkvater
parents: 241
diff changeset
   755
		tpf.tracktype = 0;
648afd1ab9a7 (svn r328) -Fix: remove some unlogical alloca()s (Tron)
darkvater
parents: 241
diff changeset
   756
		tpf.maxlength = _patches.pf_maxlength;
648afd1ab9a7 (svn r328) -Fix: remove some unlogical alloca()s (Tron)
darkvater
parents: 241
diff changeset
   757
		tpf.nstack = 0;
648afd1ab9a7 (svn r328) -Fix: remove some unlogical alloca()s (Tron)
darkvater
parents: 241
diff changeset
   758
		tpf.new_link = tpf.links;
648afd1ab9a7 (svn r328) -Fix: remove some unlogical alloca()s (Tron)
darkvater
parents: 241
diff changeset
   759
		tpf.num_links_left = lengthof(tpf.links);
648afd1ab9a7 (svn r328) -Fix: remove some unlogical alloca()s (Tron)
darkvater
parents: 241
diff changeset
   760
		memset(tpf.hash_head, 0, sizeof(tpf.hash_head));
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   761
318
648afd1ab9a7 (svn r328) -Fix: remove some unlogical alloca()s (Tron)
darkvater
parents: 241
diff changeset
   762
		NTPEnum(&tpf, tile, direction);
0
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   763
	}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   764
}
29654efe3188 (svn r1) Import of revision 975 of old (crashed) SVN
truelight
parents:
diff changeset
   765