基于案例推理的路徑規(guī)劃研究.pdf

1、路徑搜索是計(jì)算機(jī)游戲中最為常見(jiàn)的任務(wù)之一，搜索算法的質(zhì)量很大程度上影響著游戲的趣味性與可玩性。A*算法是最典型的啟發(fā)式搜索算法，在路徑確實(shí)存在的情況下，它能夠確保得到一條最優(yōu)路徑。然而，該算法有著較高的時(shí)間和空間復(fù)雜度，因此，它不適用于多任務(wù)快速路徑規(guī)劃的問(wèn)題。為了使A*算法滿(mǎn)足多任務(wù)快速路徑規(guī)劃的需求，本文提出了基于案例推理的路徑規(guī)劃算法。采用離線(xiàn)和在線(xiàn)過(guò)程相結(jié)合，提出了案例（即已知路徑的起始終止點(diǎn)對(duì)）的kd樹(shù)存儲(chǔ)和查詢(xún)機(jī)制，并給出了

2、案例的重用方法。
　　首先，在離線(xiàn)狀態(tài)下，隨機(jī)產(chǎn)生和保存一些路徑作為已知案例，并根據(jù)這些案例構(gòu)建kd樹(shù)。其次，在線(xiàn)狀態(tài)下，當(dāng)新任務(wù)出現(xiàn)的時(shí)候，我們不再簡(jiǎn)單的利用A*算法從頭進(jìn)行搜索，而是在kd樹(shù)中快速查詢(xún)最相似的案例。然后我們給出了案例的重用機(jī)制：判斷所查詢(xún)到的這個(gè)案例是否滿(mǎn)足預(yù)先設(shè)定的閾值。如果滿(mǎn)足閾值條件，那么我們就利用這條所選出來(lái)的預(yù)存相似案例，然后對(duì)該路徑進(jìn)行適當(dāng)?shù)恼{(diào)整來(lái)得到新任務(wù)的解決方案。否則，我們就要利用A*對(duì)這個(gè)新