src/road.cpp

   1 /* $Id: road.cpp 24900 2013-01-08 22:46:42Z planetmaker $ */
   2
   3 /*
   4  * This file is part of OpenTTD.
   5  * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
   6  * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
   7  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
   8  */
   9
  10 /** @file road.cpp Generic road related functions. */
  11
  12 #include "stdafx.h"
  13 #include <algorithm>
  14 #include <memory>
  15 #include <numeric>
  16 #include <unordered_map>
  17 #include <vector>
  18 #include "rail_map.h"
  19 #include "road_map.h"
  20 #include "water_map.h"
  21 #include "genworld.h"
  22 #include "company_func.h"
  23 #include "company_base.h"
  24 #include "engine_base.h"
  25 #include "date_func.h"
  26 #include "landscape.h"
  27 #include "town.h"
  28 #include "pathfinder/npf/aystar.h"
  29 #include "tunnelbridge.h"
  30 #include "road.h"
  31 #include "road_func.h"
  32 #include "roadveh.h"
  33 #include "command_func.h"
  34 #include "core/backup_type.hpp"
  35 #include "core/random_func.hpp"
  36
  37 #include "safeguards.h"
  38
  39 /**
  40  * Return if the tile is a valid tile for a crossing.
  41  *
  42  * @param tile the current tile
  43  * @param ax the axis of the road over the rail
  44  * @return true if it is a valid tile
  45  */
  46 static bool IsPossibleCrossing(const TileIndex tile, Axis ax)
  47 {
  48         return (IsTileType(tile, MP_RAILWAY) &&
  49                 GetRailTileType(tile) == RAIL_TILE_NORMAL &&
  50                 GetTrackBits(tile) == (ax == AXIS_X ? TRACK_BIT_Y : TRACK_BIT_X) &&
  51                 GetFoundationSlope(tile) == SLOPE_FLAT);
  52 }
  53
  54 /** Whether to build public roads */
  55 enum PublicRoadsConstruction {
  56         PRC_NONE,         ///< Generate no public roads
  57         PRC_WITH_CURVES,  ///< Generate roads with lots of curves
  58         PRC_AVOID_CURVES, ///< Generate roads avoiding curves if possible
  59 };
  60
  61 /**
  62  * Clean up unnecessary RoadBits of a planed tile.
  63  * @param tile current tile
  64  * @param org_rb planed RoadBits
  65  * @return optimised RoadBits
  66  */
  67 RoadBits CleanUpRoadBits(const TileIndex tile, RoadBits org_rb)
  68 {
  69         if (!IsValidTile(tile)) return ROAD_NONE;
  70         for (DiagDirection dir = DIAGDIR_BEGIN; dir < DIAGDIR_END; dir++) {
  71                 const TileIndex neighbor_tile = TileAddByDiagDir(tile, dir);
  72
  73                 /* Get the Roadbit pointing to the neighbor_tile */
  74                 const RoadBits target_rb = DiagDirToRoadBits(dir);
  75
  76                 /* If the roadbit is in the current plan */
  77                 if (org_rb & target_rb) {
  78                         bool connective = false;
  79                         const RoadBits mirrored_rb = MirrorRoadBits(target_rb);
  80
  81                         if (IsValidTile(neighbor_tile)) {
  82                                 switch (GetTileType(neighbor_tile)) {
  83                                         /* Always connective ones */
  84                                         case MP_CLEAR: case MP_TREES:
  85                                                 connective = true;
  86                                                 break;
  87
  88                                         /* The conditionally connective ones */
  89                                         case MP_TUNNELBRIDGE:
  90                                         case MP_STATION:
  91                                         case MP_ROAD:
  92                                                 if (IsNormalRoadTile(neighbor_tile)) {
  93                                                         /* Always connective */
  94                                                         connective = true;
  95                                                 } else {
  96                                                         const RoadBits neighbor_rb = GetAnyRoadBits(neighbor_tile, ROADTYPE_ROAD) | GetAnyRoadBits(neighbor_tile, ROADTYPE_TRAM); // TODO
  97
  98                                                         /* Accept only connective tiles */
  99                                                         connective = (neighbor_rb & mirrored_rb) != ROAD_NONE;
 100                                                 }
 101                                                 break;
 102
 103                                         case MP_RAILWAY:
 104                                                 connective = IsPossibleCrossing(neighbor_tile, DiagDirToAxis(dir));
 105                                                 break;
 106
 107                                         case MP_WATER:
 108                                                 /* Check for real water tile */
 109                                                 connective = !IsWater(neighbor_tile);
 110                                                 break;
 111
 112                                         /* The definitely not connective ones */
 113                                         default: break;
 114                                 }
 115                         }
 116
 117                         /* If the neighbor tile is inconnective, remove the planed road connection to it */
 118                         if (!connective) org_rb ^= target_rb;
 119                 }
 120         }
 121
 122         return org_rb;
 123 }
 124
 125 /**
 126  * Finds out, whether given company has all given RoadTypes available
 127  * @param company ID of company
 128  * @param rtid RoadType to test
 129  * @return true if company has the requested RoadType available
 130  */
 131 bool HasRoadTypeAvail(const CompanyID company, RoadTypeIdentifier rtid)
 132 {
 133         if (company == OWNER_DEITY || company == OWNER_TOWN || _game_mode == GM_EDITOR || _generating_world) {
 134                 return true; // TODO
 135         } else {
 136                 Company *c = Company::GetIfValid(company);
 137                 if (c == nullptr) return false;
 138                 return HasBit(c->avail_roadtypes[rtid.basetype], rtid.subtype);
 139         }
 140 }
 141
 142 /**
 143  * Validate functions for rail building.
 144  * @param rtid road type to check.
 145  * @return true if the current company may build the road.
 146  */
 147 bool ValParamRoadType(RoadTypeIdentifier rtid)
 148 {
 149         return rtid.IsValid() && HasRoadTypeAvail(_current_company, rtid);
 150 }
 151
 152 /**
 153  * Add the road types that are to be introduced at the given date.
 154  * @param rt      Roadtype
 155  * @param current The currently available roadsubtypes.
 156  * @param date    The date for the introduction comparisons.
 157  * @return The road types that should be available when date
 158  *         introduced road types are taken into account as well.
 159  */
 160 RoadSubTypes AddDateIntroducedRoadTypes(RoadType rt, RoadSubTypes current, Date date)
 161 {
 162         RoadSubTypes rts = current;
 163
 164         for (RoadSubType rst = ROADSUBTYPE_BEGIN; rst != ROADSUBTYPE_END; rst++) {
 165                 const RoadtypeInfo *rti = GetRoadTypeInfo(RoadTypeIdentifier(rt, rst));
 166                 /* Unused road type. */
 167                 if (rti->label == 0) continue;
 168
 169                 /* Not date introduced. */
 170                 if (!IsInsideMM(rti->introduction_date, 0, MAX_DAY)) continue;
 171
 172                 /* Not yet introduced at this date. */
 173                 if (rti->introduction_date > date) continue;
 174
 175                 /* Have we introduced all required roadtypes? */
 176                 RoadSubTypes required = rti->introduction_required_roadtypes;
 177                 if ((rts & required) != required) continue;
 178
 179                 rts |= rti->introduces_roadtypes;
 180         }
 181
 182         /* When we added roadtypes we need to run this method again; the added
 183          * roadtypes might enable more rail types to become introduced. */
 184         return rts == current ? rts : AddDateIntroducedRoadTypes(rt, rts, date);
 185 }
 186
 187 /**
 188  * Get the road (sub) types the given company can build.
 189  * @param company the company to get the roadtypes for.
 190  * @param rt the base road type to check
 191  * @return the available road sub types.
 192  */
 193 RoadSubTypes GetCompanyRoadtypes(CompanyID company, RoadType rt)
 194 {
 195         RoadSubTypes rst = ROADSUBTYPES_NONE;
 196
 197         if (rt == ROADTYPE_ROAD) rst |= ROADSUBTYPES_NORMAL; // Road is always available. // TODO
 198
 199         Engine *e;
 200         FOR_ALL_ENGINES_OF_TYPE(e, VEH_ROAD) {
 201                 const EngineInfo *ei = &e->info;
 202
 203                 if (HasBit(ei->climates, _settings_game.game_creation.landscape) &&
 204                                 (HasBit(e->company_avail, company) || _date >= e->intro_date + DAYS_IN_YEAR) &&
 205                                 rt == (HasBit(ei->misc_flags, EF_ROAD_TRAM) ? ROADTYPE_TRAM : ROADTYPE_ROAD)) {
 206                         rst |= GetRoadTypeInfo(e->GetRoadType())->introduces_roadtypes;
 207                 }
 208         }
 209
 210         return AddDateIntroducedRoadTypes(rt, rst, _date);
 211 }
 212
 213 /* ========================================================================= */
 214 /*                                PUBLIC ROADS                               */
 215 /* ========================================================================= */
 216
 217 CommandCost CmdBuildBridge(TileIndex end_tile, DoCommandFlag flags, uint32 p1, uint32 p2, const char *text = nullptr);
 218 CommandCost CmdBuildTunnel(TileIndex tile, DoCommandFlag flags, uint32 p1, uint32 p2, const char *text = nullptr);
 219 CommandCost CmdBuildRoad(TileIndex tile, DoCommandFlag flags, uint32 p1, uint32 p2, const char *text = nullptr);
 220
 221 static std::vector<TileIndex> _town_centers;
 222 static std::vector<TileIndex> _towns_visited_along_the_way;
 223 static const uint PUBLIC_ROAD_HASH_SIZE = 8U; ///< The number of bits the hash for river finding should have.
 224
 225 /**
 226 * Simple hash function for public road tiles to be used by AyStar.
 227 * @param tile The tile to hash.
 228 * @param dir The unused direction.
 229 * @return The hash for the tile.
 230 */
 231 static uint PublicRoad_Hash(uint tile, uint dir)
 232 {
 233         return GB(TileHash(TileX(tile), TileY(tile)), 0, PUBLIC_ROAD_HASH_SIZE);
 234 }
 235
 236 static const int32 BASE_COST = 1;          // Cost for utilizing an existing road, bridge, or tunnel.
 237 static const int32 COST_FOR_NEW_ROAD = 10; // Cost for building a new road.
 238 static const int32 COST_FOR_SLOPE = 5;     // Additional cost if the road heads up or down a slope.
 239
 240 /* AyStar callback for getting the cost of the current node. */
 241 static int32 PublicRoad_CalculateG(AyStar *aystar, AyStarNode *current, OpenListNode *parent)
 242 {
 243         int32 cost = BASE_COST;
 244
 245         if (!IsTileType(current->tile, MP_ROAD)) {
 246                 if (!AreTilesAdjacent(parent->path.node.tile, current->tile))
 247                 {
 248                         // We're not adjacent, so we built a tunnel or bridge.
 249                         cost += (DistanceManhattan(parent->path.node.tile, current->tile)) * COST_FOR_NEW_ROAD + 6 * COST_FOR_SLOPE;
 250                 }
 251                 else if (!IsTileFlat(current->tile)) {
 252                         cost += COST_FOR_NEW_ROAD;
 253                         cost += COST_FOR_SLOPE;
 254                 }
 255                 else
 256                 {
 257                         cost += COST_FOR_NEW_ROAD;
 258                 }
 259         }
 260
 261         if (_settings_game.game_creation.build_public_roads == PRC_AVOID_CURVES &&
 262                 parent->path.parent != nullptr &&
 263                 DiagdirBetweenTiles(parent->path.parent->node.tile, parent->path.node.tile) != DiagdirBetweenTiles(parent->path.node.tile, current->tile)) {
 264                 cost += 1;
 265         }
 266
 267         return cost;
 268 }
 269
 270 /* AyStar callback for getting the estimated cost to the destination. */
 271 static int32 PublicRoad_CalculateH(AyStar *aystar, AyStarNode *current, OpenListNode *parent)
 272 {
 273         return DistanceManhattan(*(TileIndex*)aystar->user_target, current->tile) * BASE_COST;
 274 }
 275
 276 /* Helper function to check if a tile along a certain direction is going up an inclined slope. */
 277 static bool IsUpwardsSlope(TileIndex tile, DiagDirection road_direction)
 278 {
 279         auto slope = GetTileSlope(tile);
 280
 281         if (!IsInclinedSlope(slope)) return false;
 282
 283         auto slope_direction = GetInclinedSlopeDirection(slope);
 284
 285         return road_direction == slope_direction;
 286 }
 287
 288 /* Helper function to check if a tile along a certain direction is going down an inclined slope. */
 289 static bool IsDownwardsSlope(TileIndex tile, DiagDirection road_direction)
 290 {
 291         auto slope = GetTileSlope(tile);
 292
 293         if (!IsInclinedSlope(slope)) return false;
 294
 295         auto slope_direction = GetInclinedSlopeDirection(slope);
 296
 297         return road_direction == ReverseDiagDir(slope_direction);
 298 }
 299
 300 /* Helper function to check if a road along this tile path is possible. */
 301 static bool CanBuildRoadFromTo(TileIndex begin, TileIndex end)
 302 {
 303         assert(DistanceManhattan(begin, end) == 1);
 304
 305         int heightBegin;
 306         int heightEnd;
 307         Slope slopeBegin = GetTileSlope(begin, &heightBegin);
 308         Slope slopeEnd = GetTileSlope(end, &heightEnd);
 309
 310         return
 311                 /* Slope either is inclined or flat; rivers don't support other slopes. */
 312                 (slopeEnd == SLOPE_FLAT || IsInclinedSlope(slopeEnd)) &&
 313                 /* Slope continues, then it must be lower... or either end must be flat. */
 314                 ((slopeEnd == slopeBegin && heightEnd != heightBegin) || slopeEnd == SLOPE_FLAT || slopeBegin == SLOPE_FLAT);
 315 }
 316
 317 static TileIndex BuildTunnel(PathNode *current, bool build_tunnel = false)
 318 {
 319         Backup<CompanyByte> cur_company(_current_company, OWNER_DEITY, FILE_LINE);
 320         auto build_tunnel_cmd = CmdBuildTunnel(current->node.tile, build_tunnel ? DC_EXEC : DC_NONE, ROADTYPES_ROAD | (TRANSPORT_ROAD << 8), 0);
 321         cur_company.Restore();
 322
 323         assert(!build_tunnel || build_tunnel_cmd.Succeeded());
 324         assert(!build_tunnel || (IsTileType(current->node.tile, MP_TUNNELBRIDGE) && IsTileType(_build_tunnel_endtile, MP_TUNNELBRIDGE)));
 325
 326         if (!build_tunnel_cmd.Succeeded()) return INVALID_TILE;
 327         if (!build_tunnel && !IsTileType(_build_tunnel_endtile, MP_CLEAR) && !IsTileType(_build_tunnel_endtile, MP_TREES)) return INVALID_TILE;
 328
 329         return _build_tunnel_endtile;
 330 }
 331
 332 static TileIndex BuildBridge(PathNode *current, TileIndex end_tile = INVALID_TILE, bool build_bridge = false)
 333 {
 334         TileIndex start_tile = current->node.tile;
 335
 336         DiagDirection direction = ReverseDiagDir(GetInclinedSlopeDirection(GetTileSlope(start_tile)));
 337
 338         if (!build_bridge) {
 339                 // We are not building yet, so we still need to find the end_tile.
 340                 for (TileIndex tile = start_tile + TileOffsByDiagDir(direction);
 341                         IsValidTile(tile) &&
 342                         (GetTunnelBridgeLength(start_tile, tile) <= _settings_game.construction.max_bridge_length) &&
 343                         (GetTileZ(start_tile) < (GetTileZ(tile) + _settings_game.construction.max_bridge_height)) &&
 344                         (GetTileZ(tile) <= GetTileZ(start_tile));
 345                         tile += TileOffsByDiagDir(direction)) {
 346
 347                         // No supershort bridges and always ending up on a matching upwards slope.
 348                         if (!AreTilesAdjacent(start_tile, tile) && IsUpwardsSlope(tile, direction)) {
 349                                 end_tile = tile;
 350                                 break;
 351                         }
 352                 }
 353
 354                 if (!IsValidTile(end_tile)) return INVALID_TILE;
 355                 if (!IsTileType(end_tile, MP_CLEAR) && !IsTileType(end_tile, MP_TREES)) return INVALID_TILE;
 356         }
 357
 358         assert(!build_bridge || IsValidTile(end_tile));
 359
 360         std::vector<BridgeType> available_bridge_types;
 361
 362         for (uint i = 0; i < MAX_BRIDGES; ++i) {
 363                 if (CheckBridgeAvailability((BridgeType)i, GetTunnelBridgeLength(start_tile, end_tile)).Succeeded()) {
 364                         available_bridge_types.push_back((BridgeType)i);
 365                 }
 366         }
 367
 368         assert(!build_bridge || !available_bridge_types.empty());
 369         if (available_bridge_types.empty()) return INVALID_TILE;
 370
 371         auto bridge_type = available_bridge_types[build_bridge ? RandomRange((uint32)available_bridge_types.size()) : 0];
 372
 373         Backup<CompanyByte> cur_company(_current_company, OWNER_DEITY, FILE_LINE);
 374         auto build_bridge_cmd = CmdBuildBridge(end_tile, build_bridge ? DC_EXEC : DC_NONE, start_tile, bridge_type | (ROADTYPES_ROAD << 8) | (TRANSPORT_ROAD << 15));
 375         cur_company.Restore();
 376
 377         assert(!build_bridge || build_bridge_cmd.Succeeded());
 378         assert(!build_bridge || (IsTileType(start_tile, MP_TUNNELBRIDGE) && IsTileType(end_tile, MP_TUNNELBRIDGE)));
 379
 380         if (!build_bridge_cmd.Succeeded()) return INVALID_TILE;
 381
 382         return end_tile;
 383 }
 384
 385 static TileIndex BuildRiverBridge(PathNode *current, DiagDirection road_direction, TileIndex end_tile = INVALID_TILE, bool build_bridge = false)
 386 {
 387         TileIndex start_tile = current->node.tile;
 388
 389         if (!build_bridge) {
 390                 // We are not building yet, so we still need to find the end_tile.
 391                 // We will only build a bridge if we need to cross a river, so first check for that.
 392                 TileIndex tile = start_tile + TileOffsByDiagDir(road_direction);
 393
 394                 if (!IsWaterTile(tile) || !IsRiver(tile)) return INVALID_TILE;
 395
 396                 // Now let's see if we can bridge it. But don't bridge anything more than 4 river tiles. Cities aren't allowed to, so public roads we are not either.
 397                 // Only bridges starting at slopes should be longer ones. The others look like crap when built this way. Players can build them but the map generator
 398                 // should not force that on them. This is just to bridge rivers, not to make long bridges.
 399                 for (;
 400                         IsValidTile(tile) &&
 401                         (GetTunnelBridgeLength(start_tile, tile) <= 5) &&
 402                         (GetTileZ(start_tile) < (GetTileZ(tile) + _settings_game.construction.max_bridge_height)) &&
 403                         (GetTileZ(tile) <= GetTileZ(start_tile));
 404                         tile += TileOffsByDiagDir(road_direction)) {
 405
 406                         if ((IsTileType(tile, MP_CLEAR) || IsTileType(tile, MP_TREES)) &&
 407                                 GetTileZ(tile) <= GetTileZ(start_tile) &&
 408                                 GetTileSlope(tile) == SLOPE_FLAT) {
 409                                 end_tile = tile;
 410                                 break;
 411                         }
 412                 }
 413
 414                 if (!IsValidTile(end_tile)) return INVALID_TILE;
 415                 if (!IsTileType(end_tile, MP_CLEAR) && !IsTileType(end_tile, MP_TREES)) return INVALID_TILE;
 416         }
 417
 418         assert(!build_bridge || IsValidTile(end_tile));
 419
 420         std::vector<BridgeType> available_bridge_types;
 421
 422         for (uint i = 0; i < MAX_BRIDGES; ++i) {
 423                 if (CheckBridgeAvailability((BridgeType)i, GetTunnelBridgeLength(start_tile, end_tile)).Succeeded()) {
 424                         available_bridge_types.push_back((BridgeType)i);
 425                 }
 426         }
 427
 428         auto bridge_type = available_bridge_types[build_bridge ? RandomRange((uint32)available_bridge_types.size()) : 0];
 429
 430         Backup<CompanyByte> cur_company(_current_company, OWNER_DEITY, FILE_LINE);
 431         auto build_bridge_cmd = CmdBuildBridge(end_tile, build_bridge ? DC_EXEC : DC_NONE, start_tile, bridge_type | (ROADTYPES_ROAD << 8) | (TRANSPORT_ROAD << 15));
 432         cur_company.Restore();
 433
 434         assert(!build_bridge || build_bridge_cmd.Succeeded());
 435         assert(!build_bridge || (IsTileType(start_tile, MP_TUNNELBRIDGE) && IsTileType(end_tile, MP_TUNNELBRIDGE)));
 436
 437         if (!build_bridge_cmd.Succeeded()) return INVALID_TILE;
 438
 439         return end_tile;
 440 }
 441
 442 static bool IsValidNeighbourOfPreviousTile(TileIndex tile, TileIndex previous_tile)
 443 {
 444         if (!IsValidTile(tile)) return false;
 445
 446         if (IsTileType(tile, MP_TUNNELBRIDGE))
 447         {
 448                 if (GetOtherTunnelBridgeEnd(tile) == previous_tile) return true;
 449
 450                 auto tunnel_direction = GetTunnelBridgeDirection(tile);
 451
 452                 if (previous_tile + TileOffsByDiagDir(tunnel_direction) != tile) return false;
 453         } else {
 454
 455                 if (!IsTileType(tile, MP_CLEAR) && !IsTileType(tile, MP_TREES) && !IsTileType(tile, MP_ROAD)) return false;
 456
 457                 auto slope = GetTileSlope(tile);
 458
 459                 // Do not allow foundations. We'll mess things up later.
 460                 bool hasFoundation = GetFoundationSlope(tile) != slope;
 461                 if (hasFoundation) return false;
 462
 463                 if (IsInclinedSlope(slope)) {
 464                         auto slope_direction = GetInclinedSlopeDirection(slope);
 465                         auto road_direction = DiagdirBetweenTiles(previous_tile, tile);
 466
 467                         if (slope_direction != road_direction && ReverseDiagDir(slope_direction) != road_direction) return false;
 468                 } else if (slope != SLOPE_FLAT) {
 469                         return false;
 470                 }
 471         }
 472
 473         return true;
 474 }
 475
 476 /* AyStar callback for getting the neighbouring nodes of the given node. */
 477 static void PublicRoad_GetNeighbours(AyStar *aystar, OpenListNode *current)
 478 {
 479         TileIndex tile = current->path.node.tile;
 480
 481         aystar->num_neighbours = 0;
 482
 483         // Check if we just went through a tunnel or a bridge.
 484         if (current->path.parent != nullptr && !AreTilesAdjacent(tile, current->path.parent->node.tile)) {
 485                 auto previous_tile = current->path.parent->node.tile;
 486                 // We went through a tunnel or bridge, this limits our options to proceed to only forward.
 487                 auto tunnel_bridge_direction = DiagdirBetweenTiles(previous_tile, tile);
 488
 489                 TileIndex t2 = tile + TileOffsByDiagDir(tunnel_bridge_direction);
 490                 if (IsValidNeighbourOfPreviousTile(t2, tile)) {
 491                         aystar->neighbours[aystar->num_neighbours].tile = t2;
 492                         aystar->neighbours[aystar->num_neighbours].direction = INVALID_TRACKDIR;
 493                         aystar->num_neighbours++;
 494                 }
 495         } else {
 496                 // Handle all the regular neighbours and existing tunnels/bridges.
 497                 std::vector<TileIndex> potential_neighbours;
 498
 499                 if (IsTileType(tile, MP_TUNNELBRIDGE)) {
 500                         auto neighbour = GetOtherTunnelBridgeEnd(tile);
 501
 502                         aystar->neighbours[aystar->num_neighbours].tile = neighbour;
 503                         aystar->neighbours[aystar->num_neighbours].direction = INVALID_TRACKDIR;
 504                         aystar->num_neighbours++;
 505
 506                         neighbour = tile + TileOffsByDiagDir(ReverseDiagDir(DiagdirBetweenTiles(tile, neighbour)));
 507
 508                         if (IsValidNeighbourOfPreviousTile(neighbour, tile)) {
 509                                 aystar->neighbours[aystar->num_neighbours].tile = neighbour;
 510                                 aystar->neighbours[aystar->num_neighbours].direction = INVALID_TRACKDIR;
 511                                 aystar->num_neighbours++;
 512                         }
 513                 } else {
 514                         for (DiagDirection d = DIAGDIR_BEGIN; d < DIAGDIR_END; d++) {
 515                                 auto neighbour = tile + TileOffsByDiagDir(d);
 516                                 if (IsValidNeighbourOfPreviousTile(neighbour, tile)) {
 517                                         aystar->neighbours[aystar->num_neighbours].tile = neighbour;
 518                                         aystar->neighbours[aystar->num_neighbours].direction = INVALID_TRACKDIR;
 519                                         aystar->num_neighbours++;
 520                                 }
 521                         }
 522
 523                         // Check if we can turn this into a tunnel or a bridge.
 524                         if (current->path.parent != nullptr) {
 525                                 auto road_direction = DiagdirBetweenTiles(current->path.parent->node.tile, tile);
 526                                 if (IsUpwardsSlope(tile, road_direction)) {
 527                                         auto tunnel_end = BuildTunnel(&current->path);
 528
 529                                         if (tunnel_end != INVALID_TILE) {
 530                                                 assert(IsValidDiagDirection(DiagdirBetweenTiles(tile, tunnel_end)));
 531                                                 aystar->neighbours[aystar->num_neighbours].tile = tunnel_end;
 532                                                 aystar->neighbours[aystar->num_neighbours].direction = INVALID_TRACKDIR;
 533                                                 aystar->num_neighbours++;
 534                                         }
 535                                 }
 536                                 else if (IsDownwardsSlope(tile, road_direction)) {
 537                                         auto bridge_end = BuildBridge(&current->path);
 538
 539                                         if (bridge_end != INVALID_TILE) {
 540                                                 assert(IsValidDiagDirection(DiagdirBetweenTiles(tile, bridge_end)));
 541                                                 aystar->neighbours[aystar->num_neighbours].tile = bridge_end;
 542                                                 aystar->neighbours[aystar->num_neighbours].direction = INVALID_TRACKDIR;
 543                                                 aystar->num_neighbours++;
 544                                         }
 545                                 }
 546                                 else if (GetTileSlope(tile) == SLOPE_FLAT)
 547                                 {
 548                                         // Check if we could bridge a river from a flat tile. Not looking pretty on the map but you gotta do what you gotta do.
 549                                         auto bridge_end = BuildRiverBridge(&current->path, DiagdirBetweenTiles(current->path.parent->node.tile, tile));
 550                                         assert(bridge_end == INVALID_TILE || GetTileSlope(bridge_end) == SLOPE_FLAT);
 551
 552                                         if (bridge_end != INVALID_TILE) {
 553                                                 assert(IsValidDiagDirection(DiagdirBetweenTiles(tile, bridge_end)));
 554                                                 aystar->neighbours[aystar->num_neighbours].tile = bridge_end;
 555                                                 aystar->neighbours[aystar->num_neighbours].direction = INVALID_TRACKDIR;
 556                                                 aystar->num_neighbours++;
 557                                         }
 558
 559                                 }
 560                         }
 561                 }
 562         }
 563 }
 564
 565 /* AyStar callback for checking whether we reached our destination. */
 566 static int32 PublicRoad_EndNodeCheck(AyStar *aystar, OpenListNode *current)
 567 {
 568         // Mark towns visited along the way.
 569         auto search_result = std::find(_town_centers.begin(), _town_centers.end(), current->path.node.tile);
 570
 571         if (search_result != _town_centers.end()) {
 572                 _towns_visited_along_the_way.push_back(current->path.node.tile);
 573         };
 574
 575         return current->path.node.tile == *(TileIndex*)aystar->user_target ? AYSTAR_FOUND_END_NODE : AYSTAR_DONE;
 576 }
 577
 578 /* AyStar callback when an route has been found. */
 579 static void PublicRoad_FoundEndNode(AyStar *aystar, OpenListNode *current)
 580 {
 581         PathNode* child = nullptr;
 582
 583         for (PathNode *path = &current->path; path != nullptr; path = path->parent) {
 584                 TileIndex tile = path->node.tile;
 585
 586                 TownID townID = CalcClosestTownFromTile(tile)->index;
 587
 588                 if (IsTileType(tile, MP_TUNNELBRIDGE)) {
 589                         // Just follow the path; infrastructure is already in place.
 590                         continue;
 591                 } else if (path->parent == nullptr || AreTilesAdjacent(tile, path->parent->node.tile)) {
 592                         RoadBits road_bits = ROAD_NONE;
 593
 594                         if (child != nullptr) {
 595                                 TileIndex tile2 = child->node.tile;
 596                                 road_bits |= DiagDirToRoadBits(DiagdirBetweenTiles(tile, tile2));
 597                         }
 598                         if (path->parent != nullptr) {
 599                                 TileIndex tile2 = path->parent->node.tile;
 600                                 road_bits |= DiagDirToRoadBits(DiagdirBetweenTiles(tile, tile2));
 601                         }
 602
 603                         if (child != nullptr || path->parent != nullptr) {
 604                                 // Check if we need to build anything.
 605                                 bool need_to_build_road = true;
 606
 607                                 if (IsTileType(tile, MP_ROAD)) {
 608                                         RoadBits existing_bits = GetRoadBits(tile, ROADTYPE_ROAD);
 609                                         CLRBITS(road_bits, existing_bits);
 610                                         if (road_bits == ROAD_NONE) need_to_build_road = false;
 611                                 }
 612
 613                                 // If it is already a road and has the right bits, we are good. Otherwise build the needed ones.
 614                                 if (need_to_build_road)
 615                                 {
 616                                         Backup<CompanyByte> cur_company(_current_company, OWNER_DEITY, FILE_LINE);
 617                                         auto road_built = CmdBuildRoad(tile, DC_EXEC, ROADTYPE_ROAD << 4 | road_bits, 0);
 618                                         cur_company.Restore();
 619                                 }
 620                         }
 621                 } else {
 622                         // We only get here if we have a parent and we're not adjacent to it. River/Tunnel time!
 623                         DiagDirection road_direction = DiagdirBetweenTiles(tile, path->parent->node.tile);
 624
 625                         auto end_tile = INVALID_TILE;
 626
 627                         auto start_slope = GetTileSlope(tile);
 628
 629                         if (IsUpwardsSlope(tile, road_direction)) {
 630                                 end_tile = BuildTunnel(path, true);
 631                                 assert(IsValidTile(end_tile) && IsDownwardsSlope(end_tile, road_direction));
 632                         } else if (IsDownwardsSlope(tile, road_direction)) {
 633                                 // Provide the function with the end tile, since we already know it, but still check the result.
 634                                 end_tile = BuildBridge(path, path->parent->node.tile, true);
 635                                 assert(IsValidTile(end_tile) && IsUpwardsSlope(end_tile, road_direction));
 636                         } else {
 637                                 // River bridge is the last possibility.
 638                                 assert(GetTileSlope(tile) == SLOPE_FLAT);
 639                                 end_tile = BuildRiverBridge(path, road_direction, path->parent->node.tile, true);
 640                                 assert(IsValidTile(end_tile) && GetTileSlope(end_tile) == SLOPE_FLAT);
 641                         }
 642                 }
 643
 644                 child = path;
 645         }
 646 }
 647
 648 bool FindPath(AyStar& finder, TileIndex from, TileIndex to)
 649 {
 650         finder.CalculateG = PublicRoad_CalculateG;
 651         finder.CalculateH = PublicRoad_CalculateH;
 652         finder.GetNeighbours = PublicRoad_GetNeighbours;
 653         finder.EndNodeCheck = PublicRoad_EndNodeCheck;
 654         finder.FoundEndNode = PublicRoad_FoundEndNode;
 655         finder.user_target = &(to);
 656         finder.max_search_nodes = 1 << 20; // 1,048,576
 657
 658         finder.Init(PublicRoad_Hash, 1 << PUBLIC_ROAD_HASH_SIZE);
 659
 660         AyStarNode start;
 661         start.tile = from;
 662         start.direction = INVALID_TRACKDIR;
 663         finder.AddStartNode(&start, 0);
 664
 665         bool found_path = (finder.Main() == AYSTAR_FOUND_END_NODE);
 666
 667         return found_path;
 668 }
 669
 670 /**
 671 * Build the public road network connecting towns using AyStar.
 672 */
 673 void GeneratePublicRoads()
 674 {
 675         using namespace std;
 676
 677         if (_settings_game.game_creation.build_public_roads == PRC_NONE) return;
 678
 679         _town_centers.clear();
 680         _towns_visited_along_the_way.clear();
 681
 682         vector<TileIndex> towns;
 683         towns.clear();
 684         {
 685                 Town* town;
 686                 FOR_ALL_TOWNS(town) {
 687                         towns.push_back(town->xy);
 688                         _town_centers.push_back(town->xy);
 689                 }
 690         }
 691
 692         SetGeneratingWorldProgress(GWP_PUBLIC_ROADS, (uint)towns.size());
 693
 694         // Create a list of networks which also contain a value indicating how many times we failed to connect to them.
 695         vector<pair<uint, shared_ptr<vector<TileIndex>>>> town_networks;
 696         unordered_map<TileIndex, shared_ptr<vector<TileIndex>>> towns_reachable_networks;
 697
 698         TileIndex main_town = *towns.begin();
 699         towns.erase(towns.begin());
 700
 701         shared_ptr<vector<TileIndex>> main_network = make_shared<vector<TileIndex>>();
 702         main_network->push_back(main_town);
 703
 704         town_networks.push_back(make_pair(0, main_network));
 705         IncreaseGeneratingWorldProgress(GWP_PUBLIC_ROADS);
 706
 707         sort(towns.begin(), towns.end(), [&](auto a, auto b) { return DistanceManhattan(main_town, a) < DistanceManhattan(main_town, b); });
 708
 709         for (auto begin_town : towns) {
 710                 // Check if we can connect to any of the networks.
 711                 _towns_visited_along_the_way.clear();
 712
 713                 auto reachable_network_iter = towns_reachable_networks.find(begin_town);
 714                 bool found_easy_path = false;
 715
 716                 if (reachable_network_iter != towns_reachable_networks.end()) {
 717                         auto reachable_network = reachable_network_iter->second;
 718
 719                         sort(reachable_network->begin(), reachable_network->end(), [&](auto a, auto b) { return DistanceManhattan(begin_town, a) < DistanceManhattan(begin_town, b); });
 720
 721                         TileIndex end_town = *reachable_network->begin();
 722
 723                         AyStar finder;
 724
 725                         found_easy_path = FindPath(finder, begin_town, end_town);
 726
 727                         finder.Free();
 728                 }
 729
 730                 if (found_easy_path) {
 731                         reachable_network_iter->second->push_back(begin_town);
 732
 733                         for (const TileIndex visited_town : _towns_visited_along_the_way) {
 734                                 if (visited_town != begin_town) towns_reachable_networks[visited_town] = reachable_network_iter->second;
 735                         }
 736                 } else {
 737                         // Sort networks by failed connection attempts, so we try the most likely one first.
 738                         sort(town_networks.begin(), town_networks.end(), [&](auto a, auto b) { return a.first < b.first; });
 739
 740                         if (!any_of(town_networks.begin(), town_networks.end(), [&](auto network_pair) {
 741                                 AyStar finder;
 742
 743                                 auto network = network_pair.second;
 744
 745                                 // Try to connect to the town in the network that is closest to us.
 746                                 // If we can't connect to that one, we can't connect to any of them since they are all interconnected.
 747                                 sort(network->begin(), network->end(), [&](auto a, auto b) { return DistanceManhattan(begin_town, a) < DistanceManhattan(begin_town, b); });
 748                                 TileIndex end_town = *network->begin();
 749
 750                                 bool found_path = FindPath(finder, begin_town, end_town);
 751
 752                                 if (found_path) {
 753                                         network->push_back(begin_town);
 754
 755                                         for (auto visited_town : _towns_visited_along_the_way) {
 756                                                 if (visited_town != begin_town) towns_reachable_networks[visited_town] = network;
 757                                         }
 758                                 }
 759
 760                                 // Increase number of failed attempts if necessary.
 761                                 network_pair.first += (found_path ? (network_pair.first > 0 ? -1 : 0) : 1);
 762
 763                                 finder.Free();
 764
 765                                 return found_path;
 766
 767                         })) {
 768                                 // We failed to connect to any network, so we are a separate network. Let future towns try to connect to us.
 769                                 shared_ptr<vector<TileIndex>> new_network = make_shared<vector<TileIndex>>();
 770                                 new_network->push_back(begin_town);
 771
 772                                 // We basically failed to connect to this many towns.
 773                                 int towns_already_in_networks = std::accumulate(town_networks.begin(), town_networks.end(), 0, [&](int accumulator, auto network_pair) {
 774                                         return accumulator + (int)network_pair.second->size();
 775                                 });
 776
 777                                 town_networks.push_back(make_pair(towns_already_in_networks, new_network));
 778
 779                                 for (const TileIndex visited_town : _towns_visited_along_the_way) {
 780                                         if (visited_town != begin_town) towns_reachable_networks.insert(make_pair(visited_town, new_network));
 781                                 }
 782                         }
 783                 }
 784
 785                 IncreaseGeneratingWorldProgress(GWP_PUBLIC_ROADS);
 786         }
 787 }
 788
 789
 790 /**
 791  * Get the road type for a given label.
 792  * @param label the roadtype label.
 793  * @param allow_alternate_labels Search in the alternate label lists as well.
 794  * @return the roadtype.
 795  */
 796 RoadTypeIdentifier GetRoadTypeByLabel(RoadTypeLabel label, RoadType basetype, bool allow_alternate_labels)
 797 {
 798         RoadTypeIdentifier rtid;
 799
 800         rtid.basetype = basetype;
 801
 802         /* Loop through each road type until the label is found */
 803         for (RoadSubType r = ROADSUBTYPE_BEGIN; r != ROADSUBTYPE_END; r++) {
 804                 rtid.subtype = r;
 805                 const RoadtypeInfo *rti = GetRoadTypeInfo(rtid);
 806                 if (rti->label == label) return rtid;
 807         }
 808
 809         if (allow_alternate_labels) {
 810                 /* Test if any road type defines the label as an alternate. */
 811                 for (RoadSubType r = ROADSUBTYPE_BEGIN; r != ROADSUBTYPE_END; r++) {
 812                         rtid.subtype = r;
 813                         const RoadtypeInfo *rti = GetRoadTypeInfo(rtid);
 814                         if (rti->alternate_labels.Contains(label)) return rtid;
 815                 }
 816         }
 817
 818         /* No matching label was found, so it is invalid */
 819         rtid.basetype = INVALID_ROADTYPE;
 820         rtid.subtype = INVALID_ROADSUBTYPE;
 821         return rtid;
 822 }
 823
 824 uint8 RoadTypeIdentifier::Pack() const
 825 {
 826         assert(this->IsValid());
 827
 828         return this->basetype | (this->subtype << 1);
 829 }
 830
 831 bool RoadTypeIdentifier::UnpackIfValid(uint32 data)
 832 {
 833         this->basetype = static_cast<RoadType>(GB(data, 0, 1));
 834         this->subtype = static_cast<RoadSubType>(GB(data, 1, 5));
 835
 836         return this->IsValid();
 837 }
 838
 839 /* static */ RoadTypeIdentifier RoadTypeIdentifier::Unpack(uint32 data)
 840 {
 841         RoadTypeIdentifier result;
 842         bool ret = result.UnpackIfValid(data);
 843         assert(ret);
 844         return result;
 845 }
 846
 847 /**
 848  * Returns the available RoadSubTypes for the provided RoadType
 849  * If the given company is valid then will be returned a list of the available sub types at the current date, while passing
 850  * a deity company will make all the sub types available
 851  * @param rt the RoadType to filter
 852  * @param c the company ID to check the roadtype against
 853  * @param any_date whether to return only currently introduced roadtypes or also future ones
 854  * @returns the existing RoadSubTypes
 855  */
 856 RoadSubTypes ExistingRoadSubTypesForRoadType(RoadType rt, CompanyID c)
 857 {
 858         /* Check only players which can actually own vehicles, editor and gamescripts are considered deities */
 859         if (c < OWNER_END) {
 860                 const Company *company = Company::GetIfValid(c);
 861
 862                 if (company != NULL) return company->avail_roadtypes[rt];
 863         }
 864
 865         RoadSubTypes known_roadsubtypes = ROADSUBTYPES_NONE;
 866
 867         /* Road is always visible and available. */
 868         if (rt == ROADTYPE_ROAD) known_roadsubtypes |= ROADSUBTYPES_NORMAL; // TODO
 869
 870         /* Find used roadtypes */
 871         Engine *e;
 872         FOR_ALL_ENGINES_OF_TYPE(e, VEH_ROAD) {
 873                 /* Check if the subtype can be used in the current climate */
 874                 if (!HasBit(e->info.climates,  _settings_game.game_creation.landscape)) continue;
 875
 876                 /* Check whether available for all potential companies */
 877                 if (e->company_avail != (CompanyMask)-1) continue;
 878
 879                 RoadTypeIdentifier rtid = e->GetRoadType();
 880                 if (rtid.basetype != rt) continue;
 881
 882                 known_roadsubtypes |= GetRoadTypeInfo(rtid)->introduces_roadtypes;
 883         }
 884
 885         /* Get the date introduced roadtypes as well. */
 886         known_roadsubtypes = AddDateIntroducedRoadTypes(rt, known_roadsubtypes, MAX_DAY);
 887
 888         return known_roadsubtypes;
 889 }
 890
 891 /**
 892  * Check whether we can build infrastructure for the given RoadType. This to disable building stations etc. when
 893  * you are not allowed/able to have the RoadType yet.
 894  * @param rtid the roadtype to check this for
 895  * @param company the company id to check this for
 896  * @param any_date to check only existing vehicles or if it is possible to build them in the future
 897  * @return true if there is any reason why you may build the infrastructure for the given roadtype
 898  */
 899 bool CanBuildRoadTypeInfrastructure(RoadTypeIdentifier rtid, CompanyID company)
 900 {
 901         if (_game_mode != GM_EDITOR && !Company::IsValidID(company)) return false;
 902         if (!_settings_client.gui.disable_unsuitable_building) return true;
 903
 904         RoadSubTypes roadsubtypes = ExistingRoadSubTypesForRoadType(rtid.basetype, company);
 905
 906         /* Check if the filtered subtypes does have the subtype we are checking for
 907          * and if we can build new ones */
 908         if (_settings_game.vehicle.max_roadveh > 0 && HasBit(roadsubtypes, rtid.subtype)) {
 909                 /* Can we actually build the vehicle type? */
 910                 const Engine *e;
 911                 FOR_ALL_ENGINES_OF_TYPE(e, VEH_ROAD) {
 912                         if (HasPowerOnRoad(e->GetRoadType(), rtid) || HasPowerOnRoad(rtid, e->GetRoadType())) return true;
 913                 }
 914                 return false;
 915         }
 916
 917         /* We should be able to build infrastructure when we have the actual vehicle type */
 918         const Vehicle *v;
 919         FOR_ALL_VEHICLES(v) {
 920                 if (v->type == VEH_ROAD && (company == OWNER_DEITY || v->owner == company) &&
 921                         HasBit(roadsubtypes, RoadVehicle::From(v)->rtid.subtype) && HasPowerOnRoad(RoadVehicle::From(v)->rtid, rtid)) return true;
 922         }
 923
 924         return false;
 925 }