[其他] 不使用開根號求出解的方法

[entersoal (準備衝刺)]

※ [本文轉錄自 Math 看板 #1CjosVPO ]

作者: entersoal (準備衝刺) 看板: Math
標題: [其他] 不使用開根號求出解的方法
時間: Fri Oct 15 00:19:40 2010

原po過去是念數學系的，出社會工作後進入遊戲業多少運用到數學
多半負責規格使用的演算法或是推估數據模型（戰鬥、經濟..etc.)
最近遇到了一個障礙
在處理一個狀況是在賽車這個機制下產生的



在平面XY座標系之下

假設A玩家所在的點P1為(P1x,P1y)，其速度向量V1為（V1x,V1y)，車體半徑為r1
    B玩家所在的點P2為(P2x,P2y)，其速度向量V2為（V2x,V2y)，車體半徑為r2

需要預測的狀況為兩玩家發生碰撞

我所使用的方法分幾個步驟做篩檢

I.令兩玩家構成的圓剛好相切時的連心線為d，如果 r1+r2 < d 進入II

II.利用V1和V2求出路徑公式（直線公式），在將此二線公式做二元一次聯立方程式求解
   利用克拉碼公式排除 delta=0，但delta x and delta y不全為零的狀況
   進入III

III.為我主要問題
    我希望能夠驗證此解是否能落於V1和V2旋轉正負30度所掃出的面積中，如果能驗證
    此點，則能夠確實驗證兩向量交會點在不可避免得範圍內

如此滿足三項條件就產生玩家發生碰撞的剛體碰撞運算



但我在推導第三點預到了障礙，原先只需要算與X軸夾角，

就可以推導V向量所要掃的範圍不等式，但是麻煩在此運算需要用到開根號計算cosθ

而此運算必須由Server進行所以不得使用多項式函數以上的複雜度運算

想請教不知道有沒有可以不用開根號就可以計算餘弦值的方法


或是其實我想法上有錯？感謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.32.144.10
→ VFresh      :沒仔細看全文...Orz 不過考慮泰勒展前幾項..
→ VFresh      :不知道這樣可不可以Orz
→ entersoal   :對吼！！！！還有泰勒展開式，謝謝，我找到方向了
--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.32.144.10
推 littleshan:算cos可以用查表法+內插，會比泰勒展開更快
推 odahawk:建議你用Cordic
推 truesword:有沒有可能將III的運算外包給ASIC IC去做呢
→ truesword:這樣能大幅加速運算速度
→ entersoal:應該是沒辦法，還是等推導出公式給Server運送:(
推 odahawk:CORDIC演算法連8051都跑得動，可以試試看
→ entersoal:喔喔，好，我試試看，我太孤陋寡聞，剛剛google了一下
→ entersoal:原來Cordic是一個這麼了不起的演算法
推 Bencrie:數學好真令人羨慕 >"<
推 odahawk:可以查數值分析專書，或單晶片常用演算法
→ odahawk:很多演算法簡單又好用的
→ entersoal:我以前數值分析學得還不錯，不過僅限於ODE的部份...
→ entersoal:PDE就沒學到了
推 chenglap:數學是科學和工程之本, 所以有時間多練習...