考慮浮點數，如何實現跨平台數值穩定的漫遊-尋路演算法？

01-05

有時候我們需要數值穩定的演算法，典型的例子是rts同步計算，或者手游戰鬥驗證。要求在不同的平台下，對於同樣的用戶輸入，傷害、尋路、移動等總是計算出精確一致的結果。
首先問下是不是：如果我沒有猜錯的話，在目前的移動平台-伺服器平台上，浮點數實現應該是有不一致情況的吧。[1]

在這種情況下，邏輯數值計算我們可以全用整數實現，但是場景漫遊-尋路的主流演算法往往包含浮點數，經常涉及到角度計算。這個一般如何處理呢？是否都需要改為全整數的演算法？[2]
參考：

[1]Floating point operations on ARM processor 以Arm為例，Arm的浮點數就有軟模擬、硬體IEEE-754兼容、SIMD下IEEE-754不兼容三種情況
[2]Gamasutra - Opinion: Synchronous RTS Engines And A Tale of Desyncs 《半神》的解決方案是，設置CPU強制工作在 IEEE754 模式下

要維持平台移植性，還是要靠整數（定點數）。

最近也做過這方面的事情，實現了定點數純量和矢量運算。三角函數可用45度以內的查找表，比較麻煩的是開平方和指數等。

另外要注意定點數較容易溢出，例如兩個32位定點數二維矢量的點積是65位純量，我對於一些演算法會直接使用64位結果，例如圓形相交測試是比較64位的平方距離。

我之後再補一些參考資料吧。

----

更新

關於定點數運算基礎，可參考課件 [1] 。定點數開平方的常用演算法是 [2]。對數可參考[3]及一個開源實現。[4] 第18章有反正切的近似值演算法。在 SO 上也有一些討論，如：

math - Inverse sqrt for fixed point
c++ - Fast fixed point pow, log, exp and sqrt

[1] Lauha, Jetro. "The neglected art of Fixed Point arithmetic." Retrieved August 12 (2006): 2011. ftp://chiptune.untergrund.net/users/in4kadmin/files/The_neglected_art_of_Fixed_Point_arithmetic_20060913.pdf

[2] Turkowski, Ken. "Fixed point square root." Apple Computer, Inc., Tech. Rep 96 (1994). http://www.realitypixels.com/turk/computergraphics/FixedSqrt.pdf

[3] C. S. Turner, "A Fast Binary Logarithm Algorithm", IEEE Signal Processing Mag., pp. 124,140, Sep. 2010. GitHub - dmoulding/log2fix: Fixed-point base 2 logarithm algorithm implementation in C; includes added base e and base 10 support, too.

[4] Lyons, Richard G., ed. Streamlining digital signal processing: a tricks of the trade guidebook. John Wiley Sons, 2012.

這裡有個很長的討論：

Gaffer on Games

基本上在同一平台上，只有用同一個編譯器編譯出來的同一個程序，是可能的。

順便，在STandalone REproducible FLOating-Point library 提供了所有crt浮點函數的穩定版本，完全不調用協處理器sse等功能。如果你能自己實現一下浮點數+-*/就可以了。

再順便，這個庫作者已經不維護了，下載下來的版本應該在windows是不能編譯的。請去下載stringrts源代碼中的streflop。

只有定點軟實現兩條路可以選。

應當優先定點（性能高）

不用說跨平台了，x86 CPU的SIMD單精度浮點是32位的，而FPU單精度是超過32位的（我記得好像是48位）。

遊戲開發涉及到邏輯運算的時候，所有前輩都會告訴你，不要用浮點數，浮點數是邪惡的。

我在開發有回放系統的 rts 遊戲的時候，就用 c# 實現過一套簡單的定點數，基本思路就是 32 位的整數中，前 16 位用來存儲小數，後 16 位用來存儲整數。但在做乘法的時候會溢出，所以得使用 int64，而且表示的定點數範圍只有在(-65536, 65535) 之間才是安全的，超出這個範圍的數值在做乘法運算的時候可能會溢出。總的來說想要自己編寫一個效率和魯棒性都很高的定點數基本上來說是一件非常非常難的事情。我的定點數在使用的時候還要小心翼翼的提醒自己，確定這裡的數值不會很大，所以不會溢出吧。不過對於一個 RTS 遊戲來說，最大值 65535 已經夠用了，所以一直用著都沒啥問題，也用該定點數做出過回放的功能。我參考了Fixed point math in c#? 的回答，但該代碼中的 sqrt 非常慢，以至於我最後不得不自己用牛頓迭代法寫了一個，而且其中的 sin 和 cos 函數也有問題，測下來發現誤差巨大，最後也是自己用線性插值的查表方法重新寫了一個。

TeX和MetaFont之中都是使用了平台獨立的定點數運算，包括開方和指數演算法都在。簡簡單單地實現，代碼不會超過三千行。

蟹妖，

給你一個思路，我們以前就是這麼乾的，就是確定浮點數精度的位數（比如，保留4位精度，就*10000），然後把浮點數轉換為整數（int64或者int，視最大值來定），不同設備、系統上採用整數來傳遞、計算，只有在必要的的時候，才局部轉換為浮點數用，一般遊戲的浮點數同步精度要求都不高，只是避免累計誤差而已。

效果很好。

發現了這個c#定點數的庫，在這裡分享一下。

還是用定點吧