人工智能课件第四次课.ppt

人工智能课件第四次课.ppt

《人工智能课件第四次课.ppt》由会员分享，可在线阅读，更多相关《人工智能课件第四次课.ppt（63页珍藏版）》请在冰点文库上搜索。

基本路径搜索和航点应用BasicPathfindingandWaypoints,Atitsmostbasiclevel,pathfindingissimplytheprocessofmovingthepositionofagamecharacterfromitsinitiallocationtoadesireddestination.基本路径搜索是从初始位置移动到目标位置的过程。

基本路径搜索Basicpathfindingalgorithm,if（positionXdestinationX）positionX-;elseif（positionXdestinationY）positionY-；elseif（positionYdestinationY）positionY+;,限制条件Somelimitations,Simplepathmovement,Line-of-sightpathmovement,障碍问题Problemswithobstacles,

（1）随机运动避开障碍RandomMovementObstacleAvoidance,Randommovementcanbeasimpleandeffectivemethodofobstacleavoidance.随机运动能够简单而有效地解决避开障碍。

Randommovementobstacleavoidancealgorithm,ifplayerinlineofsightfollowingstraightpathtoplayerelsemoveinrandomdirection,

（2）围绕障碍物的追踪TracingAroundObstacles,Thismethodcanbeeffectivewhenattemptingtofindapatharoundlargeobstacles,suchasamountainrangeinastrategyorrole-playinggame.解决围绕大障碍物寻找路径的问题。

基本追踪Basictracing,Computer-controlledcharacter,Itsgoal,存在的问题Problemwithtracing,Decidingwhentostoptracing?

什么时候停止追踪？

Weneedawaytodeterminewhenweshouldswitchfromthetracingstatebacktoasimplepathfindingstate.如何从追踪状态转换为路径搜索状态？

Onewayofaccomplishingthisistocalculatealinefromthepointthetracingstartstothedesireddestination.解决方法-计算从追踪开始点到目标点的直线距离。

改进的追踪Improvedtracing,改进的追踪Improvedtracing,Tracingtheoutskirtsoftheobstacleuntilthelineconnectingthestartingpointanddesireddestinationiscrossedensuresthatthepathdoesntloopbacktothestaringpoint.沿着障碍物外围追踪时，穿过障碍物连接开始点和目标点，防止追踪路径又回到起点。

视线追踪Tracingwithlineofsight,视线追踪Tracingwithlineofsight,Wefollowtheoutskirtsoftheobstacle,butateachstepwechecktoseeifthedestinationisinthecomputer-controlledcharacterslineofsight.每一步检测是否处在视线之内。

Ifso,weswitchfromatracingstatetoaline-of-sightpathfindingstate.处在视线之内，路径搜索从追踪状态转换为视线搜索状态。

（3）标记路径搜索BreadcrumbPathfinding,Breadcrumbpathfindingcanmakecomputer-controlledcharactersseemveryintelligentbecausetheplayerisunknowinglycreatingthepathforthecomputer-controlledcharacter.带标记的路径搜索是玩家无意地留下轨迹。

Eachtimetheplayertakesastep,heunknowinglyleavesaninvisiblemarker,orbreadcrumb,onthegameworld.每次玩家走一步，它就留下一个不可见的标记。

Breadcrumbtrail,Atrollrandomlymovesaboutthetile-basedenvironmentuntilitdetectsabreadcrumbonanadjacentlocation.,ai_Entityclass,#definekMaxTrailLength15classai_Entitypublic:

introw;intcol;inttype;intstate;inttrailRowkMaxTrailLength;inttrailColkMaxTrailLength;ai_Entity（）;ai_Entity（）;,变量说明,#definestatementsetsthemaximumnumberofplayerstepstotrack.设置kMaxTrailLength为玩家标记轨迹的最大步骤数。

trailRow,trailColarraysstoretherowandcolumncoordinatesoftheprevious15stepstakenbytheplayer.trailRow,trailCol保存由玩家标记的15步的横、纵坐标。

标记数组的初始化Trailarrayinitialization,inti;for（i=0;ikMaxTrailLength;i+）trailRowi=-1;trailColi=-1;,记录玩家的位置Recordingtheplayerpositions,voidai_World:

KeyDown（intkey）inti;if（key=kUpKey）for（i=0;i0）entityListi.row-;DropBreadCrumb（）;,if（key=kDownKey）for（i=0;ikMaxEntities;i+）if（entityListi.state=kPlayer）if（entityListi.row=kMaxRows-1）entityListi.row+;DropBreadCrumb（）;,if（key=kLeftKey）for（i=0;i0）entityListi.col-;DropBreadCrumb（）;if（key=kRightKey）for（i=0;ikMaxEntities;i+）if（entityListi.state=kPlayer）if（entityListi.colkMaxCols-1）entityListi.col+;DropBreadCrumb（）;,设置标记DroppingabreadCrumb,voidai_World:

DropBreadCrumb（void）inti;for（i=kMaxTrailLength-1;i-）entityList0.trailRowi=entityList0.trailRowi-1;entityList0.trailColi=entityList0.trailColi-1;entityList0.trailRow0=entityList0.row;entityList0.trailCol0=entityList0.Col;,追踪标记Followingthebreadcrumbs,Thegoalistodetermineifanyoftheeightpositionsadjacenttothecomputer-controlledtrollcontainabreadcrumb.是否在八个相邻方向之一中有标记。

Followingthebreadcrumbs,for（i=0;ikMaxEntities;i+）r=entityListi.row;c=entityListi.col;foundCrumb=-1;for（j=0;jkMaxTrailLength;j+）if（r=entityList0.trailRowj）,if（r-1=entityList0.trailRowj）,if（r=entityList0.trailRowj）,if（foundCrumb=0）entityListi.row=entityList0.trailRowfoundCrumb;entityListi.col=entityList0.trailColfoundCrumb;elseentityListi.row=entityList0.row+Rnd（0,2）-1;entityListi.col=entityList0.col+Rnd（0,2）-1;if（entityListi.row=kMaxRows）entityListi.row=kMaxRows-1;if（entityListi.col=kMaxCols）entityListi.col=kMaxCols-1;,Followingtheshortestpath,12,11,10,9,8,7,6,2,?

（4）PathFollowing,Itisnecessarytomovecomputer-controlledcharactersinagameenvironmentinarealisticwayeventhoughtheymightnothaveanultimatedestination.没有目的地的移动Car-racinggame赛车navigatearoadwaywantthecarstostayontheroad,PathFollowing,2-road1-outofbounds,地域分析Terrainanalysis,Weneedtoanalyzethesurroundingterrainanddecideonthebestmove.分析周围的地域并决定选取最佳移动。

Weexaminealleightdirectionsandtheneliminatethosethatarenotpartoftheroad.对八个方向检测，消除不在路上的部分。

Theproblembecomesoneofdecidingwhichoftheremainingdirectionstotake.决定选取哪一个方向移动？

地域分析Terrainanalysis,intr;intc;intterrainAnalysis9;r=entityListi.row;c=entityListi.col;terrainAnalysis1=terrainr-1c-1;terrainAnalysis2=terrainr-1c;terrainAnalysis3=terrainr-1c+1;terrainAnalysis4=terrainrc+1;terrainAnalysis5=terrainr+1c+1;terrainAnalysis6=terrainr+1c;terrainAnalysis7=terrainr+1c-1;terrainAnalysis8=terrainrc-1;,for（j=1;j=8;j+）if（terrainAnalysisj=1）terrainAnalysisj=0;elseterrainAnalysisj=10;,Possibledirections,Directionanalysis,if（entityListi.direction=1）terrainAnalysis1=terrainAnalysis1+2;terrainAnalysis2+;terrainAnalysis5-;terrainAnalysis8+;if（entityListi.direction=2）terrainAnalysis1+;terrainAnalysis2=terrainAnalysis2+2;terrainAnalysis3+;terrainAnalysis6-;,if（entityListi.direction=3）terrainAnalysis2+;terrainAnalysis3=terrainAnalysis3+2;terrainAnalysis4+;terrainAnalysis7-;if（entityListi.direction=4）terrainAnalysis3+;terrainAnalysis4=terrainAnalysis4+2;terrainAnalysis5+;terrainAnalysis7-;if（entityListi.direction=5）terrainAnalysis4+;terrainAnalysis5=terrainAnalysis5+2;terrainAnalysis6+;terrainAnalysis8-;,if（entityListi.direction=6）terrainAnalysis2-;terrainAnalysis5+;terrainAnalysis6=terrainAnalysis6+2;terrainAnalysis7+;if（entityListi.direction=7）terrainAnalysis3-;terrainAnalysis6+;terrainAnalysis7=terrainAnalysis7+2;terrainAnalysis8+;if（entityListi.direction=8）terrainAnalysis1+;terrainAnalysis4-;terrainAnalysis7+;terrainAnalysis8=terrainAnalysis8+2;,Weightingdirections,Thisenablesustogiveaddedweighttothepreviousdirectionwheneveritistimetoupdatethetrollsposition.当角色更新到新的位置时，对前一次的方向加一权值。

Choosingadirection,maxTerrain=0;maxIndex=0;for（j=1;jmaxTerrain）maxTerrain=terrainAnalysisj;maxIndex=j;,寻找最大值作为可能的方向。

更新位置Updateposition,if（maxIndex=1）entityList.direction=1;entityListi.row-;entityListi.col-;if（maxIndex=2）entityList.direction=2;entityListi.row-;,if（maxIndex=3）entityList.direction=3;entityListi.row-;entityListi.col+;if（maxIndex=4）entityList.direction=2;entityListi.col+;if（maxIndex=5）entityList.direction=5;entityListi.row+;entityListi.col+;,if（maxIndex=6）entityList.direction=6;entityListi.row+;if（maxIndex=7）entityList.direction=6;entityListi.row+;entityListi.col-;if（maxIndex=8）entityList.direction=8;entityListi.col-;,RoadPath,（5）WallTracing,Walltracingismoreofanexplorationtechnique.Itsmostusefulingameenvironmentsmadeofmanysmallrooms,althoughyoucanuseitinmaze-likegameenvironmentsaswell.通常运用在一些小房子或迷宫游戏中。

WallTracing,左手方法Lefthandedapproach,Abetterapproachwouldbetomakethetrollsystematicallyexploretheentireenvironment.最好是能够系统地遍历整个环境。

Ifthetrollalwaysmovestoitsleft,itwilldoathoroughjobofexploringitsenvironment.设定巡视者总是向左移动。

面向玩家的右侧Facingplayersright,左手移动方法lefthandedmovementapproach,Thetrollalwayswilltrytomovetoitsleftfirst.总是沿着左侧移动。

Ifitcantmovetoitsleft,itwilltrytomovestraightahead.不能转向左侧时，直行。

Ifthatisblocked,itwilltrytomovetoitsrightnext.如果是障碍，移向右侧。

Ifthatisblocked,itwillreversedirection.如果是障碍，移向相反方向。

Left-handedmovement,r=entityListi.row;c=entityListi.col;if（entityListi.direction=4）if（terrainr-1c=1）entityListi.row-;entityListi.direction=2;elseif（terrainrc+1=1）entityListi.col+;entityListi.direction=4;,elseif（terrainr+1c=1）entityListi.row+;entityListi.direction=6;elseif（terrainrc-1=1）entityListi.col-;entityListi.direction=8;,elseif（entityListi.direction=6）if（terrainrc+1=1）entityListi.col+;entityListi.direction=4;elseif（terrainr+1c=1）entityListi.row+;entityListi.direction=6;,elseif（terrainrc-1=1）entityListi.col-;entityListi.direction=8;elseif（terrainr-1c=1）entityListi.row-;entityListi.direction=2;,elseif（entityListi.direction=8）if（terrainr+1c=1）entityListi.row+;entityListi.direction=6;elseif（terrainrc-1=1）entityListi.col-;entityListi.direction=8;,elseif（terrainr-1c=1）entityListi.row-;entityListi.direction=2;elseif（terrainrc+1=1）entityListi.col+;entityListi.direction=4;,elseif（entityListi.direction=2）if（terrainrc-1=1）entityListi.col-;entityListi.direction=8;elseif（terrainr-1c=1）entityListi.row-;entityListi.direction=2;,elseif（terrainrc+1=1）entityListi.col+;entityListi.direction=4;elseif（terrainr+1c=1）entityListi.row+;entityListi.direction=6;,Relativedirections,Thisrequiresbecausethetiletothetrollsleftisdependentonthedirectionitsfacing.巡视者的左边依赖于它的朝向。

Wall-tracingpath,（6）WaypointNavigation航点导航,PlacingnodesEverypointonthemapisinthelineofsightofatleastonenode.,Labelingnodes,Buildingapath,Emptynodetable,Fillinginthenodetable,Completednodetable,Findingthepath,小结,RandomMovementObstacleAvoidance随机移动避开障碍物TracingAroundObstacles绕行障碍物BreadcrumbPathfinding以面包屑寻找路径PathFollowing遵循路径走WallTracing沿着墙走WaypointNavigation航点导航,思考题,在基本路径搜索中障碍物较少情况下采用了什么方式解决避开障碍物问题？

为什么必须在较少障碍物情况使用这种方式？

视线追踪与穿过障碍算得的直线追踪方式有何不同？

哪一个更好一些？

为什么？

在RoadPath中利用权值方式有什么好处？

不使用会采用何种方式处理不同可能方向？

本次实验,设计一、二个障碍，并实现如何避开障碍寻找目标点；最好实现Tracingwithlineofsight,可以结合BresenhamAlgorithm算法。

可以尝试一下BreadcrumbPathfinding的思想。

可利用二维数组形式实现Waypoint方法。