From 8b1b3fd0f91fd30d09d3acaa65bd9a7d23d966cc Mon Sep 17 00:00:00 2001 From: Peter Nelson Date: Thu, 14 Feb 2019 21:07:15 +0000 Subject: Feature: Non-rectangular sparse station catchment area. --- src/station.cpp | 169 +++++++++++++++++++++++++++++++++++++++++--------------- 1 file changed, 124 insertions(+), 45 deletions(-) (limited to 'src/station.cpp') diff --git a/src/station.cpp b/src/station.cpp index 2fc1bdb45..27063dcd7 100644 --- a/src/station.cpp +++ b/src/station.cpp @@ -23,6 +23,7 @@ #include "station_base.h" #include "roadstop_base.h" #include "industry.h" +#include "town.h" #include "core/random_func.hpp" #include "linkgraph/linkgraph.h" #include "linkgraph/linkgraphschedule.h" @@ -119,6 +120,9 @@ Station::~Station() } } + /* Remove station from industries and towns that reference it. */ + this->RemoveFromAllNearbyLists(); + /* Clear the persistent storage. */ delete this->airport.psa; @@ -261,6 +265,39 @@ void Station::MarkTilesDirty(bool cargo_change) const return length; } +/** + * Get the catchment size of an individual station tile. + * @param tile Station tile to get catchment size of. + * @param st Associated station of station tile. + * @pre IsTileType(tile, MP_STATION) + * @return The catchment size of the station tile. + */ +static uint GetTileCatchmentRadius(TileIndex tile, const Station *st) +{ + assert(IsTileType(tile, MP_STATION)); + + if (_settings_game.station.modified_catchment) { + switch (GetStationType(tile)) { + case STATION_RAIL: return CA_TRAIN; + case STATION_OILRIG: return CA_UNMODIFIED; + case STATION_AIRPORT: return st->airport.GetSpec()->catchment; + case STATION_TRUCK: return CA_TRUCK; + case STATION_BUS: return CA_BUS; + case STATION_DOCK: return CA_DOCK; + + default: NOT_REACHED(); + case STATION_BUOY: + case STATION_WAYPOINT: return CA_NONE; + } + } else { + switch (GetStationType(tile)) { + default: return CA_UNMODIFIED; + case STATION_BUOY: + case STATION_WAYPOINT: return CA_NONE; + } + } +} + /** * Determines the catchment radius of the station * @return The radius @@ -305,85 +342,127 @@ Rect Station::GetCatchmentRect() const return ret; } -/** Rect and pointer to IndustryVector */ -struct RectAndIndustryVector { - Rect rect; ///< The rectangle to search the industries in. - IndustryList *industries_near; ///< The nearby industries. -}; - /** - * Callback function for Station::RecomputeIndustriesNear() - * Tests whether tile is an industry and possibly adds - * the industry to station's industries_near list. - * @param ind_tile tile to check - * @param user_data pointer to RectAndIndustryVector - * @return always false, we want to search all tiles + * Add nearby industry to station's industries_near list if it accepts cargo. + * @param ind Industry + * @param st Station */ -static bool FindIndustryToDeliver(TileIndex ind_tile, void *user_data) +static void AddIndustryToDeliver(Industry *ind, Station *st) { - /* Only process industry tiles */ - if (!IsTileType(ind_tile, MP_INDUSTRY)) return false; - - RectAndIndustryVector *riv = (RectAndIndustryVector *)user_data; - Industry *ind = Industry::GetByTile(ind_tile); - /* Don't check further if this industry is already in the list */ - if (riv->industries_near->find(ind) != riv->industries_near->end()) return false; - - /* Only process tiles in the station acceptance rectangle */ - int x = TileX(ind_tile); - int y = TileY(ind_tile); - if (x < riv->rect.left || x > riv->rect.right || y < riv->rect.top || y > riv->rect.bottom) return false; + if (st->industries_near.find(ind) != st->industries_near.end()) return; /* Include only industries that can accept cargo */ uint cargo_index; for (cargo_index = 0; cargo_index < lengthof(ind->accepts_cargo); cargo_index++) { if (ind->accepts_cargo[cargo_index] != CT_INVALID) break; } - if (cargo_index >= lengthof(ind->accepts_cargo)) return false; + if (cargo_index >= lengthof(ind->accepts_cargo)) return; - riv->industries_near->insert(ind); + st->industries_near.insert(ind); +} + +/** + * Remove this station from the nearby stations lists of all towns and industries. + */ +void Station::RemoveFromAllNearbyLists() +{ + Town *t; + FOR_ALL_TOWNS(t) { t->stations_near.erase(this); } + Industry *i; + FOR_ALL_INDUSTRIES(i) { i->stations_near.erase(this); } +} +/** + * Test if the given town ID is covered by our catchment area. + * This is used when removing a house tile to determine if it was the last house tile + * within our catchment. + * @param t TownID to test. + * @return true if at least one house tile of TownID is covered. + */ +bool Station::CatchmentCoversTown(TownID t) const +{ + BitmapTileIterator it(this->catchment_tiles); + for (TileIndex tile = it; tile != INVALID_TILE; tile = ++it) { + if (IsTileType(tile, MP_HOUSE) && GetTownIndex(tile) == t) return true; + } return false; } /** - * Recomputes Station::industries_near, list of industries possibly - * accepting cargo in station's catchment radius + * Recompute tiles covered in our catchment area. + * This will additionally recompute nearby towns and industries. */ -void Station::RecomputeIndustriesNear() +void Station::RecomputeCatchment() { this->industries_near.clear(); - if (this->rect.IsEmpty()) return; + this->RemoveFromAllNearbyLists(); + + if (this->rect.IsEmpty()) { + this->catchment_tiles.Reset(); + return; + } + this->catchment_tiles.Initialize(GetCatchmentRect()); if (!_settings_game.station.serve_neutral_industries && this->industry != NULL) { /* Station is associated with an industry, so we only need to deliver to that industry. */ + TILE_AREA_LOOP(tile, this->industry->location) { + if (IsTileType(tile, MP_INDUSTRY) && GetIndustryIndex(tile) == this->industry->index) { + this->catchment_tiles.SetTile(tile); + } + } + /* The industry's stations_near may have been computed before its neutral station was built so clear and re-add here. */ + for (Station *st : this->industry->stations_near) { + st->industries_near.erase(this->industry); + } + this->industry->stations_near.clear(); + this->industry->stations_near.insert(this); this->industries_near.insert(this->industry); return; } - RectAndIndustryVector riv = { - this->GetCatchmentRect(), - &this->industries_near - }; + /* Loop finding all station tiles */ + TileArea ta(TileXY(this->rect.left, this->rect.top), TileXY(this->rect.right, this->rect.bottom)); + TILE_AREA_LOOP(tile, ta) { + if (!IsTileType(tile, MP_STATION) || GetStationIndex(tile) != this->index) continue; + + uint r = GetTileCatchmentRadius(tile, this); + if (r == CA_NONE) continue; + + /* This tile sub-loop doesn't need to test any tiles, they are simply added to the catchment set. */ + TileArea ta2(TileXY(max(TileX(tile) - r, 0), max(TileY(tile) - r, 0)), TileXY(min(TileX(tile) + r, MapMaxX()), min(TileY(tile) + r, MapMaxY()))); + TILE_AREA_LOOP(tile2, ta2) this->catchment_tiles.SetTile(tile2); + } - /* Compute maximum extent of acceptance rectangle wrt. station sign */ - TileIndex start_tile = this->xy; - uint max_radius = max( - max(DistanceManhattan(start_tile, TileXY(riv.rect.left, riv.rect.top)), DistanceManhattan(start_tile, TileXY(riv.rect.left, riv.rect.bottom))), - max(DistanceManhattan(start_tile, TileXY(riv.rect.right, riv.rect.top)), DistanceManhattan(start_tile, TileXY(riv.rect.right, riv.rect.bottom))) - ); + /* Search catchment tiles for towns and industries */ + BitmapTileIterator it(this->catchment_tiles); + for (TileIndex tile = it; tile != INVALID_TILE; tile = ++it) { + if (IsTileType(tile, MP_HOUSE)) { + Town *t = Town::GetByTile(tile); + t->stations_near.insert(this); + } + if (IsTileType(tile, MP_INDUSTRY)) { + Industry *i = Industry::GetByTile(tile); + + /* Ignore industry if it has a neutral station. It already can't be this station. */ + if (!_settings_game.station.serve_neutral_industries && i->neutral_station != NULL) continue; + + i->stations_near.insert(this); - CircularTileSearch(&start_tile, 2 * max_radius + 1, &FindIndustryToDeliver, &riv); + /* Add if we can deliver to this industry as well */ + AddIndustryToDeliver(i, this); + } + } } /** - * Recomputes Station::industries_near for all stations + * Recomputes catchment of all stations. + * This will additionally recompute nearby stations for all towns and industries. */ -/* static */ void Station::RecomputeIndustriesNearForAll() +/* static */ void Station::RecomputeCatchmentForAll() { Station *st; - FOR_ALL_STATIONS(st) st->RecomputeIndustriesNear(); + FOR_ALL_STATIONS(st) { st->RecomputeCatchment(); } } /************************************************************************/ -- cgit v1.2.3-54-g00ecf