《電子技術應用》
您所在的位置:首頁 > 測試測量 > 設計應用 > 一種優化碰撞檢測算法在游戲AI設計中的應用
一種優化碰撞檢測算法在游戲AI設計中的應用
來源:微型機與應用2012年第13期
鄔厚民
(廣州科技貿易職業學院,廣東 廣州 511442)
摘要: 碰撞檢測是游戲人工智能設計領域中的基本研究問題,快速智能的碰撞檢測算法直接決定游戲效果的好壞。針對捕魚類游戲的碰撞要求,設計了一種以空間網格劃分為基礎結合多重因素分析的高效智能碰撞算法,增加了相關游戲的可玩性及運行效率。
Abstract:
Key words :

摘  要: 碰撞檢測是游戲人工智能設計領域中的基本研究問題,快速智能的碰撞檢測算法直接決定游戲效果的好壞。針對捕魚類游戲的碰撞要求,設計了一種以空間網格劃分為基礎結合多重因素分析的高效智能碰撞算法,增加了相關游戲的可玩性及運行效率。
關鍵詞: 游戲算法;人工智能;碰撞檢測;網格

 人工智能技術在游戲設計中的應用越來越廣泛,已經成為游戲設計成功與否的關鍵因素。碰撞問題則是游戲AI設計領域中的基本研究問題。碰撞問題的解決過程大致可以分為碰撞模型建立、碰撞檢測、碰撞確認與響應三個階段。碰撞模型建立就是建立參與碰撞的對象以及建立便于碰撞檢測的數據模型,碰撞檢測過程是根據一定的碰撞規則和因素對參與碰撞的對象在既定的數據模型下進行檢測的過程,對碰撞檢測的反饋數據進行分析篩查得出確認結果并執行相應的操作就是碰撞響應。雖然國內外有關學者就碰撞問題也作了大量的研究,但是針對游戲設計的算法不多,若在游戲AI設計中實現,需要進行修改優化。另一方面,不同類型、玩法、主題的游戲對于對象的碰撞要求存在著很大的差異。例如,射擊類游戲比較關注子彈與目標物體的碰撞,又如動作類游戲則比較關心對象運動間的碰撞。由此可見,要根據具體游戲碰撞需求設計適合的碰撞算法來給予解決。本文根據當下熱門的捕魚游戲中的碰撞要求,設計了一種以空間網格劃分為基礎,結合多重因素分析的高效智能碰撞算法,增加了相關游戲的可玩性及運行效率。
1 碰撞檢測模型的建立  
 近年來以捕魚為題材的休閑類游戲發展相當迅速。例如,《捕魚達人》成為2011年iPhone付費應用收入最高的國產游戲之一[1]。該類游戲大體是由玩家購買子彈,調整網槍的威力,就可以攻擊游戲中游動的魚類以獲取積分。被攻擊的魚類品種不同,其積分也不同。玩家用來攻擊魚類的網槍共分為若干個等級,等級越高的網槍耗費的子彈越多,但其漁網捕魚能力也越大。對于該類游戲碰撞問題的關鍵是如何檢測漁網與魚類動態碰撞的情況。不少開發者改良使用GJK算法[2]和LC算法[3]等有關碰撞位置計算的著名算法。以上算法都是通過計算物體間表面的最小距離來確定碰撞位置,實施過程中需要遍歷檢測所有魚類對象與漁網的實時距離來判斷碰撞。這樣的算法雖然實現簡單,但是對于變速轉向對象的碰撞檢測精度不高,而且隨著對象數量的上升而增加運算量影響運行速率。
 本文提出的一種基于空間網格劃分的碰撞檢測優化算法既能增加碰撞檢測精度又能減少CPU的運算量。具體是根據某種規則將游戲場景劃分成一個個小的網格,為每個網格對應一個列表用來記錄所有屬于該單元網格的對象。由于不相鄰單元網格的對象之間距離較遠,因此只需檢測同一個單元網格或相鄰單元網格內的對象間的相交情況即可。在捕魚類游戲中,主要檢測的是漁網與魚類的碰撞,所以漁網也要進行網格化,可以利用場景網格來記錄即可,這樣只要直接檢查漁網打開時所屬網格矩陣范圍內有可能碰撞的魚類對象,而無需遍歷所有的魚類對象了,因此大大減少了檢測的數量。
 為了不影響碰撞檢測的精確度,場景分割網格應以正方形單元格為單位,大小與最小魚類的正方形包圍盒一致。魚類要設置捕捉特征點,等級越高的魚類越大,特征點就越多(最多有6個)。特征點也可以是動態變化的,例如魔鬼魚當翅膀全部打開的時候所有特征點才可以被捕捉到,如圖1所示。然后根據魚類對象特征點所在的位置將各個魚類對象分配到該網格的對應單元格內。

 場景網格分割更好地記錄了魚類對象在屏幕的位置和漁網捕魚矩陣,從而利于隨后的碰撞檢測。魚類對象的位置可以通過其特征點定位實現,給每一個單元格建立一個寄存器來存儲該單元格中不同魚類對象的特征點。實際應用時可以利用一個二維數組來實現單元格特征點存儲器的功能,二維數組行數是網格單元格總數,列數是游戲魚類對象的實例數上限。當一種魚類對象實例化時都需要產生一個對應流水標識號,利用單元格索引號和魚類對象流水標識號構成二維數組內特征點存儲單元的索引值。這樣的算法能迅速實現數據查找和更新。與此同時,魚類對象也需要設置一個存儲特征點所在單元格索引值的存儲器,存儲器的大小根據對應魚類特征點數量來確定。該存儲器可以使用一個一維數組來實現,特征點標識號可以作為數組的索引下標。
 魚類對象在游動過程中,特征點位置必然發生變化,因此需要實時判斷特征點所在的單元格,更新單元格特征點寄存器對應的數據項目,并且把單元格索引值重新計入魚類對象的特征點存儲器。這樣就可以實時地為碰撞檢測提供準確的數據基礎。
2 碰撞檢測的過程
 碰撞檢測首先需要建立監聽器,監聽對象的狀態變化以便觸發碰撞檢測過程。例如,魚類對象碰撞檢測可以利用游戲場景網格,監聽單元格特征點寄存器,若寄存器存有不同魚類對象的特征點,就可以觸發魚類對象碰撞檢測過程進行處理。
 當玩家使用某種等級網槍撒網捕魚時,根據撒網點所在的單元格,推算出漁網陣列,即可獲得一個單元格索引值集合Ai。碰撞檢測過程是逐一抽取集合中的單元格,檢測其中存在有特征點的魚類對象,然后逐一把這些魚類對象的特征點位置寄存器數據集合Bi直接與漁網單元格索引值集合Ai進行比較,若是Bi∈Ai,則可以判斷該魚類對象所有特征點都包含在漁網中。

 傳統碰撞檢測過程最重要的是準確地檢測碰撞,但從游戲的可玩性來說,僅以對象物理狀態來判斷碰撞是不夠的,需要分析其他游戲性因素進行判斷。由此可以設定碰撞檢測函數Pi=f(x1+x2+x3+x4+x5+xn), Pi代表某魚類對象與漁網碰撞值,x1~xn代表各項因素,每項因素都有不同的權重,從而影響最終的碰撞值。各項因素設定及權重分配(以5項因素為例)如表1所示。

 根據不同因素所起的作用,可以動態調節它們之間的權重值,游戲在相同的框架下也能體現出不同的游戲性。例如,動態修改x1與x2之間的權重,則捕魚技巧和游戲難度之間的體驗感就會發生變化。再者,可以在一些因素中加入動態參數,使因素權值發生游戲性的變化。例如,對用戶在線時間參數x4引入相關計算公式y=[1+sin(x×π/t)]×x/30,y是因數權值,x是時間值,t是游戲送分減分周期,如圖4所示,曲線的斜率和周期都可以作適當調節,使權重值隨在線時間波動上升。

 

 

3 碰撞的確認與響應
 此外,必須是在漁網矩陣單元格中存在特征點的魚類對象才會觸發碰撞檢測函數,函數是根據各項因素權重值返回碰撞值,以此決定是否發生實質性碰撞。例如,上文提到的鯉魚和墨魚,因為B1∈A1、B2∈A1,所以它們的x1權重值都可以得到40,而魔鬼魚因為B3∩A1=20,只有一個特征點與漁網碰撞,它的x1權重值只為8(魔鬼魚共有5個特征點)。從難度系數上來說,魔鬼魚最高、鯉魚最低,通過隨機換算可得魔鬼魚x2=10,墨魚x2=12,鯉魚x2=20。若其他因素假定都一樣合共為20,則可以推算出鯉魚碰撞值P1=40+20+20=80,墨魚P2=72,魔鬼魚P3=38。碰撞確認與響應的過程如圖5所示,碰撞檢測Y值低于60分,則判斷漁網捕魚不成功,需要累計該魚類對象被攻擊的次數,以增加下次被捕的得分值。最重要的是要觸發魚類轉向逃跑的函數。若碰撞檢測Y值高于或等于60,則判斷該魚類對象被捕獲,魚類對象觸發捕獲函數啟動捕獲動畫,并實時增加玩家的積分值。但一個游戲往往會暗含一些非常規因素。例如,玩家突然獲得了超級魚槍,只要及時使用超級漁網接觸的所有魚類都被捕獲。在實現中,直接將非常規因素折算成相應的得分值與Pi累加后再進行判斷就可以了。

 游戲AI算法跟一般程序的算法要求不同的是除了要考慮時間復雜度與空間復雜度的因素外,還要考慮游戲復雜多樣的可玩性要求。本文提出了一種新的基于空間網格劃分結合多重因素分析的智能碰撞算法,利用空間網格劃分和特征點來判斷對象碰撞關系,并分析游戲性的各項因素,合理分配權重實現碰撞檢測,從而提高了算法的執行速度,增加了游戲的可玩性。對相關游戲程序設計具有一定的應用參考價值。
參考文獻
[1] 艾瑞咨詢.2011年中國網絡游戲行業四大盤點[DB/OL].(2011-12-13)[2012-02-01].http://game.iresearch.cn/15/20111213/158889.shtml.
[2] Matthew Peterson. Interactive QuickTime[M]. Elsevier Inc.2004:99-115.
[3] DOBKIN D P, KIRKPATRICK D G. A linear algorithm for determining the separation of convex polyhedra[J]. Journal of Algorithms, 1985(6):381-392.
[4] PETERS K. Flash ActionScript3.0動畫高級教程[M].蘇金國,譯.北京:人民郵電出版社,2010.
[5] STAHLER W.游戲編程數學和物流基礎[M].北京:機械工業出版社,2008.

此內容為AET網站原創,未經授權禁止轉載。
热re99久久精品国产66热_欧美小视频在线观看_日韩成人激情影院_庆余年2免费日韩剧观看大牛_91久久久久久国产精品_国产原创欧美精品_美女999久久久精品视频_欧美大成色www永久网站婷_国产色婷婷国产综合在线理论片a_国产精品电影在线观看_日韩精品视频在线观看网址_97在线观看免费_性欧美亚洲xxxx乳在线观看_久久精品美女视频网站_777国产偷窥盗摄精品视频_在线日韩第一页
  • <strike id="ygamy"></strike>
  • 
    
      • <del id="ygamy"></del>
        <tfoot id="ygamy"></tfoot>
          <strike id="ygamy"></strike>
          国产精自产拍久久久久久蜜| 亚洲一区二区三区三| 欧美国产日韩二区| 国产精品久久77777| 欧美紧缚bdsm在线视频| 亚洲一区二区在线免费观看视频| 欧美激情va永久在线播放| 欧美亚日韩国产aⅴ精品中极品| 欧美高清视频www夜色资源网| 欧美精品久久久久久久免费观看| 国产深夜精品福利| 奶水喷射视频一区| 香港久久久电影| 国产精品丝袜久久久久久app| 欧美一区二区三区在线观看视频| 欧美精品www| 在线日韩成人| 一本色道久久综合亚洲精品高清| 欧美电影免费观看高清完整版| 欧美在线观看一区二区| 国产免费观看久久黄| 欧美视频中文在线看| 欧美在线一级va免费观看| 亚洲人线精品午夜| 欧美伦理视频网站| 亚洲乱码精品一二三四区日韩在线| 欧美资源在线| 欧美视频四区| 亚洲愉拍自拍另类高清精品| 亚洲日本va午夜在线影院| 亚洲人成在线播放网站岛国| 久久夜色精品国产欧美乱| 久久一区二区三区国产精品| 性欧美8khd高清极品| 亚洲高清av| 欧美高清视频一二三区| 久久国产一区二区三区| 欧美男人的天堂| 亚洲欧洲一区二区三区久久| 在线成人激情| 国产日韩欧美综合| 性视频1819p久久| 国产香蕉久久精品综合网| 伊人狠狠色丁香综合尤物| 欧美午夜a级限制福利片| 免费人成网站在线观看欧美高清| 亚洲一区欧美| 在线观看亚洲精品视频| 永久久久久久| 欧美激情va永久在线播放| 在线观看欧美日本| 狠狠色丁香久久综合频道| 另类天堂视频在线观看| 国产一区二区三区久久| 久久亚洲精品视频| 国产精品99久久久久久人| 国产一区二区黄| 亚洲欧美日韩综合国产aⅴ| 国产精品免费观看视频| 国产午夜精品视频| 亚洲欧洲精品一区二区三区不卡| 最新日韩精品| 欧美激情按摩在线| 亚洲一区二区三区高清| 国产精品揄拍500视频| 99riav久久精品riav| 日韩视频一区二区三区在线播放| 欧美在线亚洲综合一区| aa国产精品| 性欧美大战久久久久久久久| 极品尤物一区二区三区| 亚洲美女黄色| 国产欧美日韩视频一区二区三区| 亚洲国产成人在线播放| 国产色产综合色产在线视频| 久久综合导航| 久久精品视频亚洲| 一本色道久久88综合日韩精品| 亚洲一区免费视频| 久久久久久久久久久久久女国产乱| 欧美一区1区三区3区公司| 狠狠网亚洲精品| 国产精品久久久久久久午夜| 亚洲欧美在线另类| 雨宫琴音一区二区在线| 亚洲欧洲美洲综合色网| 亚洲观看高清完整版在线观看| 中文精品视频一区二区在线观看| 毛片av中文字幕一区二区| 欧美一级大片在线免费观看| 亚洲欧美日韩精品久久亚洲区| 亚洲在线视频观看| 精久久久久久久久久久| 久久久久成人精品免费播放动漫| 黑丝一区二区| 亚洲精品一区二区三区樱花| 欧美日韩dvd在线观看| 久久大香伊蕉在人线观看热2| 欧美成人性生活| 亚洲欧美日韩精品久久亚洲区| 久久久久99| 亚洲激情午夜| 99这里只有精品| 亚洲一区二区三区四区五区午夜| 久久在线免费观看视频| 国产午夜精品久久久久久久| 国产日本精品| 欧美绝品在线观看成人午夜影视| 日韩视频三区| 欧美激情性爽国产精品17p| 篠田优中文在线播放第一区| 亚洲免费视频观看| 久久亚洲精选| 悠悠资源网亚洲青| 国产在线观看精品一区二区三区| 久久久久久久尹人综合网亚洲| 免费成人你懂的| 欧美精品一区三区在线观看| 欧美+日本+国产+在线a∨观看| 裸体一区二区| 亚洲国产精品女人久久久| 欧美精品在线看| 牛人盗摄一区二区三区视频| 久久久综合免费视频| 狠狠色丁香久久婷婷综合丁香| 日韩一区二区福利| 欧美一区午夜视频在线观看| 久久偷看各类wc女厕嘘嘘偷窃| 亚洲成人在线免费| 久久国产精品99国产| 欧美伊人久久大香线蕉综合69| 蜜桃久久精品乱码一区二区| 欧美91视频| 亚洲婷婷免费| 一区二区三区欧美在线| 亚洲一区二区三区中文字幕在线| 亚洲第一网站免费视频| 性视频1819p久久| 在线观看国产日韩| 欧美日韩亚洲综合一区| 你懂的国产精品永久在线| 噜噜爱69成人精品| 亚洲精品一区在线观看香蕉| 久久av资源网| 欧美成人精品影院| 男人天堂欧美日韩| 国产一区二区三区网站| 欧美成人精品一区| 亚洲高清视频的网址| 欧美精品久久久久久久久久| 国产女同一区二区| 一区二区三区久久网| 欧美在线网址| 欧美一区二区三区男人的天堂| 欧美一区二区三区啪啪| 欧美在线不卡| 亚洲美女福利视频网站| 激情偷拍久久| 亚洲另类视频| 国产精品午夜av在线| 老司机凹凸av亚洲导航| 欧美日韩综合在线免费观看| 国产精品美女主播在线观看纯欲| 亚洲欧美一区二区在线观看| 一区二区不卡在线视频 午夜欧美不卡'| 黄色亚洲精品| 亚洲精品视频在线播放| 欧美伦理视频网站| 红桃视频欧美| 国产精品中文字幕欧美| 在线观看日韩一区| 亚洲美女福利视频网站| 亚洲人成网在线播放| av成人老司机| 欧美精品日韩三级| 韩国av一区二区三区| 国产精品99久久久久久宅男| 亚洲美女在线观看| 久久国产视频网站| 亚洲福利免费| 免费视频久久| 国产精品成人一区二区网站软件| 国产精品私房写真福利视频| 久久国产加勒比精品无码| 国内免费精品永久在线视频| 亚洲夜晚福利在线观看| 免费成人网www| 国产日韩精品一区二区| 老牛国产精品一区的观看方式| 欧美a级大片| 久久蜜桃香蕉精品一区二区三区| 亚洲六月丁香色婷婷综合久久| 在线看片第一页欧美| 老司机67194精品线观看| 一区二区免费在线播放| 亚洲一区二区三区乱码aⅴ蜜桃女| 欧美日韩免费精品| 久久国产精品99精品国产| 国产精品手机在线| 亚洲一区二区三区高清| 在线观看欧美日本| 亚洲视频狠狠| 欧美日韩亚洲精品内裤| 国产精品久久久久久久久久久久久久| 国产精品久久国产愉拍| 亚洲国产精品t66y| 一本色道久久88亚洲综合88| 亚洲精品欧美日韩专区| 女女同性精品视频| 亚洲欧美经典视频| 欧美一级在线视频| 久久久久国色av免费观看性色| 亚洲小视频在线观看| 一区二区三区鲁丝不卡| 亚洲在线一区二区三区| 国产人成一区二区三区影院| 欧美视频在线免费看| 韩日精品中文字幕| 久久一区激情| 欧美一区二区三区男人的天堂| 亚洲免费一级电影| 久久久午夜视频| 怡红院av一区二区三区| 牛人盗摄一区二区三区视频| 欧美亚洲第一页| 国产伦理精品不卡| 亚洲狼人综合| 久久精品国产欧美亚洲人人爽| 亚洲国产精品视频| 精品99一区二区三区| 国产精品久久久久久亚洲调教| 乱人伦精品视频在线观看| 久久久久九九九九| 欧美激情片在线观看| 99热这里只有精品8| 欧美激情久久久久| 一区二区三区**美女毛片| 亚洲一级黄色| 久久精品国产视频| 欧美电影免费观看大全| 欧美日韩少妇| 国产欧美一区二区三区在线看蜜臀| 久久精品一区二区三区中文字幕| 影音先锋久久资源网| 欧美日韩国产探花| 欧美第十八页| 国产精品视频精品视频| 亚洲国产日韩一区二区| 亚洲精品国产视频| 国产精品一二三视频| 久久亚洲精品一区二区| 久久久久久亚洲精品不卡4k岛国| 99视频精品免费观看| 欧美极品一区| 久久精品国产一区二区三区免费看| 亚洲一区二区三区欧美| 在线亚洲伦理| 亚洲高清色综合| 欧美成人精品高清在线播放| 久久久无码精品亚洲日韩按摩| 亚洲高清在线观看一区| 亚洲精品在线免费观看视频| 日韩午夜电影| 国产精品99久久久久久有的能看| 国产亚洲激情视频在线| 亚洲国产欧美在线人成| 欧美影院视频| 一区二区黄色| 欧美一级片一区| 中文精品一区二区三区| 亚洲伦理在线免费看| 亚洲久久一区二区| 欧美美女喷水视频| 国产精品乱子久久久久| 在线亚洲电影| 久久女同互慰一区二区三区| 欧美一区二区高清在线观看| 亚洲影音一区| 亚洲综合大片69999| 亚洲欧美在线x视频| 国产伦精品一区二区三区视频孕妇| 欧美一区二区黄| 国产精品va在线播放我和闺蜜| 亚洲网友自拍| 国产日韩欧美夫妻视频在线观看| 国产在线视频欧美| 国产亚洲精品一区二555| 欧美精品一区二区三区高清aⅴ| 日韩写真在线| 欧美一级精品大片| 久久久久88色偷偷免费| 在线亚洲美日韩| 亚洲国产精品久久久久秋霞影院| 国产精品色午夜在线观看| 欧美.日韩.国产.一区.二区| 亚洲人成在线观看| 欧美日韩国产首页在线观看| 久久久久欧美| 国产精品成人一区二区三区吃奶| 亚洲一区美女视频在线观看免费| 亚洲高清成人| 国产精品成人aaaaa网站| 欧美日韩亚洲免费| 宅男噜噜噜66国产日韩在线观看| 一区二区高清视频| 亚洲欧美成人一区二区在线电影| 久久精品91| 国产欧美日韩亚州综合| 欧美日韩在线综合| 国产精品igao视频网网址不卡日韩| 91久久夜色精品国产网站| 久久一综合视频| 亚洲精品小视频在线观看| 牛夜精品久久久久久久99黑人| 亚洲欧美另类久久久精品2019| 美女啪啪无遮挡免费久久网站| 9l视频自拍蝌蚪9l视频成人| 一区在线电影| 国产在线一区二区三区四区| 国产精品一区二区视频| 亚洲欧美在线x视频| 最新69国产成人精品视频免费| 国产日韩欧美制服另类| 国产精品白丝黑袜喷水久久久| 亚洲人成网站色ww在线| 亚洲一区二区三区涩| 尤物精品国产第一福利三区| 亚洲欧美国产毛片在线|