@@ -378,194 +378,194 @@ Vehicle *AllocateVehicle()
/** Allocates a lot of vehicles and frees them again
* @param vl pointer to an array of vehicles to get allocated. Can be NULL if the vehicles aren't needed (makes it test only)
* @param num number of vehicles to allocate room for
* @return true if there is room to allocate all the vehicles
*/
bool AllocateVehicles(Vehicle **vl, int num)
{
int i;
Vehicle *v;
VehicleID counter = 0;
for (i = 0; i != num; i++) {
v = AllocateSingleVehicle(&counter);
if (v == NULL) {
return false;
}
if (vl != NULL) {
vl[i] = v;
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);
void *VehicleFromPos(TileIndex tile, void *data, VehicleFromPosProc *proc)
int x = GB(TileX(tile), HASH_RES, HASH_BITS);
int y = GB(TileY(tile), HASH_RES, HASH_BITS) << HASH_BITS;
if (v->tile != tile) continue;
static void UpdateNewVehiclePosHash(Vehicle *v, bool remove)
Vehicle **old_hash = v->old_new_hash;
Vehicle **new_hash;
if (remove) {
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;
int x = GB(v->x_pos / TILE_SIZE, HASH_RES, HASH_BITS);
int y = GB(v->y_pos / TILE_SIZE, HASH_RES, HASH_BITS) << HASH_BITS;
new_hash = &_new_vehicle_position_hash[(x + y) & TOTAL_HASH_MASK];
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 (last == NULL) {
*old_hash = v->next_new_hash;
last->next_new_hash = v->next_new_hash;
/* 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, x == INVALID_COORD);
Vehicle **old_hash, **new_hash;
int old_x = v->left_coord;
int old_y = v->top_coord;
new_hash = (x == INVALID_COORD) ? NULL : &_vehicle_position_hash[GEN_HASH(x, y)];
old_hash = (old_x == INVALID_COORD) ? NULL : &_vehicle_position_hash[GEN_HASH(old_x, old_y)];
/* remove from hash table? */
u = u->next_hash;
*old_hash = v->next_hash;
last->next_hash = v->next_hash;
/* insert into hash table? */
v->next_hash = *new_hash;
void ResetVehiclePosHash()
FOR_ALL_VEHICLES(v) { v->old_new_hash = NULL; }
memset(_vehicle_position_hash, 0, sizeof(_vehicle_position_hash));
memset(_new_vehicle_position_hash, 0, sizeof(_new_vehicle_position_hash));
void InitializeVehicles()
uint i;
/* Clean the vehicle pool, and reserve enough blocks
* for the special vehicles, plus one for all the other
* vehicles (which is increased on-the-fly) */
CleanPool(&_Vehicle_pool);
AddBlockToPool(&_Vehicle_pool);
for (i = 0; i < BLOCKS_FOR_SPECIAL_VEHICLES; i++) {
ResetVehiclePosHash();
Status change: