Re: [程式] 遊戲程式：批次邏輯的時域切割 (更正翻譯)

[cjcat2266 (CJ Cat)]

※ 引述《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過短的可能性
用這個方式可以預防錯誤的結果

--

Web       http://AllenChou.net
Twitter   http://twitter.com/TheAllenChou
LinkedIn  http://linkedin.com/in/MingLunChou

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 104.174.112.138
※ 文章網址: https://www.ptt.cc/bbs/GameDesign/M.1504571987.A.232.html
※ 編輯: cjcat2266 (104.174.112.138), 09/05/2017 08:41:28
推 dreamnook: 推
推 Frostx: 推