人工智能尋路算法及其在游戲中的應(yīng)用研究.pdf

1、人工智能是游戲設(shè)計(jì)過程中重要的組成部分，路徑搜索是人工智能應(yīng)用于游戲中的最基本的問題之一。在當(dāng)今游戲工業(yè)界，A*算法是被大家最廣泛使用的人工智能尋路算法，也是最有效的最短路徑搜索算法之一。A*算法實(shí)際上是一種基于廣度優(yōu)先搜索的啟發(fā)式搜索算法，通常采用估價(jià)函數(shù)對當(dāng)前的搜索位置進(jìn)行評估。標(biāo)準(zhǔn)的A*算法根據(jù)Closed表對路徑進(jìn)行逆向提取，當(dāng)存在死路的時(shí)，它會把走向死路的點(diǎn)也包含進(jìn)去，造成走彎路的現(xiàn)象，從而不能得到最優(yōu)解。 本文針對標(biāo)

2、準(zhǔn)A*算法存在走彎路的問題，提出一種改進(jìn)的A*算法。該算法通過為每個(gè)節(jié)點(diǎn)增加一個(gè)父指針，在路徑提取的時(shí)候，根據(jù)父節(jié)點(diǎn)表和Closed表中節(jié)點(diǎn)的信息，由目標(biāo)節(jié)點(diǎn)開始通過其父指針不斷回溯，直到開始節(jié)點(diǎn)為止，這有效地避免走彎路的現(xiàn)象，保證得到最優(yōu)路徑，具有較好的通用性。由于人工智能查詢需要不斷的調(diào)用A*算法，給程序性能帶來很大的負(fù)面影響，本文針對多次A*算法的調(diào)用問題，對上述改進(jìn)A*算法做了進(jìn)一步的改進(jìn)，提出了一種衍生A*算法。該算法可以接受