人工智能课件第五次课

A*路径搜索

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

A*PathfindingWearego1定义搜索区域

DefiningthesearchareaThefirststepinpathfindingistodefinethesearcharea.首先定义搜索区域。Thegameworldneedstoberepresentedbypointsthatboththegamecharactersandobjectscanoccupy.Weneedtoreducethenodestoamanageablenumber,whichiswhatwemeanwhenwesayweneedtosimplifythesearcharea.减少搜索区域的节点数量，简化搜索区域。

定义搜索区域

Definingthesearchare2定义搜索区域

Definingthesearcharea定义搜索区域

Definingthesearchare3基于方块的搜索区域

Tiledsearcharea基于方块的搜索区域

Tiledsearcharea4StartingthesearchWewillusetheA*algorithmtofindtheshortestpathbetweenanytwonodeswhileavoidingtheobstacles.避开障碍在任意两点之间用A*算法获得最短路径。OpenList-Weneedawaytokeeptrackofwhichtilesneedtobesearched.可以作为后备检测的点的集合；ClosedList-thetilesthatalreadywerechecked.已经检测完成的点的集合。StartingthesearchWewilluse5A*伪代码

A*pseudocodeAddthestartingnodetotheopenlistWhiletheopenlistisnotempty{currentnode=nodefromopenlistwiththelowestcostifcurrentnode=goalnodethenpathcompleteelsemovecurrentnodetotheclosedlistexamineeachnodeadjacenttothecurrentnodeforeachadjacentnodeifitisn’tontheopenlistandisn’tontheclosedlistanditisn’tanobstaclethenmoveittoopenlistandcalculatecost}A*伪代码

A*pseudocodeAddthest6A*伪代码

A*pseudocode将开始点加到OpenList表中；重复一下过程，直到OpenList表空为止：{当前点=OpenList表中代价值最小的点；如果当前点为目标点，则搜索完成；否则将当前点移到ClosedList表中；对与当前点相连的每一点，重复执行：如果该点不在OpenList、ClosedList，并且不是障碍点则将该点移到OpenList表中，计算该点的代价值；}A*伪代码

A*pseudocode将开始点加到Open7CreateatiledsearchareaSpider-startingpointHumancharacter-destinationSolidblacksquares-wallobstaclesCreateatiledsearchareaSpid8AdjacenttilestoconsiderWeproceedtocheckeachoftheeightadjacenttilesandthenaddeachvalidtiletotheopenlist.对与蜘蛛相邻的八个点检查，不在任何表中和不是障碍的点加入OpenList表中。AdjacenttilestoconsiderWep9将开始点移到ClosedList表中

MovingthestartingtiletotheclosedlistStartpoint开始点将开始点移到ClosedList表中

Movingthe10LinkingtotheparentsLinktoparentsLinkingtotheparentsLinkto11赋予数值

ScoringWewillusepathscoringtodeterminethebestpathfromthestartingtiletothedestinationtile.(1)Welookatthecosttomovefromthestartingtiletoanygiventile.(2)Welookatthecosttomovefromthegiventiletothedestinationtile.(3)Wetakethesumofthecostofeachtilethatleadsbacktotheinitiallocation.赋予数值

ScoringWewillusepaths12CalculatingthepathscoreScore=Costfromstart+HeuristicWewillcheckthetileswiththelowestcost.Alowercostwillequatetoashorterpath.StartpointgivenpointdestinationCostfromstartheuristicCalculatingthepathscoreScor13InitialtilepathscoresInitialtilepathscores14初始化每一点的数值

InitialtilepathscoresThesvalueisthecostofgettingtherefromthestartingtile.s=从开始点到当前点的累计代价值Thehvalueistheheuristicwhichisanestimateofthenumberofstepsfromthegiventiletothedestinationtile.h=从当前点到目标点的步数值Thecvalueisthesumofsandh.c=s+h初始化每一点的数值

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区域代价值

TerrainCostTheshortestpathisn’talwaysthefastestpath.最短路径不一定是最快路径。Alongwalkalongaroadmightbefasterthanashorterwalkthroughaswamp.如有沼泽地的情况。区域代价值

TerrainCostTheshortest27对区域代价赋予数值

ScoringwithterraincostTotalcostfromstart=costfromstart+terraincostScore=totalcostfromstart+heuristic每一点总代价值=从开始点到当前点的累计代价值+区域代价值+启发式数值。对区域代价赋予数值

Scoringwithterrain28区域的种类

TypesofterrainOpenterrain平坦区域Cost=1Grassland草地Cost=3Swampland沼泽地Cost=5区域的种类

TypesofterrainOpenter29AddingdifferentterrainelementsAddingdifferentterraineleme30OriginalpathoverterrainelementsOriginalpathoverterrainele31Calculatingthelowest-costpathCalculatingthelowest-costpa32Thelowest-costpathThelowest-costpath33InfluenceMappingOtherelementscaninfluencepathcostwhencalculatingapathwithA*.其他因素也能影响路径代价。Nodesthatpassthroughthelineofsightofanyenemymightpresentahighercost.如在敌人的视线范围内，区域代价比较高。InfluenceMappingOtherelement34InfluenceMappingInfluenceMappingisawaytovarythecostoftheA*nodesdependingonwhatishappeninginthegame.依赖游戏的不同，给节点不同的代价值。InfluenceMappingInfluenceMap35敌人炮火影响的区域代价

Influencedbytheenemyfiringzone敌人炮火影响的区域代价

Influencedbythe36记录事件计算代价

RecordinggameincidentsWecanrecordindividualgameincidentsinaninfluencemap.Weareusingwhatthecharacterdoes.Iftheplayerrepeatedlyambushesandkillscomputer-controlledcharactersatagivendoorway,thatthedoorwaymightincreaseincost.如果玩家在门口重复地伏击并杀死角色，则门口的代价增加。记录事件计算代价

Recordinggameincide37InfluencedbythenumberofkillsInfluencedbythenumberofki38小结A*算法的基本思想；对区域代价的搜索实现的算法分析；在运行过程中代价的改变。小结A*算法的基本思想；39思考题（1）A*算法的核心思想是什么？（2）A*算法与其他（如基本路径搜索）算法有何不同？（3）在路径搜索算法中为什么A*算法是最有效的算法？（4）A*算法有何不足？遇到什么样情况不是最快的搜索算法？思考题（1）A*算法的核心思想是什么？40本次实验内容用A*算法实现路径搜索。如有时间，可以考虑区域代价情况的搜索。在实现过程中，对代价可采用数组方式记录代价值。感兴趣可以将根据运行状况改变代价值的思想，运用到实际的游戏或优化系统中。本次实验内容用A*算法实现路径搜索。41A*路径搜索

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

A*PathfindingWearego42定义搜索区域

DefiningthesearchareaThefirststepinpathfindingistodefinethesearcharea.首先定义搜索区域。Thegameworldneedstoberepresentedbypointsthatboththegamecharactersandobjectscanoccupy.Weneedtoreducethenodestoamanageablenumber,whichiswhatwemeanwhenwesayweneedtosimplifythesearcharea.减少搜索区域的节点数量，简化搜索区域。

定义搜索区域

Definingthesearchare43定义搜索区域

Definingthesearcharea定义搜索区域

Definingthesearchare44基于方块的搜索区域

Tiledsearcharea基于方块的搜索区域

Tiledsearcharea45StartingthesearchWewillusetheA*algorithmtofindtheshortestpathbetweenanytwonodeswhileavoidingtheobstacles.避开障碍在任意两点之间用A*算法获得最短路径。OpenList-Weneedawaytokeeptrackofwhichtilesneedtobesearched.可以作为后备检测的点的集合；ClosedList-thetilesthatalreadywerechecked.已经检测完成的点的集合。StartingthesearchWewilluse46A*伪代码

A*pseudocodeAddthestartingnodetotheopenlistWhiletheopenlistisnotempty{currentnode=nodefromopenlistwiththelowestcostifcurrentnode=goalnodethenpathcompleteelsemovecurrentnodetotheclosedlistexamineeachnodeadjacenttothecurrentnodeforeachadjacentnodeifitisn’tontheopenlistandisn’tontheclosedlistanditisn’tanobstaclethenmoveittoopenlistandcalculatecost}A*伪代码

A*pseudocodeAddthest47A*伪代码

A*pseudocode将开始点加到OpenList表中；重复一下过程，直到OpenList表空为止：{当前点=OpenList表中代价值最小的点；如果当前点为目标点，则搜索完成；否则将当前点移到ClosedList表中；对与当前点相连的每一点，重复执行：如果该点不在OpenList、ClosedList，并且不是障碍点则将该点移到OpenList表中，计算该点的代价值；}A*伪代码

A*pseudocode将开始点加到Open48CreateatiledsearchareaSpider-startingpointHumancharacter-destinationSolidblacksquares-wallobstaclesCreateatiledsearchareaSpid49AdjacenttilestoconsiderWeproceedtocheckeachoftheeightadjacenttilesandthenaddeachvalidtiletotheopenlist.对与蜘蛛相邻的八个点检查，不在任何表中和不是障碍的点加入OpenList表中。AdjacenttilestoconsiderWep50将开始点移到ClosedList表中

MovingthestartingtiletotheclosedlistStartpoint开始点将开始点移到ClosedList表中

Movingthe51LinkingtotheparentsLinktoparentsLinkingtotheparentsLinkto52赋予数值

ScoringWewillusepathscoringtodeterminethebestpathfromthestartingtiletothedestinationtile.(1)Welookatthecosttomovefromthestartingtiletoanygiventile.(2)Welookatthecosttomovefromthegiventiletothedestinationtile.(3)Wetakethesumofthecostofeachtilethatleadsbacktotheinitiallocation.赋予数值

ScoringWewillusepaths53CalculatingthepathscoreScore=Costfromstart+HeuristicWewillcheckthetileswiththelowestcost.Alowercostwillequatetoashorterpath.StartpointgivenpointdestinationCostfromstartheuristicCalculatingthepathscoreScor54InitialtilepathscoresInitialtilepathscores55初始化每一点的数值

InitialtilepathscoresThesvalueisthecostofgettingtherefromthestartingtile.s=从开始点到当前点的累计代价值Thehvalueistheheuristicwhichisanestimateofthenumberofstepsfromthegiventiletothedestinationtile.h=从当前点到目标点的步数值Thecvalueisthesumofsandh.c=s+h初始化每一点的数值

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区域代价值

TerrainCostTheshortestpathisn’talwaysthefastestpath.最短路径不一定是最快路径。Alongwalkalongaroadmightbefasterthanashorterwalkthroughaswamp.如有沼泽地的情况。区域代价值

TerrainCostTheshortest68对区域代价赋予数值

ScoringwithterraincostTotalcostfromstart=costfromstart+terraincostScore=totalcostfromstart+heuristic每一点总代价值=从开始点到当前点的累计代价值+区域代价值+启发式数值。对区域代价赋予数值

Scoringwithterrain69区域的种类

TypesofterrainOpenterrain平坦区域Cost=1Grassland草地Cost=3Swampland沼泽地Cost=5区域的种类

TypesofterrainOpenter70AddingdifferentterrainelementsAddingdifferentterraineleme71OriginalpathoverterrainelementsOriginalpathoverterrainele72Calculatingthelowest-costpathCalculatingthelowest-costpa73Thelowest-costpathThelowest-costpath74Inf