From 78d797a6b7cbafb79d128550d95867482cf3e931 Mon Sep 17 00:00:00 2001 From: peter1138 Date: Tue, 12 Jun 2007 11:22:32 +0000 Subject: (svn r10111) -Codechange: Add new vehicle hash table for collision detection and finding vehicles on a tile. The hash area scanned is far smaller than the old hash table, which is now used for viewport updates only. This should give a significant performance improvement for games with many vehicles. (Based on work by 'B. N. SmatZ!' and 'madman2003') --- src/roadveh_cmd.cpp | 4 +- src/train_cmd.cpp | 22 ++++++---- src/vehicle.cpp | 116 +++++++++++++++++++++++++++++++++++++++++++--------- src/vehicle.h | 3 ++ 4 files changed, 116 insertions(+), 29 deletions(-) diff --git a/src/roadveh_cmd.cpp b/src/roadveh_cmd.cpp index 364d9b637..b66483e70 100644 --- a/src/roadveh_cmd.cpp +++ b/src/roadveh_cmd.cpp @@ -709,7 +709,7 @@ static void RoadVehCheckTrainCrash(Vehicle *v) if (!IsLevelCrossingTile(tile)) continue; - if (VehicleFromPos(tile, u, EnumCheckRoadVehCrashTrain) != NULL) { + if (VehicleFromPosXY(v->x_pos, v->y_pos, u, EnumCheckRoadVehCrashTrain) != NULL) { RoadVehCrash(v); return; } @@ -889,7 +889,7 @@ static Vehicle* RoadVehFindCloseTo(Vehicle* v, int x, int y, Direction dir) rvf.y = y; rvf.dir = dir; rvf.veh = v; - u = (Vehicle*)VehicleFromPos(TileVirtXY(x, y), &rvf, EnumCheckRoadVehClose); + u = (Vehicle*)VehicleFromPosXY(x, y, &rvf, EnumCheckRoadVehClose); /* This code protects a roadvehicle from being blocked for ever * If more than 1480 / 74 days a road vehicle is blocked, it will diff --git a/src/train_cmd.cpp b/src/train_cmd.cpp index 68be61c99..5f2073cf0 100644 --- a/src/train_cmd.cpp +++ b/src/train_cmd.cpp @@ -2722,7 +2722,7 @@ static void CheckTrainCollision(Vehicle *v) tcc.v_skip = v->next; /* find colliding vehicle */ - Vehicle *realcoll = (Vehicle*)VehicleFromPos(TileVirtXY(v->x_pos, v->y_pos), &tcc, FindTrainCollideEnum); + Vehicle *realcoll = (Vehicle*)VehicleFromPosXY(v->x_pos, v->y_pos, &tcc, FindTrainCollideEnum); if (realcoll == NULL) return; Vehicle *coll = GetFirstVehicleInChain(realcoll); @@ -2775,6 +2775,8 @@ static void TrainController(Vehicle *v, bool update_image) /* For every vehicle after and including the given vehicle */ for (prev = GetPrevVehicleInChain(v); v != NULL; prev = v, v = v->next) { + DiagDirection enterdir = DIAGDIR_BEGIN; + bool update_signals = false; BeginVehicleMove(v); GetNewVehiclePosResult gp = GetNewVehiclePos(v); @@ -2810,7 +2812,7 @@ static void TrainController(Vehicle *v, bool update_image) /* Determine what direction we're entering the new tile from */ Direction dir = GetNewVehicleDirectionByTile(gp.new_tile, gp.old_tile); - DiagDirection enterdir = DirToDiagDir(dir); + enterdir = DirToDiagDir(dir); assert(IsValidDiagDirection(enterdir)); /* Get the status of the tracks in the new tile and mask @@ -2917,11 +2919,9 @@ static void TrainController(Vehicle *v, bool update_image) assert(v->u.rail.track); } - if (IsFrontEngine(v)) TrainMovedChangeSignals(gp.new_tile, enterdir); - - /* Signals can only change when the first - * (above) or the last vehicle moves. */ - if (v->next == NULL) TrainMovedChangeSignals(gp.old_tile, ReverseDiagDir(enterdir)); + /* We need to update signal status, but after the vehicle position hash + * has been updated by AfterSetTrainPos() */ + update_signals = true; if (prev == NULL) AffectSpeedByDirChange(v, chosen_dir); @@ -2958,6 +2958,14 @@ static void TrainController(Vehicle *v, bool update_image) /* This is the first vehicle in the train */ AffectSpeedByZChange(v, old_z); } + + if (update_signals) { + if (IsFrontEngine(v)) TrainMovedChangeSignals(gp.new_tile, enterdir); + + /* Signals can only change when the first + * (above) or the last vehicle moves. */ + if (v->next == NULL) TrainMovedChangeSignals(gp.old_tile, ReverseDiagDir(enterdir)); + } } return; diff --git a/src/vehicle.cpp b/src/vehicle.cpp index 025cadd00..2d46bdcbb 100644 --- a/src/vehicle.cpp +++ b/src/vehicle.cpp @@ -394,44 +394,117 @@ bool AllocateVehicles(Vehicle **vl, int num) return true; } +/* Size of the hash, 6 = 64 x 64, 7 = 128 x 128. Larger sizes will (in theory) reduce hash + * lookup times at the expense of memory usage. */ +const int HASH_BITS = 7; +const int HASH_SIZE = 1 << HASH_BITS; +const int HASH_MASK = HASH_SIZE - 1; +const int TOTAL_HASH_SIZE = 1 << (HASH_BITS * 2); +const int TOTAL_HASH_MASK = TOTAL_HASH_SIZE - 1; + +/* Resolution of the hash, 0 = 1*1 tile, 1 = 2*2 tiles, 2 = 4*4 tiles, etc. + * Profiling results show that 0 is fastest. */ +const int HASH_RES = 0; + +static Vehicle *_new_vehicle_position_hash[TOTAL_HASH_SIZE]; + +static void *VehicleFromHash(int xl, int yl, int xu, int yu, void *data, VehicleFromPosProc *proc) +{ + for (int y = yl; ; y = (y + (1 << HASH_BITS)) & (HASH_MASK << HASH_BITS)) { + for (int x = xl; ; x = (x + 1) & HASH_MASK) { + Vehicle *v = _new_vehicle_position_hash[(x + y) & TOTAL_HASH_MASK]; + for (; v != NULL; v = v->next_new_hash) { + void *a = proc(v, data); + if (a != NULL) return a; + } + if (x == xu) break; + } + if (y == yu) break; + } + + return NULL; +} + + +void *VehicleFromPosXY(int x, int y, void *data, VehicleFromPosProc *proc) +{ + const int COLL_DIST = 6; + + /* Hash area to scan is from xl,yl to xu,yu */ + int xl = GB((x - COLL_DIST) / TILE_SIZE, HASH_RES, HASH_BITS); + int xu = GB((x + COLL_DIST) / TILE_SIZE, HASH_RES, HASH_BITS); + int yl = GB((y - COLL_DIST) / TILE_SIZE, HASH_RES, HASH_BITS) << HASH_BITS; + int yu = GB((y + COLL_DIST) / TILE_SIZE, HASH_RES, HASH_BITS) << HASH_BITS; + + return VehicleFromHash(xl, yl, xu, yu, data, proc); +} -static Vehicle *_vehicle_position_hash[0x1000]; void *VehicleFromPos(TileIndex tile, void *data, VehicleFromPosProc *proc) { - Point pt = RemapCoords(TileX(tile) * TILE_SIZE, TileY(tile) * TILE_SIZE, 0); + int x = GB(TileX(tile), HASH_RES, HASH_BITS); + int y = GB(TileY(tile), HASH_RES, HASH_BITS) << HASH_BITS; - /* The hash area to scan */ - const int xl = GB(pt.x - 174, 7, 6); - const int xu = GB(pt.x + 104, 7, 6); - const int yl = GB(pt.y - 294, 6, 6) << 6; - const int yu = GB(pt.y + 56, 6, 6) << 6; + Vehicle *v = _new_vehicle_position_hash[(x + y) & TOTAL_HASH_MASK]; + for (; v != NULL; v = v->next_new_hash) { + if (v->tile != tile) continue; - int x; - int y; + void *a = proc(v, data); + if (a != NULL) return a; + } - for (y = yl;; y = (y + (1 << 6)) & (0x3F << 6)) { - for (x = xl;; x = (x + 1) & 0x3F) { - Vehicle *v = _vehicle_position_hash[(x + y) & 0xFFFF]; + return NULL; +} - while (v != NULL) { - void* a = proc(v, data); +static void UpdateNewVehiclePosHash(Vehicle *v) +{ + Vehicle **old_hash = v->old_new_hash; + Vehicle **new_hash; - if (a != NULL) return a; - v = v->next_hash; - } + if (v->tile == INVALID_TILE || v->tile == 0) { + new_hash = NULL; + } else { + int x = GB(TileX(v->tile), HASH_RES, HASH_BITS); + int y = GB(TileY(v->tile), HASH_RES, HASH_BITS) << HASH_BITS; + new_hash = &_new_vehicle_position_hash[(x + y) & TOTAL_HASH_MASK]; + } - if (x == xu) break; + if (old_hash == new_hash) return; + + /* Remove from the old position in the hash table */ + if (old_hash != NULL) { + Vehicle *last = NULL; + Vehicle *u = *old_hash; + while (u != v) { + last = u; + u = u->next_new_hash; + assert(u != NULL); } - if (y == yu) break; + if (last == NULL) { + *old_hash = v->next_new_hash; + } else { + last->next_new_hash = v->next_new_hash; + } } - return NULL; + + /* Insert vehicle at beginning of the new position in the hash table */ + if (new_hash != NULL) { + v->next_new_hash = *new_hash; + *new_hash = v; + assert(v != v->next_new_hash); + } + + /* Remember current hash position */ + v->old_new_hash = new_hash; } +static Vehicle *_vehicle_position_hash[0x1000]; static void UpdateVehiclePosHash(Vehicle* v, int x, int y) { + UpdateNewVehiclePosHash(v); + Vehicle **old_hash, **new_hash; int old_x = v->left_coord; int old_y = v->top_coord; @@ -468,6 +541,7 @@ static void UpdateVehiclePosHash(Vehicle* v, int x, int y) void ResetVehiclePosHash() { memset(_vehicle_position_hash, 0, sizeof(_vehicle_position_hash)); + memset(_new_vehicle_position_hash, 0, sizeof(_new_vehicle_position_hash)); } void InitializeVehicles() @@ -611,8 +685,10 @@ void DestroyVehicle(Vehicle *v) InvalidateWindowData(WC_VEHICLE_DEPOT, v->tile); } + v->tile = INVALID_TILE; UpdateVehiclePosHash(v, INVALID_COORD, 0); v->next_hash = NULL; + v->next_new_hash = NULL; if (IsPlayerBuildableVehicleType(v)) DeleteVehicleOrders(v); /* Now remove any artic part. This will trigger an other diff --git a/src/vehicle.h b/src/vehicle.h index 8d734bf22..2d808c0b9 100644 --- a/src/vehicle.h +++ b/src/vehicle.h @@ -290,6 +290,8 @@ struct Vehicle { int32 right_coord; int32 bottom_coord; Vehicle *next_hash; + Vehicle *next_new_hash; + Vehicle **old_new_hash; /* Related to age and service time */ Date age; // Age in days @@ -497,6 +499,7 @@ uint CountVehiclesInChain(const Vehicle* v); bool IsEngineCountable(const Vehicle *v); void DeleteVehicleChain(Vehicle *v); void *VehicleFromPos(TileIndex tile, void *data, VehicleFromPosProc *proc); +void *VehicleFromPosXY(int x, int y, void *data, VehicleFromPosProc *proc); void CallVehicleTicks(); Vehicle *FindVehicleOnTileZ(TileIndex tile, byte z); -- cgit v1.2.3-70-g09d2