基于混沌粒子群算法的賽車避障問題研究

徐 棚 張乾元 王好問

（重慶郵電大學(xué)通信與信息工程學(xué)院 重慶 400065）

引言

賽車游戲已經(jīng)產(chǎn)生多時(shí)，因?yàn)橘愜囉螒蚋咚俚馁愜嚥僮黧w驗(yàn)、豐富的獎(jiǎng)勵(lì)機(jī)制、高速刺激感、挑戰(zhàn)性，在游戲玩家中有著廣泛的吸引力。大多數(shù)賽車游戲中，主要通過速度加減以及道具拾取等起到增加游戲樂趣的效果。

游戲玩家對于賽車游戲有豐富的見解，對于如何躲避障礙物、盡可能提高速度就是賽車游戲的關(guān)鍵之處。本文對于賽車避障問題進(jìn)行分析給出其解決方案。

一、工程需求

賽車游戲中地面上有障礙球和能量球。兩種球都靜止不動(dòng)，被撞后會消失。撞上障礙球賽車的速度會降低20%，撞上能量球賽車的速度會提高10%。電腦屏幕的分辨率為1000×800。

要求：用戶看見能量球或障礙球的反應(yīng)為0.2秒，最快按鍵每秒8次。當(dāng)障礙球已經(jīng)完全出現(xiàn)在屏幕正前方，賽車以速度v向上運(yùn)行，v最小多少時(shí)，用戶不可能躲開該球。

二、方案設(shè)計(jì)與實(shí)現(xiàn)

根據(jù)直觀分析，臨界值可能存在的點(diǎn)有6個(gè)，滿足此6個(gè)邊界條件即可保證賽車一定不會碰到該球。由于躲避時(shí)賽車和球處于同一豎直線上，根據(jù)對稱性，為統(tǒng)一計(jì)算，設(shè)看到該球后均選擇向右閃躲。故此6個(gè)臨界點(diǎn)與該球的位置排布方式如下：

按從下往上的順序命名以上6個(gè)點(diǎn)，故可知對應(yīng)每個(gè)點(diǎn)的豎直向距離y(i)可表示為：

其中H=800p表示屏幕的縱向長度大小，h*=10p表示賽車的邊長。已知h0=20p， h1=19p， h2=18p，h3=17p，h4=15p，h5=13p

設(shè)第j次與第j+1次按減速鍵之間的時(shí)間間隔為 ，豎向位移的表達(dá)式滿足下式：

同理豎直方向的速度條件，水平向的距離也與6種情況相關(guān)。具體表示為：

設(shè)第k次與第k+1次按減速鍵之間的時(shí)間間隔為Δtk，豎向位移的表達(dá)式滿足以下公式：

設(shè)在最優(yōu)按鍵操作的條件下能夠恰好躲避障礙球/能量球的速度為v，故最終目標(biāo)即可表示為：

求解模型需要確定最優(yōu)按鍵次數(shù)以及任意時(shí)間結(jié)點(diǎn)處的具體按鍵操作，按鍵次數(shù)較多，屬于高維問題，為此我們采用混沌粒子群算法求解[1]。

2s內(nèi)有長度16的按鍵序列，按鍵序列每兩個(gè)元素間隔0.125s，對序列元素有以下設(shè)置：

對每組序列計(jì)算出每個(gè)序列，使剛好能躲避速度的最大值作為每個(gè)粒子的適應(yīng)度。

速度v最小為1018.96p/s時(shí)，用戶不可能躲開該球。

三、結(jié)束語

本文針對賽車游戲中避障問題，進(jìn)行建模分析并使用混沌粒子群算法給出了避開/撞上障礙物的臨界條件。