diff options
Diffstat (limited to 'src/vehicle.cpp')
| -rw-r--r-- | src/vehicle.cpp | 116 |
1 files changed, 96 insertions, 20 deletions
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 |