人工智能課件第五次課

A*路徑搜索

A*PathfindingWearegoingtodiscussthefundamentalsoftheA*pathfindingalgorithm.基本A*路徑搜索算法TheA*Algorithmprovidesaneffectivesolutiontotheproblemofpathfinding.A*路徑搜索

A*PathfindingWearego1定義搜索區(qū)域

DefiningthesearchareaThefirststepinpathfindingistodefinethesearcharea.首先定義搜索區(qū)域。Thegameworldneedstoberepresentedbypointsthatboththegamecharactersandobjectscanoccupy.Weneedtoreducethenodestoamanageablenumber,whichiswhatwemeanwhenwesayweneedtosimplifythesearcharea.減少搜索區(qū)域的節(jié)點(diǎn)數(shù)量，簡(jiǎn)化搜索區(qū)域。

定義搜索區(qū)域

Definingthesearchare2定義搜索區(qū)域

Definingthesearcharea定義搜索區(qū)域

Definingthesearchare3基于方塊的搜索區(qū)域

Tiledsearcharea基于方塊的搜索區(qū)域

Tiledsearcharea4StartingthesearchWewillusetheA*algorithmtofindtheshortestpathbetweenanytwonodeswhileavoidingtheobstacles.避開障礙在任意兩點(diǎn)之間用A*算法獲得最短路徑。OpenList-Weneedawaytokeeptrackofwhichtilesneedtobesearched.可以作為后備檢測(cè)的點(diǎn)的集合；ClosedList-thetilesthatalreadywerechecked.已經(jīng)檢測(cè)完成的點(diǎn)的集合。StartingthesearchWewilluse5A*偽代碼

A*pseudocodeAddthestartingnodetotheopenlistWhiletheopenlistisnotempty{currentnode=nodefromopenlistwiththelowestcostifcurrentnode=goalnodethenpathcompleteelsemovecurrentnodetotheclosedlistexamineeachnodeadjacenttothecurrentnodeforeachadjacentnodeifitisn’tontheopenlistandisn’tontheclosedlistanditisn’tanobstaclethenmoveittoopenlistandcalculatecost}A*偽代碼

A*pseudocodeAddthest6A*偽代碼

A*pseudocode將開始點(diǎn)加到OpenList表中；重復(fù)一下過程，直到OpenList表空為止：{當(dāng)前點(diǎn)=OpenList表中代價(jià)值最小的點(diǎn)；如果當(dāng)前點(diǎn)為目標(biāo)點(diǎn)，則搜索完成；否則將當(dāng)前點(diǎn)移到ClosedList表中；對(duì)與當(dāng)前點(diǎn)相連的每一點(diǎn)，重復(fù)執(zhí)行：如果該點(diǎn)不在OpenList、ClosedList，并且不是障礙點(diǎn)則將該點(diǎn)移到OpenList表中，計(jì)算該點(diǎn)的代價(jià)值；}A*偽代碼

A*pseudocode將開始點(diǎn)加到Open7CreateatiledsearchareaSpider-startingpointHumancharacter-destinationSolidblacksquares-wallobstaclesCreateatiledsearchareaSpid8AdjacenttilestoconsiderWeproceedtocheckeachoftheeightadjacenttilesandthenaddeachvalidtiletotheopenlist.對(duì)與蜘蛛相鄰的八個(gè)點(diǎn)檢查，不在任何表中和不是障礙的點(diǎn)加入OpenList表中。AdjacenttilestoconsiderWep9將開始點(diǎn)移到ClosedList表中

MovingthestartingtiletotheclosedlistStartpoint開始點(diǎn)將開始點(diǎn)移到ClosedList表中

Movingthe10LinkingtotheparentsLinktoparentsLinkingtotheparentsLinkto11賦予數(shù)值

ScoringWewillusepathscoringtodeterminethebestpathfromthestartingtiletothedestinationtile.(1)Welookatthecosttomovefromthestartingtiletoanygiventile.(2)Welookatthecosttomovefromthegiventiletothedestinationtile.(3)Wetakethesumofthecostofeachtilethatleadsbacktotheinitiallocation.賦予數(shù)值

ScoringWewillusepaths12CalculatingthepathscoreScore=Costfromstart+HeuristicWewillcheckthetileswiththelowestcost.Alowercostwillequatetoashorterpath.StartpointgivenpointdestinationCostfromstartheuristicCalculatingthepathscoreScor13InitialtilepathscoresInitialtilepathscores14初始化每一點(diǎn)的數(shù)值

InitialtilepathscoresThesvalueisthecostofgettingtherefromthestartingtile.s=從開始點(diǎn)到當(dāng)前點(diǎn)的累計(jì)代價(jià)值Thehvalueistheheuristicwhichisanestimateofthenumberofstepsfromthegiventiletothedestinationtile.h=從當(dāng)前點(diǎn)到目標(biāo)點(diǎn)的步數(shù)值Thecvalueisthesumofsandh.c=s+h初始化每一點(diǎn)的數(shù)值

Initialtilepathsc15Examiningtile(5,6)Examiningtile(5,6)16Examiningtile(5,5)Examiningtile(5,5)17Examiningtile(5,4)Examiningtile(5,4)18Examiningallthetiles

withacostof5Examiningallthetiles

with19Examiningalltiles

withacostof6Examiningalltiles

withaco20Examiningtile(3,4)Examiningtile(3,4)21Examiningtiles(2,5)and(3,5)Examiningtiles(2,5)and(3,522Examiningtiles(1,6)(2,6)(3,6)Examiningtiles(1,6)(2,6)(3,623最終路徑

ThecompletedpathS=6543210最終路徑

ThecompletedpathS=24FindingadeadendFindingadeadend25exerciseexercise26區(qū)域代價(jià)值

TerrainCostTheshortestpathisn’talwaysthefastestpath.最短路徑不一定是最快路徑。Alongwalkalongaroadmightbefasterthanashorterwalkthroughaswamp.如有沼澤地的情況。區(qū)域代價(jià)值

TerrainCostTheshortest27對(duì)區(qū)域代價(jià)賦予數(shù)值

ScoringwithterraincostTotalcostfromstart=costfromstart+terraincostScore=totalcostfromstart+heuristic每一點(diǎn)總代價(jià)值=從開始點(diǎn)到當(dāng)前點(diǎn)的累計(jì)代價(jià)值+區(qū)域代價(jià)值+啟發(fā)式數(shù)值。對(duì)區(qū)域代價(jià)賦予數(shù)值

Scoringwithterrain28區(qū)域的種類

TypesofterrainOpenterrain平坦區(qū)域Cost=1Grassland草地Cost=3Swampland沼澤地Cost=5區(qū)域的種類

TypesofterrainOpenter29AddingdifferentterrainelementsAddingdifferentterraineleme30OriginalpathoverterrainelementsOriginalpathoverterrainele31Calculatingthelowest-costpathCalculatingthelowest-costpa32Thelowest-costpathThelowest-costpath33InfluenceMappingOtherelementscaninfluencepathcostwhencalculatingapathwithA*.其他因素也能影響路徑代價(jià)。Nodesthatpassthroughthelineofsightofanyenemymightpresentahighercost.如在敵人的視線范圍內(nèi)，區(qū)域代價(jià)比較高。InfluenceMappingOtherelement34InfluenceMappingInfluenceMappingisawaytovarythecostoftheA*nodesdependingonwhatishappeninginthegame.依賴游戲的不同，給節(jié)點(diǎn)不同的代價(jià)值。InfluenceMappingInfluenceMap35敵人炮火影響的區(qū)域代價(jià)

Influencedbytheenemyfiringzone敵人炮火影響的區(qū)域代價(jià)

Influencedbythe36記錄事件計(jì)算代價(jià)

RecordinggameincidentsWecanrecordindividualgameincidentsinaninfluencemap.Weareusingwhatthecharacterdoes.Iftheplayerrepeatedlyambushesandkillscomputer-controlledcharactersatagivendoorway,thatthedoorwaymightincreaseincost.如果玩家在門口重復(fù)地伏擊并殺死角色，則門口的代價(jià)增加。記錄事件計(jì)算代價(jià)

Recordinggameincide37InfluencedbythenumberofkillsInfluencedbythenumberofki38小結(jié)A*算法的基本思想；對(duì)區(qū)域代價(jià)的搜索實(shí)現(xiàn)的算法分析；在運(yùn)行過程中代價(jià)的改變。小結(jié)A*算法的基本思想；39思考題（1）A*算法的核心思想是什么？（2）A*算法與其他（如基本路徑搜索）算法有何不同？（3）在路徑搜索算法中為什么A*算法是最有效的算法？（4）A*算法有何不足？遇到什么樣情況不是最快的搜索算法？思考題（1）A*算法的核心思想是什么？40本次實(shí)驗(yàn)內(nèi)容用A*算法實(shí)現(xiàn)路徑搜索。如有時(shí)間，可以考慮區(qū)域代價(jià)情況的搜索。在實(shí)現(xiàn)過程中，對(duì)代價(jià)可采用數(shù)組方式記錄代價(jià)值。感興趣可以將根據(jù)運(yùn)行狀況改變代價(jià)值的思想，運(yùn)用到實(shí)際的游戲或優(yōu)化系統(tǒng)中。本次實(shí)驗(yàn)內(nèi)容用A*算法實(shí)現(xiàn)路徑搜索。41A*路徑搜索

A*PathfindingWearegoingtodiscussthefundamentalsoftheA*pathfindingalgorithm.基本A*路徑搜索算法TheA*Algorithmprovidesaneffectivesolutiontotheproblemofpathfinding.A*路徑搜索

A*PathfindingWearego42定義搜索區(qū)域

DefiningthesearchareaThefirststepinpathfindingistodefinethesearcharea.首先定義搜索區(qū)域。Thegameworldneedstoberepresentedbypointsthatboththegamecharactersandobjectscanoccupy.Weneedtoreducethenodestoamanageablenumber,whichiswhatwemeanwhenwesayweneedtosimplifythesearcharea.減少搜索區(qū)域的節(jié)點(diǎn)數(shù)量，簡(jiǎn)化搜索區(qū)域。

定義搜索區(qū)域

Definingthesearchare43定義搜索區(qū)域

Definingthesearcharea定義搜索區(qū)域

Definingthesearchare44基于方塊的搜索區(qū)域

Tiledsearcharea基于方塊的搜索區(qū)域

Tiledsearcharea45StartingthesearchWewillusetheA*algorithmtofindtheshortestpathbetweenanytwonodeswhileavoidingtheobstacles.避開障礙在任意兩點(diǎn)之間用A*算法獲得最短路徑。OpenList-Weneedawaytokeeptrackofwhichtilesneedtobesearched.可以作為后備檢測(cè)的點(diǎn)的集合；ClosedList-thetilesthatalreadywerechecked.已經(jīng)檢測(cè)完成的點(diǎn)的集合。StartingthesearchWewilluse46A*偽代碼

A*pseudocodeAddthestartingnodetotheopenlistWhiletheopenlistisnotempty{currentnode=nodefromopenlistwiththelowestcostifcurrentnode=goalnodethenpathcompleteelsemovecurrentnodetotheclosedlistexamineeachnodeadjacenttothecurrentnodeforeachadjacentnodeifitisn’tontheopenlistandisn’tontheclosedlistanditisn’tanobstaclethenmoveittoopenlistandcalculatecost}A*偽代碼

A*pseudocodeAddthest47A*偽代碼

A*pseudocode將開始點(diǎn)加到OpenList表中；重復(fù)一下過程，直到OpenList表空為止：{當(dāng)前點(diǎn)=OpenList表中代價(jià)值最小的點(diǎn)；如果當(dāng)前點(diǎn)為目標(biāo)點(diǎn)，則搜索完成；否則將當(dāng)前點(diǎn)移到ClosedList表中；對(duì)與當(dāng)前點(diǎn)相連的每一點(diǎn)，重復(fù)執(zhí)行：如果該點(diǎn)不在OpenList、ClosedList，并且不是障礙點(diǎn)則將該點(diǎn)移到OpenList表中，計(jì)算該點(diǎn)的代價(jià)值；}A*偽代碼

A*pseudocode將開始點(diǎn)加到Open48CreateatiledsearchareaSpider-startingpointHumancharacter-destinationSolidblacksquares-wallobstaclesCreateatiledsearchareaSpid49AdjacenttilestoconsiderWeproceedtocheckeachoftheeightadjacenttilesandthenaddeachvalidtiletotheopenlist.對(duì)與蜘蛛相鄰的八個(gè)點(diǎn)檢查，不在任何表中和不是障礙的點(diǎn)加入OpenList表中。AdjacenttilestoconsiderWep50將開始點(diǎn)移到ClosedList表中

MovingthestartingtiletotheclosedlistStartpoint開始點(diǎn)將開始點(diǎn)移到ClosedList表中

Movingthe51LinkingtotheparentsLinktoparentsLinkingtotheparentsLinkto52賦予數(shù)值

ScoringWewillusepathscoringtodeterminethebestpathfromthestartingtiletothedestinationtile.(1)Welookatthecosttomovefromthestartingtiletoanygiventile.(2)Welookatthecosttomovefromthegiventiletothedestinationtile.(3)Wetakethesumofthecostofeachtilethatleadsbacktotheinitiallocation.賦予數(shù)值

ScoringWewillusepaths53CalculatingthepathscoreScore=Costfromstart+HeuristicWewillcheckthetileswiththelowestcost.Alowercostwillequatetoashorterpath.StartpointgivenpointdestinationCostfromstartheuristicCalculatingthepathscoreScor54InitialtilepathscoresInitialtilepathscores55初始化每一點(diǎn)的數(shù)值

InitialtilepathscoresThesvalueisthecostofgettingtherefromthestartingtile.s=從開始點(diǎn)到當(dāng)前點(diǎn)的累計(jì)代價(jià)值Thehvalueistheheuristicwhichisanestimateofthenumberofstepsfromthegiventiletothedestinationtile.h=從當(dāng)前點(diǎn)到目標(biāo)點(diǎn)的步數(shù)值Thecvalueisthesumofsandh.c=s+h初始化每一點(diǎn)的數(shù)值

Initialtilepathsc56Examiningtile(5,6)Examiningtile(5,6)57Examiningtile(5,5)Examiningtile(5,5)58Examiningtile(5,4)Examiningtile(5,4)59Examiningallthetiles

withacostof5Examiningallthetiles

with60Examiningalltiles

withacostof6Examiningalltiles

withaco61Examiningtile(3,4)Examiningtile(3,4)62Examiningtiles(2,5)and(3,5)Examiningtiles(2,5)and(3,563Examiningtiles(1,6)(2,6)(3,6)Examiningtiles(1,6)(2,6)(3,664最終路徑

ThecompletedpathS=6543210最終路徑

ThecompletedpathS=65FindingadeadendFindingadeadend66exerciseexercise67區(qū)域代價(jià)值

TerrainCostTheshortestpathisn’talwaysthefastestpath.最短路徑不一定是最快路徑。Alongwalkalongaroadmightbefasterthanashorterwalkthroughaswamp.如有沼澤地的情況。區(qū)域代價(jià)值

TerrainCostTheshortest68對(duì)區(qū)域代價(jià)賦予數(shù)值

ScoringwithterraincostTotalcostfromstart=costfromstart+terraincostScore=totalcostfromstart+heuristic每一點(diǎn)總代價(jià)值=從開始點(diǎn)到當(dāng)前點(diǎn)的累計(jì)代價(jià)值+區(qū)域代價(jià)值+啟發(fā)式數(shù)值。對(duì)區(qū)域代價(jià)賦予數(shù)值

Scoringwithterrain69區(qū)域的種類

TypesofterrainOpenterrain平坦區(qū)域Cost=1Grassland草地Cost=3Swampland沼澤地Cost=5區(qū)域的種類

TypesofterrainOpenter70AddingdifferentterrainelementsAddingdifferentterraineleme71OriginalpathoverterrainelementsOriginalpathoverterrainele72Calculatingthelowest-costpathCalculatingthelowest-costpa73Thelowest-costpathThelowest-costpath74Inf