src/roadstop.cpp

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