解決A*尋路中邊緣行走問題

     用碰撞體來約束世界范圍已經(jīng)用得很廣泛了，玩家與世界邊緣的交互問題也容易用碰撞面的法線和玩家朝向來解決。然而對(duì)于一個(gè)基于A* PathFinding的游戲，貌似還沒有人去考慮和解決這個(gè)問題。最初考慮這個(gè)問題，是因?yàn)橛螒蛑屑尤肓薃WSD的移動(dòng)方式，當(dāng)碰到阻擋就靜止不動(dòng)了，加上有時(shí)阻擋刷得與場(chǎng)景不太貼合，造成玩家在移動(dòng)上的不爽快。考慮下圖的情況，藍(lán)色三角是角色，紅色線段給出了前進(jìn)方向和終點(diǎn)（游戲中配置為角色朝向上5m處）。

     我想了兩種方案，最初的方案靈感來自光線反射，如下圖所示。

     因?yàn)樽钃醺褡邮禽S對(duì)齊的，通過法向量n可以得到b點(diǎn)的反射向量e'-o，將|e'-o|限定在一個(gè)固定值，此時(shí)如果e'不在阻擋里面，就將它作為新的終點(diǎn)。該方案的實(shí)驗(yàn)結(jié)果不太令人滿意，當(dāng)角色離阻擋較近時(shí)斷續(xù)感太明顯，因?yàn)閨e' - b|的長(zhǎng)度較短。另外它不能處理e'在阻擋里的情況，被卡住不動(dòng)的概率依然較大。

     第二種方案是根據(jù)移動(dòng)趨向在一個(gè)軸向找一個(gè)可達(dá)試探點(diǎn)，然后用限制了搜索空間（搜索節(jié)點(diǎn)在50以內(nèi)）的A*算法找到一條到試探點(diǎn)的路徑，如下圖。

     設(shè)diff_x = 終點(diǎn)x - 起點(diǎn)x，diff_y = 終點(diǎn)y - 起點(diǎn)y，當(dāng)diff_x > diff_y，認(rèn)定為趨向x方向上移動(dòng)，在這種情況下在終點(diǎn)y軸向上±10個(gè)格子內(nèi)去找到一個(gè)最接近終點(diǎn)的無阻擋點(diǎn)（稱它為可達(dá)試探點(diǎn)）。由于試探點(diǎn)與玩家當(dāng)前點(diǎn)極有可能是直線不連通的，而且它們不可能太遠(yuǎn)，所以使用了一個(gè)將搜索節(jié)點(diǎn)個(gè)數(shù)限制在50以內(nèi)A*來得到一條路徑。該方案大部分情況都能在邊緣找到合理點(diǎn)，但如果玩家垂直面朝阻擋內(nèi)移動(dòng)且不能在限制搜索范圍內(nèi)找到可達(dá)點(diǎn)，角色就會(huì)卡住不動(dòng)，這種情況就只能讓玩家自己調(diào)整一下朝向了。

posted on 2013-05-04 23:49 Heath 閱讀(1728) 評(píng)論(0)  編輯 收藏 引用 所屬分類: Game Development