Changeset - r6871:057e32f0d7b7
Parent rev.
Child rev.
[Not reviewed]
master
0 4 0
peter1138 - 17 years ago 2007-06-12 11:22:32
peter1138@openttd.org
(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')
4 files changed with 124 insertions and 37 deletions:
src/roadveh_cmd.cpp
2
2
src/train_cmd.cpp
15
7
src/vehicle.cpp
104
28
src/vehicle.h
3
0 comments (0 inline, 0 general)
src/roadveh_cmd.cpp
➞
Show inline comments
 
@@ -709,7 +709,7 @@ static void RoadVehCheckTrainCrash(Vehic
 

			




	
	
	
		
 
		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(Vehic

			




	
	
	
		
 
	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

			




        

    


    
    

    

        

                

                    src/train_cmd.cpp
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -2722,7 +2722,7 @@ static void CheckTrainCollision(Vehicle 

			




	
	
	
		
 
	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, 

			




	
	
	
		
 

			




	
	
	
		
 
	/* 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, 

			




	
	
	
		
 

			




	
	
	
		
 
				/* 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, 

			




	
	
	
		
 
					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, 

			




	
	
	
		
 
			/* 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;

			




	
	
	
		
 

			




        

    


    
    

    

        

                

                    src/vehicle.cpp
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -394,44 +394,117 @@ bool AllocateVehicles(Vehicle **vl, int 

			




	
	
	
		
 
	return true;

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
static Vehicle *_vehicle_position_hash[0x1000];

			




	
	
	
		
 
/* 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)

			




	
	
	
		
 
{

			




	
	
	
		
 
	Point pt = RemapCoords(TileX(tile) * TILE_SIZE, TileY(tile) * TILE_SIZE, 0);

			




	
	
	
		
 

			




	
	
	
		
 
	/* 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;

			




	
	
	
		
 

			




	
	
	
		
 
	int x;

			




	
	
	
		
 
	int y;

			




	
	
	
		
 

			




	
	
	
		
 
	for (y = yl;; y = (y + (1 << 6)) & (0x3F << 6)) {

			




	
	
	
		
 
		for (x = xl;; x = (x + 1) & 0x3F) {

			




	
	
	
		
 
			Vehicle *v = _vehicle_position_hash[(x + y) & 0xFFFF];

			




	
	
	
		
 

			




	
	
	
		
 
			while (v != NULL) {

			




	
	
	
		
 
				void* a = proc(v, data);

			




	
	
	
		
 

			




	
	
	
		
 
				if (a != NULL) return a;

			




	
	
	
		
 
				v = v->next_hash;

			




	
	
	
		
 
			}

			




	
	
	
		
 

			




	
	
	
		
 
			if (x == xu) break;

			




	
	
	
		
 
		}

			




	
	
	
		
 

			




	
	
	
		
 
		if (y == yu) break;

			




	
	
	
		
 
	int x = GB(TileX(tile), HASH_RES, HASH_BITS);

			




	
	
	
		
 
	int y = GB(TileY(tile), HASH_RES, HASH_BITS) << HASH_BITS;

			




	
	
	
		
 

			




	
	
	
		
 
	Vehicle *v = _new_vehicle_position_hash[(x + y) & TOTAL_HASH_MASK];

			




	
	
	
		
 
	for (; v != NULL; v = v->next_new_hash) {

			




	
	
	
		
 
		if (v->tile != tile) continue;

			




	
	
	
		
 

			




	
	
	
		
 
		void *a = proc(v, data);

			




	
	
	
		
 
		if (a != NULL) return a;

			




	
	
	
		
 
	}

			




	
	
	
		
 

			




	
	
	
		
 
	return NULL;

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
static void UpdateNewVehiclePosHash(Vehicle *v)

			




	
	
	
		
 
{

			




	
	
	
		
 
	Vehicle **old_hash = v->old_new_hash;

			




	
	
	
		
 
	Vehicle **new_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 (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;

			




	
	
	
		
 
		} else {

			




	
	
	
		
 
			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);

			




	
	
	
		
 

			




	
	
	
		
 
	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

			




	
	
	
		
 
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

			




        

    


    
    

    

        

                

                    src/vehicle.h
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -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*

			




	
	
	
		
 
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);

			




	
	
	
		
 

			




        

    



    


    



    



      

      





    
    0 comments (0 inline, 0 general)
    





    


  

  







  


    




    








    
        Server instance: code.theleruby.com-48
    
    
        This site is powered by
            Kallithea,
        which is
        © 2010–2022 by various authors & licensed under GPLv3.
            – Support