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 "command_func.h"
  31 #include "core/backup_type.hpp"
  32 #include "core/random_func.hpp"
  33
  34 #include "safeguards.h"
  35
  36 /**
  37  * Return if the tile is a valid tile for a crossing.
  38  *
  39  * @param tile the current tile
  40  * @param ax the axis of the road over the rail
  41  * @return true if it is a valid tile
  42  */
  43 static bool IsPossibleCrossing(const TileIndex tile, Axis ax)
  44 {
  45         return (IsTileType(tile, MP_RAILWAY) &&
  46                 GetRailTileType(tile) == RAIL_TILE_NORMAL &&
  47                 GetTrackBits(tile) == (ax == AXIS_X ? TRACK_BIT_Y : TRACK_BIT_X) &&
  48                 GetFoundationSlope(tile) == SLOPE_FLAT);
  49 }
  50
  51 /** Whether to build public roads */
  52 enum PublicRoadsConstruction {
  53         PRC_NONE,         ///< Generate no public roads
  54         PRC_WITH_CURVES,  ///< Generate roads with lots of curves
  55         PRC_AVOID_CURVES, ///< Generate roads avoiding curves if possible
  56 };
  57
  58 /**
  59  * Clean up unnecessary RoadBits of a planed tile.
  60  * @param tile current tile
  61  * @param org_rb planed RoadBits
  62  * @return optimised RoadBits
  63  */
  64 RoadBits CleanUpRoadBits(const TileIndex tile, RoadBits org_rb)
  65 {
  66         if (!IsValidTile(tile)) return ROAD_NONE;
  67         for (DiagDirection dir = DIAGDIR_BEGIN; dir < DIAGDIR_END; dir++) {
  68                 const TileIndex neighbor_tile = TileAddByDiagDir(tile, dir);
  69
  70                 /* Get the Roadbit pointing to the neighbor_tile */
  71                 const RoadBits target_rb = DiagDirToRoadBits(dir);
  72
  73                 /* If the roadbit is in the current plan */
  74                 if (org_rb & target_rb) {
  75                         bool connective = false;
  76                         const RoadBits mirrored_rb = MirrorRoadBits(target_rb);
  77
  78                         if (IsValidTile(neighbor_tile)) {
  79                                 switch (GetTileType(neighbor_tile)) {
  80                                         /* Always connective ones */
  81                                         case MP_CLEAR: case MP_TREES:
  82                                                 connective = true;
  83                                                 break;
  84
  85                                         /* The conditionally connective ones */
  86                                         case MP_TUNNELBRIDGE:
  87                                         case MP_STATION:
  88                                         case MP_ROAD:
  89                                                 if (IsNormalRoadTile(neighbor_tile)) {
  90                                                         /* Always connective */
  91                                                         connective = true;
  92                                                 } else {
  93                                                         const RoadBits neighbor_rb = GetAnyRoadBits(neighbor_tile, ROADTYPE_ROAD) | GetAnyRoadBits(neighbor_tile, ROADTYPE_TRAM);
  94
  95                                                         /* Accept only connective tiles */
  96                                                         connective = (neighbor_rb & mirrored_rb) != ROAD_NONE;
  97                                                 }
  98                                                 break;
  99
 100                                         case MP_RAILWAY:
 101                                                 connective = IsPossibleCrossing(neighbor_tile, DiagDirToAxis(dir));
 102                                                 break;
 103
 104                                         case MP_WATER:
 105                                                 /* Check for real water tile */
 106                                                 connective = !IsWater(neighbor_tile);
 107                                                 break;
 108
 109                                         /* The definitely not connective ones */
 110                                         default: break;
 111                                 }
 112                         }
 113
 114                         /* If the neighbor tile is inconnective, remove the planed road connection to it */
 115                         if (!connective) org_rb ^= target_rb;
 116                 }
 117         }
 118
 119         return org_rb;
 120 }
 121
 122 /**
 123  * Finds out, whether given company has all given RoadTypes available
 124  * @param company ID of company
 125  * @param rts RoadTypes to test
 126  * @return true if company has all requested RoadTypes available
 127  */
 128 bool HasRoadTypesAvail(const CompanyID company, const RoadTypes rts)
 129 {
 130         RoadTypes avail_roadtypes;
 131
 132         if (company == OWNER_DEITY || company == OWNER_TOWN || _game_mode == GM_EDITOR || _generating_world) {
 133                 avail_roadtypes = ROADTYPES_ROAD;
 134         } else {
 135                 Company *c = Company::GetIfValid(company);
 136                 if (c == NULL) return false;
 137                 avail_roadtypes = (RoadTypes)c->avail_roadtypes | ROADTYPES_ROAD; // road is available for always for everybody
 138         }
 139         return (rts & ~avail_roadtypes) == 0;
 140 }
 141
 142 /**
 143  * Validate functions for rail building.
 144  * @param rt road type to check.
 145  * @return true if the current company may build the road.
 146  */
 147 bool ValParamRoadType(const RoadType rt)
 148 {
 149         return HasRoadTypesAvail(_current_company, RoadTypeToRoadTypes(rt));
 150 }
 151
 152 /**
 153  * Get the road types the given company can build.
 154  * @param company the company to get the roadtypes for.
 155  * @return the road types.
 156  */
 157 RoadTypes GetCompanyRoadtypes(CompanyID company)
 158 {
 159         RoadTypes rt = ROADTYPES_NONE;
 160
 161         Engine *e;
 162         FOR_ALL_ENGINES_OF_TYPE(e, VEH_ROAD) {
 163                 const EngineInfo *ei = &e->info;
 164
 165                 if (HasBit(ei->climates, _settings_game.game_creation.landscape) &&
 166                                 (HasBit(e->company_avail, company) || _date >= e->intro_date + DAYS_IN_YEAR)) {
 167                         SetBit(rt, HasBit(ei->misc_flags, EF_ROAD_TRAM) ? ROADTYPE_TRAM : ROADTYPE_ROAD);
 168                 }
 169         }
 170
 171         return rt;
 172 }
 173
 174 /* ========================================================================= */
 175 /*                                PUBLIC ROADS                               */
 176 /* ========================================================================= */
 177
 178 CommandCost CmdBuildBridge(TileIndex end_tile, DoCommandFlag flags, uint32 p1, uint32 p2, const char *text = nullptr);
 179 CommandCost CmdBuildTunnel(TileIndex tile, DoCommandFlag flags, uint32 p1, uint32 p2, const char *text = nullptr);
 180 CommandCost CmdBuildRoad(TileIndex tile, DoCommandFlag flags, uint32 p1, uint32 p2, const char *text = nullptr);
 181
 182 static std::vector<TileIndex> _town_centers;
 183 static std::vector<TileIndex> _towns_visited_along_the_way;
 184 static const uint PUBLIC_ROAD_HASH_SIZE = 8U; ///< The number of bits the hash for river finding should have.
 185
 186 /**
 187 * Simple hash function for public road tiles to be used by AyStar.
 188 * @param tile The tile to hash.
 189 * @param dir The unused direction.
 190 * @return The hash for the tile.
 191 */
 192 static uint PublicRoad_Hash(uint tile, uint dir)
 193 {
 194         return GB(TileHash(TileX(tile), TileY(tile)), 0, PUBLIC_ROAD_HASH_SIZE);
 195 }
 196
 197 static const int32 BASE_COST = 1;          // Cost for utilizing an existing road, bridge, or tunnel.
 198 static const int32 COST_FOR_NEW_ROAD = 10; // Cost for building a new road.
 199 static const int32 COST_FOR_SLOPE = 5;     // Additional cost if the road heads up or down a slope.
 200
 201 /* AyStar callback for getting the cost of the current node. */
 202 static int32 PublicRoad_CalculateG(AyStar *aystar, AyStarNode *current, OpenListNode *parent)
 203 {
 204         int32 cost = BASE_COST;
 205
 206         if (!IsTileType(current->tile, MP_ROAD)) {
 207                 if (!AreTilesAdjacent(parent->path.node.tile, current->tile))
 208                 {
 209                         // We're not adjacent, so we built a tunnel or bridge.
 210                         cost += (DistanceManhattan(parent->path.node.tile, current->tile)) * COST_FOR_NEW_ROAD + 6 * COST_FOR_SLOPE;
 211                 }
 212                 else if (!IsTileFlat(current->tile)) {
 213                         cost += COST_FOR_NEW_ROAD;
 214                         cost += COST_FOR_SLOPE;
 215                 }
 216                 else
 217                 {
 218                         cost += COST_FOR_NEW_ROAD;
 219                 }
 220         }
 221
 222         if (_settings_game.game_creation.build_public_roads == PRC_AVOID_CURVES &&
 223                 parent->path.parent != nullptr &&
 224                 DiagdirBetweenTiles(parent->path.parent->node.tile, parent->path.node.tile) != DiagdirBetweenTiles(parent->path.node.tile, current->tile)) {
 225                 cost += 1;
 226         }
 227
 228         return cost;
 229 }
 230
 231 /* AyStar callback for getting the estimated cost to the destination. */
 232 static int32 PublicRoad_CalculateH(AyStar *aystar, AyStarNode *current, OpenListNode *parent)
 233 {
 234         return DistanceManhattan(*(TileIndex*)aystar->user_target, current->tile) * BASE_COST;
 235 }
 236
 237 /* Helper function to check if a tile along a certain direction is going up an inclined slope. */
 238 static bool IsUpwardsSlope(TileIndex tile, DiagDirection road_direction)
 239 {
 240         auto slope = GetTileSlope(tile);
 241
 242         if (!IsInclinedSlope(slope)) return false;
 243
 244         auto slope_direction = GetInclinedSlopeDirection(slope);
 245
 246         return road_direction == slope_direction;
 247 }
 248
 249 /* Helper function to check if a tile along a certain direction is going down an inclined slope. */
 250 static bool IsDownwardsSlope(TileIndex tile, DiagDirection road_direction)
 251 {
 252         auto slope = GetTileSlope(tile);
 253
 254         if (!IsInclinedSlope(slope)) return false;
 255
 256         auto slope_direction = GetInclinedSlopeDirection(slope);
 257
 258         return road_direction == ReverseDiagDir(slope_direction);
 259 }
 260
 261 /* Helper function to check if a road along this tile path is possible. */
 262 static bool CanBuildRoadFromTo(TileIndex begin, TileIndex end)
 263 {
 264         assert(DistanceManhattan(begin, end) == 1);
 265
 266         int heightBegin;
 267         int heightEnd;
 268         Slope slopeBegin = GetTileSlope(begin, &heightBegin);
 269         Slope slopeEnd = GetTileSlope(end, &heightEnd);
 270
 271         return
 272                 /* Slope either is inclined or flat; rivers don't support other slopes. */
 273                 (slopeEnd == SLOPE_FLAT || IsInclinedSlope(slopeEnd)) &&
 274                 /* Slope continues, then it must be lower... or either end must be flat. */
 275                 ((slopeEnd == slopeBegin && heightEnd != heightBegin) || slopeEnd == SLOPE_FLAT || slopeBegin == SLOPE_FLAT);
 276 }
 277
 278 static TileIndex BuildTunnel(PathNode *current, bool build_tunnel = false)
 279 {
 280         Backup<CompanyByte> cur_company(_current_company, OWNER_DEITY, FILE_LINE);
 281         auto build_tunnel_cmd = CmdBuildTunnel(current->node.tile, build_tunnel ? DC_EXEC : DC_NONE, ROADTYPES_ROAD | (TRANSPORT_ROAD << 8), 0);
 282         cur_company.Restore();
 283
 284         assert(!build_tunnel || build_tunnel_cmd.Succeeded());
 285         assert(!build_tunnel || (IsTileType(current->node.tile, MP_TUNNELBRIDGE) && IsTileType(_build_tunnel_endtile, MP_TUNNELBRIDGE)));
 286
 287         if (!build_tunnel_cmd.Succeeded()) return INVALID_TILE;
 288         if (!build_tunnel && !IsTileType(_build_tunnel_endtile, MP_CLEAR) && !IsTileType(_build_tunnel_endtile, MP_TREES)) return INVALID_TILE;
 289
 290         return _build_tunnel_endtile;
 291 }
 292
 293 static TileIndex BuildBridge(PathNode *current, TileIndex end_tile = INVALID_TILE, bool build_bridge = false)
 294 {
 295         TileIndex start_tile = current->node.tile;
 296
 297         DiagDirection direction = ReverseDiagDir(GetInclinedSlopeDirection(GetTileSlope(start_tile)));
 298
 299         if (!build_bridge) {
 300                 // We are not building yet, so we still need to find the end_tile.
 301                 for (TileIndex tile = start_tile + TileOffsByDiagDir(direction);
 302                         IsValidTile(tile) &&
 303                         (GetTunnelBridgeLength(start_tile, tile) <= _settings_game.construction.max_bridge_length) &&
 304                         (GetTileZ(start_tile) < (GetTileZ(tile) + _settings_game.construction.max_bridge_height)) &&
 305                         (GetTileZ(tile) <= GetTileZ(start_tile));
 306                         tile += TileOffsByDiagDir(direction)) {
 307
 308                         // No supershort bridges and always ending up on a matching upwards slope.
 309                         if (!AreTilesAdjacent(start_tile, tile) && IsUpwardsSlope(tile, direction)) {
 310                                 end_tile = tile;
 311                                 break;
 312                         }
 313                 }
 314
 315                 if (!IsValidTile(end_tile)) return INVALID_TILE;
 316                 if (!IsTileType(end_tile, MP_CLEAR) && !IsTileType(end_tile, MP_TREES)) return INVALID_TILE;
 317         }
 318
 319         assert(!build_bridge || IsValidTile(end_tile));
 320
 321         std::vector<BridgeType> available_bridge_types;
 322
 323         for (uint i = 0; i < MAX_BRIDGES; ++i) {
 324                 if (CheckBridgeAvailability((BridgeType)i, GetTunnelBridgeLength(start_tile, end_tile)).Succeeded()) {
 325                         available_bridge_types.push_back((BridgeType)i);
 326                 }
 327         }
 328
 329         assert(!build_bridge || !available_bridge_types.empty());
 330         if (available_bridge_types.empty()) return INVALID_TILE;
 331
 332         auto bridge_type = available_bridge_types[build_bridge ? RandomRange(available_bridge_types.size()) : 0];
 333
 334         Backup<CompanyByte> cur_company(_current_company, OWNER_DEITY, FILE_LINE);
 335         auto build_bridge_cmd = CmdBuildBridge(end_tile, build_bridge ? DC_EXEC : DC_NONE, start_tile, bridge_type | (ROADTYPES_ROAD << 8) | (TRANSPORT_ROAD << 15));
 336         cur_company.Restore();
 337
 338         assert(!build_bridge || build_bridge_cmd.Succeeded());
 339         assert(!build_bridge || (IsTileType(start_tile, MP_TUNNELBRIDGE) && IsTileType(end_tile, MP_TUNNELBRIDGE)));
 340
 341         if (!build_bridge_cmd.Succeeded()) return INVALID_TILE;
 342
 343         return end_tile;
 344 }
 345
 346 static TileIndex BuildRiverBridge(PathNode *current, DiagDirection road_direction, TileIndex end_tile = INVALID_TILE, bool build_bridge = false)
 347 {
 348         TileIndex start_tile = current->node.tile;
 349
 350         if (!build_bridge) {
 351                 // We are not building yet, so we still need to find the end_tile.
 352                 // We will only build a bridge if we need to cross a river, so first check for that.
 353                 TileIndex tile = start_tile + TileOffsByDiagDir(road_direction);
 354
 355                 if (!IsWaterTile(tile) || !IsRiver(tile)) return INVALID_TILE;
 356
 357                 // 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.
 358                 // 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
 359                 // should not force that on them. This is just to bridge rivers, not to make long bridges.
 360                 for (;
 361                         IsValidTile(tile) &&
 362                         (GetTunnelBridgeLength(start_tile, tile) <= 5) &&
 363                         (GetTileZ(start_tile) < (GetTileZ(tile) + _settings_game.construction.max_bridge_height)) &&
 364                         (GetTileZ(tile) <= GetTileZ(start_tile));
 365                         tile += TileOffsByDiagDir(road_direction)) {
 366
 367                         if ((IsTileType(tile, MP_CLEAR) || IsTileType(tile, MP_TREES)) &&
 368                                 GetTileZ(tile) <= GetTileZ(start_tile) &&
 369                                 GetTileSlope(tile) == SLOPE_FLAT) {
 370                                 end_tile = tile;
 371                                 break;
 372                         }
 373                 }
 374
 375                 if (!IsValidTile(end_tile)) return INVALID_TILE;
 376                 if (!IsTileType(end_tile, MP_CLEAR) && !IsTileType(end_tile, MP_TREES)) return INVALID_TILE;
 377         }
 378
 379         assert(!build_bridge || IsValidTile(end_tile));
 380
 381         std::vector<BridgeType> available_bridge_types;
 382
 383         for (uint i = 0; i < MAX_BRIDGES; ++i) {
 384                 if (CheckBridgeAvailability((BridgeType)i, GetTunnelBridgeLength(start_tile, end_tile)).Succeeded()) {
 385                         available_bridge_types.push_back((BridgeType)i);
 386                 }
 387         }
 388
 389         auto bridge_type = available_bridge_types[build_bridge ? RandomRange(available_bridge_types.size()) : 0];
 390
 391         Backup<CompanyByte> cur_company(_current_company, OWNER_DEITY, FILE_LINE);
 392         auto build_bridge_cmd = CmdBuildBridge(end_tile, build_bridge ? DC_EXEC : DC_NONE, start_tile, bridge_type | (ROADTYPES_ROAD << 8) | (TRANSPORT_ROAD << 15));
 393         cur_company.Restore();
 394
 395         assert(!build_bridge || build_bridge_cmd.Succeeded());
 396         assert(!build_bridge || (IsTileType(start_tile, MP_TUNNELBRIDGE) && IsTileType(end_tile, MP_TUNNELBRIDGE)));
 397
 398         if (!build_bridge_cmd.Succeeded()) return INVALID_TILE;
 399
 400         return end_tile;
 401 }
 402
 403 static bool IsValidNeighbourOfPreviousTile(TileIndex tile, TileIndex previous_tile)
 404 {
 405         if (!IsValidTile(tile)) return false;
 406
 407         if (IsTileType(tile, MP_TUNNELBRIDGE))
 408         {
 409                 if (GetOtherTunnelBridgeEnd(tile) == previous_tile) return true;
 410
 411                 auto tunnel_direction = GetTunnelBridgeDirection(tile);
 412
 413                 if (previous_tile + TileOffsByDiagDir(tunnel_direction) != tile) return false;
 414         } else {
 415
 416                 if (!IsTileType(tile, MP_CLEAR) && !IsTileType(tile, MP_TREES) && !IsTileType(tile, MP_ROAD)) return false;
 417
 418                 auto slope = GetTileSlope(tile);
 419
 420                 // Do not allow foundations. We'll mess things up later.
 421                 bool hasFoundation = GetFoundationSlope(tile) != slope;
 422                 if (hasFoundation) return false;
 423
 424                 if (IsInclinedSlope(slope)) {
 425                         auto slope_direction = GetInclinedSlopeDirection(slope);
 426                         auto road_direction = DiagdirBetweenTiles(previous_tile, tile);
 427
 428                         if (slope_direction != road_direction && ReverseDiagDir(slope_direction) != road_direction) return false;
 429                 } else if (slope != SLOPE_FLAT) {
 430                         return false;
 431                 }
 432         }
 433
 434         return true;
 435 }
 436
 437 /* AyStar callback for getting the neighbouring nodes of the given node. */
 438 static void PublicRoad_GetNeighbours(AyStar *aystar, OpenListNode *current)
 439 {
 440         TileIndex tile = current->path.node.tile;
 441
 442         aystar->num_neighbours = 0;
 443
 444         // Check if we just went through a tunnel or a bridge.
 445         if (current->path.parent != nullptr && !AreTilesAdjacent(tile, current->path.parent->node.tile)) {
 446                 auto previous_tile = current->path.parent->node.tile;
 447                 // We went through a tunnel or bridge, this limits our options to proceed to only forward.
 448                 auto tunnel_bridge_direction = DiagdirBetweenTiles(previous_tile, tile);
 449
 450                 TileIndex t2 = tile + TileOffsByDiagDir(tunnel_bridge_direction);
 451                 if (IsValidNeighbourOfPreviousTile(t2, tile)) {
 452                         aystar->neighbours[aystar->num_neighbours].tile = t2;
 453                         aystar->neighbours[aystar->num_neighbours].direction = INVALID_TRACKDIR;
 454                         aystar->num_neighbours++;
 455                 }
 456         } else {
 457                 // Handle all the regular neighbours and existing tunnels/bridges.
 458                 std::vector<TileIndex> potential_neighbours;
 459
 460                 if (IsTileType(tile, MP_TUNNELBRIDGE)) {
 461                         auto neighbour = GetOtherTunnelBridgeEnd(tile);
 462
 463                         aystar->neighbours[aystar->num_neighbours].tile = neighbour;
 464                         aystar->neighbours[aystar->num_neighbours].direction = INVALID_TRACKDIR;
 465                         aystar->num_neighbours++;
 466
 467                         neighbour = tile + TileOffsByDiagDir(ReverseDiagDir(DiagdirBetweenTiles(tile, neighbour)));
 468
 469                         if (IsValidNeighbourOfPreviousTile(neighbour, tile)) {
 470                                 aystar->neighbours[aystar->num_neighbours].tile = neighbour;
 471                                 aystar->neighbours[aystar->num_neighbours].direction = INVALID_TRACKDIR;
 472                                 aystar->num_neighbours++;
 473                         }
 474                 } else {
 475                         for (DiagDirection d = DIAGDIR_BEGIN; d < DIAGDIR_END; d++) {
 476                                 auto neighbour = tile + TileOffsByDiagDir(d);
 477                                 if (IsValidNeighbourOfPreviousTile(neighbour, tile)) {
 478                                         aystar->neighbours[aystar->num_neighbours].tile = neighbour;
 479                                         aystar->neighbours[aystar->num_neighbours].direction = INVALID_TRACKDIR;
 480                                         aystar->num_neighbours++;
 481                                 }
 482                         }
 483
 484                         // Check if we can turn this into a tunnel or a bridge.
 485                         if (current->path.parent != nullptr) {
 486                                 auto road_direction = DiagdirBetweenTiles(current->path.parent->node.tile, tile);
 487                                 if (IsUpwardsSlope(tile, road_direction)) {
 488                                         auto tunnel_end = BuildTunnel(&current->path);
 489
 490                                         if (tunnel_end != INVALID_TILE) {
 491                                                 assert(IsValidDiagDirection(DiagdirBetweenTiles(tile, tunnel_end)));
 492                                                 aystar->neighbours[aystar->num_neighbours].tile = tunnel_end;
 493                                                 aystar->neighbours[aystar->num_neighbours].direction = INVALID_TRACKDIR;
 494                                                 aystar->num_neighbours++;
 495                                         }
 496                                 }
 497                                 else if (IsDownwardsSlope(tile, road_direction)) {
 498                                         auto bridge_end = BuildBridge(&current->path);
 499
 500                                         if (bridge_end != INVALID_TILE) {
 501                                                 assert(IsValidDiagDirection(DiagdirBetweenTiles(tile, bridge_end)));
 502                                                 aystar->neighbours[aystar->num_neighbours].tile = bridge_end;
 503                                                 aystar->neighbours[aystar->num_neighbours].direction = INVALID_TRACKDIR;
 504                                                 aystar->num_neighbours++;
 505                                         }
 506                                 }
 507                                 else if (GetTileSlope(tile) == SLOPE_FLAT)
 508                                 {
 509                                         // 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.
 510                                         auto bridge_end = BuildRiverBridge(&current->path, DiagdirBetweenTiles(current->path.parent->node.tile, tile));
 511                                         assert(bridge_end == INVALID_TILE || GetTileSlope(bridge_end) == SLOPE_FLAT);
 512
 513                                         if (bridge_end != INVALID_TILE) {
 514                                                 assert(IsValidDiagDirection(DiagdirBetweenTiles(tile, bridge_end)));
 515                                                 aystar->neighbours[aystar->num_neighbours].tile = bridge_end;
 516                                                 aystar->neighbours[aystar->num_neighbours].direction = INVALID_TRACKDIR;
 517                                                 aystar->num_neighbours++;
 518                                         }
 519
 520                                 }
 521                         }
 522                 }
 523         }
 524 }
 525
 526 /* AyStar callback for checking whether we reached our destination. */
 527 static int32 PublicRoad_EndNodeCheck(AyStar *aystar, OpenListNode *current)
 528 {
 529         // Mark towns visited along the way.
 530         auto search_result = std::find(_town_centers.begin(), _town_centers.end(), current->path.node.tile);
 531
 532         if (search_result != _town_centers.end()) {
 533                 _towns_visited_along_the_way.push_back(current->path.node.tile);
 534         };
 535
 536         return current->path.node.tile == *(TileIndex*)aystar->user_target ? AYSTAR_FOUND_END_NODE : AYSTAR_DONE;
 537 }
 538
 539 /* AyStar callback when an route has been found. */
 540 static void PublicRoad_FoundEndNode(AyStar *aystar, OpenListNode *current)
 541 {
 542         PathNode* child = nullptr;
 543
 544         for (PathNode *path = &current->path; path != NULL; path = path->parent) {
 545                 TileIndex tile = path->node.tile;
 546
 547                 TownID townID = CalcClosestTownFromTile(tile)->index;
 548
 549                 if (IsTileType(tile, MP_TUNNELBRIDGE)) {
 550                         // Just follow the path; infrastructure is already in place.
 551                         continue;
 552                 } else if (path->parent == nullptr || AreTilesAdjacent(tile, path->parent->node.tile)) {
 553                         RoadBits road_bits = ROAD_NONE;
 554
 555                         if (child != nullptr) {
 556                                 TileIndex tile2 = child->node.tile;
 557                                 road_bits |= DiagDirToRoadBits(DiagdirBetweenTiles(tile, tile2));
 558                         }
 559                         if (path->parent != nullptr) {
 560                                 TileIndex tile2 = path->parent->node.tile;
 561                                 road_bits |= DiagDirToRoadBits(DiagdirBetweenTiles(tile, tile2));
 562                         }
 563
 564                         if (child != nullptr || path->parent != nullptr) {
 565                                 // Check if we need to build anything.
 566                                 bool need_to_build_road = true;
 567
 568                                 if (IsTileType(tile, MP_ROAD)) {
 569                                         RoadBits existing_bits = GetRoadBits(tile, ROADTYPE_ROAD);
 570                                         CLRBITS(road_bits, existing_bits);
 571                                         if (road_bits == ROAD_NONE) need_to_build_road = false;
 572                                 }
 573
 574                                 // If it is already a road and has the right bits, we are good. Otherwise build the needed ones.
 575                                 if (need_to_build_road)
 576                                 {
 577                                         Backup<CompanyByte> cur_company(_current_company, OWNER_DEITY, FILE_LINE);
 578                                         auto road_built = CmdBuildRoad(tile, DC_EXEC, ROADTYPE_ROAD << 4 | road_bits, 0);
 579                                         cur_company.Restore();
 580                                 }
 581                         }
 582                 } else {
 583                         // We only get here if we have a parent and we're not adjacent to it. River/Tunnel time!
 584                         DiagDirection road_direction = DiagdirBetweenTiles(tile, path->parent->node.tile);
 585
 586                         auto end_tile = INVALID_TILE;
 587
 588                         auto start_slope = GetTileSlope(tile);
 589
 590                         if (IsUpwardsSlope(tile, road_direction)) {
 591                                 end_tile = BuildTunnel(path, true);
 592                                 assert(IsValidTile(end_tile) && IsDownwardsSlope(end_tile, road_direction));
 593                         } else if (IsDownwardsSlope(tile, road_direction)) {
 594                                 // Provide the function with the end tile, since we already know it, but still check the result.
 595                                 end_tile = BuildBridge(path, path->parent->node.tile, true);
 596                                 assert(IsValidTile(end_tile) && IsUpwardsSlope(end_tile, road_direction));
 597                         } else {
 598                                 // River bridge is the last possibility.
 599                                 assert(GetTileSlope(tile) == SLOPE_FLAT);
 600                                 end_tile = BuildRiverBridge(path, road_direction, path->parent->node.tile, true);
 601                                 assert(IsValidTile(end_tile) && GetTileSlope(end_tile) == SLOPE_FLAT);
 602                         }
 603                 }
 604
 605                 child = path;
 606         }
 607 }
 608
 609 bool FindPath(AyStar& finder, TileIndex from, TileIndex to)
 610 {
 611         finder.CalculateG = PublicRoad_CalculateG;
 612         finder.CalculateH = PublicRoad_CalculateH;
 613         finder.GetNeighbours = PublicRoad_GetNeighbours;
 614         finder.EndNodeCheck = PublicRoad_EndNodeCheck;
 615         finder.FoundEndNode = PublicRoad_FoundEndNode;
 616         finder.user_target = &(to);
 617         finder.max_search_nodes = 1 << 20; // 1,048,576
 618
 619         finder.Init(PublicRoad_Hash, 1 << PUBLIC_ROAD_HASH_SIZE);
 620
 621         AyStarNode start;
 622         start.tile = from;
 623         start.direction = INVALID_TRACKDIR;
 624         finder.AddStartNode(&start, 0);
 625
 626         bool found_path = (finder.Main() == AYSTAR_FOUND_END_NODE);
 627
 628         return found_path;
 629 }
 630
 631 /**
 632 * Build the public road network connecting towns using AyStar.
 633 */
 634 void GeneratePublicRoads()
 635 {
 636         using namespace std;
 637
 638         if (_settings_game.game_creation.build_public_roads == PRC_NONE) return;
 639
 640         _town_centers.clear();
 641         _towns_visited_along_the_way.clear();
 642
 643         vector<TileIndex> towns;
 644         towns.clear();
 645         {
 646                 Town* town;
 647                 FOR_ALL_TOWNS(town) {
 648                         towns.push_back(town->xy);
 649                         _town_centers.push_back(town->xy);
 650                 }
 651         }
 652
 653         SetGeneratingWorldProgress(GWP_PUBLIC_ROADS, towns.size());
 654
 655         // Create a list of networks which also contain a value indicating how many times we failed to connect to them.
 656         vector<pair<uint, shared_ptr<vector<TileIndex>>>> town_networks;
 657         unordered_map<TileIndex, shared_ptr<vector<TileIndex>>> towns_reachable_networks;
 658
 659         TileIndex main_town = *towns.begin();
 660         towns.erase(towns.begin());
 661
 662         shared_ptr<vector<TileIndex>> main_network = make_shared<vector<TileIndex>>();
 663         main_network->push_back(main_town);
 664
 665         town_networks.push_back(make_pair(0, main_network));
 666         IncreaseGeneratingWorldProgress(GWP_PUBLIC_ROADS);
 667
 668         sort(towns.begin(), towns.end(), [&](auto a, auto b) { return DistanceManhattan(main_town, a) < DistanceManhattan(main_town, b); });
 669
 670         for (auto begin_town : towns) {
 671                 // Check if we can connect to any of the networks.
 672                 _towns_visited_along_the_way.clear();
 673
 674                 auto reachable_network_iter = towns_reachable_networks.find(begin_town);
 675                 bool found_easy_path = false;
 676
 677                 if (reachable_network_iter != towns_reachable_networks.end()) {
 678                         auto reachable_network = reachable_network_iter->second;
 679
 680                         sort(reachable_network->begin(), reachable_network->end(), [&](auto a, auto b) { return DistanceManhattan(begin_town, a) < DistanceManhattan(begin_town, b); });
 681
 682                         TileIndex end_town = *reachable_network->begin();
 683
 684                         AyStar finder;
 685
 686                         found_easy_path = FindPath(finder, begin_town, end_town);
 687
 688                         finder.Free();
 689                 }
 690
 691                 if (found_easy_path) {
 692                         reachable_network_iter->second->push_back(begin_town);
 693
 694                         for (const TileIndex visited_town : _towns_visited_along_the_way) {
 695                                 if (visited_town != begin_town) towns_reachable_networks[visited_town] = reachable_network_iter->second;
 696                         }
 697                 } else {
 698                         // Sort networks by failed connection attempts, so we try the most likely one first.
 699                         sort(town_networks.begin(), town_networks.end(), [&](auto a, auto b) { return a.first < b.first; });
 700
 701                         if (!any_of(town_networks.begin(), town_networks.end(), [&](auto network_pair) {
 702                                 AyStar finder;
 703
 704                                 auto network = network_pair.second;
 705
 706                                 // Try to connect to the town in the network that is closest to us.
 707                                 // If we can't connect to that one, we can't connect to any of them since they are all interconnected.
 708                                 sort(network->begin(), network->end(), [&](auto a, auto b) { return DistanceManhattan(begin_town, a) < DistanceManhattan(begin_town, b); });
 709                                 TileIndex end_town = *network->begin();
 710
 711                                 bool found_path = FindPath(finder, begin_town, end_town);
 712
 713                                 if (found_path) {
 714                                         network->push_back(begin_town);
 715
 716                                         for (auto visited_town : _towns_visited_along_the_way) {
 717                                                 if (visited_town != begin_town) towns_reachable_networks[visited_town] = network;
 718                                         }
 719                                 }
 720
 721                                 // Increase number of failed attempts if necessary.
 722                                 network_pair.first += (found_path ? (network_pair.first > 0 ? -1 : 0) : 1);
 723
 724                                 finder.Free();
 725
 726                                 return found_path;
 727
 728                         })) {
 729                                 // We failed to connect to any network, so we are a separate network. Let future towns try to connect to us.
 730                                 shared_ptr<vector<TileIndex>> new_network = make_shared<vector<TileIndex>>();
 731                                 new_network->push_back(begin_town);
 732
 733                                 // We basically failed to connect to this many towns.
 734                                 int towns_already_in_networks = std::accumulate(town_networks.begin(), town_networks.end(), 0, [&](int accumulator, auto network_pair) {
 735                                         return accumulator + network_pair.second->size();
 736                                 });
 737
 738                                 town_networks.push_back(make_pair(towns_already_in_networks, new_network));
 739
 740                                 for (const TileIndex visited_town : _towns_visited_along_the_way) {
 741                                         if (visited_town != begin_town) towns_reachable_networks.insert(make_pair(visited_town, new_network));
 742                                 }
 743                         }
 744                 }
 745
 746                 IncreaseGeneratingWorldProgress(GWP_PUBLIC_ROADS);
 747         }
 748 }