基于神經網絡的AI賽車游戲算法

余婷，劉循

（四川大學計算機學院學院，成都　610065）

YU Ting，LIU Xun

（College of Computer Science，Sichuan University，Chengdu 610065）

基于神經網絡的AI賽車游戲算法

余婷，劉循

（四川大學計算機學院學院，成都610065）

0　引言

長久以來賽車游戲就是深受全世界玩家喜愛的游戲類型之一，愛好賽車游戲的玩家們在競速比賽中主要以速度最快、路線最短為目標，從而使得賽車跑完賽程所花時間最短。非玩家選手也是如此，在給定比賽軌道和賽車的情況下，非玩家選手需要預判一個合理的目標軌跡，然后按照這個軌跡行駛從而達到優異的成績。而合理的軌跡受軌道形狀、汽車氣動性能、咬地過彎等因素的影響［3］。

在商業游戲中，通常是領域專家給出賽車的目標軌跡［5］，由游戲開發者通過實際的游戲進行調試。這種手動調試的過程對于游戲開發來說是非常耗費時間的。而文獻［1］中的自動軌跡生成的研究又將最短路徑和取得最大速度（最小曲率）的軌跡兩者分開計算，再將兩者折中，從而確定賽車的目標軌跡，這是一種全局最優的方法。但是在實際應用中，由于各種因素的影響賽車無法按照全局最優得到的軌跡行駛，例如障礙物或者其他賽車的撞擊。如果實時計算目標軌跡，通常計算量很大，因此本文提出一個基于神經網絡的賽車算法。具體實現為：①利用軌跡規劃在原始路徑上產生目標點，同時優化目標點降低路徑曲率；②根據目標點利用遍歷算法產生賽車的正向和側向加速度數據集，然后訓練神經網絡；③利用局部優化檢查加速度的值，確保生成的加速度不會使賽車沖出軌道。

1　算法描述

我們用三個子算法構成模擬玩家行為的智能算法：軌跡規劃、神經網絡、局部優化。

軌跡規劃在賽道上產生目標點，神經網絡根據目標點產生運動物體的正向和側向加速度，最后局部優化檢查生成的加速度有沒有使物體沖出軌道的可能，它限制加速度在安全的范圍內。

1.1軌跡規劃

我們設定賽車的可視范圍為S，把從賽車位置開始的S段長度的賽道坐標記錄下來。算法首先將賽車當前坐標點和最末的軌跡坐標點連成線段L，然后，求軌線上各個坐標點到線段L的垂直距離。如果沒有一個點的垂直距離大于預先設定的限制dl，則算法結束，產生的目標點只有一個，即最末的軌線坐標點。如果軌線上存在點的垂直距離大于dl，則將距離最大的點變為新目標點，將原來的線段分為兩段。如此遞歸地進行下去，最后停止。

對距離當前坐標點最近的目標點作“切角”和“延角”的操作。參數手動調整，使路徑曲率減小。

圖1　在賽車的可視范圍內，利用軌跡規劃算法計算出物體運動的最優軌跡

1.2神經網絡

圖2　神經網絡的5維輸入，右邊圖出現的概率小于1%

神經網絡的輸入層、隱藏層存儲了權值，權值的修改使用梯度。梯度的計算采用Backpropagation［9］。

我們使用的神經網絡有兩層，接受5維輸入，1維輸出，隱藏層為10維。激活函數為tanh-linear。5維的輸入參數分別是：賽車的當前速度（v），當前速度于第一個目標點的角度（θ1），當前位置到第一個目標點的距離（L1），當前位置、第一個目標點、第二個目標點形成的夾角 （θ2），第一個目標點到第二個目標點的距離（L2）。如圖2，圖2中與左邊圖相對應的另一種情況是右邊圖。但實驗表明，右邊圖出現的概率小于1%，所以，神經網絡忽略此情況。輸出的值是一個介于0和1之間的比值，其表示如下：

F表示賽車產生的向正前方的加速度，UpLimit表示賽車的最大加速度，為正值。DownLimit表示賽車的最大減速度，為負值。當神經網絡產生target比值后，就可以通過逆變換得到正向加速度，正向加速度確定后，側向加速度也就確定了。

我們利用遍歷算法產生一個訓練集。遍歷算法根據目標點產生賽車的正向和側向加速度。算法先嘗試

用最大的加速度到達下一個目標點。當賽車到達第一個目標點時，判斷賽車是否可以到達下一個目標點，如果出現超速而無法到達的情況，則回溯，將賽車運動的加速度減小一個定值。如此重復，直到找到最終的解。將遍歷算法的輸入和輸出經過處理后記錄下來，就可以輸入到神經網絡進行學習。選擇隱藏層不同維數的神經網絡進行測試，選取最優的。訓練的方法為Levenberg-Marquardt［7］。選取的性能函數為均方誤差。訓練集被隨機的分成了三個集合：訓練、驗證、測試。

1.3局部優化

由于遍歷算法和神經網絡產生的加速度，都無法保證賽車不會沖出軌道。因此，我們利用局部優化接收產生的加速度。假設賽車在一定時間內按照給定的加速度運動，判斷賽車在這段時間內是否有可能沖出軌道。如果有可能的話，則產生一個局部安全的加速度。

2　實驗結果

我們使用的訓練示例有11544個，訓練神經網絡的結構為：兩層，tanh-linear型，輸入5維，輸出1維。隱藏層維數不同的各個神經網絡比較如圖3。

綜合計算效果、計算時間以及防止過擬合的考慮，最后選擇隱藏層為10個節點。

2.1神經網絡與遍歷算法結果比較比較在相同的輸入下，兩種算法計算出的正向加速度和側向加速度，共比較2031組。后者減去前者差值分布如圖4（a）。（賽車最大向前加速度為3，最大減速度為-10，側向加速度為1，側向減速度為-1）

2.2算法效果對比

如圖4（b），選擇100個軌道，每個3圈，比較兩種算法控制賽車的運行時間。大多數情況下，遍歷算法優于神經網絡。

2.3算法消耗時間分析比較

遍歷算法運行時間波動較大。受外部輸入和內部參數的共同影響。當超速較多時，回溯次數增多，運行時間變大。同時，增大賽車最大加速度值，減小步長step，回溯也會增多。相反，神經網絡的計算時間固定，僅受自身機構影響。

圖3　隱藏層維數不同的各個神經網絡比較

圖4　神經網絡與遍歷算法結果比較

3　結語

本文利用神經網絡模仿玩家行為，在給定賽車和賽道的情況下，算法首先根據賽車和賽道的情況計算出最短路徑，并對最短路徑做切角、延角操作，確保了路徑在實際場景中的可行性。接著找出合適的加速度減少了賽車的運動時間。從實驗結果可以看出，神經網絡的模仿效果很理想。算法體現出優點：（1）計算用時穩定且較快；（2）插值效果好。未來的研究重點是使算法適用于賽道中存在障礙物以及其他玩家的情景，同時降低神經網絡控制賽車的運動時間。

［1］Cardamone L，Loiacono D，Lanzi P L，et al.Searching for the Optimal Racing Line Using Genetic Algorithms［C］.Computational Intelligence and Games（CIG），2010 IEEE Symposium on.IEEE，2010：388-394.

［2］Botta M，Gautieri V，Loiacono D，et al.Evolving the Optimal Racing Line in a High-End Racing Game［C］.Computational Intelligence and Games（CIG），2012 IEEE Conference on.IEEE，2012：108-115.

［3］Braghin F，Cheli F，Melzi S，et al.Race Driver Model［J］.Computers&Structures，2008，86（13）：503-1516.

［4］Tang H，Tan C H，Tan K C，et al.Neural Network Versus Behavior Based Approach in Simulated Car Racing Game［C］.Evolving and Self-Developing Intelligent Systems，2009.ESDIS'09.IEEE Workshop on.IEEE，2009：58-65.

［5］Lecchi S.Artificial Intelligence in Racing Games［C］.Computational Intelligence and Games，2009.CIG 2009.IEEE Symposium on. IEEE，2009：1-1.

［6］Bishop C M.Pattern Recognition and Machine Learning［M］.Singapore：Springer，2006：241-249.

［7］Reynaldi A，Lukas S，Margaretha H.Backpropagation and Levenberg-Marquardt Algorithm for Training Finite Element Neural Network ［C］.Computer Modeling and Simulation（EMS），2012 Sixth UKSim/AMSS European Symposium on.IEEE，2012：89-94.

［8］Bourg D M，Seemann G.AI for Game Developers［M］."O'Reilly Media，Inc."，2004：Section 14.3.

［9］Coulom R.Reinforcement Learning Using Neural Networks，with Applications to Motor Control［D］.Institute National Polytechnique de Grenoble-INPG，2002.

［10］Tan C I，Tai W K.Path Stitching：Controllable Racing Path Generation［C］.International Conference on Machine Learning and Cybernetics.2009，5：2939-2944.

［11］Haykin S，Network N.A Comprehensive Foundation［J］.Neural Networks，2004，2（2004）.

［12］Chaperot B，Fyfe C.Advanced Artificial Intelligence Techniques Applied to a Motocross Game［J］.Computing and Information Systems，2006，10（2）：27.

［13］Togelius J，Lucas S M.Arms Races and Car Races［M］.Parallel Problem Solving from Nature-PPSN IX.Springer Berlin Heidelberg，2006：613-622.

［14］Togelius J，Lucas S M.Evolving Robust and Specialized Car Racing Skills［C］.Evolutionary Computation，2006.CEC 2006.IEEE Congress on.IEEE，2006：1187-1194.

［15］Togelius J，Lucas S M，De Nardi R.Computational Intelligence in Racing Games［M］.Advanced Intelligent Paradigms in Computer Games.Springer Berlin Heidelberg，2007：39-69.

［16］Cardamone L，Loiacono D，Lanzi P L.On-Line Neuroevolution Applied to the Open Racing Car Simulator［C］.Evolutionary Computation，2009.CEC'09.IEEE Congress on.IEEE，2009：2622-2629.

YU Ting，LIU Xun

（College of Computer Science，Sichuan University，Chengdu 610065）

Racing Car Games；Neural Networks；Path-Planning；Force-Gen；Local-Optimization

AI Racing Game Algorithm Based on Neural Networks

1007-1423（2016）24-0003-04DOI：10.3969/j.issn.1007-1423.2016.24.001

余婷（1991-），女，重慶豐都人，碩士，研究方向為人工智能、計算機智能

2016-06-03

2016-08-20

賽車游戲中控制非玩家選手的智能算法在比賽場景中存在其他車輛或者障礙物時，不能僅靠整個賽場確定賽車的運動軌跡，需要根據當前狀態調整非玩家選手的運動軌跡。從而實現非玩家賽車跑完賽程所花時間最短。基于賽車固有加速度以及賽車安全性的考慮提出基于神經網絡AI賽車游戲算法，算法從三個方面模仿玩家行為從而實現賽車競速時間的減少，實驗證明算法的可行性和有效性。

賽車游戲；神經網絡；軌跡規劃；遍歷算法；局部優化

劉循（1963-），女，四川人，博士，副教授，研究方向為計算機應用

Racing game is mainly under the competition scene，and there are other cars or obstacle.In order to achieve the best lap-time on a given track with a given car，need to adjust the trajectory of the non-player based on the current status of the game rather than determine that by the entire stadium.Following this sentiment，trains neural networks to play racing games by simulating the behavior of the players.The algorithm is based on the acceleration and car safety，and imitate from three steps.It proves that the algorithm is feasible and effective.