diff options
| -rw-r--r-- | Makefile | 1 | ||||
| -rw-r--r-- | functions.h | 5 | ||||
| -rw-r--r-- | industry_cmd.c | 4 | ||||
| -rw-r--r-- | landscape.c | 19 | ||||
| -rw-r--r-- | lang/english.txt | 8 | ||||
| -rw-r--r-- | macros.h | 18 | ||||
| -rw-r--r-- | map.c | 33 | ||||
| -rw-r--r-- | map.h | 22 | ||||
| -rw-r--r-- | misc.c | 2 | ||||
| -rw-r--r-- | npf.c | 776 | ||||
| -rw-r--r-- | npf.h | 128 | ||||
| -rw-r--r-- | order_cmd.c | 6 | ||||
| -rw-r--r-- | pathfind.h | 3 | ||||
| -rw-r--r-- | queue.c | 2 | ||||
| -rw-r--r-- | rail_cmd.c | 1 | ||||
| -rw-r--r-- | road_cmd.c | 2 | ||||
| -rw-r--r-- | roadveh_cmd.c | 141 | ||||
| -rw-r--r-- | settings.c | 28 | ||||
| -rw-r--r-- | settings_gui.c | 10 | ||||
| -rw-r--r-- | ship_cmd.c | 92 | ||||
| -rw-r--r-- | station.h | 16 | ||||
| -rw-r--r-- | station_cmd.c | 6 | ||||
| -rw-r--r-- | table/directions.h | 8 | ||||
| -rw-r--r-- | train_cmd.c | 341 | ||||
| -rw-r--r-- | variables.h | 11 |
25 files changed, 1418 insertions, 265 deletions
@@ -595,6 +595,7 @@ C_SOURCES += network_gui.c C_SOURCES += network_server.c C_SOURCES += network_udp.c C_SOURCES += news_gui.c +C_SOURCES += npf.c C_SOURCES += oldloader.c C_SOURCES += order_cmd.c C_SOURCES += order_gui.c diff --git a/functions.h b/functions.h index fdcf33ba5..9808f7ccb 100644 --- a/functions.h +++ b/functions.h @@ -26,11 +26,6 @@ void ClickTile(uint tile); void GetTileDesc(uint tile, TileDesc *td); void DrawTile(TileInfo *ti); -uint TileAddWrap(TileIndex tile, int addx, int addy); -enum { - TILE_WRAPPED = (uint)-1 -}; - bool IsValidTile(uint tile); static inline Point RemapCoords(int x, int y, int z) diff --git a/industry_cmd.c b/industry_cmd.c index 126b596c7..4a2705eb1 100644 --- a/industry_cmd.c +++ b/industry_cmd.c @@ -978,7 +978,7 @@ static void MaybePlantFarmField(Industry *i) int x = (i->width>>1) + Random() % 31 - 16; int y = (i->height>>1) + Random() % 31 - 16; tile = TileAddWrap(i->xy, x, y); - if (tile != TILE_WRAPPED) + if (tile != INVALID_TILE) PlantFarmField(tile); } } @@ -1496,7 +1496,7 @@ static void DoCreateNewIndustry(Industry *i, uint tile, int type, const Industry int x = Random() % 31 - 16; int y = Random() % 31 - 16; uint new_tile = TileAddWrap(tile, x, y); - if (new_tile != TILE_WRAPPED) + if (new_tile != INVALID_TILE) PlantFarmField(new_tile); } } diff --git a/landscape.c b/landscape.c index 32726a577..0f7ca507b 100644 --- a/landscape.c +++ b/landscape.c @@ -721,25 +721,6 @@ TileIndex AdjustTileCoordRandomly(TileIndex a, byte rng) )); } -// This function checks if we add addx/addy to tile, if we -// do wrap around the edges. For example, tile = (10,2) and -// addx = +3 and addy = -4. This function will now return -// TILE_WRAPPED, because the y is wrapped. This is needed in -// for example, farmland. When the tile is not wrapped, -// the result will be tile + TILE_XY(addx, addy) -uint TileAddWrap(TileIndex tile, int addx, int addy) -{ - uint x, y; - x = TileX(tile) + addx; - y = TileY(tile) + addy; - - // Are we about to wrap? - if (x < MapMaxX() && y < MapMaxY()) - return tile + TILE_XY(addx, addy); - - return TILE_WRAPPED; -} - bool IsValidTile(uint tile) { return (tile < MapSizeX() * MapMaxY() && TileX(tile) != MapMaxX()); diff --git a/lang/english.txt b/lang/english.txt index 305d28141..c91c04e26 100644 --- a/lang/english.txt +++ b/lang/english.txt @@ -973,8 +973,8 @@ STR_SHIP_AUTORENEW_FAILED :{WHITE}Autorenew failed on ship {COMMA16} (money STR_AIRCRAFT_AUTORENEW_FAILED :{WHITE}Autorenew failed on aircraft {COMMA16} (money limit) STR_CONFIG_PATCHES :{BLACK}Configure Patches -STR_CONFIG_PATCHES_TIP :{BLACK}Configure the patches -STR_CONFIG_PATCHES_CAPTION :{WHITE}Configure Patches +STR_CONFIG_PATCHES_TIP :{BLACK}Configure the patches +STR_CONFIG_PATCHES_CAPTION :{WHITE}Configure Patches STR_CONFIG_PATCHES_OFF :Off STR_CONFIG_PATCHES_ON :On @@ -984,6 +984,7 @@ STR_CONFIG_PATCHES_CATCHMENT :{LTBLUE}Allow more realistically sized catchme STR_CONFIG_PATCHES_EXTRADYNAMITE :{LTBLUE}Allow removal of more town-owned roads, bridges, etc: {ORANGE}{STRING} STR_CONFIG_PATCHES_MAMMOTHTRAINS :{LTBLUE}Enable building very long trains: {ORANGE}{STRING} STR_CONFIG_PATCHES_REALISTICACCEL :{LTBLUE}Enable realistic acceleration for trains: {ORANGE}{STRING} +STR_CONFIG_PATCHES_FORBID_90_DEG :{LTBLUE}Forbid trains and ships to make 90 deg turns: {ORANGE}{STRING} {LTBLUE} (requires NPF) STR_CONFIG_PATCHES_JOINSTATIONS :{LTBLUE}Join train stations built next to each other: {ORANGE}{STRING} STR_CONFIG_PATCHES_FULLLOADANY :{LTBLUE}Leave station when any cargo is full, if 'full load': {ORANGE}{STRING} STR_CONFIG_PATCHES_IMPROVEDLOAD :{LTBLUE}Use improved loading algorithm: {ORANGE}{STRING} @@ -1003,7 +1004,8 @@ STR_CONFIG_PATCHES_AUTOSCROLL :{LTBLUE}Pan window when mouse is at the edge: STR_CONFIG_PATCHES_BRIBE :{LTBLUE}Allow bribing of the local authority: {ORANGE}{STRING} STR_CONFIG_PATCHES_NEW_DEPOT_FINDING :{LTBLUE}New depot finding: {ORANGE}{STRING} STR_CONFIG_PATCHES_NONUNIFORM_STATIONS :{LTBLUE}Nonuniform stations: {ORANGE}{STRING} -STR_CONFIG_PATCHES_NEW_TRAIN_PATHFIND :{LTBLUE}New algorithm for train pathfinding: {ORANGE}{STRING} +STR_CONFIG_PATCHES_NEW_TRAIN_PATHFIND :{LTBLUE}New algorithm for train pathfinding (NTP): {ORANGE}{STRING} +STR_CONFIG_PATCHES_NEW_PATHFINDING_ALL :{LTBLUE}New global pathfinding (NPF, overrides NTP): {ORANGE}{STRING} STR_CONFIG_PATCHES_SMALL_AIRPORTS :{LTBLUE}Always allow small airports: {ORANGE}{STRING} @@ -110,14 +110,32 @@ extern const byte _ffb_64[128]; static inline int FindFirstBit2x64(int value) { +/* int i = 0; if ( (byte) value == 0) { i += 8; value >>= 8; } return i + FIND_FIRST_BIT(value & 0x3F); + +Faster ( or at least cleaner ) implementation below? +*/ + if ( (byte) value == 0) { + return FIND_FIRST_BIT((value >> 8) & 0x3F) + 8; + } else { + return FIND_FIRST_BIT(value & 0x3F); + } + } +static inline int KillFirstBit2x64(int value) +{ + if ( (byte) value == 0) { + return KILL_FIRST_BIT((value >> 8) & 0x3F) << 8; + } else { + return value & (KILL_FIRST_BIT(value & 0x3F)|0x3F00); + } +} /* [min,max), strictly less than */ #define IS_BYTE_INSIDE(a,min,max) ((byte)((a)-(min)) < (byte)((max)-(min))) @@ -108,6 +108,32 @@ uint ScaleByMapSize1D(uint n) } +// This function checks if we add addx/addy to tile, if we +// do wrap around the edges. For example, tile = (10,2) and +// addx = +3 and addy = -4. This function will now return +// INVALID_TILE, because the y is wrapped. This is needed in +// for example, farmland. When the tile is not wrapped, +// the result will be tile + TILE_XY(addx, addy) +uint TileAddWrap(TileIndex tile, int addx, int addy) +{ + uint x, y; + x = TileX(tile) + addx; + y = TileY(tile) + addy; + + // Are we about to wrap? + if (x < MapMaxX() && y < MapMaxY()) + return tile + TILE_XY(addx, addy); + + return INVALID_TILE; +} + +const TileIndexDiffC _tileoffs_by_dir[] = { + {-1, 0}, + { 0, 1}, + { 1, 0}, + { 0, -1} +}; + uint DistanceManhattan(TileIndex t0, TileIndex t1) { return @@ -151,10 +177,3 @@ uint DistanceFromEdge(TileIndex tile) return minl < minh ? minl : minh; } - -const TileIndexDiffC _tileoffs_by_dir[] = { - {-1, 0}, - { 0, 1}, - { 1, 0}, - { 0, -1} -}; @@ -35,7 +35,9 @@ uint ScaleByMapSize(uint); // Scale relative to the number of tiles uint ScaleByMapSize1D(uint); // Scale relative to the circumference of the map typedef uint32 TileIndex; - +enum { + INVALID_TILE = (uint32) -1 +}; static inline uint TileX(TileIndex tile) { @@ -71,6 +73,24 @@ static inline TileIndexDiff ToTileIndexDiff(TileIndexDiffC tidc) #define TILE_ADDXY(tile, x, y) TILE_ADD(tile, TILE_XY(x, y)) +uint TileAddWrap(TileIndex tile, int addx, int addy); + +static inline TileIndexDiffC TileIndexDiffCByDir(uint dir) { + extern const TileIndexDiffC _tileoffs_by_dir[4]; + return _tileoffs_by_dir[dir]; +} + +/* Returns tile + the diff given in diff. If the result tile would end up + * outside of the map, INVALID_TILE is returned instead. + */ +static inline TileIndex AddTileIndexDiffCWrap(TileIndex tile, TileIndexDiffC diff) { + int x = TileX(tile) + diff.x; + int y = TileY(tile) + diff.y; + if (x < 0 || y < 0 || x > (int)MapMaxX() || y > (int)MapMaxY()) + return INVALID_TILE; + else + return TILE_XY(x, y); +} // Functions to calculate distances uint DistanceManhattan(TileIndex, TileIndex); // also known as L1-Norm @@ -173,6 +173,7 @@ void InitializeStations(void); static void InitializeNameMgr(void); void InitializePlayers(void); static void InitializeCheats(void); +void InitializeNPF(void); void GenerateLandscape(void); void GenerateClearTile(void); @@ -235,6 +236,7 @@ void InitializeGame(uint log_x, uint log_y) InitializeNameMgr(); InitializeVehiclesGuiList(); InitializeTrains(); + InitializeNPF(); InitializePlayers(); InitializeCheats(); @@ -0,0 +1,776 @@ +#include "stdafx.h" +#include "ttd.h" +#include "npf.h" +#include "aystar.h" +#include "macros.h" +#include "pathfind.h" +#include "station.h" +#include "tile.h" + +AyStar _train_find_station; +AyStar _train_find_depot; +AyStar _road_find_station; +AyStar _road_find_depot; +AyStar _npf_aystar; + +/* Maps a trackdir to the bit that stores its status in the map arrays, in the + * direction along with the trackdir */ +const byte _signal_along_trackdir[14] = { + 0x80, 0x80, 0x80, 0x20, 0x40, 0x10, 0, 0, + 0x40, 0x40, 0x40, 0x10, 0x80, 0x20 +}; + +/* Maps a trackdir to the bit that stores its status in the map arrays, in the + * direction against the trackdir */ +const byte _signal_against_trackdir[14] = { + 0x40, 0x40, 0x40, 0x10, 0x80, 0x20, 0, 0, + 0x80, 0x80, 0x80, 0x20, 0x40, 0x10 +}; + +/* Maps a trackdir to the trackdirs that can be reached from it (ie, when + * entering the next tile */ +const uint16 _trackdir_reaches_trackdirs[14] = { +0x1009, 0x0016, 0x1009, 0x0016, 0x0520, 0x0016, 0, 0, +0x0520, 0x2A00, 0x2A00, 0x0520, 0x2A00, 0x1009 +}; + +/* Maps a trackdir to all trackdirs that make 90 deg turns with it. */ +const uint16 _trackdir_crosses_trackdirs[14] = { +0x0202, 0x0101, 0x3030, 0x3030, 0x0C0C, 0x0C0C, 0, 0, +0x0202, 0x0101, 0x3030, 0x3030, 0x0C0C, 0x0C0C +}; + +/* Maps a track to all tracks that make 90 deg turns with it. */ +const byte _track_crosses_tracks[6] = { + 0x2, /* Track 1 -> Track 2 */ + 0x1, /* Track 2 -> Track 1 */ + 0x30, /* Upper -> Left | Right */ + 0x30, /* Lower -> Left | Right */ + 0x0C, /* Left -> Upper | Lower */ + 0x0C, /* Right -> Upper | Lower */ +}; + +/* Maps a trackdir to the (4-way) direction the tile is exited when following + * that trackdir */ +const byte _trackdir_to_exitdir[14] = { + 0,1,0,1,2,1, 0,0, + 2,3,3,2,3,0, +}; + +const byte _track_exitdir_to_trackdir[6][4] = { + {0, 0xff, 8, 0xff}, + {0xff, 1, 0xff, 9}, + {2, 0xff, 0xff, 10}, + {0xff, 3, 11, 0xf}, + {0xff, 0xff, 4, 12}, + {13, 5, 0xff, 0xff} +}; + +const byte _track_direction_to_trackdir[6][8] = { + {0xff, 0, 0xff, 0xff, 0xff, 8, 0xff, 0xff}, + {0xff, 0xff, 0xff, 1, 0xff, 0xff, 0xff, 9}, + {0xff, 0xff, 2, 0xff, 0xff, 0xff, 10, 0xff}, + {0xff, 0xff, 3, 0xff, 0xff, 0xff, 11, 0xff}, + {12, 0xff, 0xff, 0xff, 4, 0xff, 0xff, 0xff}, + {13, 0xff, 0xff, 0xff, 5, 0xff, 0xff, 0xff} +}; + +const byte _dir_to_diag_trackdir[4] = { + 0, 1, 8, 9, +}; + +const byte _reverse_dir[4] = { + 2, 3, 0, 1 +}; + +const byte _reverse_trackdir[14] = { + 8, 9, 10, 11, 12, 13, 0xFF, 0xFF, + 0, 1, 2, 3, 4, 5 +}; + +/* The cost of each trackdir. A diagonal piece is the full NPF_TILE_LENGTH, + * the shorter piece is sqrt(2)/2*NPF_TILE_LENGTH =~ 0.7071 + */ +#define NPF_STRAIGHT_LENGTH (uint)(NPF_TILE_LENGTH * 0.7071) +static const uint _trackdir_length[14] = { +NPF_TILE_LENGTH, NPF_TILE_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, 0, 0, +NPF_TILE_LENGTH, NPF_TILE_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH +}; + +uint NTPHash(uint key1, uint key2) +{ + return PATHFIND_HASH_TILE(key1); +} + +int32 NPFCalcZero(AyStar* as, AyStarNode* current, OpenListNode* parent) { + return 0; +} + +/* Calcs the heuristic to the target station (using NPFFindStationOrTileData). After + * will save the heuristic into NPFFoundTargetData if it is the smallest until + * now. It will then also save AyStarNode.user_data[NPF_TRACKDIR_CHOICE] in + * best_trackdir + */ +int32 NPFCalcStationOrTileHeuristic(AyStar* as, AyStarNode* current, OpenListNode* parent) { + NPFFindStationOrTileData* fstd = (NPFFindStationOrTileData*)as->user_target; + NPFFoundTargetData* ftd = (NPFFoundTargetData*)as->user_path; + TileIndex from = current->tile; + TileIndex to = fstd->dest_coords; + uint dist = DistanceManhattan(from, to) * NPF_TILE_LENGTH; + + if (dist < ftd->best_bird_dist) { + ftd->best_bird_dist = dist; + ftd->best_trackdir = current->user_data[NPF_TRACKDIR_CHOICE]; + } + #ifdef NPF_DEBUG + debug("Calculating H for: (%d, %d). Result: %d", TileX(current->tile), TileY(current->tile), dist); + #endif + return dist; +} + +/* Fills AyStarNode.user_data[NPF_TRACKDIRCHOICE] with the chosen direction to + * get here, either getting it from the current choice or from the parent's + * choice */ +void NPFFillTrackdirChoice(AyStarNode* current, OpenListNode* parent) +{ + if (parent->path.parent == NULL) { + byte trackdir = current->direction; + /* This is a first order decision, so we'd better save the + * direction we chose */ + current->user_data[NPF_TRACKDIR_CHOICE] = trackdir; + #ifdef NPF_DEBUG + debug("Saving trackdir: %#x", trackdir); + #endif + } else { + /* We've already made the decision, so just save our parent's + * decision */ + current->user_data[NPF_TRACKDIR_CHOICE] = parent->path.node.user_data[NPF_TRACKDIR_CHOICE]; + } + +} + +/* Will return the cost of the tunnel. If it is an entry, it will return the + * cost of that tile. If the tile is an exit, it will return the tunnel length + * including the exit tile. Requires that this is a Tunnel tile */ +uint NPFTunnelCost(AyStarNode* current) { + byte exitdir = _trackdir_to_exitdir[current->direction]; + TileIndex tile = current->tile; + if ( (uint)(_map5[tile] & 3) == _reverse_dir[exitdir]) { + /* We just popped out if this tunnel, since were + * facing the tunnel exit */ + FindLengthOfTunnelResult flotr; + flotr = FindLengthOfTunnel(tile, _reverse_dir[exitdir]); + return flotr.length * NPF_TILE_LENGTH; + //TODO: Penalty for tunnels? + } else { + /* We are entering the tunnel, the enter tile is just a + * straight track */ + return NPF_TILE_LENGTH; + } +} + +uint NPFSlopeCost(AyStarNode* current) { + TileIndex next = current->tile + TileOffsByDir(_trackdir_to_exitdir[current->direction]); + if (GetTileZ(next) > GetTileZ(current->tile)) { + /* Slope up */ + return _patches.npf_rail_slope_penalty; + } + return 0; + /* Should we give a bonus for slope down? Probably not, we + * could just substract that bonus from the penalty, because + * there is only one level of steepness... */ +} + +void NPFMarkTile(TileIndex tile) { + switch(GetTileType(tile)) { + case MP_RAILWAY: + case MP_STREET: + /* DEBUG: mark visited tiles by mowing the grass under them + * ;-) */ + _map2[tile] &= ~15; + MarkTileDirtyByTile(tile); + break; + default: + break; + } +} + +int32 NPFWaterPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent) { + //TileIndex tile = current->tile; + int32 cost = 0; + byte trackdir = current->direction; + + cost = _trackdir_length[trackdir]; /* Should be different for diagonal tracks */ + + /* TODO Penalties? */ + + return cost; +} + +/* Determine the cost of this node, for road tracks */ +int32 NPFRoadPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent) { + TileIndex tile = current->tile; + int32 cost = 0; + /* Determine base length */ + switch (GetTileType(tile)) { + case MP_TUNNELBRIDGE: + if ((_map5[tile] & 0xF0)==0) { + cost = NPFTunnelCost(current); + break; + } + /* Fall through if above if is false, it is a bridge + * then. We treat that as ordinary rail */ + case MP_STREET: + cost = NPF_TILE_LENGTH; + break; + default: + break; + } + + /* Determine extra costs */ + + /* Check for slope */ + cost += NPFSlopeCost(current); + + /* Check for turns */ + //TODO + + #ifdef NPF_MARKROUTE + NPFMarkTile(tile); + #endif + #ifdef NPF_DEBUG + debug("Calculating G for: (%d, %d). Result: %d", TileX(current->tile), TileY(current->tile), cost); + #endif + return cost; +} + + +/* Determine the cost of this node, for railway tracks */ +int32 NPFRailPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent) { + TileIndex tile = current->tile; + byte trackdir = current->direction; + int32 cost = 0; + /* Determine base length */ + switch (GetTileType(tile)) { + case MP_TUNNELBRIDGE: + if ((_map5[tile] & 0xF0)==0) { + cost = NPFTunnelCost(current); + break; + } + /* Fall through if above if is false, it is a bridge + * then. We treat that as ordinary rail */ + case MP_RAILWAY: + cost = _trackdir_length[trackdir]; /* Should be different for diagonal tracks */ + break; + case MP_STREET: /* Railway crossing */ + cost = NPF_TILE_LENGTH; + break; + default: + break; + } + + /* Determine extra costs */ + + /* Ordinary track with signals */ + if (IsTileType(tile, MP_RAILWAY) && (_map5[tile] & 0xC0) == 0x40) { + if ((_map2[tile] & _signal_along_trackdir[trackdir]) == 0) { + /* Signal facing us is red */ + if (!(current->user_data[NPF_NODE_FLAGS] & NPF_FLAG_SEEN_SIGNAL)) { + /* Penalize the first signal we + * encounter, if it is red */ + cost += _patches.npf_rail_firstred_penalty; + } + } + current->user_data[NPF_NODE_FLAGS] |= NPF_FLAG_SEEN_SIGNAL; + } + + /* Check for slope */ + cost += NPFSlopeCost(current); + + /* Check for turns */ + //TODO + + /* Check for occupied track */ + //TODO + + /* Check for station tiles */ + if (IsTileType(tile, MP_STATION)) { + /* We give a station tile a penalty. Logically we would only + * want to give station tiles that are not our destination + * this penalty. This would discourage trains to drive through + * busy stations. But, we can just give any station tile a + * penalty, because every possible route will get this penalty + * exactly once, on its end tile (if it's a station) and it + * will therefore not make a difference. */ + cost += _patches.npf_rail_station_penalty; + } + + #ifdef NPF_MARKROUTE + NPFMarkTile(tile); + #endif + #ifdef NPF_DEBUG + debug("Calculating G for: (%d, %d). Result: %d", TileX(current->tile), TileY(current->tile), cost); + #endif + return cost; +} + +/* Will find any depot */ +int32 NPFFindDepot(AyStar* as, OpenListNode *current) { + TileIndex tile = current->path.node.tile; + bool isDepot; + switch(GetTileType(tile)) { + case MP_RAILWAY: + /* Check if this is a rail depot */ + isDepot = IsTrainDepotTile(tile); + break; + case MP_STREET: + /* Check if this is a road depot */ + isDepot = IsRoadDepotTile(tile); + break; + case MP_WATER: + isDepot = IsShipDepotTile(tile); + break; + default: + isDepot = false; + break; + } + if (isDepot) + return AYSTAR_FOUND_END_NODE; + else + return AYSTAR_DONE; +} + +/* Will find a station identified using the NPFFindStationOrTileData */ +int32 NPFFindStationOrTile(AyStar* as, OpenListNode *current) { + /* If GetNeighbours said we could get here, we assume the station type + * is correct */ + NPFFindStationOrTileData* fstd = (NPFFindStationOrTileData*)as->user_target; + TileIndex tile = current->path.node.tile; + if ( (fstd->station_index == -1 && tile == fstd->dest_coords) || /* We've found the tile, or */ + (IsTileType(tile, MP_STATION) && _map2[tile] == fstd->station_index) /* the station */ + ) + return AYSTAR_FOUND_END_NODE; + else + return AYSTAR_DONE; +} + +/* To be called when current contains the (shortest route to) the target node. + * Will fill the contents of the NPFFoundTargetData using + * AyStarNode[NPF_TRACKDIR_CHOICE]. + */ +void NPFSaveTargetData(AyStar* as, OpenListNode* current) { + NPFFoundTargetData* ftd = (NPFFoundTargetData*)as->user_path; + ftd->best_trackdir = current->path.node.user_data[NPF_TRACKDIR_CHOICE]; + ftd->best_path_dist = current->g; + ftd->best_bird_dist = 0; + ftd->node = current->path.node; +} + +/* Will just follow the results of GetTileTrackStatus concerning where we can + * go and where not. Uses AyStar.user_data[NPF_TYPE] as the transport type and + * an argument to GetTileTrackStatus. Will skip tunnels, meaning that the + * entry and exit are neighbours. Will fill AyStarNode.user_data[NPF_TRACKDIR_CHOICE] with an + * appropriate value, and copy AyStarNode.user_data[NPF_NODE_FLAGS] from the + * parent */ +void NPFFollowTrack(AyStar* aystar, OpenListNode* current) { + byte src_trackdir = current->path.node.direction; + TileIndex src_tile = current->path.node.tile; + byte src_exitdir = _trackdir_to_exitdir[src_trackdir]; + FindLengthOfTunnelResult flotr; + TileIndex dst_tile; + int i = 0; + uint trackdirs, ts; + TransportType type = aystar->user_data[NPF_TYPE]; + /* Initialize to 0, so we can jump out (return) somewhere an have no neighbours */ + aystar->num_neighbours = 0; + #ifdef NPF_DEBUG + debug("Expanding: (%d, %d, %d) [%d]", TileX(src_tile), TileY(src_tile), src_trackdir, src_tile); + #endif + + /* Find dest tile */ + if (IsTileType(src_tile, MP_TUNNELBRIDGE) && (_map5[src_tile] & 0xF0)==0 && (_map5[src_tile] & 3) == src_exitdir) { + /* This is a tunnel. We know this tunnel is our type, + * otherwise we wouldn't have got here. It is also facing us, + * so we should skip it's body */ + flotr = FindLengthOfTunnel(src_tile, src_exitdir); + dst_tile = flotr.tile; + } else { + if ( + (type == TRANSPORT_ROAD && IsRoadStationTile(src_tile)) + || (type == TRANSPORT_ROAD && IsRoadDepotTile(src_tile)) + || (type == TRANSPORT_RAIL && IsTrainDepotTile(src_tile)) + ){ + /* This is a road station or a train or road depot. We can enter and exit + * those from one side only. Trackdirs don't support that (yet), so we'll + * do this here. */ + + byte exitdir; + /* Find out the exit direction first */ + if (IsRoadStationTile(src_tile)) + exitdir = GetRoadStationDir(src_tile); + else /* Train or road depot. Direction is stored the same for both, in map5 */ + exitdir = _map5[src_tile] & 3; /* Extract the direction from the map */ + + /* Let's see if were headed the right way */ + if (src_trackdir != _dir_to_diag_trackdir[exitdir]) + /* Not going out of the station/depot through the exit, but the back. No + * neighbours then. */ + return; + } + /* This a normal tile, a bridge, a tunnel exit, etc. */ + dst_tile = AddTileIndexDiffCWrap(src_tile, TileIndexDiffCByDir(_trackdir_to_exitdir[src_trackdir])); + if (dst_tile == INVALID_TILE) { + /* We reached the border of the map */ + /* TODO Nicer control flow for this */ + return; + } + } + + // TODO: check correct rail type (mono, maglev, etc) + // TODO: check tile owner + + /* Determine available tracks */ + if (type == TRANSPORT_ROAD && (IsRoadStationTile(dst_tile) || IsRoadDepotTile(dst_tile))){ + byte exitdir; + /* Road stations and depots return 0 on GTTS, so we have to do this by hand... */ + if (IsRoadStationTile(dst_tile)) + exitdir = GetRoadStationDir(dst_tile); + else /* Road depot */ + exitdir = _map5[dst_tile] & 3; /* Extract the direction from the map */ + ts = (1 << _dir_to_diag_trackdir[exitdir]) | + (1 << _dir_to_diag_trackdir[_reverse_dir[exitdir]]); + /* Find the trackdirs that are available for a station with this orientation. They are in both directions */ + } else { + ts = GetTileTrackStatus(dst_tile, type); + } + trackdirs = ts & 0x3F3F; /* Filter out signal status and the unused bits */ + + #ifdef NPF_DEBUG + debug("Next node: (%d, %d) [%d], possible trackdirs: %#x", TileX(dst_tile), TileY(dst_tile), dst_tile, trackdirs); + #endif + /* Select only trackdirs we can reach from our current trackdir */ + trackdirs &= _trackdir_reaches_trackdirs[src_trackdir]; + if (_patches.forbid_90_deg && (type == TRANSPORT_RAIL || type == TRANSPORT_WATER)) /* Filter out trackdirs that would make 90 deg turns for trains */ + trackdirs &= ~_trackdir_crosses_trackdirs[src_trackdir]; + #ifdef NPF_DEBUG + debug("After filtering: (%d, %d), possible trackdirs: %#x", TileX(dst_tile), TileY(dst_tile), trackdirs); + #endif + + /* Enumerate possible track */ + while (trackdirs != 0) { + byte dst_trackdir; + dst_trackdir = FindFirstBit2x64(trackdirs); + trackdirs = KillFirstBit2x64(trackdirs); + #ifdef NPF_DEBUG + debug("Expanded into trackdir: %d, remaining trackdirs: %#x", dst_trackdir, trackdirs); + #endif + + /* Check for oneway signal against us */ + if (IsTileType(dst_tile, MP_RAILWAY) && (_map5[dst_tile]&0xC0) == 0x40) { + // the tile has a signal + byte signal_present = _map3_lo[dst_tile]; + if (!(signal_present & _signal_along_trackdir[dst_trackdir])) { + // if one way signal not pointing towards us, stop going in this direction. + if (signal_present & _signal_against_trackdir[dst_trackdir]) + break; + } + } + { + /* We've found ourselves a neighbour :-) */ + AyStarNode* neighbour = &aystar->neighbours[i]; + neighbour->tile = dst_tile; + neighbour->direction = dst_trackdir; + /* Save user data */ + neighbour->user_data[NPF_NODE_FLAGS] = current->path.node.user_data[NPF_NODE_FLAGS]; + NPFFillTrackdirChoice(neighbour, current); + } + i++; + } + aystar->num_neighbours = i; +} + +/* + * Plan a route to the specified target (which is checked by target_proc), + * from start1 and if not NULL, from start2 as well. The type of transport we + * are checking is in type. + * When we are looking for one specific target (optionally multiple tiles), we + * should use a good heuristic to perform aystar search. When we search for + * multiple targets that are spread around, we should perform a breadth first + * search by specifiying CalcZero as our heuristic. + */ +NPFFoundTargetData NPFRouteInternal(AyStarNode* start1, AyStarNode* start2, NPFFindStationOrTileData* target, AyStar_EndNodeCheck target_proc, AyStar_CalculateH heuristic_proc, TransportType type) { + int r; + NPFFoundTargetData result; + + /* Initialize procs */ + _npf_aystar.CalculateH = heuristic_proc; + _npf_aystar.EndNodeCheck = target_proc; + _npf_aystar.FoundEndNode = NPFSaveTargetData; + _npf_aystar.GetNeighbours = NPFFollowTrack; + if (type == TRANSPORT_RAIL) + _npf_aystar.CalculateG = NPFRailPathCost; + else if (type == TRANSPORT_ROAD) + _npf_aystar.CalculateG = NPFRoadPathCost; + else if (type == TRANSPORT_WATER) + _npf_aystar.CalculateG = NPFWaterPathCost; + else + assert(0); + + /* Initialize Start Node(s) */ + start1->user_data[NPF_TRACKDIR_CHOICE] = 0xff; + start1->user_data[NPF_NODE_FLAGS] = 0; + _npf_aystar.addstart(&_npf_aystar, start1); + if (start2) { + start2->user_data[NPF_TRACKDIR_CHOICE] = 0xff; + start2->user_data[NPF_NODE_FLAGS] = NPF_FLAG_REVERSE; + _npf_aystar.addstart(&_npf_aystar, start2); + } + + /* Initialize result */ + result.best_bird_dist = (uint)-1; + result.best_path_dist = (uint)-1; + result.best_trackdir = 0xff; + _npf_aystar.user_path = &result; + + /* Initialize target */ + _npf_aystar.user_target = target; + + /* Initialize user_data */ + _npf_aystar.user_data[NPF_TYPE] = type; + + /* GO! */ + r = AyStarMain_Main(&_npf_aystar); + assert(r != AYSTAR_STILL_BUSY); + + if (result.best_bird_dist != 0) { + if (target) { + DEBUG(misc, 1) ("NPF: Could not find route to 0x%x from 0x%x.", target->dest_coords, start1->tile); + } else { + /* Assumption: target == NULL, so we are looking for a depot */ + DEBUG(misc, 1) ("NPF: Could not find route to a depot from 0x%x.", start1->tile); + } + + } + return result; +} + +NPFFoundTargetData NPFRouteToStationOrTileTwoWay(TileIndex tile1, byte trackdir1, TileIndex tile2, byte trackdir2, NPFFindStationOrTileData* target, TransportType type) { + AyStarNode start1; + AyStarNode start2; + + start1.tile = tile1; + start2.tile = tile2; + start1.direction = trackdir1; + start2.direction = trackdir2; + + return NPFRouteInternal(&start1, &start2, target, NPFFindStationOrTile, NPFCalcStationOrTileHeuristic, type); +} + +NPFFoundTargetData NPFRouteToStationOrTile(TileIndex tile, byte trackdir, NPFFindStationOrTileData* target, TransportType type) { + AyStarNode start; + + assert(tile != 0); + + start.tile = tile; + start.direction = trackdir; + /* We set this in case the target is also the start tile, we will just + * return a not found then */ + start.user_data[NPF_TRACKDIR_CHOICE] = 0xff; + + return NPFRouteInternal(&start, NULL, target, NPFFindStationOrTile, NPFCalcStationOrTileHeuristic, type); +} + +NPFFoundTargetData NPFRouteToDepotBreadthFirst(TileIndex tile, byte trackdir, TransportType type) { + AyStarNode start; + + start.tile = tile; + start.direction = trackdir; + /* We set this in case the target is also the start tile, we will just + * return a not found then */ + start.user_data[NPF_TRACKDIR_CHOICE] = 0xff; + + /* perform a breadth first search. Target is NULL, + * since we are just looking for any depot...*/ + return NPFRouteInternal(&start, NULL, NULL, NPFFindDepot, NPFCalcZero, type); +} + +NPFFoundTargetData NPFRouteToDepotTrialError(TileIndex tile, byte trackdir, TransportType type) { + /* Okay, what we're gonna do. First, we look at all depots, calculate + * the manhatten distance to get to each depot. We then sort them by + * distance. We start by trying to plan a route to the closest, then + * the next closest, etc. We stop when the best route we have found so + * far, is shorter than the manhattan distance. This will obviously + * always find the closest depot. It will probably be most efficient + * for ships, since the heuristic will not be to far off then. I hope. + */ + Queue depots; + uint i; + TileType tiletype = 0; + int r; + NPFFoundTargetData best_result; + NPFFoundTargetData result; + NPFFindStationOrTileData target; + AyStarNode start; + Depot* current; + + + /* This is a little ugly, but it works :-S */ + if (type == TRANSPORT_ROAD) + tiletype = MP_STREET; + else if (type == TRANSPORT_RAIL) + tiletype = MP_RAILWAY; + else if (type == TRANSPORT_WATER) + tiletype = MP_WATER; + else + assert(0); + + init_InsSort(&depots); + /* Okay, let's find all depots that we can use first */ + for (i=0;i<lengthof(_depots);i++) { + int depot_tile = _depots[i].xy; + if (IsTileType(depot_tile, tiletype)) + depots.push(&depots, &_depots[i], DistanceManhattan(tile, depot_tile)); + + } + + /* Now, let's initialise the aystar */ + + /* Initialize procs */ + _npf_aystar.CalculateH = NPFCalcStationOrTileHeuristic; + _npf_aystar.EndNodeCheck = NPFFindStationOrTile; + _npf_aystar.FoundEndNode = NPFSaveTargetData; + _npf_aystar.GetNeighbours = NPFFollowTrack; + if (type == TRANSPORT_RAIL) + _npf_aystar.CalculateG = NPFRailPathCost; + else if (type == TRANSPORT_ROAD) + _npf_aystar.CalculateG = NPFRoadPathCost; + else if (type == TRANSPORT_WATER) + _npf_aystar.CalculateG = NPFWaterPathCost; + else + assert(0); + + /* Initialize target */ + target.station_index = -1; /* We will initialize dest_coords inside the loop below */ + _npf_aystar.user_target = ⌖ + + /* Initialize user_data */ + _npf_aystar.user_data[NPF_TYPE] = type; + + /* Initialize Start Node */ + start.tile = tile; + start.direction = trackdir; /* We will initialize user_data inside the loop below */ + + /* Initialize Result */ + _npf_aystar.user_path = &result; + best_result.best_path_dist = (uint)-1; + + /* Just iterate the depots in order of increasing distance */ + while ((current = depots.pop(&depots))) { + /* Check to see if we already have a path shorter than this + * depot's manhattan distance. Hack: We call DistanceManhattan + * again, we should probably modify the queue to give us that + * value... */ + if ( DistanceManhattan(tile, current->xy * NPF_TILE_LENGTH) > best_result.best_path_dist) + break; + + /* Initialize Start Node */ + /* We set this in case the target is also the start tile, we will just + * return a not found then */ + start.user_data[NPF_TRACKDIR_CHOICE] = 0xff; + start.user_data[NPF_NODE_FLAGS] = 0; + _npf_aystar.addstart(&_npf_aystar, &start); + + /* Initialize result */ + result.best_bird_dist = (uint)-1; + result.best_path_dist = (uint)-1; + result.best_trackdir = 0xff; + + /* Initialize target */ + target.dest_coords = current->xy; + + /* GO! */ + r = AyStarMain_Main(&_npf_aystar); + assert(r != AYSTAR_STILL_BUSY); + + /* This depot is closer */ + if (result.best_path_dist < best_result.best_path_dist) + best_result = result; + } + if (result.best_bird_dist != 0) { + DEBUG(misc, 1) ("NPF: Could not find route to any depot from 0x%x.", tile); + } + return best_result; +} + +void InitializeNPF(void) +{ + init_AyStar(&_npf_aystar, NTPHash, 1024); + _npf_aystar.loops_per_tick = 0; + _npf_aystar.max_path_cost = 0; + _npf_aystar.max_search_nodes = 0; + /* + init_AyStar(&_train_find_station, NTPHash, 1024); + init_AyStar(&_train_find_depot, NTPHash, 1024); + init_AyStar(&_road_find_station, NTPHash, 1024); + init_AyStar(&_road_find_depot, NTPHash, 1024); + + _train_find_station.loops_per_tick = 0; + _train_find_depot.loops_per_tick = 0; + _road_find_station.loops_per_tick = 0; + _road_find_depot.loops_per_tick = 0; + + _train_find_station.max_path_cost = 0; + _train_find_depot.max_path_cost = 0; + _road_find_station.max_path_cost = 0; + _road_find_depot.max_path_cost = 0; + + _train_find_station.max_search_nodes = 0; + _train_find_depot.max_search_nodes = 0; + _road_find_station.max_search_nodes = 0; + _road_find_depot.max_search_nodes = 0; + + _train_find_station.CalculateG = NPFRailPathCost; + _train_find_depot.CalculateG = NPFRailPathCost; + _road_find_station.CalculateG = NPFRoadPathCost; + _road_find_depot.CalculateG = NPFRoadPathCost; + + _train_find_station.CalculateH = NPFCalcStationHeuristic; + _train_find_depot.CalculateH = NPFCalcStationHeuristic; + _road_find_station.CalculateH = NPFCalcStationHeuristic; + _road_find_depot.CalculateH = NPFCalcStationHeuristic; + + _train_find_station.EndNodeCheck = NPFFindStationOrTile; + _train_find_depot.EndNodeCheck = NPFFindStationOrTile; + _road_find_station.EndNodeCheck = NPFFindStationOrTile; + _road_find_depot.EndNodeCheck = NPFFindStationOrTile; + + _train_find_station.FoundEndNode = NPFSaveTargetData; + _train_find_depot.FoundEndNode = NPFSaveTargetData; + _road_find_station.FoundEndNode = NPFSaveTargetData; + _road_find_depot.FoundEndNode = NPFSaveTargetData; + + _train_find_station.GetNeighbours = NPFFollowTrack; + _train_find_depot.GetNeighbours = NPFFollowTrack; + _road_find_station.GetNeighbours = NPFFollowTrack; + _road_find_depot.GetNeighbours = NPFFollowTrack; + */ +} + +void NPFFillWithOrderData(NPFFindStationOrTileData* fstd, Vehicle* v) { + /* Ships don't really reach their stations, but the tile in front. So don't + * save the station id for ships. For roadvehs we don't store it either, + * because multistop depends on vehicles actually reaching the exact + * dest_tile, not just any stop of that station. + * So only for train orders to stations we fill fstd->station_index, for all + * others only dest_coords */ + if ((v->current_order.type) == OT_GOTO_STATION && v->type == VEH_Train) { + fstd->station_index = v->current_order.station; + /* Let's take the center of the station as our target tile for trains */ + Station* st = GetStation(v->current_order.station); + TileIndexDiffC center = {st->trainst_w/2, st->trainst_h/2}; + fstd->dest_coords = TILE_ADD(st->train_tile, ToTileIndexDiff(center)); + } else { + fstd->dest_coords = v->dest_tile; + fstd->station_index = -1; + } +} @@ -0,0 +1,128 @@ +#ifndef NPF_H +#define NPF_H + +#include "ttd.h" +#include "aystar.h" +#include "vehicle.h" + +//#define NPF_DEBUG +//#define NPF_MARKROUTE //Mark the routes considered by the pathfinder by +//mowing grass + +typedef struct NPFFindStationOrTileData { /* Meant to be stored in AyStar.targetdata */ + TileIndex dest_coords; /* An indication of where the station is, for heuristic purposes, or the target tile */ + int station_index; /* station index we're heading for, or -1 when we're heading for a tile */ +} NPFFindStationOrTileData; + +enum { /* Indices into AyStar.userdata[] */ + NPF_TYPE = 0, /* Contains an TransportTypes value */ +}; + +enum { /* Indices into AyStarNode.userdata[] */ + NPF_TRACKDIR_CHOICE = 0, /* The trackdir chosen to get here */ + NPF_NODE_FLAGS, +}; +enum { /* Flags for AyStarNode.userdata[NPF_NODE_FLAGS]*/ + NPF_FLAG_SEEN_SIGNAL = 1, /* Used to mark that a signal was seen on the way, for rail only */ + NPF_FLAG_REVERSE = 2, /* Used to mark that this node was reached from the second start node, if applicable */ +}; + +typedef struct NPFFoundTargetData { /* Meant to be stored in AyStar.userpath */ + uint best_bird_dist; /* The best heuristic found. Is 0 if the target was found */ + uint best_path_dist; /* The shortest path. Is (uint)-1 if no path is found */ + byte best_trackdir; /* The trackdir that leads to the shortes path/closest birds dist */ + AyStarNode node; /* The node within the target the search led us to */ +} NPFFoundTargetData; + +/* These functions below are _not_ re-entrant, in favor of speed! */ + +/* Will search from the given tile and direction, for a route to the given + * station for the given transport type. See the declaration of + * NPFFoundTargetData above for the meaning of the result. */ +NPFFoundTargetData NPFRouteToStationOrTile(TileIndex tile, byte trackdir, NPFFindStationOrTileData* target, TransportType type); +/* Will search as above, but with two start nodes, the second being the + * reverse. Look at the NPF_NODE_REVERSE flag in the result node to see which + * direction was taken */ +NPFFoundTargetData NPFRouteToStationOrTileTwoWay(TileIndex tile1, byte trackdir1, TileIndex tile2, byte trackdir2, NPFFindStationOrTileData* target, TransportType type); + +/* Will search a route to the closest depot. */ + +/* Search using breadth first. Good for little track choice and inaccurate + * heuristic, such as railway/road */ +NPFFoundTargetData NPFRouteToDepotBreadthFirst(TileIndex tile, byte trackdir, TransportType type); +/* Search by trying each depot in order of Manhattan Distance. Good for lots + * of choices and accurate heuristics, such as water */ +NPFFoundTargetData NPFRouteToDepotTrialError(TileIndex tile, byte trackdir, TransportType type); + +void NPFFillWithOrderData(NPFFindStationOrTileData* fstd, Vehicle* v); + +/* + * Some tables considering tracks, directions and signals. + * XXX: Better place to but these? + */ + +/** + * Maps a trackdir to the bit that stores its status in the map arrays, in the + * direction along with the trackdir. + */ +const byte _signal_along_trackdir[14]; + +/** + * Maps a trackdir to the bit that stores its status in the map arrays, in the + * direction against the trackdir. + */ +const byte _signal_against_trackdir[14]; + +/** + * Maps a trackdir to the trackdirs that can be reached from it (ie, when + * entering the next tile. + */ +const uint16 _trackdir_reaches_trackdirs[14]; + +/** + * Maps a trackdir to all trackdirs that make 90 deg turns with it. + */ +const uint16 _trackdir_crosses_trackdirs[14]; + +/** + * Maps a track to all tracks that make 90 deg turns with it. + */ +const byte _track_crosses_tracks[6]; + +/** + * Maps a trackdir to the (4-way) direction the tile is exited when following + * that trackdir. + */ +const byte _trackdir_to_exitdir[14]; + +/** + * Maps a track and an (4-way) dir to the trackdir that represents the track + * with the exit in the given direction. + */ +const byte _track_exitdir_to_trackdir[6][4]; + +/** + * Maps a track and a full (8-way) direction to the trackdir that represents + * the track running in the given direction. + */ +const byte _track_direction_to_trackdir[6][8]; + +/** + * Maps a (4-way) direction to the diagonal track that runs in that + * direction. + */ +const byte _dir_to_diag_trackdir[4]; + +/** + * Maps a (4-way) direction to the reverse. + */ +const byte _reverse_dir[4]; + +/** + * Maps a trackdir to the reverse trackdir. + */ +const byte _reverse_trackdir[14]; + +#define REVERSE_TRACKDIR(trackdir) (trackdir ^ 0x8) + +#endif // NPF_H diff --git a/order_cmd.c b/order_cmd.c index 809bed18b..fe9f22e23 100644 --- a/order_cmd.c +++ b/order_cmd.c @@ -136,9 +136,11 @@ int32 CmdInsertOrder(int x, int y, uint32 flags, uint32 veh_sel, uint32 packed_o if (v->num_orders >= 40) return_cmd_error(STR_8832_TOO_MANY_ORDERS); - /* For ships, make sure that the station is not too far away from the previous destination. */ + /* For ships, make sure that the station is not too far away from the + * previous destination, for human players with new pathfinding disabled */ if (v->type == VEH_Ship && IS_HUMAN_PLAYER(v->owner) && - sel != 0 && GetVehicleOrder(v, sel - 1)->type == OT_GOTO_STATION) { + sel != 0 && GetVehicleOrder(v, sel - 1)->type == OT_GOTO_STATION + && !_patches.new_pathfinding_all) { int dist = DistanceManhattan( GetStation(GetVehicleOrder(v, sel - 1)->station)->xy, diff --git a/pathfind.h b/pathfind.h index ea9038ea3..3ed755b9a 100644 --- a/pathfind.h +++ b/pathfind.h @@ -1,6 +1,9 @@ #ifndef PATHFIND_H #define PATHFIND_H +//#define PF_BENCH // perform simple benchmarks on the train pathfinder (not +//supported on all archs) + typedef struct TrackPathFinder TrackPathFinder; typedef bool TPFEnumProc(uint tile, void *data, int track, uint length, byte *state); typedef void TPFAfterProc(TrackPathFinder *tpf); @@ -420,7 +420,7 @@ void init_BinaryHeap(Queue* q, uint max_size) q->data.binaryheap.size = 0; // We malloc memory in block of BINARY_HEAP_BLOCKSIZE // It autosizes when it runs out of memory - q->data.binaryheap.elements = calloc(1, ((max_size - 1) / BINARY_HEAP_BLOCKSIZE) + 1); + q->data.binaryheap.elements = calloc(1, ((max_size - 1) / BINARY_HEAP_BLOCKSIZE*sizeof(BinaryHeapNode)) + 1); q->data.binaryheap.elements[0] = malloc(BINARY_HEAP_BLOCKSIZE * sizeof(BinaryHeapNode)); q->data.binaryheap.blocks = 1; q->freeq = false; diff --git a/rail_cmd.c b/rail_cmd.c index 409884497..20827b0fb 100644 --- a/rail_cmd.c +++ b/rail_cmd.c @@ -2168,7 +2168,6 @@ static uint32 GetTileTrackStatus_Track(uint tile, TransportType mode) { ret = (m5 << 8) + m5; } else return 0; - return ret; } diff --git a/road_cmd.c b/road_cmd.c index cb5133b51..c74c7c931 100644 --- a/road_cmd.c +++ b/road_cmd.c @@ -9,7 +9,7 @@ #include "player.h" #include "town.h" #include "gfx.h" -#include "table/directions.h" +#include "npf.h" #include "sound.h" /* When true, GetTrackStatus for roads will treat roads under reconstruction diff --git a/roadveh_cmd.c b/roadveh_cmd.c index 2297f6ab2..9ee7d2bf3 100644 --- a/roadveh_cmd.c +++ b/roadveh_cmd.c @@ -10,6 +10,7 @@ #include "news.h" #include "gfx.h" #include "pathfind.h" +#include "npf.h" #include "player.h" #include "sound.h" @@ -287,21 +288,33 @@ static int FindClosestRoadDepot(Vehicle *v) { uint tile = v->tile; int i; - RoadFindDepotData rfdd; if (v->u.road.state == 255) { tile = GetVehicleOutOfTunnelTile(v); } - rfdd.owner = v->owner; - rfdd.best_length = (uint)-1; + if (_patches.new_pathfinding_all) { + NPFFoundTargetData ftd; + /* See where we are now */ + byte trackdir = _dir_to_diag_trackdir[(v->direction>>1)&3]; + ftd = NPFRouteToDepotBreadthFirst(v->tile, trackdir, TRANSPORT_ROAD); + if (ftd.best_bird_dist == 0) + return GetDepotByTile(ftd.node.tile); /* Target found */ + else + return -1; /* Target not found */ + /* We do not search in two directions here, why should we? We can't reverse right now can we? */ + } else { + RoadFindDepotData rfdd; + rfdd.owner = v->owner; + rfdd.best_length = (uint)-1; - /* search in all directions */ - for(i=0; i!=4; i++) - FollowTrack(tile, 0x2000 | TRANSPORT_ROAD, i, (TPFEnumProc*)EnumRoadSignalFindDepot, NULL, &rfdd); + /* search in all directions */ + for(i=0; i!=4; i++) + FollowTrack(tile, 0x2000 | TRANSPORT_ROAD, i, (TPFEnumProc*)EnumRoadSignalFindDepot, NULL, &rfdd); - if (rfdd.best_length == (uint)-1) - return -1; + if (rfdd.best_length == (uint)-1) + return -1; - return GetDepotByTile(rfdd.tile); + return GetDepotByTile(rfdd.tile); + } } /* Send a road vehicle to the nearest depot @@ -1011,7 +1024,7 @@ static bool EnumRoadTrackFindDist(uint tile, FindRoadToChooseData *frd, int trac // Returns direction to choose // or -1 if the direction is currently blocked -static int RoadFindPathToDest(Vehicle *v, uint tile, int direction) +static int RoadFindPathToDest(Vehicle *v, uint tile, int enterdir) { #define return_track(x) {best_track = x; goto found_best_track; } @@ -1055,66 +1068,95 @@ static int RoadFindPathToDest(Vehicle *v, uint tile, int direction) */ /* remove unreachable tracks */ - bitmask &= _road_veh_fp_ax_and[direction]; + bitmask &= _road_veh_fp_ax_and[enterdir]; if (bitmask == 0) { - // reverse - return_track(_road_reverse_table[direction]); + /* No reachable tracks, so we'll reverse */ + return_track(_road_reverse_table[enterdir]); } if (v->u.road.reverse_ctr != 0) { + /* What happens here?? */ v->u.road.reverse_ctr = 0; if (v->tile != (TileIndex)tile) { - return_track(_road_reverse_table[direction]); + return_track(_road_reverse_table[enterdir]); } } desttile = v->dest_tile; if (desttile == 0) { - // Pick a random direction + // Pick a random track return_track(PickRandomBit(bitmask)); } - // Only one direction to choose between? - if (!(bitmask & (bitmask - 1))) { + // Only one track to choose between? + if (!(KillFirstBit2x64(bitmask))) { return_track(FindFirstBit2x64(bitmask)); } - if (IsTileType(desttile, MP_STREET)) { - m5 = _map5[desttile]; - if ((m5&0xF0) == 0x20) - goto do_it; - } else if (IsTileType(desttile, MP_STATION)) { - m5 = _map5[desttile]; - if (IS_BYTE_INSIDE(m5, 0x43, 0x4B)) { - m5 -= 0x43; + if (_patches.new_pathfinding_all) { + NPFFindStationOrTileData fstd; + NPFFoundTargetData ftd; + byte trackdir; + + NPFFillWithOrderData(&fstd, v); + trackdir = _dir_to_diag_trackdir[enterdir]; + //debug("Finding path. Enterdir: %d, Trackdir: %d", enterdir, trackdir); + + ftd = NPFRouteToStationOrTile(tile - TileOffsByDir(enterdir), trackdir, &fstd, TRANSPORT_ROAD); + if (ftd.best_bird_dist != 0 || ftd.best_trackdir == 0xff) { + /* Not found, just do something, or we are already there */ + //TODO: maybe display error? + //TODO: go straight ahead if possible? + return_track(FindFirstBit2x64(bitmask)); + } else { + return_track(ftd.best_trackdir); + } + } else { + if (IsTileType(desttile, MP_STREET)) { + m5 = _map5[desttile]; + if ((m5&0xF0) == 0x20) + /* We are heading for a Depot */ + goto do_it; + } else if (IsTileType(desttile, MP_STATION)) { + m5 = _map5[desttile]; + if (IS_BYTE_INSIDE(m5, 0x43, 0x4B)) { + /* We are heading for a station */ + m5 -= 0x43; do_it:; - desttile += TileOffsByDir(m5 & 3); - if (desttile == tile && bitmask&_road_pf_table_3[m5&3]) { - return_track(FindFirstBit2x64(bitmask&_road_pf_table_3[m5&3])); + /* When we are heading for a depot or station, we just + * pretend we are heading for the tile in front, we'll + * see from there */ + desttile += TileOffsByDir(m5 & 3); + if (desttile == tile && bitmask&_road_pf_table_3[m5&3]) { + /* If we are already in front of the + * station/depot and we can get in from here, + * we enter */ + return_track(FindFirstBit2x64(bitmask&_road_pf_table_3[m5&3])); + } } } - } - // do pathfind - frd.dest = desttile; - - best_track = -1; - best_dist = (uint)-1; - best_maxlen = (uint)-1; - i = 0; - do { - if (bitmask & 1) { - if (best_track == -1) best_track = i; // in case we don't find the path, just pick a direction - frd.maxtracklen = (uint)-1; - frd.mindist = (uint)-1; - FollowTrack(tile, 0x3000 | TRANSPORT_ROAD, _road_pf_directions[i], (TPFEnumProc*)EnumRoadTrackFindDist, NULL, &frd); - - if (frd.mindist < best_dist || (frd.mindist==best_dist && frd.maxtracklen < best_maxlen)) { - best_dist = frd.mindist; - best_maxlen = frd.maxtracklen; - best_track = i; + // do pathfind + frd.dest = desttile; + + best_track = -1; + best_dist = (uint)-1; + best_maxlen = (uint)-1; + i = 0; + do { + if (bitmask & 1) { + if (best_track == -1) best_track = i; // in case we don't find the path, just pick a track + frd.maxtracklen = (uint)-1; + frd.mindist = (uint)-1; + FollowTrack(tile, 0x3000 | TRANSPORT_ROAD, _road_pf_directions[i], (TPFEnumProc*)EnumRoadTrackFindDist, NULL, &frd); + + if (frd.mindist < best_dist || (frd.mindist==best_dist && frd.maxtracklen < best_maxlen)) { + best_dist = frd.mindist; + best_maxlen = frd.maxtracklen; + best_track = i; + } } - } - } while (++i,(bitmask>>=1) != 0); + } while (++i,(bitmask>>=1) != 0); + } found_best_track:; @@ -1301,6 +1343,7 @@ static void RoadVehEventHandler(Vehicle *v) again: if ((dir & 7) >= 6) { + /* Turning around */ tile = v->tile; } diff --git a/settings.c b/settings.c index 3d0d8f87f..f67090732 100644 --- a/settings.c +++ b/settings.c @@ -823,6 +823,33 @@ static const SettingDesc patch_player_settings[] = { {"window_snap_radius", SDT_UINT8, (void*)10, &_patches.window_snap_radius, NULL}, + /* New Path Finding */ + {"new_pathfinding_all", SDT_BOOL, (void*)false, &_patches.new_pathfinding_all, NULL}, + + /* When a red signal is encountered, a small detour can be made around + * it. This specifically occurs when a track is doubled, in which case + * the detour is typically 2 tiles. It is also often used at station + * entrances, when there is a choice of multiple platforms. If we take + * a typical 4 platform station, the detour is 4 tiles. To properly + * support larger stations we increase this value. + * We want to prevent that trains that want to leave at one side of a + * station, leave through the other side, turn around, enter the + * station on another platform and exit the station on the right side + * again, just because the sign at the right side was red. If we take + * a typical 5 length station, this detour is 10 or 11 tiles (not + * sure), so we set the default penalty at 10 (the station tile + * penalty will further prevent this */ + {"npf_rail_firstred_penalty", SDT_UINT32, (void*)(10 * NPF_TILE_LENGTH), &_patches.npf_rail_firstred_penalty, NULL}, + /* When a train plans a route over a station tile, this penalty is + * applied. We want that trains plan a route around a typical, 4x5 + * station, which means two tiles to the right, and two tiles back to + * the left around it, or 5 tiles of station through it. If we assign + * a penalty of 1 tile for every station tile passed, the route will + * be around it. + */ + {"npf_rail_station_penalty", SDT_UINT32, (void*)(1 * NPF_TILE_LENGTH), &_patches.npf_rail_station_penalty, NULL}, + {"npf_rail_slope_penalty", SDT_UINT32, (void*)(1 * NPF_TILE_LENGTH), &_patches.npf_rail_slope_penalty, NULL}, + {"autorenew", SDT_BOOL, (void*)false, &_patches.autorenew, NULL}, {"autorenew_months", SDT_INT16, (void*)-6, &_patches.autorenew_months, NULL}, {"autorenew_money", SDT_INT32, (void*)100000,&_patches.autorenew_money, NULL}, @@ -864,6 +891,7 @@ const SettingDesc patch_settings[] = { {"nonuniform_stations", SDT_BOOL, (void*)true, &_patches.nonuniform_stations, NULL}, {"always_small_airport",SDT_BOOL, (void*)false, &_patches.always_small_airport, NULL}, {"realistic_acceleration",SDT_BOOL, (void*)false, &_patches.realistic_acceleration, NULL}, + {"forbid_90_deg", SDT_BOOL, (void*)false, &_patches.forbid_90_deg, NULL}, {"improved_load", SDT_BOOL, (void*)false, &_patches.improved_load, NULL}, {"max_trains", SDT_UINT8, (void*)80, &_patches.max_trains, NULL}, diff --git a/settings_gui.c b/settings_gui.c index 515141206..de224a2c2 100644 --- a/settings_gui.c +++ b/settings_gui.c @@ -640,11 +640,13 @@ static const PatchEntry _patches_construction[] = { static const PatchEntry _patches_vehicles[] = { {PE_BOOL, 0, STR_CONFIG_PATCHES_REALISTICACCEL, "realistic_acceleration", &_patches.realistic_acceleration, 0, 0, 0, NULL}, - {PE_BOOL, 0, STR_CONFIG_PATCHES_MAMMOTHTRAINS, "mammoth_trains", &_patches.mammoth_trains, 0, 0, 0, NULL}, - {PE_BOOL, 0, STR_CONFIG_PATCHES_GOTODEPOT, "goto_depot", &_patches.gotodepot, 0, 0, 0, NULL}, - {PE_BOOL, 0, STR_CONFIG_PATCHES_ROADVEH_QUEUE, "roadveh_queue", &_patches.roadveh_queue, 0, 0, 0, NULL}, - {PE_BOOL, 0, STR_CONFIG_PATCHES_NEW_DEPOT_FINDING,"depot_finding", &_patches.new_depot_finding, 0, 0, 0, NULL}, + {PE_BOOL, 0, STR_CONFIG_PATCHES_FORBID_90_DEG, "forbid_90_deg", &_patches.forbid_90_deg, 0, 0, 0, NULL}, + {PE_BOOL, 0, STR_CONFIG_PATCHES_MAMMOTHTRAINS, "mammoth_trains", &_patches.mammoth_trains, 0, 0, 0, NULL}, + {PE_BOOL, 0, STR_CONFIG_PATCHES_GOTODEPOT, "goto_depot", &_patches.gotodepot, 0, 0, 0, NULL}, + {PE_BOOL, 0, STR_CONFIG_PATCHES_ROADVEH_QUEUE, "roadveh_queue", &_patches.roadveh_queue, 0, 0, 0, NULL}, + {PE_BOOL, 0, STR_CONFIG_PATCHES_NEW_DEPOT_FINDING,"depot_finding", &_patches.new_depot_finding, 0, 0, 0, NULL}, {PE_BOOL, 0, STR_CONFIG_PATCHES_NEW_TRAIN_PATHFIND,"new_pathfinding", &_patches.new_pathfinding, 0, 0, 0, NULL}, + {PE_BOOL, 0, STR_CONFIG_PATCHES_NEW_PATHFINDING_ALL, "new_pathfinding_all", &_patches.new_pathfinding_all, 0, 0, 0, NULL}, {PE_BOOL, PF_PLAYERBASED, STR_CONFIG_PATCHES_WARN_INCOME_LESS, "train_income_warn", &_patches.train_income_warn, 0, 0, 0, NULL}, {PE_UINT8, PF_MULTISTRING | PF_PLAYERBASED, STR_CONFIG_PATCHES_ORDER_REVIEW, "order_review_system", &_patches.order_review_system,0,2, 1, NULL}, diff --git a/ship_cmd.c b/ship_cmd.c index 238a0b43e..bad598136 100644 --- a/ship_cmd.c +++ b/ship_cmd.c @@ -13,6 +13,7 @@ #include "gui.h" #include "player.h" #include "sound.h" +#include "npf.h" static const uint16 _ship_sprites[] = {0x0E5D, 0x0E55, 0x0E65, 0x0E6D}; static const byte _ship_sometracks[4] = {0x19, 0x16, 0x25, 0x2A}; @@ -70,17 +71,26 @@ static int FindClosestShipDepot(Vehicle *v) byte owner = v->owner; uint tile2 = v->tile; - for(i=0; i!=lengthof(_depots); i++) { - tile = _depots[i].xy; - if (IsTileType(tile, MP_WATER) && _map_owner[tile] == owner) { - dist = DistanceManhattan(tile, tile2); - if (dist < best_dist) { - best_dist = dist; - best_depot = i; + if (_patches.new_pathfinding_all) { + NPFFoundTargetData ftd; + byte trackdir = _track_direction_to_trackdir[FIND_FIRST_BIT(v->u.ship.state)][v->direction]; + ftd = NPFRouteToDepotTrialError(v->tile, trackdir, TRANSPORT_ROAD); + if (ftd.best_bird_dist == 0) + best_depot = ftd.node.tile; /* Found target */ + else + best_depot = -1; /* Did not find target */ + } else { + for(i=0; i!=lengthof(_depots); i++) { + tile = _depots[i].xy; + if (IsTileType(tile, MP_WATER) && _map_owner[tile] == owner) { + dist = DistanceManhattan(tile, tile2); + if (dist < best_dist) { + best_dist = dist; + best_depot = i; + } } } } - return best_depot; } @@ -568,27 +578,55 @@ bad:; return best_bird_dist; } -static int ChooseShipTrack(Vehicle *v, uint tile, int dir, uint tracks) +/* returns the track to choose on the next tile, or -1 when it's better to + * reverse. The tile given is the tile we are about to enter, enterdir is the + * direction in which we are entering the tile */ +static int ChooseShipTrack(Vehicle *v, uint tile, int enterdir, uint tracks) { - uint b; - uint tot_dist, dist; - int track; - uint tile2; - - assert(dir>=0 && dir<=3); - tile2 = TILE_ADD(tile, -TileOffsByDir(dir)); - dir ^= 2; - tot_dist = (uint)-1; - b = GetTileShipTrackStatus(tile2) & _ship_sometracks[dir] & v->u.ship.state; - if (b != 0) { - dist = FindShipTrack(v, tile2, dir, b, tile, &track); - if (dist != (uint)-1) - tot_dist = dist + 1; + assert(enterdir>=0 && enterdir<=3); + + if (_patches.new_pathfinding_all) { + NPFFindStationOrTileData fstd; + NPFFoundTargetData ftd; + uint src_tile = TILE_ADD(tile, TileOffsByDir(_reverse_dir[enterdir])); + byte track = FIND_FIRST_BIT(v->u.ship.state); + assert (KILL_FIRST_BIT(v->u.ship.state) == 0); /* Check that only one bit is set in state */ + assert (v->u.ship.state != 0x80); /* Check that we are not in a depot */ + assert (track < 6); + + NPFFillWithOrderData(&fstd, v); + + ftd = NPFRouteToStationOrTile(src_tile, _track_direction_to_trackdir[track][v->direction], &fstd, TRANSPORT_WATER); + + if (ftd.best_bird_dist == 0 && ftd.best_trackdir != 0xff) + /* Found the target, and it is not our current tile */ + return ftd.best_trackdir & 7; /* TODO: Wrapper function? */ + else + return -1; /* Couldn't find target, reverse */ + /* TODO: When the target is unreachable, the ship will keep reversing */ + } else { + uint b; + uint tot_dist, dist; + int track; + uint tile2; + + tile2 = TILE_ADD(tile, -TileOffsByDir(enterdir)); + tot_dist = (uint)-1; + + /* Let's find out how far it would be if we would reverse first */ + b = GetTileShipTrackStatus(tile2) & _ship_sometracks[_reverse_dir[enterdir]] & v->u.ship.state; + if (b != 0) { + dist = FindShipTrack(v, tile2, _reverse_dir[enterdir], b, tile, &track); + if (dist != (uint)-1) + tot_dist = dist + 1; + } + /* And if we would not reverse? */ + dist = FindShipTrack(v, tile, enterdir, tracks, 0, &track); + if (dist > tot_dist) + /* We could better reverse */ + return -1; + return track; } - dist = FindShipTrack(v, tile, dir^2, tracks, 0, &track); - if (dist > tot_dist) - return -1; - return track; } static const byte _new_vehicle_direction_table[11] = { @@ -2,6 +2,7 @@ #define STATION_H #include "sprite.h" +#include "tile.h" #include "vehicle.h" typedef struct GoodsEntry { @@ -224,4 +225,19 @@ uint GetNumRoadStops(const Station *st, RoadStopType type); RoadStop * GetPrimaryRoadStop(const Station *st, RoadStopType type); RoadStop * GetFirstFreeRoadStop( void ); +static inline bool IsTrainStationTile(uint tile) { + return IsTileType(tile, MP_STATION) && IS_BYTE_INSIDE(_map5[tile], 0, 8); +} + +static inline bool IsRoadStationTile(uint tile) { + return IsTileType(tile, MP_STATION) && IS_BYTE_INSIDE(_map5[tile], 0x43, 0x4B); +} + +/* Get's the direction the station exit points towards. Ie, returns 0 for a + * station with the exit NE. */ +static inline byte GetRoadStationDir(uint tile) { + assert(IsRoadStationTile(tile)); + return (_map5[tile] - 0x43) & 3; +} + #endif /* STATION_H */ diff --git a/station_cmd.c b/station_cmd.c index c5a1475cc..98fe79fe6 100644 --- a/station_cmd.c +++ b/station_cmd.c @@ -16,7 +16,7 @@ #include "player.h" #include "airport.h" #include "sprite.h" -#include "table/directions.h" +#include "npf.h" // FIXME -- need to be embedded into Airport variable. Is dynamically // deducteable from graphics-tile array, so will not be needed @@ -2277,10 +2277,6 @@ static void ClickTile_Station(uint tile) } } -static inline bool IsTrainStationTile(uint tile) { - return IsTileType(tile, MP_STATION) && IS_BYTE_INSIDE(_map5[tile], 0, 8); -} - static const byte _enter_station_speedtable[12] = { 215, 195, 175, 155, 135, 115, 95, 75, 55, 35, 15, 0 }; diff --git a/table/directions.h b/table/directions.h deleted file mode 100644 index c25468cfe..000000000 --- a/table/directions.h +++ /dev/null @@ -1,8 +0,0 @@ -static const byte _dir_to_straight_trackdir[4] = { - 0, 1, 8, 9, -}; - -static const byte _reverse_dir[4] = { -// 3, 0, 1, 2 - 2, 3, 0, 1 -}; diff --git a/train_cmd.c b/train_cmd.c index 2cbadb142..d9473be93 100644 --- a/train_cmd.c +++ b/train_cmd.c @@ -6,6 +6,7 @@ #include "vehicle.h" #include "command.h" #include "pathfind.h" +#include "npf.h" #include "station.h" #include "table/train_cmd.h" #include "gfx.h" @@ -25,16 +26,9 @@ static const byte _vehicle_initial_x_fract[4] = {10,8,4,8}; static const byte _vehicle_initial_y_fract[4] = {8,4,8,10}; static const byte _state_dir_table[4] = { 0x20, 8, 0x10, 4 }; -static const byte _signal_onedir[14] = { - 0x80, 0x80, 0x80, 0x20, 0x40, 0x10, 0, 0, - 0x40, 0x40, 0x40, 0x10, 0x80, 0x20 -}; - -static const byte _signal_otherdir[14] = { - 0x40, 0x40, 0x40, 0x10, 0x80, 0x20, 0, 0, - 0x80, 0x80, 0x80, 0x20, 0x40, 0x10 -}; +/* These two arrays are used for realistic acceleration. XXX: How should they + * be interpreted? */ static const byte _curve_neighbours45[8][2] = { {7, 1}, {0, 2}, @@ -1301,7 +1295,7 @@ static bool TrainFindDepotEnumProc(uint tile, TrainFindDepotData *tfdd, int trac // make sure the train doesn't run against a oneway signal if ((_map5[tile] & 0xC0) == 0x40) { - if (!(_map3_lo[tile] & _signal_onedir[track]) && _map3_lo[tile] & _signal_otherdir[track]) + if (!(_map3_lo[tile] & _signal_along_trackdir[track]) && _map3_lo[tile] & _signal_against_trackdir[track]) return true; } } @@ -1328,7 +1322,16 @@ static TrainFindDepotData FindClosestTrainDepot(Vehicle *v) if (v->u.rail.track == 0x40) { tile = GetVehicleOutOfTunnelTile(v); } - if (!_patches.new_depot_finding) { + if (_patches.new_pathfinding_all) { + NPFFoundTargetData ftd; + byte trackdir = _track_direction_to_trackdir[FIND_FIRST_BIT(v->u.rail.track)][v->direction]; + ftd = NPFRouteToDepotBreadthFirst(v->tile, trackdir, TRANSPORT_RAIL); + if (ftd.best_bird_dist == 0) { + /* Found target */ + tfdd.tile = ftd.node.tile; + tfdd.best_length = ftd.best_path_dist; + } + } else if (!_patches.new_depot_finding) { // search in all directions for(i=0; i!=4; i++) NewTrainPathfind(tile, i, (TPFEnumProc*)TrainFindDepotEnumProc, &tfdd, NULL); @@ -1547,6 +1550,7 @@ static bool CheckTrainStayInDepot(Vehicle *v) return false; } +/* Check for station tiles */ typedef struct TrainTrackFollowerData { TileIndex dest_coords; int station_index; // station index we're heading for @@ -1559,14 +1563,14 @@ static bool TrainTrackFollower(uint tile, TrainTrackFollowerData *ttfd, int trac if (IsTileType(tile, MP_RAILWAY) && (_map5[tile]&0xC0) == 0x40) { // the tile has a signal byte m3 = _map3_lo[tile]; - if (!(m3 & _signal_onedir[track])) { + if (!(m3 & _signal_along_trackdir[track])) { // if one way signal not pointing towards us, stop going in this direction. - if (m3 & _signal_otherdir[track]) + if (m3 & _signal_against_trackdir[track]) return true; - } else if (_map2[tile] & _signal_onedir[track]) { + } else if (_map2[tile] & _signal_along_trackdir[track]) { // green signal in our direction. either one way or two way. *state = true; - } else if (m3 & _signal_otherdir[track]) { + } else if (m3 & _signal_against_trackdir[track]) { // two way signal. unless we passed another green signal on the way, // stop going in this direction. if (!*state) return true; @@ -1643,97 +1647,132 @@ static const byte _search_directions[6][4] = { }; static const byte _pick_track_table[6] = {1, 3, 2, 2, 0, 0}; +#if PF_BENCHMARK +unsigned int rdtsc() +{ + unsigned int high, low; + + __asm__ __volatile__ ("rdtsc" : "=a" (low), "=d" (high)); + return low; +} +#endif + /* choose a track */ -static byte ChooseTrainTrack(Vehicle *v, uint tile, int direction, byte trackbits) +static byte ChooseTrainTrack(Vehicle *v, uint tile, int enterdir, byte trackbits) { TrainTrackFollowerData fd; int bits = trackbits; uint best_track; -#if 0 +#if PF_BENCHMARK int time = rdtsc(); static float f; #endif assert( (bits & ~0x3F) == 0); - /* quick return in case only one possible direction is available */ + /* quick return in case only one possible track is available */ if (KILL_FIRST_BIT(bits) == 0) return FIND_FIRST_BIT(bits); - FillWithStationData(&fd, v); - - if (_patches.new_pathfinding) { - fd.best_bird_dist = (uint)-1; - fd.best_track_dist = (uint)-1; - fd.best_track = 0xFF; - NewTrainPathfind(tile - TileOffsByDir(direction), direction, (TPFEnumProc*)TrainTrackFollower, &fd, NULL); - -// printf("Train %d %s\n", v->unitnumber, fd.best_track_dist == -1 ? "NOTFOUND" : "FOUND"); - - if (fd.best_track == 0xff) { - // blaha + if (_patches.new_pathfinding_all) { /* Use a new pathfinding for everything */ + NPFFindStationOrTileData fstd; + NPFFoundTargetData ftd; + byte trackdir; + + NPFFillWithOrderData(&fstd, v); + /* The enterdir for the new tile, is the exitdir for the old tile */ + trackdir = _track_exitdir_to_trackdir[FIND_FIRST_BIT(v->u.rail.track)][enterdir]; + assert(trackdir != 0xff); + + ftd = NPFRouteToStationOrTile(tile - TileOffsByDir(enterdir), trackdir, &fstd, TRANSPORT_RAIL); + if (ftd.best_bird_dist != 0 || ftd.best_trackdir == 0xff) { + /* Not found, or we are already there. Just do something */ + //TODO: maybe display error? + //TODO: go straight ahead if possible? best_track = FIND_FIRST_BIT(bits); } else { - best_track = fd.best_track & 7; + /* Discard enterdir information, making it a normal track */ + best_track = ftd.best_trackdir & 7; /* TODO: Wrapper function? */ } } else { - int i, r; - uint best_bird_dist = 0; - uint best_track_dist = 0; - byte train_dir = v->direction & 3; - - - best_track = -1; - do { - i = FIND_FIRST_BIT(bits); - bits = KILL_FIRST_BIT(bits); + FillWithStationData(&fd, v); + if (_patches.new_pathfinding) { + /* New train pathfinding */ fd.best_bird_dist = (uint)-1; fd.best_track_dist = (uint)-1; + fd.best_track = 0xFF; + NewTrainPathfind(tile - TileOffsByDir(enterdir), enterdir, (TPFEnumProc*)TrainTrackFollower, &fd, NULL); - NewTrainPathfind(tile, _search_directions[i][direction], (TPFEnumProc*)TrainTrackFollower, &fd, NULL); - if (best_track != (uint)-1) { - if (best_track_dist == (uint)-1) { - if (fd.best_track_dist == (uint)-1) { - /* neither reached the destination, pick the one with the smallest bird dist */ - if (fd.best_bird_dist > best_bird_dist) goto bad; - if (fd.best_bird_dist < best_bird_dist) goto good; - } else { - /* we found the destination for the first time */ - goto good; - } - } else { - if (fd.best_track_dist == (uint)-1) { - /* didn't find destination, but we've found the destination previously */ - goto bad; + // printf("Train %d %s\n", v->unitnumber, fd.best_track_dist == -1 ? "NOTFOUND" : "FOUND"); + + if (fd.best_track == 0xff) { + // blaha + best_track = FIND_FIRST_BIT(bits); + } else { + best_track = fd.best_track & 7; + } + } else { + /* Original pathfinding */ + int i, r; + uint best_bird_dist = 0; + uint best_track_dist = 0; + byte train_dir = v->direction & 3; + + + best_track = (uint)-1; + + do { + i = FIND_FIRST_BIT(bits); + bits = KILL_FIRST_BIT(bits); + + fd.best_bird_dist = (uint)-1; + fd.best_track_dist = (uint)-1; + + NewTrainPathfind(tile, _search_directions[i][enterdir], (TPFEnumProc*)TrainTrackFollower, &fd, NULL); + if (best_track != (uint)-1) { + if (best_track_dist == (uint)-1) { + if (fd.best_track_dist == (uint)-1) { + /* neither reached the destination, pick the one with the smallest bird dist */ + if (fd.best_bird_dist > best_bird_dist) goto bad; + if (fd.best_bird_dist < best_bird_dist) goto good; + } else { + /* we found the destination for the first time */ + goto good; + } } else { - /* both old & new reached the destination, compare track length */ - if (fd.best_track_dist > best_track_dist) goto bad; - if (fd.best_track_dist < best_track_dist) goto good; + if (fd.best_track_dist == (uint)-1) { + /* didn't find destination, but we've found the destination previously */ + goto bad; + } else { + /* both old & new reached the destination, compare track length */ + if (fd.best_track_dist > best_track_dist) goto bad; + if (fd.best_track_dist < best_track_dist) goto good; + } } - } - /* if we reach this position, there's two paths of equal value so far. - * pick one randomly. */ - r = (byte)Random(); - if (_pick_track_table[i] == train_dir) r += 80; - if (_pick_track_table[best_track] == train_dir) r -= 80; + /* if we reach this position, there's two paths of equal value so far. + * pick one randomly. */ + r = (byte)Random(); + if (_pick_track_table[i] == train_dir) r += 80; + if (_pick_track_table[best_track] == train_dir) r -= 80; - if (r <= 127) goto bad; - } - good:; - best_track = i; - best_bird_dist = fd.best_bird_dist; - best_track_dist = fd.best_track_dist; - bad:; - } while (bits != 0); -// printf("Train %d %s\n", v->unitnumber, best_track_dist == -1 ? "NOTFOUND" : "FOUND"); - assert(best_track != (uint)-1); + if (r <= 127) goto bad; + } + good:; + best_track = i; + best_bird_dist = fd.best_bird_dist; + best_track_dist = fd.best_track_dist; + bad:; + } while (bits != 0); + // printf("Train %d %s\n", v->unitnumber, best_track_dist == -1 ? "NOTFOUND" : "FOUND"); + assert(best_track != (uint)-1); + } } -#if 0 +#if PF_BENCHMARK time = rdtsc() - time; f = f * 0.99 + 0.01 * time; printf("PF time = %d %f\n", time, f); @@ -1766,49 +1805,74 @@ static bool CheckReverseTrain(Vehicle *v) i = _search_directions[FIND_FIRST_BIT(v->u.rail.track)][v->direction>>1]; - while(true) { - fd.best_bird_dist = (uint)-1; - fd.best_track_dist = (uint)-1; + if (_patches.new_pathfinding_all) { /* Use a new pathfinding for everything */ + NPFFindStationOrTileData fstd; + NPFFoundTargetData ftd; + byte trackdir, trackdir_rev; + Vehicle* last = GetLastVehicleInChain(v); - NewTrainPathfind(v->tile, reverse ^ i, (TPFEnumProc*)TrainTrackFollower, &fd, NULL); + NPFFillWithOrderData(&fstd, v); - if (best_track != -1) { - if (best_bird_dist != 0) { - if (fd.best_bird_dist != 0) { - /* neither reached the destination, pick the one with the smallest bird dist */ - if (fd.best_bird_dist > best_bird_dist) goto bad; - if (fd.best_bird_dist < best_bird_dist) goto good; - } else { - /* we found the destination for the first time */ - goto good; - } - } else { - if (fd.best_bird_dist != 0) { - /* didn't find destination, but we've found the destination previously */ - goto bad; + trackdir = _track_direction_to_trackdir[FIND_FIRST_BIT(v->u.rail.track)][v->direction]; + trackdir_rev = REVERSE_TRACKDIR(_track_direction_to_trackdir[FIND_FIRST_BIT(last->u.rail.track)][last->direction]); + assert(trackdir != 0xff); + assert(trackdir_rev != 0xff); + + ftd = NPFRouteToStationOrTileTwoWay(v->tile, trackdir, last->tile, trackdir_rev, &fstd, TRANSPORT_RAIL); + if (ftd.best_bird_dist != 0) { + /* We didn't find anything, just keep on going straight ahead */ + reverse_best = false; + } else { + if (ftd.node.user_data[NPF_NODE_FLAGS] & NPF_FLAG_REVERSE) + reverse_best = true; + else + reverse_best = false; + } + } else { + while(true) { + fd.best_bird_dist = (uint)-1; + fd.best_track_dist = (uint)-1; + + NewTrainPathfind(v->tile, reverse ^ i, (TPFEnumProc*)TrainTrackFollower, &fd, NULL); + + if (best_track != -1) { + if (best_bird_dist != 0) { + if (fd.best_bird_dist != 0) { + /* neither reached the destination, pick the one with the smallest bird dist */ + if (fd.best_bird_dist > best_bird_dist) goto bad; + if (fd.best_bird_dist < best_bird_dist) goto good; + } else { + /* we found the destination for the first time */ + goto good; + } } else { - /* both old & new reached the destination, compare track length */ - if (fd.best_track_dist > best_track_dist) goto bad; - if (fd.best_track_dist < best_track_dist) goto good; + if (fd.best_bird_dist != 0) { + /* didn't find destination, but we've found the destination previously */ + goto bad; + } else { + /* both old & new reached the destination, compare track length */ + if (fd.best_track_dist > best_track_dist) goto bad; + if (fd.best_track_dist < best_track_dist) goto good; + } } - } - /* if we reach this position, there's two paths of equal value so far. - * pick one randomly. */ - r = (byte)Random(); - if (_pick_track_table[i] == (v->direction & 3)) r += 80; - if (_pick_track_table[best_track] == (v->direction & 3)) r -= 80; - if (r <= 127) goto bad; - } + /* if we reach this position, there's two paths of equal value so far. + * pick one randomly. */ + r = (byte)Random(); + if (_pick_track_table[i] == (v->direction & 3)) r += 80; + if (_pick_track_table[best_track] == (v->direction & 3)) r -= 80; + if (r <= 127) goto bad; + } good:; - best_track = i; - best_bird_dist = fd.best_bird_dist; - best_track_dist = fd.best_track_dist; - reverse_best = reverse; + best_track = i; + best_bird_dist = fd.best_bird_dist; + best_track_dist = fd.best_track_dist; + reverse_best = reverse; bad:; - if (reverse != 0) - break; - reverse = 2; + if (reverse != 0) + break; + reverse = 2; + } } return reverse_best != 0; @@ -2331,7 +2395,7 @@ static void TrainController(Vehicle *v) Vehicle *prev = NULL; GetNewVehiclePosResult gp; uint32 r, tracks,ts; - int dir, i; + int i, enterdir, newdir, dir; byte chosen_dir; byte chosen_track; byte old_z; @@ -2355,8 +2419,10 @@ static void TrainController(Vehicle *v) return; r = VehicleEnterTile(v, gp.new_tile, gp.x, gp.y); - if (r & 0x8) + if (r & 0x8) { + //debug("%x & 0x8", r); goto invalid_rail; + } if (r & 0x2) { TrainEnterStation(v, r >> 8); return; @@ -2371,30 +2437,43 @@ static void TrainController(Vehicle *v) } else { /* A new tile is about to be entered. */ + byte bits; /* Determine what direction we're entering the new tile from */ dir = GetNewVehicleDirectionByTile(gp.new_tile, gp.old_tile); - assert(dir==1 || dir==3 || dir==5 || dir==7); + enterdir = dir >> 1; + assert(enterdir==0 || enterdir==1 || enterdir==2 || enterdir==3); /* Get the status of the tracks in the new tile and mask * away the bits that aren't reachable. */ - ts = GetTileTrackStatus(gp.new_tile, TRANSPORT_RAIL) & _reachable_tracks[dir >> 1]; + ts = GetTileTrackStatus(gp.new_tile, TRANSPORT_RAIL) & _reachable_tracks[enterdir]; /* Combine the from & to directions. * Now, the lower byte contains the track status, and the byte at bit 16 contains * the signal status. */ tracks = ts|(ts >> 8); - if ( (byte) tracks == 0) + bits = tracks & 0xFF; + if (_patches.new_pathfinding_all && _patches.forbid_90_deg && prev == NULL) + /* We allow wagons to make 90 deg turns, because forbid_90_deg + * can be switched on halfway a turn */ + bits &= ~_track_crosses_tracks[FIND_FIRST_BIT(v->u.rail.track)]; + + if ( bits == 0) { + //debug("%x == 0", bits); goto invalid_rail; + } /* Check if the new tile contrains tracks that are compatible * with the current train, if not, bail out. */ - if (!CheckCompatibleRail(v, gp.new_tile)) + if (!CheckCompatibleRail(v, gp.new_tile)) { + //debug("!CheckCompatibleRail(%p, %x)", v, gp.new_tile); goto invalid_rail; + } if (prev == NULL) { /* Currently the locomotive is active. Determine which one of the * available tracks to choose */ - chosen_track = 1 << ChooseTrainTrack(v, gp.new_tile, dir>>1, (byte)tracks); + chosen_track = 1 << ChooseTrainTrack(v, gp.new_tile, enterdir, bits); + assert(chosen_track & tracks); /* Check if it's a red signal and that force proceed is not clicked. */ if ( (tracks>>16)&chosen_track && v->u.rail.force_proceed == 0) goto red_light; @@ -2402,7 +2481,7 @@ static void TrainController(Vehicle *v) static byte _matching_tracks[8] = {0x30, 1, 0xC, 2, 0x30, 1, 0xC, 2}; /* The wagon is active, simply follow the prev vehicle. */ - chosen_track = (byte)(_matching_tracks[GetDirectionToVehicle(prev, gp.x, gp.y)] & tracks); + chosen_track = (byte)(_matching_tracks[GetDirectionToVehicle(prev, gp.x, gp.y)] & bits); } /* make sure chosen track is a valid track */ @@ -2410,7 +2489,7 @@ static void TrainController(Vehicle *v) /* Update XY to reflect the entrance to the new tile, and select the direction to use */ { - const byte *b = _initial_tile_subcoord[FIND_FIRST_BIT(chosen_track)][dir>>1]; + const byte *b = _initial_tile_subcoord[FIND_FIRST_BIT(chosen_track)][enterdir]; gp.x = (gp.x & ~0xF) | b[0]; gp.y = (gp.y & ~0xF) | b[1]; chosen_dir = b[2]; @@ -2418,8 +2497,10 @@ static void TrainController(Vehicle *v) /* Call the landscape function and tell it that the vehicle entered the tile */ r = VehicleEnterTile(v, gp.new_tile, gp.x, gp.y); - if (r&0x8) + if (r&0x8){ + //debug("%x & 0x8", r); goto invalid_rail; + } if (v->subtype == TS_Front_Engine) v->load_unload_time_rem = 0; @@ -2429,12 +2510,12 @@ static void TrainController(Vehicle *v) } if (v->subtype == TS_Front_Engine) - TrainMovedChangeSignals(gp.new_tile, dir>>1); + TrainMovedChangeSignals(gp.new_tile, enterdir); /* Signals can only change when the first * (above) or the last vehicle moves. */ if (v->next == NULL) - TrainMovedChangeSignals(gp.old_tile, (dir>>1) ^ 2); + TrainMovedChangeSignals(gp.old_tile, (enterdir) ^ 2); if (prev == NULL) { AffectSpeedByDirChange(v, chosen_dir); @@ -2462,9 +2543,9 @@ static void TrainController(Vehicle *v) common:; /* update image of train, as well as delta XY */ - dir = GetNewVehicleDirection(v, gp.x, gp.y); - UpdateTrainDeltaXY(v, dir); - v->cur_image = GetTrainImage(v, dir); + newdir = GetNewVehicleDirection(v, gp.x, gp.y); + UpdateTrainDeltaXY(v, newdir); + v->cur_image = GetTrainImage(v, newdir); v->x_pos = gp.x; v->y_pos = gp.y; @@ -2498,18 +2579,18 @@ red_light: { * FIND_FIRST_BIT only handles 6 bits at a time. */ i = FindFirstBit2x64(ts); - if (!(_map3_lo[gp.new_tile] & _signal_otherdir[i])) { + if (!(_map3_lo[gp.new_tile] & _signal_against_trackdir[i])) { v->cur_speed = 0; v->subspeed = 0; v->progress = 255-100; if (++v->load_unload_time_rem < _patches.wait_oneway_signal * 20) return; - } else if (_map3_lo[gp.new_tile] & _signal_onedir[i]){ + } else if (_map3_lo[gp.new_tile] & _signal_along_trackdir[i]){ v->cur_speed = 0; v->subspeed = 0; v->progress = 255-10; if (++v->load_unload_time_rem < _patches.wait_twoway_signal * 73) { - uint o_tile = gp.new_tile + TileOffsByDir(dir >> 1); + uint o_tile = gp.new_tile + TileOffsByDir(enterdir); /* check if a train is waiting on the other side */ if (VehicleFromPos(o_tile, (void*)( (o_tile<<8) | (dir^4)), (VehicleFromPosProc*)CheckVehicleAtSignal) == NULL) return; diff --git a/variables.h b/variables.h index f80e2e160..214406b26 100644 --- a/variables.h +++ b/variables.h @@ -128,6 +128,7 @@ typedef struct Patches { bool nonuniform_stations;// allow nonuniform train stations bool always_small_airport; // always allow small airports bool realistic_acceleration; // realistic acceleration for trains + bool forbid_90_deg; // forbid trains to make 90 deg turns bool invisible_trees; // don't show trees when buildings are transparent bool no_servicing_if_no_breakdowns; // dont send vehicles to depot when breakdowns are disabled @@ -186,6 +187,13 @@ typedef struct Patches { byte drag_signals_density; // many signals density bool ainew_active; // Is the new AI active? + /* New Path Finding */ + bool new_pathfinding_all; /* Use the newest pathfinding algorithm for all */ + + uint32 npf_rail_firstred_penalty; /* The penalty for when the first signal is red */ + uint32 npf_rail_station_penalty; /* The penalty for station tiles */ + uint32 npf_rail_slope_penalty; /* The penalty for sloping upwards */ + bool population_in_label; // Show the population of a town in his label? } Patches; @@ -434,6 +442,9 @@ VARDEF byte _vehicle_design_names; /* tunnelbridge */ #define MAX_BRIDGES 13 +/* For new pathfinding. Define here so it is globally available */ +#define NPF_TILE_LENGTH 100 + /* Autoreplace vehicle stuff*/ VARDEF byte _autoreplace_array[256]; VARDEF uint16 _player_num_engines[256]; |