summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Makefile1
-rw-r--r--functions.h5
-rw-r--r--industry_cmd.c4
-rw-r--r--landscape.c19
-rw-r--r--lang/english.txt8
-rw-r--r--macros.h18
-rw-r--r--map.c33
-rw-r--r--map.h22
-rw-r--r--misc.c2
-rw-r--r--npf.c776
-rw-r--r--npf.h128
-rw-r--r--order_cmd.c6
-rw-r--r--pathfind.h3
-rw-r--r--queue.c2
-rw-r--r--rail_cmd.c1
-rw-r--r--road_cmd.c2
-rw-r--r--roadveh_cmd.c141
-rw-r--r--settings.c28
-rw-r--r--settings_gui.c10
-rw-r--r--ship_cmd.c92
-rw-r--r--station.h16
-rw-r--r--station_cmd.c6
-rw-r--r--table/directions.h8
-rw-r--r--train_cmd.c341
-rw-r--r--variables.h11
25 files changed, 1418 insertions, 265 deletions
diff --git a/Makefile b/Makefile
index 8f9452c04..e942f5335 100644
--- a/Makefile
+++ b/Makefile
@@ -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}
diff --git a/macros.h b/macros.h
index 19194ac86..71f015bdb 100644
--- a/macros.h
+++ b/macros.h
@@ -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)))
diff --git a/map.c b/map.c
index 2481843d2..98d2c4e39 100644
--- a/map.c
+++ b/map.c
@@ -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}
-};
diff --git a/map.h b/map.h
index 605b89495..55704a555 100644
--- a/map.h
+++ b/map.h
@@ -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
diff --git a/misc.c b/misc.c
index f4e363585..bb7eb4f0e 100644
--- a/misc.c
+++ b/misc.c
@@ -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();
diff --git a/npf.c b/npf.c
new file mode 100644
index 000000000..430c03ebb
--- /dev/null
+++ b/npf.c
@@ -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 = &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;
+ }
+}
diff --git a/npf.h b/npf.h
new file mode 100644
index 000000000..0b3e17a0e
--- /dev/null
+++ b/npf.h
@@ -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);
diff --git a/queue.c b/queue.c
index 00e14b8b3..21c163688 100644
--- a/queue.c
+++ b/queue.c
@@ -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] = {
diff --git a/station.h b/station.h
index ca14257b1..8bfb28d68 100644
--- a/station.h
+++ b/station.h
@@ -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];
generated by cgit v1.2.3-54-g00ecf (git 2.44.0) at 2024-07-11 06:56:04 +0000