src/roadstop.cpp

   1 /*
   2  * This file is part of OpenTTD.
   3  * 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.
   4  * 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.
   5  * 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/>.
   6  */
   7
   8 /** @file roadstop.cpp Implementation of the roadstop base class. */
   9
  10 #include "stdafx.h"
  11 #include "roadveh.h"
  12 #include "core/pool_func.hpp"
  13 #include "roadstop_base.h"
  14 #include "station_base.h"
  15 #include "vehicle_func.h"
  16
  17 #include "safeguards.h"
  18
  19 /** The pool of roadstops. */
  20 RoadStopPool _roadstop_pool("RoadStop");
  21 INSTANTIATE_POOL_METHODS(RoadStop)
  22
  23 /**
  24  * De-Initializes RoadStops.
  25  */
  26 RoadStop::~RoadStop()
  27 {
  28         /* When we are the head we need to free the entries */
  29         if (HasBit(this->status, RSSFB_BASE_ENTRY)) {
  30                 delete this->east;
  31                 delete this->west;
  32         }
  33
  34         if (CleaningPool()) return;
  35 }
  36
  37 /**
  38  * Get the next road stop accessible by this vehicle.
  39  * @param v the vehicle to get the next road stop for.
  40  * @return the next road stop accessible.
  41  */
  42 RoadStop *RoadStop::GetNextRoadStop(const RoadVehicle *v) const
  43 {
  44         for (RoadStop *rs = this->next; rs != nullptr; rs = rs->next) {
  45                 /* The vehicle cannot go to this roadstop (different roadtype) */
  46                 if (!HasTileAnyRoadType(rs->xy, v->compatible_roadtypes)) continue;
  47                 /* The vehicle is articulated and can therefore not go to a standard road stop. */
  48                 if (IsBayRoadStopTile(rs->xy) && v->HasArticulatedPart()) continue;
  49
  50                 /* The vehicle can actually go to this road stop. So, return it! */
  51                 return rs;
  52         }
  53
  54         return nullptr;
  55 }
  56
  57 /**
  58  * Join this road stop to another 'base' road stop if possible;
  59  * fill all necessary data to become an actual drive through road stop.
  60  * Also update the length etc.
  61  */
  62 void RoadStop::MakeDriveThrough()
  63 {
  64         assert(this->east == nullptr && this->west == nullptr);
  65
  66         RoadStopType rst = GetRoadStopType(this->xy);
  67         DiagDirection dir = GetRoadStopDir(this->xy);
  68         /* Use absolute so we always go towards the northern tile */
  69         TileIndexDiff offset = abs(TileOffsByDiagDir(dir));
  70
  71         /* Information about the tile north of us */
  72         TileIndex north_tile = this->xy - offset;
  73         bool north = IsDriveThroughRoadStopContinuation(this->xy, north_tile);
  74         RoadStop *rs_north = north ? RoadStop::GetByTile(north_tile, rst) : nullptr;
  75
  76         /* Information about the tile south of us */
  77         TileIndex south_tile = this->xy + offset;
  78         bool south = IsDriveThroughRoadStopContinuation(this->xy, south_tile);
  79         RoadStop *rs_south = south ? RoadStop::GetByTile(south_tile, rst) : nullptr;
  80
  81         /* Amount of road stops that will be added to the 'northern' head */
  82         int added = 1;
  83         if (north && rs_north->east != nullptr) { // (east != nullptr) == (west != nullptr)
  84                 /* There is a more northern one, so this can join them */
  85                 this->east = rs_north->east;
  86                 this->west = rs_north->west;
  87
  88                 if (south && rs_south->east != nullptr) { // (east != nullptr) == (west != nullptr)
  89                         /* There more southern tiles too, they must 'join' us too */
  90                         ClrBit(rs_south->status, RSSFB_BASE_ENTRY);
  91                         this->east->occupied += rs_south->east->occupied;
  92                         this->west->occupied += rs_south->west->occupied;
  93
  94                         /* Free the now unneeded entry structs */
  95                         delete rs_south->east;
  96                         delete rs_south->west;
  97
  98                         /* Make all 'children' of the southern tile take the new master */
  99                         for (; IsDriveThroughRoadStopContinuation(this->xy, south_tile); south_tile += offset) {
 100                                 rs_south = RoadStop::GetByTile(south_tile, rst);
 101                                 if (rs_south->east == nullptr) break;
 102                                 rs_south->east = rs_north->east;
 103                                 rs_south->west = rs_north->west;
 104                                 added++;
 105                         }
 106                 }
 107         } else if (south && rs_south->east != nullptr) { // (east != nullptr) == (west != nullptr)
 108                 /* There is one to the south, but not to the north... so we become 'parent' */
 109                 this->east = rs_south->east;
 110                 this->west = rs_south->west;
 111                 SetBit(this->status, RSSFB_BASE_ENTRY);
 112                 ClrBit(rs_south->status, RSSFB_BASE_ENTRY);
 113         } else {
 114                 /* We are the only... so we are automatically the master */
 115                 this->east = new Entry();
 116                 this->west = new Entry();
 117                 SetBit(this->status, RSSFB_BASE_ENTRY);
 118         }
 119
 120         /* Now update the lengths */
 121         added *= TILE_SIZE;
 122         this->east->length += added;
 123         this->west->length += added;
 124 }
 125
 126 /**
 127  * Prepare for removal of this stop; update other neighbouring stops
 128  * if needed. Also update the length etc.
 129  */
 130 void RoadStop::ClearDriveThrough()
 131 {
 132         assert(this->east != nullptr && this->west != nullptr);
 133
 134         RoadStopType rst = GetRoadStopType(this->xy);
 135         DiagDirection dir = GetRoadStopDir(this->xy);
 136         /* Use absolute so we always go towards the northern tile */
 137         TileIndexDiff offset = abs(TileOffsByDiagDir(dir));
 138
 139         /* Information about the tile north of us */
 140         TileIndex north_tile = this->xy - offset;
 141         bool north = IsDriveThroughRoadStopContinuation(this->xy, north_tile);
 142         RoadStop *rs_north = north ? RoadStop::GetByTile(north_tile, rst) : nullptr;
 143
 144         /* Information about the tile south of us */
 145         TileIndex south_tile = this->xy + offset;
 146         bool south = IsDriveThroughRoadStopContinuation(this->xy, south_tile);
 147         RoadStop *rs_south = south ? RoadStop::GetByTile(south_tile, rst) : nullptr;
 148
 149         /* Must only be cleared after we determined which neighbours are
 150          * part of our little entry 'queue' */
 151         DoClearSquare(this->xy);
 152
 153         if (north) {
 154                 /* There is a tile to the north, so we can't clear ourselves. */
 155                 if (south) {
 156                         /* There are more southern tiles too, they must be split;
 157                          * first make the new southern 'base' */
 158                         SetBit(rs_south->status, RSSFB_BASE_ENTRY);
 159                         rs_south->east = new Entry();
 160                         rs_south->west = new Entry();
 161
 162                         /* Keep track of the base because we need it later on */
 163                         RoadStop *rs_south_base = rs_south;
 164                         TileIndex base_tile = south_tile;
 165
 166                         /* Make all (even more) southern stops part of the new entry queue */
 167                         for (south_tile += offset; IsDriveThroughRoadStopContinuation(base_tile, south_tile); south_tile += offset) {
 168                                 rs_south = RoadStop::GetByTile(south_tile, rst);
 169                                 rs_south->east = rs_south_base->east;
 170                                 rs_south->west = rs_south_base->west;
 171                         }
 172
 173                         /* Find the other end; the northern most tile */
 174                         for (; IsDriveThroughRoadStopContinuation(base_tile, north_tile); north_tile -= offset) {
 175                                 rs_north = RoadStop::GetByTile(north_tile, rst);
 176                         }
 177
 178                         /* We have to rebuild the entries because we cannot easily determine
 179                          * how full each part is. So instead of keeping and maintaining a list
 180                          * of vehicles and using that to 'rebuild' the occupied state we just
 181                          * rebuild it from scratch as that removes lots of maintenance code
 182                          * for the vehicle list and it's faster in real games as long as you
 183                          * do not keep split and merge road stop every tick by the millions. */
 184                         rs_south_base->east->Rebuild(rs_south_base);
 185                         rs_south_base->west->Rebuild(rs_south_base);
 186
 187                         assert(HasBit(rs_north->status, RSSFB_BASE_ENTRY));
 188                         rs_north->east->Rebuild(rs_north);
 189                         rs_north->west->Rebuild(rs_north);
 190                 } else {
 191                         /* Only we left, so simple update the length. */
 192                         rs_north->east->length -= TILE_SIZE;
 193                         rs_north->west->length -= TILE_SIZE;
 194                 }
 195         } else if (south) {
 196                 /* There is only something to the south. Hand over the base entry */
 197                 SetBit(rs_south->status, RSSFB_BASE_ENTRY);
 198                 rs_south->east->length -= TILE_SIZE;
 199                 rs_south->west->length -= TILE_SIZE;
 200         } else {
 201                 /* We were the last */
 202                 delete this->east;
 203                 delete this->west;
 204         }
 205
 206         /* Make sure we don't get used for something 'incorrect' */
 207         ClrBit(this->status, RSSFB_BASE_ENTRY);
 208         this->east = nullptr;
 209         this->west = nullptr;
 210 }
 211
 212 /**
 213  * Leave the road stop
 214  * @param rv the vehicle that leaves the stop
 215  */
 216 void RoadStop::Leave(RoadVehicle *rv)
 217 {
 218         if (IsBayRoadStopTile(rv->tile)) {
 219                 /* Vehicle is leaving a road stop tile, mark bay as free */
 220                 this->FreeBay(HasBit(rv->state, RVS_USING_SECOND_BAY));
 221                 this->SetEntranceBusy(false);
 222         } else {
 223                 /* Otherwise just leave the drive through's entry cache. */
 224                 this->GetEntry(DirToDiagDir(rv->direction))->Leave(rv);
 225         }
 226 }
 227
 228 /**
 229  * Enter the road stop
 230  * @param rv   the vehicle that enters the stop
 231  * @return whether the road stop could actually be entered
 232  */
 233 bool RoadStop::Enter(RoadVehicle *rv)
 234 {
 235         if (IsBayRoadStopTile(this->xy)) {
 236                 /* For normal (non drive-through) road stops
 237                  * Check if station is busy or if there are no free bays or whether it is a articulated vehicle. */
 238                 if (this->IsEntranceBusy() || !this->HasFreeBay() || rv->HasArticulatedPart()) return false;
 239
 240                 SetBit(rv->state, RVS_IN_ROAD_STOP);
 241
 242                 /* Allocate a bay and update the road state */
 243                 uint bay_nr = this->AllocateBay();
 244                 SB(rv->state, RVS_USING_SECOND_BAY, 1, bay_nr);
 245
 246                 /* Mark the station entrance as busy */
 247                 this->SetEntranceBusy(true);
 248                 return true;
 249         }
 250
 251         /* Vehicles entering a drive-through stop from the 'normal' side use first bay (bay 0). */
 252         this->GetEntry(DirToDiagDir(rv->direction))->Enter(rv);
 253
 254         /* Indicate a drive-through stop */
 255         SetBit(rv->state, RVS_IN_DT_ROAD_STOP);
 256         return true;
 257 }
 258
 259 /**
 260  * Find a roadstop at given tile
 261  * @param tile tile with roadstop
 262  * @param type roadstop type
 263  * @return pointer to RoadStop
 264  * @pre there has to be roadstop of given type there!
 265  */
 266 /* static */ RoadStop *RoadStop::GetByTile(TileIndex tile, RoadStopType type)
 267 {
 268         const Station *st = Station::GetByTile(tile);
 269
 270         for (RoadStop *rs = st->GetPrimaryRoadStop(type);; rs = rs->next) {
 271                 if (rs->xy == tile) return rs;
 272                 assert(rs->next != nullptr);
 273         }
 274 }
 275
 276 /**
 277  * Leave the road stop
 278  * @param rv the vehicle that leaves the stop
 279  */
 280 void RoadStop::Entry::Leave(const RoadVehicle *rv)
 281 {
 282         this->occupied -= rv->gcache.cached_total_length;
 283         assert(this->occupied >= 0);
 284 }
 285
 286 /**
 287  * Enter the road stop
 288  * @param rv the vehicle that enters the stop
 289  */
 290 void RoadStop::Entry::Enter(const RoadVehicle *rv)
 291 {
 292         /* we cannot assert on this->occupied < this->length because of the
 293          * remote possibility that RVs are running through each other when
 294          * trying to prevention an infinite jam. */
 295         this->occupied += rv->gcache.cached_total_length;
 296 }
 297
 298 /**
 299  * Checks whether the 'next' tile is still part of the road same drive through
 300  * stop 'rs' in the same direction for the same vehicle.
 301  * @param rs   the road stop tile to check against
 302  * @param next the 'next' tile to check
 303  * @return true if the 'next' tile is part of the road stop at 'next'.
 304  */
 305 /* static */ bool RoadStop::IsDriveThroughRoadStopContinuation(TileIndex rs, TileIndex next)
 306 {
 307         return IsTileType(next, MP_STATION) &&
 308                         GetStationIndex(next) == GetStationIndex(rs) &&
 309                         GetStationType(next) == GetStationType(rs) &&
 310                         GetRoadStopDir(next) == GetRoadStopDir(rs) &&
 311                         IsDriveThroughStopTile(next);
 312 }
 313
 314 typedef std::list<const RoadVehicle *> RVList; ///< A list of road vehicles
 315
 316 /** Helper for finding RVs in a road stop. */
 317 struct RoadStopEntryRebuilderHelper {
 318         RVList vehicles;   ///< The list of vehicles to possibly add to.
 319         DiagDirection dir; ///< The direction the vehicle has to face to be added.
 320 };
 321
 322 /**
 323  * Add road vehicles to the station's list if needed.
 324  * @param v the found vehicle
 325  * @param data the extra data used to make our decision
 326  * @return always nullptr
 327  */
 328 Vehicle *FindVehiclesInRoadStop(Vehicle *v, void *data)
 329 {
 330         RoadStopEntryRebuilderHelper *rserh = (RoadStopEntryRebuilderHelper*)data;
 331         /* Not a RV or not in the right direction or crashed :( */
 332         if (v->type != VEH_ROAD || DirToDiagDir(v->direction) != rserh->dir || !v->IsPrimaryVehicle() || (v->vehstatus & VS_CRASHED) != 0) return nullptr;
 333
 334         RoadVehicle *rv = RoadVehicle::From(v);
 335         /* Don't add ones not in a road stop */
 336         if (rv->state < RVSB_IN_ROAD_STOP) return nullptr;
 337
 338         /* Do not add duplicates! */
 339         for (const auto &it : rserh->vehicles) {
 340                 if (rv == it) return nullptr;
 341         }
 342
 343         rserh->vehicles.push_back(rv);
 344         return nullptr;
 345 }
 346
 347 /**
 348  * Rebuild, from scratch, the vehicles and other metadata on this stop.
 349  * @param rs   the roadstop this entry is part of
 350  * @param side the side of the road stop to look at
 351  */
 352 void RoadStop::Entry::Rebuild(const RoadStop *rs, int side)
 353 {
 354         assert(HasBit(rs->status, RSSFB_BASE_ENTRY));
 355
 356         DiagDirection dir = GetRoadStopDir(rs->xy);
 357         if (side == -1) side = (rs->east == this);
 358
 359         RoadStopEntryRebuilderHelper rserh;
 360         rserh.dir = side ? dir : ReverseDiagDir(dir);
 361
 362         this->length = 0;
 363         TileIndexDiff offset = abs(TileOffsByDiagDir(dir));
 364         for (TileIndex tile = rs->xy; IsDriveThroughRoadStopContinuation(rs->xy, tile); tile += offset) {
 365                 this->length += TILE_SIZE;
 366                 FindVehicleOnPos(tile, &rserh, FindVehiclesInRoadStop);
 367         }
 368
 369         this->occupied = 0;
 370         for (const auto &it : rserh.vehicles) {
 371                 this->occupied += it->gcache.cached_total_length;
 372         }
 373 }
 374
 375
 376 /**
 377  * Check the integrity of the data in this struct.
 378  * @param rs the roadstop this entry is part of
 379  */
 380 void RoadStop::Entry::CheckIntegrity(const RoadStop *rs) const
 381 {
 382         if (!HasBit(rs->status, RSSFB_BASE_ENTRY)) return;
 383
 384         /* The tile 'before' the road stop must not be part of this 'line' */
 385         assert(!IsDriveThroughRoadStopContinuation(rs->xy, rs->xy - abs(TileOffsByDiagDir(GetRoadStopDir(rs->xy)))));
 386
 387         Entry temp;
 388         temp.Rebuild(rs, rs->east == this);
 389         if (temp.length != this->length || temp.occupied != this->occupied) NOT_REACHED();
 390 }