@@ -282,386 +282,386 @@ void AfterLoadVehicles()
}
static Vehicle *InitializeVehicle(Vehicle *v)
{
VehicleID index = v->index;
memset(v, 0, sizeof(Vehicle));
v->index = index;
assert(v->orders == NULL);
v = new (v) InvalidVehicle();
v->left_coord = INVALID_COORD;
v->first = NULL;
v->next = NULL;
v->next_hash = NULL;
v->string_id = 0;
v->next_shared = NULL;
v->prev_shared = NULL;
v->depot_list = NULL;
v->random_bits = 0;
v->group_id = DEFAULT_GROUP;
v->fill_percent_te_id = INVALID_TE_ID;
return v;
/**
* Get a value for a vehicle's random_bits.
* @return A random value from 0 to 255.
*/
byte VehicleRandomBits()
return GB(Random(), 0, 8);
Vehicle *ForceAllocateSpecialVehicle()
/* This stays a strange story.. there should always be room for special
* vehicles (special effects all over the map), but with 65k of vehicles
* is this realistic to double-check for that? For now we just reserve
* BLOCKS_FOR_SPECIAL_VEHICLES times block_size vehicles that may only
* be used for special vehicles.. should work nicely :) */
Vehicle *v;
/* We don't use FOR_ALL here, because FOR_ALL skips invalid items.
* TODO - This is just a temporary stage, this will be removed. */
for (v = GetVehicle(0); v != NULL; v = (v->index + 1U < GetVehiclePoolSize()) ? GetVehicle(v->index + 1) : NULL) {
/* No more room for the special vehicles, return NULL */
if (v->index >= (1 << Vehicle_POOL_BLOCK_SIZE_BITS) * BLOCKS_FOR_SPECIAL_VEHICLES)
return NULL;
if (!IsValidVehicle(v)) return InitializeVehicle(v);
* finds a free vehicle in the memory or allocates a new one
* returns a pointer to the first free vehicle or NULL if all vehicles are in use
* *skip_vehicles is an offset to where in the array we should begin looking
* this is to avoid looping though the same vehicles more than once after we learned that they are not free
* this feature is used by AllocateVehicles() since it need to allocate more than one and when
* another block is added to _Vehicle_pool, since we only do that when we know it's already full
static Vehicle *AllocateSingleVehicle(VehicleID *skip_vehicles)
/* See note by ForceAllocateSpecialVehicle() why we skip the
* first blocks */
const int offset = (1 << Vehicle_POOL_BLOCK_SIZE_BITS) * BLOCKS_FOR_SPECIAL_VEHICLES;
* @todo - This is just a temporary stage, this will be removed. */
if (*skip_vehicles < (_Vehicle_pool.total_items - offset)) { // make sure the offset in the array is not larger than the array itself
for (v = GetVehicle(offset + *skip_vehicles); v != NULL; v = (v->index + 1U < GetVehiclePoolSize()) ? GetVehicle(v->index + 1) : NULL) {
(*skip_vehicles)++;
/* Check if we can add a block to the pool */
if (AddBlockToPool(&_Vehicle_pool))
return AllocateSingleVehicle(skip_vehicles);
Vehicle *AllocateVehicle()
VehicleID counter = 0;
return AllocateSingleVehicle(&counter);
/** 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;
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;
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();
Vehicle *GetLastVehicleInChain(Vehicle *v)
while (v->next != NULL) v = v->next;
/** Finds the previous vehicle in a chain, by a brute force search.
* This old function is REALLY slow because it searches through all vehicles to
* find the previous vehicle, but if v->first has not been set, then this function
* will need to be used to find the previous one. This function should never be
* called by anything but GetFirstVehicleInChain
static Vehicle *GetPrevVehicleInChain_bruteforce(const Vehicle *v)
Vehicle *u;
FOR_ALL_VEHICLES(u) if (u->type == v->type && u->next == v) return u;
/** Find the previous vehicle in a chain, by using the v->first cache.
* While this function is fast, it cannot be used in the GetFirstVehicleInChain
* function, otherwise you'll end up in an infinite loop call
Vehicle *GetPrevVehicleInChain(const Vehicle *v)
assert(v != NULL);
u = GetFirstVehicleInChain(v);
/* Check to see if this is the first */
if (v == u) return NULL;
for (; u->next != v; u = u->next) assert(u->next != NULL);
return u;
/** Finds the first vehicle in a chain.
* This function reads out the v->first cache. Should the cache be dirty,
* it determines the first vehicle in a chain, and updates the cache.
Vehicle *GetFirstVehicleInChain(const Vehicle *v)
Vehicle* u;
assert(v->type == VEH_TRAIN || v->type == VEH_ROAD);
if (v->first != NULL) {
if (v->type == VEH_TRAIN) {
if (IsFrontEngine(v->first) || IsFreeWagon(v->first)) return v->first;
if (IsRoadVehFront(v->first)) return v->first;
DEBUG(misc, 0, "v->first cache faulty. We shouldn't be here, rebuilding cache!");
/* It is the fact (currently) that newly built vehicles do not have
* their ->first pointer set. When this is the case, go up to the
* first engine and set the pointers correctly. Also the first pointer
* is not saved in a savegame, so this has to be fixed up after loading */
/* Find the 'locomotive' or the first wagon in a chain */
while ((u = GetPrevVehicleInChain_bruteforce(v)) != NULL) v = u;
/* Set the first pointer of all vehicles in that chain to the first wagon */
if ((v->type == VEH_TRAIN && (IsFrontEngine(v) || IsFreeWagon(v))) ||
(v->type == VEH_ROAD && IsRoadVehFront(v))) {
for (u = (Vehicle *)v; u != NULL; u = u->next) u->first = (Vehicle *)v;
return (Vehicle*)v;
uint CountVehiclesInChain(const Vehicle* v)
uint count = 0;
do count++; while ((v = v->next) != NULL);
return count;
/** Check if a vehicle is counted in num_engines in each player struct
* @param *v Vehicle to test
* @return true if the vehicle is counted in num_engines
bool IsEngineCountable(const Vehicle *v)
switch (v->type) {
case VEH_AIRCRAFT: return IsNormalAircraft(v); // don't count plane shadows and helicopter rotors
case VEH_TRAIN:
return !IsArticulatedPart(v) && // tenders and other articulated parts
(!IsMultiheaded(v) || IsTrainEngine(v)); // rear parts of multiheaded engines
Status change: