--- a/vehicle.c	Sat Mar 18 15:19:30 2006 +0000
+++ b/vehicle.c	Sat Mar 18 15:22:27 2006 +0000
@@ -218,6 +218,11 @@
 
 	FOR_ALL_VEHICLES(v) {
 		v->first = NULL;
+		if (v->type == VEH_Train && (IsFrontEngine(v) || IsFreeWagon(v)))
+			TrainConsistChanged(v);
+	}
+
+	FOR_ALL_VEHICLES(v) {
 		if (v->type != 0) {
 			switch (v->type) {
 				case VEH_Train: v->cur_image = GetTrainImage(v, v->direction); break;
@@ -234,9 +239,6 @@
 
 			v->left_coord = INVALID_COORD;
 			VehiclePositionChanged(v);
-
-			if (v->type == VEH_Train && (IsFrontEngine(v) || IsFreeWagon(v)))
-				TrainConsistChanged(v);
 		}
 	}
 }
@@ -1999,20 +2001,42 @@
 
 UnitID GetFreeUnitNumber(byte type)
 {
-	UnitID unit_num = 0;
-	Vehicle *u;
+	UnitID unit, max;
+	const Vehicle *u;
+	static bool *cache = NULL;
+	static UnitID gmax = 0;
 
-restart:
-	unit_num++;
+	switch (type) {
+		case VEH_Train:    max = _patches.max_trains; break;
+		case VEH_Road:     max = _patches.max_roadveh; break;
+		case VEH_Ship:     max = _patches.max_ships; break;
+		case VEH_Aircraft: max = _patches.max_aircraft; break;
+		default: assert(0);
+	}
+
+	if (max > gmax) {
+		gmax = max;
+		free(cache);
+		cache = malloc((max + 1) * sizeof(*cache));
+	}
+
+	// Clear the cache
+	memset(cache, 0, (max + 1) * sizeof(*cache));
+
+	// Fill the cache
 	FOR_ALL_VEHICLES(u) {
-		if (u->type == type && u->owner == _current_player &&
-		    unit_num == u->unitnumber)
-					goto restart;
+		if (u->type == type && u->owner == _current_player && u->unitnumber != 0 && u->unitnumber <= max)
+			cache[u->unitnumber] = true;
 	}
-	return unit_num;
+
+	// Find the first unused unit number
+	for (unit = 1; unit <= max; unit++) {
+		if (!cache[unit]) break;
+	}
+
+	return unit;
 }
 
-
 // Save and load of vehicles
 const SaveLoad _common_veh_desc[] = {
 	SLE_VAR(Vehicle,subtype,					SLE_UINT8),