# pathfind.cpp

Go to the documentation of this file.

    00001 /* $Id: pathfind.cpp 15299 2009-01-31 20:16:06Z smatz $ */
    00002
    00005 #include "stdafx.h"
    00006 #include "station_map.h"
    00007 #include "settings_type.h"
    00008 #include "pathfind.h"
    00009 #include "debug.h"
    00010 #include "tunnelbridge_map.h"
    00011 #include "core/random_func.hpp"
    00012 #include "core/alloc_type.hpp"
    00013 #include "tunnelbridge.h"
    00014
    00015 /* remember which tiles we have already visited so we don't visit them again. */
    00016 static bool TPFSetTileBit(TrackPathFinder *tpf, TileIndex tile, int dir)
    00017 {
    00018   uint hash, val, offs;
    00019   TrackPathFinderLink *link, *new_link;
    00020   uint bits = 1 << dir;
    00021
    00022   if (tpf->disable_tile_hash)
    00023     return true;
    00024
    00025   hash = PATHFIND_HASH_TILE(tile);
    00026
    00027   val = tpf->hash_head[hash];
    00028
    00029   if (val == 0) {
    00030     /* unused hash entry, set the appropriate bit in it and return true
    00031      * to indicate that a bit was set. */
    00032     tpf->hash_head[hash] = bits;
    00033     tpf->hash_tile[hash] = tile;
    00034     return true;
    00035   } else if (!(val & 0x8000)) {
    00036     /* single tile */
    00037
    00038     if (tile == tpf->hash_tile[hash]) {
    00039       /* found another bit for the same tile,
    00040        * check if this bit is already set, if so, return false */
    00041       if (val & bits)
    00042         return false;
    00043
    00044       /* otherwise set the bit and return true to indicate that the bit
    00045        * was set */
    00046       tpf->hash_head[hash] = val | bits;
    00047       return true;
    00048     } else {
    00049       /* two tiles with the same hash, need to make a link */
    00050
    00051       /* allocate a link. if out of links, handle this by returning
    00052        * that a tile was already visisted. */
    00053       if (tpf->num_links_left == 0) {
    00054         return false;
    00055       }
    00056       tpf->num_links_left--;
    00057       link = tpf->new_link++;
    00058
    00059       /* move the data that was previously in the hash_??? variables
    00060        * to the link struct, and let the hash variables point to the link */
    00061       link->tile = tpf->hash_tile[hash];
    00062       tpf->hash_tile[hash] = PATHFIND_GET_LINK_OFFS(tpf, link);
    00063
    00064       link->flags = tpf->hash_head[hash];
    00065       tpf->hash_head[hash] = 0xFFFF; // multi link
    00066
    00067       link->next = 0xFFFF;
    00068     }
    00069   } else {
    00070     /* a linked list of many tiles,
    00071      * find the one corresponding to the tile, if it exists.
    00072      * otherwise make a new link */
    00073
    00074     offs = tpf->hash_tile[hash];
    00075     do {
    00076       link = PATHFIND_GET_LINK_PTR(tpf, offs);
    00077       if (tile == link->tile) {
    00078         /* found the tile in the link list,
    00079          * check if the bit was alrady set, if so return false to indicate that the
    00080          * bit was already set */
    00081         if (link->flags & bits)
    00082           return false;
    00083         link->flags |= bits;
    00084         return true;
    00085       }
    00086     } while ((offs=link->next) != 0xFFFF);
    00087   }
    00088
    00089   /* get here if we need to add a new link to link,
    00090    * first, allocate a new link, in the same way as before */
    00091   if (tpf->num_links_left == 0) {
    00092       return false;
    00093   }
    00094   tpf->num_links_left--;
    00095   new_link = tpf->new_link++;
    00096
    00097   /* then fill the link with the new info, and establish a ptr from the old
    00098    * link to the new one */
    00099   new_link->tile = tile;
    00100   new_link->flags = bits;
    00101   new_link->next = 0xFFFF;
    00102
    00103   link->next = PATHFIND_GET_LINK_OFFS(tpf, new_link);
    00104   return true;
    00105 }
    00106
    00107 static void TPFModeShip(TrackPathFinder *tpf, TileIndex tile, DiagDirection direction)
    00108 {
    00109   assert(tpf->tracktype == TRANSPORT_WATER);
    00110
    00111   if (IsTileType(tile, MP_TUNNELBRIDGE)) {
    00112     /* wrong track type */
    00113     if (GetTunnelBridgeTransportType(tile) != tpf->tracktype) return;
    00114
    00115     DiagDirection dir = GetTunnelBridgeDirection(tile);
    00116     /* entering tunnel / bridge? */
    00117     if (dir == direction) {
    00118       TileIndex endtile = GetOtherTunnelBridgeEnd(tile);
    00119
    00120       tpf->rd.cur_length += GetTunnelBridgeLength(tile, endtile) + 1;
    00121
    00122       TPFSetTileBit(tpf, tile, 14);
    00123       TPFSetTileBit(tpf, endtile, 14);
    00124
    00125       tile = endtile;
    00126     } else {
    00127       /* leaving tunnel / bridge? */
    00128       if (ReverseDiagDir(dir) != direction) return;
    00129     }
    00130   }
    00131
    00132   /* This addition will sometimes overflow by a single tile.
    00133    * The use of TILE_MASK here makes sure that we still point at a valid
    00134    * tile, and then this tile will be in the sentinel row/col, so GetTileTrackStatus will fail. */
    00135   tile = TILE_MASK(tile + TileOffsByDiagDir(direction));
    00136
    00137   if (++tpf->rd.cur_length > 50)
    00138     return;
    00139
    00140   TrackBits bits = TrackStatusToTrackBits(GetTileTrackStatus(tile, tpf->tracktype, tpf->sub_type)) & DiagdirReachesTracks(direction);
    00141   if (bits == TRACK_BIT_NONE) return;
    00142
    00143   assert(TileX(tile) != MapMaxX() && TileY(tile) != MapMaxY());
    00144
    00145   bool only_one_track = true;
    00146   do {
    00147     Track track = RemoveFirstTrack(&bits);
    00148     if (bits != TRACK_BIT_NONE) only_one_track = false;
    00149     RememberData rd = tpf->rd;
    00150
    00151     /* Change direction 4 times only */
    00152     if (!only_one_track && track != tpf->rd.last_choosen_track) {
    00153       if (++tpf->rd.depth > 4) {
    00154         tpf->rd = rd;
    00155         return;
    00156       }
    00157       tpf->rd.last_choosen_track = track;
    00158     }
    00159
    00160     tpf->the_dir = TrackEnterdirToTrackdir(track, direction);
    00161
    00162     if (!tpf->enum_proc(tile, tpf->userdata, tpf->the_dir, tpf->rd.cur_length)) {
    00163       TPFModeShip(tpf, tile, TrackdirToExitdir(tpf->the_dir));
    00164     }
    00165
    00166     tpf->rd = rd;
    00167   } while (bits != TRACK_BIT_NONE);
    00168
    00169 }
    00170
    00180 static inline bool CanAccessTileInDir(TileIndex tile, DiagDirection side, TransportType tracktype)
    00181 {
    00182   if (tracktype == TRANSPORT_RAIL) {
    00183     /* depot from wrong side */
    00184     if (IsRailDepotTile(tile) && GetRailDepotDirection(tile) != side) return false;
    00185   } else if (tracktype == TRANSPORT_ROAD) {
    00186     /* depot from wrong side */
    00187     if (IsRoadDepotTile(tile) && GetRoadDepotDirection(tile) != side) return false;
    00188     /* non-driverthrough road station from wrong side */
    00189     if (IsStandardRoadStopTile(tile) && GetRoadStopDir(tile) != side) return false;
    00190   }
    00191
    00192   return true;
    00193 }
    00194
    00195 static void TPFModeNormal(TrackPathFinder *tpf, TileIndex tile, DiagDirection direction)
    00196 {
    00197   const TileIndex tile_org = tile;
    00198
    00199   if (IsTileType(tile, MP_TUNNELBRIDGE)) {
    00200     /* wrong track type */
    00201     if (GetTunnelBridgeTransportType(tile) != tpf->tracktype) return;
    00202
    00203     DiagDirection dir = GetTunnelBridgeDirection(tile);
    00204     /* entering tunnel / bridge? */
    00205     if (dir == direction) {
    00206       TileIndex endtile = GetOtherTunnelBridgeEnd(tile);
    00207
    00208       tpf->rd.cur_length += GetTunnelBridgeLength(tile, endtile) + 1;
    00209
    00210       TPFSetTileBit(tpf, tile, 14);
    00211       TPFSetTileBit(tpf, endtile, 14);
    00212
    00213       tile = endtile;
    00214     } else {
    00215       /* leaving tunnel / bridge? */
    00216       if (ReverseDiagDir(dir) != direction) return;
    00217     }
    00218   } else {
    00219     /* can we leave tile in this dir? */
    00220     if (!CanAccessTileInDir(tile, direction, tpf->tracktype)) return;
    00221   }
    00222
    00223   tile += TileOffsByDiagDir(direction);
    00224
    00225   /* can we enter tile in this dir? */
    00226   if (!CanAccessTileInDir(tile, ReverseDiagDir(direction), tpf->tracktype)) return;
    00227
    00228   /* Check if the new tile is a tunnel or bridge head and that the direction
    00229    * and transport type match */
    00230   if (IsTileType(tile, MP_TUNNELBRIDGE)) {
    00231     if (GetTunnelBridgeDirection(tile) != direction ||
    00232         GetTunnelBridgeTransportType(tile) != tpf->tracktype) {
    00233       return;
    00234     }
    00235   }
    00236
    00237   TrackdirBits trackdirbits = TrackStatusToTrackdirBits(GetTileTrackStatus(tile, tpf->tracktype, tpf->sub_type));
    00238
    00239   /* Check in case of rail if the owner is the same */
    00240   if (tpf->tracktype == TRANSPORT_RAIL) {
    00241     if (trackdirbits != TRACKDIR_BIT_NONE && TrackStatusToTrackdirBits(GetTileTrackStatus(tile_org, TRANSPORT_RAIL, 0)) != TRACKDIR_BIT_NONE) {
    00242       if (GetTileOwner(tile_org) != GetTileOwner(tile)) return;
    00243     }
    00244   }
    00245
    00246   tpf->rd.cur_length++;
    00247
    00248   trackdirbits &= DiagdirReachesTrackdirs(direction);
    00249   TrackBits bits = TrackdirBitsToTrackBits(trackdirbits);
    00250
    00251   if (bits != TRACK_BIT_NONE) {
    00252     if (!tpf->disable_tile_hash || (tpf->rd.cur_length <= 64 && (KillFirstBit(bits) == 0 || ++tpf->rd.depth <= 7))) {
    00253       do {
    00254         Track track = RemoveFirstTrack(&bits);
    00255
    00256         tpf->the_dir = TrackEnterdirToTrackdir(track, direction);
    00257         RememberData rd = tpf->rd;
    00258
    00259         /* make sure we are not leaving from invalid side */
    00260         if (TPFSetTileBit(tpf, tile, tpf->the_dir) && CanAccessTileInDir(tile, TrackdirToExitdir(tpf->the_dir), tpf->tracktype) &&
    00261             !tpf->enum_proc(tile, tpf->userdata, tpf->the_dir, tpf->rd.cur_length) ) {
    00262           TPFModeNormal(tpf, tile, TrackdirToExitdir(tpf->the_dir));
    00263         }
    00264         tpf->rd = rd;
    00265       } while (bits != TRACK_BIT_NONE);
    00266     }
    00267   }
    00268 }
    00269
    00270 void FollowTrack(TileIndex tile, PathfindFlags flags, TransportType tt, uint sub_type, DiagDirection direction, TPFEnumProc *enum_proc, TPFAfterProc *after_proc, void *data)
    00271 {
    00272   assert(IsValidDiagDirection(direction));
    00273
    00274   SmallStackSafeStackAlloc<TrackPathFinder, 1> tpf;
    00275
    00276   /* initialize path finder variables */
    00277   tpf->userdata = data;
    00278   tpf->enum_proc = enum_proc;
    00279   tpf->new_link = tpf->links;
    00280   tpf->num_links_left = lengthof(tpf->links);
    00281
    00282   tpf->rd.cur_length = 0;
    00283   tpf->rd.depth = 0;
    00284   tpf->rd.last_choosen_track = INVALID_TRACK;
    00285
    00286   tpf->disable_tile_hash = (flags & PATHFIND_FLAGS_DISABLE_TILE_HASH) != 0;
    00287
    00288   tpf->tracktype = tt;
    00289   tpf->sub_type = sub_type;
    00290
    00291   if ((flags & PATHFIND_FLAGS_SHIP_MODE) != 0) {
    00292     tpf->enum_proc(tile, data, INVALID_TRACKDIR, 0);
    00293     TPFModeShip(tpf, tile, direction);
    00294   } else {
    00295     /* clear the hash_heads */
    00296     memset(tpf->hash_head, 0, sizeof(tpf->hash_head));
    00297     TPFModeNormal(tpf, tile, direction);
    00298   }
    00299
    00300   if (after_proc != NULL) after_proc(tpf);
    00301 }
    00302
    00303 struct StackedItem {
    00304   TileIndex tile;
    00305   uint16 cur_length;
    00306   uint16 priority;
    00307   TrackdirByte track;
    00308   byte depth;
    00309   byte state;
    00310   byte first_track;
    00311 };
    00312
    00313 struct HashLink {
    00314   TileIndex tile;
    00315   uint16 typelength;
    00316   uint16 next;
    00317 };
    00318
    00319 struct NewTrackPathFinder {
    00320   NTPEnumProc *enum_proc;
    00321   void *userdata;
    00322   TileIndex dest;
    00323
    00324   TransportType tracktype;
    00325   RailTypes railtypes;
    00326   uint maxlength;
    00327
    00328   HashLink *new_link;
    00329   uint num_links_left;
    00330
    00331   uint nstack;
    00332   StackedItem stack[256];
    00333
    00334   uint16 hash_head[0x400];
    00335   TileIndex hash_tile[0x400];
    00336
    00337   HashLink links[0x400];
    00338
    00339 };
    00340 #define NTP_GET_LINK_OFFS(tpf, link) ((byte*)(link) - (byte*)tpf->links)
    00341 #define NTP_GET_LINK_PTR(tpf, link_offs) (HashLink*)((byte*)tpf->links + (link_offs))
    00342
    00343 #define ARR(i) tpf->stack[(i)-1]
    00344
    00347 static inline void HeapifyUp(NewTrackPathFinder *tpf)
    00348 {
    00349   StackedItem si;
    00350   int i = ++tpf->nstack;
    00351
    00352   while (i != 1 && ARR(i).priority < ARR(i>>1).priority) {
    00353     /* the child element is larger than the parent item.
    00354      * swap the child item and the parent item. */
    00355     si = ARR(i); ARR(i) = ARR(i >> 1); ARR(i >> 1) = si;
    00356     i >>= 1;
    00357   }
    00358 }
    00359
    00361 static inline void HeapifyDown(NewTrackPathFinder *tpf)
    00362 {
    00363   StackedItem si;
    00364   int i = 1, j;
    00365   int n;
    00366
    00367   assert(tpf->nstack > 0);
    00368   n = --tpf->nstack;
    00369
    00370   if (n == 0) return; // heap is empty so nothing to do?
    00371
    00372   /* copy the last item to index 0. we use it as base for heapify. */
    00373   ARR(1) = ARR(n + 1);
    00374
    00375   while ((j = i * 2) <= n) {
    00376     /* figure out which is smaller of the children. */
    00377     if (j != n && ARR(j).priority > ARR(j + 1).priority)
    00378       j++; // right item is smaller
    00379
    00380     assert(i <= n && j <= n);
    00381     if (ARR(i).priority <= ARR(j).priority)
    00382       break; // base elem smaller than smallest, done!
    00383
    00384     /* swap parent with the child */
    00385     si = ARR(i); ARR(i) = ARR(j); ARR(j) = si;
    00386     i = j;
    00387   }
    00388 }
    00389
    00393 static bool NtpVisit(NewTrackPathFinder *tpf, TileIndex tile, DiagDirection dir, uint length)
    00394 {
    00395   uint hash,head;
    00396   HashLink *link, *new_link;
    00397
    00398   assert(length < 16384-1);
    00399
    00400   hash = PATHFIND_HASH_TILE(tile);
    00401
    00402   /* never visited before? */
    00403   if ((head=tpf->hash_head[hash]) == 0) {
    00404     tpf->hash_tile[hash] = tile;
    00405     tpf->hash_head[hash] = dir | (length << 2);
    00406     return true;
    00407   }
    00408
    00409   if (head != 0xffff) {
    00410     if (tile == tpf->hash_tile[hash] && (head & 0x3) == (uint)dir) {
    00411
    00412       /* longer length */
    00413       if (length >= (head >> 2)) return false;
    00414
    00415       tpf->hash_head[hash] = dir | (length << 2);
    00416       return true;
    00417     }
    00418     /* two tiles with the same hash, need to make a link
    00419      * allocate a link. if out of links, handle this by returning
    00420      * that a tile was already visisted. */
    00421     if (tpf->num_links_left == 0) {
    00422       DEBUG(ntp, 1, "No links left");
    00423       return false;
    00424     }
    00425
    00426     tpf->num_links_left--;
    00427     link = tpf->new_link++;
    00428
    00429     /* move the data that was previously in the hash_??? variables
    00430      * to the link struct, and let the hash variables point to the link */
    00431     link->tile = tpf->hash_tile[hash];
    00432     tpf->hash_tile[hash] = NTP_GET_LINK_OFFS(tpf, link);
    00433
    00434     link->typelength = tpf->hash_head[hash];
    00435     tpf->hash_head[hash] = 0xFFFF; // multi link
    00436     link->next = 0xFFFF;
    00437   } else {
    00438     /* a linked list of many tiles,
    00439      * find the one corresponding to the tile, if it exists.
    00440      * otherwise make a new link */
    00441
    00442     uint offs = tpf->hash_tile[hash];
    00443     do {
    00444       link = NTP_GET_LINK_PTR(tpf, offs);
    00445       if (tile == link->tile && (link->typelength & 0x3U) == (uint)dir) {
    00446         if (length >= (uint)(link->typelength >> 2)) return false;
    00447         link->typelength = dir | (length << 2);
    00448         return true;
    00449       }
    00450     } while ((offs = link->next) != 0xFFFF);
    00451   }
    00452
    00453   /* get here if we need to add a new link to link,
    00454    * first, allocate a new link, in the same way as before */
    00455   if (tpf->num_links_left == 0) {
    00456     DEBUG(ntp, 1, "No links left");
    00457     return false;
    00458   }
    00459   tpf->num_links_left--;
    00460   new_link = tpf->new_link++;
    00461
    00462   /* then fill the link with the new info, and establish a ptr from the old
    00463    * link to the new one */
    00464   new_link->tile = tile;
    00465   new_link->typelength = dir | (length << 2);
    00466   new_link->next = 0xFFFF;
    00467
    00468   link->next = NTP_GET_LINK_OFFS(tpf, new_link);
    00469   return true;
    00470 }
    00471
    00479 static bool NtpCheck(NewTrackPathFinder *tpf, TileIndex tile, uint dir, uint length)
    00480 {
    00481   uint hash,head,offs;
    00482   HashLink *link;
    00483
    00484   hash = PATHFIND_HASH_TILE(tile);
    00485   head=tpf->hash_head[hash];
    00486   assert(head);
    00487
    00488   if (head != 0xffff) {
    00489     assert( tpf->hash_tile[hash] == tile && (head & 3) == dir);
    00490     assert( (head >> 2) <= length);
    00491     return length == (head >> 2);
    00492   }
    00493
    00494   /* else it's a linked list of many tiles */
    00495   offs = tpf->hash_tile[hash];
    00496   for (;;) {
    00497     link = NTP_GET_LINK_PTR(tpf, offs);
    00498     if (tile == link->tile && (link->typelength & 0x3U) == dir) {
    00499       assert((uint)(link->typelength >> 2) <= length);
    00500       return length == (uint)(link->typelength >> 2);
    00501     }
    00502     offs = link->next;
    00503     assert(offs != 0xffff);
    00504   }
    00505 }
    00506
    00507
    00508 static uint DistanceMoo(TileIndex t0, TileIndex t1)
    00509 {
    00510   const uint dx = Delta(TileX(t0), TileX(t1));
    00511   const uint dy = Delta(TileY(t0), TileY(t1));
    00512
    00513   const uint straightTracks = 2 * min(dx, dy); // The number of straight (not full length) tracks
    00514   /* OPTIMISATION:
    00515    * Original: diagTracks = max(dx, dy) - min(dx,dy);
    00516    * Proof:
    00517    * (dx-dy) - straightTracks  == (min + max) - straightTracks = min + // max - 2 * min = max - min */
    00518   const uint diagTracks = dx + dy - straightTracks; // The number of diagonal (full tile length) tracks.
    00519
    00520   return diagTracks*DIAG_FACTOR + straightTracks*STR_FACTOR;
    00521 }
    00522
    00523 /* These has to be small cause the max length of a track
    00524  * is currently limited to 16384 */
    00525
    00526 static const byte _length_of_track[16] = {
    00527   DIAG_FACTOR, DIAG_FACTOR, STR_FACTOR, STR_FACTOR, STR_FACTOR, STR_FACTOR, 0, 0,
    00528   DIAG_FACTOR, DIAG_FACTOR, STR_FACTOR, STR_FACTOR, STR_FACTOR, STR_FACTOR, 0, 0
    00529 };
    00530
    00531 /* new more optimized pathfinder for trains...
    00532  * Tile is the tile the train is at.
    00533  * direction is the tile the train is moving towards. */
    00534
    00535 static void NTPEnum(NewTrackPathFinder *tpf, TileIndex tile, DiagDirection direction)
    00536 {
    00537   TrackBits bits, allbits;
    00538   Trackdir track;
    00539   TileIndex tile_org;
    00540   StackedItem si;
    00541   int estimation;
    00542
    00543
    00544
    00545   /* Need to have a special case for the start.
    00546    * We shouldn't call the callback for the current tile. */
    00547   si.cur_length = 1; // Need to start at 1 cause 0 is a reserved value.
    00548   si.depth = 0;
    00549   si.state = 0;
    00550   si.first_track = 0xFF;
    00551   goto start_at;
    00552
    00553   for (;;) {
    00554     /* Get the next item to search from from the priority queue */
    00555     do {
    00556       if (tpf->nstack == 0)
    00557         return; // nothing left? then we're done!
    00558       si = tpf->stack[0];
    00559       tile = si.tile;
    00560
    00561       HeapifyDown(tpf);
    00562       /* Make sure we havn't already visited this tile. */
    00563     } while (!NtpCheck(tpf, tile, ReverseDiagDir(TrackdirToExitdir(ReverseTrackdir(si.track))), si.cur_length));
    00564
    00565     /* Add the length of this track. */
    00566     si.cur_length += _length_of_track[si.track];
    00567
    00568 callback_and_continue:
    00569     if (tpf->enum_proc(tile, tpf->userdata, si.first_track, si.cur_length))
    00570       return;
    00571
    00572     assert(si.track <= 13);
    00573     direction = TrackdirToExitdir(si.track);
    00574
    00575 start_at:
    00576     /* If the tile is the entry tile of a tunnel, and we're not going out of the tunnel,
    00577      *   need to find the exit of the tunnel. */
    00578     if (IsTileType(tile, MP_TUNNELBRIDGE)) {
    00579       if (GetTunnelBridgeDirection(tile) != ReverseDiagDir(direction)) {
    00580         /* We are not just driving out of the tunnel/bridge */
    00581         if (GetTunnelBridgeDirection(tile) != direction ||
    00582             GetTunnelBridgeTransportType(tile) != tpf->tracktype) {
    00583           /* We are not driving into the tunnel/bridge, or it is an invalid tunnel/bridge */
    00584           continue;
    00585         }
    00586         if (!HasBit(tpf->railtypes, GetRailType(tile))) {
    00587           bits = TRACK_BIT_NONE;
    00588           break;
    00589         }
    00590
    00591         TileIndex endtile = GetOtherTunnelBridgeEnd(tile);
    00592         si.cur_length += DIAG_FACTOR * (GetTunnelBridgeLength(tile, endtile) + 1);
    00593         tile = endtile;
    00594         /* tile now points to the exit tile of the tunnel/bridge */
    00595       }
    00596     }
    00597
    00598     /* This is a special loop used to go through
    00599      * a rail net and find the first intersection */
    00600     tile_org = tile;
    00601     for (;;) {
    00602       assert(direction <= 3);
    00603       tile += TileOffsByDiagDir(direction);
    00604
    00605       /* too long search length? bail out. */
    00606       if (si.cur_length >= tpf->maxlength) {
    00607         DEBUG(ntp, 1, "Cur_length too big");
    00608         bits = TRACK_BIT_NONE;
    00609         break;
    00610       }
    00611
    00612       /* Not a regular rail tile?
    00613        * Then we can't use the code below, but revert to more general code. */
    00614       if (!IsTileType(tile, MP_RAILWAY) || !IsPlainRailTile(tile)) {
    00615         /* We found a tile which is not a normal railway tile.
    00616          * Determine which tracks that exist on this tile. */
    00617         bits = TrackdirBitsToTrackBits(TrackStatusToTrackdirBits(GetTileTrackStatus(tile, TRANSPORT_RAIL, 0)) & DiagdirReachesTrackdirs(direction));
    00618
    00619         /* Check that the tile contains exactly one track */
    00620         if (bits == 0 || KillFirstBit(bits) != 0) break;
    00621
    00622         if (!HasBit(tpf->railtypes, GetRailType(tile))) {
    00623           bits = TRACK_BIT_NONE;
    00624           break;
    00625         }
    00626
    00627         /*******************
    00628          * If we reach here, the tile has exactly one track.
    00629          *   tile - index to a tile that is not rail tile, but still straight (with optional signals)
    00630          *   bits - bitmask of which track that exist on the tile (exactly one bit is set)
    00631          *   direction - which direction are we moving in?
    00632          *******************/
    00633         si.track = TrackEnterdirToTrackdir(FindFirstTrack(bits), direction);
    00634         si.cur_length += _length_of_track[si.track];
    00635         goto callback_and_continue;
    00636       }
    00637
    00638       /* Regular rail tile, determine which tracks exist. */
    00639       allbits = GetTrackBits(tile);
    00640       /* Which tracks are reachable? */
    00641       bits = allbits & DiagdirReachesTracks(direction);
    00642
    00643       /* The tile has no reachable tracks => End of rail segment
    00644        * or Intersection => End of rail segment. We check this agains all the
    00645        * bits, not just reachable ones, to prevent infinite loops. */
    00646       if (bits == TRACK_BIT_NONE || TracksOverlap(allbits)) break;
    00647
    00648       if (!HasBit(tpf->railtypes, GetRailType(tile))) {
    00649         bits = TRACK_BIT_NONE;
    00650         break;
    00651       }
    00652
    00653       /* If we reach here, the tile has exactly one track, and this
    00654        track is reachable = > Rail segment continues */
    00655
    00656       track = TrackEnterdirToTrackdir(FindFirstTrack(bits), direction);
    00657       assert(track != INVALID_TRACKDIR);
    00658
    00659       si.cur_length += _length_of_track[track];
    00660
    00661       /* Check if this rail is an upwards slope. If it is, then add a penalty. */
    00662       if (IsDiagonalTrackdir(track) && IsUphillTrackdir(GetTileSlope(tile, NULL), track)) {
    00663         // upwards slope. add some penalty.
    00664         si.cur_length += 4 * DIAG_FACTOR;
    00665       }
    00666
    00667       /* railway tile with signals..? */
    00668       if (HasSignals(tile)) {
    00669         if (!HasSignalOnTrackdir(tile, track)) {
    00670           /* if one way signal not pointing towards us, stop going in this direction => End of rail segment. */
    00671           if (HasSignalOnTrackdir(tile, ReverseTrackdir(track)) && IsOnewaySignal(tile, TrackdirToTrack(track))) {
    00672             bits = TRACK_BIT_NONE;
    00673             break;
    00674           }
    00675         } else if (GetSignalStateByTrackdir(tile, track) == SIGNAL_STATE_GREEN) {
    00676           /* green signal in our direction. either one way or two way. */
    00677           si.state |= 3;
    00678         } else {
    00679           /* reached a red signal. */
    00680           if (HasSignalOnTrackdir(tile, ReverseTrackdir(track))) {
    00681             /* two way red signal. unless we passed another green signal on the way,
    00682              * stop going in this direction => End of rail segment.
    00683              * this is to prevent us from going into a full platform. */
    00684             if (!(si.state & 1)) {
    00685               bits = TRACK_BIT_NONE;
    00686               break;
    00687             }
    00688           }
    00689           if (!(si.state & 2)) {
    00690             /* Is this the first signal we see? And it's red... add penalty */
    00691             si.cur_length += 10 * DIAG_FACTOR;
    00692             si.state += 2; // remember that we added penalty.
    00693             /* Because we added a penalty, we can't just continue as usual.
    00694              * Need to get out and let A* do it's job with
    00695              * possibly finding an even shorter path. */
    00696             break;
    00697           }
    00698         }
    00699
    00700         if (tpf->enum_proc(tile, tpf->userdata, si.first_track, si.cur_length))
    00701           return; // Don't process this tile any further
    00702       }
    00703
    00704       /* continue with the next track */
    00705       direction = TrackdirToExitdir(track);
    00706
    00707       /* safety check if we're running around chasing our tail... (infinite loop) */
    00708       if (tile == tile_org) {
    00709         bits = TRACK_BIT_NONE;
    00710         break;
    00711       }
    00712     }
    00713
    00714     /* There are no tracks to choose between.
    00715      * Stop searching in this direction */
    00716     if (bits == TRACK_BIT_NONE)
    00717       continue;
    00718
    00719     /****************
    00720      * We got multiple tracks to choose between (intersection).
    00721      * Branch the search space into several branches.
    00722      ****************/
    00723
    00724     /* Check if we've already visited this intersection.
    00725      * If we've already visited it with a better length, then
    00726      * there's no point in visiting it again. */
    00727     if (!NtpVisit(tpf, tile, direction, si.cur_length))
    00728       continue;
    00729
    00730     /* Push all possible alternatives that we can reach from here
    00731      * onto the priority heap.
    00732      * 'bits' contains the tracks that we can choose between. */
    00733
    00734     /* First compute the estimated distance to the target.
    00735      * This is used to implement A* */
    00736     estimation = 0;
    00737     if (tpf->dest != 0)
    00738       estimation = DistanceMoo(tile, tpf->dest);
    00739
    00740     si.depth++;
    00741     if (si.depth == 0)
    00742       continue; // We overflowed our depth. No more searching in this direction.
    00743     si.tile = tile;
    00744     while (bits != TRACK_BIT_NONE) {
    00745       Track track = RemoveFirstTrack(&bits);
    00746       si.track = TrackEnterdirToTrackdir(track, direction);
    00747       assert(si.track != 0xFF);
    00748       si.priority = si.cur_length + estimation;
    00749
    00750       /* out of stack items, bail out? */
    00751       if (tpf->nstack >= lengthof(tpf->stack)) {
    00752         DEBUG(ntp, 1, "Out of stack");
    00753         break;
    00754       }
    00755
    00756       tpf->stack[tpf->nstack] = si;
    00757       HeapifyUp(tpf);
    00758     };
    00759
    00760     /* If this is the first intersection, we need to fill the first_track member.
    00761      * so the code outside knows which path is better.
    00762      * also randomize the order in which we search through them. */
    00763     if (si.depth == 1) {
    00764       assert(tpf->nstack == 1 || tpf->nstack == 2 || tpf->nstack == 3);
    00765       if (tpf->nstack != 1) {
    00766         uint32 r = Random();
    00767         if (r & 1) Swap(tpf->stack[0].track, tpf->stack[1].track);
    00768         if (tpf->nstack != 2) {
    00769           TrackdirByte t = tpf->stack[2].track;
    00770           if (r & 2) Swap(tpf->stack[0].track, t);
    00771           if (r & 4) Swap(tpf->stack[1].track, t);
    00772           tpf->stack[2].first_track = tpf->stack[2].track = t;
    00773         }
    00774         tpf->stack[0].first_track = tpf->stack[0].track;
    00775         tpf->stack[1].first_track = tpf->stack[1].track;
    00776       }
    00777     }
    00778
    00779     /* Continue with the next from the queue... */
    00780   }
    00781 }
    00782
    00783
    00785 void NewTrainPathfind(TileIndex tile, TileIndex dest, RailTypes railtypes, DiagDirection direction, NTPEnumProc *enum_proc, void *data)
    00786 {
    00787   SmallStackSafeStackAlloc<NewTrackPathFinder, 1> tpf;
    00788
    00789   tpf->dest = dest;
    00790   tpf->userdata = data;
    00791   tpf->enum_proc = enum_proc;
    00792   tpf->tracktype = TRANSPORT_RAIL;
    00793   tpf->railtypes = railtypes;
    00794   tpf->maxlength = min(_settings_game.pf.opf.pf_maxlength * 3, 10000);
    00795   tpf->nstack = 0;
    00796   tpf->new_link = tpf->links;
    00797   tpf->num_links_left = lengthof(tpf->links);
    00798   memset(tpf->hash_head, 0, sizeof(tpf->hash_head));
    00799
    00800   NTPEnum(tpf, tile, direction);
    00801 }