summaryrefslogtreecommitdiff
path: root/pathfind.c
diff options
context:
space:
mode:
Diffstat (limited to 'pathfind.c')
-rw-r--r--pathfind.c80
1 files changed, 40 insertions, 40 deletions
diff --git a/pathfind.c b/pathfind.c
index 1a39aa376..9a566a273 100644
--- a/pathfind.c
+++ b/pathfind.c
@@ -37,7 +37,7 @@ static bool TPFSetTileBit(TrackPathFinder *tpf, uint tile, int dir)
return true;
} else {
/* two tiles with the same hash, need to make a link */
-
+
/* allocate a link. if out of links, handle this by returning
* that a tile was already visisted. */
if (tpf->num_links_left == 0)
@@ -51,7 +51,7 @@ static bool TPFSetTileBit(TrackPathFinder *tpf, uint tile, int dir)
tpf->hash_tile[hash] = PATHFIND_GET_LINK_OFFS(tpf, link);
link->flags = tpf->hash_head[hash];
- tpf->hash_head[hash] = 0xFFFF; /* multi link */
+ tpf->hash_head[hash] = 0xFFFF; /* multi link */
link->next = 0xFFFF;
}
@@ -59,7 +59,7 @@ static bool TPFSetTileBit(TrackPathFinder *tpf, uint tile, int dir)
/* a linked list of many tiles,
* find the one corresponding to the tile, if it exists.
* otherwise make a new link */
-
+
offs = tpf->hash_tile[hash];
do {
link = PATHFIND_GET_LINK_PTR(tpf, offs);
@@ -74,7 +74,7 @@ static bool TPFSetTileBit(TrackPathFinder *tpf, uint tile, int dir)
}
} while ((offs=link->next) != 0xFFFF);
}
-
+
/* get here if we need to add a new link to link,
* first, allocate a new link, in the same way as before */
if (tpf->num_links_left == 0)
@@ -130,12 +130,12 @@ void TPFMode2(TrackPathFinder *tpf, uint tile, int direction)
// This addition will sometimes overflow by a single tile.
// The use of TILE_MASK here makes sure that we still point at a valid
- // tile, and then this tile will be in the sentinel row/col, so GetTileTrackStatus will fail.
+ // tile, and then this tile will be in the sentinel row/col, so GetTileTrackStatus will fail.
tile = TILE_MASK(tile + _tileoffs_by_dir[direction]);
if (++tpf->rd.cur_length > 50)
return;
-
+
bits = GetTileTrackStatus(tile, tpf->tracktype);
bits = (byte)((bits | (bits >> 8)) & _bits_mask[direction]);
if (bits == 0)
@@ -161,7 +161,7 @@ void TPFMode2(TrackPathFinder *tpf, uint tile, int direction)
// Change direction 4 times only
if ((byte)i != tpf->rd.pft_var6) {
if(++tpf->rd.depth > 4) {
- tpf->rd = rd;
+ tpf->rd = rd;
return;
}
tpf->rd.pft_var6 = (byte)i;
@@ -169,7 +169,7 @@ void TPFMode2(TrackPathFinder *tpf, uint tile, int direction)
continue_here:;
tpf->the_dir = HASBIT(_otherdir_mask[direction],i) ? (i+8) : i;
-
+
#ifdef DEBUG_TILE_PUSH
dbg_push_tile(tile, tpf->the_dir);
#endif
@@ -265,7 +265,7 @@ void TPFMode1(TrackPathFinder *tpf, uint tile, int direction)
if (IS_TILETYPE(tile, MP_TUNNELBRIDGE) && (_map5[tile] & 0xF0)==0) {
if ((_map5[tile] & 3) != direction || ((_map5[tile]>>1)&6) != tpf->tracktype)
return;
- tile = SkipToEndOfTunnel(tpf, tile, direction);
+ tile = SkipToEndOfTunnel(tpf, tile, direction);
}
tile += _tileoffs_by_dir[direction];
tpf->rd.cur_length++;
@@ -286,7 +286,7 @@ void TPFMode1(TrackPathFinder *tpf, uint tile, int direction)
tpf->the_dir = (_otherdir_mask[direction] & (byte)(1 << i)) ? (i+8) : i;
rd = tpf->rd;
-
+
#ifdef DEBUG_TILE_PUSH
dbg_push_tile(tile, tpf->the_dir);
#endif
@@ -304,12 +304,12 @@ void TPFMode1(TrackPathFinder *tpf, uint tile, int direction)
/* the next is only used when signals are checked.
* seems to go in 2 directions simultaneously */
-
+
/* if i can get rid of this, tail end recursion can be used to minimize
- * stack space dramatically. */
+ * stack space dramatically. */
if (tpf->hasbit_13)
return;
-
+
tile = tile_org;
direction ^= 2;
@@ -327,7 +327,7 @@ void TPFMode1(TrackPathFinder *tpf, uint tile, int direction)
do {
i = FIND_FIRST_BIT(bits);
bits = KILL_FIRST_BIT(bits);
-
+
tpf->the_dir = (_otherdir_mask[direction] & (byte)(1 << i)) ? (i+8) : i;
rd = tpf->rd;
if (TPFSetTileBit(tpf, tile, tpf->the_dir) &&
@@ -344,16 +344,16 @@ void FollowTrack(uint tile, uint16 flags, byte direction, TPFEnumProc *enum_proc
assert(direction < 4);
- /* initialize path finder variables */
+ /* initialize path finder variables */
tpf->userdata = data;
- tpf->enum_proc = enum_proc;
+ tpf->enum_proc = enum_proc;
tpf->new_link = tpf->links;
tpf->num_links_left = 0x400;
tpf->rd.cur_length = 0;
tpf->rd.depth = 0;
tpf->rd.pft_var6 = 0;
-
+
tpf->var2 = HASBIT(flags, 15) ? 0x43 : 0xFF; /* 0x8000 */
tpf->disable_tile_hash = HASBIT(flags, 12) != 0; /* 0x1000 */
@@ -362,10 +362,10 @@ void FollowTrack(uint tile, uint16 flags, byte direction, TPFEnumProc *enum_proc
tpf->tracktype = (byte)flags;
- if (HASBIT(flags, 11)) {
+ if (HASBIT(flags, 11)) {
tpf->rd.pft_var6 = 0xFF;
tpf->enum_proc(tile, data, 0, 0, 0);
- TPFMode2(tpf, tile, direction);
+ TPFMode2(tpf, tile, direction);
} else {
/* clear the hash_heads */
memset(tpf->hash_head, 0, sizeof(tpf->hash_head));
@@ -373,7 +373,7 @@ void FollowTrack(uint tile, uint16 flags, byte direction, TPFEnumProc *enum_proc
}
if (after_proc != NULL)
- after_proc(tpf);
+ after_proc(tpf);
}
typedef struct {
@@ -439,10 +439,10 @@ static void INLINE HeapifyUp(NewTrackPathFinder *tpf)
{
StackedItem si;
int i = ++tpf->nstack;
-
+
while (i != 1 && ARR(i).cur_length < ARR(i>>1).cur_length) {
// the child element is larger than the parent item.
- // swap the child item and the parent item.
+ // swap the child item and the parent item.
si = ARR(i); ARR(i) = ARR(i>>1); ARR(i>>1) = si;
i>>=1;
}
@@ -462,13 +462,13 @@ static void INLINE HeapifyDown(NewTrackPathFinder *tpf)
while ((j=i*2) <= n) {
// figure out which is smaller of the children.
- if (j != n && ARR(j).cur_length > ARR(j+1).cur_length)
+ if (j != n && ARR(j).cur_length > ARR(j+1).cur_length)
j++; // right item is smaller
assert(i <= n && j <= n);
if (ARR(i).cur_length <= ARR(j).cur_length)
break; // base elem smaller than smallest, done!
-
+
// swap parent with the child
si = ARR(i); ARR(i) = ARR(j); ARR(j) = si;
i = j;
@@ -484,7 +484,7 @@ static bool NtpVisit(NewTrackPathFinder *tpf, uint tile, uint dir, uint length)
HashLink *link, *new_link;
assert(length < 1024);
-
+
hash = PATHFIND_HASH_TILE(tile);
// never visited before?
@@ -496,10 +496,10 @@ static bool NtpVisit(NewTrackPathFinder *tpf, uint tile, uint dir, uint length)
if (head != 0xffff) {
if ( (TileIndex)tile == tpf->hash_tile[hash] && (head & 0x3) == dir ) {
-
+
// longer length
if (length >= (head >> 2)) return false;
-
+
tpf->hash_head[hash] = dir | (length << 2);
return true;
}
@@ -517,13 +517,13 @@ static bool NtpVisit(NewTrackPathFinder *tpf, uint tile, uint dir, uint length)
tpf->hash_tile[hash] = NTP_GET_LINK_OFFS(tpf, link);
link->typelength = tpf->hash_head[hash];
- tpf->hash_head[hash] = 0xFFFF; /* multi link */
+ tpf->hash_head[hash] = 0xFFFF; /* multi link */
link->next = 0xFFFF;
} else {
// a linked list of many tiles,
// find the one corresponding to the tile, if it exists.
// otherwise make a new link
-
+
uint offs = tpf->hash_tile[hash];
do {
link = NTP_GET_LINK_PTR(tpf, offs);
@@ -534,7 +534,7 @@ static bool NtpVisit(NewTrackPathFinder *tpf, uint tile, uint dir, uint length)
}
} while ((offs=link->next) != 0xFFFF);
}
-
+
/* get here if we need to add a new link to link,
* first, allocate a new link, in the same way as before */
if (tpf->num_links_left == 0)
@@ -613,7 +613,7 @@ restart:
for(;;) {
tile += _tileoffs_by_dir[direction];
-
+
// too long search length? bail out.
if (++si.cur_length >= tpf->maxlength)
goto popnext;
@@ -628,7 +628,7 @@ restart:
// regular rail tile, determine the tracks that are actually reachable.
bits &= _bits_mask[direction];
if (bits == 0) goto popnext; // no tracks there? stop searching.
-
+
// complex tile?, let the generic handler handle that..
if (KILL_FIRST_BIT(bits) != 0) break;
@@ -656,16 +656,16 @@ restart:
// too high recursion depth.. bail out..
if (si.depth >= _patches.pf_maxdepth)
goto popnext;
-
+
si.depth++; // increase recursion depth.
// see if this tile was already visited..?
if (NtpVisit(tpf, tile, direction, si.cur_length)) {
- // push all possible alternatives
+ // push all possible alternatives
si.tile = tile;
do {
si.track = _new_track[FIND_FIRST_BIT(bits)][direction];
-
+
// out of stack items, bail out?
if (tpf->nstack >= lengthof(tpf->stack))
break;
@@ -678,11 +678,11 @@ restart:
// also randomize the order in which we search through them.
if (si.depth == 1) {
uint32 r = Random();
- assert(tpf->nstack == 2 || tpf->nstack == 3);
- if (r&1) swap_byte(&tpf->stack[0].track, &tpf->stack[1].track);
+ assert(tpf->nstack == 2 || tpf->nstack == 3);
+ if (r&1) swap_byte(&tpf->stack[0].track, &tpf->stack[1].track);
if (tpf->nstack != 2) {
byte t = tpf->stack[2].track;
- if (r&2) swap_byte(&tpf->stack[0].track, &t);
+ if (r&2) swap_byte(&tpf->stack[0].track, &t);
if (r&4) swap_byte(&tpf->stack[1].track, &t);
tpf->stack[2].first_track = tpf->stack[2].track = t;
}
@@ -702,7 +702,7 @@ popnext:
!NtpCheck(tpf, tile, _tpf_prev_direction[si.track], si.cur_length) || // already have better path to that tile?
tpf->enum_proc(tile, tpf->userdata, si.track, si.cur_length, &si.state)
);
-
+
direction = _tpf_new_direction[si.track];
goto restart;
}
@@ -718,7 +718,7 @@ void NewTrainPathfind(uint tile, byte direction, TPFEnumProc *enum_proc, void *d
tpf = alloca(sizeof(NewTrackPathFinder));
tpf->userdata = data;
- tpf->enum_proc = enum_proc;
+ tpf->enum_proc = enum_proc;
tpf->tracktype = 0;
tpf->maxlength = _patches.pf_maxlength;
tpf->nstack = 0;
generated by cgit v1.2.3-54-g00ecf (git 2.44.0) at 2024-07-10 04:38:56 +0000