BigWorld 的AOI设计

AOI同步管理器Witness

在分布式大世界中，一个Cell里的所有Entity的数量可能成百上千。如果对于每个玩家的客户端都把当前Cell里的Entity都同步到客户端的话，流量和CPU的压力变得非常恐怖，因此在Bigworld里也对每个玩家Entity施加了一个AOI同步范围的限制。为了集中处理AOI以及附加的属性同步逻辑，避免代码散落在RealEntity的相关文件中，Bigworld给每个RealEntity都附加了一个Witness的对象，通过addToAoI和removeFromAoI这两个接口来承接AOI相关回调:

/**
 *	This class is a witness to the movements and perceptions of a RealEntity.
 *	It is created when a client is attached to this entity. Its main activity
 *	centres around the management of an Area of Interest list.
 */
class Witness : public Updatable
{
public:
	// Creation/Destruction
	Witness( RealEntity & owner, BinaryIStream & data,
			CreateRealInfo createRealInfo, bool hasChangedSpace = false );
public:
	RealEntity & real()					{ return real_; }
	const RealEntity & real() const		{ return real_; }

	Entity & entity()					{ return entity_; }
	const Entity & entity() const		{ return entity_; }
	void addToAoI( Entity * pEntity, bool setManuallyAdded );
	void removeFromAoI( Entity * pEntity, bool clearManuallyAdded );

	void newPosition( const Vector3 & position );
	// 省略很多代码
};

class RealEntity
{
public:
	void enableWitness( BinaryIStream & data, Mercury::ReplyID replyID );
	void disableWitness( bool isRestore = false );
private:
	Witness * pWitness_;
};

但是对于非客户端玩家对应的RealEntity来说，这个Witness对象是不需要创建的，因为这些RealEntity并没有同步AOI内Entity数据的需求。因此默认情况下这个pWitness_指针是空的，只有接收到enableWitness这个RPC的时候才会创建这个Witness实例:

/**
 *	This method adds or deletes the Witness of this RealEntity.
 */
void RealEntity::enableWitness( BinaryIStream & data, Mercury::ReplyID replyID )
{
	// Send an empty reply to ack this message
	this->channel().bundle().startReply( replyID );

	bool isRestore;
	data >> isRestore;

	if (data.remainingLength() > 0)
	{
		INFO_MSG( "RealEntity::enableWitness: adding witness for %u%s\n",
			entity_.id(), isRestore ? " (restoring)" : "" );

		// take control
		if (controlledBy_.id == NULL_ENTITY_ID)
		{
			controlledBy_.init( entity_.id(), entity_.baseAddr_,
				controlledBy_.BASE, entity_.pType()->typeID() );
		}

		int bytesToClientPerPacket;
		data >> bytesToClientPerPacket;

		MemoryOStream witnessData;
		StreamHelper::addRealEntityWithWitnesses( witnessData,
				bytesToClientPerPacket,
				CellAppConfig::defaultAoIRadius() );

		// make the witness
		MF_ASSERT( pWitness_ == NULL );

		// Delay calls to onEnteredAoI
		Entity::callbacksPermitted( false ); //{

		this->setWitness( new Witness( *this, witnessData,
			isRestore ? CREATE_REAL_FROM_RESTORE : CREATE_REAL_FROM_INIT ) );

		Entity::callbacksPermitted( true ); //}

		Entity::nominateRealEntity( entity_ );
		Script::call( PyObject_GetAttrString( &entity_, "onGetWitness" ),
				PyTuple_New( 0 ), "onGetWitness", true );
		Entity::nominateRealEntityPop();
	}
	else
	{
		this->disableWitness( isRestore );
	}

	if (this->entity().cell().pReplayData())
	{
		this->entity().cell().pReplayData()->addEntityPlayerStateChange( 
			this->entity() );
	}
}

而这个enableWitness只有BaseApp里的Proxy才会发起，在之前客户端进入场景的相关代码分析中我们提到当这个Proxy的客户端PlayerEntity建立之后就会通过enableEntities这个RPC来触发这个enableWitness的调用，来通知服务器端可以向下同步AOI内的所有Entity了：

/**
 *	This method sends an enable or disable witness message to our cell entity.
 *
 *	@param enable		whether to enable or disable the witness
 *	@param isRestore 	is this an explicit witness enable/disable send as a
 *						result of a restore cell entity?
 */
void Proxy::sendEnableDisableWitness( bool enable, bool isRestore )
{
	AUTO_SCOPED_THIS_ENTITY_PROFILE;

	Mercury::Bundle & bundle = this->cellBundle();
	bundle.startRequest( CellAppInterface::enableWitness,
			new EnableWitnessReplyHandler( this ) );

	bundle << id_;
	bundle << isRestore;

	++numOutstandingEnableWitness_;
	cellHasWitness_ = enable;

	if (enable)
	{
		bundle << BaseAppConfig::bytesPerPacketToClient();
	}
	// else just send an empty stream

	this->sendToCell();	// send it straight away
}

/**
 *	This method handles a request from the client to enable or disable updates
 *	from the cell. It forwards this message on to the cell.
 */
void Proxy::enableEntities()
{
	DEBUG_MSG( "Proxy::enableEntities(%u)\n", id_ );

	// if this is the first we've heard of it, then send the client the props
	// 省略很多代码

	// ... and tell the cell the game is on
	if (!entitiesEnabled_)
	{
		entitiesEnabled_ = true;

		if (this->hasCellEntity())
		{
			this->sendEnableDisableWitness( /*enable:*/true );

			// remove ProxyPusher
			if (pProxyPusher_ != NULL)
			{
				delete pProxyPusher_;
				pProxyPusher_ = NULL;
			}
		}
	}
	// 省略很多代码
}

由于客户端发送enableEntities的时候对应的CellApp上的Entity可能还没有创建完成，因此在CellEntity创建完成的回调里会再检查一下entitiesEnabled_这个标记位，如果为true的话则再次通知对应的CellEntity去创建Witness对象：

/**
 *	This method deals with our cell entity being created.
 */
void Proxy::cellEntityCreated()
{
	AUTO_SCOPED_THIS_ENTITY_PROFILE;

	if (!entitiesEnabled_) return;
	MF_ASSERT( this->hasClient() );

	MF_ASSERT( this->hasCellEntity() );

	//  create the witness
	this->sendEnableDisableWitness( /*enable:*/true );

	// get rid of the proxy pusher now that the witness will be sending us
	// regular updates (the self motivator should definitely be there).
	MF_ASSERT( pProxyPusher_ != NULL );
	delete pProxyPusher_;
	pProxyPusher_ = NULL;
}

当客户端断线的时候，对应的通知回调Proxy::detachFromClient会自动调用sendEnableDisableWitness(false)来通知对应的RealEntity去删除绑定的Witness对象，因为此时已经没有相关的客户端连接了，即使Proxy接收到AOI相关数据也只能丢弃:

void Proxy::detachFromClient( bool shouldCondemn )
{
	// 省略很多代码

	// Don't try to disable the witness if we've already sent the
	// destroyCell message.
	if (cellHasWitness_ && this->shouldSendToCell())
	{
		this->sendEnableDisableWitness( /*enable:*/false );
	}
	// 省略很多代码
}

通过上面的代码分析我们可以得出结论：只有客户端连接存在的时候这个Witness对象才会被创建，当客户端断开的时候这个Witness对象就会被销毁。

AOI内Entity的进出管理

当一个Witness被创建的时候，其Witness::init函数中会向AOI计算系统注册一个与当前RealEntity相关的AOI半径对象AoITrigger:

/**
 *	This method initialises this object some more. It is only separate from
 *	the constructor for historical reasons.
 */
void Witness::init()
{
	// Disabling callbacks is not needed since no script should be triggered but
	// it's helpful for debugging.
	Entity::callbacksPermitted( false );

	// Create AoI triggers around ourself.
	{
		SCOPED_PROFILE( SHUFFLE_AOI_TRIGGERS_PROFILE );
		pAoITrigger_ = new AoITrigger( *this, pAoIRoot_, aoiRadius_ );
		if (this->isAoIRooted())
		{
			MobileRangeListNode * pRoot =
				static_cast< MobileRangeListNode * >( pAoIRoot_ );
			pRoot->addTrigger( pAoITrigger_ );
		}
		else
		{
			entity().addTrigger( pAoITrigger_ );
		}
	}

	Entity::callbacksPermitted( true );

	// 省略一些代码
}

这里的pAoIRoot_代表的是当前Entity在AOI系统里对应的坐标节点，因此pAoITrigger_就代表以当前Entity位置为中心aoiRadius_为半径的触发器。这个AoITrigger的主要作用就是注册这个触发器，然后在其他Entity进出触发器的时候通知到Witness来执行addToAoI和removeFromAoI:

/**
 *	This class is used for AoI triggers. It is similar to the Range trigger
 *	except that it will add the other entity to its owner entity's AoI list.
 */
class AoITrigger : public RangeTrigger
{
public:
	AoITrigger( Witness & owner, RangeListNode * pCentralNode, float range ) :
		RangeTrigger( pCentralNode, range,
				RangeListNode::FLAG_LOWER_AOI_TRIGGER,
				RangeListNode::FLAG_UPPER_AOI_TRIGGER,
				RangeListNode::FLAG_NO_TRIGGERS,
				RangeListNode::FLAG_NO_TRIGGERS ),
		owner_( owner )
	{
		// Collect the large entities whose range we currently sit.
		owner_.entity().space().visitLargeEntities(
			pCentralNode->x(),
			pCentralNode->z(),
			*this );

		this->insert();
	}

	~AoITrigger()
	{
		this->removeWithoutContracting();
	}

	virtual BW::string debugString() const;

	virtual void triggerEnter( Entity & entity );
	virtual void triggerLeave( Entity & entity );
	virtual Entity * pEntity() const { return &owner_.entity(); }

private:
	Witness & owner_;
};
/**
 * This method is called when an entity enters (triggers) the AoI.
 * It forwards the call to the entity.
 *
 * @param entity The entity who triggered this trigger/entered AoI.
 */
void AoITrigger::triggerEnter( Entity & entity )
{
	if ((&entity != &owner_.entity()) &&
			!entity.pType()->description().isManualAoI())
	{
		owner_.addToAoI( &entity, /* setManuallyAdded */ false );
	}
}


/**
 * This method is called when an entity leaves (untriggers) the AoI.
 * It forwards the call to the entity
 *
 * @param entity The entity who untriggered this trigger/left AoI.
 */
void AoITrigger::triggerLeave( Entity & entity )
{
	if ((&entity != &owner_.entity()) &&
			(!entity.pType()->description().isManualAoI()))
	{
		owner_.removeFromAoI( &entity, /* clearManuallyAdded */ false );
	}
}

目前我们先忽略AoITrigger父类RangeTrigger是如何触发triggerEnter/triggerLeave的，暂时只关注addToAoI和removeFromAoI的处理流程。

当一个Entity(A)需要进入到到当前的RealEntity(B)的AOI范围时，Witness::addToAoI会被调用到:

/**
 *	This class is used by RealEntityWithWitnesses to cache information about
 *	other entities.
 */
class EntityCache
{
public:
	// TODO: Remove this restriction.
	static const int MAX_LOD_LEVELS = 4;

	typedef double Priority;

	EntityCache( const Entity * pEntity );
	// 省略很多字段
	// Accessors

	EntityConstPtr pEntity() const	{ return pEntity_; }
	EntityConstPtr & pEntity()		{ return pEntity_; }
private:
	EntityConstPtr	pEntity_;
	Flags			flags_;	// TODO: Not good structure packing.
	AoIUpdateSchemeID updateSchemeID_;

	VehicleChangeNum	vehicleChangeNum_;

	Priority	priority_;	// double
	Priority    lastPriorityDelta_; // double

	EventNumber		lastEventNumber_;			// int32
	// 省略很多字段
};
inline
bool operator<( const EntityCache & left, const EntityCache & right )
{
	return left.pEntity() < right.pEntity();
}

/**
 *	This method adds the input entity to this entity's Area of Interest.
 */
void Witness::addToAoI( Entity * pEntity, bool setManuallyAdded )
{
	// 省略一些错误判断

	// see if the entity is already in our AoI
	EntityCache * pCache = aoiMap_.find( *pEntity );

	// 省略一些错误判断

	if (pCache != NULL)
	{
		// 这里先忽略pCache复用的一些逻辑
	}
	else
	{
		pCache = aoiMap_.add( *pEntity );
		pCache->setEnterPending();
		this->addToSeen( pCache );
	}

	// 忽略一些后续逻辑
}

这里会涉及到一个非常重要的类型EntityCache，如果一个Entity(A)需要向RealEntity(B)的客户端同步，那么RealEntity(B)上就会为这个Entity(A)创建一个EntityCache对象，来负责刚开始进入AOI时的全量同步以及后续的增量同步。由于一个RealEntity上会同步大量的Entity到自身客户端，因此在EntityCache之上还有一个Witness的类型来管理所有的EntityCache,其内部使用EntityCacheMap这个集合来存储所有的EntityCache，:

/**
 *	This class is a map of entity caches
 */
class EntityCacheMap
{
public:
	~EntityCacheMap();

	EntityCache * add( const Entity & e );
	void del( EntityCache * ec );

	EntityCache * find( const Entity & e ) const;
	EntityCache * find( EntityID id ) const;

	uint32 size() const	{ return set_.size(); }

	void writeToStream( BinaryOStream & stream ) const;

	void visit( EntityCacheVisitor & visitor ) const;
	void mutate( EntityCacheMutator & mutator );

	static void addWatchers();

private:
	typedef BW::set< EntityCache > Implementor;

	Implementor set_;
};

了解了EntityCache与EntityCacheMap的类型作用之后，我们再回到addToAoI。addToAoI这里会先查询当前aoiMap_是否已经有pEntity对应的EntityCache，如果有的话会执行复用，没有的话会创建一个新的pCache，同时标记这个pCache为开始同步EnterPending状态，并通过addToSeen加入到当前的同步队列entityQueue_里:

/**
 *	Add the given entity into the entity cache map
 */
EntityCache * EntityCacheMap::add( const Entity & e )
{
	++g_numInAoI;
	++g_numInAoIEver;
	EntityCache eCache( &e );
	Implementor::iterator iter = set_.insert( eCache ).first;

	return const_cast< EntityCache *>( &*iter );
}

/**
 *	This method adds the input entity to the collection of seen entities.
 *	It is called by addToAoI, or later in requestEntityUpdate.
 */
void Witness::addToSeen( EntityCache * pCache )
{
	EntityCache::Priority initialPriority = 0.0;


	// We want to give the entity the minimum current priority. We need to
	// be careful here. 
	if (!entityQueue_.empty())
	{
		initialPriority = entityQueue_.front()->priority();
	}

	pCache->priority( initialPriority );

// #define DELAY_ENTER_AOI
#ifdef DELAY_ENTER_AOI
	const bool shouldUpdatePriority = !pCache->isEnterPending();

	if (shouldUpdatePriority && !pCache->isGone())
	{
		pCache->updatePriority( entity_.position() );
	}
#endif

	entityQueue_.push_back( pCache );
	std::push_heap( entityQueue_.begin(), entityQueue_.end(), PriorityCompare() );
}

这个entityQueue_其实是一个最小堆的优先队列，里面会使用EntityCache的优先级字段来执行最小堆维护。但是目前新建的EntityCache只是加入到entityQueue_里，并没有做任何的同步操作，同步数据的处理在每帧都会执行的Witness::update中。由于这个函数比较庞大，我们目前先只展示新的Entity进入AOI时的处理:

/**
 *	This method is called regularly to send data to the witnesses associated
 *	with this entity.
 */
void Witness::update()
{
	// 省略很多代码
	// This is the maximum amount of priority change that we go through in a
	// tick. Based on the default AoIUpdateScheme (distance/5 + 1) things up
	// to 45 metres away can be sent every frame.
	const float MAX_PRIORITY_DELTA =
		CellAppConfig::witnessUpdateMaxPriorityDelta();

	// We want to make sure that entities at a distance are never sent at 10Hz.
	// What we do is make sure that the change in priorities that we go over is
	// capped.
	// Note: We calculate the max priority from the front priority. We should
	// probably calculate from the previous maxPriority. Doing it the current
	// way, if you only have 1 entity in your AoI, it will be sent every frame.
	EntityCache::Priority maxPriority = entityQueue_.empty() ? 0.f :
		entityQueue_.front()->priority() + MAX_PRIORITY_DELTA;

	KnownEntityQueue::iterator queueBegin = entityQueue_.begin();
	KnownEntityQueue::iterator queueEnd = entityQueue_.end();

			// Entities in queue &&
	while ((queueBegin != queueEnd) &&
				// Priority change less than MAX_PRIORITY_DELTA &&
				(*queueBegin)->priority() < maxPriority &&
				// Packet still has space (includes 2 bytes for sequenceNumber))
				bundle.size() < desiredPacketSize - 2)
	{
		loopCounter++;

		// Pop the top entity. pop_heap actually keeps the entity in the vector
		// but puts it in the end. [queueBegin, queueEnd) is a heap and
		// [queueEnd, entityQueue_.end()) has the entities that have been popped
		EntityCache * pCache = entityQueue_.front();
		std::pop_heap( queueBegin, queueEnd--, PriorityCompare() );
		bool wasPrioritised = pCache->isPrioritised();

		if (!pCache->isUpdatable())
		{
			this->handleStateChange( &pCache, queueEnd );
		}
		// 暂时省略一些逻辑
	}
	// 省略很多的代码
}

这里会使用一个while循环不断的当前最小堆的顶端元素，看来EntityCache::priority越小其处理优先级越高。当前EntityCache是EnterPending状态的时候，isUpdatable会返回false，因此会走到handleStateChange来处理当前新创建的EntityCache，并调用到handleEnterPending:

/**
 * This method processes an entity cache state change
 *
 * @param ppCache   The current entity cache. Can be NULL after the call if it was invalidated.
 * @param queueEnd Iterator pointing to the last entry in the heap
 */
void Witness::handleStateChange( EntityCache ** ppCache,
				KnownEntityQueue::iterator & queueEnd )
{
	MF_ASSERT( ppCache != NULL );

	Mercury::Bundle & bundle = this->bundle();
	EntityCache * pCache = *ppCache;

	MF_ASSERT( !pCache->isRequestPending() );
	if (pCache->isGone())
	{
		this->deleteFromSeen( bundle, queueEnd );
		*ppCache = NULL;
	}// 忽略其他的一些分支
	else if (pCache->isEnterPending())
	{
		this->handleEnterPending( bundle, queueEnd );
	}
	// 忽略一些逻辑
}

这个handleEnterPending的主要逻辑是通过sendEnter来构造一个BaseAppIntInterface::enterAoI的消息，通知Base当前有新Entity进入AOI，同时这里将当前的pCache的状态切换为RequestPending:

/**
 *	This handles the sending of an ENTER_PENDING EntityCache, and its removal
 *	from the entity queue. 
 */
void Witness::handleEnterPending( Mercury::Bundle & bundle,
		KnownEntityQueue::iterator iEntityCache )
{
	this->sendEnter( bundle, *iEntityCache );
	*iEntityCache = entityQueue_.back();
	entityQueue_.pop_back();
}

/**
 *	This method sends the enterAoI message to the client.
 */
void Witness::sendEnter( Mercury::Bundle & bundle, EntityCache * pCache )
{
	size_t oldSize = bundle.size();
	const Entity * pEntity = pCache->pEntity().get();

	pCache->idAlias( this->allocateIDAlias( *pEntity ) );

	MF_ASSERT( !pCache->isRequestPending() );
	pCache->clearEnterPending();
	pCache->setRequestPending();

	pCache->vehicleChangeNum( pEntity->vehicleChangeNum() );

	// TODO: Need to have some sort of timer on the pending entities.
	// At the moment, we do not handle the case where the client does
	// not reply to this message.

	if (pEntity->pVehicle() != NULL)
	{
		// 忽略载具逻辑
	}
	else
	{
		BaseAppIntInterface::enterAoIArgs & rEnterAoI =
			BaseAppIntInterface::enterAoIArgs::start( bundle );

		rEnterAoI.id = pEntity->id();
		rEnterAoI.idAlias = pCache->idAlias();
	}
	pEntity->pType()->stats().enterAoICounter().
		countSentToOtherClients( bundle.size() - oldSize );
}

当BaseApp上的Proxy接收到这个消息的时候，其处理函数会直接将此消息转发到客户端上:

/**
 *	This method forwards this message to the client (reliably)
 */
#define STRUCT_CLIENT_MESSAGE_FORWARDER( MESSAGE )							\
void Proxy::MESSAGE( const BaseAppIntInterface::MESSAGE##Args & args )		\
{																			\
	if (this->hasOutstandingEnableWitness())								\
	{																		\
		/* Do nothing. It's for an old client. */							\
	}																		\
	else if (this->hasClient())												\
	{																		\
		Mercury::Bundle & b =											\
			this->clientBundle();											\
		b.startMessage( ClientInterface::MESSAGE );							\
		((BinaryOStream&)b) << args;										\
	}																		\
	else																	\
	{																		\
		WARNING_MSG( "Proxy::" #MESSAGE										\
			": Cannot forward for %u. No client attached\n", id_ );			\
	}																		\
}	

STRUCT_CLIENT_MESSAGE_FORWARDER( enterAoI )				// forward to client

客户端接收到这个消息之后，会决定后续的同步操作的相关参数:

/**
 *	This method handles the message from the server that an entity has entered
 *	our Area of Interest (AoI).
 */
void ServerConnection::enterAoI( const ClientInterface::enterAoIArgs & args )
{
	this->enterAoI( args.id, args.idAlias );
}
/**
 *	This method is the common implementation of enterAoI and enterAoIOnVehicle.
 */
void ServerConnection::enterAoI( EntityID id, IDAlias idAlias,
		EntityID vehicleID )
{
	// Set this even if args.idAlias is NO_ID_ALIAS.
	idAlias_[ idAlias ] = id;

	if (pHandler_)
	{
		const CacheStamps * pStamps = pHandler_->onEntityCacheTest( id );

		if (pStamps)
		{
			this->requestEntityUpdate( id, *pStamps );
		}
		else
		{
			this->requestEntityUpdate( id );
		}
	}
}

typedef BW::vector< EventNumber > CacheStamps;

这里的onEntityCacheTest会根据当前Entity的标识符来计算出上次同步到这个Entity的各个属性LOD的最新版本号，并通知服务器下发这些版本号之后的消息。如果之前没同步过或者过期太久，则通知服务器执行一次最新状态的全量下发。这里打包BaseAppExtInterface::requestEntityUpdate这个消息时会带上之前记录的属性序列号数组:

/**
 *	This method requests the server to send update information for the entity
 *	with the input id.
 *
 *  @param id		ID of the entity whose update is requested.
 *	@param stamps	A vector containing the known cache event stamps. If none
 *					are known, stamps is empty.
 */
void ServerConnection::requestEntityUpdate( EntityID id,
	const CacheStamps & stamps )
{
	if (this->isOffline())
		return;

	this->bundle().startMessage( BaseAppExtInterface::requestEntityUpdate );
	this->bundle() << id;

	CacheStamps::const_iterator iter = stamps.begin();

	while (iter != stamps.end())
	{
		this->bundle() << (*iter);

		iter++;
	}
}

Proxy接收到这个BaseAppExtInterface::requestEntityUpdate消息之后，只是通过CellAppInterface::requestEntityUpdate重新打包并中转到对应的RealEntity上:

/**
 *	This method handles a request from the client for information about a given
 *	entity. It forwards this message on to the cell.
 */
void Proxy::requestEntityUpdate( const Mercury::Address & srcAddr,
								 Mercury::UnpackedMessageHeader & header, 
								 BinaryIStream & data )
{
	Mercury::Bundle & b = this->cellBundle();
	b.startMessage( CellAppInterface::requestEntityUpdate );
	b << id_;
	b.transfer( data, data.remainingLength() );
}

/**
 *	This method is called by the client in order to request an update for an
 *	entity that has recently entered its AoI.
 */
void Entity::requestEntityUpdate( BinaryIStream & data )
{
	MF_ASSERT( pReal_ != NULL );

	if (pReal_ != NULL && pReal_->pWitness() != NULL)
	{
		EntityID id;
		data >> id;

		int length = data.remainingLength();

		pReal_->pWitness()->requestEntityUpdate( id,
				(EventNumber *)data.retrieve( length ),
				length/sizeof(EventNumber) );
	}
}

兜了一个大圈之后，最终回到了Witness来处理，这里会将当前的EntityCache从RequestPending切换为CreatePending:

/**
 *	This virtual method is used to handle a request from the client to update
 *	the information associated with a particular entity.
 */
void Witness::requestEntityUpdate( EntityID id,
		EventNumber * pEventNumbers, int size )
{
	EntityCache * pCache = aoiMap_.find( id );

	// 一些错误处理

	pCache->clearRequestPending();
	pCache->setCreatePending();

// make sure that the client is not try to stuff us up
	if (size > pCache->numLoDLevels())
	{
		ERROR_MSG( "CHEAT: Witness::requestEntityUpdate: "
			"Client %u sent %d LoD event stamps when max is %d\n",
			entity_.id(), size, pCache->numLoDLevels() );
		size = pCache->numLoDLevels();
	}

	// ok we have the all clear, let's add it to the seen list then
	pCache->lodEventNumbers( pEventNumbers, size );
	this->addToSeen( pCache );
};

这里会将客户端传递过来的属性序号数组解释为属性各级LOD的最新客户端记录。如果这个Entity之前没在这个客户端同步过，则这个LOD数组就是空的。关于属性LOD的内容留在后面介绍，这里先跳过。

将这个数组设置为lodEventNumbers信息之后，这个Entity又会通过addToSeen以最高优先级0加入到同步队列entityQueue_中，等待后续的Witness::update处理。Witness::update处理CreatePending状态的EntityCache时，会先使用sendCreate来发送当前的属性消息到客户端来推动对应Entity在客户端的创建，然后再以当前的位置来计算更新优先级，因为已经没有那么紧急了:

else if (pCache->isCreatePending())
{
	this->sendCreate( bundle, pCache );
	pCache->updatePriority( entity_.position() );
}

/**
 *	This method sends the createEntity message to the client.
 */
void Witness::sendCreate( Mercury::Bundle & bundle, EntityCache * pCache )
{
	size_t oldSize = bundle.size();
	pCache->clearCreatePending();

	if (pCache->isRefresh())
	{
		ERROR_MSG( "Witness::sendCreate: isRefresh = true\n" );
		pCache->clearRefresh();
	}

	MF_ASSERT( pCache->isUpdatable() );

	const Entity & entity = *pCache->pEntity();

	entity.writeVehicleChangeToBundle( bundle, *pCache );

	bool isVolatile = entity.volatileInfo().hasVolatile( 0.f );

	if (isVolatile)
	{
		bundle.startMessage( BaseAppIntInterface::createEntity );
	}
	else
	{
		bundle.startMessage( BaseAppIntInterface::createEntityDetailed );
	}

	{
		CompressionOStream compressedStream( bundle,
			this->entity().pType()->description().externalNetworkCompressionType() );

		compressedStream << entity.id() << entity.clientTypeID();
		compressedStream << entity.localPosition();

		// 省略朝向相关数据的填充

		pCache->addOuterDetailLevel( compressedStream );
	}

	entity.pType()->stats().createEntityCounter().
		countSentToOtherClients( bundle.size() - oldSize );
}

这个sendCreate的逻辑先清除当前GuidCache的CreatePending状态，然后构造一个BaseAppIntInterface::createEntity消息发到客户端，这个消息会先填入当前Entity的id和type，然后再是位置与朝向。最后再通过addOuterDetailLevel来加入当前LOD最大的那些属性信息到消息之中:

/**
 *	This method adds the properties that have changed in the outer detail level
 *	to the input stream.
 */
void EntityCache::addOuterDetailLevel( BinaryOStream & stream )
{
	MF_ASSERT( detailLevel_ == this->numLoDLevels() );
	detailLevel_ = this->numLoDLevels() - 1;
	lastEventNumber_ = this->pEntity()->lastEventNumber();

	this->addChangedProperties( stream );
}

这里被调用的addChangedProperties函数我们在属性LOD里已经介绍过了,读者可以去回顾一下具体内容。

这个CreateEntity的消息会通过Proxy转发到客户端去处理:

VARLEN_CLIENT_MESSAGE_FORWARDER( createEntity )			// forward to client
VARLEN_CLIENT_MESSAGE_FORWARDER( createEntityDetailed )	// forward to client
/**
 *	This method handles a createEntity call from the server.
 */
void ServerConnection::createEntity( BinaryIStream & rawStream )
{
	CompressionIStream stream( rawStream );

	EntityID id;
	stream >> id;

	MF_ASSERT_DEV( id != EntityID( -1 ) )	// old-style deprecated hack
	// Connected Entity gets createCellPlayer instead
	MF_ASSERT( id != id_ );

	EntityTypeID type;
	stream >> type;

	Position3D pos( 0.f, 0.f, 0.f );
	PackedYawPitchRoll< /* HALFPITCH */ false > compressedYPR;
	float yaw;
	float pitch;
	float roll;

	stream >> pos >> compressedYPR;

	compressedYPR.get( yaw, pitch, roll );

	EntityID vehicleID = this->getVehicleID( id );

	if (pHandler_)
	{
		pHandler_->onEntityCreate( id, type,
			spaceID_, vehicleID, pos, yaw, pitch, roll,
			stream );
	}

	this->detailedPositionReceived( id, spaceID_, vehicleID, pos );
}

当客户端接受到这个消息的时候，依次从消息里解析出id,type,pos,yaw，最后使用onEntityCreate来创建Entity并初始化相关属性值:

/*
 *	Override from ServerMessageHandler.
 */
void BWServerMessageHandler::onEntityCreate( EntityID id, 
		EntityTypeID entityTypeID,
		SpaceID spaceID, EntityID vehicleID, const Position3D & position,
		float yaw, float pitch, float roll, BinaryIStream & data )
{
	entities_.handleEntityCreate( id, entityTypeID, spaceID, vehicleID,
		position, yaw, pitch, roll, data );
}
/*
 *	@see ServerMessageHandler::onEntityCreate
 */
void BWEntities::handleEntityCreate( EntityID id, 
		EntityTypeID entityTypeID,
		SpaceID spaceID, EntityID vehicleID, const Position3D & position,
		float yaw, float pitch, float roll, BinaryIStream & data )
{
	MF_ASSERT( !isLocalEntityID( id ) );

	BWEntityPtr pEntity = entityFactory_.create( id, entityTypeID,
			spaceID, data, &connection_ );

	if (!pEntity)
	{
		ERROR_MSG( "BWServerMessageHandler::handleEntityCreate: "
					"Failed for entity %d\n",
				id );
		return;
	}

	Direction3D direction( Vector3( roll, pitch, yaw ) );

	this->addEntity( pEntity.get(), spaceID, vehicleID, position,
		direction );
}

这里真正执行Entity创建的函数entityFactory_.create我们之前在介绍玩家第一次创建的时候已经介绍过了，至此一个Entity进入一个RealEntity的AOI并同步到客户端的完整流程就执行完毕了。

由于Witness::sendCreate开头会把GuidCache的CreatePending状态清除，那么后续Witness::update的时候，处理的逻辑就变了。这里会先通过sendQueueElement将当前EntityCache需要下发的属性打包下去，然后再通过updatePriority来更新当前的LOD等级:

if (!pCache->isUpdatable())
{
	this->handleStateChange( &pCache, queueEnd );
}
else if (!pCache->isPrioritised())
{
	// The entity has not gone anywhere, so we will proceed with the update.
	hasAddedReliableRelativePosition |= this->sendQueueElement( pCache );

	pCache->updatePriority( entity_.position() );
}


/**
 * This method writes client update data to bundle
 *
 * @param pCache  The current entity cache 
 * @return		  True if a reliable position update message was included in the
 *				  bundle, false otherwise.
 */
bool Witness::sendQueueElement( EntityCache * pCache )
{
	Mercury::Bundle & bundle = this->bundle();

	const Entity & otherEntity = *pCache->pEntity();
	bool hasAddedReliableRelativePosition = false;

	// Recalculate the priority value of this entity
	float distSqr = pCache->getLoDPriority( entity_.position() );

	// Send data updates to the client for this entity

#define DEBUG_BANDWIDTH
#ifdef DEBUG_BANDWIDTH
	int oldSize = bundle.size();
#endif // DEBUG_BANDWIDTH

#if VOLATILE_POSITIONS_ARE_ABSOLUTE
	otherEntity.writeClientUpdateDataToBundle( bundle, Position3D::zero(),
		*pCache, distSqr );
#else /* VOLATILE_POSITIONS_ARE_ABSOLUTE */
	hasAddedReliableRelativePosition |=
		otherEntity.writeClientUpdateDataToBundle( bundle,
			referencePosition_, *pCache, distSqr );
#endif /* VOLATILE_POSITIONS_ARE_ABSOLUTE */


#ifdef DEBUG_BANDWIDTH
	if (bundle.size() - oldSize > CellAppConfig::entitySpamSize())
	{
		WARNING_MSG( "Witness::update: "
							"%u added %d bytes to bundle of %u\n",
			otherEntity.id(),
			bundle.size() - oldSize,
			entity_.id() );
	}
#endif // DEBUG_BANDWIDTH

	return hasAddedReliableRelativePosition;
}

到了sendQueueElement里会使用writeClientUpdateDataToBundle根据当前的LOD设置来计算出哪些属性需要同步下去，并加入到bundle里， 相关内容已经在前文中已经介绍过了，读者可以去回顾一下。

接下来来了解一下一个Entity被AOI移除的流程，首先走到之前注册的回调Witness::removeFromAoI:

/**
 *	This method removes the input entity from this entity's Area of Interest.
 *
 *	It is not actually removed immediately. This method is called when an AoI
 *	trigger is untriggered. It adds this to a leftAoI set and the normal
 *	priority queue updating is used to actually remove it from the list.
 */
void Witness::removeFromAoI( Entity * pEntity, bool clearManuallyAdded )
{
	// Check if this is a remove that is matched with an ignored addToAoI call.
	if (this->entity().isInAoIOffload())
	{
		MF_ASSERT( pEntity->isDestroyed() );
		this->entity().isInAoIOffload( false );

		return;
	}

	// 跳过一些容错代码

	// find the entity in our AoI
	EntityCache * pCache = aoiMap_.find( *pEntity );
	// 跳过一些容错代码

	if (clearManuallyAdded)
	{
		pCache->clearManuallyAdded();
		if (pCache->isAddedByTrigger())
		{
			return;
		}
	}
	else
	{
		pCache->clearAddedByTrigger();
		if (pCache->isManuallyAdded())
		{
			return;
		}
	}

	MF_ASSERT( !pCache->isGone() );
	pCache->setGone();

	if (this->shouldAddReplayAoIUpdates())
	{
		this->entity().cell().pReplayData()->addEntityAoIChange( 
			this->entity().id(), *(pCache->pEntity()), 
			/* hasEnteredAoI */ false );
	}

	// Also see the calls in Witness::init() for offloading
	this->entity().callback( "onLeftAoI", PyTuple_Pack( 1, pEntity ),
		"onLeftAoI", true );
}

开头的isInAoIOffload与Entity迁移相关，我们这里先略过。后续的流程就是从aoiMap_里找到这个Entity对应的EntityCache，标记为Gone状态。这里并没有直接删除这个EntityCache，在Witness::update的时候，会通过handleStateChange将Gone状态的Entity通知客户端去销毁,并在aoiMap_里删除这个EntityCache:

void Witness::handleStateChange( EntityCache ** ppCache,
				KnownEntityQueue::iterator & queueEnd )
{
	MF_ASSERT( ppCache != NULL );

	Mercury::Bundle & bundle = this->bundle();
	EntityCache * pCache = *ppCache;

	MF_ASSERT( !pCache->isRequestPending() );
	if (pCache->isGone())
	{
		this->deleteFromSeen( bundle, queueEnd );
		*ppCache = NULL;
	}
	// 省略一些代码
}

void Witness::deleteFromSeen( Mercury::Bundle & bundle,
	KnownEntityQueue::iterator iter )
{
	EntityCache * pCache = *iter;

	this->deleteFromClient( bundle, pCache );
	this->deleteFromAoI( iter );
}

/**
 *	This method removes and deletes an EntityCache from the AoI.
 */
void Witness::deleteFromAoI( KnownEntityQueue::iterator iter )
{
	EntityCache * pCache = *iter;

	// We want to remove this entity from the vector. To do this, we move the
	// last element to the one we want to delete and pop the back.
	*iter = entityQueue_.back();
	entityQueue_.pop_back();

	// Now remove it from the AoI map (if it's in there)
	aoiMap_.del( pCache );
}
/**
 *	Delete the given entity cache from the entity cache map
 *	(the entity cache itself will be deleted by this operation)
 */
void EntityCacheMap::del( EntityCache * ec )
{
	--g_numInAoI;

	MF_ASSERT( ec );
	MF_ASSERT( ec->pEntity() );
	// set_.erase( EntityCacheMap::toIterator( ec ) );
	set_.erase( *ec );
}

这里的deleteFromClient会构造一个BaseAppIntInterface::leaveAoI的RPC，通过Proxy转发到对应的客户端:

/**
 *	This method informs the client that an entity has left its AoI.
 */
void Witness::deleteFromClient( Mercury::Bundle & bundle,
	EntityCache * pCache )
{
	pCache->clearRefresh();

	EntityID id = pCache->pEntity()->id();

	if (!pCache->isEnterPending())
	{
		pCache->addLeaveAoIMessage( bundle, id );
	}

	this->onLeaveAoI( pCache, id );

	// Reset client related state
	pCache->onEntityRemovedFromClient();
}

void EntityCache::addLeaveAoIMessage( Mercury::Bundle & bundle,
	   EntityID id ) const
{
	MF_ASSERT( !this->pEntity() || this->pEntity()->id() == id );

	// The leaveAoI message contains the id of the entity leaving the AoI and
	// then the sequence of event numbers that are the LoD level stamps.

	// TODO: At the moment, we send all of the stamps but we only really need to
	// send stamps for those levels that we actually entered.

	bundle.startMessage( BaseAppIntInterface::leaveAoI );
	bundle << id;

	if (this->pEntity())
	{
		const int size = this->numLoDLevels();

		// For detail levels higher (more detailed) than the current one, we
		// send the stored value.
		for (int i = 0; i < detailLevel_; i++)
		{
			bundle << lodEventNumbers_[i];
		}

		// For the current and lower detail levels, we know that they are all at
		// the current event number. (Only the current one is set and the others
		// are implied).
		for (int i = detailLevel_; i < size; i++)
		{
			bundle << this->lastEventNumber();
		}
	}
}

比较奇怪的是这个RPC除了会带上当前Entity的id字段之外，还会带上各个Lod等级属性的已同步最大序列号。当客户端接收到这个消息之后,会解析出这些序列号，执行onEntityLeave:

/**
 *	This method handles the message from the server that an entity has left our
 *	Area of Interest (AoI).
 */
void ServerConnection::leaveAoI( BinaryIStream & stream )
{
	EntityID id;
	stream >> id;

	// TODO: What if the entity just leaves the AoI and then returns?
	if (controlledEntities_.erase( id ))
	{
		if (pHandler_)
		{
			pHandler_->onEntityControl( id, false );
		}
	}

	if (pHandler_)
	{
		CacheStamps stamps( stream.remainingLength() / sizeof(EventNumber) );

		CacheStamps::iterator iter = stamps.begin();

		while (iter != stamps.end())
		{
			stream >> (*iter);

			iter++;
		}

		pHandler_->onEntityLeave( id, stamps );
	}

	passengerToVehicle_.erase( id );
}

这里的onEntityLeave会通知客户端把这个Entity从当前World里移除，并在这个pEntity的引用计数为0的时候触发这个BWEntity的析构：

/*
 *	Override from ServerMessageHandler.
 */
void BWServerMessageHandler::onEntityLeave( EntityID id, 
		const CacheStamps & stamps )
{
	entities_.handleEntityLeave( id );
}

/**
 *	This method removes an entity from this collection.
 *
 *	@param entityID	The ID of the entity to remove.
 *	@return True if id was a known Entity, false otherwise
 */
bool BWEntities::handleEntityLeave( EntityID entityID )
{
	// We should never be asked to remove the player.
	// Use BWEntities::clear() if you're doing that.
	MF_ASSERT( pPlayer_ == NULL || pPlayer_->entityID() != entityID );

	BWEntityPtr pEntity = this->findAny( entityID );

	if (pEntity == NULL)
	{
		// This may happen if an entity entered and left without being
		// created in between
		return false;
	}

	PassengersVector vPassengers;

	if (activeEntities_.removeEntityFromWorld( entityID, &vPassengers ))
	{
		// 忽略载具相关的处理
	}
	else
	{
		MF_VERIFY( appPendingEntities_.eraseEntity( entityID ) ||
			pendingPassengers_.erasePassenger( entityID ) );
	}

	pEntity->destroyNonPlayer();

	return true;
}

使用十字链表的AOI系统

在Witness里创建的AoITrigger是RangeTrigger的简单子类，负责接受trigger的enter/leave回调并转发到Witness上。上面的小结里我们详解了回调的后续处理逻辑，现在我们来探究区域进出回调是如何产生的，也就是其底层的AOI计算更新方式。我们首先来看一下RangeTrigger的类型定义:

/**
 *	This class encapsulates a full range trigger. It contains a upper and lower
 *	bound trigger node.
 */
class RangeTrigger
{
public:
	RangeTrigger( RangeListNode * pCentralNode, float range,
			RangeListNode::RangeListFlags wantsFlagsLower,
			RangeListNode::RangeListFlags wantsFlagsUpper,
			RangeListNode::RangeListFlags makesFlagsLower,
			RangeListNode::RangeListFlags makesFlagsUpper );
	// 省略一些接口定义
// protected:
public:
	RangeListNode *			pCentralNode_;

	RangeTriggerNode		upperBound_;
	RangeTriggerNode		lowerBound_;

	// Old location of the entity
	float				oldEntityX_;
	float				oldEntityZ_;
};

RangeTrigger::RangeTrigger( RangeListNode * pCentralNode,
		float range,
		RangeListNode::RangeListFlags wantsFlagsLower,
		RangeListNode::RangeListFlags wantsFlagsUpper,
		RangeListNode::RangeListFlags makesFlagsLower,
		RangeListNode::RangeListFlags makesFlagsUpper ) :
	pCentralNode_( pCentralNode ),
	upperBound_( this, range, wantsFlagsUpper, makesFlagsUpper ),
	lowerBound_( this, -range, wantsFlagsLower,
			RangeListNode::RangeListFlags(
				makesFlagsLower | RangeListNode::FLAG_IS_LOWER_BOUND ) ),
	oldEntityX_( pCentralNode->x() ),
	oldEntityZ_( pCentralNode->z() )
{
}

pCentralNode和range的意义我们在前文中已经介绍过了，剩下需要关注的是后面的四个RangeListFlags的意义。从上面贴出的构造函数可以看出，每个RangeTrigger会创建两个RangeTriggerNode节点，分别代表触发范围的上边界与下边界。wantsFlags和makesFlags会被一路传递到RangeTriggerNode的父类RangeListNode之中:

/**
 *	This class is used for range triggers (traps). Its position is the same as
 *	the entity's position plus a range. Once another entity crosses the node, it
 *	will either trigger or untrigger it and it will notify its owner entity.
 */
class RangeTriggerNode : public RangeListNode
{
public:
	RangeTriggerNode( RangeTrigger * pRangeTrigger,
		float range,
		RangeListFlags wantsFlags,
		RangeListFlags makesFlags );

	// 省略很多函数和变量声明
protected:	
	RangeTrigger * pRange_;
	float range_;
	float oldRange_;
};

RangeTriggerNode::RangeTriggerNode( RangeTrigger * pRangeTrigger,
		float range,
		RangeListFlags wantsFlags,
		RangeListFlags makesFlags ) :
	RangeListNode( wantsFlags, makesFlags,
			(makesFlags & FLAG_IS_LOWER_BOUND) ?
				RANGE_LIST_ORDER_LOWER_BOUND :
				RANGE_LIST_ORDER_UPPER_BOUND ),
	pRange_( pRangeTrigger ),
	range_( range ),
	oldRange_( 0.f )
{
}

在RangeListNode的成员变量定义的注释里提供了这两个Flags的作用，makesFlags代表当前节点进出触发边界时应该展示的类型信息，而wantsFlags_则代表的是当前节点作为边界节点时所在意的节点类型信息。即一个RangeListNode(A)穿越了RangeListNode(B)所代表的边界时，如果A->makesFlags_ & B->wantsFlags_ != 0，那么才会引发后续的enter/leave回调，这部分逻辑对应RangeListNode::wantsCrossingWith函数:

/**
 * This class is the base of all range nodes. Range Nodes are used to keep track of
 * the order of entities and triggers relative to the x axis or the z axis.
 * This is used for AoI calculations and range queries.
 */
class RangeListNode
{
public:
	enum RangeListFlags
	{
		FLAG_NO_TRIGGERS		= 0,
		FLAG_ENTITY_TRIGGER		= 0x01,
		FLAG_LOWER_AOI_TRIGGER	= 0x02,
		FLAG_UPPER_AOI_TRIGGER	= 0x04,

		FLAG_IS_ENTITY			= 0x10,
		FLAG_IS_LOWER_BOUND		= 0x20
	};

	RangeListNode( RangeListFlags wantsFlags,
			RangeListFlags makesFlags,
			RangeListOrder order ) :
		pPrevX_( NULL ),
		pNextX_( NULL ),
		pPrevZ_( NULL ),
		pNextZ_( NULL ),
		wantsFlags_( wantsFlags ),
		makesFlags_( makesFlags ),
		order_( order )
	{ }
	virtual ~RangeListNode()	{}
protected:
	//pointers to the prev and next entities in the X and Z direction
	RangeListNode *	pPrevX_;
	RangeListNode *	pNextX_;
	RangeListNode *	pPrevZ_;
	RangeListNode *	pNextZ_;

	// Flags for type of crossings this node wants to receive
	RangeListFlags	wantsFlags_;

	// Flags for type of crossings this node wants to make
	RangeListFlags	makesFlags_;
	RangeListOrder	order_;
};

bool RangeListNode::wantsCrossingWith( RangeListNode * pOther ) const
{
	return (wantsFlags_ & pOther->makesFlags_);
}

了解这两个Flags的意义之后，再回顾一下AoITrigger里传递的Flags的相关值，可以知道当前AoITrigger创建的两个RangeListNode只负责被动接收FLAG_LOWER_AOI_TRIGGER/FLAG_UPPER_AOI_TRIGGER类型的节点的进出边界回调，但是这两个节点自身的移动不会触发任何可能的其他边界节点的enter/leave通知，因为他们的makesFlags都是FLAG_NO_TRIGGERS:

AoITrigger( Witness & owner, RangeListNode * pCentralNode, float range ) :
	RangeTrigger( pCentralNode, range,
			RangeListNode::FLAG_LOWER_AOI_TRIGGER,
			RangeListNode::FLAG_UPPER_AOI_TRIGGER,
			RangeListNode::FLAG_NO_TRIGGERS,
			RangeListNode::FLAG_NO_TRIGGERS ),
	owner_( owner )
{
	// Collect the large entities whose range we currently sit.
	owner_.entity().space().visitLargeEntities(
		pCentralNode->x(),
		pCentralNode->z(),
		*this );

	this->insert();
}

现在进出AOI的触发器已经设置好了，还需要其他的节点充当触发者，来提供FLAG_LOWER_AOI_TRIGGER/FLAG_UPPER_AOI_TRIGGER的makesFlags，这些当作触发者的节点就是EntityRangeListNode节点，他的构造函数里会将自己的wantsFlags设置为FLAG_NO_TRIGGERS，同时将makesFlags设置为FLAG_ENTITY_TRIGGER |FLAG_LOWER_AOI_TRIGGER |FLAG_UPPER_AOI_TRIGGER |FLAG_IS_ENTITY，刚好与之前的AoITrigger相反，因此一个EntityRangeListNode在移动的时候如果进出了一个AoITrigger的相关节点，AoITrigger上的wantsCrossingWith肯定能返回true:

/**
 *	This class is used as an entity's entry into the range list. The position
 *	of this node is the same as the entity's position. When the entity moves,
 *	this node may also move along the x/z lists.
 */
class EntityRangeListNode : public RangeListNode
{
public:
	EntityRangeListNode( Entity * entity );

	float x() const;
	float z() const;

	BW::string debugString() const;
	Entity * getEntity() const;

	void remove();

	void isAoITrigger( bool isAoITrigger );

	static Entity * getEntity( RangeListNode * pNode )
	{
		MF_ASSERT( pNode->isEntity() );
		return static_cast< EntityRangeListNode * >( pNode )->getEntity();
	}

	static const Entity * getEntity( const RangeListNode * pNode )
	{
		MF_ASSERT( pNode->isEntity() );
		return static_cast< const EntityRangeListNode * >( pNode )->getEntity();
	}

protected:
	Entity * pEntity_;
};

/**
 * This is the constructor for the EntityRangeListNode.
 * @param pEntity - entity that is associated with this node
 */
EntityRangeListNode::EntityRangeListNode( Entity * pEntity ) :
	RangeListNode( FLAG_NO_TRIGGERS,
				RangeListFlags(
					FLAG_ENTITY_TRIGGER |
					FLAG_LOWER_AOI_TRIGGER |
					FLAG_UPPER_AOI_TRIGGER |
					FLAG_IS_ENTITY ),
			RANGE_LIST_ORDER_ENTITY ),
	pEntity_( pEntity )
{}

每个Entity在被创建的时候，都会创建一个EntityRangeListNode赋值到当前的pRangeListNode_成员变量上，因此EntityRangeListNode跟Entity总是一对一的:

Entity::Entity( EntityTypePtr pEntityType ):
	PyObjectPlus( pEntityType->pPyType(), true ),
{
	++g_numEntitiesEver;

	pRangeListNode_ = new EntityRangeListNode( this );
}

现在我们有了触发器与触发者，接下来需要一个管理设施来将这两个类型的RangeListNode放在同一个结构里管理，这个结构就是RangeList:

/**
 *	This class implements a range list.
 */
class RangeList
{
public:
	RangeList();

	void add( RangeListNode * pNode );

	// For debugging
	bool isSorted() const;
	void debugDump();

	const RangeListNode * pFirstNode() const	{ return &first_; }
	const RangeListNode * pLastNode() const		{ return &last_; }

	RangeListNode * pFirstNode() { return &first_; }
	RangeListNode * pLastNode()	{ return &last_; }

private:
	RangeListTerminator first_;
	RangeListTerminator last_;
};

这个类型看上去像是一个单链表的定义，其实不然,他是一个十字链表，分别对应X轴和Z轴。与mosaic_game里的十字链表类似，这里有两个特殊的节点first_/last_作为两端的头尾节点来使用。mosaic_game里是给这种头尾节点加上一个aoi_list_node_type的标记，而这里还额外的提供了一个类型RangeListTerminator:

/**
 *	This class is used for the terminators of the range list. They are either
 *	the head or tail of the list. They always have a position of +/- FLT_MAX.
 */
class RangeListTerminator : public RangeListNode
{
public:
	RangeListTerminator( bool isHead ) :
		RangeListNode( RangeListFlags( 0 ), RangeListFlags( 0 ),
				isHead ? RANGE_LIST_ORDER_HEAD : RANGE_LIST_ORDER_TAIL) {}
	float x() const { return (order_ ? FLT_MAX : -FLT_MAX); }
	float z() const { return (order_ ? FLT_MAX : -FLT_MAX); }
	BW::string debugString() const { return order_ ? "Tail" : "Head"; }
};

每个Space内部会有一个RangeList来管理整个Space的AOI,当一个Entity被添加到Space时，会调用到Entity::addToRangeList来将这个Entity加入到这个RangeList中:

/**
 *	This method adds an entity to this space.
 */
void Space::addEntity( Entity * pEntity )
{
	MF_ASSERT( pEntity->removalHandle() == NO_SPACE_REMOVAL_HANDLE );

	pEntity->removalHandle( entities_.size() );
	entities_.push_back( pEntity );

	pEntity->addToRangeList( rangeList_, appealRadiusList_ );
}
/**
 *	This method adds this entity to a range list.
 *
 *	@param rangeList The range list to add to.
 */
void Entity::addToRangeList( RangeList & rangeList,
	RangeTriggerList & appealRadiusList )
{
	AUTO_SCOPED_THIS_ENTITY_PROFILE;

	rangeList.add( pRangeListNode_ );

	// 省略一些代码
}

当执行新节点的插入的时候，这里的add接口会对新加入的节点执行这两个轴的分别插入，做法就是先插入到first_节点的next里,然后再遍历过去直到移动到合适的位置:

/**
 *	This method adds an element to the range list.
 */
void RangeList::add( RangeListNode * pNode )
{
	SCOPED_PROFILE( SHUFFLE_ENTITY_PROFILE );

	MF_ASSERT( pNode != NULL );

	first_.nextX()->insertBeforeX( pNode );
	first_.nextZ()->insertBeforeZ( pNode );
	pNode->shuffleXThenZ( -FLT_MAX, -FLT_MAX );
}

/**
 *	This method inserts a range node before another one in the X list.
 *
 *	@param pNode The node to insert before.
 */
void RangeListNode::insertBeforeX( RangeListNode * pNode )
{
	MF_ASSERT( this != pNode );

	if (pPrevX_!=NULL)
	{
		pPrevX_->pNextX_ = pNode;
	}

	pNode->pPrevX_ = pPrevX_;

	this ->pPrevX_ = pNode;
	pNode->pNextX_ = this;
}

这里的shuffleXThenZ其实也是分别做X轴的平移与Z轴的平移，其内部调用的shuffleX与shuffleZ代码基本一样，除了处理的轴不一样，所以这里只贴出shuffleX的实现:

/**
 *	This method makes sure that this entity is in the correct place in the
 *	global sorted position lists. If a shuffle is performed, crossedX or
 *	crossedZ is called on both nodes.
 *
 *	@param oldX The old value of the x position.
 *	@param oldZ The old value of the z position.
 */
void RangeListNode::shuffleXThenZ( float oldX, float oldZ )
{
	this->shuffleX( oldX, oldZ );
	this->shuffleZ( oldX, oldZ );
	// this->shuffleZ( this->x() );
}

/**
 *	This method makes sure that this entity is in the correct place in X
 *	position lists. If a shuffle is performed, crossedX is called on both nodes.
 *
 *	@param oldX The old value of the x position.
 *	@param oldZ The old value of the z position.
 */
void RangeListNode::shuffleX( float oldX, float oldZ )
{
	MF_ASSERT( !Entity::callbacksPermitted() );
	static bool inShuffle = false;
	MF_ASSERT( !inShuffle );	// make sure we are not reentrant
	inShuffle = true;

	float ourPosX = this->x();
	float othPosX;

	// Shuffle to the left(negative X)...
	while (pPrevX_ != NULL &&
			(ourPosX < (othPosX = pPrevX_->x()) ||
				(isEqual( ourPosX, othPosX ) &&
				order_ <= pPrevX_->order_)))
	{
		if (this->wantsCrossingWith( pPrevX_ ))
		{
			this->crossedX( pPrevX_, true, pPrevX_->x(), pPrevX_->z() );
		}

		if (pPrevX_->wantsCrossingWith( this ))
		{
			pPrevX_->crossedX( this, false, oldX, oldZ );
		}

		// unlink us
		if (pNextX_!= NULL)
		{
			pNextX_->pPrevX_ = pPrevX_;
		}

		pPrevX_->pNextX_ = pNextX_;

		// fix our pointers
		pNextX_ = pPrevX_;
		pPrevX_ = pPrevX_->pPrevX_;

		// relink us
		if (pPrevX_ != NULL)
		{
			pPrevX_->pNextX_= this;
		}

		pNextX_->pPrevX_= this;
	}

	// Shuffle to the right(positive X)...
	while (pNextX_ != NULL &&
			(ourPosX > (othPosX = pNextX_->x()) ||
				(isEqual( ourPosX, othPosX ) &&
				order_ >= pNextX_->order_)))
	{
		if (this->wantsCrossingWith( pNextX_ ))
		{
			this->crossedX( pNextX_, false, pNextX_->x(), pNextX_->z() );
		}

		if (pNextX_->wantsCrossingWith( this ))
		{
			pNextX_->crossedX( this, true, oldX, oldZ );
		}

		// unlink us
		if (pPrevX_ != NULL)
		{
			pPrevX_->pNextX_ = pNextX_;
		}

		pNextX_->pPrevX_ = pPrevX_;
		// fix our pointers
		pPrevX_ = pNextX_;
		pNextX_ = pNextX_->pNextX_;

		// relink us
		pPrevX_->pNextX_ = this;

		if (pNextX_ != NULL)
		{
			pNextX_->pPrevX_ = this;
		}
	}

	inShuffle = false;
}

shuffleX的实现有一点点长，但是代码理解起来还是很简单的，这里分为了互为镜像的两个while循环，第一个while循环负责将当前节点往左移动到最新坐标对应的位置，第二个while循环负责将当前节点往右移动到最新坐标对应的位置。其实可以预先根据OldX与ourPosX的相对大小来只执行其中一个while，ourPosX>OldX的时候往右移，反之往左移动。不过这里反正任何一个while执行到了内部都会导致另外一个while的准入条件不会被满足，因此也就没啥性能影响。

在遍历的过程中除了维护好十字链表的结构之外，最重要的就是触发进入Trigger的回调，也就是这四行代码:

if (this->wantsCrossingWith( pPrevX_ ))
{
	this->crossedX( pPrevX_, true, pPrevX_->x(), pPrevX_->z() );
}

if (pPrevX_->wantsCrossingWith( this ))
{
	pPrevX_->crossedX( this, false, oldX, oldZ );
}

这里的wantsCrossingWith函数我们在前面介绍过了，就是一些mask计算来过滤掉各自不关心的ListNode的进出边界。当这个边界节点对移动的节点感兴趣时，对应的crossed(X/Z)就会被调用。在RangeListNode的基类里这两个函数是空实现的虚函数，只有在子类的RangeTriggerNode里才有具体实现:

class RangeListNode
{
	virtual void crossedX( RangeListNode * /*node*/, bool /*positiveCrossing*/,
		float /*oldOthX*/, float /*oldOthZ*/ ) {}
	virtual void crossedZ( RangeListNode * /*node*/, bool /*positiveCrossing*/,
		float /*oldOthX*/, float /*oldOthZ*/ ) {}
};

/**
 *	This method is called whenever there is a shuffle in the X direction.
 *	The range trigger node then decides whether or not the entity triggers or
 *	untriggers it.
 *
 *	@param pNode Other entity that has crossed this trigger node.
 *	@param positiveCrossing Which direction the shuffle occurred.
 *	@param oldOthX The old x co-ordinate of the other node.
 *	@param oldOthZ The old z co-ordinate of the other node.
 */
void RangeTriggerNode::crossedX( RangeListNode * pNode, bool positiveCrossing,
	float oldOthX, float oldOthZ )
{
	if (pNode->isEntity())
	{
		this->crossedXEntity( pNode, positiveCrossing, oldOthX, oldOthZ );
	}
	else
	{
		this->crossedXEntityRange( pNode, positiveCrossing );
	}
}

目前我们只关心pNode是Entity的情况，因此跟进crossedXEntity的实现:

/**
 *	This method is called whenever there is a shuffle in the X direction.
 *	The range trigger node then decides whether or not the entity triggers or
 *	untriggers it.
 *
 *	@param pNode Other entity that has crossed this trigger node.
 *	@param positiveCrossing Which direction the shuffle occurred.
 *	@param oldOthX The old x co-ordinate of the other node.
 *	@param oldOthZ The old z co-ordinate of the other node.
 */
void RangeTriggerNode::crossedXEntity( RangeListNode * pNode,
		bool positiveCrossing, float oldOthX, float oldOthZ )
{
	if (pNode == pRange_->pCentralNode()) return;

	// x is shuffled first so the old z position is checked.
	const bool wasInZ = pRange_->wasInZRange( oldOthZ, fabsf( oldRange_ ) );

	if (!wasInZ)
	{
		return;
	}

	Entity * pOtherEntity = EntityRangeListNode::getEntity( pNode );

	const bool isEntering = (this->isLowerBound() == positiveCrossing);

	if (isEntering)
	{
		const bool isInX = pRange_->isInXRange( pNode->x(), fabsf( range_ ) );
		const bool isInZ = pRange_->isInZRange( pNode->z(), fabsf( range_ ) );

		if (isInX && isInZ)
		{
			pRange_->triggerEnter( *pOtherEntity );
		}
	}
	else
	{
		const bool wasInX = pRange_->wasInXRange( oldOthX, fabsf( oldRange_ ) );

		if (wasInX)
		{
			pRange_->triggerLeave( *pOtherEntity );
		}
	}
}

由于进出边界的时候都会触发这个crossedXEntity，所以这里的主要逻辑就是在判断当前是进入边界还是离开边界，即需要计算wasIn(X/Z)和isIn(X/Z)这四个变量，然后再去触发对应的Trigger(Enter/Leave)。这里触发的Trigger(Enter/Leave)最终会调用到Witness提供的addToAoI/removeFromAoI，这两个接口已经在上面的小结里介绍过了，读者可以去回顾一下。

由于Entity是不断移动着的，因此Entity需要定期的更新RangeList里对应节点的最新位置。对于Entity身上的pRangeListNode_，每次位置变化的时候都会调用下面的接口来同步位置到RangeList:

/**
 *	This method is called when an Entity's position changes for any reason,
 *	and regardless of whether the Entity is a real or a ghost.
 *
 *	Note: Anything could happen to the entity over this call if it is a real,
 *  since its movement could trip a trigger, which could call script and
 *  offload or destroy this entity (or cancel any controller).
 */
void Entity::updateInternalsForNewPosition( const Vector3 & oldPosition,
		bool isVehicleMovement )
{
	MF_ASSERT_DEV( isValidPosition( globalPosition_ ) );

	START_PROFILE( SHUFFLE_ENTITY_PROFILE );

	// Make sure that no controllers are cancelled while doing this.
	// (And that no triggers are added/deleted/modified!)
	Entity::callbacksPermitted( false );

	// check if upper triggers should move first or lower ones
	bool increaseX = (oldPosition.x < globalPosition_.x);
	bool increaseZ = (oldPosition.z < globalPosition_.z);

	// shuffle the leading triggers
	for (Triggers::iterator it = triggers_.begin(); it != triggers_.end(); it++)
	{
		(*it)->shuffleXThenZExpand( increaseX, increaseZ,
									oldPosition.x, oldPosition.z );
	}

	// shuffle the entity
	pRangeListNode_->shuffleXThenZ( oldPosition.x, oldPosition.z );

	// shuffle the trailing triggers
	for (Triggers::reverse_iterator it = triggers_.rbegin();
			it != triggers_.rend(); it++)
	{
		(*it)->shuffleXThenZContract( increaseX, increaseZ,
										oldPosition.x, oldPosition.z );
	}

	// 省略很多代码
}

注意到这里除了会更新pRangeListNode_的最新位置之外，还会遍历所有挂载在当前Entity上的triggers_去更新，刚好Witness创建的AoITrigger也会注册到这个triggers容器里。

void Witness::init()
{
	// Disabling callbacks is not needed since no script should be triggered but
	// it's helpful for debugging.
	Entity::callbacksPermitted( false );

	// Create AoI triggers around ourself.
	{
		SCOPED_PROFILE( SHUFFLE_AOI_TRIGGERS_PROFILE );
		pAoITrigger_ = new AoITrigger( *this, pAoIRoot_, aoiRadius_ );
		if (this->isAoIRooted())
		{
			MobileRangeListNode * pRoot =
				static_cast< MobileRangeListNode * >( pAoIRoot_ );
			pRoot->addTrigger( pAoITrigger_ );
		}
		else
		{
			entity().addTrigger( pAoITrigger_ );
		}
	}
	// 省略后续代码
}

这里更新triggers_的位置的形式有点特殊，先执行shuffleXThenZExpand，等pRangeListNode_的位置更新之后，再执行shuffleXThenZContract。shuffleXThenZExpand负责移动upper/lower两个节点里与当前移动方向一致的那个节点，效果是扩大upper-lower之间的空间，即expand:

/**
 *	This method shuffles only the trigger nodes that would expand the area
 *	encompassed by this trigger, for a movement in the direction indicated.
 */
void RangeTrigger::shuffleXThenZExpand( bool xInc, bool zInc,
		float oldX, float oldZ )
{
	// TODO: Remove this assert after a while
	MF_ASSERT( isEqual( oldEntityX_, oldX ) );
	MF_ASSERT( isEqual( oldEntityZ_, oldZ ) );
	// It does really matter what arguments are passed here for shuffleX and
	// shuffleZ as they are not used since the triggers do not have
	// FLAG_MAKES_CROSSINGS set.
	RangeTriggerNode* xTrigger = xInc ? &upperBound_ : &lowerBound_;
	xTrigger->shuffleX( oldX + xTrigger->range(), oldZ + xTrigger->range() );
	RangeTriggerNode* zTrigger = zInc ? &upperBound_ : &lowerBound_;
	zTrigger->shuffleZ( oldX + zTrigger->range(), oldZ + zTrigger->range() );
}

shuffleXThenZContract刚好与之相反，负责移动upper/lower两个节点里与当前移动方向反向的那个节点，效果是收缩upper-lower之间的空间，即contract:

/**
 *	This method shuffles only the trigger nodes that would contract the area
 *	encompassed by this trigger, for a movement in the direction indicated.
 */
void RangeTrigger::shuffleXThenZContract( bool xInc, bool zInc,
		float oldX, float oldZ )
{
	// TODO: Remove this assert after a while
	MF_ASSERT( isEqual( oldEntityX_, oldX ) );
	MF_ASSERT( isEqual( oldEntityZ_, oldZ ) );

	// It does really matter what arguments are passed here for shuffleX and
	// shuffleZ as they are not used since the triggers do not have
	// FLAG_MAKES_CROSSINGS set.
	RangeTriggerNode* xTrigger = xInc ? &lowerBound_ : &upperBound_;
	xTrigger->shuffleX( oldX + xTrigger->range(), oldZ + xTrigger->range() );
	RangeTriggerNode* zTrigger = zInc ? & lowerBound_ : &upperBound_;
	zTrigger->shuffleZ( oldX + zTrigger->range(), oldZ + zTrigger->range() );
	oldEntityX_ = pCentralNode_->x();
	oldEntityZ_ = pCentralNode_->z();
}

shuffleXThenZExpand与shuffleXThenZContract之间的差别刚好等于其函数名之间的差别，这样设计的作用是保证移动过程中一个rangeTrigger的lower/upper的位置区间是有效的，即lower <upper，同时保证这个区间内内一定包括了其所附属的Entity的pRangeListNode_。

AOI内Entity同步时的数据压缩

位置与朝向的数据压缩

在发送初始Entity创建信息的函数sendCreate里填充朝向的时候根据isVolatile的值来决定使用压缩精度的数值还是使用全精度的数值，这个Entity::volatileInfo存储的是是否应该以将位置朝向信息当作高频变化属性去同步，如果不是高频变化的话就同步全精度:

void Witness::sendCreate( Mercury::Bundle & bundle, EntityCache * pCache )
{
	// 省略一些代码

	bool isVolatile = entity.volatileInfo().hasVolatile( 0.f );

	if (isVolatile)
	{
		bundle.startMessage( BaseAppIntInterface::createEntity );
	}
	else
	{
		bundle.startMessage( BaseAppIntInterface::createEntityDetailed );
	}

	{
		CompressionOStream compressedStream( bundle,
			this->entity().pType()->description().externalNetworkCompressionType() );

		compressedStream << entity.id() << entity.clientTypeID();
		compressedStream << entity.localPosition();

		if (isVolatile)
		{
			compressedStream << PackedYawPitchRoll< /* HALFPITCH */ false >(
				entity.localDirection().yaw, entity.localDirection().pitch,
				entity.localDirection().roll );
		}
		else
		{
			compressedStream << entity.localDirection().yaw;
			compressedStream << entity.localDirection().pitch;
			compressedStream << entity.localDirection().roll;
		}

		pCache->addOuterDetailLevel( compressedStream );
	}
}

这里的PacketYawPitchRoll结构体会将传入的数据以合适的精度打包为一个字节数组，一般来说是每个分量压缩为一个字节:

// When sending a Yaw-only direction update:
#define YAW_YAWBITS 8

// When sending a Yaw and Pitch direction update:
#define YAWPITCH_YAWBITS 8
#define YAWPITCH_PITCHBITS 8
// Controls whether pitch should be [-pi,pi) or [-pi/2,pi/2)
#define YAWPITCH_HALFPITCH false

// When sending a Yaw, Pitch and Roll direction update:
#define YAWPITCHROLL_YAWBITS 8
#define YAWPITCHROLL_PITCHBITS 8
#define YAWPITCHROLL_ROLLBITS 8
// Controls whether pitch should be [-pi,pi) or [-pi/2,pi/2)
#define YAWPITCHROLL_HALFPITCH true

/**
 *	This class is used to pack a yaw, pitch and roll value for network
 *	transmission.
 *
 *	@ingroup network
 */
template< bool HALFPITCH = YAWPITCHROLL_HALFPITCH,
	int YAWBITS = YAWPITCHROLL_YAWBITS, int PITCHBITS = YAWPITCHROLL_PITCHBITS,
	int ROLLBITS = YAWPITCHROLL_ROLLBITS >
class PackedYawPitchRoll
{
	static const int BYTES = ((YAWBITS + PITCHBITS + ROLLBITS - 1) / 8) + 1;
public:
	PackedYawPitchRoll( float yaw, float pitch, float roll )
	{
		this->set( yaw, pitch, roll );
	}

	PackedYawPitchRoll() {};

	void set( float yaw, float pitch, float roll );
	void get( float & yaw, float & pitch, float & roll ) const;

	friend BinaryIStream& operator>>( BinaryIStream& is,
		PackedYawPitchRoll< HALFPITCH, YAWBITS, PITCHBITS, ROLLBITS > &ypr )
	{
		memcpy( ypr.buff_, is.retrieve( BYTES ), BYTES );
		return is;
	}

	friend BinaryOStream& operator<<( BinaryOStream& os,
		const PackedYawPitchRoll< HALFPITCH, YAWBITS, PITCHBITS, ROLLBITS >
			&ypr )
	{
		memcpy( os.reserve( BYTES ), ypr.buff_, BYTES );
		return os;
	}

private:
	char buff_[ BYTES ];
};

这里的打包机制就是将输入的弧度float(-pi, pi)以丢失精度的方式转为int8(-128, 127)，因为朝向数据并不需要太高的精度：

template< int BITS >
inline int angleToInt( float angle )
{
	const float upperBound = float(1 << (BITS - 1));
	return (int)floorf( angle * (upperBound / MATH_PI) + 0.5f );
}

// Specialisations to use the original fixed-size calculations
/**
 *	This method is used to convert an angle in the range [-pi, pi) into an int
 *	using only a certain number of bits.
 *
 *	@see intToAngle
 */
template<>
inline int angleToInt< 8 >( float angle )
{
	return (int8)floorf( (angle * 128.f) / MATH_PI + 0.5f );
}


/**
 *	This method stores the supplied yaw, pitch and roll values in our buffer
 */
template< bool HALFPITCH, int YAWBITS, int PITCHBITS, int ROLLBITS >
inline void PackedYawPitchRoll< HALFPITCH, YAWBITS, PITCHBITS, ROLLBITS >::set(
	float yaw, float pitch, float roll )
{
	BitWriter writer;
	writer.add( YAWBITS, angleToInt< YAWBITS >( yaw ) );
	writer.add( PITCHBITS,
		HALFPITCH ?
		halfAngleToInt< PITCHBITS >( pitch ) :
	angleToInt< PITCHBITS >( pitch ));
	writer.add( ROLLBITS, angleToInt< ROLLBITS >( roll ) );
	MF_ASSERT( writer.usedBytes() == BYTES );
	memcpy( buff_, writer.bytes(), BYTES );
}

在这样的数据压缩机制下，本来需要3*float的朝向数据变成了3*int8，从12个字节降低到了3个字节。

在后续的数据更新函数Entity::writeClientUpdateDataToBundle中，如果发现不需要将完整精读的位置朝向信息下发的话，会使用writeVolatileDataToBundle来同步最新的位置和朝向下去，以减少流量:

bool Entity::writeClientUpdateDataToBundle( Mercury::Bundle & bundle,
		const Vector3 & basePos,
		EntityCache & cache,
		float lodPriority ) const
{
	// 省略一些代码
	{
		cache.lastVolatileUpdateNumber( volatileUpdateNumber_ );

		if (this->volatileInfo().hasVolatile( lodPriority ))
		{
			const bool isReliable = hasEventsToSend;

			if (cache.isAlwaysDetailed() || (cache.isPrioritised() && CellAppConfig::sendDetailedPlayerVehicles()) )
			{
				this->writeVolatileDetailedDataToBundle( bundle,
						cache.idAlias(), isReliable );
			}
			else
			{
				hasAddedReliableRelativePosition =
					this->writeVolatileDataToBundle( bundle, basePos,
						cache.idAlias(), lodPriority, isReliable );
			}
			// 省略一些代码
		}
	}
	// 省略一些代码
}

这里的writeVolatileDataToBundle函数会利用当前的最新位置与传入的上次同步位置basePos来做差量diff，这样可以避免完整的将Vector3同步下去，减少流量消耗：

bool Entity::writeVolatileDataToBundle( Mercury::Bundle & bundle,
		const Vector3 & basePosition,
		IDAlias idAlias,
		float priorityThreshold,
		bool isReliable ) const
{
	const bool sendAlias    = (idAlias != NO_ID_ALIAS);
	const bool sendOnGround = this->isOnGround();
	const bool shouldSendPosition = volatileInfo_.shouldSendPosition();
	const float scale = CellAppConfig::packedXZScale();

	// Calculate the relative position.
#if VOLATILE_POSITIONS_ARE_ABSOLUTE
	const bool isRelative = false;
	const Vector3 relativePos = localPosition_;
#else /* VOLATILE_POSITIONS_ARE_ABSOLUTE */
	const bool isRelative = (pVehicle_ == NULL);
	const Vector3 relativePos = isRelative ?
		localPosition_ - basePosition : localPosition_;
#endif /* VOLATILE_POSITIONS_ARE_ABSOLUTE */

	if (shouldSendPosition)
	{
		// If we cannot represent the given relative position
		// with a PackedXZ or PackedXYZ (as appropriate) send
		// a detailed volatile position update instead.
		const float maxLimit = sendOnGround ?
			PackedXZ::maxLimit( scale ) :
			PackedXYZ::maxLimit( scale );

		const float minLimit = sendOnGround ?
			PackedXZ::minLimit( scale ) :
			PackedXYZ::minLimit( scale );

		if ((relativePos.x < minLimit) || (maxLimit <= relativePos.x) ||
			(relativePos.z < minLimit) || (maxLimit <= relativePos.z))
		{
			this->writeVolatileDetailedDataToBundle( bundle,
				idAlias, isReliable );
			return false;
		}
	}

	const int posType = shouldSendPosition ? sendOnGround : 2;
	const int dirType = volatileInfo_.dirType( priorityThreshold );

	const int index = sendAlias * 12 + posType * 4 + dirType;

	// We can't actually send an avatarUpdate*NoPosNoDir message, we
	// would never have entered this method.
	// TODO: Remove those messages.
	MF_ASSERT( dirType < 3 || posType < 2 );

	if (isReliable)
	{
		BaseAppIntInterface::makeNextMessageReliableArgs::start(
			bundle ).isReliable = true;
	}

	bundle.startMessage( *getAvatarUpdateMessage( index ) );

	if (sendAlias)
	{
		bundle << idAlias;
	}
	else
	{
		bundle << this->id();
	}

	if (shouldSendPosition)
	{
		if (sendOnGround)
		{
			bundle << PackedXZ( relativePos.x, relativePos.z, scale );
		}
		else
		{
			bundle << PackedXYZ( relativePos.x, relativePos.y, relativePos.z,
					scale );
		}
	}

	// const Direction3D & dir = this->direction();
	const Direction3D & dir = localDirection_;

	switch (dirType)
	{
		case 0:
			bundle << YawPitchRoll( dir.yaw, dir.pitch, dir.roll );
			break;

		case 1:
			bundle << YawPitch( dir.yaw, dir.pitch );
			break;

		case 2:
			bundle << Yaw( dir.yaw );
			break;
	}

	return isReliable && isRelative;
}

其差量diff的原理其实就是计算出位置差量relativePosition,将每个分量乘以一个CellAppConfig::packedXZScale()然后判断这些分量是否都能被一个降低精度的float来表示，这里的PackedXZ/PackedXYZ使用的都是3bit的指数区域加上8bit的尾数构成的低精度float。

// The range of the X and Z components of the position updates are spread over
// the maximumAoIRadius configured in the CellApp based on the least-accurate
// of on-Ground and off-Ground update ranges.
// So the exponent range of the two types of updates is the same, as any
// extra bits in one or the other would be wasted.
// Setting this to 0 will produce fixed-point volatile updates.
#define EXPONENTBITS_XZ 3

// When sending an on-Ground (XZ) position update:
// (EXPONENTBITS_XZ + XZ_MANTISSABITS_XZ + 1) * 2 bits
// Mantissa controls the maximum accuracy of a position update
#define XZ_MANTISSABITS_XZ 8

/**
 *	This class is used to store a packed x and z coordinate.
 */
template< int EXPONENT_BITS = EXPONENTBITS_XZ,
	int MANTISSA_BITS = XZ_MANTISSABITS_XZ >
class PackedGroundPos
{
	// X and Z are each EXPONENT + MANTISSA + 1 (for the sign)
	static const int BITS = (EXPONENT_BITS + MANTISSA_BITS + 1) * 2;
	static const int BYTES = ((BITS - 1) / 8) + 1;
public:
};

typedef PackedGroundPos<> PackedXZ;

如果能被这个低精度float表示的话则只需要发送这个差量数据PackedXZ/PackedXYZ，否则发送全量数据Vector3。这里还会根据当前是否在地面上进一步的忽略高度轴Y轴的数据同步，因为有贴地需求的话客户端总是可以通过XZ投影到地面计算出Y来。

这里的朝向同步也很有意思，根据当前的粒度volatileInfo_.dirType( priorityThreshold )设置来决定同步几个分量，最粗粒度下只同步单个的Yaw分量，最高粒度下需要同步三个分量YawPitchRoll。同时这里的Yaw,YawPitch,YawPitchRoll依然是降低精度的，使用int8来执行数据同步。

/**
 *	This class is used to pack a yaw value for network transmission.
 *
 *	@ingroup network
 */
template< int YAWBITS = YAW_YAWBITS >
class PackedYaw
{
	static const int BYTES = ((YAWBITS - 1) / 8) + 1;
public:
};

综上，最优情况下使用PackedXZ来同步位置以及使用单一的Yaw来同步朝向的话，只需要5个字节，相对于原来的两个vector3占据的24字节来说节省到了1/4，是非常明显的流量优化。

EntityId的数据压缩

在Bigworld中，Entity的ID类型是uint32，由于每次同步一些属性和位置朝向下去的时候都需要将这个ID作为数据的开头进行填充，所以这里也是一个比较大的开销。考虑到客户端能同步到的的Entity一般不会太多，所以可以在当前客户端范围内将一个完整的全局唯一标识符int32_t EntityID映射为一个Witness局部唯一标识符int8_t idAlias:

class EntityCache
{
private:
	IDAlias			idAlias_;					// uint8
};
/**
 *	This method returns the id alias that is used for this entity.
 */
INLINE IDAlias EntityCache::idAlias() const
{
	return idAlias_;
}


/**
 *	This method sets the id alias that is used for this entity.
 */
INLINE void EntityCache::idAlias( IDAlias idAlias )
{
	idAlias_ = idAlias;
}

在Entity因为进入AOI需要打包数据下发到客户端的时候，Witness会给这个Entity分配一个局部唯一索引:

/**
 *	This method sends the enterAoI message to the client.
 */
void Witness::sendEnter( Mercury::Bundle & bundle, EntityCache * pCache )
{
	size_t oldSize = bundle.size();
	const Entity * pEntity = pCache->pEntity().get();

	pCache->idAlias( this->allocateIDAlias( *pEntity ) );
	// 省略后续代码
}

/**
 *	This method allocates a new id alias for the input entity. It may allocate
 *	NO_ID_ALIAS.
 */
IDAlias Witness::allocateIDAlias( const Entity & entity )
{
	// Only give an ID alias to those entities who have volatile data.
	// TODO: Consider whether this should be done on the entity's volatileInfo
	// or the entity type's volatileInfo.
	if (entity.volatileInfo().hasVolatile( 0.f ) &&
			numFreeAliases_ != 0)
	{
		numFreeAliases_--;
		return freeAliases_[ numFreeAliases_ ];
	}

	return NO_ID_ALIAS;
}

这里的allocateIDAlias机制是内部提前预分配好255个索引放在freeAliases里，这样可以很方便的通过numFreeAliases_来申请和放回:

class Witness
{
private:
	IDAlias freeAliases_[ 256 ];
	int		numFreeAliases_;
};

Witness::Witness( RealEntity & owner, BinaryIStream & data,
		CreateRealInfo createRealInfo, bool hasChangedSpace )
{
	// 省略一些代码
			// In the freeAliases_ array, we want the first numFreeAliases_ to contain
	// the free aliases. To do this, we first fill the array with 1s. We then go
	// through and set the elements whose index is used to 0. We then traverse
	// this array. For each 1 we find, we know that we add that index to the set
	// and increase the number found by 1.
	memset( freeAliases_, 1, sizeof( freeAliases_ ) );
	// 省略一些代码
	// Finish setting up freeAliases_. Currently, the array has 1s corresponding
	// to free ids and 0s corresponding to used. We want the set of free numbers
	// to be at the start of the array.

	// Make sure that this NO_ID_ALIAS is reserved, and not actually used as an
	// ID.
	freeAliases_[ NO_ID_ALIAS ] = 0;

	for (uint i = 0; i < sizeof( freeAliases_ ); i++)
	{
		// If temp is 0, next space is written but numFreeAliases_ is not
		// incremented. Doing it this way avoids any if statements.
		int temp = freeAliases_[i];
		freeAliases_[ numFreeAliases_ ] = i;
		numFreeAliases_ += temp;
	}
}
/**
 *	This method does the work that needs to be done when an entity leaves this
 *	entity's Area of Interest.
 */
void Witness::onLeaveAoI( EntityCache * pCache, EntityID id )
{
	if (pCache->idAlias() != NO_ID_ALIAS)
	{
		freeAliases_[ numFreeAliases_ ] = pCache->idAlias();
		numFreeAliases_++;
	}
}

这样设置好了idAlias，给客户端发送的创建Entity的数据里就需要填充这个参数:

void Witness::sendEnter( Mercury::Bundle & bundle, EntityCache * pCache )
{
	// 省略一些代码
	if (pEntity->pVehicle() != NULL)
	{
		// 忽略载具相关的处理
	}
	else
	{
		BaseAppIntInterface::enterAoIArgs & rEnterAoI =
			BaseAppIntInterface::enterAoIArgs::start( bundle );

		rEnterAoI.id = pEntity->id();
		rEnterAoI.idAlias = pCache->idAlias();
	}
	pEntity->pType()->stats().enterAoICounter().
		countSentToOtherClients( bundle.size() - oldSize );
}

当客户端接收到这个enterAoI的RPC时，会在客户端建立Alias到EntityID的映射:

void ServerConnection::enterAoI( EntityID id, IDAlias idAlias,
		EntityID vehicleID )
{
	// Set this even if args.idAlias is NO_ID_ALIAS.
	idAlias_[ idAlias ] = id;

	if (pHandler_)
	{
		const CacheStamps * pStamps = pHandler_->onEntityCacheTest( id );

		if (pStamps)
		{
			this->requestEntityUpdate( id, *pStamps );
		}
		else
		{
			this->requestEntityUpdate( id );
		}
	}
}

在完成了初次的数据同步之后，后续的数据更新writeClientUpdateDataToBundle提供Entity标识符的时候就只需要这个单字节的idAlias，而不需要完整的四字节了:

bool Entity::writeClientUpdateDataToBundle( Mercury::Bundle & bundle,
		const Vector3 & basePos,
		EntityCache & cache,
		float lodPriority ) const
{
	// 省略之前的代码
	bool hasAddedReliableRelativePosition = false;

	// Not currently enabled as it affects the filters if this is not sent
	// regularly.
	//if (cache.lastVolatileUpdateNumber() != volatileUpdateNumber_)
	{
		cache.lastVolatileUpdateNumber( volatileUpdateNumber_ );

		if (this->volatileInfo().hasVolatile( lodPriority ))
		{
			const bool isReliable = hasEventsToSend;

			if (cache.isAlwaysDetailed() || (cache.isPrioritised() && CellAppConfig::sendDetailedPlayerVehicles()) )
			{
				this->writeVolatileDetailedDataToBundle( bundle,
						cache.idAlias(), isReliable );
			}
			else
			{
				hasAddedReliableRelativePosition =
					this->writeVolatileDataToBundle( bundle, basePos,
						cache.idAlias(), lodPriority, isReliable );
			}

			hasSelectedEntity = true;

			oldSize = bundle.size();
			g_nonVolatileBytes += (oldSize - initSize);
	#if ENABLE_WATCHERS
			pEntityType_->stats().countVolatileSentToOtherClients(
					oldSize - initSize );
	#endif
		}
	}
	// 省略后续代码
}

值得注意的是由于当前alias可用数量只有255个，如果当前Witness没有剩余的alias给新的EntityCache分配的话，这个EntityCache里就无法设置alias，此时下发数据的时候需要带上完整的EntityID。为了方便客户端判断消息里使用的是EntityID还是Alias，下发数据的时候会根据是否有Alias来生成不同的msgID:

bool Entity::writeVolatileDataToBundle( Mercury::Bundle & bundle,
		const Vector3 & basePosition,
		IDAlias idAlias,
		float priorityThreshold,
		bool isReliable ) const
{
	const bool sendAlias    = (idAlias != NO_ID_ALIAS);
	// 省略一些代码
	const int index = sendAlias * 12 + posType * 4 + dirType;
	bundle.startMessage( *getAvatarUpdateMessage( index ) );
	// 省略后续代码
}

这个getAvatarUpdateMessage内部会为所有类型的数据更新都生成一个使用EntityID的msgID和一个使用Alias的EntityID:

const Mercury::InterfaceElement * Entity::getAvatarUpdateMessage( int index )
{

#define BEGIN_AV_UPD_MESSAGES()											\
	static const Mercury::InterfaceElement * s_avatarUpdateMessage[] =	\
	{

#define AV_UPD_MESSAGE( TYPE ) &BaseAppIntInterface::avatarUpdate##TYPE,

#define END_AV_UPD_MESSAGES()	};

	BEGIN_AV_UPD_MESSAGES()
		AV_UPD_MESSAGE( NoAliasFullPosYawPitchRoll )
		AV_UPD_MESSAGE( NoAliasFullPosYawPitch )
		AV_UPD_MESSAGE( NoAliasFullPosYaw )
		AV_UPD_MESSAGE( NoAliasFullPosNoDir )

		AV_UPD_MESSAGE( NoAliasOnGroundYawPitchRoll )
		AV_UPD_MESSAGE( NoAliasOnGroundYawPitch )
		AV_UPD_MESSAGE( NoAliasOnGroundYaw )
		AV_UPD_MESSAGE( NoAliasOnGroundNoDir )

		AV_UPD_MESSAGE( NoAliasNoPosYawPitchRoll )
		AV_UPD_MESSAGE( NoAliasNoPosYawPitch )
		AV_UPD_MESSAGE( NoAliasNoPosYaw )
		AV_UPD_MESSAGE( NoAliasNoPosNoDir )

		AV_UPD_MESSAGE( AliasFullPosYawPitchRoll )
		AV_UPD_MESSAGE( AliasFullPosYawPitch )
		AV_UPD_MESSAGE( AliasFullPosYaw )
		AV_UPD_MESSAGE( AliasFullPosNoDir )

		AV_UPD_MESSAGE( AliasOnGroundYawPitchRoll )
		AV_UPD_MESSAGE( AliasOnGroundYawPitch )
		AV_UPD_MESSAGE( AliasOnGroundYaw )
		AV_UPD_MESSAGE( AliasOnGroundNoDir )

		AV_UPD_MESSAGE( AliasNoPosYawPitchRoll )
		AV_UPD_MESSAGE( AliasNoPosYawPitch )
		AV_UPD_MESSAGE( AliasNoPosYaw )
		AV_UPD_MESSAGE( AliasNoPosNoDir )
	END_AV_UPD_MESSAGES()

	MF_ASSERT( 0 <= index && index < 24 );

	return s_avatarUpdateMessage[ index ];
}

客户端会根据接收到的msgID信息来决定是使用哪个函数去解析输入的ID:

void ServerConnection::avatarUpdateNoAliasDetailed(
	const ClientInterface::avatarUpdateNoAliasDetailedArgs & args )
{
	EntityID id = args.id;

	selectedEntityID_ = id;

	/* Ignore updates from controlled entities */
	if (this->isControlledLocally( id ))	
	{
		return;
	}

	EntityID vehicleID = this->getVehicleID( id );

	if (pHandler_ != NULL)
	{
		pHandler_->onEntityMoveWithError( id, spaceID_, vehicleID,
			args.position, Vector3::zero(), args.dir.yaw,
			args.dir.pitch, args.dir.roll, /* isVolatile */ true );
	}

	this->detailedPositionReceived( id, spaceID_, vehicleID, args.position );
}

void ServerConnection::avatarUpdateAliasDetailed(
	const ClientInterface::avatarUpdateAliasDetailedArgs & args )
{
	EntityID id = idAlias_[ args.idAlias ];

	selectedEntityID_ = id;

	/* Ignore updates from controlled entities */
	if (this->isControlledLocally( id ))	
	{
		return;
	}

	EntityID vehicleID = this->getVehicleID( id );

	if (pHandler_ != NULL)
	{
		pHandler_->onEntityMoveWithError( id, spaceID_, vehicleID,
			args.position, Vector3::zero(), args.dir.yaw,
			args.dir.pitch, args.dir.roll, /* isVolatile */ true );
	}

	this->detailedPositionReceived( id, spaceID_, vehicleID, args.position );
}

属性同步的流量控制

在前面的内容中我们提到了EntityCache上的一个Priority字段，这个字段代表了这个EntityCache的同步优先级。这个同步优先级是为了限制单帧下发的数据量而存在的，通过限制单帧同步数据量来减少一些情况下的性能毛刺。为了做到有效的流量控制，在Witness::update的时候会通过entityQueue_这个基于数组的EntityCache的优先级的最小堆来不断的拿出其中优先级最高的EntityCache去处理：

void Witness::update()
{
	// 省略很多代码


	// This is the maximum amount of priority change that we go through in a
	// tick. Based on the default AoIUpdateScheme (distance/5 + 1) things up
	// to 45 metres away can be sent every frame.
	const float MAX_PRIORITY_DELTA =
		CellAppConfig::witnessUpdateMaxPriorityDelta();

	// We want to make sure that entities at a distance are never sent at 10Hz.
	// What we do is make sure that the change in priorities that we go over is
	// capped.
	// Note: We calculate the max priority from the front priority. We should
	// probably calculate from the previous maxPriority. Doing it the current
	// way, if you only have 1 entity in your AoI, it will be sent every frame.
	EntityCache::Priority maxPriority = entityQueue_.empty() ? 0.f :
		entityQueue_.front()->priority() + MAX_PRIORITY_DELTA;

	KnownEntityQueue::iterator queueBegin = entityQueue_.begin();
	KnownEntityQueue::iterator queueEnd = entityQueue_.end();

			// Entities in queue &&
	while ((queueBegin != queueEnd) &&
				// Priority change less than MAX_PRIORITY_DELTA &&
				(*queueBegin)->priority() < maxPriority &&
				// Packet still has space (includes 2 bytes for sequenceNumber))
				bundle.size() < desiredPacketSize - 2)
	{
		loopCounter++;

		// Pop the top entity. pop_heap actually keeps the entity in the vector
		// but puts it in the end. [queueBegin, queueEnd) is a heap and
		// [queueEnd, entityQueue_.end()) has the entities that have been popped
		EntityCache * pCache = entityQueue_.front();
		std::pop_heap( queueBegin, queueEnd--, PriorityCompare() );
		bool wasPrioritised = pCache->isPrioritised();
		
		// See if the entity is still in our AoI

		MF_ASSERT(!pCache->isRequestPending());

		if (pCache->pEntity()->isDestroyed() && !pCache->isGone())
		{
			MF_ASSERT(pCache->isManuallyAdded());
			this->removeFromAoI( const_cast<Entity *>( pCache->pEntity().get() ),
				 /* clearManuallyAdded */ true );
		}

		if (!pCache->isUpdatable())
		{
			this->handleStateChange( &pCache, queueEnd );
		}
		else if (!pCache->isPrioritised())
		{
			// The entity has not gone anywhere, so we will proceed with the update.
			hasAddedReliableRelativePosition |= this->sendQueueElement( pCache );

			pCache->updatePriority( entity_.position() );
		}
	}
	// 省略后续代码
}

注意到上面的while循环的终止条件,开头的queueBegin != queueEnd是为了避免当前的最小二叉树为空，最后的bundle.size() < desiredPacketSize - 2是为了限制当前update生成的bundle的数据大小不能超过desiredPacketSize太多，这两个条件也就是常规的基于同步优先级的流量控制条件。至于中间的(*queueBegin)->priority() < maxPriority就设计的很巧妙了，他限定了要被更新的EntityCache的优先级与初始时entityQueue_里顶部元素的优先级差值不能超过MAX_PRIORITY_DELTA，注释里说这个条件的作用是为了限制在一定范围外的EntityCache的向下同步频率不能超过10HZ,下面我们来看看Bigworld是如何实现这个目标的。

对于每一个被更新到的EntityCache，在执行完sendQueueElement之后，都会以当前的位置来计算新的同步优先级:

/**
 *	This method updates the priority associated with this cache.
 */
INLINE void EntityCache::updatePriority( const Vector3 & origin )
{
	// TODO: The use of a double precision floating for the priority
	//		values gives 52 bits for significant figures.
	//
	//		If we increment the priority values by 10000 a second, we will
	//		run into trouble in about 140 years (provided the avatar doesn't
	//		change cells in that time), so we probably won't need to reset
	//		the priority values.
	//
	//		At present, we are incrementing priority values at around
	//		1000 per second - which assumes that everyone is roughly 500
	//		metres from the avatar.
	//
	// PM:	One solution to this would be to use an integer value for the
	//		priority and use a comparison that wraps. e.g. (x - y) > 0. This
	//		would work if the range in the priorities never exceeds half the
	//		range of the integer type.

	float distSQ = this->getDistanceSquared( origin );

	Priority delta = AoIUpdateSchemes::apply( updateSchemeID_, distSQ );

	// Limit the delta increase to a fraction of the previous delta to avoid
	// client's avatar filter starvation caused by rapid priority changes due
	// to AoI update scheme change.
	const double deltaGrowthThrottle =
		CellAppConfig::witnessUpdateDeltaGrowthThrottle();
	delta = std::min( delta, deltaGrowthThrottle * lastPriorityDelta_ );
	lastPriorityDelta_ = delta;

	// MF_ASSERT( priority_ < BW_MAX_PRIORITY );
	priority_ += delta;
	// MF_ASSERT( priority_ < BW_MAX_PRIORITY );
}

/**
	*	This method applies the AoI update scheme, returning a priority delta
	*	for the given distance.
	*
	*	@param distanceSquared 	The distance from the witness, squared.
	*	@return 				The priority delta.
	*/
double apply( float distanceSquared ) const
{
	if (this->shouldTreatAsCoincident())
	{
		return 1.0;
	}

	const float distance = sqrtf( distanceSquared );
	return (distance * distanceWeighting_ + 1.f) * weighting_;
}

一个EntityCache刚进入AOI的时候其初始priority都会被设置为0, 后续的priority更新都需要通过EntityCache::updatePriority。这里的EntityCache::updatePriority的核心逻辑是根据当前EntityCache与Witness之间的距离来计算priority的Delta值，在默认实现的AoIUpdateSchemes::apply里，这个Delta值与距离distance成简单线性关系。在这样的设定下，距离Witness越近的EntityCache其priority增加的越慢，而距离Witness越远的EntityCache其priority增加的越快。这里用一个简单的例子来描述一下在这样的priority更新机制下的EntityCache基于距离的同步频率限制是怎么做到的。假设当前有Witness(A)和EntityCache(B),EntityCache(C), B,C都刚刚加入到AOI中因此priority都是0。但是B距离A只有10M，同时C距离A有30M,这样就会导致B的priority每次会增加1，同时C的priority每次增加3。

假如所有的Entity的位置在之后都不发生改变，且下行流量会被desiredPacketSize限制到每次只能同步一个EntityCache，那么Witness::update会以这样的形式来触发EntityCache的下行同步:

1. 初始的时候entityQueue_里经过排序的优先级为B(0), C(0)，向下同步B，同时优先级排序结果更新为C(0),B(1)
2. 第二次, 向下同步C，同时优先级排序结果更新为B(1),C(3)
3. 第三次, 向下同步B，同时优先级排序结果更新为B(2),C(3)
4. 第四次, 向下同步B，同时优先级排序结果更新为B(3),C(3)
5. 第五次, 向下同步B，同时优先级排序结果更新为C(3),B(4)
6. 第六次, 向下同步C，同时优先级排序结果更新为B(4),C(6)
7. 第七次, 向下同步B，同时优先级排序结果更新为B(5),C(6)
8. 第八次, 向下同步B，同时优先级排序结果更新为B(6),C(6)
9. 第九次, 向下同步B，同时优先级排序结果更新为C(6),B(7)
10. 第十次, 向下同步C，同时优先级排序结果更新为B(7),C(9)

从上面的分析可以看出，每四次更新会执行三次B的同步，同时执行一次C的同步，这样就达到了基于距离的降频的目的。

如果desiredPacketSize设置的比较大导致单帧可以同步的EntityCache数量比较多，此时就可以通过MAX_PRIORITY_DELTA来进行补充限频，在MAX_PRIORITY_DELTA=0.8的限制下，我们再来分析一下EntityCache的下行同步:

1. 初始的时候entityQueue_里经过排序的优先级为B(0), C(0)，向下同步B,C，同时优先级排序结果更新为B(1),C(3)
2. 第二次, 3-1>0.8，因此C被限制无法向下同步，只能同步B，同时优先级排序结果更新为B(2),C(3)
3. 第三次, 3-2>0.8, 因此C被限制无法向下同步，只能同步B，同时优先级排序结果更新为B(3),C(3)
4. 第四次, 3-3<0.8，因此向下同步B,C，同时优先级排序结果更新为B(4),C(6)
5. 第五次, 6-4>0.8，因此C被限制无法向下同步，只能同步B，同时优先级排序结果更新为B(5),C(6)
6. 第六次, 6-5>0.8, 因此C被限制无法向下同步，只能同步B，同时优先级排序结果更新为B(6),C(6)
7. 第七次, 6-6<0.8，因此向下同步B,C，同时优先级排序结果更新为B(7),C(9)

由于Witness::update获取了当前entityQueue_的最高优先级元素之后都会使用pop_heap将这个元素放到entityQueue_最小堆的末尾，并更新这个EntityCache的priority，所以在while循环结束之后，我们需要重新维护好这个entityQueue_完整数组的最小堆的性质。最简单的情况是当前while循环里会处理entityQueue_的所有元素，此时会将整个entityQueue_里的所有EntityCache的priority都设置为0，这样可以避免priority的无限膨胀:

// We need to push all of the sent entities back on the heap.

if (queueEnd == entityQueue_.begin())
{
	// Must have sent and popped all prioritised entities.
	MF_ASSERT( numPrioritised == 0 );

	START_PROFILE( profileMakeHeap );
	while (queueEnd != entityQueue_.end())
	{
		// TODO: Ask Murph about this... Shouldn't this then updatePriority
		// according to current distance?
		// As it is, if we empty the queue, next tick will send entities in
		// random order. We know we've just finished sending _everything_,
		// so we should send them again in order of closeness.
		(*queueEnd)->priority( 0.f );
		// i.e. now,
		// (*queueEnd)->updatePriority( entity_.position() );
		// TODO: Blame this file, perhaps.

		++queueEnd;
	}

	std::make_heap( entityQueue_.begin(), entityQueue_.end(), PriorityCompare() );
	STOP_PROFILE_WITH_DATA( profileMakeHeap, entityQueue_.size() );
}

这里维护最小堆的时候直接对整个entityQueue_做一个make_heap即可，其实不调用make_heap也是可以的，因为里面的priority都是0。

对于出现有些EntityCache被限制下行的情况，需要将所有已经下发的EntityCache重新通过push_heap来加入到最小堆中:

if (queueEnd == entityQueue_.begin())
{
	// 这里处理所有的EntityCache都下发的情况
}
else
{
	EntityCache::Priority earliestPriority = entityQueue_.front()->priority();

	START_PROFILE( profileClearPrioritised );
	int count=0;
	// 忽略载具相关处理
	STOP_PROFILE_WITH_DATA( profileClearPrioritised, count );

	// Must have sent and cleared all prioritised entities.
	MF_ASSERT( numPrioritised == 0 );

	START_PROFILE( profilePush );
	count=0;
	while (queueEnd != entityQueue_.end())
	{
		// We want to do a check to make sure no entity gets sent in the
		// "past". If an entity should have be sent multiple times in a
		// frame it does not keep up with virtual time without this check.
		if ((*queueEnd)->priority() < earliestPriority)
		{
			(*queueEnd)->priority( earliestPriority );
		}

		count++;
		std::push_heap( queueBegin, ++queueEnd, PriorityCompare() );
	}
	STOP_PROFILE_WITH_DATA( profilePush, count );
}

这里有一个earliestPriority处理，其作用是避免低优先级的EntityCache长期被高优先级的EntityCache拦住。因为高优先级的EntityCache增加的太慢了，可能需要好多次update才能超过低优先级EntityCache的priority。所以这里判断发现一个已经处理的EntityCache的优先级居然比未处理的EntityCache的优先级还高，那么会快速提升这个priority。

迁移对AOI同步的影响

上述的AOI内同步流程还需要处理大世界里不可避免的迁移的情况，假设当前Entity(A)需要往RealEntity(B)的客户端执行同步，我们需要分别处理下面两种情况:

1. RealEntity(B)可能会从一个Cell迁移到另外一个Cell，如何避免迁移之后对于Entity(A)的EntityCache记录不丢失。
2. Entity(A)可能从GhostEntity切换为了RealEntity，也可能从RealEntity切换为了GhostEntity，如何在Ghost/Real之间维护好这个eventHistory_的同步

如果每次迁移之后EntityCache的同步进度都丢失，那么迁移之后就需要对当前客户端里的所有Entity都重新执行一次Witness::addToAoi，这样会导致当前所有客户端Entity的所有客户端属性的最新副本被重新打包，这是不可接受的。所以RealEntity在迁移的时候，会将Witness的状态也打包进去，放到stream里的最后面:

/**
 *	This method should put the relevant data into the input BinaryOStream so
 *	that this entity can be onloaded to another cell. It is mostly read off
 *	in the readOffloadData except for a bit done in our constructor above.
 *
 *	@param data		The stream to place the data on.
 *	@param isTeleport Indicates whether this is a teleport.
 */
void RealEntity::writeOffloadData( BinaryOStream & data, bool isTeleport )
{

	// 省略很多代码
	// ----- below here read off in our constructor above
	if (pWitness_ != NULL)
	{
		data << 'W';
		pWitness_->writeOffloadData( data );
	}
	else
	{
		data << '-';
	}
}

这个Witness::writeOffloadData会把当前的记录都下发下去,其内部的writeAoI负责将每个EntityCache相关数据写入进去:

/**
 *	This method should put the relevant data into the input BinaryOStream so
 *	that this entity can be onloaded to another cell.
 *
 *	@param data		The stream to place the data on.
 */
void Witness::writeOffloadData( BinaryOStream & data ) const
{
#if !VOLATILE_POSITIONS_ARE_ABSOLUTE
	data << referencePosition_ << referenceSeqNum_ << hasReferencePosition_;
#endif /* !VOLATILE_POSITIONS_ARE_ABSOLUTE */

	data << maxPacketSize_;

	data << stealthFactor_;

	this->writeSpaceDataEntries( data );

	this->writeAoI( data );
}

/**
 *	This method writes the AoI from the Witness to a stream to be used in
 *	onloading.
 *
 *	@param data The output stream to write the witness' AoI to.
 */
void Witness::writeAoI( BinaryOStream & data ) const
{
	// NOTE: This needs to match StreamHelper::addRealEntityWithWitnesses
	// in bigworld/src/lib/server/stream_helper.hpp
	// and Witness::readAoI

	data << (uint32)aoiMap_.size();
	data << aoiRadius_ << aoiHyst_;

	data << this->isAoIRooted();

	if (this->isAoIRooted())
	{
		data << this->pAoIRoot()->x() << this->pAoIRoot()->z();
	}

	// write the AoI
	aoiMap_.writeToStream( data );
}

/**
 *	Write out all our entries to the given stream.
 *	Our size has already been written out.
 */
void EntityCacheMap::writeToStream( BinaryOStream & stream ) const
{
	Implementor::iterator it = set_.begin();
	Implementor::iterator nd = set_.end();
	for (; it != nd; ++it)
	{
		stream << *it;
	}
}

当执行单个EntityCache的序列化的时候，会将当前的最新版本号lastEventNumber_，最新粒度等级detailLevel_，以及每个LodLevel下的最新同步版本号都写入进去，这些数据就是我们目前执行属性同步最重要的部分：

/**
 *	Streaming operator for EntityCache.
 */
BinaryOStream & operator<<( BinaryOStream & stream,
		const EntityCache & entityCache )
{
	EntityConstPtr pEntity = entityCache.pEntity();
	stream << pEntity->id();

	EntityCache::VehicleChangeNum vehicleChangeNumState =
		EntityCache::VEHICLE_CHANGE_NUM_OLD;

	if (pEntity->vehicleChangeNum() == entityCache.vehicleChangeNum())
	{
		vehicleChangeNumState =
			pEntity->pVehicle() ?
				EntityCache::VEHICLE_CHANGE_NUM_HAS_VEHICLE :
				EntityCache::VEHICLE_CHANGE_NUM_HAS_NO_VEHICLE;
	}

	stream <<
		entityCache.flags_ <<
		entityCache.updateSchemeID_ <<
		// Stream on the state of the vehicleChangeNum_ instead of the current
		// value. This is used to set an appropriate value on the reading side.
		vehicleChangeNumState << // entityCache.vehicleChangeNum_ <<
		// NOTE: It's been explicitly decided it's not worthwhile streaming
		// lastPriorityDelta_. This could cause a rapid priority increase if an
		// offload occurs while adjusting to a large priority delta change.
		entityCache.priority_ <<
		entityCache.lastEventNumber_ <<
		entityCache.idAlias_ <<
		entityCache.detailLevel_;

	// Only have to stream on the size because if the receiving cell does not
	// have this entity, it does not know the type of the entity and so does
	// not know the cache size.
	// TODO: Could add the type instead.

	int size = entityCache.numLoDLevels();

	stream << uint8(size);

	for (int i = 0; i < size - 1; i++)
	{
		stream << entityCache.lodEventNumbers_[i];
	}

	if (vehicleChangeNumState == EntityCache::VEHICLE_CHANGE_NUM_HAS_VEHICLE)
	{
		// This is read off in Witness::Witness.
		stream << pEntity->pVehicle()->id();
	}

	return stream;
}

当迁移到目标进程之后，会按照上述流程的逆过程将Witness以及内部的所有EntityCache执行重建,这里就只贴出Witness::readAoI的代码:

/**
 *	This method reads the AoI from the stream to initialise the Witness.
 *
 *	@param data	The input stream containing the AoI initialise from.
 */
void Witness::readAoI( BinaryIStream & data )
{
	// NOTE: This needs to match StreamHelper::addRealEntityWithWitnesses
	// in bigworld/src/lib/server/stream_helper.hpp
	// and Witness::writeAoI

	uint32 entityQueueSize = 0;
	data >> entityQueueSize;

	data >> aoiRadius_ >> aoiHyst_;

	bool isAoIRooted;
	data >> isAoIRooted;

	MF_ASSERT( !this->isAoIRooted() );

	// 忽略一些代码

	MF_ASSERT( isAoIRooted == this->isAoIRooted() );

	// Read in the Area of Interest entities. We need to be careful that the
	// new AoI that is constructed matches what the client thinks the AoI is.
	MF_ASSERT( entityQueueSize < 1000000 );

	if (entityQueueSize == 0)
	{
		return;
	}

	// Number of entities that do not even exist on this CellApp.
	int numLostEntities = 0;

	entityQueue_.reserve( entityQueueSize );

	for (size_t i = 0; i < entityQueueSize; i++)
	{
		EntityID id;
		data >> id;

		Entity * pEntity = CellApp::instance().findEntity( id );

		if (pEntity == NULL)
		{
			// We are not concerned about the alias due to the leave being sent
			// before the client is notified of enters
			EntityCache dummyCache( NULL );
			data >> dummyCache;
			// 忽略一些AOI记录的Entity已经找不到的处理
			++numLostEntities;
			continue;
		}

		EntityCache * pCache = aoiMap_.add( *pEntity );

		data >> *pCache;

		EntityID expectedVehicleID = 0;
		if (pCache->vehicleChangeNum() ==
			EntityCache::VEHICLE_CHANGE_NUM_HAS_VEHICLE)
		{
			// This is written in EntityCache's streaming operator
			data >> expectedVehicleID;
		}
		entityQueue_.push_back( pCache );
		// we add pending entities to the queue too (init removes them)
		MF_ASSERT( pCache->idAlias() == NO_ID_ALIAS ||
				freeAliases_[ pCache->idAlias() ] == 1 );
		freeAliases_[ pCache->idAlias() ] = 0;

		MF_ASSERT( !pEntity->isInAoIOffload() );
		pEntity->isInAoIOffload( true );

		pCache->setGone();
		// 省略一些代码
	}

	std::make_heap( entityQueue_.begin(), entityQueue_.end(), PriorityCompare() );

	if (numLostEntities > 0)
	{
		INFO_MSG( "Witness::readAoI: Lost %d of %u entities from AoI\n",
				numLostEntities, entityQueueSize );
	}
}

上面的代码数量虽然比较长，但是还是比较好理解的，首先获取之前在AOI内的所有Entity的ID，并将entityQueue_进行reserve对应的大小，避免后续的频繁扩容。然后遍历解析出来的每个EntityID：

1. 如果对应的Entity在当前Cell里找不到，则使用一个dummyCache来消耗掉后续的EntityCache数据，并通知客户端销毁这个EntityID对应的Entity。
2. 如果能找到对应的Entity，则为这个Entity创建一个新的EntityCache，并使用记录的数据来初始化这个EntityCache，主要是各种属性的同步版本号信息。

由于相邻Cell里的Entity集合一般来说都是不一样的，所以在迁移之前记录的Witness里的AOI内Entity可能并不在迁移后的Cell里，即使Entity在新的Cell里，可能会由于位置的变化导致这个Entity可能已经不符合进入当前Witness的AOI标准。所以在readAOI里会先将读取到的EntityCache数据先临时标记为离开状态setGone， 同时将对应的Entity标记为isInAoIOffload等到后面执行Witness::init的时候再重新执行检查:

/**
 *	This method initialises this object some more. It is only separate from
 *	the constructor for historical reasons.
 */
void Witness::init()
{
	// Disabling callbacks is not needed since no script should be triggered but
	// it's helpful for debugging.
	Entity::callbacksPermitted( false );

	// Create AoI triggers around ourself.
	{
		SCOPED_PROFILE( SHUFFLE_AOI_TRIGGERS_PROFILE );
		pAoITrigger_ = new AoITrigger( *this, pAoIRoot_, aoiRadius_ );
		if (this->isAoIRooted())
		{
			MobileRangeListNode * pRoot =
				static_cast< MobileRangeListNode * >( pAoIRoot_ );
			pRoot->addTrigger( pAoITrigger_ );
		}
		else
		{
			entity().addTrigger( pAoITrigger_ );
		}
	}

	Entity::callbacksPermitted( true );

	// 先省略一些代码
}

开头的AoITrigger负责重新创建一个基于半径aoiRadius的AOI触发器，然后使用callbacksPermitted来重新触发AOI更新。如果计算出来一个Entity应该进入当前Witness的AOI，那么之前介绍的addToAoI函数就会被调用：

/**
 *	This method adds the input entity to this entity's Area of Interest.
 */
void Witness::addToAoI( Entity * pEntity, bool setManuallyAdded )
{
	// 省略很多代码
	// see if the entity is already in our AoI
	EntityCache * pCache = aoiMap_.find( *pEntity );

	bool wasInAoIOffload = pEntity->isInAoIOffload();

	if (wasInAoIOffload)
	{
		pEntity->isInAoIOffload( false );
		// TODO: Set cache pointer as result of isInAoIOffload,
		// so we don't need to look it up when onloading.
		MF_ASSERT( pCache != NULL );

		// we want to do the same processing as for if it was gone
		MF_ASSERT( pCache->isGone() );
	}

	if (pCache != NULL)
	{
		if (pCache->isGone())
		{
			pCache->reuse();
		}
		// 省略很多代码
	}
	// 省略很多代码
}

这里的addToAoI对于已经标记为isInAoIOffload的Entity会有特殊的处理，走到这里说明这个Entity仍然在AOI里，因此之前标记的Entity::isInAoioffload状态会被清除，并通过pCache->reuse来清除之前的EntityCache::isGone状态。这里pCache->reuse其实还有一个意外情况，如果恢复之后还在AOI内的EntityCache记录的最新状态与对应Entity的EventHistory的最早状态之间有断档，此时代表属性同步记录无法完美衔接，因此需要触发这个EntityCache的重新全量同步。这里先使用setRefresh做一下重新同步标记，然后在Witness::update里通过handleStateChange来通知客户端删除之前的Entity记录，等待重新全量同步:

/**
 *	This method is called if an entity is reintroduced to an AoI before it has
 *	had a chance to be removed.
 */
void EntityCache::reuse()
{
	MF_ASSERT( this->isGone() );
	this->clearGone();

	if (this->lastEventNumber() < pEntity_->eventHistory().lastTrimmedEventNumber()
		&& this->isUpdatable())
	{
		// In this case, we have missed events. Refresh the entity
		// properties by throwing it out of the AoI and make it re-enter
		// immediately after.
		INFO_MSG( "EntityCache::reuse: Client has last received event %d, "
				"entity is at event %d but only has history since event %d. "
				"Not reusing cache.\n",
			this->lastEventNumber(),
			pEntity_->lastEventNumber(),
			pEntity_->eventHistory().lastTrimmedEventNumber() );

		this->setRefresh();
	}
}

void Witness::handleStateChange( EntityCache ** ppCache,
				KnownEntityQueue::iterator & queueEnd )
{
	MF_ASSERT( ppCache != NULL );

	Mercury::Bundle & bundle = this->bundle();
	EntityCache * pCache = *ppCache;

	MF_ASSERT( !pCache->isRequestPending() );
	if (pCache->isGone())
	{
	}// 省略很多其他分支
	else if (pCache->isRefresh())
	{
		pCache->clearRefresh();
		// We are effectively resetting this entity cache's
		// history, tell the client that it's gone and (re-)entered.
		this->deleteFromClient( bundle, pCache );

		pCache->setEnterPending();
		this->handleEnterPending( bundle, queueEnd );
	}
}

剩下的aoiMap里的EntityCache对应的Entity如果还有isInAoIOffload状态，则代表这些Entity已经不再满足停留带当前AOI内的需求，因此可以通知其执行onLeftAoI操作:

void Witness::init()
{
	// 省略之前的代码
	KnownEntityQueue::size_type i = 0;

	// Sort out entities that didn't make it back into our AoI.
	while (i < entityQueue_.size())
	{
		KnownEntityQueue::iterator iter = entityQueue_.begin() + i;
		EntityCache * pCache = *iter;
		Entity * pEntity = const_cast< Entity * >( pCache->pEntity().get() );

		if (pEntity->isInAoIOffload())
		{
			pEntity->isInAoIOffload( false );

			this->entity().callback( "onLeftAoI",
					PyTuple_Pack( 1, pEntity ),
					"onLeftAoI", true );

			// 'gone' should still be set on it
			MF_ASSERT( pCache->isGone() );
			if (!pCache->isRequestPending())
			{
				++i;
			}
			else
			{
				*iter = entityQueue_.back();
				entityQueue_.pop_back();
			}
		}
		// 省略一些代码
	}
	// And finally make the entity queue into a heap.
	std::make_heap( entityQueue_.begin(), entityQueue_.end(), PriorityCompare() );
}

至此，迁移之后就可以完整的恢复出来迁移之前打包的aoiMap数据，并剔除了Entity不存在或者Entity已经不在AOI范围内的EntityCache。

搞定了Witness的迁移处理之后我们再来看看Entity上存储的eventHistory_的迁移处理。在之前的属性修改回调中我们已经看到了其他客户端可见属性在被修改之后，生成的EventHistory会被RealEntity广播到所有的GhostEntity上，所以剩下来我们只需要关注两点：GhostEntity创建时的EventHistory设置，以及Real/Ghost切换时的EventHistory同步。

当GhostEntity被创建的时候，在mosaic_game里的做法是把当前RealEntity上的EventHistory队列全都打包过去。但是Bigworld里并没有这么做，因为这个EventHistory的trim间隔太长了导致这个数组的数据会比较大，全量发送过去非常消耗CPU和流量。Bigworld的做法很不一样，除了打包Ghost属性数据，还会打包当前的最新版本号lastEventNumber_和一个记录了每个属性相关的最新版本号的数据propertyEventStamps_:

/**
 *	This method is called by writeGhostDataToStream once the decision on
 *	whether or not to compress has been made.
 */
void Entity::writeGhostDataToStreamInternal( BinaryOStream & stream ) const
{
	stream << numTimesRealOffloaded_ << localPosition_ << isOnGround_ <<
		lastEventNumber_ << volatileInfo_;

	stream << CellApp::instance().interface().address();
	stream << baseAddr_;
	stream << localDirection_;

	propertyEventStamps_.addToStream( stream );

	TOKEN_ADD( stream, "GProperties" );

	// Do ghosted properties dependent on entity type
	//this->pType()->addDataToStream( this, stream, DATA_GHOSTED );

	// write our ghost properties to the stream
	for (uint32 i = 0; i < pEntityType_->propCountGhost(); ++i)
	{
		MF_ASSERT( properties_[i] );

		DataDescription * pDataDesc = pEntityType_->propIndex( i );

		// TODO - implement component properties processing here
		MF_ASSERT( !pDataDesc->isComponentised() );

		ScriptDataSource source( properties_[i] );
		if (!pDataDesc->addToStream( source, stream, false ))
		{
			CRITICAL_MSG( "Entity::writeGhostDataToStream(%u): "
					"Could not write ghost property %s.%s to stream\n",
				id_, this->pType()->name(), pDataDesc->name().c_str() );
		}
	}
	TOKEN_ADD( stream, "GController" );

	this->writeGhostControllersToStream( stream );

	TOKEN_ADD( stream, "GTail" );
	stream << periodsWithoutWitness_ << aoiUpdateSchemeID_;
}

这里的propertyEventStamps的类型并不是简单的map，用了一个专用类型PropertyEventStamps:

/**
 *	This class is used to store the event number when a property last
 *	changed for each property in an entity that is 'otherClient'.
 */
class PropertyEventStamps
{
public:
	void init( const EntityDescription & entityDescription );
	void init( const EntityDescription & entityDescription,
		   EventNumber lastEventNumber );

	void set( const DataDescription & dataDescription,
			EventNumber eventNumber );

	EventNumber get( const DataDescription & dataDescription ) const;

	void addToStream( BinaryOStream & stream ) const;
	void removeFromStream( BinaryIStream & stream );

private:
	typedef BW::vector< EventNumber > Stamps;
	Stamps eventStamps_;
};

这个类型内部使用一个数组来存储每个属性字段的最新版本号，而属性到数组里的索引是唯一的，在EntityDescrition里已经构造好了:

/**
 *	This method is used to initialise PropertyEventStamps. This basically means
 *	that the number of stamps that this object can store is set to the number of
 *	properties in the associated entity that are stamped.
 */
INLINE void PropertyEventStamps::init(
		const EntityDescription & entityDescription )
{
	// Resize the stamps to the required size and set all values to 1.
	eventStamps_.resize( entityDescription.numEventStampedProperties(), 1 );
}

/**
 *	This method is used to set an event number corresponding to a data
 *	description.
 */
INLINE void PropertyEventStamps::set(
		const DataDescription & dataDescription, EventNumber eventNumber )
{
	// Each DataDescription has an index for which element it stores its stamp
	// in.
	const int index = dataDescription.eventStampIndex();
	IF_NOT_MF_ASSERT_DEV( 0 <= index && index < (int)eventStamps_.size() )
	{
		MF_EXIT( "invalid event stamp index" );
	}


	eventStamps_[ index ] = eventNumber;
}

当每次一个其他客户端可见属性被修改的时候，Entity::onOwnedPropertyChanged除了会生成一个EventHistory之外，还会更新这里的propertyEventStamps_，将这个被修改的属性的最新版本号更新一下:

bool Entity::onOwnedPropertyChanged( const DataDescription * pDescription,
	PropertyChange & change )
{
	// 省略很多代码
	if (pDescription->isGhostedData())
	{
		// If the data is for other clients, add an event to our history.
		if (pDescription->isOtherClientData())
		{
			// 省略很多代码
			// Add history event for clients
			HistoryEvent * pEvent =
				pReal_->addHistoryEvent( msgID, stream,
					*pDescription, streamSize, pDescription->detailLevel() );

			propertyEventStamps_.set( *pDescription, pEvent->number() );
		}
		// 省略很多代码
	}
	// 省略很多代码
}

当GhostEntity被创建的时候，就会从这些数据里读取出lastEventNumber和propertyEventStamps_:

/**
 *	This method is called by readGhostDataFromStream once the decision on
 *	whether or not to uncompress has been made.
 */
void Entity::readGhostDataFromStreamInternal( BinaryIStream & data )
{
	// This was streamed on by Entity::writeGhostDataToStream.
	data >> numTimesRealOffloaded_ >> localPosition_ >> isOnGround_ >>
		lastEventNumber_ >> volatileInfo_;

	eventHistory_.lastTrimmedEventNumber( lastEventNumber_ );

	globalPosition_ = localPosition_;

	// Initialise the structure that stores the time-stamps for when
	// clientServer properties were last changed.
	propertyEventStamps_.init( pEntityType_->description() );

	Mercury::Address realAddr;
	data >> realAddr;
	pRealChannel_ = CellAppChannels::instance().get( realAddr );

	data >> baseAddr_;
	data >> localDirection_;
	globalDirection_ = localDirection_;

	propertyEventStamps_.removeFromStream( data );
	// 省略后续代码 主要是属性解析部分
}

读取到lastEventNumber_之后，这里的eventHistory_会在本地记录上次trim的版本号为lastEventNumber_，代表本地的属性历史能提供的最小版本号就是lastEventNumber_。这个数据主要是在EntityCache的DetailLevel变化的时候补充发送新DetailLevel的所有属性的最新版本号来使用的，具体代码可以回顾一下前面介绍的EntityCache::addChangedProperties。

从上面的流程中可以看出，每次Ghost被创建的时候并不会带上eventHistory里的所有历史数据，而是只带上整体属性的最新版本号和所有DetailLevel的最新版本号。这样的设计对于已经在新Cell的Witness来说没什么影响，如果进入这个Witness的AOI那就以最新的属性版本来同步即可，但是对于后面从其他Cell迁移过来的Witness来说就不怎么友好了。举个例子Cell(A)上有Witness(M)，其aoiMap拥有GhostEntity(S)对应的EntityCache，其版本号为10。如果Witness(M)迁移到Cell(B)上，在这期间在Cell(C)上的RealEntity(S)往Cell(B)创建了一个一个新的GhostEntity(S)，并且这个新的GhostEntity(S)的属性版本号为13。那么在Witness(M)的恢复过程中会发现Entity(S)的EventHistory会缺失属性记录11,12，导致无法继续之前的同步。此时只能通过setRefresh机制来通知客户端删除老的Entity(S)并以最新属性记录来创建新的Entity(S)。

至于后续的Real/Ghost切换，eventHistory_的处理就非常简单了，其实就是不处理：

1. RealEntity迁移出去的时候，老的Cell里的Entity::eventHistory_数组保持不变，打包迁移数据的时候并不会带上eventHistory_
2. RealEntity迁移到某个Cell来关联对应的Entity的时候，新的Cell里的Entity::eventHistory_数组保持不变

在这样的处理下，老Cell里的Entity迁移前的eventHistory_与新Cell的eventHistory_是一模一样的，保证了RealEntity与所有的GhostEntity上的eventHistory_同步，这样就可以继续后面属性修改引发的增量同步。