Mercurial > hg > openttd
changeset 5395:14fd6d7d9cfc draft
(svn r7585) -Codechange: CheckStationSpreadOut() took too much CPU. Station rectangle is now maintained instead of calculating it each time by walking through whole map. Should help with the performance issue related to AIs trying to build road stops too often. (idea by Celestar)
author | KUDr <KUDr@openttd.org> |
---|---|
date | Wed, 27 Dec 2006 23:11:43 +0000 |
parents | 6a8700f3706c |
children | 95f0fd277635 |
files | station.h station_cmd.c |
diffstat | 2 files changed, 180 insertions(+), 36 deletions(-) [+] |
line wrap: on
line diff
--- a/station.h +++ b/station.h @@ -47,6 +47,15 @@ uint8 localidx; /// Station ID within GRF of station } StationSpecList; +/** Station spread out rectangle (not saved) */ +typedef struct StationRect +{ + uint16 left; + uint16 top; + uint16 right; + uint16 bottom; +} StationRect; + struct Station { TileIndex xy; RoadStop *bus_stops; @@ -94,6 +103,8 @@ byte truck_stop_status_obsolete; byte bus_stop_status_obsolete; byte blocked_months_obsolete; + + StationRect rect; }; enum {
--- a/station_cmd.c +++ b/station_cmd.c @@ -34,6 +34,14 @@ #include "yapf/yapf.h" #include "date.h" +static void StationRect_Init(Station *st); +static bool StationRect_IsEmpty(Station *st); +static bool StationRect_BeforeAddTile(Station *st, TileIndex tile, bool exec); +static bool StationRect_BeforeAddRect(Station *st, TileIndex tile, uint16 w, uint16 h, bool exec); +static bool StationRect_AfterRemoveTile(Station *st, TileIndex tile); +static bool StationRect_AfterRemoveRect(Station *st, TileIndex tile, uint16 w, uint16 h); + + /** * Called if a new block is added to the station-pool */ @@ -468,6 +476,7 @@ st->random_bits = Random(); st->waiting_triggers = 0; + StationRect_Init(st); } // Update the virtual coords needed to draw the station sign. @@ -733,38 +742,14 @@ InvalidateWindowWidget(WC_STATION_VIEW, st->index, 4); } -static bool CheckStationSpreadOut(Station *st, TileIndex tile, int w, int h) -{ - StationID station_index = st->index; - uint x1 = TileX(tile); - uint y1 = TileY(tile); - ottd_Rectangle r = {x1, y1, x1 + w - 1, y1 + h - 1}; - // get station bounding rect - for (tile = 0; tile < MapSize(); tile++) { - if (IsTileType(tile, MP_STATION) && GetStationIndex(tile) == station_index) MergePoint(&r, tile); - } - // check if bounding rect doesn't exceed the maximum station spread - if (r.max_x - r.min_x >= _patches.station_spread || r.max_y - r.min_y >= _patches.station_spread) { - _error_message = STR_306C_STATION_TOO_SPREAD_OUT; - return false; - } - return true; -} - static void UpdateStationSignCoord(Station *st) { - ottd_Rectangle r = {MapSizeX(), MapSizeY(), 0, 0}; - TileIndex tile; - - // get station bounding rect - for (tile = 0; tile < MapSize(); tile++) { - if (IsTileType(tile, MP_STATION) && GetStationIndex(tile) == st->index) MergePoint(&r, tile); - } - - if (r.max_x < r.min_x) return; // no tiles belong to this station - - // clamp sign coord to be inside the rect - st->xy = TileXY(clampu(TileX(st->xy), r.min_x, r.max_x), clampu(TileY(st->xy), r.min_y, r.max_y)); + StationRect *r = &st->rect; + + if (StationRect_IsEmpty(st)) return; // no tiles belong to this station + + // clamp sign coord to be inside the station rect + st->xy = TileXY(clampu(TileX(st->xy), r->left, r->right), clampu(TileY(st->xy), r->top, r->bottom)); UpdateStationVirtCoordDirty(st); } @@ -1041,7 +1026,7 @@ } //XXX can't we pack this in the "else" part of the if above? - if (!CheckStationSpreadOut(st, tile_org, w_org, h_org)) return CMD_ERROR; + if (!StationRect_BeforeAddRect(st, tile_org, w_org, h_org, false)) return CMD_ERROR; } else { // Create a new station st = AllocateStation(); @@ -1100,6 +1085,8 @@ st->build_date = _date; + StationRect_BeforeAddRect(st, tile_org, w_org, h_org, true); + tile_delta = (axis == AXIS_X ? TileDiffXY(1, 0) : TileDiffXY(0, 1)); track = AxisToTrack(axis); @@ -1220,6 +1207,7 @@ uint specindex = GetCustomStationSpecIndex(tile); Track track = GetRailStationTrack(tile); DoClearSquare(tile); + StationRect_AfterRemoveTile(st, tile); SetSignalsOnBothDir(tile, track); YapfNotifyTrackLayoutChange(tile, track); @@ -1336,7 +1324,10 @@ } while (--h); if (flags & DC_EXEC) { + StationRect_AfterRemoveRect(st, st->train_tile, st->trainst_w, st->trainst_h); + st->train_tile = 0; + st->trainst_w = st->trainst_h = 0; st->facilities &= ~FACIL_TRAIN; free(st->speclist); @@ -1462,7 +1453,7 @@ return_cmd_error(STR_3009_TOO_CLOSE_TO_ANOTHER_STATION); } - if (!CheckStationSpreadOut(st, tile, 1, 1)) return CMD_ERROR; + if (!StationRect_BeforeAddTile(st, tile, false)) return CMD_ERROR; FindRoadStopSpot(type, st, &currstop, &prev); } else { @@ -1500,6 +1491,8 @@ st->build_date = _date; + StationRect_BeforeAddTile(st, tile, true); + MakeRoadStop(tile, st->owner, st->index, type, p1); UpdateStationVirtCoordDirty(st); @@ -1547,6 +1540,7 @@ DeleteRoadStop(cur_stop); DoClearSquare(tile); + StationRect_AfterRemoveTile(st, tile); UpdateStationVirtCoordDirty(st); DeleteStationIfEmpty(st); @@ -1708,8 +1702,7 @@ if (st->owner != OWNER_NONE && st->owner != _current_player) return_cmd_error(STR_3009_TOO_CLOSE_TO_ANOTHER_STATION); - if (!CheckStationSpreadOut(st, tile, 1, 1)) - return CMD_ERROR; + if (!StationRect_BeforeAddRect(st, tile, w, h, false)) return CMD_ERROR; if (st->airport_tile != 0) return_cmd_error(STR_300D_TOO_CLOSE_TO_ANOTHER_AIRPORT); @@ -1746,6 +1739,8 @@ st->build_date = _date; + StationRect_BeforeAddRect(st, tile, w, h, true); + /* if airport was demolished while planes were en-route to it, the * positions can no longer be the same (v->u.air.pos), since different * airports have different indexes. So update all planes en-route to this @@ -1808,6 +1803,8 @@ ); } + StationRect_AfterRemoveRect(st, tile, w, h); + st->airport_tile = 0; st->facilities &= ~FACIL_AIRPORT; @@ -1977,7 +1974,7 @@ if (st->owner != OWNER_NONE && st->owner != _current_player) return_cmd_error(STR_3009_TOO_CLOSE_TO_ANOTHER_STATION); - if (!CheckStationSpreadOut(st, tile, 1, 1)) return CMD_ERROR; + if (!StationRect_BeforeAddRect(st, tile, _dock_w_chk[direction], _dock_h_chk[direction], false)) return CMD_ERROR; if (st->dock_tile != 0) return_cmd_error(STR_304C_TOO_CLOSE_TO_ANOTHER_DOCK); } else { @@ -2006,6 +2003,8 @@ st->build_date = _date; + StationRect_BeforeAddRect(st, tile, _dock_w_chk[direction], _dock_h_chk[direction], true); + MakeDock(tile, st->owner, st->index, direction); UpdateStationVirtCoordDirty(st); @@ -2031,8 +2030,11 @@ if (flags & DC_EXEC) { DoClearSquare(tile1); - MakeWater(tile2); + + StationRect_AfterRemoveTile(st, tile1); + StationRect_AfterRemoveTile(st, tile2); + MarkTileDirtyByTile(tile2); st->dock_tile = 0; @@ -2899,6 +2901,7 @@ { Station *st; uint i; + TileIndex tile; /* Update the speclists of all stations to point to the currently loaded custom stations. */ FOR_ALL_STATIONS(st) { @@ -2908,6 +2911,12 @@ st->speclist[i].spec = GetCustomStationSpecByGrf(st->speclist[i].grfid, st->speclist[i].localidx); } } + + for (tile = 0; tile < MapSize(); tile++) { + if (GetTileType(tile) != MP_STATION) continue; + st = GetStationByTile(tile); + StationRect_BeforeAddTile(st, tile, true); + } } @@ -3138,3 +3147,127 @@ { 'STNS', Save_STNS, Load_STNS, CH_ARRAY }, { 'ROAD', Save_ROADSTOP, Load_ROADSTOP, CH_ARRAY | CH_LAST}, }; + + +#define my_min(a, b) (((a) < (b)) ? (a) : (b)) +#define my_max(a, b) (((a) > (b)) ? (a) : (b)) +#define my_value_in_range(v, a, b) ((a) <= (v) && (v) <= (b)) +#define my_pt_in_rect(r, x, y) (my_value_in_range(x, (r)->left, (r)->right) && my_value_in_range(y, (r)->top, (r)->bottom)) + +static void StationRect_Init(Station *st) +{ + StationRect *r = &st->rect; + r->left = r->top = r->right = r->bottom = 0; +} + +static bool StationRect_IsEmpty(Station *st) +{ + return (st->rect.left == 0 || st->rect.left > st->rect.right || st->rect.top > st->rect.bottom); +} + +static bool StationRect_BeforeAddTile(Station *st, TileIndex tile, bool exec) +{ + StationRect *r = &st->rect; + uint16 x = TileX(tile); + uint16 y = TileY(tile); + if (StationRect_IsEmpty(st)) { + // we are adding the first station tile + r->left = r->right = x; + r->top = r->bottom = y; + } else if (!my_pt_in_rect(r, x, y)) { + // current rect is not empty and new point is outside this rect + // make new spread-out rectangle + StationRect new_rect = {my_min(x, r->left), my_min(y, r->top), my_max(x, r->right), my_max(y, r->bottom)}; + // check new rect dimensions against preset max + uint16 w = new_rect.right - new_rect.left + 1; + uint16 h = new_rect.bottom - new_rect.top + 1; + if (w > _patches.station_spread || h > _patches.station_spread) { + assert(!exec); + _error_message = STR_306C_STATION_TOO_SPREAD_OUT; + return false; + } + // spread-out ok, return true + if (exec) { + // we should update the station rect + *r = new_rect; + } + } else { + ; // new point is inside the rect, we don't need to do anything + } + return true; +} + +static bool StationRect_BeforeAddRect(Station *st, TileIndex tile, uint16 w, uint16 h, bool exec) +{ + return StationRect_BeforeAddTile(st, tile, exec) && StationRect_BeforeAddTile(st, TILE_ADDXY(tile, w - 1, h - 1), exec); +} + +static inline bool ScanRectForStationTiles(StationID st_id, uint16 left, uint16 top, uint16 right, uint16 bottom) +{ + TileIndex top_left = TileXY(left, top); + uint16 width = right - left + 1; + uint16 height = bottom - top + 1; + BEGIN_TILE_LOOP(tile, width, height, top_left) + if (IsTileType(tile, MP_STATION) && GetStationIndex(tile) == st_id) return true; + END_TILE_LOOP(tile, width, height, top_left); + return false; +} + +static bool StationRect_AfterRemoveTile(Station *st, TileIndex tile) +{ + StationRect *r = &st->rect; + uint16 x = TileX(tile); + uint16 y = TileY(tile); + bool reduce_x, reduce_y; + + // look if removed tile was on the bounding rect edge + // and try to reduce the rect by this edge + // do it until we have empty rect or nothing to do + for (;;) { + // check if removed tile is on rect edge + bool left_edge = (x == r->left); + bool right_edge = (x == r->right); + bool top_edge = (y == r->top); + bool bottom_edge = (y == r->bottom); + // can we reduce the rect in either direction? + reduce_x = ((left_edge || right_edge) && !ScanRectForStationTiles(st->index, x, r->top, x, r->bottom)); + reduce_y = ((top_edge || bottom_edge) && !ScanRectForStationTiles(st->index, r->left, y, r->right, y)); + if (!(reduce_x || reduce_y)) break; // nothing to do (can't reduce) + if (reduce_x) { + // reduce horizontally + if (left_edge) { + // move left edge right + r->left = x = x + 1; + } else { + // move right edge left + r->right = x = x - 1; + } + } + if (reduce_y) { + // reduce vertically + if (top_edge) { + // move top edge down + r->top = y = y + 1; + } else { + // move bottom edge up + r->bottom = y = y - 1; + } + } + if (r->left > r->right || r->top > r->bottom) { + // can't continue, if the remaining rectangle is empty + StationRect_Init(st); + return true; // empty remaining rect + } + } + return false; // non-empty remaining rect +} + +static bool StationRect_AfterRemoveRect(Station *st, TileIndex tile, uint16 w, uint16 h) +{ + bool empty; + assert(my_pt_in_rect(&st->rect, TileX(tile), TileY(tile))); + assert(my_pt_in_rect(&st->rect, TileX(tile) + w - 1, TileY(tile) + h - 1)); + empty = StationRect_AfterRemoveTile(st, tile); + if (w != 1 || h != 1) empty = empty || StationRect_AfterRemoveTile(st, TILE_ADDXY(tile, w - 1, h - 1)); + return empty; +}