人工智能ppt课件第五次课

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.Weareusing