※ 引述《cjcat2266 (CJ Cat)》之銘言：
: 原文連結 http://wp.me/p4mzke-14V
: 動畫生成原始碼 https://github.com/TheAllenChou/timeslicing
: 遊戲程式系列文 http://allenchou.net/game-programming-series/
最近遇到並解決時域切割的一個陷阱
在此跟大家分享一下
用判定NPC是否能看到玩家當作例子
演算法本體就是每個NPC的眼睛到玩家的射線投射(raycast)
這個運算不便宜，且幾個frame的視覺邏輯層延遲不容易被玩家感覺到
所以非常適合時域切割
如果你的NPC視覺API設計只是單純的存"代表可否看到玩家的bool值"
那基本上不會有什麼問題
void ProcessResults()
{
for (int i = 0; i < m_batchSize; ++i)
{
const BatchResult &result = batchResults[i];
npcCanSeePlayer[result.iNpc] = result.canSeePlayer;
}
}
bool CanNpcSeePlayer(int iNpc)
{
return npcCanSeePlayer[i];
}
但是如果你的NPC視覺API提供跟時間有關的存取介面
例如"過去X秒之內NPC是否可以看見玩家"，那就要注意一下了
直覺上的實作方式是這樣
void ProcessResults()
{
for (int i = 0; i < m_batchSize; ++i)
{
const BatchResult &result = batchResults[i];
if (result.canSeePlayer)
{
lastNpcSawPlayerTime[result.iNpc] = GetTime();
}
}
}
bool CanNpcSeePlayer(int Npc, Time timeWindow)
{
return GetTime() - lastNpcSawPlayerTime[iNpc] <= timeWindow;
}
但其實有個致命的缺點
要是剛好NPC數量多到時域切割的一個循環比timeWindow還要長
那呼叫CanNpcSeePlayer有可能會得到false negative
像詢問"過去1.0秒期間NPC是否有看見玩家"
但是剛好當時NPC比較多，時域切割循環需要1.1秒
剛好在循環進度介於1.0秒和1.1之間呼叫CanNpcSeePlayer就會得到false
即使true才是正確結果
強制實施最長時域切割循環時間不失為個解決方式
但是只要timeWindow夠短，永遠會有上述的問題
所以比較有彈性的解決方式，是處理運算解果的時候同時記錄時間
在詢問結果的時候，額外檢查最後一次true結果時間是否等於處理結果的時間
如果是的話，不管timeWindow一律回傳結果為true
void ProcessResults()
{
for (int i = 0; i < m_batchSize; ++i)
{
const BatchResult &result = batchResults[i];
if (result.canSeePlayer)
{
lastNpcSawPlayerTime[result.iNpc] = GetTime();
}
// record time of results processing as well
lastResultsProcessedTime[result.iNpc] = GetTime();
}
}
bool CanNpcSeePlayer(int Npc, Time timeWindow)
{
const bool lastResultTrue =
lastResultsProcessedTime[iNpc].IsValid()
&& lastResultsProcessedTime[iNpc] == lastNpcSawPlayerTime[iNpc];
if (lastResultTrue)
return true;
return GetTime() - lastNpcSawPlayerTime[iNpc] <= timeWindow;
}
時域切割循環時間自然是越短越理想
但是總是有詢問結果的timeWindow過短的可能性
用這個方式可以預防錯誤的結果